Envy-free item divisions exist for many agents with random preferences
Envy-Free Allocations for Random Non-Additive Valuations
Computer Science and Game Theory
Summary
Dividing items so that everyone feels fairly treated is hard, especially when people’s values for item groups aren’t simple sums. The authors study a model where people’s original preferences are scrambled by randomly renaming items. They show that when there are many items divided evenly among any fixed number of people, it's very likely that a perfectly fair division exists. This solves an open question about fairness in more complex cases with multiple agents.
What this means in practice
- •For marketplace platform designers: Guarantee fair resource allocation among users with complex, entangled preferences when item identities are effectively randomized.
- •For supply chain planners: Improve allocation fairness of divisible goods among multiple parties even with complicated non-linear values per bundle under uncertainty.
A theory result. No direct application yet.
Authors
Pasin Manurangsi
Abstract
Benade et al. (EC 2024) introduced a semi-random model for non-additive fair division in which each agent starts with an arbitrary base valuation over bundles of items and independently permutes the item names uniformly at random. While they proved that envy-free allocations exist with high probability as the number of items grows for $n = 2$ agents, they left open whether the same holds for $n > 2$ agents. We resolve this open question in the affirmative: for any fixed number of agents $n$ and any number of items $m$ divisible by $n$, an envy-free allocation exists with probability $1 - o(1)$ as $m \to \infty$. Our proof combines the second moment method with a connection to the (small-set) expansion of generalized Johnson graphs, which may be of independent interest.