Resilient Fair Allocation of Indivisible Goods

Fair allocation of indivisible goods has been studied extensively. However, the solutions offered to date are not resilient to subsequent changes that may occur after the allocation has been decided and executed, e.g., agents leaving the system, or additional goods are discovered. Currently, such settings require rerunning the allocation algorithm from scratch, potentially shifting most allocated goods between the agents. This can be cumbersome at best, or impossible at worst. In this paper, we study the notion of resilience, which quantifies the number of changes needed to resolve subsequent changes in the environment. We then apply it to the problem of fair allocation of indivisible goods, focusing on the EF1 and EFX solution concepts. For the EF1 solution concept, we provide constructive and efficient algorithms to restore EF1 after a simultaneous loss of goods, addition of new goods, and resignation of agents. We show that the addition of new agents cannot be resolved efficiently when the agents' valuation may be arbitrary. When agents have identical valuations, we show how to accept new agents efficiently. For the EFX solution concept, we (mostly) prove negative results, establishing that restoring EFX may be prohibitively costly, even for agents with identical valuations.