Best of Both Worlds Guarantees for Equitable Allocations

Umang Bhaskar Vishwa Prakash HV Tata Institute of Fundamental Research Chennai Mathematical Institute [email protected] [email protected] Aditi Sethia Rakshitha Indian Institute of Science, Bangalore Indian Institute of Technology, Delhi [email protected] [email protected] · 2025

Read Best of Both Worlds Guarantees for Equitable Allocations by Umang Bhaskar Vishwa Prakash HV Tata Institute of Fundamental Research Chennai Mathematical Institute [email protected] [email protected] Aditi Sethia Rakshitha Indian Institute of Science, Bangalore Indian Institute of Technology, Delhi [email protected] [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-2505-05809.txt.

Description

Umang Bhaskar and co-authors study in 2025 fair division allocations that are equitable both before and after a random draw. An allocation is equitable when all agents gain equal value from their share. For indivisible items an exact match may not exist, so a relaxed rule allows a gap that one item's removal would fix. Their goal joins fairness in expectation with that relaxed rule for every outcome.

A geometric condition on mixes of relaxed allocations decides when such best of both worlds allocations exist. For two agents they always exist and can be computed fast. For three or more they may not exist, and even deciding the question is hard, though a slower method works for a fixed number of agents.

Catalog record

CREATORUmang Bhaskar Vishwa Prakash HV Tata Institute of Fundamental Research Chennai Mathematical Institute [email protected] [email protected] Aditi Sethia Rakshitha Indian Institute of Science, Bangalore Indian Institute of Technology, Delhi [email protected] [email protected]
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE63 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-05809

Browse the full library · About the Tower of Babel