| paper | On the complexity of core, kernel, and bargaining set |
| authors | G. Greco, Enrico Malizia, L. Palopoli, Francesco Scarcello |
| venue | AI 2011 |
| filed under | coalition · wvg |
| judged by | gpt-5.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{coNP}\)-complete under polynomial-time many-one reductions, even for equal positive dyadic masses; \(\mathrm{NP}\)-hard under polynomial-time Turing reductions. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Corollary 4.9
statement extracted from the paper’s text layer
Given rational \(\mu\in\mathbb{Q}_{\ge 0}^{\tau}\) with \(\sum_t\mu_t=1\) and a symmetric rational type-interaction matrix \(W=(w_{tu})\) with \(w_{tt}=0\), define \(V_W(a)=\sum_{t<u}w_{tu}a_ta_u\) for \(a\in[0,\mu]\); decide whether there exists \(x\in\mathbb{R}^{\tau}\) such that \(\sum_t\mu_tx_t=V_W(\mu)\) and \(\sum_ta_tx_t\ge V_W(a)\) for every coalition-mass vector \(a\in[0,\mu]\).
A high-multiplicity block graph game with \(r\mu_t\) interchangeable agents of type \(t\), cross-type pair weights \(w_{tu}/r\), coalition mass \(a\), and a common per-agent payoff \(x_t\) for each type.
The opponent's strongest point is that \(F(b)\) is affine in each coordinate, so its maximum over \([0,1]^\tau\) occurs at a vertex; the proponent did not show that genuinely fractional coalitions bind.
fatal: False
The mirror covers core non-emptiness and its hardness/membership theme in the block-graph high-multiplicity regime; it leaves kernel membership, bargaining-set membership, and the paper's other structural results alone.
The strongest honest case is a single lead mirror for the paper’s core non-emptiness result. I would not force the kernel or bargaining-set results into the continuum: their definitions distinguish a coalition containing individual \(i\) from one excluding individual \(j\), and that distinction becomes measure-zero in an atomless population. A type-level replacement is possible, but it would be a materially less faithful problem.
The lead mirror is a continuous block-graph game. There are \(\tau\) agent types, with population distribution \(\mu=(\mu_1,\ldots,\mu_\tau)\), where \(\mu_t\) is the fraction of society of type \(t\). A type includes the complete role of an agent: its reservation payoff and its interaction with every other type. The intended regime is many repeated agents in a small number of roles—for example, a large cooperative production system with many interchangeable workers, suppliers, or local teams whose complementarities depend only on role. Thus \(n\) is large while \(\tau\) is fixed or at least much smaller than \(n\).
Let \(W=(w_{tu})\) be a symmetric weighted interaction graph on the types. If a coalition contains mass \(a_t\in[0,\mu_t]\) of type \(t\), define its normalized worth by
\(\displaystyle V_W(a)=\sum_{t<u}w_{tu}a_ta_u.\)
This is the continuum analogue of the graph-game worth: value comes from interactions whose two endpoints are present in the coalition. An allocation is a type-level per-agent payoff vector \(x=(x_1,\ldots,x_\tau)\). The continuous core problem is:
\(\displaystyle \mathsf{CoreNonEmptiness}_\infty:\)
given rational \(\mu\) and \(W\), decide whether there exists \(x\in\mathbb R^\tau\) such that
\(\displaystyle \sum_t\mu_tx_t=V_W(\mu)\)
and
\(\displaystyle \sum_t a_tx_t\ge V_W(a)\quad\text{for every }a\in[0,\mu].\)
A solution is the payoff rate \(x_t\) assigned to every member of type \(t\). The objective is feasibility, exactly as in the paper’s core non-emptiness problem; a constructive version outputs such an \(x\).
This is genuinely a continuous-population question. Take \(r\mu_t\) finite agents of type \(t\), make every type-\(t\)/type-\(u\) edge have weight \(w_{tu}/r\), and let a coalition contain \(k_t\) agents of type \(t\). With \(a_t=k_t/r\),
\(\displaystyle \frac{1}{r}v_r(S)=\sum_{t<u}w_{tu}\frac{k_t}{r}\frac{k_u}{r}=V_W(a).\)
Thus the continuous problem is the high-multiplicity limit of the corresponding block graph games. The finite games are invariant under permutations within each type, and because the core is convex, averaging any core allocation over those permutations yields a type-constant allocation. So restricting the continuous allocation to \(x_t\) is not an arbitrary simplification.
The named lead anchor is Corollary 4.9, proved in this paper. It states:
Let \(\mathcal R\) be any nondeterministic polynomial-time compact representation such that \(\mathcal G\precsim_e\mathcal R\), for example marginal contribution nets. On the class \(\mathcal C(\mathcal R)\), \(\textsc{Core-NonEmptiness}\) is \(\mathrm{coNP}\)-complete.
Here \(\mathcal G\precsim_e\mathcal R\) means that graph games can be translated in polynomial time into equivalent \(\mathcal R\)-games with the same coalition-worth function. \(\textsc{Core-NonEmptiness}\) asks whether there exists an imputation \(x\) satisfying \(x(S)\ge v(S)\) for every coalition and efficiency for the grand coalition. The paper proves the upper bound in Theorem 4.8, while the hardness component comes from Proposition 4.3 and the cited graph-game hardness of Deng and Papadimitriou. The corollary therefore covers graph games, marginal contribution networks, and every sufficiently expressive nondeterministic compact representation.
The continuous question above is recognisably the same question: does any payoff distribution protect the entire population against every possible deviating coalition? What changes is only the population object: membership bits for named agents become masses \(a_t\), while the cooperative-game structure and the core’s blocking condition remain intact. It is not continuity of outcomes, lotteries, or probabilities; the continuous object is the society and the possible deviating mass.
I would expect the unrestricted continuous problem to remain computationally interesting, probably with a split rather than a universal answer. For fixed \(x\), separation asks whether
\(\displaystyle \max_{0\le a\le\mu}\bigl(V_W(a)-a\cdot x\bigr)>0.\)
For block graph games this is a signed quadratic optimization problem over a box. Hence the continuous relaxation does not automatically erase the combinatorics: hardness may survive through the type-interaction graph, giving a Class B problem. On structured type graphs—bounded treewidth, restricted signs, or interaction functions with an efficient separation oracle—the core becomes a semi-infinite linear-feasibility problem amenable to continuous-optimization machinery, suggesting Class A subclasses. The central questions are whether the paper’s hard gadgets survive fractional coalition masses, and precisely which interaction structures admit polynomial separation.
The weakest point is that an arbitrary graph game from the paper is not automatically a convincing high-multiplicity population: its edges may encode idiosyncratic individual relationships. The mirror therefore relies on the legitimate but narrower regime of repeated role-based interaction, represented by a block graph or step graphon. If a referee insists that only the original arbitrary graph instances count, this case weakens. But for the programme’s stated standard—find a sensible high-multiplicity scenario for one named result—the block-graph core is a faithful, concrete mirror of Corollary 4.9, and it gives a precise continuous problem whose tractability boundary is worth studying.
The proponent’s lead anchor does not survive in the form stated. The proposed “continuous” core is exactly a finite graph-game core on the types.
Assume \(\mu_t>0\), and write \(b_t=a_t/\mu_t\) and \(y_t=\mu_t x_t\). The violation of a core constraint is
\[ F(b)=\sum_{t<u}w_{tu}\mu_t\mu_u b_tb_u-\sum_t y_tb_t, \qquad b\in[0,1]^\tau . \]
For each coordinate \(b_t\), \(F\) is affine when all other coordinates are fixed. Therefore its maximum over the box is attained at a vertex \(b\in\{0,1\}^\tau\). Consequently, it is enough to test coalitions containing either all or none of each type. The continuous core conditions reduce to
\[ \sum_{t\in S}y_t\geq \sum_{\{t,u\}\subseteq S}w_{tu}\mu_t\mu_u \]
for every \(S\subseteq T\), together with efficiency. That is precisely the core of a finite \(\tau\)-player graph game with rescaled edge weights.
This is not merely a disappointing complexity result. The partial-mass coalitions—the purported continuous object—cannot be binding at all. Replicating each type \(r\) times does not repair this: with the proposed \(w_{tu}/r\) scaling, the same multi-affine argument shows that every coalition of partial type blocks is dominated by a coalition containing whole blocks. The alleged high-multiplicity limit therefore adds no population-level structure; it is a finite type game written with mass variables.
The natural repair is to add interactions among members of the same type, producing diagonal terms such as \(q_t a_t^2\). That can make fractional masses matter, but it is no longer the proposed mirror of the paper’s graph games. The paper supplies weights for named pairs; it supplies neither type classes nor a convention that every pair within a type should receive a particular scaled interaction. The diagonal density is additional modelling data. Different choices agree on the original finite graph problem while producing different continuous cores. A genuinely nontrivial fractional extension is therefore not determined by Corollary 4.9; it defines a new dense mean-field cooperative game.
The same issue appears more generally. The finite worth function specifies values only at incidence vectors of coalitions. To evaluate a fractional coalition one must choose an extension—multilinear, concave, threshold-based, or something else. For graph games, the canonical multilinear extension collapses as above. Any extension for which interior masses become computationally important imports assumptions absent from the paper and makes the resulting complexity depend on the extension rather than on the paper’s compact representation.
A graphon or continuous-location version could be interesting, but it would not rescue this anchor. A finite-step graphon again reduces to the finite type calculation; a genuinely continuous kernel introduces an infinite-dimensional object and a new representation problem. Its complexity would concern the encoding and approximation of the kernel, not the compact graph-game problems proved in this paper.
The kernel and bargaining-set results are even less promising: their definitions explicitly compare coalitions containing named \(i\) while excluding named \(j\), and a faithful atomless analogue loses that distinction. Type-level replacements would require new notions of surplus, objection, and counterobjection.
So I would reject the proposed block-graph construction as a worthwhile continuous mirror of Corollary 4.9: it is a finite graph-game core in disguise. I would not claim that no related mean-field cooperative game could ever be worth studying; adding density-dependent interactions could produce one. But that would be a new model motivated by the paper, not a continuization of any computational result established in it.
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.