Minimum subsidies needed for fair allocation of indivisible goods

Asymptotic Subsidies for Envy-Free Allocation

Computer Science and Game Theory

Summary

Dividing indivisible goods fairly between many people can sometimes cause envy, where someone feels another got a better share. This paper studies how much extra money (subsidy) is needed to prevent envy exactly when dividing these goods. The authors provide algorithms and mathematical results to calculate this minimum subsidy, especially as the number of people grows very large. Their findings give a clear picture of how subsidies behave depending on the number of goods and people involved.

What this means in practice

  • For market designers: Determine minimal financial compensations to ensure envy-free allocations in large multi-agent resource division problems.
  • For allocation algorithm developers: Use the provided cubic-time algorithms to compute envy-free allocations with minimal subsidies under additive random valuations.

Authors

Zekai Wu

Abstract

We study the minimum monetary subsidy required for exact envy-freeness in allocating $m_n$ indivisible goods to $n$ agents. Valuations are additive, item values are i.i.d. from a distribution on $[0,1]$ with density bounded above and away from zero, and all agents value money equally. We consider $n\to\infty$ with $m_n=qn+r_n$, where $q\ge0$ is a fixed integer and $0\le r_n<n$. For the nonzero-remainder case where $1\le r_n<n$, we give a cubic-time algorithm based on a maximum-weight matching of balanced bundles and complementary dual prices. It returns an envy-free outcome for every instance. Under the random model, both its payment and the unrestricted minimum are $n-r_n+o_p(n)$ for $q\ge1$. When $q=0$ and $r_n/n$ converges to a limit below one, the error term improves to $O_p(1)$. For exact divisibility, where $r_n=0$, prior work gives zero subsidy with high probability for $q\ge2$. The square case $q=1$ is exceptional. Its minimum subsidy is $Θ_p(\log n)$ and, with high probability, equals the optimum over allocations in which every agent receives exactly one good. This restricted optimum can be computed in cubic time using a maximum-weight perfect matching and all-pairs shortest paths. Together, these results provide a unified asymptotic characterization of the minimum subsidy.