Extending EFX allocations to further multi-graph classes

DOI10.4230/LIPICS.FSTTCS.2025.15MaRDI QIDQ7391887zbMATH OpenFDO

Authors Umang Bhaskar, Yeshwant Pandit

Publication date 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.FSTTCS.2025.15

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx)

Cites work

• A Little Charity Guarantees Almost Envy-Freeness
• Almost envy-freeness with general valuations
• EFX exists for three agents
• Envy-free relaxations for goods, chores, and mixed items
• Existence of EFX for two additive valuations
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Multiple birds with one stone: beating 1/2 for EFX and GMMS via envy cycle elimination
• On Approximate Envy-Freeness for Indivisible Chores and Mixed Resources
• The frontier of intractability for EFX with two agents

This page was built for publication: Extending EFX allocations to further multi-graph classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7391887)