Computer Science - Computer Science and Game Theory
The two standard fairness notions in the resource allocation literature are
proportionality and envy-freeness. If there are n agents competing for the
available resources, then proportionality requires that each agent receives at
least a 1/n fraction of their total value for the set of resources. On the
other hand, envy-freeness requires that each agent weakly prefers the resources
allocated to them over those allocated to any other agent. Each of these
notions has its own benefits, but it is well known that neither one of the two
is always achievable when the resources being allocated are indivisible. As a
result, a lot of work has focused on satisfying fairness notions that relax
either proportionality or envy-freeness. In this paper, we focus on MXS (a
relaxation of proportionality) and EFL (a relaxation of envy-freeness). Each of
these notions was previously shown to be achievable on its own [Barman et
al.,2018, Caragiannis et al., 2023], and our main result is an algorithm that
computes allocations that simultaneously satisfy both, combining the benefits
of approximate proportionality and approximate envy-freeness. In fact, we prove
this for any instance involving agents with valuation functions that are
restricted MMS-feasible, which are more general than additive valuations. Also,
since every EFL allocation directly satisfies other well-studied fairness
notions like EF1, 1/2-EFX, 1/2-GMMS, and 2/3-PMMS, and every MXS allocation
satisfies 4/7-MMS, the allocations returned by our algorithm simultaneously
satisfy a wide variety of fairness notions and are, therefore, universally fair
[Amanatidis et al., 2020].
Metrics
10 Record Views
Details
Title
Simultaneously Satisfying MXS and EFL
Creators
Arash Ashuri
Vasilis Gkatzelis
Resource Type
Preprint
Language
English
Academic Unit
Computer Science (Computing)
Other Identifier
991021970099704721
Research Home Page
Browse by research and academic units
Learn about the ETD submission process at Drexel
Learn about the Libraries’ research data management services