Improving Envy Freeness up to Any Good Guarantees Through Rainbow Cycle Number

Bhaskar Ray Chaudhury (), Jugal Garg (), Kurt Mehlhorn (), Ruta Mehta () and Pranabendu Misra ()
Additional contact information
Bhaskar Ray Chaudhury: Department of Industrial and Enterprise Systems Engineering, University of Illinois Urbana–Champaign, Urbana, Illinois 61820
Jugal Garg: Department of Industrial and Enterprise Systems Engineering, University of Illinois Urbana–Champaign, Urbana, Illinois 61820
Kurt Mehlhorn: Saarland Informatics Campus, Max Planck Institute for Informatics, 66123 Saarbrucken, Germany
Ruta Mehta: Department of Computer Science, University of Illinois Urbana-Champaign, Urbana, Illinois 61801
Pranabendu Misra: Department of Computer Science, Chennai Mathematical Institute, Chennai 603103, India

Mathematics of Operations Research, 2024, vol. 49, issue 4, 2323-2340

Abstract: We study the problem of fairly allocating a set of indivisible goods among n agents with additive valuations. Envy freeness up to any good (EFX) is arguably the most compelling fairness notion in this context. However, the existence of an EFX allocation has not been settled and is one of the most important problems in fair division. Toward resolving this question, many impressive results show the existence of its relaxations. In particular, it is known that 0.618-EFX allocations exist and that EFX allocation exists if we do not allocate at most ( n -1) goods. Reducing the number of unallocated goods has emerged as a systematic way to tackle the main question. For example, follow-up works on three- and four-agents cases, respectively, allocated two more unallocated goods through an involved procedure. In this paper, we study the general case and achieve sublinear numbers of unallocated goods. Through a new approach, we show that for every ε ∈ ( 0 , 1 / 2 ] , there always exists a ( 1 − ε ) -EFX allocation with sublinear number of unallocated goods and high Nash welfare. For this, we reduce the EFX problem to a novel problem in extremal graph theory. We define the notion of rainbow cycle number R ( · ) in directed graphs. For all d ∈ N , R ( d ) is the largest k such that there exists a k -partite graph G = ( ∪ i ∈ [ k ] V i , E ) , in which each part has at most d vertices (i.e., | V i | ≤ d for all i ∈ [ k ] ); for any two parts V i and V j , each vertex in V i has an incoming edge from some vertex in V j and vice versa; and there exists no cycle in G that contains at most one vertex from each part. We show that any upper bound on R ( d ) directly translates to a sublinear bound on the number of unallocated goods. We establish a polynomial upper bound on R ( d ) , yielding our main result. Furthermore, our approach is constructive, which also gives a polynomial-time algorithm for finding such an allocation.

Keywords: Primary: 91B32; 68Q25; 68W40; discrete fair division; EFX allocations; rainbow cycle number (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2021.0252 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:49:y:2024:i:4:p:2323-2340

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().