Fair Division in a Variable Setting
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915959819730944 |
|---|---|
| author | Chandramouleeswaran, Harish Nimbhorkar, Prajakta Rathi, Nidhi |
| author_facet | Chandramouleeswaran, Harish Nimbhorkar, Prajakta Rathi, Nidhi |
| contents | We study fair division of indivisible items under a variable input setting, where the set of agents or items may change over time. Starting from an arbitrary allocation, the goal is to restore envy-freeness up to one item (EF1) through item transfers while causing as little disruption as possible. We formalize this via `valid transfers' and introduce the EF1-Restoration problem.
We give efficient algorithms for EF1-Restoration when agents have identical monotone valuations and the items are either all goods or all chores. In contrast, even for identical additive valuations, we prove that optimizing the number of valid transfers is NP-hard. For the stronger notion of EFX, we show that deciding whether EFX-Restoration admits any positive solution is weakly NP-hard for identical additive valuations. We also show that, unlike the pure goods and pure chores cases, EF1-Restoration may be impossible for mixed manna.
For additive binary valuations, we prove that deciding whether EF1-Restoration is possible is NP-hard, and so is finding the minimum number of valid transfers when restoration is possible. We complement these hardness results with a polynomial-time algorithm for the subclass of additive binary valuations defined using multigraphs, introduced by Christodoulou et al. (EC 2023), when allocations are required to be orientations.
Finally, for monotone binary valuations, we prove that deciding whether EF1-Restoration is possible is PSPACE-complete. Together, our results give a broad complexity landscape for restoring EF1 under variable inputs across several natural valuation classes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_14421 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fair Division in a Variable Setting Chandramouleeswaran, Harish Nimbhorkar, Prajakta Rathi, Nidhi Computer Science and Game Theory Data Structures and Algorithms 91B32 (Primary), 91A68, 68Q25 F.2.2; I.2.11; J.4 We study fair division of indivisible items under a variable input setting, where the set of agents or items may change over time. Starting from an arbitrary allocation, the goal is to restore envy-freeness up to one item (EF1) through item transfers while causing as little disruption as possible. We formalize this via `valid transfers' and introduce the EF1-Restoration problem. We give efficient algorithms for EF1-Restoration when agents have identical monotone valuations and the items are either all goods or all chores. In contrast, even for identical additive valuations, we prove that optimizing the number of valid transfers is NP-hard. For the stronger notion of EFX, we show that deciding whether EFX-Restoration admits any positive solution is weakly NP-hard for identical additive valuations. We also show that, unlike the pure goods and pure chores cases, EF1-Restoration may be impossible for mixed manna. For additive binary valuations, we prove that deciding whether EF1-Restoration is possible is NP-hard, and so is finding the minimum number of valid transfers when restoration is possible. We complement these hardness results with a polynomial-time algorithm for the subclass of additive binary valuations defined using multigraphs, introduced by Christodoulou et al. (EC 2023), when allocations are required to be orientations. Finally, for monotone binary valuations, we prove that deciding whether EF1-Restoration is possible is PSPACE-complete. Together, our results give a broad complexity landscape for restoring EF1 under variable inputs across several natural valuation classes. |
| title | Fair Division in a Variable Setting |
| topic | Computer Science and Game Theory Data Structures and Algorithms 91B32 (Primary), 91A68, 68Q25 F.2.2; I.2.11; J.4 |
| url | https://arxiv.org/abs/2410.14421 |