EUVIMEDEUVIMED entdecken
Crossref

The Complexity of Extending Fair Allocations of Indivisible Goods

Argyrios Deligkas, Eduard Eiben, Robert Ganian, Tiger-Lily Goldsmith, Stavros D. Ioannidis

Journal of Artificial Intelligence Research · 07.07.2026 · 86

DOI: 10.1613/jair.1.20353 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Artificial Intelligence Research, online erschienen am 07.07.2026. Verfasst von Argyrios Deligkas und 4 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 that 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.

Zitieren

APA

Deligkas, A., Eiben, E., Ganian, R., Goldsmith, T., & Ioannidis, S. D. (2026). The Complexity of Extending Fair Allocations of Indivisible Goods. Journal of Artificial Intelligence Research, 86. https://doi.org/10.1613/jair.1.20353

Vancouver

Deligkas A, Eiben E, Ganian R, Goldsmith T, Ioannidis SD. The Complexity of Extending Fair Allocations of Indivisible Goods. Journal of Artificial Intelligence Research. 2026;86. doi:10.1613/jair.1.20353

BibTeX
@article{Deligkas2026,
  author = {Deligkas, Argyrios and Eiben, Eduard and Ganian, Robert and Goldsmith, Tiger-Lily and Ioannidis, Stavros D.},
  title = {The Complexity of Extending Fair Allocations of Indivisible Goods},
  journal = {Journal of Artificial Intelligence Research},
  year = {2026},
  volume = {86},
  doi = {10.1613/jair.1.20353}
}
Kostenlos starten →