Fair Division with Two-Sided Preferences

Fair Division with Two-Sided Preferences

Ayumi Igarashi, Yasushi Kawase, Warut Suksompong, Hanna Sumita

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence
Main Track. Pages 2756-2764. https://doi.org/10.24963/ijcai.2023/307

We study a fair division setting in which a number of players are to be fairly distributed among a set of teams. In our model, not only do the teams have preferences over the players as in the canonical fair division setting, but the players also have preferences over the teams. We focus on guaranteeing envy-freeness up to one player (EF1) for the teams together with a stability condition for both sides. We show that an allocation satisfying EF1, swap stability, and individual stability always exists and can be computed in polynomial time, even when teams may have positive or negative values for players. Similarly, a balanced and swap stable allocation that satisfies a relaxation of EF1 can be computed efficiently. When teams have nonnegative values for players, we prove that an EF1 and Pareto optimal allocation exists and, if the valuations are binary, can be found in polynomial time. We also examine the compatibility between EF1 and justified envy-freeness.
Keywords:
Game Theory and Economic Paradigms: GTEP: Fair division
Game Theory and Economic Paradigms: GTEP: Computational social choice