| paper | d4-conf-ijcai-2009-0140 |
| 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}\)-complete · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 5
statement extracted from the paper’s text layer
Given a finite set of complete belief types \(\Theta\), rational masses \(\mu_\theta>0\) summing to \(1\), rational type-to-type belief weights \(b_{\theta\phi}\), a threshold \(q\), and a proposed finite coalition structure with type masses \(x_{j\theta}\) and demand rates \(d_{j\theta}\), decide whether the outcome is in the continuous CS-core. A blocking deviation selects masses \(y_{j\theta}\in[0,x_{j\theta}]\); every participating type \(\theta\) must believe it succeeds, meaning \(\sum_\phi b_{\theta\phi}Y_\phi\ge q\), where \(Y_\phi=\sum_j y_{j\phi}\), and the weighted incumbent payoff must satisfy \(\sum_{j,\theta} y_{j\theta}d_{j\theta}u_\theta(C_j)<1\). Is there such a deviation?
Agents of each type share a complete belief profile, and \(\mu_\theta\) is their population mass. The proposed outcome assigns that mass to coalition blocks with per-capita demand rates; the decision witness is a type-by-block mass transfer \(y_{j\theta}\). A blocking coalition must meet each participating type’s threshold belief and have total incumbent payoff below \(1\), so it can offer every member a strictly higher rate while keeping total demand equal to \(1\).
The mirror is most natural for projects whose capability threshold grows with the workforce, while some of the paper’s motivating team tasks may have fixed requirements.
fatal: False
The mirror covers Theorem 5’s CS-core membership problem for weighted voting games with beliefs; it leaves Theorem 6’s CS-core nonemptiness result and the simple-game core results aside.
The strongest anchor is Theorem 5, proved in this paper. It says that, given a weighted voting game with beliefs \(G=(N;\vec b;q)\) and an outcome \((CS,d)\), deciding whether that outcome belongs to the CS-core is coNP-complete—even when every integer belief weight satisfies \(b_i(j)\le n\). The paper gives a reduction from CLIQUE, though it omits a subclaim of the reduction for space. This result isolates a useful question: does the difficulty of finding a coalition that can successfully deviate survive when the population is represented by mass?
A plausible regime is a large decentralized response or service operation with thousands or millions of autonomous units but only tens or hundreds of recurring capability-and-belief profiles. For example, units in a profile might have the same equipment and the same point estimates of what each capability class can do. Teams form to carry out tasks that succeed once their perceived capability threshold is met, and members negotiate shares of the team’s expected payoff. This retains the paper’s threshold game, private point beliefs, coalition structures, and demand-based stability. It makes the agents numerous while keeping the support \(\tau\) modest. A type must include its whole relevant profile, including its belief rule; grouping agents by capability alone would not suffice.
I would call the mirror Continuous WVG-with-Beliefs CS-Core Membership. Its input is a finite type set \(\Theta\), rational masses \(\mu_\theta>0\) summing to \(1\), a rational threshold \(q\), and rational nonnegative belief weights \(b_{\theta\phi}\). A type-\(\theta\) agent believes a coalition \(S\) succeeds exactly when
\[
\sum_{\phi\in\Theta} b_{\theta\phi}\,\mu_\phi(S)\ge q,
\]
where \(\mu_\phi(S)\) is the mass of type \(\phi\) in \(S\). Thus beliefs remain point beliefs; they are not replaced by probability distributions.
The input also gives a proposed outcome with finitely many coalition blocks \(C_1,\ldots,C_r\). Let \(x_{j\theta}\) be the mass of type \(\theta\) in block \(C_j\), and \(d_{j\theta}\) the per-capita demand rate for that mass. Require \(\sum_jx_{j\theta}=\mu_\theta\) and \(\sum_\theta x_{j\theta}d_{j\theta}=1\) for each block. The rate is the demand share scaled by population mass: if each of \(n\) discrete agents has mass \(1/n\), its rate is \(n\) times its demand share. This keeps the total demand for a successful coalition equal to one.
The decision question is whether that outcome is stable. A proposed deviation is described by masses \(y_{j\theta}\in[0,x_{j\theta}]\) drawn from the incumbent blocks. Write \(Y_\phi=\sum_j y_{j\phi}\). Every type with \(y_{j\theta}>0\) must believe the deviating coalition succeeds:
\[
\sum_\phi b_{\theta\phi}Y_\phi\ge q.
\]
Its incumbent payoff rate is \(p_{j\theta}=d_{j\theta}u_\theta(C_j)\), where \(u_\theta(C_j)\) is \(1\) or \(0\) according to that type’s belief. A deviation is profitable exactly when
\[
\sum_{j,\theta}y_{j\theta}p_{j\theta}<1.
\]
Then the deviators can choose rates \(e_{j\theta}>p_{j\theta}\) whose total demand is one. So the mass profile \(y\) is the stability witness; there is no separate welfare objective. The problem asks whether such a witness exists, or equivalently whether the proposed outcome is outside the continuous CS-core. Its natural complexity parameters are \(\tau\), \(r\), and the rational input bit length \(L\).
I expect this problem to remain hard, probably for continuum-specific reasons: choosing which belief types participate still creates a combinatorial search over \(\tau\), even though each type can contribute fractional mass. I would not claim Theorem 5’s hardness transfers automatically. Its CLIQUE reduction concerns indivisible players, and fractional participation may invalidate that reduction. Resolving whether the continuous problem is tractable, remains coNP-hard, or becomes hard in a different way is exactly the interesting complexity question. Further questions include how hardness changes with bounded \(\tau\), whether the discrete result can be recovered under a granularity restriction, and what the continuous analogue of the paper’s CS-core nonemptiness result, Theorem 6, looks like.
My weakest point is the symmetry built into the regime: the paper permits each player to have a separate belief vector, while this mirror groups agents whose belief rules agree by type. That is a genuine restriction, and the continuous membership test also uses a finitely described coalition structure. But both fit a plausible large-population setting in which many agents share profiles and form a finite set of teams. The mirror still asks the paper’s underlying question—whether any coalition can block a proposed outcome—while making population mass, rather than named individuals, the object being divided.
Theorem 5 is a real computational anchor: the paper proves a named complexity result about CS-core membership. So the case against cannot be that there is no result to mirror, or that existing continuous work has already settled it.
The weakness is that the theorem’s hard instances are built from individually indexed belief vectors. In the CLIQUE reduction, the belief data encode a graph on the players. To retain that arbitrary graph when agents are grouped by complete type, the model needs a type for each distinct belief profile; the reduction therefore gives no evidence for hardness in a regime with many agents but relatively few recurring types. A type-to-type belief matrix is a coherent stronger mirror, and agents in a large operation could plausibly share role-based beliefs. But it replaces the paper’s individualized guesses about named potential partners with common beliefs about categories. That is a meaningful homogeneous restriction, not an objection to high multiplicity itself—and it leaves the connection between the theorem’s hardness and the proposed population regime unestablished.
There is also a scaling problem for the paper’s team-formation interpretation. If agents have bounded contributions and tasks require a fixed amount of capability, normalizing population to mass one sends the threshold from \(q\) to \(q/n\). As \(n\) grows, the threshold tends to zero; the resulting mass model no longer captures the original distinction between small coalitions that can and cannot execute a task. Theorem 5’s proposed pair blocks also have mass tending to zero as the number of graph vertices grows. Keeping a nontrivial threshold requires scaling task requirements with population, so that teams must command a positive fraction of the workforce. That can describe a large collective project, but it is a less direct fit for the paper’s setting of agents splitting into teams to perform tasks.
The stronger mirror can address this by choosing macroscopic projects, type-level beliefs, and per-capita demand rates. It can also represent heterogeneous incumbent demands with a richer distribution over rates. Those choices make a coherent continuous CS-core membership question; they are not formal flaws. The objection is that the more faithfully the model preserves the theorem’s individualized belief structure and small-team setting, the less it looks like a population continuum; the more clearly it becomes a mass model, the more of the motivating structure has been replaced. Theorem 6’s partition-into-triangles result faces the same gap: its graph vertices and exact-cover blocks are discrete players, and its reduction does not establish a meaningful mass-based regime.
That is the strongest negative case I can make, but it is not a universal defeat. A role-based model of a large, population-scaled collective project remains plausible, and the paper’s authors might recognize it as a worthwhile homogeneous version of their problem. The case against is therefore weak at the crucial point: it questions the fit and motivation of the best mirror, but cannot honestly show that no worthwhile scenario exists.
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.