Repeated Fair Allocation of Indivisible Items
Preprint
Abstract
The problem of fairly allocating a set of indivisible items is a well-known challenge in the field of (computational) social choice. In this scenario, there is a fundamental incompatibility between notions of fairness (such as envy-freeness and proportionality) and economic efficiency (such as Pareto-optimality). However, in the real world, items are not always allocated once and for all, but often repeatedly. For example, the items may be recurring chores to distribute in a household. Motivated by this, we initiate the study of the repeated fair division of indivisible goods and chores, and propose a formal model for this scenario. In this paper, we show that, if the number of repetitions is a multiple of the number of agents, there always exists a sequence of allocations that is proportional and Pareto-optimal. On the other hand, irrespective of the number of repetitions, an envy-free and Pareto-optimal sequence of allocations may not exist. For the case of two agents, we show that if the number of repetitions is even, it is always possible to find a sequence of allocations that is overall envy-free and Pareto-optimal. We then prove even stronger fairness guarantees, showing that every allocation in such a sequence satisfies some relaxation of envy-freeness. Finally, in case that the number of repetitions can be chosen freely, we show that envy-free and Pareto-optimal allocations are achievable for any number of agents.Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- Repeatedly matching items to agents fairly and efficientlyTheoretical Computer Science, 2023
- Fair division of indivisible goods: Recent progress and open questionsArtificial Intelligence, 2023
- Fair allocation of indivisible goods and choresAutonomous Agents and Multi-Agent Systems, 2021
- Best of Both Worlds: Ex-Ante and Ex-Post Fairness in Resource Allocation2020
- No Agent Left Behind: Dynamic Fair Division of Multiple ResourcesJournal of Artificial Intelligence Research, 2014
- Designing Random Allocation Mechanisms: Theory and ApplicationsAmerican Economic Review, 2013
- The undercut procedure: an algorithm for the envy-free division of indivisible itemsSocial Choice and Welfare, 2011
- Fair division of indivisible items between two people with identical preferences: Envy-freeness, Pareto-optimality, and equitySocial Choice and Welfare, 2000
- A procedure for divorce settlementsMediation Quarterly, 1996
- Integer Programming with a Fixed Number of VariablesMathematics of Operations Research, 1983