17 papers
Fairness and Non-wastefulness in Matching with Siblings and Initial Enrollments: Compatibility and Complexity
Haris Aziz, Gergely Csáji, Zhaohong Sun +1
We study a two-sided matching problem between families and daycare centers in which a family may have multiple children with joint preferences, and some children may already be enr…
MLN-EIGS: A multilayer network framework for solving Stackelberg escape interdiction games on dynamic transportation networks
Sukanya Samanta, Kei Kimura, Makoto Yokoo +1
Interdicting an escaping criminal with limited police resources on large-scale transportation networks is a challenging problem due to the dynamic nature of both attacker movement…
Compatible -Relaxations of Fairness and Non-Wastefulness Under Hereditary Constraints
Tenma Wakasugi, Zhaohong Sun, Kei Kimura +1
We study two-sided matching markets under hereditary constraints, which extend beyond simple capacity limits and arise in applications such as diversity requirements and refugee re…
A New Relaxation of Fairness in Two-Sided Matching Respecting Acquaintance Relationships
Ryota Takeshima, Kei Kimura, Ayumu Kuroki +2
Two-sided matching, such as matching between students and schools, has been applied to various aspects of real life and has been the subject of much research, however, it has been…
Coalitions on the Fly in Cooperative Games
Yao Zhang, Indrajit Saha, Zhaohong Sun +1
In this work, we examine a sequential setting of a cooperative game in which players arrive dynamically to form coalitions and complete tasks either together or individually, depen…
COBRA: Contextual Bandit Algorithm for Ensuring Truthful Strategic Agents
Arun Verma, Indrajit Saha, Makoto Yokoo +1
This paper considers a contextual bandit problem involving multiple agents, where a learner sequentially observes the contexts and the agent's reported arms, and then selects the a…
Whoever Said Money Won't Solve All Your Problems? Weighted Envy-free Allocation with Subsidy
Noga Klein Elmalem, Haris Aziz, Rica Gonen +7
We explore solutions for fairly allocating indivisible items among agents assigned weights representing their entitlements. Our fairness goal is weighted-envy-freeness (WEF), where…
Probabilistic Analysis of Stable Matching in Large Markets with Siblings
Zhaohong Sun, Tomohiko Yokoyama, Makoto Yokoo
We study a practical centralized matching problem which assigns children to daycare centers. The collective preferences of siblings from the same family introduce complementarities…
Achieving Balanced Representation in School Choice with Diversity Goals
Zhaohong Sun, Makoto Yokoo
Student placements under diversity constraints are a common practice globally. This paper addresses the selection of students by a single school under a \emph{one-to-one convention…
Parameterized Voter Relevance in Facility Location Games with Tree-Shaped Invitation Graphs
Ryoto Ando, Kei Kimura, Taiki Todo +1
Diffusion mechanism design, which investigate how to incentivise agents to invite as many colleagues to a multi-agent decision making as possible, is a new research paradigm at the…
Analyzing Incentives and Fairness in Ordered Weighted Average for Facility Location Games
Kento Yoshida, Kei Kimura, Taiki Todo +1
Facility location games provide an abstract model of mechanism design. In such games, a mechanism takes a profile of single-peaked preferences over an interval as an input and…
Keep Everyone Happy: Online Fair Division of Numerous Items with Few Copies
Arun Verma, Indrajit Saha, Makoto Yokoo +1
This paper considers a novel variant of the online fair division problem involving multiple agents in which a learner sequentially observes an indivisible item that must be irrevoc…
Weighted Envy-free Allocation with Subsidy
Haris Aziz, Xin Huang, Kei Kimura +4
We consider the problem of fair allocation of indivisible items with subsidies when agents have weighted entitlements. After highlighting several important differences from the unw…
Solving a Stackelberg Game on Transportation Networks in a Dynamic Crime Scenario: A Mixed Approach on Multi-Layer Networks
Sukanya Samanta, Kei Kimura, Makoto Yokoo +1
Interdicting a criminal with limited police resources is a challenging task as the criminal changes location over time. The size of the large transportation network further adds to…
Online -Convex Minimization
Ken Yokoyama, Shinji Ito, Tatsuya Matsuoka +2
An online decision-making problem is a learning problem in which a player repeatedly makes decisions in order to minimize the long-term loss. These problems that emerge in applicat…
Fairness and efficiency trade-off in two-sided matching
Sung-Ho Cho, Kei Kimura, Kiki Liu +5
The theory of two-sided matching has been extensively developed and applied to many real-life application domains. As the theory has been applied to increasingly diverse types of e…
Stable Matchings in Practice: A Constraint Programming Approach
Zhaohong Sun, Naoyuki Yamada, Yoshihiro Takenami +2
We study a practical two-sided matching problem of allocating children to daycare centers, which has significant social implications. We are cooperating with several municipalities…