| paper | Coalition Formation Games and Social Ranking Solutions |
| authors | — |
| venue | AAMAS 2022 |
| filed under | coalition · hedonic |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 3.2
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu_t\ge0\) with \(\sum_{t\in T}\mu_t=1\), a finite template set \(\mathcal K\subseteq\mathbb Z_{\ge0}^{\tau}\setminus\{0\}\), and a total preorder \(\succcurlyeq\) on \(\mathcal K\), find \(q\ge0\) satisfying \(\sum_{a\in\mathcal K}a_tq_a=\mu_t\) for every \(t\), such that no template \(b\) has \(\sum_{a:\,b\succ a}a_tq_a>0\) for every type \(t\) with \(b_t>0\).
A type-symmetric repeated-team high-multiplicity model: \(\mu_t\) is the mass of interchangeable type \(t\), \(q_a\) is the mass of teams with composition template \(a\), and the task is to construct a core-stable \(q\) under the common strength preorder.
The paper supplies no type-invariant encoding for its arbitrary subset preorder, so the mirror is restricted to a newly specified finite template family and its tractability depends on how that family and \(\phi\) are represented.
fatal: False
The mirror covers only the strength-only hedonic result Theorem 3.2; Theorems 3.8 and 3.10 and Proposition 4.3, including lex-cel and non-hedonic partition effects, are left untouched.
The strongest honest mirror is of Theorem 3.2, proved in this paper. It states that, for the hedonic game \(G_1\) whose preferences depend only on coalitional strength, the core is exactly the set \(A(\succeq)\) generated by Algorithm 1. This is a constructive algorithmic result, although the paper does not state a formal \(P\)-time bound or any NP-hardness theorem.
I would call the mirror \(\mathrm{StrengthCore}_\infty\). There are finitely many complete agent types \(T=\{1,\ldots,\tau\}\), with rational masses \(\mu_t\ge 0\) and \(\sum_t\mu_t=1\). A type includes the agent’s role, coalition preferences, and all parameters relevant to the power relation. The intended regime is a large organization repeatedly forming teams: many interchangeable engineers, designers, analysts, and so on, with \(N\gg\tau\).
A coalition template is an integer vector \(a\in\mathbb Z_{\ge0}^{\tau}\setminus\{0\}\), where \(a_t\) is the number of type-\(t\) agents in the coalition. Let \(\mathcal K\) be the finite set of admissible templates, including every singleton template. The common coalitional power relation is a total preorder \(\succeq\) on \(\mathcal K\), represented by rational scores \(\phi(a)\), with \(a\succeq b\) iff \(\phi(a)\ge\phi(b)\). This is the type-level counterpart of the paper’s power relation over subsets.
A continuous coalition structure is a vector \(q=(q_a)_{a\in\mathcal K}\), where \(q_a\ge0\) is the mass of coalitions having template \(a\), satisfying
\[ \sum_{a\in\mathcal K}a_tq_a=\mu_t \qquad\text{for every }t\in T. \]
Thus agents are not fractionally assigned inside a team: \(q_a\) represents a continuum of repeated teams of the same composition. Agents of the same type are interchangeable, exactly as required by high multiplicity.
A template \(b\) blocks \(q\) if, for every type \(t\) with \(b_t>0\), there is positive mass of type-\(t\) agents currently belonging to strictly weaker coalitions:
\[ \sum_{a:\,b\succ a}a_tq_a>0. \]
Those agents can be selected in sufficiently small positive proportions to form a coalition of template \(b\), and every participant strictly improves because preferences depend only on coalition strength. The problem asks for a feasible \(q\) with no blocking template, or equivalently for a core-stable continuous coalition structure.
The direct continuous analogue of Algorithm 1 is:
\[
\varepsilon=\min_{t:a_t>0}\frac{\rho_t}{a_t},
\]
add \(\varepsilon\) to \(q_a\), and replace \(\rho\) by \(\rho-\varepsilon a\);
At least one type is exhausted at every iteration, so there are at most \(\tau\) iterations. The same earliest-intersection argument as in Theorem 3.2 shows that the resulting structure is core-stable: if a blocking template existed, consider the first greedy coalition from which its participants are drawn. The blocker was feasible at that step but strictly stronger, contradicting maximality.
With \(\mathcal K\) explicitly listed, this is a Class A problem: the greedy algorithm needs polynomially many rational operations and comparisons in \(\tau\), \(|\mathcal K|\), and the input bit length. If \(\mathcal K\) is exponentially large but given implicitly, the central subproblem becomes
\[ \max\{\phi(a):a\in\mathcal K,\ a\le\rho\}, \]
which is a genuine pricing problem. Additively separable or otherwise structured power scores may make it tractable; a compact but expressive power representation could instead produce a continuum-specific hardness boundary.
This is recognizable as the authors’ problem rather than a welfare variant. It preserves their common power relation, their strength-only hedonic preferences, their blocking-coalition notion, and their greedy strongest-coalition construction. The only changes are exactly the high-multiplicity ones: exchangeable types replace named agents, and repeated coalitions are represented by masses. For rational data, the dictionary is exact: clear denominators, create \(M\mu_t\) clones of type \(t\), and create \(Mq_a\) coalitions of each template \(a\). Conversely, every such finite coalition structure aggregates to a \(q\)-vector.
The weakest point is the role-template restriction. The paper permits an arbitrary power relation over all subsets of named players, whereas this mirror assumes that interchangeable agents can be represented by type-count templates and that the relation is invariant under exchanges within a type. That is a substantive regime choice, not a theorem about every instance of \(G_1\). It is nevertheless a plausible high-multiplicity scenario—repeated project teams, classes, or organizational units—and it is precisely the sort of scenario the programme asks us to find.
I would not claim that this covers Theorem 3.10 or Proposition 4.3. Their lex-cel and partition-dependent rankings require a non-canonical choice of how to measure the rank of agents in a continuum, and the finite \(n\ge7\) emptiness argument may disappear when positive mass can split across repeated coalition templates. Those are useful follow-up questions, but they should not be smuggled into the present mirror.
The proponent’s anchor is the paper’s only plausible computational one, but it does not support the claimed mirror.
Theorem 3.2 is an algorithmic characterization, not a complexity result. Its input is a complete quotient order over all \(2^n-1\) coalitions, and the paper gives no encoding, running-time bound, decision problem, or optimization problem. Thus the proposed polynomiality in \(\tau\) and explicitly listed \(\mathcal K\) is not a theorem about a paper-defined computational regime. It is polynomial only because the new model lists the entire template universe. If \(\mathcal K\) is implicit, the difficulty is entirely delegated to an unspecified representation of the arbitrary power relation \(\phi\).
More seriously, the proposed greedy algorithm is not well-defined dimensionally. The vector \(a\) records the integer number of agents in one coalition, whereas \(\rho_t\) is a population fraction. Comparing \(a_t\le \rho_t\) compares agents per coalition with mass. For example, take types \(A,B,U\), masses \(\mu_A=1/2\), \(\mu_B=1/4\), \(\mu_U=1/4\), and templates \(a=(1,0,1)\) and \(b=(3,1,0)\), with \(b\succ a\succ\) all singleton templates. The proposed test rejects \(b\) because \(3>1/2\), selects \(a\), and exhausts \(U\), leaving positive mass of \(A\) and \(B\). But a positive mass \(\varepsilon b\), with \(\varepsilon\le 1/12\), can then be formed; every participant prefers \(b\) to their current coalition. Hence the resulting structure is blocked.
The natural repair is to regard \(b\) as infinitesimally feasible whenever every type in its support has positive residual mass, and to consume the maximum scalar multiple \(\varepsilon b\). That repaired greedy rule may indeed produce one stable mass allocation. But it is no longer the paper’s Algorithm 1 in any direct sense. It replaces the paper’s finite coalition-removal operation by a support-elimination process over repeated team templates.
More importantly, the repair requires assumptions absent from the paper. The original power relation is an arbitrary ranking of named subsets. A distribution of agent types does not determine how two coalitions with the same type-count vector are ranked. To obtain \(\phi(a)\), one must impose exchangeability of agents within types and specify a new ranking over count vectors. One must also decide whether coalition sizes are bounded, whether rankings are invariant under scaling, and how an unbounded family of finite templates is represented. These choices define a new coalition-formation model; they are not consequences of continuization.
If coalition size is unbounded, the natural template space is infinite and a strongest feasible template need not exist. If size is bounded or \(\mathcal K\) is explicitly listed, the input has been changed into a finite template-packing instance. If \(\phi\) is compactly represented, any resulting hardness or tractability comes from that newly chosen representation of \(\phi\), not from the population becoming continuous. None of these variants is a computational question actually posed by the paper.
There is therefore no strong continuous-computational anchor here. The paper proves a structural theorem about a finite, fully specified coalition order; it does not identify a complexity phenomenon whose high-multiplicity relaxation can be charted. A type-symmetric repeated-team model can certainly be invented, and the honest negative case cannot prove that no researcher would find it useful. But the proposed mirror is either malformed, or becomes a different model whose essential data and computational content must be supplied from outside the paper. I would not green this paper as a worthwhile ChoCo continuization target.
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.