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