Campus Event Calendar

Event Entry

What and Who

Epistemic EFX Allocations Exist for Monotone Valuations

Hannaneh Akrami
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1  
AG Audience

Date, Time and Location

Tuesday, 11 June 2024
30 Minutes
E1 4


The notion of envy-freeness up to any item (EFX) is considered

to be the most fascinating fairness concept in fair division of
indivisible items. Unfortunately, despite significant efforts, existence
of EFX allocations is a major open problem in fair division, thereby
making the study of approximations and relaxations of EFX a natural line
of research. Recently, Caragiannis et al. introduced a promising
relaxation of EFX, called epistemic EFX (EEFX). We say an allocation to
be EEFX if, for every agent, it is possible to shuffle the items in the
remaining bundles so that she becomes EFX-satisfied''. Caragiannis et
al. prove existence and polynomial-time computability of EEFX
allocations for additive valuations. A natural question asks what
happens when we consider valuations more general than additive?

We address this important open question and answer it affirmatively by
establishing the existence of EEFX allocations for an arbitrary number
of agents with general monotone valuations. To the best of our
knowledge, EEFX is the only known relaxation of EFX to have such strong
existential guarantees. Furthermore, we complement our existential
result by proving computational and information-theoretic lower bounds.
We prove that for an arbitrary number of (more than one) agents (even)
with identical submodular valuations, it is PLS-hard to compute EEFX
allocations and it requires exponentially-many value queries to do so.

Joint work with Nidhi Rathi


Nidhi Rathi
+49 681 9325 1134
--email hidden

Virtual Meeting Details

897 027 2575
passcode not visible
logged in users only

Nidhi Rathi, 05/22/2024 23:15 -- Created document.