| paper | Improved MMS Approximations for Few Agent Types |
| authors | Parnian Shahkar, Jugal Garg |
| venue | IJCAI 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 4
statement extracted from the paper’s text layer
For two types \(i\in\{1,2\}\), rational masses \(\mu_i\) with \(\sum_i\mu_i=1\), finite good profiles \(G\), rational per-capita supplies \(s_g\), and additive values \(v_i(g)\), define \(\beta_i(s)\) as the supremum \(\beta\) for which finite-support masses \(\lambda_B\ge0\) over integral bundles \(B\in\mathbb{Z}_{\ge0}^{G}\) satisfy \(\sum_B\lambda_B=1\), \(\sum_B B_g\lambda_B\le s_g\), and \(v_i(B)\ge\beta\) whenever \(\lambda_B>0\). Decide whether finite-support masses \(\lambda_{i,B}\ge0\) exist with \(\sum_B\lambda_{i,B}=\mu_i\), \(\sum_{i,B}B_g\lambda_{i,B}\le s_g\), and \(\lambda_{i,B}>0\Rightarrow v_i(B)\ge\frac{4}{5}\beta_i(s)\) for each type.
Two valuation types with masses \(\mu_i\), per-capita supplies \(s_g\) of indivisible good profiles, and configuration masses \(\lambda_{i,B}\) over integral bundles; maximize \(\alpha\) subject to mass balance, supply constraints, and \(v_i(B)\ge\alpha\beta_i(s)\).
Because the paper's polynomial-time guarantee is measured in expanded \(n\), the mass/configuration version needs a new binary-encoded algorithm and a proof that \(\beta_i(s)\) matches the cloned MMS benchmark.
fatal: False
The mirror covers Theorems \(3\), \(4\), and \(5\), and Corollaries \(2\) and \(3\); it leaves Theorem \(2\), auxiliary structural results, the cited MMS PTAS, and unrelated chores results untouched.
The strongest positive case is the paper’s two-type result, anchored on Theorem 4, proved in this paper: “Given a 2-type ONI\(_\alpha\) instance, Algorithm 2 returns a \(\frac45\)-MMS.” Theorem 5 is a credible secondary anchor: it proves a \(\frac{16}{21}\)-MMS allocation for three types. These are named algorithmic approximation results, although the paper does not contain a named theorem explicitly stating an NP-hardness or \(P\)-classification. I would not smuggle its unnumbered polynomial-time remark into the anchor.
The mirror is a high-multiplicity fair-division market. A type is exactly the paper’s type: a complete additive valuation vector over the goods. The population is represented by masses \(\mu_i\), with \(\sum_i\mu_i=1\), rather than by named agents. A plausible regime is a national allocation of many course seats, housing units, offices, or placements to millions of applicants belonging to two or three stable preference classes. The number of agents is very large, while the number of valuation types is fixed at two or three.
For indivisible goods, a fixed finite inventory cannot support a meaningful atomless limit: eventually almost everyone receives nothing. The honest high-multiplicity regime must scale resources with the population. Let \(G\) be a finite set of good profiles, \(s_g\in\mathbb{Q}_{\ge0}\) the per-capita supply of profile \(g\), and \(v_i(g)\) the value of one copy to type \(i\). Clearing denominators by a scale \(q\) gives \(q\mu_i\) agents of type \(i\) and \(qs_g\) indivisible copies of \(g\).
I would define the lead problem, Two-Type Batch-MMS\(_\infty\), as follows. An allocation is a finite-support collection of masses \(\lambda_{i,B}\), where \(B\in\mathbb{Z}_{\ge0}^{G}\) is an integral bundle and \(\lambda_{i,B}\) is the mass of type-\(i\) agents receiving that whole bundle. It must satisfy
\[ \sum_B\lambda_{i,B}=\mu_i \]
for each type \(i\), and
\[ \sum_{i,B} B_g\lambda_{i,B}\le s_g \]
for every good profile \(g\). Given per-type MMS benchmarks \(b_i\) — \(b_i=1\) in the paper’s normalized setting — the question is whether one can find such an allocation with
\[ \lambda_{i,B}>0 \quad\Longrightarrow\quad v_i(B)\ge \frac45 b_i. \]
The optimization version maximizes the largest achievable \(\alpha\). This is not an average-utility relaxation: every positive mass of agents receives an entire indivisible bundle meeting the MMS threshold. If \(\mu\), \(s\), and \(\lambda\) are rational, clearing denominators produces an ordinary finite allocation of cloned agents and indivisible goods, with the same bundle values and certificates. That rational-clone correspondence is the main fidelity argument.
This is an author-recognizable mirror of Theorem 4. Algorithm 2 already works by assigning bags to type masses according to majority size, minority valuations, and threshold claims. Its comparisons of \(T_1\) and \(T_2\) become comparisons of \(\mu_1\) and \(\mu_2\); its bag-filling phase becomes a mass allocation over integral bundle configurations. I expect the fixed-\(\frac45\) feasibility problem to be tractable in the paper’s approximation sense—Class A—using the same structural argument plus a configuration formulation and the paper’s PTAS-qualified MMS computation. Exact optimization of the best \(\alpha\) may remain Class B, because the residual difficulty lies in integral bundle configurations and can survive after cloning.
The secondary anchor is Theorem 5, also proved here: “Given a 3-type ONI\(_\alpha\) instance, Algorithm 3 returns a \(\frac{16}{21}\)-MMS.” Its continuous problem, Three-Type Batch-MMS\(_\infty\), uses the same bundle-mass formulation with \(\mu_1\ge\mu_2\ge\mu_3\), and asks for a feasible allocation satisfying
\[ \lambda_{i,B}>0 \quad\Longrightarrow\quad v_i(B)\ge \frac{16}{21}b_i \]
for all three types. The four bag classes \(C_1,C_2,C_3,C_4\) become mass classes, and comparisons such as \(|C_j|>T_j\) become \(c_j>\mu_j\). The two-part Algorithm 5 is particularly suggestive of a finite-type continuous algorithm: it maintains only which types remain active or saturated and the available high-, middle-, and low-valued item mass.
I again expect the fixed-guarantee problem to be Class A, though less confidently than the two-type case. The genuine open work is proving that the integer bag-filling and boundary cases commute with rational mass limits. No continuum-specific hardness is apparent; if hardness remains, it should come from indivisible goods and configuration structure, hence Class B rather than Class C.
The mirror covers the paper’s main positive results, Theorems 4 and 5, together with Theorem 3 and Corollaries 2 and 3. It does not try to continuize every proof device or the cited PTAS. Natural follow-up questions are whether \(\frac45\) and \(\frac{16}{21}\) are tight as functions of the mass vector, whether finite-clone allocations round from a mass solution with a controlled additive loss, how hard exact clone-MMS computation remains, and whether a useful ratio exists for \(k\) types with \(k\) growing.
The weakest point is unavoidable: this is an extension, not a literal atomless limit of one fixed finite set of goods. Per-capita resource scaling and a mass distribution over whole integral bundles are necessary to prevent MMS from degenerating, but a strict referee could say that the resource side has also been continuized. The case survives because the population semantics are exactly the paper’s few-identical-types regime, utilities remain additive, goods remain indivisible within each bundle, and rational masses recover finite cloned instances exactly. The first theorem of the ChoCo extension should nevertheless prove that the clone-MMS benchmark and the paper’s bag-filling guarantees commute with this limit.
The strongest negative case is against the proposed *direct* mirror, not against every possible high-multiplicity extension. The paper passes the named-result gate: Theorems 4 and 5 are genuine algorithmic approximation results. But neither theorem supplies the continuous algorithm the proponent claims.
With a fixed finite set of goods, the literal atomless limit degenerates. An indivisible good can be assigned to only one agent, hence to a zero-mass subset of the population. Almost all agents receive the empty bundle, so every positive MMS guarantee disappears. Thus a population distribution \(\mu\) alone cannot be the mirror.
The proposed repair scales the goods with the population. That is mathematically sensible, but it changes the problem into a joint high-multiplicity market \((\mu,s,v)\), where \(s_g\) is per-capita supply. The paper’s normalization \(b_i=1\) is not automatically defined by \(\mu\); one must instead define an asymptotic benchmark such as
\[ \beta_i(s)=\max\left\{\beta: \sum_B\lambda_B=1,\ \sum_B B_g\lambda_B\le s_g,\ v_i(B)\ge\beta\ \text{whenever }\lambda_B>0 \right\}. \]
That is a new configuration problem, not merely the paper’s population with counts replaced by masses.
For Theorem 4, rational-clone correspondence cuts both ways. A rational mass allocation \(\lambda\) can indeed be cleared to a finite cloned instance, so the theorem’s \(4/5\) guarantee transfers as an existence corollary. But this means the continuous statement adds no new fairness theorem. The new computational question is whether one can solve the cloned problem in time polynomial in the binary encoding of the multiplicities. Algorithm 2 does not establish that: it explicitly constructs \(n\) high-valued items, \(n\) bags, and performs operations whose running time is polynomial in expanded \(n\), not in \(\log n\). Its configuration formulation has potentially exponentially many integral bundles, and no compact separation algorithm is provided. Calling this Class A is therefore speculation, not a consequence of Theorem 4.
Theorem 5 is weaker as an anchor. Algorithm 3 depends on a particular majority-type SHV partition, the four integer classes \(C_1,\ldots,C_4\), and Algorithm 5’s sequential removal of individual high-, middle-, and low-valued items. Replacing \(|C_j|\) and \(T_j\) by masses does not preserve that algorithm: one must first construct a common partition of the scaled inventory and then prove that the saturation and bag-filling process commutes with the high-multiplicity limit. If arbitrary configuration mixtures are allowed instead, the formulation remains meaningful, but Theorem 5 no longer supplies its algorithm or proof.
Thus both anchors establish, at most, plausible high-multiplicity extensions whose existence guarantees follow by cloning. They do not establish a population-only continuum, nor a compressed continuous algorithm. The real difficulty has migrated into the indivisible-good/configuration side, while the population distribution itself contributes no new structure.
I cannot honestly defend the universal claim that no worthwhile mirror exists. Repeated course seats or housing units with a few exact valuation classes give a plausible author-recognizable extension, and rational clone fidelity is unusually strong here. The defensible negative verdict is narrower: the proponent has shown an interesting high-multiplicity fair-division programme, but has not shown that Theorems 4 or 5 already yield a worthwhile continuous computational mirror, let alone the claimed Class-A result.
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.