| paper | Maximin Share Allocations on Cycles |
| authors | Zbigniew Lonc, M. Truszczynski |
| venue | IJCAI 2018 |
| filed under | fairalloc · shares |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-complete}\), already for \(\tau=1\) and nonnegative integer utilities. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 3.1
statement extracted from the paper’s text layer
Given a finite goods set \(V\), a complete compatibility graph, a nonnegative rational additive utility \(u\), a rational threshold \(k\), and population mass \(1\) with per-capita supply \(\sigma_v=\frac12\) for every \(v\in V\), decide whether variables \(x_B\ge0\), for \(B\subseteq V\), exist such that \(\sum_{B\subseteq V}x_B=1\), \(\sum_{B\ni v}x_B=\frac12\) for every \(v\in V\), and \(x_B>0\Rightarrow u(B)=\sum_{v\in B}u(v)\ge k\). Each positive \(x_B\) is mass receiving the integral bundle \(B\), with at most one copy of each good type per bundle.
A one-type high-multiplicity fair-division model with population mass \(1\), utility type \(u\), integral bundle patterns \(B\subseteq V\), mass variables \(x_B\), and supplies \(\sigma_v=\frac12\); the objective is threshold-feasibility with \(u(B)\ge k\) for every used pattern.
The mirror needs an explicit at-most-one-copy-per-good-type convention and a formal denominator-clearing realization theorem connecting rational mass allocations to finite replicated instances.
fatal: False
The mirror covers Proposition 3.1's complete-graph threshold hardness and Theorem 3.11's fixed-type cycle allocation algorithm; it leaves the remaining upper bounds, approximation guarantees, tight examples, and open general cycle-hardness question unmirrored.
A credible mirror exists, and it is strongest if the population is made continuous while each individual agent still receives an integral connected bundle.
Normalize population mass to \(1\). A type is a complete utility vector \(u_r:V\to\mathbb{Q}_{\ge 0}\), and \(\mu_r\) is the mass of agents of type \(r\). Goods retain their graph structure. If \(B\subseteq V\) is a connected bundle, let \(x_{r,B}\) be the mass of type-\(r\) agents receiving the integral bundle \(B\). Goods must also scale with the population: \(\sigma_v\) is the supply of copies of good \(v\) per unit population. Thus
\( \sum_B x_{r,B}=\mu_r \)
and
\( \sum_{r}\sum_{B\ni v}x_{r,B}=\sigma_v. \)
For the high-multiplicity image of a discrete instance with \(n\) agents, \(s_r\) agents of type \(r\), and one copy of each good, take \(\mu_r=s_r/n\) and \(\sigma_v=1/n\). This is the limit of \(Hn\) agents and \(H\) copies of each good as \(H\) grows. The fractional object is the distribution of agents across bundle patterns; no individual receives a fractional bundle.
My lead anchor is Proposition 3.1, proved in this paper. It states that \({\sc Mms\text{-}Values\text{-}G}\) is NP-complete: given a graph \(G\) on \(m\) goods, one non-negative rational utility function \(u\), an integer \(n>1\), and a rational \(k\), decide whether \(\mms^{(n)}(G,u)\ge k\). The paper proves NP-hardness even when \(G\) is complete, \(n=2\), and \(u\) is integer-valued, by reducing from the cited NP-complete problem \({\sc Partition}\).
The corresponding continuous problem is:
Continuous MMS-Value\(_\infty\). Given a complete compatibility graph on goods \(V\), an additive utility \(u\), and a rational threshold \(k\), with population mass \(1\) and supply \(\sigma_v=\frac12\) of every good, decide whether there is a distribution \(x_B\) over integral bundles \(B\subseteq V\) such that \( \sum_Bx_B=1\), \( \sum_{B\ni v}x_B=\frac12\) for every \(v\), and \(x_B>0\) only when \(u(B)\ge k\).
This is a genuine continuous-population question. It describes \(2H\) indistinguishable agents and \(H\) copies of each good in the high-multiplicity interpretation, with one utility type and \(2H\gg 1\) agents.
The paper’s Partition reduction survives exactly. Let \(S=\sum_v u(v)\) and \(k=\lceil S/2\rceil\). Under any feasible continuous allocation, the average utility of an assigned bundle is
\( \sum_Bx_Bu(B)=\sum_v \frac12u(v)=S/2. \)
If \(S\) is odd, this average is below \(k\), so the answer is no. If \(S\) is even, every bundle in the support must have utility exactly \(S/2\). Hence a feasible distribution exists only if some subset \(B\) has value \(S/2\), and then its complement also has value \(S/2\). Conversely, a partition \(B,V\setminus B\) gives a feasible continuous allocation by assigning mass \(\frac12\) to each bundle.
Thus the expected direction is hardness transfer: the continuous problem is NP-hard, and in fact has polynomial-size basic-support witnesses. The combinatorics survive in the indivisible bundle patterns and the utility values, not in the identities of individual agents. This is a Class B mirror. It is not made trivial by replacing the population with mass.
A second, cycle-specific anchor is Theorem 3.11, proved in the paper. It states that for every fixed \(t\), there is a polynomial-time algorithm deciding whether an mms-allocation exists for \(m\) goods on a cycle and \(n\) agents of \(t\) utility types, and computing one if it exists. The input is compressed as \(t\) utility sequences and the counts \(s_1,\ldots,s_t\). The theorem is proved using polynomial-time computation of each type’s maximin share and a dynamic programme over the type-count vector.
The continuous version is the following.
Continuous MMS-Allocation\(_\infty\) on a Cycle. Given a cycle \(C\), utility types \(u_1,\ldots,u_t\), rational masses \(\mu_1,\ldots,\mu_t\) summing to \(1\), and rational per-capita supplies \(\sigma_v\), compute the continuous maximin benchmark \(M_r\) for each type \(r\), where \(M_r\) is the largest \(q\) for which a unit mass of type-\(r\) agents can be distributed over connected cyclic intervals so that every used interval has utility at least \(q\) and the supplies \(\sigma_v\) are exactly exhausted. Then decide whether there are variables \(x_{r,I}\), one for each type and cyclic interval \(I\), satisfying
\( \sum_Ix_{r,I}=\mu_r \),
\( \sum_{r,I:v\in I}x_{r,I}=\sigma_v \),
and \(x_{r,I}>0\Rightarrow u_r(I)\ge M_r\).
A solution is the mass distribution \(x\); every infinitesimal agent still receives one integral connected interval. For the direct high-multiplicity image of the paper’s instance, take \(\sigma_v=1/n\) and \(\mu_r=s_r/n\).
I expect this problem to be in Class A. A cycle has only \(O(m^2)\) connected intervals. For each type, \(M_r\) can be found by testing the finitely many possible interval values using a marginal-feasibility LP. Once the \(M_r\) are known, the allocation question itself is one rational LP with variables \(x_{r,I}\). The continuous problem is therefore polynomial-time solvable, even though the finite problem requires the paper’s more intricate dynamic programme.
This is a plausible mirror because the paper itself already identifies identical utility functions as agent types and represents a large electorate by type counts. Replacing \(s_r\) by the mass ratio \(\mu_r\) is not changing the social-choice question; it removes irrelevant agent names and passes to the high-multiplicity regime. Existing type-count work is supporting evidence for the mirror, not a novelty collision.
The scope is deliberately limited. The first mirror covers the paper’s general graph value problem in the complete-graph hardness subcase. The second covers the cycle allocation problem in the fixed-type regime. I am not claiming that the paper’s unresolved NP-hardness question for arbitrary cycle mms-allocation has been settled, nor that every approximation theorem automatically has the same continuous interpretation.
The weakest point is the goods-side co-modification. A literal finite cycle has one copy of each good, whereas the continuum model needs per-capita supplies of goods. A sceptical referee could demand a formal realization theorem showing that every rational mass allocation \(x\) is the limit of allocations of \(H\)-copy instances, especially for cycles. That bridge is not proved here. The case nevertheless remains substantial: the individual bundles remain integral and connected, the population is the continuous object, Proposition 3.1 retains hardness under the limit, and Theorem 3.11 gives direct evidence that the cycle problem has a meaningful high-multiplicity regime.
The strongest negative case is that both proposed mirrors initially blur population continuization with resource and allocation fractionalization.
For Proposition 3.1, keeping the \(m\) goods fixed while making the population atomless makes the MMS value collapse: almost all agents must receive the empty bundle. To avoid that, the proposed model replicates every good and imposes per-capita supplies. But then one must specify whether an agent may receive multiple copies of the same good, how copies inherit the cycle graph, and whether bundles are subsets or multisets. These choices are absent from the paper and produce different problems. The displayed \(x_B\)-model is therefore not automatically the high-multiplicity limit of the paper’s instance; it is a fractional packing model over bundle patterns.
That objection is not ultimately sufficient. The programme expressly permits per-capita resource scaling when population continuization forces it. With a natural “at most one copy of each good type per bundle” convention, a rational \(x_B\) can be denominator-cleared into an allocation with \(H\) copies of each good and \(2H\) identical agents. The Partition argument then genuinely survives. The single-type population is not disqualifying: a point mass is a valid type distribution, and this is precisely a Class B hardness transfer. I cannot honestly defeat this anchor.
Theorem 3.11 has a real technical defect as stated. The paper’s benchmark is \(\mms^{(n)}(C,u_r)\), where \(n\) is the total number of agents, not the mass \(\mu_r\) of type \(r\). Thus \(M_r\) must be computed using the total per-capita supply, in a homogeneous population of type \(r\), rather than from the type-\(r\) population itself. But after that correction, the proposed LP is a credible high-multiplicity image: cyclic intervals are the integral bundle patterns, and the mass and supply equations are exactly the aggregate form of an allocation with many copies of each good. There are only \(O(tm^2)\) interval variables, and the benchmark is found by the same feasibility LP over threshold values. This is a plausible Class A result, not a mere restatement.
So the honest negative case is weak. One can demand a formal realization theorem and an explicit convention for replicated goods and cycle adjacency, but those are repairs to a worthwhile mirror, not reasons that no mirror exists. Under the programme’s rules, Proposition 3.1 survives decisively, and the repaired Theorem 3.11 mirror probably survives as well. A universal “no worthwhile continuous mirror” verdict would rely on objections the programme explicitly rules out.
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.