| paper | Fair and Efficient Completion of Indivisible Goods |
| authors | Vishwa Prakash HV, Ayumi Igarashi, Rohit Vaish |
| venue | AAAI 2025 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 2
statement extracted from the paper’s text layer
Given finite good types \(G\), rational student-type masses \(\mu_t\), binary approval vectors \(a_t\), frozen bundles \(F_t\), and rational per-capita supplies \(q_g\), decide whether there exists a mass distribution \(x_{t,B}\) over whole bundles \(B\subseteq G\setminus F_t\) satisfying type-mass and supply constraints, with every occupied bundle meeting its evaluator type’s MMS threshold \(\lambda_t\), where \(\lambda_t\) is the maximum minimum value over all mass-feasible hypothetical completions of the frozen-slot population under \(a_t\).
A high-multiplicity course-allocation model with student types \(t\), masses \(\mu_t\), binary approvals \(a_t\), frozen bundles \(F_t\), and per-capita supplies \(q_g\); the variables are masses \(x_{t,B}\) assigned to indivisible whole bundles, and the objective is feasibility of the MMS constraints.
The mirror depends on accepting simultaneous replication of the resource stock; under a fixed-good interpretation, MMS becomes zero once the population exceeds the number of goods.
fatal: False
The mirror covers binary-additive MMS-COMPLETION, the MMS half of Theorem 2; it leaves Prop1, Pareto-optimality combinations, EF1, lexicographic results, and general-additive results untouched.
The strongest positive case is a high-multiplicity course-allocation mirror of the paper’s binary MMS result.
My lead anchor is Theorem 2, proved in this paper: “For binary additive valuations, MMS-COMPLETION and Prop1-COMPLETION can be solved in polynomial time.” I would mirror its MMS-COMPLETION half with the problem \(\mathrm{BinMMS\text{-}Completion}_\infty\).
The natural regime is a large course-allocation system. There are \(N\) students but only \(\tau\ll N\) complete student types. A type \(t\) specifies both its binary approval vector \(a_t:G\to\{0,1\}\) over a finite catalogue \(G\) of course or section types, and its frozen bundle \(F_t\) of mandatory courses. If two students have different frozen bundles, they are different types, as high multiplicity requires.
Each good type \(g\) has a per-capita supply \(q_g\). In a finite \(N\)-student realization, this means \(Nq_g\) indivisible copies of \(g\); \(q_g\) is rational and \(N\) is chosen so that all multiplicities are integral. Thus students still receive indivisible bundles: the continuum is in the mass of students receiving each whole bundle, not in fractional courses.
The instance consists of rational type masses \(\mu_t\), with \(\sum_t\mu_t=1\), the frozen bundles \(F_t\), the approval vectors \(a_t\), and the supplies \(q_g\). Let the residual supply be \(q_g^U=q_g-\sum_t\mu_t\mathbf 1[g\in F_t]\).
A completion is a family \(x_{t,B}\ge0\), where \(B\subseteq G\setminus F_t\) is a complete indivisible bundle and \(x_{t,B}\) is the mass of type-\(t\) students receiving \(B\). It must satisfy \(\sum_Bx_{t,B}=\mu_t\) for every \(t\), and \(\sum_{t,B:g\in B}x_{t,B}=q_g^U\) for every \(g\). The objective is feasibility: output such an \(x\), with every student receiving at least its MMS value, or certify that none exists.
The continuum MMS value must preserve the paper’s particular frozen-allocation definition. For each evaluator type \(t\), imagine a population of hypothetical bundles whose frozen states have masses \(\mu_s\). Define \(\lambda_t\) as the largest \(\lambda\) for which there exists a hypothetical completion \(z_{s,B}\) satisfying the same mass and supply constraints and such that every occupied configuration \((s,B)\) has value \(\sum_{g\in F_s\cup B}a_t(g)\ge\lambda\). The actual completion \(x\) is MMS-feasible exactly when every occupied \((t,B)\) satisfies \(\sum_{g\in F_t\cup B}a_t(g)\ge\lambda_t\).
This is recognisably the authors’ problem. Frozen mandatory courses remain frozen, all remaining indivisible goods must be completed, valuations are still binary additive, and MMS still evaluates every frozen bundle in the hypothetical partition—not merely the evaluator’s own bundle. The course-allocation motivation is already present in the paper, so this is not an artificial change of story.
I expect \(\mathrm{BinMMS\text{-}Completion}_\infty\) to be Class A. The proof route of Theorem 2 survives almost verbatim. For a fixed evaluator type \(t\) and threshold \(\lambda\), a lower-quota flow assigns approved residual goods to frozen-slot types \(s\), with lower quota \(\max\{0,\lambda-a_t(F_s)\}\) for mass \(\mu_s\). Testing the finitely many possible integer thresholds computes \(\lambda_t\). A second lower-quota flow enforces the resulting thresholds for the actual type masses. Rational capacities replace integer capacities, and the flow can be decomposed into a sparse distribution over whole bundles \(B\), so the formulation does not secretly replace indivisible allocations by average utilities.
Clearing denominators gives the exact bridge back: a rational solution \(x\) becomes a finite allocation of cloned students and cloned course goods, while every finite high-multiplicity instance produces such an \(x\). This is an extension-level mirror rather than a literal fixed-good limit, because supplies scale with the population. That scaling is necessary: with a fixed stock of goods and \(N\to\infty\), MMS would usually collapse to zero and the problem would become vacuous.
The mirror deliberately covers only the MMS-COMPLETION part of Theorem 2. It does not claim to cover the paper’s EF1 hardness results or the general-additive hardness results. Natural follow-up questions are whether the same construction handles the Prop1 half of Theorem 2, whether the PO restriction from Corollary 2 can be added without changing the flow structure, and where general additive valuations introduce genuinely hard configuration pricing.
The weakest point is the continuum extension of MMS itself. The paper defines MMS using an \(n\)-bundle partition, whereas the mirror replaces those bundles by a mass distribution over frozen-slot types. I believe this is the canonical normalized high-multiplicity limit, but a referee could reasonably demand a formal clone-consistency theorem. If “continuization” were required to keep the number of physical goods fixed while only the population grows, then this mirror would fail; its credibility depends on the repeated-student/repeated-course-seat regime being accepted as the relevant high-multiplicity instance class.
The strongest negative argument is a sharp dichotomy around Theorem 2. If only the population is continuized while the finite set \(M\) of indivisible goods is held fixed, MMS collapses. Once \(n>|M|\), every \(n\)-way partition contains an empty bundle, so every agent’s MMS value is \(0\). Frozen goods do not help: they are still among the same \(m\) goods. Thus MMS-COMPLETION becomes automatically feasible, and no choice of student type space repairs the degeneration. Replacing indivisible goods by divisible mass would avoid it only by moving to outcome-space continuity, which the programme excludes.
The proponent’s rescue is to scale course seats with the population. That is mathematically coherent, but it is no longer a population-only mirror of the paper’s fixed-good completion problem. It replaces \(m\) named goods by \(Nq_g\) repeated copies, lets the resource universe grow with \(N\), and introduces per-capita supply as a new asymptotic datum. The resulting object is a capacitated assignment problem over repeated item types. The flow argument then survives precisely because the model has been changed into that repeated-resource regime; it does not establish that the paper’s original MMS-COMPLETION problem has a nondegenerate population limit.
That said, this objection is conditional, not decisive under the programme’s broadest interpretation. Repeated course seats are a plausible high-multiplicity regime, and the goods remain indivisible. For rational masses and supplies, the proposed \(x_{t,B}\) can indeed be realized by cloning students and course copies; the evaluator-specific benchmark \(\lambda_t\) is a legitimate limit of the paper’s MMS definition. The flow is not secretly fractional allocation.
So I cannot honestly defeat this anchor universally. The negative case establishes only that a faithful fixed-resource continuization is vacuous. If ChoCo accepts simultaneous replication of agents and resources as a valid high-multiplicity regime, Theorem 2 supplies a genuine Class A mirror, and the proponent’s case survives.
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.