Terrible) Chore

Speaker(s)

Tomasz Wąs

Affiliation

LAMSADE, Paryż

Date

Dec. 7, 2023, 10:15 a.m.

Information about the event

online

Title in Polish

Fairly Allocating Goods and

Seminar

Seminar Games, Mechanisms, and Social Networks

---

We study the fair allocation of mixtures of indivisible goods and chores under lexicographic preferences—a subdomain of additive preferences. A prominent fairness notion for allocating indivisible items is envy-freeness up to any item (EFX). Yet, its existence and computation has remained a notable open problem. By identifying a class of instances with "terrible chores", we show that determining the existence of an EFX allocation is NP-complete. This result immediately implies the intractability of EFX under additive preferences. Nonetheless, we propose a natural subclass of lexicographic preferences for which an EFX and Pareto optimal (PO) allocation is guaranteed to exist and can be computed efficiently for any mixed instance. Focusing on two weaker fairness notions, we investigate finding EF1 and PO allocations for special instances with terrible chores, and show that MMS and PO allocations can be computed efficiently for any mixed instance with lexicographic preferences.

---