Repeated Fair Allocation of Indivisible Items
Authors: Ayumi Igarashi, Martin Lackner, Oliviero Nardi, Arianna Novaro
AAAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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 Paretooptimal 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 envyfreeness. 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.Our main contribution is the definition of a new (offline) model for the repeated fair allocation of goods and chores, which we present in Section 2. In particular, we specify how sequences of allocations will be evaluated with respect to classical axioms of fairness and efficiency: we distinguish between sequences satisfying some axioms per-round (i.e., for every allocation composing them), or overall (i.e., when considering the collection of all the bundles every agent has received in the sequence). We consider two general cases: one where the number of repetitions is predetermined and given as part of the input and one where the number of repetitions can be chosen freely based on the instance. In the sequel, we refer to these as the fixed and variable cases, respectively. In Section 3, we study our model for a fixed number of rounds (k) with n agents. We show that: if the number of rounds is a multiple of n, we can always guarantee the existence of a sequence of allocations that is envy-free overall in (Proposition 4), and a sequence of allocations that is proportional and Pareto-optimal (Theorem 7). This is essentially optimal in two respects. First, for any number n 2 of agents and any fixed number k of rounds which is not a multiple of n, a sequence of allocations that is proportional overall may not exist (Proposition 5). Moreover, for any number n > 2 of agents and any fixed number k of rounds, there is an instance of chore allocation where an envy-free and Pareto-optimal sequence of allocations may not exist (Theorem 6). |
| Researcher Affiliation | Academia | Ayumi Igarashi1, Martin Lackner2, Oliviero Nardi2, Arianna Novaro3 1The University of Tokyo 2DBAI, TU Wien 3CES, University of Paris 1 Panth eon-Sorbonne |
| Pseudocode | Yes | Figure 1: An ILP for finding a proportional and PO allocation sequence for n agents. |
| Open Source Code | No | The paper does not provide any statement about releasing source code or a link to a code repository. |
| Open Datasets | No | The paper is theoretical and does not describe experiments using datasets. Therefore, no information about publicly available training data is provided. |
| Dataset Splits | No | The paper is theoretical and does not describe experiments using datasets or specify data splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not describe any hardware specifications used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not list specific software dependencies with version numbers. It refers to an 'integer linear program (ILP)' but does not specify a solver or its version. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with specific hyperparameters or training configurations. |