| paper | On Fair and Efficient Allocations of Indivisible Goods |
| authors | J. Garg, Aniket Murhekar |
| venue | AAAI 2021 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 5
statement extracted from the paper’s text layer
Given rational type masses \( \mu_t \) with \( \sum_t \mu_t=1 \), rational per-capita supplies \( 0\le \sigma_j\le1 \), and additive \( k \)-ary values \( v_{tj} \) for types \( t\in T=[\tau] \) and goods \( j\in[m] \), find masses \( z_{t,B}\ge0 \) for integral bundles \( B\subseteq[m] \) satisfying \( \sum_B z_{t,B}=\mu_t \) and \( \sum_{t,B:j\in B}z_{t,B}=\sigma_j \), such that every pair of positive-mass cohorts satisfies \( \mathrm{EF1} \) under \( v_t(B)=\sum_{j\in B}v_{tj} \), and no capacity-feasible fractional reallocation weakly improves every supported cohort while strictly improving one. Determine whether such an allocation can be computed in time polynomial in \( m,\tau,k \) and the input bit length, independently of the common population denominator.
A high-multiplicity course-allocation model with finitely many valuation types \( T \), mass distribution \( \mu \), per-capita supplies \( \sigma \), integral bundle columns \( B \), decision variables \( z_{t,B} \), and a feasibility objective of finding support-level \( \mathrm{EF1} \) plus continuum \( \mathrm{fPO} \).
The mirror requires a nontrivial compression and limit theorem: scaling supplies, restricting bundle multiplicities, and enforcing EF1 across positive-mass support cohorts may produce an extension rather than a direct restatement of Theorem 5.
fatal: False
The mirror covers the \( k \)-ary \( \mathrm{EF1}+\mathrm{fPO} \) algorithmic result of Theorem 5, while leaving the general pseudo-polynomial results, EQ1 results, constant-agent results, MNW result, and \( \mathrm{PLS} \) membership result unmirrored.
I would make one positive case, led by Theorem 5.
The anchor is Theorem 5, proved in this paper: “Given a \(k\)-ary fair division instance \(I\), where \(k\) is a constant, an allocation that is both EF1 and fPO can be computed in time \(\poly(m,n)\).” This is not cited from elsewhere; it is proved here from the paper’s general algorithm, Theorem 3, together with Lemma 7’s bound \(U\le (m+1)^k\).
The continuous mirror I would propose is Continuous \(k\)-ary EF1+\(\mathrm{fPO}\).
There are finitely many good classes \(G=[m]\), finitely many agent types \(T=[\tau]\), and rational masses \(\mu_t\ge 0\) with \(\sum_t\mu_t=1\). Type \(t\) has additive values \(v_{tj}\) for good class \(j\), with at most \(k\) distinct values among the \(m\) goods. Each good class \(j\) has a rational per-capita supply \(\sigma_j\): in a population of \(N\) agents, there are \(N\sigma_j\) interchangeable copies of that good. The copies remain indivisible.
An integral bundle is a subset \(B\subseteq G\), with utility \(v_t(B)=\sum_{j\in B}v_{tj}\). The decision variable is \(z_{t,B}\), the mass of type \(t\) receiving bundle \(B\). It must satisfy
\( \sum_B z_{t,B}=\mu_t \)
for every type \(t\), and
\( \sum_{t,B:j\in B}z_{t,B}=\sigma_j \)
for every good class \(j\). Thus the population is continuous, but every individual in the resulting society receives an integral bundle. The mass variable only records how many agents receive each bundle.
The EF1 requirement is imposed pointwise on positive-mass cohorts: whenever \(z_{t,B}>0\) and \(z_{u,B'}>0\), type \(t\) must satisfy
\( v_t(B)\ge v_t(B'\setminus\{j\}) \)
for some \(j\in B'\). This is not an average-utility relaxation. Every positive-mass group of agents must be EF1 with respect to every other positive-mass group.
The fPO requirement is also the paper’s requirement, translated to the continuum. There must be no fractional reallocation \(y_{t,B,j}\in[0,1]\) satisfying
\( \sum_{t,B}z_{t,B}y_{t,B,j}\le \sigma_j \)
for every \(j\), while giving every positive-mass cohort weakly higher utility,
\( \sum_j v_{tj}y_{t,B,j}\ge v_t(B), \)
and giving at least one positive-mass cohort strictly higher utility. The requested output is therefore a finite-support mass allocation \(z\) satisfying EF1 and fPO; this is a search problem, not a welfare-maximization problem.
This is a genuine high-multiplicity regime. For a common denominator \(N\), the instance becomes a finite fair-division instance with \(N\mu_t\) agents of type \(t\) and \(N\sigma_j\) copies of good class \(j\). As \(N\) grows, the number of named agents becomes enormous while \(\tau\), \(m\), and \(k\) remain fixed or moderate. A natural setting is a large course-allocation market: many students fall into a small number of complete valuation profiles, and course seats are offered in large interchangeable cohorts. The paper itself gives the “rate goods using a few values” interpretation, so the authors should recognise this as their problem rather than as an unrelated model.
The expected classification is Class A: tractable, although this is a conjectural continuation of the paper rather than a theorem already proved there. The paper’s key reason for tractability is precisely the feature that survives aggregation: with constant \(k\), each type has only polynomially many possible utility levels, \(U\le(m+1)^k\). The price/MBB and alternating-transfer arguments behind Theorem 5 should have an aggregate version in which identical agents and identical transfer events are processed in batches of mass rather than one named agent at a time. A configuration or column-generation formulation would expose the bundle patterns, while the \(k\)-ary restriction should keep the relevant utility and pricing structure polynomially bounded.
The central question is therefore:
Given rational \(\mu\), \(\sigma\), and \(k\)-ary additive valuations \(v\), can one compute a mass allocation \(z\) satisfying integral-bundle EF1 and continuum fPO in time polynomial in \(m\), \(\tau\), \(k\), and the input bit length, independently of the population denominator?
That question also preserves the paper’s boundary. If \(\tau\) is allowed to be as large as the number of named agents, the discrete problem embeds directly by taking each agent as its own type; hardness can then transfer. The interesting mirror is the high-multiplicity regime with small \(\tau\), where population multiplicity—not the number of alternatives or valuation dimensions—is what disappears.
The weakest point is that Theorem 5 is polynomial in the paper’s explicit number of agents \(n\), not in the number of types \(\tau\) plus the bit length of their masses. Running the paper’s algorithm on \(N\) cloned agents would therefore not establish the desired result: \(N\) may be exponentially larger than the input encoding. Moreover, the continuum solution may require a distribution over exponentially many bundles, and proving a polynomial-support representation or an efficient pricing oracle is a real part of the problem. The opposing analyst can fairly say that the paper supplies the structural motivation, not the aggregate algorithm.
That weakness does not make the mirror artificial. It identifies exactly the new computational question: whether the paper’s \(k\)-ary tractability survives the passage from named agents to massed types. I would not stretch this anchor to claim coverage of the paper’s EQ1 results, constant-\(n\) results, MNW result, or Theorem 15’s PLS membership. Theorem 5 alone gives a precise and credible continuous-population problem.
The proponent’s sole anchor, Theorem 5, is a genuine computational result, so the strongest decisive objection—“there is nothing here to mirror”—is unavailable. The negative case must instead attack whether the proposed high-multiplicity object remains this paper’s fair-division problem.
The paper allocates \(m\) individually indivisible goods, each available once. If the population is made continuous while those goods remain fixed, the limit degenerates: only finitely many agents can receive anything, and almost every unit of population has the zero bundle. EF1 then becomes largely vacuous, while the individual structure responsible for the paper’s algorithm disappears. Thus a nontrivial mirror must scale the supplies as well.
But scaling supplies changes the object more substantially than the proponent admits. With \(N\) copies of every good class, one must decide whether an agent may receive several copies of the same class. Allowing that produces a multi-unit fair-division problem with different bundles, utility ranges, and EF1 comparisons. Forbidding it, as the proposed \(B\subseteq G\) formulation does, imposes a new course-enrolment-style constraint absent from the paper. Either choice is defensible, but neither is forced by Theorem 5; the proposed mirror is therefore a new capacitated allocation model, not a direct continuization of the stated problem.
The deeper difficulty is that the paper’s \(k\)-ary argument controls the number of utility values available to each named agent. It does not control the number of bundle cohorts that must be represented after aggregation. Even with only \(\tau\) valuation types, an allocation may require support over exponentially many integral bundles \(B\subseteq G\). EF1 is a condition on pairs of assigned bundles, not merely on type utilities, and fPO concerns the entire fractional exchange structure. The paper gives no compression theorem showing that its alternating-path and least-spender dynamics can be carried out on type masses and polynomially many bundle columns. The proponent’s “batch the transfers” claim is precisely the missing theorem, not an implication of Theorem 5.
There is also a genuine limiting mismatch. In a finite cloned instance, a cohort of one agent still participates in EF1 and fPO. In the continuum, a vanishing cohort disappears unless the model explicitly imposes conditions on every positive-mass support component. That repair is reasonable, but it replaces individual fairness by support-level fairness. The result can be useful, yet it is no longer simply the paper’s EF1 guarantee under a change of notation.
Thus the best negative conclusion is that Theorem 5 does not itself justify a worthwhile continuous mirror: the faithful fixed-supply limit is degenerate, while the nondegenerate scaled-supply version requires new feasibility rules, new bundle representations, and a new compression theory. However, this case is not airtight. The scaled course-allocation interpretation is natural, the authors would likely recognize it as their problem, and the gap—whether EF1+\(\mathrm{fPO}\) survives type-mass aggregation—is a legitimate high-multiplicity computational question. I cannot honestly claim that this anchor has been defeated; the negative case is weak precisely because the proposed mirror survives as a plausible new problem even though the paper does not solve it.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.