| paper | Fair Division of Indivisible Goods: A Survey |
| authors | Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, Alexandros A. Voudouris |
| venue | IJCAI 2022 |
| filed under | fairalloc · chores-online |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | high |
| authors would recognise it | no |
The paper contains no qualifying numbered computational result, so it fails the objective computational-anchor requirement. Moreover, the proposed mass-EF1 model requires repeated goods with per-capita supply, changing the finite-goods problem into a new market model outside the population-only scope. The opponent therefore defeats both the anchor gate and the proposed rescue.
fails bit a — no named computational result to mirror
With finitely many indivisible goods, almost every nonatomic agent receives \(\varnothing\), making EF1 vacuous; the proposed positive supplies \(\sigma_g\) introduce repeated resources rather than merely continuizing the population.
fatal: True
The only proposed anchor is Algorithm 2; the survey's NP-hardness and algorithmic claims elsewhere are unnumbered prose summaries and do not satisfy the anchor rule.
The strongest honest case is conditional, because this survey contains no qualifying numbered Theorem, Lemma, Corollary, or Proposition. Its numbered items are Definitions 1–7, Algorithms 1–2, and Open Problems 1–10. The NP-completeness and NP-hardness claims occur only in prose summaries of cited work. Thus there is no theorem number I can quote without inventing one.
The only plausible anchor is Algorithm 2 (Round-Robin), which the survey reports as computing an EF1 allocation for additive valuations. This is an algorithmic result reported from Caragiannis et al. [2019b], not a numbered theorem proved in the survey. If numbered algorithms are accepted as anchors, it gives a credible positive case.
The mirror would be a High-Multiplicity EF1 Allocation problem. There are finitely many good kinds \(G=\{g_1,\ldots,g_q\}\), finitely many agent types \(T\), rational masses \(\mu_t\) with \(\sum_t\mu_t=1\), and additive valuations \(v_t(g)\in\mathbb Q_{\ge0}\). Type \(t\) means agents with exactly the same valuation vector. The regime is a large institution with \(N\) agents, \(N\) very large, but only \(\tau\ll N\) valuation types; goods are standardized indivisible items with many distinct copies of each kind.
A continuous allocation is a mass \(x_{t,B}\ge0\), where \(B\) is an integral bundle and \(x_{t,B}\) is the mass of type-\(t\) agents receiving that whole bundle. It must satisfy
\[ \sum_B x_{t,B}=\mu_t \]
for every \(t\), and
\[ \sum_{t,B} B_gx_{t,B}=\sigma_g \]
for every good kind \(g\), where \(\sigma_g\) is the per-capita supply. Individuals still receive indivisible bundles; \(x\) records only how the population is distributed among bundles.
The question is: find a finite-support \(x\) such that, for every pair of supported bundles \(B\) and \(B'\), with the first assigned to type \(t\) and the second to type \(t'\),
\[ v_t(B)\ge v_t(B')-\max_{g:B'_g>0}v_t(g). \]
This is precisely EF1: every agent’s envy toward every other supported bundle can be removed by deleting one good. The objective is to output such a compressed allocation, rather than expanding \(N\) named agents.
The original authors should recognise this as their problem: the valuation model and EF1 condition are unchanged, while the list of individual valuation vectors is replaced by its exact high-multiplicity representation. Round-Robin supplies the structural intuition: agents of the same type can be processed in bulk, and the resulting allocation can be represented by type–bundle masses. I would expect a Class A result for fixed \(q\) and \(\tau\), using a configuration-flow or column-generation formulation, with rounding back to finite populations. If \(q\) is unrestricted and bundle pricing is implicit, the pricing problem may itself become hard; that boundary would be a useful further question.
The weakest point is substantial: to avoid the degeneracy of infinitely many agents competing for finitely many goods, the mirror uses many copies of good kinds and aggregate supply \(\sigma\). Although each finite approximant still has indivisible goods, an opponent can reasonably argue that this also continuizes the resource side. The case therefore supports a population mirror most convincingly in large markets with repeated standardized goods, not for an arbitrary finite-goods instance.
If the anchor rule is applied strictly, however, the correct conclusion is that this paper offers no admissible named computational anchor. The survey’s unnumbered statement that computing MMS is NP-hard would be a stronger hardness anchor, but it cannot be used under the stated requirements.
The paper should fail the programme’s anchor gate before one even reaches modelling. It contains no numbered Theorem, Lemma, Corollary, or Proposition asserting a computational result. Algorithm 2 is a numbered procedure, but its EF1 guarantee is stated only in surrounding prose and attributed to earlier work. Thus there is no qualifying named computational result in the paper to mirror. The unnumbered NP-hardness statement for MMS cannot repair this, especially since it was not one of the proposed anchors.
Even if numbered algorithms are admitted, Round-Robin does not yield a faithful population-only mirror. Keep the paper’s \(m\) indivisible goods fixed and replace the agents by a nonatomic population. Each good can be assigned to at most one agent, hence its recipient is a measure-zero point. With finitely many goods, almost every agent receives \(\varnothing\). EF1 then holds almost everywhere for a vacuous reason, while the finitely many recipients carrying all the interesting information disappear from the type-mass distribution. If fairness is required also for those exceptional agents, the model must retain their identities and assignments; the society distribution \(\mu\) is no longer sufficient.
The proposed rescue—\(q\) good kinds with positive per-capita supplies \(\sigma_g\)—changes the problem in exactly the way the programme’s scope excludes. A finite approximant now contains roughly \(N\sigma_g\) copies of each good kind. The allocation
\[ \sum_{t,B} B_g x_{t,B}=\sigma_g \]
is therefore a high-multiplicity market model with repeated resources, not the population continuization of a finite set \(M\) of indivisible goods. It may be a sensible new model, but it continuizes the resource side as well. The alternative rescues are equally different: allowing a good to be shared is divisible-resource fair division; randomizing its recipient is ex-ante fairness; retaining exceptional recipients restores individual-level data.
Round-Robin itself does not close this gap. Its proof relies on a finite serial order of named agents, successive choices, and the first good selected by one agent. A type–bundle mass \(x_{t,B}\) is an aggregate allocation, not the execution of that procedure. To obtain one, one must add a priority schedule and repeated-copy supply, neither of which follows from Algorithm 2 or from the survey’s formulation.
The identity objection is not the right one here: EF1 is indeed type-based once bundles are known. Nor would it be legitimate to object that a continuous version might be easy or hard. The obstruction is more basic: with fixed indivisible goods the continuum collapses, while the nondegenerate version requires a different, resource-scaled market problem.
The honest limitation is that, if ChoCo deliberately expands its scope to large markets with repeated standardized goods, the proposed mass-EF1 problem is plausible and potentially worthwhile. But that is an independent high-multiplicity fair-division model, not a continuous mirror anchored by this survey. Under the stated named-result and population-only requirements, this paper provides no defensible mirror.
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.