The Complexity of Extending Fair Allocations of Indivisible Goods
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915179786141696 |
|---|---|
| author | Deligkas, Argyrios Eiben, Eduard Ganian, Robert Goldsmith, Tiger-Lily Ioannidis, Stavros D. |
| author_facet | Deligkas, Argyrios Eiben, Eduard Ganian, Robert Goldsmith, Tiger-Lily Ioannidis, Stavros D. |
| contents | We initiate the study of computing envy-free allocations of indivisible items in the extension setting, i.e., when some part of the allocation is fixed and the task is to allocate the remaining items. Given the known NP-hardness of the problem, we investigate whether -- and under which conditions -- one can obtain fixed-parameter algorithms for computing a solution in settings where most of the allocation is already fixed. Our results provide a broad complexity-theoretic classification of the problem which includes: (a) fixed-parameter algorithms tailored to settings with few distinct types of agents or items; (b) lower bounds which exclude the generalization of these positive results to more general settings. We conclude by showing that -- unlike when computing allocations from scratch -- the non-algorithmic question of whether more relaxed EFX allocations exist can be completely resolved in the extension setting. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_01368 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Complexity of Extending Fair Allocations of Indivisible Goods Deligkas, Argyrios Eiben, Eduard Ganian, Robert Goldsmith, Tiger-Lily Ioannidis, Stavros D. Computer Science and Game Theory Data Structures and Algorithms 91B32 F.2.2 We initiate the study of computing envy-free allocations of indivisible items in the extension setting, i.e., when some part of the allocation is fixed and the task is to allocate the remaining items. Given the known NP-hardness of the problem, we investigate whether -- and under which conditions -- one can obtain fixed-parameter algorithms for computing a solution in settings where most of the allocation is already fixed. Our results provide a broad complexity-theoretic classification of the problem which includes: (a) fixed-parameter algorithms tailored to settings with few distinct types of agents or items; (b) lower bounds which exclude the generalization of these positive results to more general settings. We conclude by showing that -- unlike when computing allocations from scratch -- the non-algorithmic question of whether more relaxed EFX allocations exist can be completely resolved in the extension setting. |
| title | The Complexity of Extending Fair Allocations of Indivisible Goods |
| topic | Computer Science and Game Theory Data Structures and Algorithms 91B32 F.2.2 |
| url | https://arxiv.org/abs/2503.01368 |