Control of Fair Division
Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 67-72.
Abstract
We initiate the study of control actions in fair division problems where a benevolent or malicious central organizer changes the structure of the fair division problem for self-interest or to benefit one, some or all agents. One motivation for such control is to improve fairness by minimally changing the problem. As a case study, we consider the problem of adding or deleting a small number of items to improve fairness. For two agents, we present polynomial-time algorithms for adding or deleting the minimum number of items to achieve ordinal envy-freeness. For three agents, we show that both problems, as well as the more basic problem of checking whether an envy-free allocation exists, are NP-complete. This closes a problem open for over five years. Our framework leads to a number of interesting directions in the area of fair division.
@inproceedings{ijcai2016p17,
title = {Control of Fair Division},
author = {Aziz, Haris and Schlotter, Ildikó and Walsh, Toby},
booktitle = {Proceedings of the Twenty-Fifth International Joint Conference on
Artificial Intelligence, {IJCAI-16}},
publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
editor = {Subbarao Kambhampati},
pages = {67--72},
year = {2016},
month = {7},
url = {https://ijcai.org/proceedings/2016/17},
}
TY - CPAPER TI - Control of Fair Division AU - Aziz, Haris AU - Schlotter, Ildikó AU - Walsh, Toby T2 - Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16 PB - AAAI Press / International Joint Conferences on Artificial Intelligence PY - 2016 SP - 67 EP - 72 UR - https://ijcai.org/proceedings/2016/17 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
