Max min fairness achieves near optimal results in large random markets
Asymptotic Max-Min Fair Allocation with Random Utilities
Computer Science and Game TheoryInformation Theory
Summary
This paper looks at how to fairly divide items among people when each person values items differently and those values are random. The authors study a specific fairness rule called max-min fairness, which tries to make the worst-off person as well off as possible. They find that as the number of people and items grows, the fairness rule’s solution gets very close to the best possible overall happiness. This means that using max-min fairness in large random settings doesn’t really reduce total satisfaction much.
What this means in practice
- •For market designers: Design efficient and fair allocation mechanisms in large markets with unpredictable participant preferences by relying on asymptotic guarantees.
- •For resource allocation engineers: Implement allocation algorithms that balance fairness and total efficiency when assigning indivisible goods in large-scale systems with random valuations.
A theory result. No direct application yet.
Authors
Noam Glazner, Amir Leshem
Abstract
We investigate the asymptotic behavior of max-min fair allocations for indivisible goods under i.i.d. random utilities. For $N$ agents and $K$ goods with utilities ${\mU_{i,j}}$ drawn independently from a common distribution $F$, we derive asymptotic characterizations of the max-min value in the balanced case $K=N$ (and in $K=LN$ extensions) via distributional quantiles. We then study the efficiency impact of max-min fairness by comparing the resulting total welfare with the optimal sum welfare. For distributions with sufficiently light tails, we prove that the relative efficiency loss converges to zero as the market grows, implying that max-min fairness incurs negligible welfare loss in large random instances for a broad class of distributions.