EUVIMEDEUVIMED entdecken
Crossref

Envy-Freeness up to Any Good Allocations on Graphs

George Christodoulou, Amos Fiat, Elias Koutsoupias, Alkmini Sgouritsa

Mathematics of Operations Research · 15.06.2026

DOI: 10.1287/moor.2025.0915 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Mathematics of Operations Research, online erschienen am 15.06.2026. Verfasst von George Christodoulou und 3 weiteren Autor:innen. Die Arbeit nennt 41 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We study envy-freeness up to any good (EFX) in settings where valuations can be represented via a graph of arbitrary size where vertices correspond to agents and edges to items. An item (edge) has zero marginal value to all agents (vertices) not incident to the edge. Each vertex may have an arbitrary monotone valuation on the set of incident edges. We first consider allocations that correspond to orientations of the edges, where we show that EFX does not always exist, and furthermore, that it is NP-complete to decide whether an EFX orientation exists. Our main result is that EFX allocations exist for this setting. This is one of the few cases where EFX allocations are known to exist for more than three agents. Funding: The research project is implemented in the framework of the Hellenic Foundation for Research and Innovation (HFRI) call “Basic research Financing (Horizontal Support of all Sciences)” under the National Recovery and Resilience Plan “Greece 2.0” funded by the European Union—NextGenerationEU [HFRI Project 15635].

Zitieren

APA

Christodoulou, G., Fiat, A., Koutsoupias, E., & Sgouritsa, A. (2026). Envy-Freeness up to Any Good Allocations on Graphs. Mathematics of Operations Research. https://doi.org/10.1287/moor.2025.0915

Vancouver

Christodoulou G, Fiat A, Koutsoupias E, Sgouritsa A. Envy-Freeness up to Any Good Allocations on Graphs. Mathematics of Operations Research. 2026. doi:10.1287/moor.2025.0915

BibTeX
@article{Christodoulou2026,
  author = {Christodoulou, George and Fiat, Amos and Koutsoupias, Elias and Sgouritsa, Alkmini},
  title = {Envy-Freeness up to Any Good Allocations on Graphs},
  journal = {Mathematics of Operations Research},
  year = {2026},
  doi = {10.1287/moor.2025.0915}
}
Kostenlos starten →