2 citations · 7 across the 15 of their papers we have counts for
8 papers · 1 filter
Solving the Maximum Popular Matching Problem with Matroid Constraints
Gergely Csáji, Tamás Király, Yu Yokoi
We consider the problem of finding a maximum popular matching in a many-to-many matching setting with two-sided preferences and matroid constraints. This problem was proposed by Ka…
Maximum Stable Matching with Matroids and Partial Orders
Gergely Csáji, Tamás Király, Yu Yokoi
The Stable Marriage problem (SM), solved by the famous deferred acceptance algorithm of Gale and Shapley (GS), has many natural generalizations. If we allow ties in preferences, th…
Random Assignment of Indivisible Goods under Constraints
Yasushi Kawase, Hanna Sumita, Yu Yokoi
We investigate the problem of random assignment of indivisible goods, in which each agent has an ordinal preference and a constraint. Our goal is to characterize the conditions und…
Incomplete List Setting of the Hospitals/Residents Problem with Maximally Satisfying Lower Quotas
Kazuhisa Makino, Shuichi Miyazaki, Yu Yokoi
To mitigate the imbalance in the number of assignees in the Hospitals/Residents problem, Goko et al. [Goko et al., Maximally Satisfying Lower Quotas in the Hospitals/Residents Prob…
Fair and Truthful Mechanism with Limited Subsidy
Hiromichi Goko, Ayumi Igarashi, Yasushi Kawase +5
The notion of \emph{envy-freeness} is a natural and intuitive fairness requirement in resource allocation. With indivisible goods, such fair allocations are unfortunately not guara…
Maximally Satisfying Lower Quotas in the Hospitals/Residents Problem with Ties
Hiromichi Goko, Kazuhisa Makino, Shuichi Miyazaki +1
Motivated by the serious problem that hospitals in rural areas suffer from a shortage of residents, we study the Hospitals/Residents model in which hospitals are associated with lo…
Subgame Perfect Equilibria of Sequential Matching Games
Yasushi Kawase, Yutaro Yamaguchi, Yu Yokoi
We study a decentralized matching market in which firms sequentially make offers to potential workers. For each offer, the worker can choose "accept" or "reject," but the decision…
Envy-free Matchings with Lower Quotas
Yu Yokoi
While every instance of the Hospitals/Residents problem admits a stable matching, the problem with lower quotas (HR-LQ) has instances with no stable matching. For such an instance,…