[2J5-GS-5] Agents:

[2J5-GS-5-02] Local envy freeness and lattice structure in two-sided matching

〇Ayumu Kuroki¹, Kei Kimura¹, Ryota Takeshima¹, Makoto Yokoo¹ (1. Univ. of Kyushu)

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

For two-sided matching problems such as the stable marriage problem, college admission, and resident assignment, it is known that the Gale-Shapley algorithm can be used to find the one-sided optimal matching in polynomial time. The fact that one-sided optimal matching exists is derived from the fact that the stable matching set has a mathematical structure called a lattice. On the other hand, in an actual matching market, it may be considered more natural for envy to occur only for acquaintances (neighbors). For this reason, Takeshima et al. proposed to define the property that envy toward neighbors does not exist as local envy-freeness. Neighborhood relations can be represented by an undirected graph. In this paper, we discuss the impact of the structure of this graph and restrictions on the preferences of the matching participants on the possession of the lattice structure of the matching set that satisfies local envy freeness.