出版者・発行元：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

記述言語：日本語   出版者・発行元：一般社団法人 人工知能学会  

<p>本論文では，時間の経過に伴い選好が変化する状況を捉えることのできる，2 期間を通じた両方向マッチングを考察する．このようなモデルでは，各期間で異なるエージェントとマッチングすることが可能である．従来の研究では，いずれの期間においても，エージェント一人，あるいはエージェントのペアが結託することで得をするようなことがないマッチングを動的安定なマッチングとして定義している． 本論文では，2 期間マッチングにおける新たな公平性および非浪費性，個人合理性を定義し，動的安定性との関係性について考察する．また，定義した公平性と非浪費性を同時に満たすマッチングの存在性について議論する．</p>

DOI： 10.11517/pjsai.jsai2024.0_1i3gs501

CiNii Research

出版者・発行元：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

出版者・発行元：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

出版者・発行元：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

記述言語：英語  

記述言語：英語  

記述言語：英語  

記述言語：英語  

記述言語：英語  

記述言語：英語  

記述言語：英語  

記述言語：英語