| paper | A characterization of absorbing sets in coalition formation games |
| authors | Agustín G. Bonifacio, E. Inarra, P. Neme |
| venue | GEB 2024 |
| filed under | coalition · hedonic |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | unclear |
Theorem 1 and Proposition 2 are named structural results, but neither asserts that an object is computable or that computing it is hard. The proposed continuous template model is coherent, but it adds substantial modelling choices around anonymous types, template incidence, and partial dissolution. Because bit (a) fails for every raised anchor, the grade is red.
fails bit a — no named computational result to mirror
The decisive objection is that neither anchor is computational under the gate, while the proposed mass/template dynamics are additional modelling choices not specified by the paper.
fatal: True
The proposed mirror covers Theorem 1 through absorbing-set and reduced-form recognition and Proposition 2 through stability reachability; it leaves the other structural results and bargaining and rationing applications without a computational mirror.
The strongest honest positive case is qualified: the paper admits a natural continuous-population analogue, but it contains no named complexity result. No theorem here proves membership in \(\mathrm{P}\), NP-hardness, \(\mathrm{FPT}\), or any other computational classification. Thus, under the programme’s strict anchor rule, this is not a fully compliant computational mirror. The best available case anchors on the paper’s structural results.
The lead anchor is Theorem 1, proved in this paper in Appendix B: “For each coalition formation game, each absorbing set generates a reduced form and, conversely, each reduced form generates an absorbing set.” This is a genuine characterization theorem, not a citation. A useful secondary anchor is Proposition 2, also proved here: a stable coalition formation game exhibits convergence to stability if and only if none of its reduced forms contains a generalized ring.
A plausible high-multiplicity regime is a large network of repeated local teams, project groups, or organizational units. There are many agents occupying a small number of recurring roles; agents of the same type have the same preferences over permissible coalition compositions, the same eligibility constraints, and the same outside option. The number of agents can be very large while the number of types and coalition templates remains moderate. This is not a claim that every coalition game is naturally high-multiplicity. It is a particular regime in which the authors’ preference-over-coalitions model is economically recognizable.
I would define the continuous population as follows. Let \(T\) be a finite set of agent types and let \(\mu\in\mathbb Q_+^T\) be the population-mass vector. Let \(\mathcal K=\{\mathbf k^1,\ldots,\mathbf k^q\}\) be a finite menu of permissible coalition templates, where \(\mathbf k^a_t\) is the number of type-\(t\) roles in one copy of template \(a\). Each type has a strict preference order over the templates containing it and an outside option \(\bot\). A continuous coalition structure is \((y,\rho)\), where \(y_a\ge 0\) is the mass of coalitions of template \(a\), and \(\rho_t\ge0\) is the mass of type \(t\) agents currently alone, satisfying \(\sum_a \mathbf k^a_t y_a+\rho_t=\mu_t\) for every \(t\).
A positive-mass deviation forms \(\delta>0\) copies of a target template \(a\). It may remove \(d_b\) mass of existing coalitions of template \(b\), and \(x_{t,b}\) mass of type \(t\) from those coalitions, together with \(x_{t,\bot}\) mass of singleton type-\(t\) agents, subject to \(\sum_b x_{t,b}+x_{t,\bot}=\delta\mathbf k^a_t\). Whenever \(x_{t,b}>0\), type \(t\) must strictly prefer \(a\) to \(b\); whenever \(x_{t,\bot}>0\), it must prefer \(a\) to \(\bot\). Every partially raided old coalition is dissolved, and its non-participating members become singletons, exactly as in the paper’s \(\gamma\)-model. This defines the continuous domination relation \(\gg_\infty\), its transitive closure, and continuous stability.
The corresponding problem is:
Continuous Reduced-Form Recognition \(\mathrm{CRFR}_\infty\). Given \(T,\mu,\mathcal K\), the type preferences, and a rational polyhedral candidate region \(A\) of continuous coalition structures, decide whether \(A\) is an absorbing set under \(\gg_\infty\). If it is, output a finite reduced form consisting of positive-mass generalized rings, fixed coalition templates, and residual singleton types, together with a protection certificate showing that the reduced form generates exactly \(A\).
Here a positive-mass generalized ring is a finite cyclic collection of templates for which a common positive mass can successively move around the cycle through strictly profitable deviations. Overlapping cycles are merged as in the paper. A fixed component is a template whose mass is present in every structure in \(A\). Protection and maximality are defined by quantifying over all feasible positive-mass deviations that break a component. This is a direct population version of the paper’s generalized rings, fixed components, singleton set, and protection conditions.
I would expect \(\mathrm{CRFR}_\infty\) to be tractable in the explicit bounded-template regime: candidate deviations are described by linear feasibility constraints, and the relevant cyclicity and protection tests should reduce to finite graph search plus LP separation. With unrestricted coalition templates, the problem may instead become hard through template-incidence or packing structure. Any such hardness would concern coalition composition, not the number of named agents, so it would be a Class B or Class C boundary question rather than a simple multiplicity obstruction.
The second mirror is:
Continuous Convergence to Stability \(\mathrm{CTS}_\infty\). Given the same finite-type mass game, with the promise that at least one continuous stable structure exists, decide whether every non-stable continuous coalition structure can reach a stable one through a finite sequence of positive-mass profitable deviations. If the answer is negative, return a positive-mass generalized ring and a non-stable structure from which no stable structure is reachable.
This is the direct continuum counterpart of Proposition 2. The expected characterization is that \(\mathrm{CTS}_\infty\) holds exactly when no continuous reduced form contains a positive-mass generalized ring. It should be tractable for explicitly listed bounded menus, while the unrestricted version could expose a genuine boundary caused by coalition-template interactions.
The high-multiplicity bridge is credible: rational \(\mu\), \(y\), and \(\rho\) can be scaled to a finite population by clearing denominators, while large repeated populations approximate arbitrary rational mass structures. Importantly, the individual coalition remains an integral role template; only the mass of identical coalition copies is divisible. Thus this is population continuization, not outcome-space fractionalization.
The weakest point is that the original paper’s coalitions are subsets of named agents, so overlap is identity-sensitive. A distribution over types alone does not determine which agents can belong to the same coalition. The template menu and explicit raid rule repair that ambiguity, but they are a genuine co-modification of the model. A referee could reasonably say that the resulting theory is a new continuous coalition-formation model rather than a literal limit of the paper.
So the positive case is real but modest: Theorem 1 and Proposition 2 support a plausible continuous mass-transfer programme, especially for repeated local teams. But because neither result is computational, the paper cannot honestly be presented as supplying a qualifying \(\mathrm{P}\)/hardness anchor.
The strongest negative case is decisive at the programme’s gate: this paper contains no named computational result. Theorem 1 is a structural bijection between absorbing sets and reduced forms; Proposition 2 is a structural characterization of convergence to stability. Neither states a complexity bound, an algorithm, a hardness result, an approximation guarantee, or a parameterized classification. Thus \(\mathrm{CRFR}_\infty\) and \(\mathrm{CTS}_\infty\) would be newly invented computational problems, not continuous mirrors of computational results proved by the paper.
Theorem 1 also does not survive as a natural population object without replacing the paper’s central structure. Its primitives are named-agent coalitions \(C\subseteq N\), arbitrary incidence in \(\mathcal K\), and partitions of those exact coalitions. Generalized rings, maximal sets, breaking, and protection all depend on which individual agents overlap. A type distribution \(\mu\) does not record that incidence.
The proposed template repair adds precisely the missing model: permissible role-multisets, exchangeability, coalition-copy masses, and a rule for partially raiding and dissolving old coalitions. That may define a coherent new anonymous coalition-formation model, but it is not determined by the paper. If one retains identity-sensitive eligibility, those identities must enter the types or an additional group structure, and the type space grows with the population. If one removes them, one has restricted the paper to an all-to-all anonymous template economy. Either way, the original theorem is no longer the anchor.
There is also a substantive granularity change. In the paper, a coalition is atomic: if a deviation intersects it, the coalition is dissolved and its remaining members become singletons. In the continuum, a deviation can remove an arbitrarily small fraction of the mass of a coalition template. Then a “fixed component” is no longer an atomic coalition present in every structure, and the protection conditions change qualitatively. Forcing an entire positive mass of copies to dissolve restores atomicity only by imposing a new rule that is absent from the paper.
Proposition 2 has an independent problem. Its proof relies on the finiteness of the coalition-structure graph: every non-stable state reaches an absorbing set, and cyclic behavior is captured by finite cycles. With arbitrarily small positive-mass deviations, the continuous state space has no such property. There may be infinite improving sequences approaching a stable boundary without reaching it, or support changes whose limit is not represented by a finite generalized ring. To recover the proposition one must either impose a minimum deviation mass, which reintroduces a discrete scale, or allow limit/closure convergence, which creates a new analytic dynamical system. Neither is a minor restatement.
The proposed polyhedral candidate \(A\) does not solve this: the paper’s absorbing set is a transitive-closure object, while continuous transitive closures can involve infinitely many supports and need not themselves be a single rational polyhedron. Recognition of a specially supplied polyhedral \(A\) could certainly be studied, but that would be a new problem whose computational content is not supplied by Proposition 2.
So every anchor raised by the proponent fails as a qualifying ChoCo anchor. The honest qualification is that an anonymous repeated-role coalition model could be worthwhile in its own right. But that would be a new continuous coalition-formation theory motivated by the paper, not a continuous computational mirror of this paper’s results. The universal claim that no conceivable scenario could be worthwhile is not provable; the strong defensible verdict is narrower: this paper offers no named computational result and no sufficiently canonical population continuization to justify spending the programme’s effort on it.
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.