Fair Allocation of Indivisible Items with Externalities

Prelegent(ci)

Šimon Schierreich

Afiliacja

AGH University of Science and Technology

Język referatu

angielski

Termin

12 marca 2026 12:00

Informacje na temat wydarzenia

seminar online

Seminarium

Seminarium „Ekonomia algorytmiczna”

---

We study the problem of fairly allocating indivisible items under externalities, where each agent can receive utility or disutility from items allocated to other agents. This allows us to capture scenarios in which agents benefit from or compete against one another. We extend the well-studied notions of envy-freeness up to one item (EF1) and envy-freeness up to any item (EFX) to this setting. We show that while an allocation satisfying both notions exists and can be computed efficiently for two agents, the existence for EFX is not guaranteed in general, and deciding it is NP-complete even when there are only three agents or only six different item values. On the other hand, we prove that when both the number of agents and the number of different item values are bounded, the problem becomes fixed-parameter tractable.

This is a joint work with Haris Aziz, Argyrios Deligkas, Eduard Eiben, Viktoriia Korchemna, Warut Suksompong, Zhaohong Sun, and Toby Walsh.

---