PaperlayerView exact revision on arXiv

Source-linked AI summary

Envy-Free Decompositions of Random Assignments: Settling Four Agents, and What Lies Beyond

Keyi Li, Yihao He, Quanyi Li

arXiv:2609.35192v1cs.GT

TL;DR

A random assignment’s ex-ante SD-EF matrix can admit decompositions with very different realized envy, leaving open whether every such matrix has a Dec-EF decomposition. The paper combines convexity, envy-budget arguments, and exact computational certificates to settle the four-agent case and establish further structural results. It also identifies limits of canonical decompositions and an unresolved complexity boundary.

  • Problem

    Although SD-EF is a property of the assignment matrix, realized envy depends on the decomposition, and the general existence question for Dec-EF decompositions remained open.

    Source: §1 · p. 1

  • Method

    The paper uses convexity to reduce profile-wise worst cases to SD-EF polytope vertices and certifies the cases by exact LPs and rational decompositions.

    Source: §1 · pp. 1–2, §3 · p. 3

  • Results

    Every SD-EF matrix with four agents is EF-decomposable; the paper also settles five agents with at most four preference types and all five-agent probabilistic-serial matrices.

    Source: §1 · p. 2, §8 · p. 8

  • Takeaways & Limitations

    The envy budget fixes each agent’s total envy across decompositions, so any Dec-EF failure must concentrate envy on particular pairs.

    Source: §1 · p. 1, §8 · p. 8

    For SD-EF inputs, the complexity of computing t* and finding a Dec-EF decomposition remains open.

    Source: §8 · p. 8

Abstract

from arXiv · show

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.

1 Introduction

A random assignment’s matrix can satisfy stochastic-dominance envy-freeness while its decomposition yields very different realized envy. This paper settles the four-agent case and develops structural, computational, and complexity results on when Dec-EF decompositions exist.

1 Introduction

  • The matrix fixes agents’ lotteries, but a decomposition fixes the joint outcomes that determine realized envy, so equal matrices can yield different ex-post fairness.For three agents with identical preferences, cyclic shifts yield envy probability 2/3, whereas the uniform distribution over six assignments keeps each pairwise probability at 1/2.Source: §1 · p. 1
  • The paper reduces each profile’s worst-case SD-EF matrix to vertices and certifies those cases with rational decompositions checked in exact arithmetic.A convexity argument makes vertex checks sufficient, while the envy-budget identity shows that violations require envy concentration on particular pairs.Source: §1 · pp. 1–2
  • Every SD-EF matrix with four agents admits a Dec-EF decomposition, certified by exact enumeration of 26,927 vertices across 762 profiles up to symmetry.The paper also settles five agents with at most four preference types and certifies the probabilistic serial matrix for every five-agent profile; adversarial search finds no counterexample up to seven agents.Source: §1 · p. 2
  • For every n, two structural classes are settled: matrices with at most two distinct rows and profiles where all but two agents share a preference.For the latter class, the maximum-entropy decomposition is Dec-EF; the proof uses a monotonicity lemma for weighted least-squares rankings.Source: §1 · p. 2
  • Natural decompositions can fail: greedy Birkhoff–von Neumann can approach envy probability (n−1)/n, and maximum entropy fails at n=4 when all preferences differ.The paper also reports that dependent rounding fails in experiments and that mixing with the uniform matrix gives structure-dependent approximation guarantees.Source: §1 · p. 2

1.1 Related Work

  • Deciding EF-decomposability for arbitrary random assignments is strongly NP-complete, while the related work situates Dec-EF among ex-ante and ex-post fairness guarantees.The related-work discussion contrasts realized-assignment Dec-EF with interim envy-freeness, which restricts pairwise joint distributions.Source: §1 · p. 2, §1.1 · p. 2
  • The proof follows computer-aided social-choice work but uses polyhedral convexity to obtain a finite reduction and rational certificates verifiable in exact arithmetic.The paper distinguishes this continuous optimization setting from prior SAT- or SMT-based impossibility proofs.Source: §1.1 · p. 2

2 Preliminaries

The preliminaries define assignment matrices, SD-EF, and Dec-EF, then formulate the smallest achievable maximum envy probability as an optimization problem over decompositions.

2 Preliminaries

  • An assignment matrix P is bistochastic, with entry P_io giving the probability that agent i receives object o; its rows are agents’ lotteries.The paper uses strict preference ranks and preference types to describe profiles.Source: §2 · p. 2
  • SD-EF matrices form a polytope containing the uniform matrix, defined by stochastic-dominance comparisons between agents’ lotteries.For each agent, its lottery stochastically dominates every other agent’s lottery according to its own preference.Source: §2 · p. 2
  • A decomposition is a distribution over deterministic assignments whose weighted permutation matrices reproduce P; its envy probabilities measure realized pairwise envy.A decomposition is Dec-EF when every ordered pair’s envy probability is at most 1/2, and P is EF-decomposable if it has such a decomposition.Source: §2 · pp. 2–3
  • The optimization objective t*(P) minimizes the maximum pairwise envy probability over decompositions, and EF-decomposability is equivalent to t*(P) ≤ 1/2.The profile-level quantity maximizes t*(P) over the SD-EF polytope; the cited prior results cover n≤3 and profiles with at most two preference types.Source: §2 · p. 3
  • Greedy Birkhoff–von Neumann repeatedly removes a maximum-bottleneck permutation, whereas maximum entropy chooses the unique decomposition maximizing entropy.Both canonical decompositions depend on P alone.Source: §2 · p. 3

3 Structural Results

Two structural facts organize the analysis: convexity reduces the worst case to vertices, while an envy-budget identity fixes each agent’s total envy across decompositions. Together they explain the 1/2 threshold and why failure must come from concentrating envy on particular pairs.

3 Structural Results

  • Because t*(P) is convex and piecewise linear, the maximum over an SD-EF polytope is attained at a vertex, so checking every vertex suffices.The paper’s proof mixes optimal decompositions for two matrices to establish convexity, then uses the convexity of the sublevel set t*(P)≤1/2.Source: §3 · p. 3
  • LP duality gives a weighted characterization of t*(P) as the maximum, over distributions on ordered pairs, of the minimum weighted envy over decompositions.The first equality follows from von Neumann’s minimax theorem; the paper uses the characterization for adversarial search and connects it to a later weighted problem.Source: §3 · p. 3
  • For every agent, the sum of its envy probabilities toward others equals its expected rank, regardless of which decomposition implements P.In a realized assignment, the number of agents envied equals the number of objects preferred to the agent’s own object; SD-EF bounds the expected-rank total by (n−1)/2.Source: §3 · p. 3
  • For SD-EF matrices, the envy-budget bound makes the average envy probability toward other agents at most 1/2 in every decomposition.Thus a violation of Dec-EF must concentrate envy on particular pairs rather than increase its total amount.Source: §3 · p. 3
  • The threshold is tight: the uniform matrix has minimum maximum envy probability 1/2, and identical-preference agents’ two envy probabilities sum to 1.SD-EF also forces identical-preference agents to have equal rows, since dominance in both directions gives equal preference-prefix sums.Source: §3 · p. 3

4 Four Agents and Beyond

The paper certifies Dec-EF decomposability for every four-agent SD-EF matrix, then extends exact computations to restricted five- and six-agent cases and five-agent probabilistic-serial assignments. Adversarial searches find no counterexample through seven agents.

Computational method

  • Convexity reduces each profile’s universal decomposability check to its SD-EF polytope’s vertices, where exact rational certificates verify the envy bound.The pipeline enumerates vertices and checks decompositions in exact arithmetic.Source: §4 · p. 3

Four agents

  • Every four-agent SD-EF matrix is EF-decomposable, with the worst-case envy threshold exactly 1/2.Exact rational decompositions certify all 26,927 vertices across 762 profile orbits.Source: §4 · p. 4

Five agents

  • Every five-agent SD-EF matrix with at most four distinct preferences is EF-decomposable.The proof exactly enumerates and certifies the vertices for the three- and four-type cases.Source: §4 · p. 4

Six agents

  • Every six-agent SD-EF matrix with three pairs of agents sharing preferences is EF-decomposable.The computation certifies all 50,833,539 type-reduced vertices.Source: §4 · p. 4

Probabilistic serial

  • For every five-agent profile, the probabilistic serial assignment matrix is EF-decomposable.Each computed matrix received an exact rational certificate with maximum envy probability at most 1/2.Source: §4 · p. 4

Adversarial search

  • Ascent searches across profiles with five to seven agents found no value above 1/2, up to floating-point error.The searches used random restarts and covered 25,000 five-agent, 5,000 six-agent, and 1,300 seven-agent profiles.Source: §4 · p. 4

5 General 𝑛: Two Provable Classes

For general n, the paper proves Dec-EF results in two structural classes using symmetrization and maximum entropy. Product-form coupling bounds and a monotonicity lemma for weighted least-squares rankings support these results.

5.1 Symmetrization and Two Distinct Rows

  • For bistochastic matrices with at most two distinct rows and expected ranks at most (n−1)/2, symmetrizing any decomposition gives Dec-EF; SD-EF satisfies the rank condition.The result depends on the number of distinct rows, not preference types, and can cover profiles where every agent has a different preference.Source: §5.1 · pp. 4–5

5.2 Product-Form Couplings and Maximum Entropy

  • For product-form couplings with zero diagonal, stochastic dominance bounds envy probability by 1/2; maximum entropy yields such pair laws when all other agents have identical rows.For larger n, this argument requires the remaining agents to have identical rows; otherwise pair laws are generally not product-form and maximum entropy can fail.Source: §5.2 · p. 5

5.3 All Agents but Two Alike

  • When all agents but two share a preference, the maximum-entropy decomposition of every SD-EF matrix is Dec-EF.For positive matrices, the construction uses the unique zero-diagonal product-form coupling of the two exceptional agents, computed by matrix scaling.Source: §5.3 · pp. 5–6
  • A monotone least-squares ranking makes the envy difference a non-negative combination of the prefix differences constrained by SD-EF.The lemma establishes that every solution of the weighted Laplacian system ranks objects in the prescribed order when its weights satisfy the stated non-negativity conditions.Source: §5.3 · p. 5
  • The maximum-entropy decomposition in this class is computable in polynomial time by matrix scaling.The theorem covers the five-agent (3, 1, 1) and six-agent (4, 1, 1) patterns checked computationally.Source: §5.3 · p. 6

6 Canonical Decompositions and Approximation

The section evaluates natural decompositions and mixing bounds, showing that common matrix-only choices can concentrate envy while structural conditions can still guarantee Dec-EF.

Mixtures

  • Mixing a uniform decomposition with a decomposition of the residual matrix gives a (1−θ/2)-Dec-EF bound, where θ=1−n min_i,o P_io.The uniform component has envy probability 1/2; the residual component can be decomposed with envy probability at most 1.Source: §6 · pp. 6–7

Greedy decomposition

  • With λ_k=(2−ε)^−k, greedy decomposition envy tends to (n−1)/n, although t*(P)≤1/2+O(n^2ε).The SD-EF matrices have unique decompositions returned by greedy Birkhoff–von Neumann.Source: §6 · p. 7

Maximum entropy

  • Maximum entropy is Dec-EF for three agents, two distinct rows, or profiles where all but two agents share a preference.A four-agent counterexample therefore requires four distinct preferences.Source: §6 · p. 7
  • A four-agent SD-EF matrix has maximum-entropy envy probability 25/48>1/2, despite an optimum t*(P)=7/16.The maximum-entropy decomposition is the product-form member of the matrix’s decomposition segment.Source: §6 · p. 7

Dependent rounding

  • Dependent rounding reaches envy probability 0.52 at n=5 in experiments, and its negative-correlation guarantees do not control pairs of disjoint edges.The authors also show that independent-product comparisons of pair probabilities need not hold within a constant factor.Source: §6 · p. 7

7 Computational Complexity

The section establishes strong NP-completeness for Dec-EF decomposability of arbitrary assignments and NP-completeness for weighted envy minimization, including on SD-EF inputs.

Dec-EF decomposability

  • Deciding whether an arbitrary random assignment is EF-decomposable is strongly NP-complete, even for block-diagonal matrices with entries in {0, 1/6, 1/4, 1/3}.Approximating t*(P) within additive error 1/poly(n) is NP-hard.Source: §7 · p. 7
  • The hardness reduction encodes 3-colouring: a decomposition is Dec-EF exactly when its supported assignments yield proper colourings.The construction keeps all matrix entries constant, establishing strong NP-hardness.Source: §7 · pp. 7–8

Hardness gap

  • The general-input hardness does not settle the SD-EF max-envy problem; a constant gap follows from a 3-colouring hardness result with perfect completeness and a constant fraction of violated edges.In the stated gap, yes-instances have t*(P)=1/2, while no-instances have t*(P)≥1/2+1/(2|E|).Source: §7 · p. 8

Weighted envy

  • Weighted envy-threshold feasibility is NP-complete even when all agents share one preference and P is the uniform SD-EF matrix.With identical preferences, weighted envy counts backward arcs in the assignment-induced order.Source: §7 · p. 8

8 Conclusion

The paper settles the four-agent open case and extends results to selected five-agent settings, while identifying unresolved routes to guarantees for larger profiles.

Conclusion

  • Every SD-EF matrix with four agents is EF-decomposable; the result also covers five agents with at most four preference types and all five-agent PS matrices.Adversarial search found no counterexample through seven agents.Source: §8 · p. 8
  • The four-agent case is settled: because t* is convex, vertices suffice, and each certificate is a small rational decomposition, making the computer-aided proof checkable.Source: §8 · p. 8
  • A proof for more preference types must handle pair laws that are not product-form; no constant α<1 independent of n is known, and the SD-EF complexity questions remain open.The open questions include computing t* and finding a Dec-EF decomposition on SD-EF inputs.Source: §8 · p. 8

A Supplementary Proofs

The supplementary proofs establish continuity and coupling properties for maximum entropy, support its fairness results under row-structure conditions, and formulate an LP for two-row components.

A.1 Two topological facts

  • The EF-decomposable matrices form a polytope, and the unique maximum-entropy decomposition varies continuously with P.This continuity transfers α-Dec-EF guarantees from convergent perturbed matrices to their limit.Source: §A.1 · p. 9

A.2 The maximum-entropy form (Corollary 5.3)

  • When all agents outside a pair have identical rows, the maximum-entropy pair marginal has zero-diagonal product form, yielding envy probabilities at most 1/2 under SD-EF.The proof uses symmetry in the entropy dual and applies by continuity to general P.Source: §A.2 · p. 9

A.3 The product-form coupling (Theorem 5.4)

  • For two selected agents, alternating row and column scaling constructs a zero-diagonal product-form coupling with the prescribed marginals; it is the unique such maximum-entropy coupling.The construction relies on a positive off-diagonal coupling and matrix scaling for the prescribed zero pattern.Source: §A.3 · p. 9

A.4 Remarks on Lemma 5.5

  • The weighted least-squares ranking is monotone under the proof’s nonnegative sign condition, but general additive weights can break monotonicity.The proof also bounds consecutive score differences by 4/n in the normalized solution.Source: §A.4 · p. 10

A.5 The two-row LP (Section 6)

  • For each agent bipartition, an LP computes the maximum weight of a two-row component contained in P, subject to row-sum, expected-rank, and entrywise constraints.The variables are the scaled component rows and their weight.Source: §A.5 · p. 10

B.1 Pipeline and what is certified

The pipeline reduces the guarantee to checking vertices of each SD-EF polytope, then certifies each vertex with a rational decomposition. Exact runs cover the four-agent case, selected five- and six-agent profile classes, and probabilistic serial matrices for five agents; adversarial searches up to seven agents found no value above 1/2, up to floating-point error.

B.1 Pipeline and what is certified

  • The worst value over an SD-EF polytope is attained at a vertex, so certifying every vertex suffices to establish the guarantee for every matrix in that profile.Profiles are enumerated up to relabeling; the four-agent run covers 762 such profile orbits.Source: §B.1 · p. 10
  • 26,927 four-agent vertices receive rational certificates checked by an independent verifier, with certificates confirming the marginals, SD-EF, and envy probabilities at most 1/2.The orbit certificates cover all 244 profiles.Source: §B.1 · p. 10
  • Type reduction makes the five-agent, four-type case and six-agent pattern (2, 2, 2) tractable by representing identical-preference agents with one row and multiplicities.The reduction follows because SD-EF in both directions forces agents with identical preferences to have identical rows.Source: §B.1 · p. 10

B.2 Runs

  • Every five-agent probabilistic-serial matrix in 1,876,016 orbits passes exact rational certification with every envy probability at most 1/2.The certificates verify nonnegative weights and exact marginals; the full-LP fallback was not needed.Source: §B.2 · p. 10
  • Across random and three-type profiles for n=5 and n=6, and random profiles for n=7, adversarial ascent found a maximum of 1/2 up to floating-point error.The search alternates between a min-max LP and movement to a polytope vertex maximizing its dual multipliers.Source: §B.2 · p. 10

B.3 Examples

The examples section reports exact-run coverage and illustrates that natural decomposition rules can exceed the 1/2 envy threshold. It also identifies a profile pattern covered by a general theorem.

B.3 Examples

  • Table 3 states that every enumerated vertex, and every PS matrix, received a rational certificate of t*≤1.The supplied caption does not specify further run-by-run comparisons.Source: Table 3 · p. 11
  • The multiplicity pattern (4, 1, 1) is covered for every n by Theorem 5.4.Source: §B.3 · p. 11
  • Bipartite dependent rounding with lexicographic cycle choice reaches maximum envy 0.522±0.004 on an n=5 SD-EF instance, while random cycle choice reaches about 0.51.A random search found maximum-entropy envy up to 0.502 at n=5.Source: §B.3 · p. 11

C Reproducibility

The paper provides its code and result summaries as ancillary files, along with dependencies and entry points for reproducing major runs and checks.

C Reproducibility

  • Ancillary files include code and result summaries; the listed dependencies are Python 3.10+, numpy, scipy (HiGHS), and pycddlib 3.Source: C Reproducibility · p. 11
  • Named entry points cover typed exhaustive runs, exact PS certification, adversarial ascent, examples, dependent rounding, and checks for the two-plus and complexity results.Source: C Reproducibility · p. 11
Loading 2609.35192v1…