Fair Division with Prioritized Agents

Authors

  • Xiaolin Bu Shanghai Jiao Tong University
  • Zihao Li Nanyang Technological University
  • Shengxin Liu Harbin Institute of Technology, Shenzhen
  • Jiaxin Song Shanghai Jiao Tong University
  • Biaoshuai Tao Shanghai Jiao Tong University

DOI:

https://doi.org/10.1609/aaai.v37i5.25688

Keywords:

GTEP: Fair Division

Abstract

We consider the fair division problem of indivisible items. It is well-known that an envy-free allocation may not exist, and a relaxed version of envy-freeness, envy-freeness up to one item (EF1), has been widely considered. In an EF1 allocation, an agent may envy others' allocated shares, but only up to one item. In many applications, we may wish to specify a subset of prioritized agents where strict envy-freeness needs to be guaranteed from these agents to the remaining agents, while ensuring the whole allocation is still EF1. Prioritized agents may be those agents who are envious in a previous EF1 allocation, those agents who belong to underrepresented groups, etc. Motivated by this, we propose a new fairness notion named envy-freeness with prioritized agents EFprior, and study the existence and the algorithmic aspects for the problem of computing an EFprior allocation. With additive valuations, the simple round-robin algorithm is able to compute an EFprior allocation. In this paper, we mainly focus on general valuations. In particular, we present a polynomial-time algorithm that outputs an EFprior allocation with most of the items allocated. When all the items need to be allocated, we also present polynomial-time algorithms for some well-motivated special cases.

Downloads

Published

2023-06-26

How to Cite

Bu, X., Li, Z., Liu, S., Song, J., & Tao, B. (2023). Fair Division with Prioritized Agents. Proceedings of the AAAI Conference on Artificial Intelligence, 37(5), 5540-5548. https://doi.org/10.1609/aaai.v37i5.25688

Issue

Section

AAAI Technical Track on Game Theory and Economic Paradigms