PaperlayerView exact revision on arXiv

Source-linked AI summary

Asymptotic Subsidies for Envy-Free Allocation

Zekai Wu

arXiv:2610.10272v1cs.GT

TL;DR

The paper studies how many goods relative to agents determine the monetary subsidies needed for exact envy-freeness under random additive valuations. It analyzes balanced-bundle matching and, in the square case, singleton allocations, finding asymptotic subsidy scales that vary with divisibility and the goods-to-agents ratio.

  • Problem

    The paper asks how much total compensation exact envy-freeness requires with high probability as the number of indivisible goods varies relative to the number of agents.

    Source: §1 · pp. 1–2

  • Method

    For nonzero remainders, the paper matches balanced bundles and uses dual-price compensation; for the square case, it analyzes the singleton-allocation optimum.

    Source: §1 · pp. 2–3

  • Results

    For nonzero remainders, the minimum is n−r_n+o_p(n) when q≥1 and n−r_n+O_p(1) when q=0 with r_n/n→λ<1; the square-case minimum is logarithmic.

    Source: §3 · p. 5, §5 · p. 12

  • Takeaways & Limitations

    Typical minimum compensation depends on the number of goods and its divisibility by the number of agents, with zero subsidy known w.h.p. at exact divisibility for q≥2.

    Source: §5 · p. 12

    The random-model results assume independent item values from a common distribution with density bounded above and away from zero on [0, 1].

    Source: §2 · p. 4

Abstract

from arXiv · show

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 $\Theta_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.

1 Introduction

The paper asks how the number of indivisible goods relative to agents shapes the compensation needed for exact envy-freeness, then characterizes minimum subsidies under random valuations. Its results connect asymptotic fair division with subsidy-based fair division, including a distinct logarithmic scale when goods equal agents.

1 Introduction

  • Prior asymptotic existence results identify settings where goods alone can yield envy-freeness, but do not determine required compensation when such an allocation does not exist.Worst-case subsidy guarantees and experiments with synthetic and Spliddit instances motivate studying typical compensation needs beyond worst-case bounds.Source: §1 · p. 2
  • The paper asks how much total monetary compensation exact envy-freeness requires with high probability as the number of goods varies relative to the number of agents.The model uses additive valuations drawn independently from a common distribution on [0, 1] with density bounded above and away from zero.Source: §1 · p. 2
  • For nonzero remainders, a balanced-bundle matching with dual-price compensation is envy-free for every instance and runs in O(n^3) time; the square case has logarithmic compensation.The paper also reports that its nonzero-remainder payment matches the unrestricted minimum asymptotically.Source: §1 · pp. 2–3
  • Prior work gives zero subsidy with high probability when goods are exactly divisible among agents and q ≥2; the square case q = 1 instead has logarithmic compensation.For the square case, the unrestricted optimum coincides with the singleton-allocation optimum with high probability, computable in O(n^3) time.Source: §1 · p. 3, §1.1 · p. 4

2 Preliminaries

The preliminaries specify additive valuations, the random valuation model, and the subsidy-adjusted envy-freeness criterion. They also fix the goods-to-agents asymptotic regime used throughout.

2 Preliminaries

  • Each agent values a bundle additively, with each good's value in [0, 1], and an allocation partitions all goods among the agents.Envy-freeness requires each agent to value her own bundle at least as highly as every other agent's bundle.Source: §2 · p. 4
  • Item values are independent draws from a common distribution whose density is bounded above and bounded away from zero on [0, 1].The density bounds are used in probabilistic analysis; the algorithms take realized valuations as input.Source: §2 · p. 4
  • The analysis sets m_n = qn + r_n for fixed integer q ≥0 and 0 ≤r_n<n, with limits taken as n grows.Money is valued equally by all agents, and envy-freeness compares each agent's bundle-plus-subsidy value with every other's.Source: §2 · p. 5

3 Nonzero remainders

For nonzero remainders, balanced bundles and matching yield an instance-wise envy-free construction whose payment has the same leading asymptotic size as the unrestricted minimum. The analysis treats sparse goods separately from the q ≥1 regime.

3 Nonzero remainders

  • The construction partitions goods into r_n bundles of q+1 and n−r_n bundles of q, then matches bundles to agents by maximum weight and uses dual prices for subsidies.Payments are set from complementary dual prices so that the resulting allocation and subsidy vector are envy-free.Source: §3 · pp. 5–6
  • For 1 ≤r_n<n, the algorithm's payment is n−r_n+O_p(1) when q=0 and n−r_n+o_p(n) when q≥1; its outcome is envy-free for every instance.For q=0, the O_p(1) bound assumes r_n/n→λ<1.Source: §3 · p. 5

3.1 The sparse case: q = 0

  • When q=0 and r_n/n→λ<1, the minimum subsidy divided by n converges in probability to 1−λ.The proof overview says every envy-free outcome incurs the construction's same leading payment, up to a tight random constant-order error.Source: §3.1 · p. 7
  • For one good and uniform valuations, the optimum is (n−1)(1−v_(n−1)) and converges in distribution to a Γ(2, 1) random variable.Here v_(n−1) denotes the second-largest valuation; all agents with empty bundles receive the same payment.Source: §3.1 · p. 7

3.2 The case q ≥1

  • For q≥1, the algorithm's upper bound relies on adjusted dual bundle potentials being nearly constant, which makes payment depend on the number of smaller bundles.The estimate holds simultaneously over maximum-weight matchings and complementary optimal dual solutions.Source: §3.2 · p. 8
  • For q≥1, the lower-bound proof splits on total excess above bundle size q: many excess goods yield disjoint (q+1)-tuples, while few yield a near-unit seed payment.In the few-excess case, high-valued q-subsets propagate the payment through bundles of size q to almost all agents.Source: §3.2 · pp. 8–9

4 Exact divisibility

With exact divisibility, the minimum subsidy is zero for q=0, Θp(log n) for q=1, and zero with high probability for q≥2. In the square case, the unrestricted optimum equals the singleton-allocation optimum with high probability, which is computable in cubic time.

4 Exact divisibility

  • 0 for q=0, Θp(log n) for q=1, and 0 w.h.p. for q≥2 characterize the minimum subsidy when m_n=qn.The q≥2 guarantee follows from prior work; the square case is treated separately.Source: §4 · p. 9

4.1 Singleton reduction and computation

  • O(n^3) time suffices to compute the minimum-payment envy-free singleton allocation using a maximum-weight perfect matching and all-pairs shortest paths.The matching is unique almost surely, and maximum path weights give the coordinatewise least nonnegative payments.Source: §4.1 · p. 10
  • With high probability, every nonsingleton allocation costs at least n−o(n), while a singleton outcome costs o(n), so the unrestricted optimum equals the singleton optimum.When m_n=n, every nonsingleton allocation has both an empty bundle and a bundle with at least two goods.Source: §4.1 · pp. 10–11

4.2 The logarithmic compensation scale

  • For m_n=n, the unrestricted minimum subsidy is Θp(log n); for the uniform distribution on [0, 1], it is 2 log n + Op(1).The logarithmic bounds transfer from the singleton optimum to the unrestricted optimum.Source: §4.2 · p. 12

5 Conclusion

The results characterize how the number of goods and its divisibility by the number of agents shape typical compensation requirements. A future direction is to replace money with heterogeneous divisible goods and study how preference diversity affects the required budget.

5 Conclusion

  • For m_n=qn+r_n with fixed q, the nonzero-remainder optimum is n−r_n+o_p(n), while the square case has logarithmic compensation.Together with the known zero-subsidy guarantee for m_n=qn and q≥2, the results show how divisibility shapes typical compensation requirements.Source: §5 · p. 12
  • Under random valuations of indivisible goods, how preference diversity affects the minimum divisible-good budget for exact envy-freeness remains open.The comparison assumes each agent values the entire divisible endowment at most B; valuations of its parts may differ.Source: §5 · p. 12

A Missing Proofs of Section 3

For nonzero remainders, Theorem 1 gives the asymptotic subsidy estimates and the algorithm’s guarantee. Its proof uses complementary dual prices to establish envy-freeness and bounds the running time through matching computation.

A Missing Proofs of Section 3

  • For 1≤r_n<n, the estimate is n−r_n+O_p(1) when q=0 and n−r_n+o_p(n) when q≥1.The q=0 case assumes r_n/n→λ<1.Source: A Missing Proofs of Section 3 · p. 15
  • Algorithm 1 returns an envy-free outcome for every valuation profile in O(n^3) time, with payment obeying the corresponding random-model estimate.For fixed q, m_n=O(n), giving the cubic running time.Source: A Missing Proofs of Section 3 · p. 15
  • Complementary slackness makes matched bundle values equal to the sum of dual potentials, which yields the pairwise envy-free inequalities for the resulting payments.The payments are nonnegative by the definition of H.Source: A Missing Proofs of Section 3 · p. 15

A.1 The sparse case: q = 0

When 0<m_n<n and m_n/n→λ<1, the q=0 minimum subsidy is n−m_n+O_p(1). The proof bounds the algorithm’s upper cost and a lower bound applying to every envy-free outcome.

A.1 The sparse case: q = 0

  • Under 0 < m_n < n and m_n/n → λ < 1, EF ≤ n−m_n+O_p(1); the lower bound applies to every EF outcome.Source: §A.1 · pp. 15, 17
  • The algorithm’s upper bound uses the n−m_n agents matched to empty bundles and bounds the associated payment using the singleton-bundle potentials.Those potentials are at most one, and dual feasibility makes each at least the unmatched agents’ value for that good.Source: §A.1 · p. 17
  • Every envy-free allocation has at least n−m_n empty bundles, whose agents must receive equal payments; an order statistic of agents’ largest values gives a lower bound on that payment.At least one of the m_n+1 agents with the smallest η_i must have an empty bundle.Source: §A.1 · pp. 16–17

A.2 The case q ≥1

For q ≥1 and nonzero remainder, the proof establishes matching upper and lower bounds of n − r_n + o_p(n) on the minimum envy-free payment. The upper bound comes from concentrating the dual prices, while the lower bound applies uniformly to all envy-free allocations.

A.2 The case q ≥1

  • With high probability, the dual-price potentials have range o(1), making the construction’s total payment estimate sharp.The potential range bound applies simultaneously to every maximum-weight matching and complementary optimal dual solution.Source: §A.2 · pp. 18, 20
  • Uniform high-probability valuation events support the lower bound even when the envy-free allocation is chosen after valuations are observed.The proof uses families of disjoint goods that may depend on the realized valuations.Source: §A.2 · pp. 20–22
  • When at least n^2/3 agents exceed q goods, many disjoint (q + 1)-tuples force payment contributions from nearly all agents with at most q goods.The tuple-family event leaves at most n^2/3 exceptional agents.Source: §A.2 · p. 21
  • When fewer than n^2/3 agents exceed q goods, price comparisons propagate from a high-valued tuple through exact-q owners to yield the lower bound.The proof uses the first and third properties of Lemma 6 to propagate the initial comparison.Source: §A.2 · pp. 21–22
  • The minimum payment is n − r_n + o_p(n), matching the algorithm’s payment estimate.The upper bound follows from the dual-price construction; the lower bound holds for every envy-free allocation.Source: §A.2 · pp. 20, 22

B Missing Proofs of Section 4

This appendix supplies the proofs for the square case, beginning with singleton computation and reduction before analyzing choice shares and logarithmic bounds.

B Missing Proofs of Section 4

  • The appendix’s proof sequence establishes singleton computation and reduction before deriving the logarithmic bounds.The appendix assumes m_n = n.Source: B Missing Proofs of Section 4 · p. 22
  • B_sing denotes the minimum total payment among envy-free allocations in which each agent receives exactly one good.The section considers the square case m_n = n.Source: B Missing Proofs of Section 4 · p. 22
  • The singleton restriction fixes every agent’s bundle size at one good in this square-case payment minimization.This is the allocation class used to define B_sing.Source: B Missing Proofs of Section 4 · p. 22

B.1 Singleton reduction and computation

In the square case, the unrestricted optimum coincides with the singleton-allocation optimum with high probability. A maximum-weight perfect matching fixes the singleton allocation, and shortest paths compute its minimum supporting payments in cubic time.

B.1 Singleton reduction and computation

  • The maximum-weight perfect matching is unique almost surely because distinct matchings have different total welfare almost surely.Any singleton envy-free allocation must maximize welfare, since the payment terms cancel when its envy-free inequalities are summed against another matching.Source: §B.1 · p. 23
  • For the welfare-maximizing matching, the coordinatewise minimal nonnegative envy-free payments equal maximum directed-path weights.The edge weight from i to j is v_i(j) − v_i(i); the shortest-path formulation uses its negation.Source: §B.1 · pp. 22–23
  • A maximum-weight perfect matching and all-pairs shortest paths each take O(n^3) time, yielding a cubic-time singleton optimum computation.All remaining steps take O(n^2) time.Source: §B.1 · pp. 22–23
  • With probability tending to one, the unrestricted optimum equals the singleton-allocation optimum, while every nonsingleton envy-free outcome costs n − o(n).The proof exhibits a singleton outcome with payment o_p(n), making it cheaper than every nonsingleton outcome with high probability.Source: §B.1 · pp. 24–25

B.2 The logarithmic compensation scale

The square-case minimum compensation has logarithmic scale, and with high probability the unrestricted minimum equals the singleton-restricted optimum. The proof derives a distribution-free representation of choice shares and uses it to bound singleton payments.

B.2 The logarithmic compensation scale

  • The change of variables from valuation rows to payment potentials yields a density involving a weighted-Laplacian determinant on each matching cell.The density sums contributions from directed forests toward the root set.Source: §B.2 · pp. 25–26
  • The choice-share map sends the relevant potential region bijectively to the positive probability simplex, preserving strict coordinate order.The proof establishes this by strict convexity and the first-order condition for the choice-share map.Source: §B.2 · pp. 25–27
  • Conditional on the root set, choice shares have a representation using independent exponential variables and a Gamma variable, normalized by their sum.Roots share Z/n; each nonroot share adds its exponential variable divided by the same normalizer.Source: §B.2 · p. 28
  • The minimum choice share satisfies p_min = Θ_p(n^−3/2), while the number of roots K is Θ_p(√n) and the maximum choice share is O_p(log n/n).Source: §B.2 · p. 28
  • For m_n = n and every fixed ε > 0, B_sing satisfies (1/(2β)) log n − O_p(1) ≤ B_sing ≤ (1/(2α)) log n + O_p(1).Source: §B.2 · p. 30
Loading 2610.10272v1…