| paper | Complexity of coalition structure generation |
| authors | H. Aziz, B. de Keijzer |
| venue | ATAL 2011 |
| filed under | coalition · wvg |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Computing an optimal coalition structure is in \(\mathrm{P}\), with running time \(O(\tau L^2)\) bit operations. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 2
statement extracted from the paper’s text layer
Given finitely many types \(T\), rational masses \(\mu\in\mathbb{Q}_{\ge0}^{T}\) with \(\sum_t\mu_t=1\), rational per-agent weights \(w_t\), and a rational per-capita quota \(q>0\), partition the unit mass into finitely many profiles \(x^1,\ldots,x^r\in\mathbb{R}_{\ge0}^{T}\) satisfying \(\sum_j x^j=\mu\), maximizing the number of blocks \(j\) with \(\sum_t w_t x^j_t\ge q\), using a compact multiplicity representation for repeated profiles.
A nonatomic weighted voting game in which type \(t\) carries mass \(\mu_t\) and per-agent weight \(w_t\); decision variables are coalition mass profiles and their multiplicities, and the objective counts profiles reaching the aggregate quota \(q\).
Every faithful atomless version collapses to the aggregate weight \(W=\sum_t w_t\mu_t\), so the mirror may be a weak flagship because it removes nearly all coalition-formation combinatorics.
fatal: False
The mirror covers Proposition 2 and the weighted-voting portion of the paper, with Corollary 1 providing supporting high-multiplicity evidence. It leaves the type-identification lower bounds, graph, flow, matching, path, skill-game, minimal-winning-coalition, and threshold-game results unmirrored.
My lead anchor is Proposition 2, proved in this paper. It states:
For a weighted voting game, deciding whether there exists a coalition structure with social welfare at least \(k\) is NP-complete.
Here a weighted voting game is \([q;w_1,\ldots,w_n]\); a coalition is winning when its total weight reaches \(q\), and the welfare of a coalition structure is the number of winning coalitions it contains. The paper proves the result by reducing from Partition and notes that strong NP-hardness follows from 3-Partition.
The continuous mirror I would propose is Mass-WVG Coalition Structure Generation\(_\infty\).
An instance consists of a finite set of player types \(T=\{1,\ldots,\tau\}\), a rational population distribution \(\mu\in\mathbb{Q}_{\ge 0}^{\tau}\) with \(\sum_t\mu_t=1\), a rational voting weight \(w_t\ge0\) for each type, and a positive rational quota \(q\). Type \(t\) represents a mass \(\mu_t\) of agents who are strategically identical: every agent of that type contributes weight \(w_t\), and there are no other player-specific attributes.
A coalition is now a mass profile \(x\in\mathbb{R}_{\ge0}^{\tau}\). It is winning when
\[ \sum_{t=1}^{\tau} w_t x_t\ge q. \]
A continuous coalition structure is a partition of the population into such profiles. Its welfare is the number of winning blocks. For computational purposes the output is given compactly as profiles with multiplicities, rather than by listing every individual agent or every repeated block. The problem asks for a welfare-maximising continuous coalition structure.
The natural regime is a large federation, authority, or organisation in which many agents belong to a modest number of statutory voting-power classes: for example, thousands of delegates from each of several accreditation levels. The number of agents is enormous, while \(\tau\) is small relative to the population, though \(\tau\) need not be a constant. Agents within a type share the same weight and are interchangeable in the game. This is exactly the high-multiplicity interpretation of the paper’s player types, not an assumption that all named individuals have identical prices or preferences.
The quota is interpreted per capita: a discrete population of size \(N\) has \(N\mu_t\) agents of type \(t\) and quota \(Nq\). This is the natural macroscopic regime in which a winning coalition consumes a non-vanishing fraction of the population. It is also the kind of co-modification that continuization requires when supplies and thresholds must scale with population size.
This problem is immediately solvable. Let
\[ W=\sum_{t=1}^{\tau}w_t\mu_t \]
be the society’s total voting weight. Every winning coalition consumes at least \(q\) units of weight, so no structure can contain more than
\[ K^\star=\left\lfloor\frac{W}{q}\right\rfloor \]
winning coalitions. Conversely, if \(K^\star>0\), divide every type mass equally among \(K^\star\) coalitions: set
\[ x_t=\frac{\mu_t}{K^\star}. \]
Each block then has weight \(W/K^\star\ge q\), so all \(K^\star\) blocks win. Thus \(K^\star\) is optimal, and the solution has a compact representation consisting of one profile \(x\) with multiplicity \(K^\star\). The answer is computable in polynomial time in \(\tau\) and the input bit length.
So I expect this mirror to be Class A: tractable. Proposition 2’s discrete hardness comes from indivisibly assigning particular weights to particular coalitions, exactly the kind of combinatorics that disappears when each type is divisible. This is not an arbitrary simplification: the underlying weighted-voting game, quota rule, exhaustive partition requirement, and welfare objective are all retained. What changes is the population regime.
The paper itself makes this interpretation especially plausible. Its Definition 15 identifies strategically equivalent players as belonging to the same type, and Corollary 1, proved in the paper, gives a polynomial-time algorithm for WVG coalition-structure generation when the number of distinct weights is constant. The proposed mirror is the corresponding divisible-population question, with the number of weight types allowed to vary. Existing type-based tractability therefore supports, rather than collides with, the mirror.
The high-multiplicity dictionary is direct. Given a discrete instance with \(N\mu_t\) agents of type \(t\), every discrete coalition structure induces profiles \(x^j_t\) recording the fraction of type \(t\) placed in coalition \(j\). Conversely, a continuous structure whose profiles have denominators dividing \(N\) expands to an ordinary discrete coalition structure. The continuous problem is therefore the divisible relaxation of the same OptCS(WVG) problem. In the discrete problem, the Partition reduction exploits integrality; in the continuous problem, the same total weight can be split across blocks and the reduction no longer works.
The main weakness is that the mirror uses a macroscopic quota \(Nq\), rather than holding the paper’s numerical quota fixed while increasing the population. If a referee insists on the latter scaling, the resulting limit describes microscopic coalitions and is a different question. I would defend the proposed scaling as the honest continuum regime for coalition formation: quota is a fraction of total voting capacity, just as population mass is a fraction of society. The mirror also deliberately covers Proposition 2 rather than every result in the paper; it does not claim that all graph games, minimal-winning-coalition representations, or threshold games become easy.
It generates useful follow-up questions: whether bounded coalition sizes restore hardness; how much discrete welfare is lost when a continuous solution is rounded to \(N\) agents; whether multiple simultaneous quotas still admit a closed-form solution; and whether graph-game interaction terms produce genuinely continuum-specific hardness.
Proposition 2 is the only serious anchor, and the strongest negative case is that its continuous relaxation degenerates. This is not because weighted voting lacks a high-multiplicity interpretation: thousands of delegates in a few voting-weight classes are an entirely sensible continuous society. Corollary 1 is therefore supporting evidence, not a novelty collision.
The difficulty is that every atomless version preserving the substance of Proposition 2 collapses to one scalar. Let
\[ W=\sum_t w_t\mu_t \]
be the total voting weight. If \(k\) disjoint mass-coalitions are winning, then \(kq\le W\). Conversely, for \(k=\lfloor W/q\rfloor\), divide every type mass equally among \(k\) coalitions. Each coalition then has weight \(W/k\ge q\). Hence
\[ \operatorname{OPT}=\left\lfloor\frac{W}{q}\right\rfloor. \]
This argument is independent of whether the quota is fixed or scaled per capita. With a fixed quota, the normalized welfare converges to the same scalar ratio; with a macroscopic quota, the optimum is already exactly the displayed integer.
Thus the continuous structure does not retain the combinatorial object responsible for Proposition 2: the indivisible assignment of particular weights to particular coalitions. Every type can be spread proportionally across every coalition, so the optimal structure is just repeated copies of the same aggregate profile. The entire type space matters only through total weight.
A better version cannot recover that combinatorics while remaining this problem. Forbidding a type from being split, or treating its mass as indivisible packets, returns to the discrete problem. Adding compatibility constraints, coalition-size bounds, type quotas, or graph interactions creates a different coalitional game rather than a continuization of the WVG result. Fixing the number of coalitions does not help: feasibility is still determined by aggregate weight.
Corollary 1 does not independently rescue the proposal. The paper already identifies bounded weight classes as a tractable high-multiplicity regime; replacing integer multiplicities by divisible masses adds a relaxation, but no new structural computational question. I would not call that prior work a collision—the programme explicitly treats high-multiplicity results as supporting evidence—but the continuous version looks more like a one-line capacity baseline than a worthwhile mirror of the paper’s complexity landscape.
This negative case is not airtight. The proposed society is well-posed, and if ChoCo values documenting exact collapses and discrete-to-continuous rounding bridges, Proposition 2 survives. What the negative case can honestly establish is narrower: this paper’s central WVG hardness result is a poor flagship mirror, because every faithful atomless version destroys the very coalition-formation structure that made the result interesting.
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.