Language：Japanese   Publisher：The Japanese Society for Artificial Intelligence  

<p>The theory of two-sided matching has been extensively developed, and it is hoped that matching will reduce students' envies and improve overall welfare. However, it turns out that there exists a trade-off between efficiency and fairness. Therefore, keeping fairness at a certain level that can be applied in the real world also leads to increased efficiency. Our contribution is to establish a weaker fairness requirement called reverse Envy-Freeness from up to k peers (r-EF-k). r-EF-k requires that each student is envied by at most k students. By varying k, r-EF-k can represent different levels of fairness. We discuss mechanism that satisfy r-EF-k and certain efficiency properties.</p>

DOI： 10.11517/pjsai.jsai2024.0_2f6gs501

CiNii Research

Publisher：Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS  

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 environments, researchers and practitioners have encountered various forms of distributional constraints. As a mechanism can handle a more general class of constraints, we can assign students more flexibly to colleges to increase students' welfare. However, it turns out that there exists a trade-off between students' welfare (efficiency) and fairness (which means no student has justified envy). Furthermore, this trade-off becomes sharper as the class of constraints becomes more general. The first contribution of this paper is to clarify the boundary on whether a strategyproof and fair mechanism can satisfy certain efficiency properties for each class of constraints. Our second contribution is to establish a weaker fairness requirement called envy-freeness up to k peers (EF-k), which is inspired by a similar concept used in the fair division of indivisible items. EF-k guarantees that each student has justified envy towards at most k students. By varying k, EF-k can represent different levels of fairness. We investigate theoretical properties associated with EF-k. Furthermore, we develop two contrasting strategyproof mechanisms that work for general hereditary constraints, i.e., one mechanism can guarantee a strong efficiency requirement, while the other can guarantee EF-k for any fixed k. We evaluate the performance of these mechanisms through computer simulation.

Scopus

Publisher：Proceedings of the 37th AAAI Conference on Artificial Intelligence, AAAI 2023  

In this paper, we study a daycare matching problem in Japan and report the design and implementation of a new centralized algorithm. There are two features that make this market different from the classical hospital-doctor matching problem: i) some children are initially enrolled and prefer to be transferred to other daycare centers; ii) one family may be associated with two or more children and is allowed to submit preferences over combinations of daycare centers. We revisit some well-studied properties including individual rationality, non-wastefulness, as well as stability, and generalize them to this new setting. We design an algorithm based on integer programming (IP) that captures these properties and conduct experiments on five real-life data sets provided by three municipalities. Experimental results show that i) our algorithm performs at least as well as currently used methods in terms of numbers of matched children and blocking coalition; ii) we can find a stable outcome for all instances, although the existence of such an outcome is not guaranteed in theory.

DOI： 10.1609/aaai.v37i12.26694

Scopus

Publisher：Proceedings of the 37th AAAI Conference on Artificial Intelligence, AAAI 2023  

We study a fair allocation problem of indivisible items under additive externalities in which each agent also receives utility from items that are assigned to other agents. This allows us to capture scenarios in which agents benefit from or compete against one another. We extend the well-studied properties of envy-freeness up to one item (EF1) and envy-freeness up to any item (EFX) to this setting, and we propose a new fairness concept called general fair share (GFS), which applies to a more general public decision making model. We undertake a detailed study and present algorithms for finding fair allocations.

Scopus

Publisher：Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS  

Selection under category or diversity constraints is a ubiquitous and widely-applicable problem that is encountered in immigration, school choice, hiring, and healthcare rationing. These diversity constraints are typically represented by minimum and maximum quotas on various categories or types. We undertake a detailed comparative study of applicant selection algorithms with respect to the diversity goals.

Scopus

Language：English  

Language：English  

Language：English  

Language：English  

Language：English  

Language：English  

Language：English  

Language：English