PaperlayerView exact revision on arXiv

Source-linked AI summary

Envy-Free Allocations for Random Non-Additive Valuations

Pasin Manurangsi

arXiv:2610.34434v1cs.GTmath.CO

TL;DR

The random-renaming model supports arbitrary non-additive valuations, but the supplied prior-results account leaves the general multi-agent case beyond two agents unresolved. The proof combines a second-moment count of good allocations with spectral and small-set expansion bounds for generalized Johnson graphs. For n ≥ 3 and n | m, envy-free allocations exist with high probability whenever m = ω(n360).

  • Problem

    The random-renaming model supports arbitrary non-additive valuations, but the supplied prior-results account leaves the general multi-agent case beyond two agents unresolved.

    Source: §1 · p. 2

  • Method

    The proof combines a second-moment count of good allocations with spectral and small-set expansion bounds for generalized Johnson graphs.

    Source: §1.2 · p. 4, §5 · p. 14

  • Results

    For n ≥ 3 and n | m, envy-free allocations exist with high probability whenever m = ω(n360).

    Source: §1 · p. 3

  • Takeaways & Limitations

    For all n ≥ 3 and valuation functions, envy-free allocations exist with high probability whenever m = ω(n360).

    Source: §1 · p. 3

    The authors identify a natural barrier for improving the threshold to m = ω(n2) using their spectral second-moment approach; the result leaves a polynomial gap to the birthday-paradox lower bound.

    Source: §5 · p. 14

Abstract

from arXiv · show

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.

1 Introduction

The paper resolves whether envy-free allocations exist with high probability for more than two agents under arbitrary non-additive valuations. It introduces the random-renaming model and combines a second-moment argument with graph expansion to prove existence under a polynomial item threshold.

1 Introduction

  • Indivisible items can prevent envy-free division in worst cases, motivating asymptotic study when item counts grow and preferences vary.The paper situates this work within asymptotic fair division and the challenge of extending it beyond additive valuations.Source: §1 · p. 1
  • In the random-renaming model, each agent independently permutes item names applied to an arbitrary base valuation, allowing general non-additive preferences.The model can capture complementarities and substitutabilities among items.Source: §1 · pp. 1–2
  • Prior results covered order-consistent valuations for multiple agents and arbitrary valuations for two agents, leaving the general case n > 2 open.The two-agent proof uses complementary bundles, a symmetry that does not extend to n ≥ 3.Source: §1 · pp. 2–3
  • For n ≥ 3 and n | m, envy-free allocations exist with high probability when m = ω(n360).The paper does not optimize the exponent, and identifies a birthday-paradox lower bound of m = Ω(n2) for constant-probability failure.Source: §1 · p. 3

1.2 Proof Overview

  • The proof counts good allocations with a second-moment argument, replacing hard-to-control envy-freeness probabilities with a top-α subset-rank condition.A good allocation gives each agent a bundle in her top tier while keeping the other bundles outside that tier.Source: §1.2 · p. 4
  • The moment bounds reduce to edge-collision probabilities in Kneser and generalized Johnson graphs, whose expansion properties control overlaps between bundles.The proof overview gives collision bounds O(α^19/18) for J(m, q, 0) and (1 + o(1/n))α2 for J(m, q, t) when t ≈ q/n.Source: §1.2 · pp. 5–6
  • The second-moment count is restricted to a large δ-intersection-balanced family to avoid atypically overlapping allocation pairs inflating its second moment.A union bound and concentration show that such a large family exists.Source: §1.2 · p. 6

2 Preliminaries

For n ≥ 3 agents and m divisible by n, the preliminaries set q = m/n and develop generalized Johnson graphs and δ-intersection-balanced families of balanced allocations.

2.1 Generalized Johnson and Kneser Graphs

  • J(m, q, t) connects q-element subsets of [m] whose intersection has size t; t = 0 gives the Kneser graph.A uniformly random oriented edge is a pair of adjacent subsets.Source: §2.1 · p. 7

2.2 δ-Intersection Balanced Allocations

  • A δ-intersection-balanced family keeps every pair of bundles’ intersections within a (1 ± δ) factor of their expected size, q/n.The condition applies to every bundle pair across each pair of allocations.Source: §2.2 · p. 7
  • If m > n^3 δ^-2 ln(nD), there exist D balanced allocations that are pairwise δ-intersection balanced.The proof samples D allocations independently and uses a union bound to establish existence.Source: §2.2 · p. 7

3 Proof of Main Theorem via Graph Collision Bounds

The proof bounds edge collisions in two graph regimes, then applies a second-moment argument over balanced allocations to bound the probability that no envy-free allocation exists.

3.1 Edge Collision Bounds in the Kneser and Generalized Johnson Graphs

  • In J(m, q, 0), the edge collision probability is O(α^19/18); near the expected overlap q/n, it is very close to α^2.The latter regime uses |t − q/n| ≤ δq/n, with δ ∈ (0, 1/6].Source: §3.1 · p. 8

3.2 Proof of Theorem 1.1 from Lemmas 3.1 and 3.2

  • The proof counts balanced allocations that are good for every agent; a positive count guarantees an envy-free allocation, and the second moment is bounded using the graph collision lemmas.The first moment for a fixed allocation is close to α^n; the second-moment argument uses pairwise δ-intersection-balanced allocations and Paley–Zygmund.Source: §3.2 · pp. 9–10
  • The probability that no envy-free allocation exists is at most 30n^2 m^-1/180.The proof sets ε = 30n^2 m^-1/180 and bounds the failure probability by ε.Source: §3.2 · p. 11

4 Proofs of the Graph Collision Lemmas

The graph-collision lemmas are proved using hypercontractivity for the Kneser graph and expander mixing with the generalized Johnson graph’s spectrum.

4.2 Proof of Lemma 3.2

  • For generalized Johnson graphs, the proof combines the Expander Mixing Lemma with a bound using the graph’s known spectrum.The spectrum is given by Eberlein polynomials.Source: §4 · p. 11, §4.2 · p. 12

4.1 Proof of Lemma 3.1

  • The Kneser-graph proof reduces to standard product-space hypercontractivity and bounds collision probability by α^19/18.For a vertex subset of density α, the proof obtains 5P[S ∈ T ∧ S′ ∈ T] ≤ α^19/18.Source: §4.1 · pp. 11–12

5 Conclusion

The paper proves high-probability envy-free existence for arbitrary non-additive valuations in the random renaming model under its stated item-count condition. Closing the gap to the Ω(n²) lower bound remains open, and the spectral second-moment approach encounters a barrier to that improvement.

5 Conclusion

  • For n ≥ 3 and m divisible by n, envy-free allocations exist with high probability when m = ω(n^360), without monotonicity, subadditivity, or positivity assumptions.The proof combines the second moment method, top-α subset ranking, and spectral analysis of generalized Johnson graphs.Source: §5 · p. 14
  • The gap between the m = ω(n^360) guarantee and the Ω(n²) birthday-paradox lower bound remains open.The paper asks whether m = ω(n²), with n | m, suffices for arbitrary valuations.Source: §5 · p. 14
  • For m = O(n³), an eigenvalue lower bound prevents the spectral approach from meeting its required bound, so reaching m = ω(n²) likely needs new ideas.The stated obstruction is max_{r≥1}|λ_r(m,q,t_i)| ≥ Ω(1/m), while the approach requires it to be ≪ 1/n³.Source: §5 · p. 14

AI Disclosure

The author describes the division of work between their own contributions and an AI assistant’s role in the paper.

AI Disclosure

  • The author discovered the top-α subset ranking idea and its connection to generalized Johnson graph expansion.Source: AI Disclosure · p. 14
  • Gemini discovered the proofs of the expansion bounds in Section 4 and helped draft the paper.Source: AI Disclosure · p. 14
  • The author says they verified and heavily edited all proofs and take full responsibility for their correctness.Source: AI Disclosure · p. 14
Loading 2610.34434v1…