| paper | Maximin Share Guarantees for Few Agents with Subadditive Valuations |
| authors | George Christodoulou, Vasilis Christoforidis, Symeon Mastrakoulis, Alkmini Sgouritsa |
| venue | IJCAI 2025 |
| filed under | fairalloc · shares |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
The paper fails bit (a): none of Theorems 1–5 asserts a complexity classification, algorithm, or computational approximation guarantee. The two-type mass model is a plausible new fair-division extension, but it requires a clone-lift, supply scaling, valuation encoding, and a new optimization objective; its \(1/2\)-decision version is also guaranteed yes by Theorem 2. Thus it cannot provide this paper with a qualifying continuous computational mirror.
fails bit a — no named computational result to mirror
The proposed extension chiefly covers the many-agent, two-valuation-type regime of Theorem 2; Theorem 1 and Theorems 3–4 concern fixed small-agent guarantees, while Theorem 5 is a finite impossibility result.
The paper has no qualifying computational anchor under the programme’s rule. Theorem 1, Theorem 2, Theorem 3, and Theorem 4 are existence or characterization theorems; Theorem 5 is an impossibility theorem. They are proved in this paper, but none asserts NP-hardness, membership in P, fixed-parameter tractability, an approximation algorithm, or query complexity. The cited lower bounds from Ghodsi et al. are also existence/impossibility results, not computational anchors. Thus, strictly speaking, there are zero anchor-specific continuous problems to report.
The strongest positive case nevertheless comes from Theorem 2, proved here. It is the only result whose regime genuinely supports high multiplicity: arbitrarily many agents, but only two complete valuation types \(v_S\) and \(v_T\). A plausible scenario is a large recurring allocation of indivisible benefit packages to households from two standardized socioeconomic profiles. Households of the same profile have the same valuation of every bundle, while package supplies scale with the size of the population.
My lead candidate would be the following extension, which I would label an extension rather than a direct mirror.
Call it \(\textsf{TwoType\text{-}MMS}_\infty\). An instance contains two rational type masses \(\mu_S,\mu_T\) with \(\mu_S+\mu_T=1\); item categories \(G\); rational per-capita supplies \(\rho_g\) for \(g\in G\); a scale \(N\) such that \(N\mu_t\) and \(N\rho_g\) are integers; and two normalized, monotone, subadditive valuations
\[
v_t:\mathbb Z_{\ge 0}^{G}\to\mathbb Q_{\ge 0},
\qquad t\in\{S,T\}.
\]
A bundle is an integral vector \(b\), so goods remain indivisible. At scale \(N\), there are \(N\mu_t\) agents of type \(t\) and \(N\rho_g\) copies of item \(g\).
For each type, define
\[
\operatorname{MMS}_{t,N}(\rho)
=
\max_{\substack{b^1,\ldots,b^N\in\mathbb Z_{\ge0}^{G}\\
\sum_j b^j=N\rho}}
\min_{j\in[N]}v_t(b^j).
\]
The solution is a finite-support mass allocation \(x_{t,b}\ge0\), where \(x_{t,b}\) is the mass of type-\(t\) agents receiving bundle \(b\), satisfying
\[
\sum_b x_{t,b}=\mu_t
\quad\text{and}\quad
\sum_{t,b}b_gx_{t,b}\le \rho_g
\quad\text{for every }g.
\]
The objective is to maximize \(\alpha\) subject to
\[
x_{t,b}>0
\;\Longrightarrow\;
v_t(b)\ge
\alpha\,\operatorname{MMS}_{t,N}(\rho).
\]
Its decision version asks whether \(\alpha\ge\frac12\) is achievable.
This preserves the paper’s central object: indivisible bundles, subadditive valuations, type-specific MMS benchmarks, and the \(\frac12\)-guarantee. At rational points where \(Nx_{t,b}\) is integral, clearing denominators recovers an ordinary finite allocation exactly. The mass formulation is therefore a genuine high-multiplicity encoding, not a fractional-goods problem. Theorem 2 suggests \(\alpha\ge\frac12\) at every finite scale, provided the multiset valuation is a legitimate subadditive clone-lift of the paper’s valuation.
I would expect the aggregate optimization to have a plausible Class-A route when valuations admit polynomial-time configuration pricing or separation: the variables are bundle configurations, and the population dimension collapses to two types. With unrestricted subadditive value-oracle input, however, computing the MMS threshold and pricing acceptable bundles may itself be hard. Any such hardness would come from item/configuration combinatorics rather than population multiplicity, so it would be closer to Class B than to continuum-specific hardness.
Theorem 1 is a poor secondary anchor because it is explicitly limited to at most four agents. Theorems 3 and 4 likewise concern three-agent parameter vectors. Theorem 5 is a useful finite obstruction but does not naturally yield a population problem without specifying how the six indivisible items are replicated.
The weakest point is substantial: MMS is inherently defined relative to a finite number of agents, and arbitrary subadditive set valuations have no canonical way to value repeated item copies. Without supply scaling and an explicit clone-lift, the proposed mirror either has too few goods for a positive-mass population or silently fractionalizes the goods, leaving the paper’s problem. Moreover, the paper never supplies an algorithmic representation for its valuations. So this is a credible, author-recognizable continuous extension of Theorem 2, but not a strict positive case under the programme’s named-computational-anchor gate.
The decisive objection is that this paper has no qualifying computational anchor. Theorem 1, Theorem 2, and Theorems 3–4 are existence or parameter-characterization results; Theorem 5 is a fairness impossibility result. None gives a complexity classification, an algorithm, a hardness result, or even a query model. Thus every proposed “continuous question” is an additional computational problem invented around the paper, rather than a continuization of one of its computational results. Under ChoCo’s stated gate, that is already a strong negative verdict.
Theorem 2 is the only plausible rescue, and it does establish a legitimate high-multiplicity regime in one respect: arbitrarily many agents can share two complete valuation types. This should not be rejected merely because agents are grouped by type. That is exactly what high multiplicity means.
The difficulty is the goods. If the paper’s finite item set \(M\) is held fixed while the number of agents grows, then once \(n>|M|\), every \(n\)-partition contains an empty bundle. Since \(v(\varnothing)=0\), every agent’s MMS is \(0\), and the \(1/2\)-MMS guarantee becomes vacuous. The proposed repair—scaling item supplies with population size—may be sensible, but it creates a new multi-unit model. The original set valuation \(v:2^M\to\mathbb{R}_{\ge 0}\) does not determine a valuation on multisets \(v:\mathbb{Z}_{\ge0}^{G}\to\mathbb{R}_{\ge0}\). Two extensions can agree on every original bundle and behave entirely differently on repeated copies. Choosing a clone-lift, supply rates \(\rho\), and an input representation is therefore substantive new modelling, not a harmless limiting operation.
The proposed decision problem is also algorithmically empty at its advertised threshold. If every finite-scale clone-lift is a valid instance of Theorem 2, then the answer to “is \(\alpha\ge 1/2\) achievable?” is always yes. Maximizing the best \(\alpha\), finding an allocation, or computing the MMS threshold could be interesting, but those are new optimization problems not asserted by the paper. Their complexity depends entirely on whether valuations are given by value oracles, explicit tables, XOS descriptions, circuits, or some other encoding—the paper specifies none of this.
Theorem 1 does not repair the situation. Its content is intrinsically about at most four agents. Giving four valuation types positive mass changes the benchmark from a four-way partition to an \(N\)-way partition; cloning the four agents does not preserve the theorem’s object. Theorems 3 and 4 have the same problem, with the additional issue that \(d=(d_1,d_2,d_3)\) describes each agent’s MMS benchmark, not population multiplicity. Turning \(d\) into a type parameter would define a new fairness model, while keeping \(d\) fixed as the population grows again makes the benchmark unrelated to standard MMS.
Theorem 5 is only a finite six-item obstruction. Retaining those six items gives the same zero-MMS degeneration; replicating them requires exactly the unspecified multiset valuation and supply model described above. Whether the obstruction survives such a construction is not the objection—the point is that the paper supplies no population problem or computational question to which it could be attached.
I cannot honestly claim that no separately designed high-multiplicity MMS problem could ever be worthwhile. A new configuration-optimization problem for, say, two multi-unit valuation types might well merit study. But that would be a new ChoCo project inspired by the paper, not a continuous computational mirror of it. The defensible negative verdict is therefore strong under the programme’s anchor rule: this paper contributes no computational result, and its best high-multiplicity extension either has a vacuous fixed-supply limit or becomes an N-indexed, representation-dependent multi-unit problem whose natural \(1/2\)-decision version is already trivial.
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.