16 citations · 33 across the 10 of their papers we have counts for
10 papers
Sensitivity and Differential Privacy in Metric Voting with Distortion below Three
Shinsaku Sakaue, Kaito Fujii, Soh Kumabe +1
Voting rules aggregate individual preferences into collective decisions, but the rankings they receive contain only ordinal information. The metric distortion framework studies ord…
The Secretary Problem with Predictions
Kaito Fujii, Yuichi Yoshida
The value maximization version of the secretary problem is the problem of hiring a candidate with the largest value from a randomly ordered sequence of candidates. In this work, we…
Bayes correlated equilibria, no-regret dynamics in Bayesian games, and the price of anarchy
Kaito Fujii
This paper investigates equilibrium computation and the price of anarchy for Bayesian games, which are the fundamental models of games with incomplete information. In normal-form g…
Lazy and Fast Greedy MAP Inference for Determinantal Point Process
Shinichi Hemmi, Taihei Oki, Shinsaku Sakaue +2
The maximum a posteriori (MAP) inference for determinantal point processes (DPPs) is crucial for selecting diverse items in many machine learning applications. Although DPP MAP inf…
Algorithmic Bayesian persuasion with combinatorial actions
Kaito Fujii, Shinsaku Sakaue
Bayesian persuasion is a model for understanding strategic information revelation: an agent with an informational advantage, called a sender, strategically discloses information by…
Approximation Guarantees of Local Search Algorithms via Localizability of Set Functions
Kaito Fujii
This paper proposes a new framework for providing approximation guarantees of local search algorithms. Local search is a basic algorithm design technique and is widely used for var…
An improved algorithm for the submodular secretary problem with a cardinality constraint
Kaito Fujii
We study the submodular secretary problem with a cardinality constraint. In this problem, candidates for secretaries appear sequentially in random order. At the arrival of each…
Beyond Adaptive Submodularity: Approximation Guarantees of Greedy Policy with Adaptive Submodularity Ratio
Kaito Fujii, Shinsaku Sakaue
We propose a new concept named adaptive submodularity ratio to study the greedy policy for sequential decision making. While the greedy policy is known to perform well for a wide v…
Fast greedy algorithms for dictionary selection with generalized sparsity constraints
Kaito Fujii, Tasuku Soma
In dictionary selection, several atoms are selected from finite candidates that successfully approximate given data points in the sparse representation. We propose a novel efficien…
Polynomial-Time Algorithms for Submodular Laplacian Systems
Kaito Fujii, Tasuku Soma, Yuichi Yoshida
Let be an undirected graph, be the associated Laplacian matrix, and be a vector. Solving the Laplacian system $L_G x…