Fair random assignment methods guarantee low envy for four agents
Envy-Free Decompositions of Random Assignments: Settling Four Agents, and What Lies Beyond
Computer Science and Game Theory
Summary
When giving out things randomly to people, it's important to be fair so nobody feels jealous of someone else's share. The authors focus on a fairness idea called envy-freeness and prove that for four people, there is always a way to mix assignments so nobody envies another more than half the time. They use computer verification to check all possible cases for four people and show similar positive results for five agents under some conditions. They also find that for bigger groups, deciding fairness is much harder, and some natural methods don't always keep envy low.
What this means in practice
- •For resource allocation teams: Create random assignment procedures that ensure no agent strongly prefers another’s allocation more than half the time when dealing with four participants.
- •For online marketplaces: Implement fair item distribution algorithms for small groups that minimize envy occurrences, improving perceived fairness in allocations.
Authors
Keyi Li, Yihao He, Quanyi Li
Abstract
A random assignment of n indivisible objects to n agents is specified by its assignment matrix and implemented by drawing a deterministic assignment from a Birkhoff-von Neumann decomposition. Kawase et al. observed that the choice of decomposition matters for fairness: a matrix that is envy-free in the sense of stochastic dominance (SD-EF) can be decomposed so that some agent envies another with probability close to 1. They call a decomposition Dec-EF if every agent envies every other agent with probability at most 1/2, proved that every SD-EF matrix admits a Dec-EF decomposition when n <= 3 or when there are at most two distinct preferences, and left the general case open. We settle the first open case: every SD-EF matrix with four agents admits a Dec-EF decomposition. The worst case over the SD-EF polytope of a profile is attained at a vertex, and our computer-aided proof enumerates all 26,927 vertices for the 762 profiles up to symmetry in exact arithmetic and certifies each by a rational decomposition. The same method settles five agents with at most four distinct preferences and the probabilistic serial rule for all five-agent profiles, and adversarial search up to seven agents finds no counterexample. For general n, an envy-budget identity shows that 1/2 is the best possible threshold. We prove that every SD-EF matrix with at most two distinct rows admits a Dec-EF decomposition, and that the maximum-entropy decomposition is Dec-EF whenever all agents but two share a preference; the latter proof rests on a new monotonicity lemma for weighted least-squares rankings. In general, natural decompositions fail: greedy Birkhoff-von Neumann can come arbitrarily close to envy probability (n-1)/n, and maximum entropy fails at n = 4 when all preferences differ. Deciding whether an arbitrary random assignment, not necessarily SD-EF, admits a Dec-EF decomposition is strongly NP-complete.