Fair allocation guarantees ensure nearly exact shares for most agents
Fair Share Allocations for Almost All Agents
Computer Science and Game Theory
Summary
The paper deals with dividing items that can't be split among people who value them differently. It shows that under certain conditions about how much each person is entitled to, every person can get exactly what they deserve according to a fairness measure called AnyPrice Share. For equal shares, this means nearly everyone gets a fair portion close to their ideal maximin share. The authors also provide ways to guarantee fairness either all the time or most of the time. These results hold even when people's entitlements differ, as long as each entitlement is not too large.
What this means in practice
- •For marketplace platform designers: Design allocation algorithms that fairly divide indivisible goods ensuring nearly exact entitled shares for users with small or equal claims.
- •For resource allocation engineers: Implement fair resource division systems that maintain proportional fairness guarantees in expectation or deterministically under small entitlement caps.
A theory result. No direct application yet.
Authors
Tomer Ezra, Tamar Garbuz
Abstract
We study fair allocation of indivisible goods among agents with additive valuations. Our main result guarantees every agent her exact AnyPrice Share (APS) whenever the total entitlement is at most $1-\varepsilon$ and each individual entitlement is sufficiently small. For equal entitlements, this yields a $1$-out-of-$(n+O(\sqrt{n\log n}))$ maximin share (MMS) allocation. We also establish two best-of-both-worlds guarantees that preserve proportionality in expectation: each agent receives her full MMS with probability at least $1-O((\log n/n)^{1/3})$, or every agent receives her $1$-out-of-$(n+O(n^{2/3}(\log n)^{1/3}))$ MMS in every outcome. Both guarantees extend to sufficiently small unequal entitlements, with APS replacing MMS. Quantitatively, our deterministic result allows an entitlement cap of order $\varepsilon^2/\log(1/\varepsilon)$, while an impossibility construction shows that any universally sufficient cap must be $O(\varepsilon)$.