| paper | Cooperative Games with Overlapping Coalitions |
| authors | G. Chalkiadakis, Edith Elkind, E. Markakis, M. Polukarov, N. Jennings |
| venue | JAIR 2010 |
| filed under | coalition · hedonic |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Polynomial-time solvable in \(m,\tau,k,L\) under the standard binary-rational encoding of resource weights. · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 8
statement extracted from the paper’s text layer
Given a finite type set \(A\), rational masses \(\mu\), per-agent weights \(w_a\), rational task types \(t_j=(T_j,u_j)\), and a finite-support outcome \(\mathcal O\) assigning each type a complete contribution/payoff signature across named old streams, decide whether a measurable deviating submass \(q_a\le\mu_a\), possibly partitioned across deviation patterns, can form or modify overlapping task streams with feasible resource and threshold constraints such that nondeviators preserve their contributions and each deviating unit keeps an old stream's payoff exactly when its contribution there is unchanged, while every deviating unit receives strictly higher payoff.
A nonatomic high-multiplicity \(r\)-core membership problem for OCF threshold-task games: types \(a\) carry mass \(\mu_a\) and resource \(w_a\), task streams have per-capita densities, and deviations optimize per-unit improvement over measurable submasses while preserving the paper's stream-specific payoff-retention rule.
The opponent correctly notes that refined-core deviations depend on stream-by-stream contribution signatures, so aggregate variables such as \(z_{aj}\) are insufficient and generic biclique instances may require nearly one type per vertex.
fatal: False
The mirror covers Theorem 8's \(r\)-core membership and Proposition 9's overlapping-TTG welfare problem, while leaving the \(c\)-core and \(o\)-core results, non-overlapping analogues, non-emptiness, and structural theorems untreated.
There is a credible mirror here, and I would make Theorem 8 the lead. The paper is not already continuous: its vectors \(r\in[0,1]^n\) make each finite agent’s resource divisible, but the population is still a finite set of named agents.
The natural regime is a large pool of cloud workers, edge devices, or sensors repeatedly assigned to tasks. A type \(a\) is a complete capability-and-contract profile: resource weight \(w_a\), current participation pattern in the task streams, and current payoff pattern. The society is a distribution \(\mu=(\mu_a)_{a\in A}\), where \(\mu_a\) is the fraction of the workforce of type \(a\), with \(|A|=\tau\ll N\). Agents of one type are interchangeable, but may split their resource among overlapping tasks exactly as in the paper.
A continuous OCF outcome is represented by densities of task instances and aggregate resource allocations. If \(y_j\) is the number of type-\(j\) tasks per unit population and \(z_{aj}\) is the resource supplied by type \(a\), feasibility requires \(\sum_j z_{aj}\le\mu_aw_a\) and \(\sum_a z_{aj}\ge T_jy_j\). Each finite task remains an ordinary integral task; \(y_j\) is its density in a high-multiplicity population. Thus this is not merely reusing the paper’s fractional participation variable.
Theorem 8 is my strongest anchor. It states, and is proved in this paper, that given a threshold task game \(G=(N;w;t)\) and an outcome \((CS,x)\) of the corresponding overlapping game \(\dot G\), deciding whether \((CS,x)\) belongs to the refined core is strongly coNP-complete. The proof is a reduction from MAXIMUM EDGE BICLIQUE. The difficulty is not just choosing whether to deviate: agents must decide which existing partial coalitions to abandon while retaining payoffs from coalitions whose contributions remain unchanged.
The corresponding continuous problem is:
Continuous Refined-Core Membership for OCF-TTG. An instance consists of a finite type set \(A\), rational masses \(\mu_a\), weights \(w_a\), rational task types \((T_j,u_j)\), and a finite-support continuous outcome \(\mathcal O\). The outcome specifies each task-stream class, the contribution made by every type to that class, and the payoff received by each type from it. A measurable submass \(q_a\le\mu_a\) may deviate. It may preserve its contribution to some old streams, change or abandon its contribution to others, and form new overlapping task streams. Nondeviating mass must retain the old contribution pattern. A deviating infinitesimal agent retains the payoff from an old stream exactly when its contribution to that stream is unchanged, as in Definition 9; otherwise that payoff is lost. The deviators may redistribute the value of their new task streams among themselves.
The decision question is whether there exists a positive-mass deviation for which every deviating agent receives strictly more than under \(\mathcal O\). Equivalently, maximize the minimum per-agent improvement \(\delta\) over all measurable deviations and answer YES precisely when \(\delta>0\) is achievable. A solution is therefore either a certificate consisting of the deviating type masses, changed-stream pattern, new resource allocation, and payoff allocation, or a proof that no such deviation exists.
I would expect this problem to be Class B: hardness transfers. The MAXIMUM EDGE BICLIQUE instance can be lifted by replacing each original player with a repeated type of mass \(1/n\), and then taking arbitrarily many clones of each type. The graph is stored in the type’s participation/payoff signature across the old task streams, not in the names of individual agents. In the paper’s reduction, the large payoff \(M\) makes abandoning a non-edge stream unprofitable. Consequently, the support of any profitable mass deviation must still have the common-neighbourhood structure of a biclique. Fractional mass does not remove that combinatorial support condition: for any chosen set of streams, taking all compatible type mass is at least as profitable as taking only part of it. The hard object therefore lives in the type-interaction pattern, not in the number of agents.
This is a plausible author-recognisable continuation because it retains the paper’s exact stability concept, overlapping resource allocation, threshold tasks, and the distinction between c-, r-, and o-deviations. It only replaces a large collection of interchangeable players by type masses.
A second, supporting anchor is Proposition 9, proved in Appendix A. It states that, given a TTG \(G\) and \(K\), deciding whether the overlapping game \(\dot G\) has an outcome of social welfare at least \(K\) is NP-complete. It also states that the problem becomes polynomial-time solvable when all weights, thresholds, and utilities are unary, or when there are at most two task types.
Its continuous counterpart is:
Continuous OCF-TTG Welfare Density. Given \(\mu\), weights \(w_a\), task types \((T_j,u_j)\), and a rational target \(K\), choose task densities \(y_j\ge0\) and resource allocations \(z_{aj}\ge0\) satisfying \(\sum_jz_{aj}\le\mu_aw_a\) and \(\sum_az_{aj}\ge T_jy_j\). Maximize the per-capita welfare \(\sum_j u_jy_j\), and decide whether the optimum is at least \(K\).
This is a genuine high-multiplicity version of the paper’s welfare problem: for a finite society of size \(N\), task counts are integers \(\alpha_j\), while \(y_j=\alpha_j/N\); the continuous problem is the limit as \(N\) grows. It is a Class A problem. With unrestricted task densities, the optimum is obtained by the best utility-to-resource ratio, \(\max_j u_j/T_j\), subject to the aggregate resource \(\bar w=\sum_a\mu_aw_a\). The finite NP-hard unbounded-knapsack structure becomes a density LP, while the individual task instances themselves remain integral.
These mirrors cover the paper’s computational results on overlapping-task welfare and refined-core membership. They do not claim to continuize every theorem: the c-core and o-core deserve separate questions, and the structural existence theorems are not themselves computational anchors.
The weakest point is that the continuous r-core must allow partial type masses to change different old coalitions, so its deviation space is richer than the finite one. Theorem 8’s reduction should therefore be regarded as a strong hardness-transfer conjecture until written out formally. Proposition 9 has a separate vulnerability: if task instances are globally indivisible and do not scale with the population, the density LP is not the right limit. In the repeated-task cloud or sensor setting, however, task density is forced by high multiplicity, making the mirror both natural and technically meaningful.
The negative case is weaker than the proponent admits, but it cannot honestly sustain the universal conclusion.
Theorem 8 is not a clean population-complexity anchor. Its reduction encodes the MAXIMUM EDGE BICLIQUE instance in the payoff matrix \(x_i^j\): each player’s entire vector of payoffs across the \(k\) existing coalitions records that player’s neighbourhood in the graph. A type preserving the refined-core semantics must therefore include the complete participation, coalition, and payoff signature. In a generic graph, almost every vertex becomes a different type. Replicating each such type many times merely replaces named vertices by weighted vertex classes; the hard combinatorics remains in the type catalogue and the labelled coalition streams, not in population multiplicity.
There is also a genuine quotienting problem. The refined core tracks which particular contribution to which particular coalition a deviator changes, because that determines which old payoff is lost. Aggregate quantities such as \(z_{aj}\) do not say whether the same mass supplied all streams or whether different submasses supplied different streams. Those configurations have different refined-core deviations. Preserving the distinction requires a measure over complete contribution vectors—or splitting every such pattern into a separate type. The former is an infinite-dimensional state description; the latter can require as many types as the original individualized instance.
Allowing a type’s mass to split does not repair this cleanly. It changes the reduction from selecting whole players and whole coalition incidences to selecting fractional vertex mass. Forbidding such splitting preserves the biclique gadget only by making types indivisible blocks, so the “continuum” is then just a weighted finite graph. Thus the proposed mirror either loses the paper’s refined-core semantics or makes population multiplicity computationally incidental. This is a serious objection, although not a proof that no carefully designed typed application could be worthwhile.
Proposition 9 is an even less convincing population anchor. In the paper’s overlapping TTG, welfare depends on the population only through total resource \(w(N)\). Under a distribution \(\mu\), all type information collapses to the single mean resource
\[
\bar w=\sum_a \mu_a w_a.
\]
Replacing integer task counts \(\alpha_j\) by densities \(y_j\) then yields the ordinary fractional knapsack expression
\[
\max \sum_j u_jy_j
\quad\text{subject to}\quad
\sum_j T_jy_j\le \bar w.
\]
That is primarily a continuization of task multiplicities, not of the society. It becomes a legitimate population mirror only after adding a new assumption that task opportunities and task welfare scale with population. That assumption is plausible for a cloud-workforce or sensor-network application, but it is not supplied by Proposition 9 itself. Without it, the continuous society is substantively irrelevant; with it, the result is a new asymptotic task-market model rather than a direct mirror of the paper’s computational question.
Still, this does not justify the universal negative claim. A repeated-worker, repeated-task interpretation makes Proposition 9 a sensible high-multiplicity relaxation, and a carefully specified finite-support version of Theorem 8 could be a meaningful weighted typed-deviation problem. The honest conclusion is therefore that the proponent’s Theorem 8 mirror is under-specified and the Proposition 9 mirror is population-degenerate unless extra scaling assumptions are supplied—but I cannot defensibly claim that every worthwhile continuous mirror is ruled out.
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.