| paper | Bounding the Cost of Stability in Games over Interaction Networks |
| authors | R. Meir, Yair Zick, Edith Elkind, J. Rosenschein |
| venue | AAAI 2013 |
| filed under | coalition · wvg |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | unclear |
The paper's numbered contributions are structural bounds and tightness statements about \(\mathrm{RCoS}\), not computational theorems. Algorithm 1 is a constructive proof device that may be exponential, and the only hardness statement is imported from prior work, so bit (a) fails. The proposed typed mass model is statable, but positive homogeneity makes \(B_\infty\) dual to fractional coalition packing while a type graph does not preserve the individual network's treewidth.
fails bit a — no named computational result to mirror
Theorem 3 is a structural bound rather than a qualifying computational result, and the proposed homogeneous mass formulation collapses the finite packing-versus-covering gap.
fatal: True
The proposed mirror covers Theorems 3 and 5 as mass-level treewidth and pathwidth stability bounds and Theorem 4 as a repeated-type tightness question; it leaves Proposition 1, the computational behavior of Algorithm 1, the hypergraph extensions, and the least-core implications aside.
The strongest honest case is qualified: the paper has a genuinely natural continuous-population mirror, but it has no named computational-complexity theorem. Its contribution is structural and game-theoretic. Thus, under a strict ChoCo anchor rule, this is not a fully compliant computational case. The best available anchor is nevertheless substantial.
My lead anchor is Theorem 3, proved in this paper:
“For every game \(G=\langle N,v\rangle\) and every interaction network \(H\) over \(N\), it holds that \(\mathrm{RCoS}(G|H)\le \mathrm{tw}(H)+1\).”
Here \(G|H\) permits exactly the connected coalitions of \(H\), and \(\mathrm{RCoS}\) is the minimum total stable payoff divided by the value of an optimal coalition structure. The theorem applies to arbitrary nonnegative TU games, not merely simple or superadditive games. Its proof constructs a stable payoff vector whose total payment is at most \((\mathrm{tw}(H)+1)\mathrm{OPT}(G|H)\), using Theorem 2 for simple games and an induction that decomposes a general game into simple layers. It is proved here, not cited from elsewhere. However, it is not a polynomial-time theorem: Algorithm 1 can be exponential for non-monotone games.
The continuous mirror would be a Typed Continuous Treewidth Cost-of-Stability problem. Consider a large population with finitely many complete types \(T=\{1,\ldots,\tau\}\). A type specifies an agent’s coalition-value parameters, communication role, reservation value, and every other property relevant to the game. The population is described by rational masses \(\mu_t\), with \(\sum_t\mu_t=1\). Let \(K\) be a finite interaction graph on the types, and regard a coalition as feasible when the set of types carrying positive coalition mass is connected in \(K\).
A coalition is now a mass vector \(\nu\in[0,\mu]\). Its value is \(V(\nu)\), where \(V\) is a rational, positively homogeneous TU valuation: \(V(\lambda\nu)=\lambda V(\nu)\). A coalition structure is a collection \(\{\nu^j\}\) with \(\sum_j\nu^j=\mu\), each \(\nu^j\) having connected support. Define \(\mathrm{OPT}_\infty\) as the maximum of \(\sum_jV(\nu^j)\).
The action is to choose a nonnegative type-level payment vector \(p\in\mathbb{R}^{\tau}_{\ge0}\). It is stable if \(p\cdot\nu\ge V(\nu)\) for every feasible coalition mass vector \(\nu\le\mu\). The objective is to minimize the total payment \(p\cdot\mu\). Thus the precise problem is to compute
\[ B_\infty=\min\{p\cdot\mu:p\ge0,\ p\cdot\nu\ge V(\nu)\text{ for every feasible }\nu\le\mu\}, \]
or equivalently \(\mathrm{RCoS}_\infty=B_\infty/\mathrm{OPT}_\infty\), and to output an optimal stable payment vector \(p\). For a concrete finite encoding, \(V\) could be a rational piecewise-linear homogeneous valuation, for example \(V(\nu)=\sum_\ell w_\ell\min_{t\in F_\ell}\nu_t+\sum_t a_t\nu_t\).
This is a genuine high-multiplicity analogue. If \(\mu_t=n_t/q\), create \(n_t\) interchangeable agents of type \(t\), and define the finite coalition value by \(v_q(S)=qV(\nu(S))\). Type-level payments correspond to symmetric finite payments. Because agents of the same type are interchangeable, averaging any stable finite payoff vector over permutations within each type preserves stability and total payment. The continuous problem is therefore not object-space fractionalization: the coalition-value problem and communication constraints remain, while the population is represented by masses.
The expected continuous analogue of Theorem 3 is
\[ \mathrm{RCoS}_\infty\le \mathrm{tw}(K)+1. \]
For the broad succinct version, I would expect the exact optimization problem to be Class B: normalizing finite multiplicities gives an upward embedding, so combinatorial hardness in coalition composition and interaction structure can survive. The continuum removes only the irrelevant naming and counting of repeated agents. A restricted version with fixed \(\tau\), bounded treewidth, monotone \(V\), and an efficient separation oracle may instead be Class A, perhaps through dynamic programming or column-generation LP. The central computational question is whether one can solve the pricing problem \( \max_\nu\{V(\nu)-p\cdot\nu\}\) over connected coalition masses.
The paper’s Theorem 5 gives a natural extension, though I would not use it as a second main anchor because it is closely related. It states, again as a result proved here, that for every TU game and interaction network,
\[ \mathrm{RCoS}(G|H)\le \mathrm{pw}(H), \]
and that this bound is tight. The corresponding continuous question replaces \(\mathrm{tw}(K)+1\) by \(\mathrm{pw}(K)\) and asks whether the sharper path-decomposition guarantee survives under type masses. Theorem 4 also suggests a useful follow-up: does the Fano-plane construction proving tightness for every \(k\ge2\) remain tight after repeating each role type at arbitrarily high multiplicity?
The regime is plausible for large consortia, federated organizations, or infrastructure networks in which many agents occupy repeated communication and production roles. The meaningful population parameter is then the number of agents per role, while \(\tau\) and the interaction skeleton remain small. The authors should recognize the mirror because it preserves exactly their objects—TU coalition values, connected cooperation, stable payments, and treewidth—rather than replacing the problem with a different fractional allocation problem.
The weakest point is also decisive: Theorem 3 is not a complexity classification, and the paper explicitly emphasizes that its results are “purely game-theoretic rather than algorithmic.” The only hardness statement about computing RCoS at treewidth \(2\) is attributed to Greco et al. (2011b), not proved as a numbered result here. Therefore I would present this as a strong substantive continuous mirror, but not claim that the paper itself supplies a qualifying computational anchor under the strictest ChoCo standard.
The strongest negative point comes before modelling: this paper has no qualifying computational anchor. Theorem 3 and Theorem 5 are structural ratio bounds, and Theorem 4 is a tightness construction. Algorithm 1 is explicitly exponential for general non-monotone games. The paper’s remarks that computing RCoS remains hard at treewidth \(2\) are literature summaries, not results proved here. Indeed, the authors describe their contribution as “purely game-theoretic rather than algorithmic.” Under ChoCo’s rule, there is therefore no named computational theorem to continuize.
The proposed mirror also collapses in its most natural homogeneous form. Let \(\mathcal Z\) be the normalized connected type-mass vectors. Positive homogeneity gives \(V(\lambda z)=\lambda V(z)\). The proposed continuous optimum is then exactly the fractional packing problem
\[ \max \left\{\sum_j \lambda_j V(z^j): \sum_j \lambda_j z^j\le \mu,\ \lambda_j\ge 0,\ z^j\in\mathcal Z\right\}. \]
Its dual is
\[ \min\left\{p\cdot\mu: p\ge 0,\ p\cdot z\ge V(z)\ \text{for every }z\in\mathcal Z\right\}, \]
which is precisely the proposed \(B_\infty\). For the rational piecewise-linear valuations suggested by the proponent, ordinary finite-dimensional convex duality therefore gives
\[ B_\infty=\mathrm{OPT}_\infty \]
whenever the optimum is nonzero. Thus \(\mathrm{RCoS}_\infty=1\): the atomless coalition structure removes the integral packing-versus-covering gap that creates the finite cost of stability. The pricing problem may still be computationally interesting, but the paper’s central quantity has become a primal-dual identity, and the treewidth and pathwidth bounds are vacuous.
Avoiding that collapse requires abandoning the natural homogeneous high-multiplicity model: one must retain indivisible coalition blocks, fixed coalition costs, nonhomogeneous thresholds, or identity-level matching. Those may define worthwhile new cooperative-game problems, but they are not straightforward population continuizations of this paper’s RCoS theorem.
There is a second, independent fidelity problem. Treewidth and pathwidth belong to the individual interaction graph \(H\), whereas a type graph \(K\) does not determine a high-multiplicity lift of \(H\). If \(q\) copies of type \(A\) interact with \(q\) copies of type \(B\) through all cross-edges, the lift is \(K_{q,q}\), whose treewidth grows with \(q\), despite \(K\) having width \(1\). If only matched copies interact, the mass vector cannot record the matching. Treating \(K\) itself as the interaction network therefore changes the model rather than preserving the paper’s network parameter.
This defeats Theorem 3’s proposed mirror. The theorem’s proof pays individual separator vertices and charges those payments against disjoint winning coalitions. In a mass model, a type separator can be split among many coalitions, while type-level intersection need not mean intersection of actual agents. The proof’s finite combinatorial invariant is consequently absent.
Theorem 5 inherits exactly the same defects; it supplies neither an independent computational anchor nor a nontrivial continuous quantity. Theorem 4 is even less transferable. Its Fano-plane lower bound depends on named points and the fact that winning coalitions intersect as sets of individuals. After repeating point types, coalitions can use disjoint mass from the same type. Preserving the original incidence requires copy-level matching, which restores identity information and defeats the type-only model; collapsing incidence to types produces a new hypergraph game, whose homogeneous version again has \(\mathrm{RCoS}_\infty=1\).
The honest limitation is that one cannot prove that no specially designed nonhomogeneous typed cooperative game would be worth studying. But that would be a new computational project, not a continuous mirror of a computational result in this paper. On the programme’s stated standard, none of the three proposed anchors supports a green case.
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.