Publications - Current Year

We study the problem of computing \emph{fair} divisions of a set of
indivisible goods among agents with \emph{additive} valuations. For the past
many decades, the literature has explored various notions of fairness, that can
be primarily seen as either having \emph{envy-based} or \emph{share-based}
lens. For the discrete setting of resource-allocation problems, \emph{envy-free
up to any good} (EFX) and \emph{maximin share} (MMS) are widely considered as
the flag-bearers of fairness notions in the above two categories, thereby
capturing different aspects of fairness herein. Due to lack of existence
results of these notions and the fact that a good approximation of EFX or MMS
does not imply particularly strong guarantees of the other, it becomes
important to understand the compatibility of EFX and MMS allocations with one
another.
In this work, we identify a novel way to simultaneously achieve MMS
guarantees with EFX/EF1 notions of fairness, while beating the best known
approximation factors [Chaudhury et al., 2021, Amanatidis et al., 2020]. Our
main contribution is to constructively prove the existence of (i) a partial
allocation that is both $2/3$-MMS and EFX, and (ii) a complete allocation that
is both $2/3$-MMS and EF1. Our algorithms run in pseudo-polynomial time if the
approximation factor for MMS is relaxed to $2/3-\varepsilon$ for any constant
$\varepsilon > 0$ and in polynomial time if, in addition, the EFX (or EF1)
guarantee is relaxed to $(1-\delta)$-EFX (or $(1-\delta)$-EF1) for any constant
$\delta>0$. In particular, we improve from the best approximation factor known
prior to our work, which computes partial allocations that are $1/2$-MMS and
EFX in pseudo-polynomial time [Chaudhury et al., 2021].

We study the fundamental problem of fairly dividing a set of indivisible
items among agents with (general) monotone valuations. The notion of
envy-freeness up to any item (EFX) is considered to be one of the most
fascinating fairness concepts in this line of work. 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 (beside EF1) to have such strong existential
guarantees. Furthermore, we complement our existential result by proving
computational and information-theoretic lower bounds. We prove that even for an
arbitrary number of (more than one) agents with identical submodular
valuations, it is PLS-hard to compute EEFX allocations and it requires
exponentially-many value queries to do so.