| paper | Learning Coalition Structures with Games |
| authors | — |
| venue | AAAI 2024 |
| filed under | coalition · hedonic |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 3.2
statement extracted from the paper’s text layer
Given \(\tau\) rational-mass types with finite rational action and payoff descriptions, all copies of each type constrained to one unknown coalition block \(\Pi\), adaptively design factorized normal-form games and default type-action profiles, receive one bit indicating whether the profile is a Nash equilibrium under coalition aggregate payoff \(\sum_{t\in B}\mu_tu_t\), and recover \(\Pi\) with minimum worst-case queries.
Type-closed mass-weighted normal-form CSL with cohort types, an unknown partition of types, adaptive factorized game/profile queries, a one-bit coalition-level Nash-equilibrium oracle, and exact-recovery query complexity as objective.
The type-closed assumption restricts the paper’s arbitrary partition of named individuals to a partition of cohorts, while the mass distribution is largely bookkeeping for the query algorithm.
fatal: False
The mirror covers normal-form CSL, including Theorems 3.1 and 3.2 and the gadget lemmas; it leaves the congestion, graphical-game, auction, and experimental results untreated.
The strongest positive case is a continuous, high-multiplicity version of the paper’s normal-form CSL problem. I would not lead with the auction results: continuous auctions introduce distracting issues about maxima, ties, and allocation among a positive-mass population. The normal-form result is a much cleaner mirror.
My lead anchor is Theorem 3.2, proved in this paper: “IG solves the CSL problem with a sample complexity upper bounded by \(n\log_2 n+3n\).” It is supported by Lemma 3.1 and Lemma 3.2, also proved here, which establish the pairwise and product-game gadgets. Theorem 3.1, likewise proved here, supplies the matching information-theoretic lower bound; its Bell-number asymptotic is the only part relying on an external result, De Bruijn’s cited estimate.
Call the mirror Type-Closed Continuum Coalition Structure Learning. An instance contains:
Type \(t\) represents a mass \(\mu_t\) of agents with identical action sets and payoff parameters. The regime is explicitly type-closed: all agents of a given type belong to the same latent coalition. Thus the unknown object is the coalition structure of the repeated cohorts, not an arbitrary partition of indistinguishable individuals.
A query is a compactly represented normal-form game \(G\), together with a default type-level strategy profile \(a\). A coalition \(B\in\Pi\) evaluates a profile by its aggregate payoff
\[ U_B(a)=\sum_{t\in B}\mu_tu_t(a). \]
The one-bit observation is
\[ O_\Pi(G,a)=1 \]
if and only if \(a\) is a Nash equilibrium when each latent coalition may coordinate a joint deviation of all its types. The algorithm chooses successive games adaptively from previous bits and must output \(\Pi\), or equivalently the coalition masses \(\sum_{t\in B}\mu_t\). Its objective is to minimize the worst-case number of designed games.
This is a population-continuum problem in the relevant sense: the society is given by mass, coalition welfare is an integral over the population, and the complexity should depend on \(\tau\), not on the number \(N\) of repeated agents. A discrete high-multiplicity instance with \(n_t\) copies of type \(t\) maps directly to \(\mu_t=n_t/N\).
The paper’s gadget lifts essentially verbatim. For types \(x\) and \(y\), give them the Prisoner’s-Dilemma actions from Definition 3.2, but scale the per-agent payoffs of type \(x\) by \(1/\mu_x\) and those of type \(y\) by \(1/\mu_y\). Hence the aggregate payoff of the two type cohorts is exactly the \(2\times2\) table used in the paper. If \(x\) and \(y\) are in different coalitions, neither coalition benefits from deviating at the default profile \((D_x,D_y)\). If they are in the same coalition, jointly choosing \((C_x,C_y)\) raises aggregate payoff from \(2\) to \(6\). Therefore the continuum query has precisely the conclusion of Lemma 3.1.
Products of these pair gadgets are represented factor-wise, rather than by explicitly listing an exponentially large payoff table. By the same reasoning as Lemma 3.2, one bit tells whether every tested pair lies in different coalitions. Iterative Grouping can therefore run over types rather than named agents, giving
\[ \tau\log_2\tau+3\tau \]
queries. Conversely, there are \(B_\tau\) possible partitions of the type set, so every one-bit algorithm needs at least \(\lceil\log_2 B_\tau\rceil\) queries. This reproduces the paper’s Theorem 3.1/Theorem 3.2 landscape with \(\tau\) replacing \(n\). With rational masses, the inverse-mass payoff scaling has polynomial encoding length; one may also restrict to masses bounded below by \(1/\operatorname{poly}(\tau)\).
A plausible regime is a platform with millions of repeated agents but only tens or hundreds of economically distinct cohorts: for example, ride-hailing drivers grouped by city zone, shift, vehicle class, and compensation schedule, or bidder accounts grouped by valuation and bidding-role profile. The hidden coalitions could be fleet units, operating teams, or bidding syndicates that coordinate entire cohorts. The platform can design incentive games and observe whether a prescribed behaviour is stable, but does not know which cohorts share a coordination channel. Here \(N\) may be \(10^6\) while \(\tau\) is \(50\)–\(500\). Asking for the number of experiments needed to identify the latent coordination structure is a natural high-multiplicity question, not merely fractionalizing an auction outcome.
I would expect this mirror to be Class A: tractable. The paper already supplies the structural insight and the algorithmic template. The continuous version makes the population compression explicit and turns the dependence on the number of agents into dependence on the number of distinct cohorts. The lower bound remains meaningful because the algorithm is learning a partition of type mass, not estimating a continuous parameter.
The main weakness is real: this is a type-closed, block-continuum model, not an arbitrary measurable coalition relation over individuals. It also assumes the paper’s unusually strong observation oracle—exact Nash-equilibrium testing—and permits designed payoffs scaled according to cohort mass. If the intended mirror requires coalitions to split identical types, bounded incentives, noisy observations, or purely auction-based interventions, this particular construction no longer suffices.
That weakness does not destroy the positive case under the programme’s standard. The question is whether there exists a sensible high-multiplicity regime, not whether every individual-level version admits a continuum limit. This one preserves the paper’s central object—the unknown coalition partition learned through deliberately designed games—while replacing repeated agents by mass-bearing types. Further work would ask whether the same result survives bounded payoffs, noisy or bounded-rational observations, type-splitting coalitions, and the congestion, graphical-game, or auction settings.
The strongest negative case is that the proposed mirror does not preserve the paper’s unknown object. In the paper, the target is an arbitrary partition of named agents. In a high-multiplicity population, however, identical copies of a type could belong to different coalitions. Then \(\mu_t\) and the visible payoff parameters do not determine coalition behaviour. The latent object must record how each type’s mass is split across coalitions—effectively variables \(\mu_{t,B}\), or a measurable equivalence relation on the underlying population. Exact recovery of that object is not a finite \(\tau\)-type learning problem: mass observations cannot distinguish rearrangements of individuals within a type.
The proposed “type-closed” restriction avoids this only by stipulating that every copy of type \(t\) belongs to the same coalition. That turns the target into a partition of \(\tau\) cohorts, not the coalition structure studied in the paper. The resulting algorithm is simply Theorem 3.2 with \(n\) renamed \(\tau\), while the masses are largely decorative: the pair-testing and binary-search procedure does not use \(\mu\) at all. It is a finite weighted-agent reformulation, rather than a population-level computational question. If the output is only the multiset of coalition masses, the situation is even less faithful: partitions such as \(\{\{1\},\{2,3\}\}\) and \(\{\{2\},\{1,3\}\}\) have identical coalition masses but are different coalition structures, so the Bell-number lower bound no longer applies.
Attempts to repair this expose the same dilemma. If coalition membership is included in the type, then the types already encode the unknown relation and may be as numerous as the original agents. If it is allowed to vary within a type, the finite type-level mirror disappears. If one instead interprets a type as an organizational cohort whose members necessarily coordinate, that is a plausible new cohort-collusion problem—but it is no longer a genuine continuization of arbitrary CSL.
There is no serious objection based on the payoff scaling itself: the Prisoner’s-Dilemma gadget can in fact work with bounded, unscaled payoffs, since the coalition’s gain is positive for every pair of positive masses. Nor can one object merely that the theorem transfers unchanged; that would be an impermissible “continuization does not help” argument.
Consequently, this is not an airtight negative case. The cohort interpretation is sufficiently plausible that Theorem 3.2 remains a viable high-multiplicity mirror under the programme’s permissive standard. The defensible criticism is narrower: the proponent has shown a block-structured, type-level variant, not that the paper’s identity-sensitive coalition-learning problem has a genuine continuum analogue. That weakens the claimed mirror substantially, but does not support the universal conclusion that no worthwhile scenario exists.
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.