EUVIMEDEUVIMED entdecken
Crossref

Efficient Constructions of EFX Allocations for Two Types of Indivisible Goods

Vladimir Davidiuk, Yuriy Dementiev, Artur Ignatiev, Danil Sagunov

Journal of Artificial Intelligence Research · 11.11.2026 · 87

DOI: 10.1613/jair.1.22553 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Artificial Intelligence Research, online erschienen am 11.11.2026. Verfasst von Vladimir Davidiuk und 3 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We study the problem of fairly and efficiently allocating indivisible goods among agents with additive valuations. We focus on envy-freeness up to any good (EFX)—an important fairness notion in fair division of indivisible goods. A central open question in this field is whether EFX allocations always exist for any number of agents. While prior work has established EFX existence for settings with at most three distinct valuations (HV, Ghosal, et al. 2025) and for two types of goods (Gorantla et al. 2023), the general case remains unresolved. In this paper, we extend the existent knowledge by proving that EFX allocations satisfying Pareto optimality (PO) always exist and can be computed in quasilinear time when there are two types of goods, given that the valuations are positive. This result strengthens the existing work of (Gorantla et al. 2023), which only guarantees the existence of EFX allocations without ensuring Pareto optimality. Our findings demonstrate a fairly simple and efficient algorithm constructing an EFX+PO allocation.

Zitieren

APA

Davidiuk, V., Dementiev, Y., Ignatiev, A., & Sagunov, D. (2026). Efficient Constructions of EFX Allocations for Two Types of Indivisible Goods. Journal of Artificial Intelligence Research, 87. https://doi.org/10.1613/jair.1.22553

Vancouver

Davidiuk V, Dementiev Y, Ignatiev A, Sagunov D. Efficient Constructions of EFX Allocations for Two Types of Indivisible Goods. Journal of Artificial Intelligence Research. 2026;87. doi:10.1613/jair.1.22553

BibTeX
@article{Davidiuk2026,
  author = {Davidiuk, Vladimir and Dementiev, Yuriy and Ignatiev, Artur and Sagunov, Danil},
  title = {Efficient Constructions of EFX Allocations for Two Types of Indivisible Goods},
  journal = {Journal of Artificial Intelligence Research},
  year = {2026},
  volume = {87},
  doi = {10.1613/jair.1.22553}
}
Kostenlos starten →