| paper | A Tight Negative Example for MMS Fair Allocations |
| authors | U. Feige, Ariel Sapir, Laliv Tauber |
| venue | WINE 2021 |
| filed under | fairalloc · shares |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Polynomial-time solvable; every instance is feasible. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 14
statement extracted from the paper’s text layer
For each \(N\ge4\), let \(n=\lceil(N+4)/2\rceil\) and use the Theorem 14 valuation types \(R,C\), masses \(\mu_R=\lfloor N/2\rfloor/N\) and \(\mu_C=1-\mu_R\), and per-capita supply \(\rho_g=1/N\) for every item class; decide whether masses \(x_{\theta,B}\) can be assigned to integral bundles \(B\) with \(\sum_Bx_{\theta,B}=\mu_\theta\), \(\sum_{\theta,B:g\in B}x_{\theta,B}=\rho_g\), and \(v_\theta(B)\ge W_\theta\) whenever \(x_{\theta,B}>0\), where \(W_\theta\) is the type's continuum MMS threshold.
A configuration model with valuation types \(\Theta=\{R,C\}\), type masses \(\mu\), item-class supplies \(\rho\), and variables \(x_{\theta,B}\) denoting mass of type \(\theta\) receiving integral bundle \(B\); maximize \(\lambda\) subject to the mass and supply constraints and support-wise guarantees \(v_\theta(B)\ge\lambda W_\theta\), with exact CMMS fairness at \(\lambda\ge1\).
The anchors do not establish the complexity of arbitrary continuous MMS allocation; they only motivate a new general configuration-LP problem beyond the explicitly constructed families.
fatal: False
The mirror covers the constructive goods-gap results in Theorems 1 and 14, while leaving the general upper-bound results, structural classification, chores extension, and exact computer-assisted gap verification largely untouched.
The strongest positive case is a genuine high-multiplicity MMS problem in which goods remain indivisible for every individual, but identical valuation types may be split across different integral bundles.
There is no named NP-hardness, P, FPT, or W[1]-hardness theorem in the supplied paper. Its named results are existence, gap, and computer-assisted optimization theorems. I therefore use two named theorems proved in the paper, with Theorem 14 as the lead.
The common mirror is as follows. Let \(\Theta\) be a finite set of valuation types, with population distribution \(\mu\). Let \(G\) be a finite set of good classes, with per-capita supply \(\rho_g\). An individual still receives an integral bundle \(B\) of goods; only the mass of agents receiving each bundle is fractional. The decision variable is \(x_{\theta,B}\), the mass of type \(\theta\) receiving \(B\), subject to \(\sum_B x_{\theta,B}=\mu_\theta\) and \(\sum_{\theta,B:g\in B}x_{\theta,B}=\rho_g\).
For each type \(\theta\), define its continuum MMS threshold \(W_\theta\) as the largest \(w\) for which there is a distribution \(y_B\) over integral bundles satisfying the per-capita supply constraints and \(y_B>0\Rightarrow v_\theta(B)\ge w\). The continuous problem asks for an allocation \(x\) maximizing \(\lambda\) such that every bundle receiving positive mass of type \(\theta\) satisfies \(v_\theta(B)\ge \lambda W_\theta\). Exact continuous MMS fairness is the case \(\lambda\ge1\). This is not fractional utility: no individual receives a fraction of a good, and the guarantee is support-wise, not merely in expectation.
The lead anchor is Theorem 14, proved in this paper. It states that, for \(N\ge4\), with \(n=\lceil (N+4)/2\rceil\), there is an allocation instance with \(N\) agents and at most \(N+4n-7\) items—\(3N+1\) items when \(N\) is even and \(3N+3\) when \(N\) is odd—such that every allocation gives some agent at most \(1-\frac1{f(n)}\) of her MMS, where \(f(n)=n^2(n-2)^2+n\). The construction uses only two valuation functions, \(V_R\) and \(V_C\), repeated among row and column agents, together with auxiliary items.
The continuous problem mirroring Theorem 14 is:
\(\textsc{Exact-CMMS}_{\infty}^{\mathrm{Thm14}}\). Given the theorem’s constructed instance, let \(\Theta=\{R,C\}\), let \(\mu_R=\lfloor N/2\rfloor/N\) and \(\mu_C=1-\mu_R\), and give every item class per-capita supply \(1/N\). Decide whether there is a measurable assignment of integral bundles to the two type masses such that every \(R\)-agent and every \(C\)-agent receives at least her continuum MMS \(W_R,W_C\).
This is a faithful high-multiplicity regime: take \(k\) copies of every item and \(k\) copies of every agent slot. For fixed \(N\), the number of agents grows as \(kN\), while there remain only two valuation types and a fixed collection of item classes. The two types can represent large cohorts with identical valuations over standardized indivisible resources.
On this family the answer is explicitly yes. The row type has an MMS partition consisting of the \(n\) row bundles and the \(N-n\) auxiliary singleton bundles; the column type has the analogous column partition. Every bundle in the relevant partition has value \(t_V=n^2(n-2)^2+n\), and the total value of all goods is \(Nt_V\), so \(W_R=W_C=t_V\). Give mass \(\mu_R/N\) of type \(R\) to each row-partition bundle and mass \(\mu_C/N\) of type \(C\) to each column-partition bundle. Each partition uses every item exactly once, so every item is consumed with mass \((\mu_R+\mu_C)/N=1/N\). Thus all agents receive their full continuum MMS.
The finite gap from Theorem 14 therefore disappears under the population mirror. This is not a defect: it isolates precisely the combinatorial obstruction caused by having only one named representative of each type. For \(k\) sufficiently divisible, the displayed mass allocation can be implemented exactly by cloning agents and goods; every clone still receives an integral bundle.
The second anchor is Theorem 1, also proved here. It states that there is a three-agent, nine-item additive-goods instance in which every allocation gives some agent at most \(\frac{39}{40}\) of her MMS, equivalently \(Gap(3,9)\ge\frac1{40}\).
Its continuous mirror is the concrete problem \(\textsc{Exact-CMMS}_{\infty}^{3,9}\). There are three types \(R,C,U\), each of mass \(1/3\), nine item classes each with per-capita supply \(1/3\), and the paper’s valuation matrices:
\(v_R=\begin{pmatrix}1&16&23\\26&4&10\\12&19&9\end{pmatrix}\),
\(v_C=\begin{pmatrix}1&16&22\\26&4&9\\13&20&9\end{pmatrix}\),
\(v_U=\begin{pmatrix}1&15&23\\25&4&10\\13&20&9\end{pmatrix}\).
The question is whether masses of these three types can be assigned to integral bundles, using every item class with mass \(1/3\), while every type receives at least its continuum MMS.
Again the answer is yes, explicitly. Each type’s MMS is \(40\): \(R\) uses the three rows, \(C\) the three columns, and \(U\) uses \(P=\{e_2,e_4\}\), \(D=\{e_3,e_5,e_7\}\), and \(Q=\{e_1,e_6,e_8,e_9\}\). Assign mass \(1/9\) of each type to each of its three MMS bundles. Every item appears once in the \(R\)-partition, once in the \(C\)-partition, and once in the \(U\)-partition, so its total use is \(1/9+1/9+1/9=1/3\). Every individual receives a bundle worth \(40\).
Thus Theorem 1’s finite nonexistence result does not transfer: the continuous population can divide each cohort across its own MMS bundles while preserving integral bundles at the individual level. This is exactly the kind of Class A phenomenon the continuization programme is meant to expose.
The expected classification is therefore Class A for these mirrors, though not yet a proved polynomial-time result in the general case. The configuration formulation has exponentially many bundle variables, so general tractability depends on whether the relevant pricing and MMS-threshold problems admit efficient separation. The paper’s LP and MIP machinery makes that a natural computational question, rather than making the mirror a mere restatement.
The further questions are substantial: whether exact continuous MMS fairness always exists under per-capita supplies; whether welfare maximization subject to exact MMS fairness is tractable; whether binary-encoded supplies create genuine pricing hardness; and which restrictions—type caps, nonreplicable goods, or support constraints—restore the finite MMS gaps.
The weakest point is that the mirror changes the quantifier from “one bundle for each named agent” to “a distribution of integral bundles across a mass of identical agents.” I believe that is the correct high-multiplicity interpretation, but it is also exactly where the finite theorem’s obstruction dissolves. If the authors insisted that every identical type must receive the same bundle, the mirror would be artificially discrete again. Conversely, if the programme requires a general complexity theorem rather than these explicit continuum constructions, this paper supplies no such anchor.
The decisive objection is that this paper has no named computational result to continuize. Theorems 1 and 14 are existential gap and nonexistence theorems; the LP and MIP are proof devices for a finite extremal claim, not algorithms or complexity classifications. Thus \(\textsc{Exact-CMMS}\) is a new fair-division problem inspired by the paper, not a computational mirror of one of its results.
The proposed Theorem 14 mirror is nevertheless a legitimate high-multiplicity construction. For its two types, let \(P_R\) and \(P_C\) be the row and column MMS partitions. Setting
\[ x_{R,B}=\frac{\mu_R}{N}\quad(B\in P_R), \qquad x_{C,B}=\frac{\mu_C}{N}\quad(B\in P_C) \]
does give every supported agent value \(t_V\), while each item is used with mass \(1/N\). I would not object that this splits identical types, or that individuals still receive integral bundles; those are precisely the natural high-multiplicity semantics.
But this certificate also exposes the weakness of the anchor. It is simply a convexification of two displayed partitions. On the fixed theorem family, feasibility is hard-coded and requires no pricing, separation, approximation, or complexity analysis. If one instead asks for arbitrary valuation types, supplies, and MMS thresholds, one has created a new configuration-LP problem. Theorem 14 supplies neither an algorithmic theorem nor a meaningful boundary for that problem.
Theorem 1 has the same defect. The assignment
\[ x_{\theta,B}=\frac{1}{9} \]
for each type \(\theta\in\{R,C,U\}\) and each bundle \(B\) in that type’s displayed MMS partition is a valid aggregate allocation: every item receives total mass \(1/3\), and every individual bundle remains integral. This shows that the finite obstruction disappears when cohorts may be split across bundles. It does not computationally mirror the theorem; it replaces its central quantifier—one bundle for each named agent—by a distribution over bundles.
A stronger possible mirror would study the asymptotic quantity obtained by taking \(k\) copies of every agent type and \(k\) copies of every item, then letting \(k\) grow. That is a coherent question, but it is not determined by the paper: scaling agents without goods is infeasible, scaling goods and agents gives the convexified limit, and other scaling regimes give different benchmarks. Asking for the general limit, its exact computation, or its approximation complexity would be a new high-multiplicity MMS programme, not a result extracted from this paper.
So the negative case is strong for ChoCo’s stated computational agenda: neither proposed anchor is a named computational theorem, and each fixed mirror is an explicit convex-combination certificate. The honest weakness is that the proponent’s model is not malformed. Under the programme’s broad definition, it supports a potentially worthwhile new project on high-multiplicity MMS allocation. What it does not provide is a worthwhile continuous mirror of this particular paper’s computational content, because that content is absent.
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.