| paper | Complexity of Deliberative Coalition Formation |
| authors | Edith Elkind, Abheek Ghosh, Paul Goldberg |
| venue | AAAI 2022 |
| filed under | coalition · hedonic |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 8
statement extracted from the paper’s text layer
Given rational types \(v^1,\ldots,v^\tau\in\mathbb{Q}^d\), rational masses \(\mu_j>0\) with \(\sum_j\mu_j=1\), and a rational threshold \(\eta\in[0,1]\), with status quo \(0\), decide whether there exists \(x\in\mathbb{R}^d\setminus\{0\}\) such that \(\sum_{j:\,\lVert v^j-x\rVert_2<\lVert v^j\rVert_2}\mu_j\ge\eta\).
A finite-support high-multiplicity Euclidean society whose complete types are spatial positions \(v^j\), whose masses are \(\mu_j\), and whose decision variable is a proposal \(x\) maximizing approval mass \(\sum_{j:\,\lVert v^j-x\rVert_2<\lVert v^j\rVert_2}\mu_j\).
The paper's reductions do not establish hardness when \(\tau\) is much smaller than the underlying population, so they leave open whether the high-multiplicity regime changes the complexity or merely reweights a finite instance.
fatal: False
The mirror directly covers centralized SCORE hardness in both Euclidean and hypercube spaces and gives a mass analogue of \(k\)-COMPROMISE; it leaves the transition-length bounds, the \(2^{\Theta(d)}\) compromise-size lower bound, and the positive parameterized results largely untouched.
My strongest mirror is the high-multiplicity version of the paper’s centralized “find a popular proposal” problem. The proposal space remains exactly the paper’s space; only the population becomes continuous. Thus, in the Euclidean model, \(X=\mathbb{R}^d\) is inherited from the paper, not being counted as the continuization.
The type is a complete spatial position \(v\in\mathbb{Q}^d\). A society is a finite-support distribution \(\mu=(\mu_1,\ldots,\mu_\tau)\), where \(\mu_j\) is the fraction of citizens at position \(v^j\), \(\sum_j\mu_j=1\). This is plausible for a national platform-setting exercise in which millions of citizens fall into a few hundred or thousand standardized ideological or demographic-position cells. The individual count \(N\) can be much larger than \(\tau\), with \(\mu_j=a_j/N\).
My lead anchor is Theorem 8: “Euc-SCORE is NP-complete.” This theorem is proved in the paper, by reduction from \(3\)-SAT.
Call the continuous problem \(\textsc{Mass-Euc-SCORE}\). An instance consists of rational vectors \(v^1,\ldots,v^\tau\in\mathbb{Q}^d\), rational masses \(\mu_j>0\), and a rational threshold \(\eta\in[0,1]\). The status quo is \(r=0\). A proposal \(x\in\mathbb{R}^d\setminus\{0\}\) approves type \(v^j\) precisely when
\[ \|v^j-x\|_2<\|v^j\|_2. \]
Its support is
\[ \operatorname{score}_\mu(x) = \sum_{j:\,\|v^j-x\|_2<\|v^j\|_2}\mu_j. \]
The decision question is whether there exists \(x\) with \(\operatorname{score}_\mu(x)\ge\eta\); the optimization version asks for a maximizing proposal.
This is recognizably the authors’ problem: the status quo, metric approval rule, proposal geometry, and objective are unchanged. Only headcount has become mass. The discrete-to-continuous dictionary is exact: from an \(n\)-agent instance, put mass \(1/n\) on each agent’s position, aggregating duplicate positions. Then \(\eta\) becomes the original integer threshold divided by \(n\). Conversely, every rational \(\mu\) can be expanded into a finite electorate with \(N\mu_j\) identical agents. Therefore the expected classification is hardness transfers, Class B. The hardness is driven by the geometry and number of types, not by the accidental naming of individuals; that is precisely a meaningful result for the programme. Natural follow-up questions are whether approximation hardness survives, whether fixed \(d\) gives a polynomial algorithm for the mass problem, and whether more structured distributions yield tractable cases.
A second worthwhile anchor is Corollary 3: “Hyp-SCORE is NP-complete.” It is proved here from Theorem 2, which establishes that Hyp-PERFECT SCORE is NP-complete.
The corresponding problem \(\textsc{Mass-Hyp-SCORE}\) has support types \(v^j\in\{0,1\}^d\), rational masses \(\mu_j\), status quo \(0^d\), and proposal \(x\in\{0,1\}^d\setminus\{0^d\}\). Type \(v^j\) approves \(x\) iff
\[ \|v^j-x\|_1<\|v^j\|_1. \]
The question is whether some proposal has approval mass at least \(\eta\). This models a large population deliberating over a fixed binary agenda: many citizens may share the same complete issue-position vector, perhaps because their views are organized by party, region, occupation, or a standardized policy profile.
Again, the paper’s discrete instance embeds directly by setting \(\mu_j\) equal to the frequency of each type. Repeating every type \(M\) times produces a population of size \(N=M\tau\) without changing the continuous instance. Hence this is also a Class B mirror: the continuous population does not dissolve the NP-hardness. The important further questions concern parameterization by \(d\) or \(\tau\), weighted versus uniform masses, and approximation when only an approximately popular proposal is required.
To cover the genuinely decentralized part of the paper, I would add one dynamic anchor: Corollary 4, proved here, which states that for every \(k\ge2\), there is no polynomial-time algorithm for Hyp-\(k\)-COMPROMISE unless \(P=NP\).
Call its mirror \(\textsc{Mass-Hyp-}k\textsc{-COMPROMISE}\). Besides \((\mu,d)\), the input contains a finite coalition structure
\[ \mathcal D=\{(\alpha^\ell,x^\ell)\}_{\ell=1}^q, \]
where \(\alpha^\ell_j\) is the mass of type \(v^j\) currently in coalition \(\ell\), \(\sum_\ell\alpha^\ell_j=\mu_j\), and every type with positive mass in coalition \(\ell\) approves \(x^\ell\). A valid transition chooses at most \(k\) coalitions and a proposal \(x\). From each selected coalition, all its mass whose type approves \(x\) moves into a new coalition. If that new coalition has mass \(b\), the transition is valid exactly when \(b\) is strictly larger than the mass of every selected coalition; nonapproving mass remains in its old coalition. The task is to output such a transition, or report that none exists.
This is a direct mass translation of Definition 2.1, including the myopic coalition-size incentive. The expected classification is again hardness transfers, because every discrete coalition structure can be represented by rational mass vectors \(\alpha^\ell\). This mirror generates questions that the paper itself does not answer: whether bounded \(\tau\), bounded \(d\), or restricted coalition structure makes transitions tractable; whether continuous mass admits better convergence bounds than the paper’s \(2^n\) bound; and whether approximate or best-response transitions behave differently.
The weakest point is that these mirrors establish a credible continuous population formulation, but they do not produce a Class A tractability gain. Their hardness survives because it lives in the type geometry or agenda dimension. Nor do they automatically mirror the paper’s exponential transition-length results, which would require a careful theory of mass-valued coalition states. Still, that is a limitation of the claim, not a failure of the mirror: the paper contains central, named computational results whose exact high-multiplicity versions are natural, meaningful, and provably inherit the paper’s complexity.
The negative case is weaker than the proponent’s, but there is one real objection: none of the three mirrors, as stated, demonstrates a genuinely population-continuous phenomenon.
For Theorem 8, the proposed \(\textsc{Mass-Euc-SCORE}\) is a weighted restatement of the original problem. The reduction uses one type per original agent, so \(\tau=n\) and every mass is \(1/n\). Expanding each rational mass into duplicate agents merely reverses the encoding. This establishes a weighted high-multiplicity formulation, but not hardness in a regime where a large population is compressed into a small collection of types. The proponent would need results parameterized by \(\tau\), or a natural density representation, to show that continuization contributes anything beyond replacing repeated rows by binary weights.
A genuinely atomless Euclidean population does not obviously repair this. Writing \(x=ru\), approval is
\[ \|v-x\|_2<\|v\|_2 \quad\Longleftrightarrow\quad v\cdot u>r/2. \]
For an atomless distribution, letting \(r\) approach zero eliminates the radial part of the proposal and leaves only the mass of a hemisphere. The original proposal geometry therefore collapses toward an infinitesimal-direction problem; retaining a positive radius or a minimum displacement would create a new model requiring additional justification. The finite-support version avoids this collapse, but then it is precisely a weighted finite instance.
The same objection applies to Corollary 3. \(\textsc{Mass-Hyp-SCORE}\) is perfectly well-defined, and repeated binary issue profiles are sociologically plausible. But the NP-hardness again comes from allowing as many distinct type vectors as agents. If the intended population really consists of a modest number of party, regional, or occupational profiles, the paper’s reduction no longer explains the difficulty. The proposed anchor therefore shows that weighted hardness survives an encoding change, not that a continuous population creates a new computational object.
For Corollary 4, the mass formulation is more delicate. A mass society \(\mu\) does not determine a coalition structure; one must additionally provide \(\alpha^\ell_j\), the mass of each type in each coalition. If there are many coalitions, this requires essentially the full discrete partition as input, so no population compression occurs. If the number of coalitions is bounded, the formulation becomes a legitimate continuous dynamic, but it is then a new measure-valued coalition process rather than a direct consequence of the paper’s decentralized model. The proponent has not shown that its convergence or transition questions retain the paper’s identity-sensitive dynamics in a useful compressed representation.
These objections do not amount to a decisive negative verdict. The paper has named computational results, its agents can naturally be repeated by spatial or binary type, and neither support nor coalition transitions fundamentally requires individual identity. Existing high-multiplicity work would support rather than undermine the modelling choice. Thus the strongest honest conclusion is that the proponent has not yet shown a specifically *continuum-enabled* payoff, but the universal claim that no worthwhile mirror exists cannot be sustained: the finite-support high-multiplicity versions of Theorems 8, 3, and Corollary 4 are all legitimate questions, with the main weakness lying in the case for their added value rather than in their well-posedness.
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.