Achieving EF1 and Epistemic EFX Guarantees Simultaneously

Speaker(s)

Nidhi Rathi

Affiliation

University of Warsaw

Language of the talk

English

Date

April 9, 2026, noon

Information about the event

seminar online

Seminar

Seminar Algorithmic Economics

---

We study the fundamental problem of fairly dividing a set of indivisible goods among agents with additive valuations. Here, envy-freeness up to any good (EFX) is a central fairness notion and resolving its existence is regarded as one of the most important open problems in this area of research. Two prominent relaxations of EFX are envy-freeness up to one good (EF1) and epistemic EFX (EEFX). While allocations satisfying each of these notions individually are known to exist even for general monotone valuations, whether both can be satisfied simultaneously remains open for all instances in which the EFX problem is itself unresolved.
In this work, we show that there always exists an allocation that is both EF1 (in fact, the stronger notion EFL) and EEFX for additive valuations, thereby resolving the primary open question raised by Akrami and Rathi (2025) and bringing us one step closer to resolving the elusive EFX problem. We introduce a new share-based fairness notion, termed strong EEFX share, which may be of independent interest and which implies EEFX feasibility of bundles. We show that this notion is compatible with EF1, leading to the desired existence result. 

This is a joint work with Hannaneh Akrami, Ryoga Mahara, and Kurt Mehlhorn.
Link - https://arxiv.org/abs/2602.11732

---