Almost and Approximate EFX for Few Types of Agents
Vishwa Prakash HV Ruta Mehta Chennai Mathematical Institute University of Illinois Urbana-Champaign [email protected] [email protected] Prajakta Nimbhorkar Chennai Mathematical Institute [email protected] · 2025
Read Almost and Approximate EFX for Few Types of Agents by Vishwa Prakash HV Ruta Mehta Chennai Mathematical Institute University of Illinois Urbana-Champaign [email protected] [email protected] Prajakta Nimbhorkar Chennai Mathematical Institute [email protected] (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-15380.txt.
Description
Vishwa Prakash, Ruta Mehta, and Prajakta Nimbhorkar present a 2025 paper on splitting indivisible goods fairly when people come in few types. Fairness here means approximate envy-freeness up to any single good: nobody should envy another's bundle once one item is ignored. Earlier results guaranteed such allocations for at most three distinct valuation types, or weaker fairness for up to seven agents. The authors extend the guarantee.
With at most four distinct valuations, a two-thirds-strength version of the fairness property always exists, for any number of agents. They also study a relaxed version where some goods go to charity, unallocated, and nobody envies the charity pile either. There, near-perfect fairness needs a charity pile that shrinks as the number of types shrinks. The paper is theoretical computer science about fair division.
Catalog record
| CREATOR | Vishwa Prakash HV Ruta Mehta Chennai Mathematical Institute University of Illinois Urbana-Champaign [email protected] [email protected] Prajakta Nimbhorkar Chennai Mathematical Institute [email protected] |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 86 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-15380