Logo image
Back
Simultaneously Satisfying MXS and EFL
Conference proceeding   Open access

Simultaneously Satisfying MXS and EFL

Arash Ashuri and Vasilis Gkatzelis
EC '25: Proceedings of the 26th ACM Conference on Economics and Computation, pp 689-718
02 Jul 2025
DOI: https://doi.org/10.1145/3736252.3742613
Featured in Collection :   Research Supported by Drexel Libraries' OA Programs
url
https://doi.org/10.1145/3736252.3742613View
Published, Version of Record (VoR)Open Access via Drexel Libraries Read and Publish Program 2025CC BY V4.0,  Open

Abstract

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 which was previously shown to be achievable on its own [Barman et al., 2018, Caragiannis et al., 2023]. Our main result is an algorithm that constructs 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.

Metrics

3 Record Views

Details

Logo image