Allocation methods balance fairness before and after random choices
On best of both worlds allocations with subadditive valuations
Computer Science and Game Theory
Summary
This paper studies how to fairly divide indivisible items among people who value them in complex ways. The authors focus on two fairness ideas: one that guarantees fairness after items are assigned (maximin share), and one that looks at fairness on average before assignment (maximum expectation share). They show how to turn an allocation that meets a fairness level in the first sense into one that also meets a fairness guarantee on average. This approach works especially well for certain types of valuations and improves fairness in random allocations.
What this means in practice
- •For resource allocation engineers: Design allocation protocols that guarantee fairness both on average and in individual assignments for systems with indivisible goods and complex agent preferences.
- •For cloud service schedulers: Implement randomized task or resource assignments ensuring balanced fairness expectations and actual outcomes under complex valuation models.
A theory result. No direct application yet.
Authors
Uriel Feige
Abstract
We consider allocation of indivisible goods to agents with equal entitlements and subadditive valuations. As an ex-post fairness notion we consider the maximin share (MMS), and as an ex-ante fairness notion we consider the maximum expectation share (MES), which is always at least as large as the MMS, and sometimes much larger. We present a simple transformation that for every $0 < ρ\le 1$, given any algorithm that produces $ρ$-MMS allocations, transforms it into a randomized allocation algorithm that offers $ρ$-MMS ex-post simultaneously with $η$-MES ex-ante. We prove several new properties of MES, and use them to show that $η\ge \min[\fracρ{2 + ρ}, \frac{1}{4}]$. We also present cases in which the transformation results in a higher value of $η$. Applying our transformation to currently known allocation algorithms shows for subadditive valuations the existence of randomized allocations that are simultaneously $Ω(\frac{1}{\log\log n})$-MES ex-ante and $Ω(\frac{1}{\log\log n})$-MMS ex-post, and for XOS valuations the existence of randomized allocations that are simultaneously $\frac{4}{27}$-MES ex-ante and $\frac{4}{17}$-MMS ex-post.