| paper | d4-conf-aaai-2026-0773 |
| 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, even for \(\tau=1\), strictly positive integer valuations, and \(q_b=1/2\) for every good type. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 12
Given finitely many complete agent types \(a\in[d]\), good types \(b\in[t]\), rational masses \(\mu_a>0\) summing to \(1\), rational additive values \(v_{ab}\ge 0\), and rational per-capita supplies \(q_b\ge 0\), decide whether and construct a finite-support assignment \(\lambda_{a,z}\ge 0\) of type mass to integral bundles \(z\in\mathbb{Z}_{\ge 0}^t\). Require \(\sum_z\lambda_{a,z}=\mu_a\) for every \(a\), \(\sum_{a,z}\lambda_{a,z}z_b=q_b\) for every \(b\), and \(v_a\cdot z\ge v_a\cdot z'\) whenever \(\lambda_{a,z}>0\) and \(\lambda_{a',z'}>0\). Each unit of mass receives an integral bundle; the computational task is to decide whether such an envy-free assignment exists and output one if it does.
A continuum population over finitely many complete valuation types, with rational type masses and per-capita supplies; choose a mass distribution over integral bundles that meets supplies and satisfies envy-freeness.
Although the proponent flags the gcd change, the sharper concern remains: arbitrary \(q_b\) can remove the theorem’s divisibility regime, so the mirror’s complexity may concern a broader feasibility problem than the paper’s \(\nu\)-threshold.
fatal: False
The mirror covers the deterministic envy-free allocation result for valuation types and good types; it leaves the PRD mechanism, truthfulness guarantees, and weighted and group extensions aside.
My strongest positive case is the paper’s deterministic multiple agent types and good types result, not its random-item PRD mechanism. Imagine a large university system allocating seats across a fixed set of course categories to applicants in a few program or eligibility classes. Within each class, applicants have the same additive values for every category. If the population has size \(N\), the number of distinct classes \(\tau\) can stay fixed or moderate while \(N\gg\tau\); course supplies scale with \(N\). That is a credible high-multiplicity regime.
The lead anchor is Theorem 12, proved in this paper. It states that, in the types setting, there is a threshold \(\nu=O(n^2/r)\) such that whenever each of the \(t\) good types has at least \(\nu\) items and each type’s item count is divisible by \(r=\gcd(n_1,\ldots,n_d)\), a complete envy-free allocation exists; when agents are pairwise distinct, the bound improves to \(\nu=O(n)\). The paper’s construction gives the allocation in polynomial time. The preceding Theorem 11 is cited prior work on existence for this finite-type setting, so it supports the premise that repeated valuation types are a sensible regime; it is not a collision with the continuous question. ([Theorems 11–12](https://ojs.aaai.org/index.php/AAAI/article/download/38737/42699))
Here is the continuous problem I would hand to a prover: Continuous Type-EF *(lead)*. An instance has agent types \(a\in[d]\), good types \(b\in[t]\), rational masses \(\mu_a>0\) with \(\sum_a\mu_a=1\), rational additive values \(v_{ab}\ge0\), and rational per-capita supplies \(q_b\ge0\). A type is complete here: its members share the same values for every good type. A solution is a finite list of nonnegative masses \(\lambda_{a,z}\), where \(z\in\mathbb Z_{\ge0}^t\) is an integral bundle. It must satisfy
\[
\sum_z\lambda_{a,z}=\mu_a\quad\forall a,
\qquad
\sum_{a,z}\lambda_{a,z}z_b=q_b\quad\forall b.
\]
The allocation is envy-free if, whenever \(\lambda_{a,z}>0\) and \(\lambda_{a',z'}>0\), then \(v_a\cdot z\ge v_a\cdot z'\). The computational task is to decide whether such a solution exists and, if so, output it. Thus each unit of agent mass receives an integral bundle; fractional quantities occur only in how a type’s mass is distributed across bundles and in the per-capita aggregate supplies.
This is close to the authors’ own problem: Section 6.3 already pools agents with identical valuations into super-agents and reasons about good-type inventories. The continuous mirror replaces counts \(n_a\) by proportions \(\mu_a\), and total inventories by per-capita supplies \(q_b\). I expect the unrestricted exact problem to be Class C: selecting an envy-compatible menu of integral bundles still looks combinatorial. Theorem 12 suggests a tractable high-supply region, but it does not establish that this full continuous problem is in P. Nor would I claim hardness transfers: the paper’s introductory partition-hardness observation is not a numbered anchor, and allowing type mass to split among bundles may dissolve that reduction.
The mirror covers only the paper’s deterministic types result and its constructive allocation. It does not claim to continuize the PRD mechanism or its truthfulness guarantee. Its weakest point is the co-modification: Theorem 12 is about finite populations and has a threshold and divisibility condition involving \(r\), while this mirror uses per-capita supplies and permits type mass to split across integral bundles. That is a real change in the allocation model. The case survives because the population itself is what becomes continuous, the underlying envy condition remains intact, and the paper already treats repeated valuation types as super-agents.
Two natural follow-ups are whether the finite theorem’s gcd and divisibility effects persist or disappear in the mass model, and whether a direct algorithm can run in time polynomial in \(d,t\) and the binary input length without expanding rational masses into a potentially enormous finite population.
The strongest case against is that Theorem 12’s headline is an existence threshold, not a complexity classification. Its construction is polynomial time, but the theorem does not formulate a decision or optimization problem with an input encoding and complexity bound. The proposed Continuous Type-EF therefore adds a broader question: feasibility for arbitrary rational supplies and arbitrary mixtures of integral bundles. That question may be worthwhile, but it is not simply the theorem’s computational result with counts replaced by masses.
The closer mirror also exposes a modeling tension. Theorem 12 relies on finite multiplicities and the arithmetic of \(r=\gcd(n_1,\ldots,n_d)\), including divisibility of each good-type inventory. Arbitrary per-capita supplies can erase that structure. To preserve it, one could restrict supplies to the corresponding rational lattice and track how it changes under population replication. But then the mirror is count-sensitive, and its new content must come from compressed input or from allowing type mass to split across equal-utility integral bundles—not from replacing the population alone.
That objection does not hold up against the best version of the mirror. Rational masses and per-capita supplies can encode replicated finite instances, while each unit of mass still receives an integral bundle. The model retains envy comparisons and makes the population continuous in precisely the relevant sense. The paper’s super-agent construction and repeated valuation types make this a credible high-multiplicity regime. The cited Theorem 11 is evidence for that regime, not a continuous prior-art collision.
So the negative case is weak. The theorem’s arithmetic may make a faithful mirror more delicate than the proponent’s first formulation suggests, and the paper does not provide a formal complexity classification to carry over. But neither point shows that the stronger continuous question lacks value. I cannot honestly rule out a worthwhile mirror for this anchor.
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.