| paper | Exact and Approximate Maximin Share Allocations in Multi-Graphs |
| authors | George Christodoulou, S. Mastrakoulis |
| venue | AAAI 2026 |
| filed under | fairalloc · shares |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-hard}\) · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given finite agent types \(A\) with masses \(\lambda_a\), finite item types \(R\) with endpoint sets \(\partial r\subseteq A\), regular high-multiplicity incidence data with the \(\Theta(N)\)-per-agent scaling needed for nondegenerate \(N\)-way MMS, and additive valuations \(v_a\), find masses \(x_{a,B}\) over integral bundle patterns \(B\) satisfying agent-mass and item-density conservation, such that every supported \(B\) has \(v_a(B)\ge\mu_a^\infty\) and every positive-mass pair \(B,D\) satisfies \(v_a(B)\ge\mu_a^2(B\uplus D)\). Here \(\mu_a^\infty\) is the maximin value obtained from distributions over integral bundle patterns with the appropriate normalized per-agent incident supply.
A configuration-LP model over agent types, mass, and integral bundle patterns: \(x_{a,B}\) is the mass of type-\(a\) agents receiving \(B\); item-type densities are conserved; the objective is feasibility of exact \(\mu_a^\infty\)-MMS and pairwise PMMS guarantees.
With fixed per-agent degree and \(O(N)\) item copies, literal \(N\)-way MMS can degenerate to zero, while aggregate \(q_r\) does not determine the regular incidence design; the mirror must explicitly specify dense scaling or define \(\mu_a^\infty\) as the normalized high-multiplicity limit.
fatal: False
The mirror covers Theorem 1's exact MMS-and-PMMS construction. It leaves the XOS, subadditive, independent-transversal, and other approximation and impossibility results outside the anchored question.
Under the programme’s literal anchor rule, this paper has no qualifying computational anchor. Its numbered results prove existence, approximation, and impossibility statements, but none states NP-hardness, membership in \(P\), FPT, W[1]-hardness, or a comparable complexity classification. The remarks that allocations can be “computed efficiently” are not formal numbered complexity results; the NP-completeness claim about EFX is cited prior work, not a result proved here.
The strongest substantive rescue is nevertheless a natural high-multiplicity mirror of Theorem 1.
Theorem 1, proved in this paper, states: every multigraph with \(n\) additive agents has an orientation that is simultaneously an exact MMS allocation and a PMMS allocation.
Consider finitely many agent types \(A\), with masses \(\lambda_a\) summing to \(1\). Each item type \(r\) has total mass \(q_r\) and is incident to at most two agent types, \(\partial r\subseteq A\). The incidence structure is regular: all agents of type \(a\) see the same multiset of incident item copies, and have the same additive valuation \(v_a\). Thus a concrete realization with \(N\) agents has \(N\lambda_a\) agents of type \(a\), \(Nq_r\) parallel item copies of type \(r\), and every item is allocated integrally to one of its endpoint agents.
A bundle pattern \(B\) is an integral multiset of incident item copies. Let \(x_{a,B}\) be the mass of type-\(a\) agents receiving \(B\). Feasibility requires \(\sum_Bx_{a,B}=\lambda_a\) for every \(a\), and \(\sum_{a,B}b_r(B)x_{a,B}=q_r\) for every item type \(r\). Define the continuum MMS value \(\mu_a^\infty\) by partitioning the per-agent incident supply into a probability distribution over integral bundle patterns and maximizing the minimum \(v_a(B)\) in its support. The question is:
\[ \textsc{Continuous Graphical Exact MMS--PMMS}: \]
given \((A,\lambda,q,v)\), find such an \(x\) in which every supported bundle satisfies \(v_a(B)\geq\mu_a^\infty\), and every pair of supported bundles satisfies the direct type-level PMMS condition \(v_a(B)\geq\mu_a^2(B\mathbin{\uplus}D)\).
This is a genuine population continuization. The individual outcome remains an integral bundle and every item remains assigned to an endpoint; only the mass of identical agents receiving each bundle is fractional. Rational instances embed into finite regular multigraphs by clearing denominators, while finite regular multigraphs collapse to these mass variables. A large market of repeated organisational roles competing for repeated pairwise service lots or contract items is a plausible regime: \(N\) is large, while the number of roles and item classes is fixed.
I would expect this mirror to be Class A. The cut-and-choose construction in Theorem 1 should lift to the type level, and the aggregate formulation is a configuration LP. The new result would be a high-multiplicity implementation theorem—especially a polynomial-time algorithm under compressed supplies—not something established by the paper.
A second, weaker but still meaningful mirror comes from Theorem 11, also proved here: every multigraph with subadditive agents admits a \(1/2\)-MMS orientation, while for every \(\varepsilon>0\) some instance has no \((1/2+\varepsilon)\)-MMS allocation. Its continuous version uses the same \((A,\lambda,q)\) model with subadditive type valuations and asks for the largest \(\alpha\) such that \(v_a(B)\geq\alpha\mu_a^\infty\) for every positive-mass bundle pattern. The expected question is whether the \(1/2\) barrier survives regular high multiplicity. I expect it to survive in dense pairwise markets, although that would be an approximation-bound transfer, not a computational-hardness result.
The weakest point is decisive: neither mirror is anchored to a named computational-complexity theorem. The paper supplies a strong mathematical subject for continuization, especially Theorem 1, but under the ChoCo eligibility rule it cannot honestly be presented as a fully compliant computational case.
I would reject this paper under the programme’s eligibility rule. Neither proposed anchor is a computational result. Theorem 1 is an existence theorem; Theorem 11 is a matching approximation guarantee. The paper contains no numbered complexity classification, input model, polynomial-time bound, parameterized result, or hardness theorem of its own. The concluding claim that the allocation “can be computed efficiently” is not a formal complexity result. Thus a continuous configuration problem inspired by either theorem would be a new fair-division project, not a continuization of a computational contribution.
Theorem 1’s proposed mirror is also less clean than it appears. The paper’s MMS value for an agent is defined by partitioning her incident items into \(n\) bundles, where \(n\) is the number of agents. In a fixed finite-type population with \(O(N)\) total item copies and \(N\) agents, each agent sees only \(O(1)\) relevant items; eventually an \(N\)-way partition has empty bundles and \(\mu_i^N=0\). The discrete benchmark therefore degenerates.
To prevent that, one must make the item supply grow as \(O(N^2)\), or replace the finite MMS benchmark by the proposed support-based quantity \(\mu_a^\infty\). Either move is legitimate only as a new modelling decision. The latter is not the paper’s MMS limit: it is a max-min lottery over integral bundle patterns. The former requires a dense incidence structure and a precise scaling regime absent from the paper. Moreover, aggregate quantities \(q_r\) do not by themselves specify the individual incidence design needed by the graph model; encoding that design either introduces growing micro-types or another substantial new object.
Theorem 11 is no stronger as an anchor. Its upper-bound construction relies on \(n\) distinct agents, \(n\) bundle coordinates, and a complete \(n\)-partite conflict pattern: every complete canonical bundle of one agent intersects every canonical bundle of another. In a fixed high-multiplicity type space, those agent and bundle labels cannot simply be collapsed without changing the valuation. Retaining them makes the number of types or item coordinates grow with the population, so the construction is not a fixed-type high-multiplicity regime. The proposed continuous \(1/2\)-MMS question therefore needs a new obstruction, not merely a scaling of Lemma 8.
The configuration-LP formulation may be mathematically sensible, and I would not claim that no researcher could make it interesting. That is the honest weakness of the negative case: a carefully rebuilt dense-market model with a new MMS benchmark might become a worthwhile fair-division paper. But it would not be a ChoCo mirror of this paper’s computational results. Under the programme’s gate, both anchors fail, and the paper should receive a negative verdict.
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.