| paper | d4-conf-ijcai-2007-0238 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\Sigma_2^{\mathrm P}\)-complete under polynomial-time many-one reductions; hence \(\mathrm{NP}\)-hard, even when all masses equal \(1\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 6.3
statement extracted from the paper’s text layer
Given a finite type set \(T\), positive rational masses \(\mu_t\), and NTU rules whose literals test whether coalition mass \(z_t\) is positive or zero and whose triggered rules add chosen payoff-increment vectors, decide whether \(V(\mu)\) contains an \(x\) such that for every nonzero \(z\leq\mu\) and every \(y\in V(z)\), some \(t\) with \(z_t>0\) satisfies \(y_t\leq x_t\).
The society is a rational distribution \(\mu\) over complete role and payoff types. A coalition is a mass vector \(z\leq\mu\); its rule outcomes depend on the support of \(z\) and assign a shared per-person payoff to each participating type. The decision asks whether a grand-coalition payoff \(x\in V(\mu)\) exists that no coalition mass and feasible outcome \(y\in V(z)\) can strictly improve for every participating type.
The paper permits individual-specific NTU payoff vectors, and its consequence sets need not be convex, so the mirror's single shared payoff per type is not justified merely by symmetry.
fatal: False
The mirror covers the NTU marginal-contribution-net core result in Theorem 6.3; it leaves the transferable-payoff results and other representation classes aside.
The strongest mirror I believe in is NTU-MCN\(_\infty\) Core Nonemptiness. Picture a large cooperative or production network with many participants but relatively few complete role profiles. A type records everything that matters to the game: role, contract, outside option, and payoff rules. The society is a distribution \(\mu\in\mathbb{Q}_{>0}^{\tau}\) over \(\tau\) such types, with \(\sum_t\mu_t=1\). A coalition is a mass vector \(z\in[0,\mu]\); participants of type \(t\) who join receive the same per-person payoff. This suits settings where a role cohort can split across projects, while members of a cohort remain interchangeable.
Here is the problem precisely. The input is \(\mu\) and a finite set of rules. Each rule has positive and negative type literals and a finite set of rational payoff-increment vectors. It is triggered when every positive type has \(z_t>0\) and every negative type has \(z_t=0\). For each triggered rule, choose one of its increment vectors and add the chosen vectors; the resulting set is \(V(z)\), the feasible per-person payoff profiles for coalition \(z\). The grand coalition can choose \(x\in V(\mu)\). Decide whether there is such an \(x\) for which, for every nonzero \(z\leq\mu\) and every \(y\in V(z)\), some participating type \(t\) has \(y_t\leq x_t\). That is exactly the core question: no coalition mass can give every one of its members a strict improvement. A “yes” solution is a grand-coalition payoff vector \(x\) satisfying this condition.
My anchor is Theorem 6.3, proved in this paper. It states that NTU core nonemptiness is in \(\Sigma_2^P\) for every nondeterministic polynomial-time compact representation; it is \(\Sigma_2^P\)-complete for marginal contribution nets; and it is in co-NP when the representation is deterministic polynomial-time. The paper proves the membership results and proves the hardness by reducing validity of \(\exists\alpha\,\forall\beta\,\phi(\alpha,\beta)\), with \(\phi\) in 3DNF. The \(\Sigma_2^P\)-complete marginal-net result is the anchor for this mirror.
For these support-triggered type rules, I expect the hardness to transfer. Every nonzero mass vector \(z\) has a support \(S=\{t:z_t>0\}\). The rules and per-person payoff options depend on \(S\), just as the paper’s rules depend on which named players belong to a coalition. Thus every continuous coalition has the same rule outcomes and strict-improvement test as the finite coalition of types \(S\). Conversely, every finite coalition of types is realized by choosing positive mass from exactly those types. The finite marginal-net core instance therefore embeds directly: give each source player its own type with positive mass. The continuous problem is \(\Sigma_2^P\)-complete in this rule language. The hardness is carried by the number and interaction of distinct types, not by the total population size.
That is a credible high-multiplicity regime: many people share each role profile, and the rules describe complementarities among profiles. The continuous object is the society and the coalitions’ mass vectors; payoff consequences remain per-person vectors, as the NTU model requires. This mirror covers the paper’s NTU marginal-contribution-net result, not its transferable-payoff results.
The weak point is that this particular extension’s rules react to whether a type has positive mass, not to its precise mass. Changing \(\mu_t\) or taking a smaller positive slice can change aggregate population amounts without changing the core test. So the result gives a clean, honest hardness transfer, but it does not show that fractional mass geometry itself causes hardness. A referee who requires coalition worths to vary with mass magnitude could reject this as too close to a type-level discrete game. That limitation does not erase the mirror: it identifies a natural high-multiplicity NTU core problem and shows exactly why the paper’s hardness survives in it.
The strongest objection is to the proposed Theorem 6.3 mirror’s mass semantics. In that model, a rule reacts only to whether a type has positive mass, and its per-person consequences do not depend on how much mass joins. So the core test quantifies over supports \(S=\{t:z_t>0\}\), not over mass vectors: every support is available for every society with those types, and every coalition with that support has the same consequences. Changing the proportions or duplicating the population leaves the answer unchanged. Even an arbitrarily small slice of a type can trigger the same payoff change as the whole cohort. That is a real continuum-degeneracy objection: mass is present in the notation but absent from the computation.
The better repair is to make consequences depend on coalition composition—for example, through mass thresholds, production constraints, or per-capita returns that vary with \(z\). That could yield a worthwhile continuous NTU core problem. But Theorem 6.3’s marginal contribution nets do not specify such a law. They define consequences for subsets of named players and add payoff increments to individual coordinates. Choosing how those rules scale when a type contains a continuum of participants adds a production or allocation model; different choices produce different computational questions. A faithful treatment may also need to allow members of one type to receive different payoffs: the paper’s NTU consequence sets need not be convex, so symmetry of the players alone does not justify replacing their payoff coordinates by one shared type-level payoff.
This does not erase the anchor. Theorem 6.3 is a named computational result, and role-based cooperative settings make a type-level extension plausible. I would reject the support-only mirror as evidence that population continuization itself is doing work, while treating a mass-sensitive version as a possible new project. That leaves the universal negative case weak: the paper does not provide the scaling semantics, but a convincing model could supply them.
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.