[2J5-GS-5] Agents:

[2J5-GS-5-01] Local envy-freeness and Efficiency in Two-sided matching

〇Ryota Takeshima¹, Kei Kimura¹, Makoto Yokoo¹ (1. Kyushu University)

Keywords:Mechanism design, Two-sided matching, Graph theory

Two-sided matching has been applied in various real-world situations, such as school choice systems and the assignment of medical residents, and has been extensively studied. However, based on its fundamental assumptions, it suffers from the problem where efficiency and fairness cannot be achieved simultaneously. In particular, the known impossibility theorem is based on the assumption that any student may feel justified envy toward any other student. However, in practice, it is often more natural to assume that students may feel justified envy only toward their acquaintances (neighbors). For this reason, Takeshima et al. proposed the definition of local envy-freeness as the property that there is no envy toward one's neighbors. In this context, neighbor relationships can be represented using an undirected graph. This study aims to investigate whether the trade-off between fairness and efficiency can be improved by restricting the structure of the graph. Specifically, it examines the degree of local envy-freeness achievable through a mechanism that satisfies pareto efficiency when applied to graphs with bounded treewidth.