Control of Fair Division

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. PDF