EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Reforming an Unfair Allocation by Exchanging Goods

Sheung Man Yuen, Ayumi Igarashi, Naoyuki Kamiyama, Warut Suksompong

Algorithmica · 2026-08 · 88 (4)

DOI: 10.1007/s00453-026-01401-8 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Algorithmica, online erschienen am 29.06.2026. Verfasst von Sheung Man Yuen und 3 weiteren Autor:innen. Die Arbeit nennt 37 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Japan Science and Technology Agency, Japan Society for the Promotion of Science, Ministry of Education - Singapore.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Fairly allocating indivisible goods is a frequently occurring task in everyday life. Given an initial allocation of the goods, we consider the problem of reforming it via a sequence of exchanges to attain fairness in the form of envy-freeness up to one good (EF1). We present a vast array of results on the complexity of determining whether it is possible to reach an EF1 allocation from the initial allocation and, if so, the minimum number of exchanges required. In particular, we uncover several distinctions based on the number of agents involved and their utility functions. Furthermore, we derive essentially tight bounds on the worst-case number of exchanges needed to achieve EF1 when the initial allocation is balanced.

Förderung

  • Japan Science and Technology Agency
  • Japan Society for the Promotion of Science
  • Ministry of Education - Singapore
  • National University of Singapore

Zitieren

APA

Yuen, S. M., Igarashi, A., Kamiyama, N., & Suksompong, W. (2026). Reforming an Unfair Allocation by Exchanging Goods. Algorithmica, 88(4). https://doi.org/10.1007/s00453-026-01401-8

Vancouver

Yuen SM, Igarashi A, Kamiyama N, Suksompong W. Reforming an Unfair Allocation by Exchanging Goods. Algorithmica. 2026;88(4). doi:10.1007/s00453-026-01401-8

BibTeX
@article{Yuen2026,
  author = {Yuen, Sheung Man and Igarashi, Ayumi and Kamiyama, Naoyuki and Suksompong, Warut},
  title = {Reforming an Unfair Allocation by Exchanging Goods},
  journal = {Algorithmica},
  year = {2026},
  volume = {88},
  number = {4},
  doi = {10.1007/s00453-026-01401-8}
}
Kostenlos starten →