| paper | d4-conf-ijcai-2011-0335 |
| 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: \(\mathrm{NP}\text{-hard}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 5.5
statement extracted from the paper’s text layer
Given finite role types \(T\), positive rational masses \(\mu_t\) summing to \(1\), and a succinct nonnegative rational worth function \(w:2^T\to\mathbb{Q}_{\ge 0}\), let \(\Omega\) be a union of intervals \(\Omega_t\) of lengths \(\mu_t\). For a measurable coalition \(A\), set \(F(A)=\{t:\lambda(A\cap\Omega_t)=\mu_t\}\) and \(W(A)=w(F(A))\). Does there exist a finite measurable partition \(\Pi\) of \(\Omega\) and an integrable payoff density \(x\), individually rational at each type’s reservation rate \(w(\{t\})/\mu_t\), such that \(\int_C x=W(C)\) for every \(C\in\Pi\) and \(\int_A x\ge W(A)\) for every measurable \(A\)?
An atomless population partitioned into role types with masses \(\mu_t\); a coalition earns \(w(F(A))\), where only fully participating types count; the decision variables are a finite measurable coalition partition \(\Pi\) and an integrable payoff density \(x\), subject to individual rationality, block efficiency, and core stability.
The threshold rule makes partial members of a role contribute nothing, so the mirror does not cover settings where coalition worth changes with participation; this limits its generality despite the federation scenario.
fatal: False
The mirror covers the nonemptiness results in Theorems 4.1 and 5.5. It leaves CORE-CHECK, CS-COS, and CS-LCV without a separate continuous formulation.
The strongest case is a mass version of coalition worth that preserves the paper’s central question: can agents allocate worth so no coalition wants to break away? I would make Role-Mass Core Nonemptiness the lead mirror.
Let \(T\) be a finite set of complete role types, with rational masses \(\mu_t>0\) summing to \(1\). Let \(w:2^T\to\mathbb Q_{\ge0}\) be a succinct, polynomial-time computable worth function. Represent the atomless society as intervals \(\Omega_t\) of lengths \(\mu_t\). For a measurable coalition \(A\), define its *fully assembled types* by
\[
F(A)=\{t\in T:\lambda(A\cap\Omega_t)=\mu_t\},
\]
and set its worth to \(W(A)=w(F(A))\). In this model, a coalition can take any fraction of any type’s mass, but a type’s role-level worth is activated only when its whole mass joins. Give each member of type \(t\) a reservation payoff per unit mass \(b_t=w(\{t\})/\mu_t\). The question is whether there is an integrable payoff density \(x\) such that \(x\ge b_t\) almost everywhere on \(\Omega_t\), \(\int_\Omega x=w(T)\), and \(\int_A x\ge W(A)\) for every measurable coalition \(A\). This is a feasibility problem: find a stable, efficient allocation.
My lead anchor is Theorem 4.1, proved in this paper. It states that CORE-NONEMPTINESS and CORE-CHECK are co-NP-complete, with hardness even on superadditive games. The paper attributes membership to Malizia et al. (2007) and proves the hardness here. Its reduction uses players \(N=\{X,\neg X:X\in\operatorname{vars}(\Phi)\}\), and gives a coalition worth \(2|S|/|N|\) when \(|S|>|N|/2\), \(1+1/|N|\) when \(S\) is consistent and its assignment satisfies \(\Phi\), and \(0\) otherwise. The equal payoff vector with each player receiving \(2/|N|\) is in the core exactly when \(\Phi\) is unsatisfiable; the game constructed is superadditive.
This result maps directly to Role-Mass Core Nonemptiness. Take one type for each literal role and let \(w(S)=v_\Phi(S)\). A core payoff \(y_t\) for each finite role player gives the continuous density \(x=y_t/\mu_t\) on that type. Conversely, integrate any continuous allocation over each type interval to recover finite payoffs. At a deviation containing whole types \(S\), the constraint is exactly the finite core constraint for \(S\); fractions of additional types cannot hurt because payoffs are nonnegative. Thus the continuous instance has a core exactly when the original game does. In this reduction, the worth extension is also superadditive: the constructed finite worth is monotone as well as superadditive, and combining disjoint coalitions can only add fully assembled types. I expect hardness to transfer here, rather than disappear in the continuum.
A second, independently useful anchor is Theorem 5.5, also proved in this paper. It states that CS-CORE-NONEMPTINESS, CS-COS, and CS-LCV are \(\Delta_2^P\)-complete. I rely on the CS-CORE-NONEMPTINESS result: decide whether there is a coalition structure and payoff vector in the coalition structure core. The paper establishes its hardness in Theorem 5.3 and its upper bound through its cohesive-cover characterization and the social-welfare computation in Lemma 5.4.
The corresponding mirror is Role-Mass Coalition-Structure Core Nonemptiness. Use the same \((T,\mu,w,W)\). A solution is a finite measurable partition \(\Pi\) of the society and an integrable payoff density \(x\), with individual rationality, \(\int_C x=W(C)\) for every \(C\in\Pi\), and \(\int_A x\ge W(A)\) for every measurable deviation \(A\). The objective is existence of such a stable partition and allocation. A finite coalition structure maps to a partition into unions of whole type intervals. In the other direction, a positive-worth block must contain whole type intervals; stability against those full-type deviations, together with nonnegative individual payoffs, lets one recover an efficient finite partition of the types. Types left only in partial, zero-worth pieces must have zero worth as singletons, or they would block. So this mirror preserves the coalition-structure question, and I expect \(\Delta_2^P\)-hardness to transfer as well.
The regime is a large federation or cooperative economy with many interchangeable members in each occupational or mandate role. Members of a role share its preferences, costs, and reservation rate; worth is generated by which complete roles participate. In the reductions, \(T\) is the set of literal roles for Theorem 4.1, or the constructed roles for Theorem 5.5. If there are \(K\) interchangeable members per role, then the finite approximation has \(N=K\tau\) agents and \(\tau=|T|\) types; \(K\) can be large even though the number of roles grows with the reduction. The mass coordinates describe the population itself. The model does not continuize outcomes, time, or uncertainty.
My weakest point is the threshold worth technology: a partial role contributes no role-level worth, while completing the role triggers it. That makes the continuous model less natural for economies where value changes smoothly with participation, and the reductions’ combinatorics still live in the number of roles \(\tau\). But this is a real high-multiplicity regime—many identical members per role—and a recognizable core problem over fractional coalition masses. The paper studies compact worth functions broadly, and its Theorem 4.1 even supplies a superadditive hardness case. I think the authors could recognize this as a legitimate special-case mirror, while a referee would reasonably ask whether the result persists for smoothly aggregative worth functions.
I would limit the claim to these two nonemptiness results. Natural follow-ups are whether smooth mass-dependent worth functions make core existence easier, whether bounded \(\tau\) changes either complexity, and how cost of stability and least-core value should be defined when coalitions and their subsidies are mass-valued.
The proposed construction is algebraically sound, and that exposes its weakness. The paper gives a worth \(v(S)\) for subsets of finitely many players. A society with divisible type masses needs worths for partial participation too: a function of mass vectors \(q\in\prod_t[0,\mu_t]\). The proposed \(W(A)=w(F(A))\) supplies those missing values by making worth depend only on whether a type’s *entire* mass joins.
That choice makes every proper fraction of a type strategically inert. Given a continuous payoff density \(x\), the relevant quantity is just \(y_t=\int_{\Omega_t}x\): the core constraints reduce to the finite constraints \(y(S)\ge v(S)\). Conversely, a finite core payoff lifts to a constant density on each type. So Theorem 4.1’s result transfers exactly because each type interval acts as one finite player. The SAT reduction’s literal roles are formula-specific; copying each role many times does not create a population of members who can participate independently. They must join en bloc. This is a structural objection to the population model, not an objection that hardness survives or that prices belong to types.
A stronger population model could let coalitions include arbitrary fractions of each type. But then the paper’s \(v\) does not specify worth at those fractions. A linear or smooth mass-worth rule adds assumptions about production and participation; an interpolation that preserves the theorem’s coalition table is an extra construction. Each could motivate new cooperative-game research, but neither is determined by Theorem 4.1. The threshold rule preserves the result precisely by making partial participation irrelevant.
Theorem 5.5 has the same problem, with an added one. Under the threshold rule, meaningful coalition structures collapse to partitions of the finite type set, so the \(\Delta_2^P\)-complete problem is again the original finite problem in measure notation. Allowing a type’s mass to split among blocks requires worths for partial coalitions and a rule for aggregating worth across potentially many blocks. The paper’s finite coalition-structure result supplies neither. Restricting the continuum to finite measurable partitions is possible, but it does not resolve the missing worth semantics.
The weakness in this negative case is real: a federation in which a role creates worth only when all its members participate is coherent, and the paper’s broad worth-function model allows that kind of complementarity. If the authors accept that scenario, the proposed mirrors are well-posed and the hardness transfers. My case against them is that this is a discrete role game wrapped in a continuous population, rather than a persuasive high-multiplicity version of the paper’s computational questions. I cannot rule out every worthwhile atomless cooperative-game problem inspired by the paper.
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.