Existence of Fair and Efficient Allocation of Indivisible ChoresOberseminar Discrete Optimization

by Ryoga Mahara (University of Tokyo)

Monday Oct 13, 2025, 6:00 PM → 7:00 PM Europe/Berlin

Arithmeum, Lennéstr., 2 - Seminarraum (Arithmeum / Research Institute for Discrete Mathematics)

We study the problem of allocating indivisible chores among agents with additive cost functions in a fair and efficient manner. A major open question in this area is whether there always exists an allocation that is envy-free up to one chore (EF1) and Pareto optimal (PO). In this talk, I will present a positive answer to this question by proving the existence of such an allocation under additive cost functions. Our proof is based on a novel combination of a fixed-point argument and a discrete algorithm, which provides a significant methodological advance in this area.

Our additional key contributions are as follows. We show that there always exists an allocation that is EF1 and fractional Pareto optimal (fPO), where fPO is a stronger efficiency concept than PO. We also show that an EF1 and PO allocation can be computed in polynomial time when the number of agents is constant. Finally, we extend all of these results to the more general setting of weighted EF1 (wEF1), which accounts for agents’ entitlements.

 

The Oberseminar takes place in the Seminarraum, 1^st floor. Participants are invited to have coffee or tea in the lounge before.