| paper | d4-conf-aaai-2021-1740 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-hard for fixed \(\rho=1\) and \(\epsilon=\tfrac12\), even with \(\tau=1\) and \(P=4\); no such PTAS unless \(\mathrm{P}=\mathrm{NP}\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 3.3
statement extracted from the paper’s text layer
Given \(P\in\mathbb{N}\), \(d\) item types, rational per-capita supplies \(q\in\mathbb{Q}_{\ge 0}^d\), rational signed values \(v\in\mathbb{Q}^d\), and fixed \(\rho,\epsilon>0\), consider distributions over integral bundles \(b\in\mathbb{Z}_{\ge 0}^d\) with masses \(\lambda_b>0\), \(\sum_b\lambda_b=1\), and \(\sum_b\lambda_b b=q\). Let \(\mathrm{CMMS}(q,v)\) be the supremum, over such distributions, of \(\min_{\lambda_b>0} v\cdot b\). Under the promise \(\mathrm{CMMS}\ge 0\), compute a distribution whose every positive-mass bundle has value at least \((1-\epsilon)\mathrm{CMMS}\) when \(\mathrm{CMMS}\ge P\min\{V^+,V^-\}/\rho\), where \(V^+=\sum_{v_j>0}q_jv_j\) and \(V^-=\sum_{v_j<0}q_j|v_j|\); otherwise report that the threshold fails.
A homogeneous population of mass \(1\) receives integral bundles of \(d\) indivisible item types, with mean supply \(q\) per recipient. The decision is a distribution over bundle patterns, and the objective is to maximize the least value among patterns with positive mass, retaining the paper's B-MMS threshold scaled to total inventory by \(P\).
With bounded total chore stock, the chore-bearing recipients have mass tending to zero as \(P\) grows, so the support-based minimum can be discontinuous at the limiting society; the proponent identifies this regime but does not address that limit instability.
fatal: False
The mirror covers only the nonnegative-MMS branch of Theorem 3.3; it leaves the negative-MMS branch, the broader informal Theorem 1.1, and settings with nonidentical agents untouched.
My strongest case is a narrow mirror of Theorem 3.3, proved in this paper. It says that for identical agents with nonnegative MMS, the B-MMS problem can be solved in \(O(mnL)\) time. For fixed \(\rho\) and \(\epsilon\), that means returning a \((1-\epsilon)\)-MMS allocation when \(\mathrm{MMS}\ge \min\{v^+,v^-\}/\rho\), and reporting that the threshold fails otherwise, using the paper’s trivial-allocation convention. Here \(m\) is the number of items, \(n\) the number of agents, and \(L\) the bit length of the valuations. The paper proves this positive-MMS result; its broader informal Theorem 1.1 also discusses negative MMS. The hardness result mentioned in the introduction is attributed to earlier work and is not a numbered hardness theorem in this paper, so I would not use it as an anchor.
Consider a large cohort in which every person has the same additive valuation over standardized item types: some types are goods and some are chores. A plausible setting is a repeated allocation program with a homogeneous user cohort, abundant valued items, and a relatively small stock of unpopular duties. Let \(P\) be the population scale, let \(q_j\) be the per-person supply of item type \(j\), and let \(v_j\) be its signed value. The represented cohort has \(Pq_j\) copies of type \(j\). The agent-type distribution has support size one, even when \(P\) is large.
I would pose the mirror as Continuous B-MMS+. Its input is \(P\), rational per-person supplies \(q\), rational values \(v\), and fixed \(\rho,\epsilon\), with \(\mathrm{CMMS}\ge 0\). A bundle is still integral: \(b\in\mathbb Z_{\ge0}^d\) records the number of copies of each of the \(d\) item types that a person receives. An allocation is a finite list of bundle patterns \(b^k\) and population masses \(\lambda_k>0\), satisfying \(\sum_k\lambda_k=1\) and \(\sum_k\lambda_k b^k=q\). Its guarantee is \(\min_k v\cdot b^k\), and \(\mathrm{CMMS}(q,v)\) is the supremum of this guarantee over feasible allocations. Thus \(\lambda_k\) is the fraction of the cohort receiving an integral bundle; it does not split items within a person’s bundle.
Set \(V^+=\sum_{v_j>0}q_jv_j\) and \(V^-=\sum_{v_j<0}q_j|v_j|\). The question is: either return such an allocation with every positive-mass bundle worth at least \((1-\epsilon)\mathrm{CMMS}\) when \(\mathrm{CMMS}\ge P\min\{V^+,V^-\}/\rho\), or report that this threshold fails. The factor \(P\) preserves the paper’s threshold on the *total* inventory: the replicated discrete instance has aggregate positive and negative values \(PV^+\) and \(PV^-\). In the finite counterpart, assigning \(r\) of the \(P\) people a bundle corresponds to mass \(r/P\); the continuous version permits arbitrary masses instead of only multiples of \(1/P\).
This is recognizable as the authors’ maximin-share question: the people still have identical additive valuations, every recipient gets an indivisible bundle, and the objective still maximizes the least-valued bundle. The continuation is in the population assignment: a mass of recipients can receive each integral bundle pattern. It is not continuity of the bundles themselves. I expect this bounded version to be tractable, probably through a configuration LP over integral bundle patterns. A witness at a fixed target value is a convex combination of patterns \(b\) satisfying \(v\cdot b\) at least that target. The key open issue is whether the pricing problem for those patterns is efficient when the number of item types varies.
This case covers only the nonnegative-MMS B-MMS result, not the paper’s negative-MMS branch or guarantees for nonidentical agents. The weakest point is the regime: the theorem compares MMS with the total value of the manna, so ordinary replication in which goods and chores both scale proportionally with \(P\) will generally make its threshold fail. A plausible large-cohort regime needs one side of the inventory to stay small in aggregate—for example, a bounded stock of chores alongside enough goods to keep every bundle’s value above the threshold. That is a real, but narrower, high-multiplicity question. The paper’s \(O(mnL)\) bound also does not itself give a runtime polynomial in the bit length of \(P\); the continuous problem would need its own complexity analysis.
The strongest negative case is about the condition in the paper’s Theorem 3.3. It makes a faithful continuous mirror collapse in the usual fixed-density population limit.
Suppose each member of a cohort has fixed per-capita positive value \(g>0\) and chore cost \(c>0\). With \(n\) recipients, the paper’s totals are \(v^+=ng\) and \(v^-=nc\). For nonnegative MMS, the average bundle value gives \(\mathrm{MMS}_n\le g-c\), while Theorem 3.3’s promise requires \(\mathrm{MMS}_n\ge n\min\{g,c\}/\rho\). For fixed \(g,c,\rho\), those conditions cannot both hold once \(n\) is large. Thus the theorem’s promise does not cover a mixed society with stable per-capita supplies.
The proponent’s bounded-stock-of-chores regime avoids that contradiction, but it exposes a limit problem: if total chore value stays bounded while the population grows, chore supply per person tends to zero. The positive-mass distribution over recipients then loses the chore-bearing cohort in the limit. At each finite \(n\), that tiny cohort may still determine the minimum bundle value; in the limiting population, its zero mass is invisible. The theorem-faithful mirror therefore either excludes fixed-density mixed populations or loses the mixed part that made the theorem distinctive. The paper’s running time, \(O(mnL)\), also supplies no algorithm polynomial in a binary-encoded population scale.
That does not defeat the stronger normalized proposal. One could define a per-capita MMS problem with integral bundles and arbitrary masses, and compare its value with per-capita goods and chore totals. This is a well-posed high-multiplicity question, and the continuum would still be in the population assignment. But its promise changes the factor of \(n\) in Theorem 3.3; the paper’s result does not establish it. That makes it a new, potentially worthwhile problem rather than a faithful mirror of the anchored theorem.
So the negative case is strongest against the theorem-faithful mirror, and weak against the broader claim. I cannot honestly rule out the normalized formulation: it retains the paper’s maximin-share objective and integral bundles while making recipient mass continuous. The central objection is a real degeneration in the regime covered by the named result, not a universal reason that no continuous mirror is worth studying.
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.