| paper | Stability in Online Coalition Formation |
| 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
statement extracted from the paper’s text layer
Given a finite type set \(T\), a strict rational interaction matrix \(v\) with \(v_{t,t}>0\), and an adversarial finite sequence of positive rational-mass cohorts whose total mass is one, construct a deterministic online policy that irrevocably assigns each arriving cohort to an existing or new coalition so that after every prefix the typed mass partition is Pareto-optimal, where \(U_t(K)=\sum_s v_{t,s}z_s(K)\) and domination means weak improvement almost everywhere and strict improvement on positive mass.
A finite-type additive hedonic mass model with cohort-assignment variables, dictator labels for coalitions, rational type masses, and the objective of maintaining Pareto optimality at every arrival prefix.
The guarantee is not established for arbitrary strict typed populations: atomless or individually interleaved arrivals can create zero-mass founders and singleton dust, while positive diagonal utilities and cohort arrivals restrict the original model.
fatal: False
Covers Theorem 3's Pareto-optimality guarantee, and consequently the PO basis of Corollary 1, under positive-mass typed cohorts; it leaves the other stability and impossibility results untouched.
I would lead with Theorem 3:
“There exists a deterministic online algorithm, which always outputs a PO partition for strict ASHGs.”
This theorem is proved in the paper, not merely cited. Its proof is constructive, through Algorithm 2. Corollary 1 is a direct consequence, but I would not count it as an independent anchor.
The mirror I would propose is PO-Online-ASHG\(_\infty\). There is a finite set \(T\) of agent types, with \(|T|=\tau\), and a rational interaction matrix \(v:T\times T\to\mathbb Q\setminus\{0\}\). A type is a complete utility profile: two agents of type \(t\) have identical utilities toward every type \(s\). The population is a unit mass, with \(\mu_t\) denoting the mass of type \(t\).
Agents arrive in an ordered stream of rational-mass cohorts. A cohort of mass \(a_r\) and type \(t_r\) arrives; the algorithm sees only the current population and current interaction information, and must irrevocably assign that mass to an existing coalition or create a new coalition. The mass of type \(s\) in a coalition \(K\) is \(z_s(K)\), and a type-\(t\) agent in \(K\) receives
\[ U_t(K)=\sum_{s\in T}v_{t,s}z_s(K). \]
This is exactly the normalized high-multiplicity version of additive utility: dividing a finite coalition utility by \(n\) does not change preference comparisons.
A feasible solution is an online assignment policy together with the resulting measurable partition of population mass. It is successful if, after every arrival prefix, the current partition is Pareto-optimal: there is no alternative partition that weakly improves almost every agent and strictly improves a positive-mass set. The objective is therefore not welfare maximization but maintaining Pareto optimality online and irrevocably.
The natural high-multiplicity regime is a company or research organization with, say, \(10^5\) workers but only 10–30 recurring compatibility profiles: software engineers, project managers, designers, researchers, and so on. Workers within a type share the same preferences toward the relevant worker types. This is close to the paper’s own motivating example of workers joining existing departments or teams. The arrival order remains essential and may be adversarial; only interchangeable copies are aggregated into mass. Thus this is not merely a static fractional partition problem.
The continuous policy is the mass version of Algorithm 2. Each coalition has a dictator type, namely the type of its first arriving cohort. Incoming mass of type \(t\) joins the earliest existing coalition whose dictator type \(d\) satisfies \(v_{d,t}>0\). If no such coalition exists, it starts a new coalition and \(t\) becomes its dictator. In the especially natural cohort regime where \(v_{t,t}>0\) for every type, there are at most \(\tau\) coalitions: once type \(t\) has founded a coalition, later type-\(t\) mass joins it.
The proof idea survives aggregation. The first coalition contains precisely the mass that its dictator likes and excludes the mass that it dislikes. Hence its dictator type is at its unique best coalition. Any Pareto improvement must preserve that coalition. Removing it leaves the same problem on the remaining mass, so induction fixes the coalitions one by one. With \(k\) arrival cohorts, the policy can be implemented in polynomial time—naively \(O(k\tau)\)—and its output is a compact list of coalition mass vectors. I would therefore expect this mirror to be Class A: tractable through the same structural serial-dictatorship insight, rather than through an LP.
This is plausibly the authors’ problem rather than a tractable caricature. The online restriction, irrevocability, additive hedonic utilities, strictness, and Pareto objective are all retained. What changes is only the population representation: many interchangeable workers are supplied as mass. The paper’s theorem is actually stronger than the mirror, since it permits arbitrary strict ASHGs and individually distinct agents; the mirror asks whether its constructive guarantee has a meaningful high-multiplicity form.
The weakest point is important. The finite proof relies on a named first agent acting as dictator. In a genuinely atomless population, an individual has measure zero, so a naive continuum limit can erase that witness and make the Pareto argument fail. My proposed regime avoids this by using positive-mass arrival cohorts, with same-type agents positively compatible, so each coalition has a positive-mass founding type rather than a vanishing singleton founder. If a referee insists on completely atomless arrival with no cohort or seed convention, this particular mirror needs further work. That is a real limitation, not a cosmetic one.
The further questions are valuable in their own right: can the \(v_{t,t}>0\) condition be removed while retaining a compact representation of singleton “dust” coalitions? What is the right continuum analogue of CIS or CNS, given that a single-agent veto has zero mass? And do the paper’s negative results, especially Theorem 5, survive when the adversarially chosen individuals are replaced by a fixed finite set of mass types? My case covers Theorem 3—and, conditionally, its PO-to-CIS consequence—but does not claim to mirror the paper’s entire collection of negative online results.
The proponent’s anchor is Theorem 3, and the proposed mirror does not actually preserve that theorem as stated. The finite proof relies on a named first agent whose strict utility identifies a uniquely best coalition. In a population continuum, that founder may have measure zero, so the proof’s Pareto witness disappears.
There is a concrete failure. Take two types \(a,b\), with symmetric utilities \(v_{aa}=v_{bb}=-1\) and \(v_{ab}=v_{ba}=1\). Let all \(a\)-mass arrive first and all \(b\)-mass second. Processing agents individually, the \(a\)-agents form singleton coalitions; the first \(b\)-mass joins the first \(a\)-coalition. In the continuum limit that coalition contains positive \(b\)-mass but zero \(a\)-mass. The remaining \(a\)-mass is singleton dust. Moving all mass into one coalition weakly improves every \(a\)-agent and strictly improves the \(b\)-agents, so the alleged output is not Pareto-optimal. The finite serial-dictator argument is not closed under this limit.
The proponent’s repair—requiring \(v_{tt}>0\) and allowing positive-mass cohorts to found coalitions—does all the substantive work. It excludes strict ASHGs with negative same-type interactions, and treating a cohort as an indivisible founding block changes the paper’s one-agent-at-a-time model. If instead arbitrary strict types are retained, one must represent atomless singleton dust, zero-mass dictators, or institutional seed labels. The first option requires a richer measurable-partition object; the latter two restore identity-level information rather than a pure population distribution. Corollary 1 inherits exactly the same obstruction.
The company example therefore does not rescue the general mirror: it is a new batched, self-compatible finite-type model in which the serial-dictatorship proof has been engineered to survive aggregation. That is a legitimate adjacent problem, but not a faithful continuous counterpart of Theorem 3.
This is nevertheless a weak negative case in the universal sense demanded here. A restricted positive-diagonal, cohort-arrival model is coherent and arguably worth studying. I can defeat the mirror as proposed and the full strict-ASHG limit, but I cannot honestly claim that every natural continuous mirror of Theorem 3 fails.
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.