| paper | Simplification and Improvement of MMS Approximation |
| authors | Hannaneh Akrami, Jugal Garg, Eklavya Sharma, Setareh Taki |
| venue | IJCAI 2023 |
| filed under | fairalloc · shares |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 1 is an existence guarantee, not a numbered result about the complexity or computation of a problem; the exact-MMS NP-hardness statement appears only as background. The proposed scaled-inventory configuration problem is meaningful and plausibly recognizable to the authors, but it cannot supply the missing computational anchor. Theorem 2’s restricted \(\texttt{bagFill}\) barrier does not change that conclusion.
fails bit a — no named computational result to mirror
The proposed mirror covers the paper’s main \(\alpha\)-MMS existence guarantee and treats Theorem 2 only as evidence about a restricted algorithmic framework; it does not cover a named computational theorem, exact finite-instance MMS computation, or unrestricted optimal-allocation complexity.
The strongest positive case is a high-multiplicity mirror of the paper’s main existence result, Theorem 1. I would not claim that every part of the paper continuizes equally well.
Take a large population of households receiving indivisible goods from a catalogue \(G\). A type \(t\) is a complete additive valuation vector \(v_t\in\mathbb{Q}_{\ge 0}^{G}\). The population is described by masses \(\mu_t\), with \(\sum_t\mu_t=1\). There are only \(\tau\) valuation types, where \(\tau\) is small, while the number of households is very large. The inventory is given per capita by \(q\in\mathbb{Q}_{\ge0}^{G}\): a finite replication with \(Kq_g\) copies of good \(g\) serves \(K\) households. Each physical copy remains indivisible.
A bundle is therefore an integral vector \(b\in\mathbb{Z}_{\ge0}^{G}\), not a fractional bundle. A continuous allocation is a collection of masses \(\lambda_{t,b}\), where \(\lambda_{t,b}\) is the fraction of type \(t\) receiving bundle \(b\), satisfying
\[ \sum_b\lambda_{t,b}=\mu_t \]
and
\[ \sum_{t,b}\lambda_{t,b}b_g=q_g \]
for every good \(g\). Thus the continuum aggregates many deterministic integral allocations; it does not give an individual a fraction of a good.
The appropriate continuous MMS benchmark for type \(t\) is
\[ \operatorname{cMMS}_t(q) = \sup_{\rho} \left\{ \eta: \sum_b \rho_b b=q,\quad \rho_b>0\Rightarrow v_t(b)\ge \eta \right\}, \]
where \(\rho\) is a probability distribution over integral bundles. This is exactly the high-multiplicity limit of partitioning \(Kq\) goods into \(K\) bundles and taking the least-valued bundle. A mass allocation is \(\alpha\)-cMMS if every bundle receiving positive mass from type \(t\) has value at least \(\alpha\operatorname{cMMS}_t(q)\).
The named anchor is Theorem 1, proved in this paper. It states that every finite fair-division instance with additive valuations admits a
\[ \left( \frac34+ \min\left(\frac1{36},\frac{3}{4(4n-1)}\right) \right)\text{-MMS allocation}. \]
The continuous problem I would hand to a prover is:
\[ \textsc{High-Multiplicity-MMS} \]
Given rational \((G,T,\mu,q,v)\) and a rational \(\alpha\), decide whether there exists a finite-support mass allocation \(\lambda\) satisfying the inventory constraints and
\[ \lambda_{t,b}>0 \quad\Longrightarrow\quad v_t(b)\ge \alpha\operatorname{cMMS}_t(q) \]
for every type \(t\) with \(\mu_t>0\). The optimization version maximizes \(\alpha\), and a solution is an explicit finite list of integral bundles and their assigned masses.
The bridge to Theorem 1 is direct. Choose \(K\) so that \(K\mu_t\) and \(Kq_g\) are integral, construct the \(K\)-replicated finite instance, and apply Theorem 1. Its guarantee is
\[ \alpha_K= \frac34+ \min\left(\frac1{36},\frac{3}{4(4K-1)}\right), \]
which tends to \(3/4\) as \(K\) tends to infinity. The resulting finite allocations have empirical bundle distributions; a limiting subsequence gives a mass allocation of the form above. The missing technical lemma is to prove carefully that finite MMS values converge to \(\operatorname{cMMS}_t(q)\), with appropriate rounding statements in the reverse direction. That is a genuine deliverable, not an assumption.
I expect the unrestricted exact problem to be Class B rather than continuum-specifically hard. The configuration variables are masses of integral bundles, and computing the continuous MMS benchmark or pricing feasible bundles can still encode partition and knapsack through the goods and valuation dimensions. The combinatorics live in \(G\) and the valuation numbers, not in the number of named agents. However, for fixed \(|G|\), fixed valuation alphabets, or bounded bundle structure, the problem has a credible Class A or parameterized route through configuration LPs and type-level transportation. The paper’s ordered-instance reductions and bagFill procedure suggest precisely the kind of structure one would try to aggregate.
The regime is plausible in a disaster-relief or public-benefits setting: millions of households, a catalogue of repeated indivisible items, and a small number of need profiles. The type includes the entire valuation vector, so this is not pretending that idiosyncratic prices disappear. It simply studies the regime where many households genuinely share the same profile. The authors would still recognize the problem: additive valuations, indivisible bundles, the same MMS benchmark, and the same objective of maximizing the guaranteed fraction.
The paper’s Theorem 2, also proved here, is useful supporting evidence rather than a second anchor. Its Example 1 has identical valuations for all agents, hence only one valuation type, and the bound
\[ \frac{3n}{4n-2} = \frac34+\frac{3}{8n-4} \]
tends to \(3/4\). This suggests a further continuous question: whether the large-population limit of the paper’s reduction-plus-bagFill technique has an exact \(3/4\) worst-case barrier even when \(\tau=1\). I would not present Theorem 2 as a general upper bound for all continuous allocations, since it concerns a restricted algorithmic class.
The weakest point is that MMS is intrinsically defined using a finite number of bundles, and passing to an essential-infimum over a distribution of bundles changes the object. Moreover, a meaningful continuum requires the inventory to scale with the population; with a fixed finite set of physical goods, almost everyone receives nothing. My mirror therefore depends on accepting the natural high-multiplicity regime in which both households and item copies grow, while each individual allocation remains integral. If one instead makes goods divisible, the problem becomes easier but ceases to be a population-only continuization and falls outside the programme’s scope.
The strongest negative case is a source-discipline objection: the proposed anchor is not actually a named computational result of the paper. Theorem 1 is an existence theorem. It states that an \(\alpha\)-MMS allocation exists; it does not state a complexity bound, an approximation algorithm theorem, or a parameterized result. The paper’s algorithmic discussion is informal, and Algorithm 1 explicitly requires computing an exact MMS partition, which the paper itself notes is NP-hard. Thus \(\textsc{High\text{-}Multiplicity\text{-}MMS}\) is a newly manufactured computational problem inspired by Theorem 1, not a continuization of a computational theorem proved here.
The proposed model also cannot be obtained by continuizing the population alone. If the paper’s finite set of goods \(M\) is held fixed while the number of agents grows to \(K\), then once \(K>|M|\), every \(K\)-way partition has an empty bundle. With nonnegative valuations, every agent’s MMS becomes zero. The only way to avoid this degeneration is the proponent’s additional assumption that the inventory itself scales to \(Kq\). That is sensible, but it changes the model into a repeated-agent, repeated-inventory configuration problem. The new object contains a per-capita supply vector \(q\), integral bundle configurations, and an asymptotic resource-scaling convention absent from the paper.
The proposed \(\operatorname{cMMS}\) further confirms that this is an extension rather than a direct mirror. Finite \(K\)-agent instances permit only bundle distributions whose masses are multiples of \(1/K\); \(\operatorname{cMMS}\) permits arbitrary real distributions \(\rho\) satisfying an average-inventory equation. Convergence may well hold, but the proponent concedes that the required convergence and reverse-rounding theorem is missing. Clearing denominators can require a \(K\) far larger than the binary encoding of \(q\), so running the finite algorithm on a replicated instance is not a polynomial-time high-multiplicity algorithm. A genuine ChoCo result would need a compressed configuration formulation and a complexity analysis in the encoding length of \((\mu,q)\), not merely a finite theorem applied to an exponentially replicated instance.
Theorem 2 supplies no independent rescue. Its upper bound concerns only algorithms restricted to bagFill and the four reduction sets \(S_k\); it is not a lower bound on the best MMS allocation. Indeed, the example has identical valuations, and the paper explicitly notes that MMS allocations exist for identical valuations. A continuous allocation over configurations is not required to use bagFill, so Theorem 2 says nothing about the optimum of the proposed continuous problem. Moreover, the example uses \(m=3n-1\) position-specific goods with values depending on their ranks. Preserving it as \(n\) grows requires growing the goods catalogue or changing the valuation structure; repeating a fixed finite catalogue does not reproduce the example.
A stronger version of the proponent’s proposal is nevertheless quite plausible: finitely many valuation types, rational population masses, a repeated finite catalogue of indivisible goods, per-capita supplies, and mass distributions over whole integral bundles. Disaster-relief or public-benefit allocation makes that regime recognizable, and it avoids the usual identity and multiplicity objections. Its configuration LP could be an interesting new Class A/B/C problem.
That concession is important. The universal claim that no worthwhile mirror exists is not honestly sustainable against that stronger extension. The defensible negative verdict is narrower: this paper supplies no qualifying named computational anchor, and the proposed MMS construction is a substantial repeated-resource re-modelling whose computational bridge remains to be proved. Under a strict ChoCo screen, that is enough to reject it; under an extension-friendly screen, 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.