| paper | d4-conf-aaai-2016-0686 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
The proposed continuous feasibility question is a recognizable extension of exact MMS allocation, but its anchor, Theorem 2.1, is not computational. Moreover, mixing each type’s own MMS distribution across its mass satisfies the shared per-capita supplies, so the proposed feasibility problem is always yes; that answer alone would not disqualify a mirror, but it does not supply the missing computational anchor.
fails bit a — no named computational result to mirror
For each type, assign its MMS distribution π_t to mass μ_t; the weighted expected use of each good is at most ∑_t μ_t s_g = s_g, so the proposed feasibility problem is always satisfied.
fatal: False
The question targets Theorem 2.1’s exact-MMS feasibility issue; it does not mirror Theorem 3.1’s random-valuation guarantee or the paper’s approximate-MMS results.
The best high-multiplicity mirror I can defend is an exact-MMS allocation problem for a large recurring cohort: many claimants receive bundles from a stock that scales with the cohort, and each claimant belongs to one of a small number \(\tau\) of complete additive-valuation types. For example, a large public program might distribute standardized kits to millions of people whose valuations fall into a few stable profiles. Each person still receives an integral bundle of indivisible goods; the continuum lets us assign different bundles to different fractions of a type.
I should be clear about the anchor: this paper has no named computational-complexity result classifying a problem as polynomial-time solvable, NP-hard, or similar. Its numbered results concern existence. The closest anchor for this mirror is Theorem 2.1, proved here: for every \(n\ge3\), there is an instance with \(n\) players and at most \(3n+4\) goods that has no allocation giving every player their maximin share. That is a meaningful result about the underlying allocation problem, but it is not a complexity result under the requested anchor criterion.
A precise continuous question suggested by it is Continuous MMS Feasibility. An instance has \(q\) standardized good categories, a finite set \(T\) of additive valuation types \(v_t\in\mathbb Q_{\ge0}^q\), type masses \(\mu_t\ge0\) summing to \(1\), and per-capita supplies \(s_g\ge0\). A person receives an integral bundle \(b\in\mathbb Z_{\ge0}^q\). Define \(M_t(s)\) as the largest guarantee type \(t\) could secure by partitioning the per-capita stock into bundles: equivalently, maximize \(z\) over finite-support distributions \(\pi\) on integral bundles such that \(\mathbb E_\pi[b_g]\le s_g\) and every bundle in the support has \(v_t\cdot b\ge z\). The question is whether there are masses \(x_{t,b}\ge0\) such that
\[
\sum_b x_{t,b}=\mu_t,\qquad
\sum_{t,b}x_{t,b}b_g\le s_g,\qquad
x_{t,b}>0\implies v_t\cdot b\ge M_t(s).
\]
A solution assigns every unit of population a whole bundle worth at least its type’s MMS, while allowing a type’s mass to be split among bundles. This keeps the guarantee individual-level; it does not replace it with an average-utility threshold.
This seems like a credible mirror of the paper’s underlying question: does everyone get their exact MMS guarantee? It changes the population regime, and scales supplies with that population, while preserving additive valuations, indivisible bundles, and the MMS benchmark. It also asks directly whether the nonexistence phenomenon in Theorem 2.1 survives when repeated types can be allocated at mass granularity. My tentative expectation is continuum-specific hardness when \(q\) is part of the input: bundle choice introduces integer covering and pricing structure, which may remain hard even after population multiplicity is removed. That is a conjecture about this new problem, not a consequence of Theorem 2.1. Further questions include whether the continuum problem is always feasible, and whether its answer matches the limit of finite instances obtained by cloning each type and scaling each good supply.
The weak point is that Theorem 2.1 neither proves hardness nor guarantees failure in a bounded-type regime. The paper’s Theorem 3.1 is also not a complexity anchor: it says that if each player’s independently sampled value distribution has variance at least a constant \(c>0\), then for every \(\varepsilon>0\) some \(K(c,\varepsilon)\) ensures an MMS allocation exists with probability at least \(1-\varepsilon\) whenever \(\max(n,m)\ge K\). The paper describes an algorithm in connection with this result, but the theorem is a probability-of-existence statement. Its independent random valuations may also yield too many distinct realized types for a high-multiplicity interpretation. So the positive case is a plausible new computational question prompted by the paper, not a computational result already established by it.
The cleanest objection is that the paper’s anchor is not a computational result. Theorem 2.1 proves that some finite instances lack an exact MMS allocation; it gives no complexity classification or algorithmic question. Theorem 3.1 is a high-probability existence result. Turning either into a computational problem may be worthwhile, but that would add a question the paper does not answer.
More damagingly, the proposed Continuous MMS Feasibility problem collapses under its own definition. For each type \(t\), take a bundle distribution \(\pi_t\) witnessing \(M_t(s)\), and set \(x_{t,b}=\mu_t\pi_t(b)\). Then
\[
\sum_b x_{t,b}=\mu_t,\qquad
\sum_{t,b}x_{t,b}b_g
=\sum_t\mu_t\,\mathbb E_{\pi_t}[b_g]
\le \sum_t\mu_t s_g=s_g.
\]
Every bundle assigned positive mass meets its type’s MMS threshold. So the proposed feasibility question is always satisfied: each type can spread its own MMS partition across its mass, and the mixture of those partitions fits the shared per-capita supply. The individual bundles remain integral; it is the population that makes the mixing possible.
That also defeats the stronger version of the anchor: asking whether a continuous population can exhibit the paper’s MMS nonexistence phenomenon. With type masses free to split, the same construction supplies a feasible allocation for every type distribution under this benchmark. Recovering the finite coordination conflict would require an extra restriction—such as forcing everyone of a type to receive the same bundle or reinstating integer headcounts. Neither follows from high multiplicity; the first rules out splitting a type’s mass among bundles, and the second restores finite population granularity.
The random-valuation theorem offers no clear computational anchor either. Its formal conclusion concerns probability of existence, not a stated complexity bound. In its natural continuous-valued setting, independently sampled valuation vectors are generally all distinct, so the paper’s random regime does not naturally give a small finite support of complete types. With a finite type space, the mass-mixing argument again makes exact feasibility automatic under the proposed benchmark.
This is a strong case against the proposed mirror, but not an honest proof that no useful continuous question can arise from the paper. A large cohort with a few valuation types is a sensible regime. One could study the complexity of computing each type’s MMS threshold or the finite-population rounding needed to recover indivisible-agent guarantees. Those may be worthwhile new computational problems; they are not continuizations of a computational result established here.
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.