| paper | Anytime Coalition Structure Generation with Worst Case Guarantees |
| authors | T. Sandholm, K. Larson, Martin Andersson, O. Shehory, F. Tohmé |
| venue | AAAI 1998 |
| filed under | coalition · hedonic |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Let \(B\) be the maximum revealed welfare among queried partitions. The smallest certifiable factor is \(Cm/B\) if \(B>0\), and \(+\infty\) if \(B=0\). It is computable in polynomial time in the full input length. No finite \(q\) guarantees a finite certificate uniformly over \(\mathcal V_C\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given finite types \(T\), mass vector \(\mu\), and an oracle-accessible class \(\mathcal V_L\) of nonnegative typed coalition-value functions \(v:D_\mu\to\mathbb R_{\ge0}\), where \(D_\mu=\{x\in\mathbb R_{\ge0}^{\tau}:x\le\mu\}\), \(v(0)=0\), and \(v(x)\le L\lVert x\rVert_1\), a query is a finite partition \(X=(x^1,\ldots,x^r)\) with \(\sum_jx^j=\mu\) revealing \(v(x^j)\). After \(q\) queries, determine the smallest \(K\) for which an output \(\widehat X\) can certify \(\max_Y V_{v'}(Y)\le K V_{v'}(\widehat X)\) for every \(v'\in\mathcal V_L\) consistent with the transcript.
A high-multiplicity coalition game over type-mass vectors \(x\), with finite partitions of \(\mu\) as feasible coalition structures, welfare \(V(X)=\sum_jv(x^j)\), per-capita scaling to prevent fragmentation pathologies, and value-query access used to certify a worst-case approximation ratio.
The exact oracle formulation lacks an ordinary finite-input bit-complexity model until the admissible value-function class and representation are fixed; a finite explicit formula could also change the information structure.
fatal: False
The mirror covers Theorem 3’s worst-case certification lower bound, while leaving Theorems 1, 2, 4, and 5 and the distributed incentive mechanism untreated.
The strongest honest mirror is a continuous version of the paper’s worst-case certification problem, rather than of its distributed incentive mechanism.
Consider a large pool of interchangeable temporary workers forming project teams. There are \(n\) workers but only \(\tau\) skill types, with \(\tau\ll n\). A type includes every feature relevant to coalition value: skills, prices, availability, and coordination costs. The society is described by a mass vector \(\mu\in\mathbb{R}_{\ge 0}^{\tau}\), with \(\sum_t\mu_t=1\).
A coalition is represented by its type-mass vector \(x\), where \(0\le x_t\le\mu_t\). Its value \(v(x)\ge0\) is the revenue from the team minus coordination and setup costs. A coalition structure is a finite list \(X=(x^1,\ldots,x^r)\) satisfying \(\sum_jx^j=\mu\), and its welfare is
\[ V(X)=\sum_{j=1}^r v(x^j). \]
This is a genuine high-multiplicity model: individual workers remain assigned integrally to one team, but in the continuum limit the set of workers assigned to each team has a mass. Coalitions can be non-superadditive because coordination overhead, communication costs, or anti-trust constraints can make splitting preferable to merging.
My lead anchor is Theorem 3, proved in this paper. It states that no search algorithm other than the one searching the bottom two levels of the coalition-structure graph can establish a finite worst-case ratio bound while searching only \(2^a-1\) coalition structures or fewer. The reason is that every coalition value \(v_S\) must be observed. The bottom node exposes the grand coalition, while the second level exposes every other subset. Omitting a second-level structure containing coalitions \(P\) and \(Q\) requires more than one replacement structure to observe both values. Consequently, \(2^a-1\) is the minimum number of structures needed to establish any bound in general characteristic-function games, and the bottom-two-level search is uniquely minimal.
The corresponding continuous problem is:
Continuous Worst-Case Coalition Search \(\mathrm{CWCS}_\infty\). Given a finite type set \(T\), mass vector \(\mu\), a nonnegative characteristic function \(v(x)\) over coalition-mass vectors, a query budget \(q\), and a target ratio \(K\), determine whether one can query at most \(q\) continuous coalition structures and return a queried structure \(\widehat X\) together with a valid certificate
\[ \max_X V_{v'}(X)\le K\,V_{v'}(\widehat X) \]
for every nonnegative characteristic function \(v'\) agreeing with all observed coalition values.
A query reveals \(v(x^j)\) for every coalition \(x^j\) in the queried structure, giving the search procedure at least as much information as the paper’s analysis uses. The objective is to minimize the certifiable \(K\), or, in the threshold version, decide whether \(K\) is achievable with \(q\) queries.
This is recognizably the authors’ problem: the feasible objects are still coalition structures, the objective is still the sum of coalition values, and the computational resource is still partial search through an enormous structure space. Only the population has been continuized, with subsets replaced by measurable masses.
In the unrestricted exact-query model, I expect \(\mathrm{CWCS}_\infty\) to be Class C: continuum-specifically impossible to certify with finitely many queries. The obstruction is stronger than the paper’s \(2^a-1\) lower bound. Even with one type, write \(\mu=1\). Any finite collection of queried structures contains only finitely many coalition masses. Choose \(r\in(0,1)\) so that neither \(r\) nor \(1-r\) appears in those structures. One can then define a nonnegative continuous piecewise-linear value function consisting of a tiny baseline plus arbitrarily large bumps near \(r\) and \(1-r\). It agrees with the baseline on every queried coalition, but the unqueried partition \((r,1-r)\) has arbitrarily large welfare. Thus no finite query transcript certifies any finite universal ratio.
This is not a claim that the paper’s discrete theorem literally survives homogeneous replication. In a finite replicated game, symmetry may collapse many named coalitions into the same mass profile. Rather, the point is that the paper’s underlying search question has a natural high-multiplicity counterpart, and its behavior changes sharply when coalition mass becomes divisible. The discrete “observe every subset” argument becomes an uncountable coverage problem.
That negative result would generate the more structured questions that make the mirror computationally useful: does a known Lipschitz bound on \(v\) yield an \(\varepsilon\)-approximate certificate via a finite covering; what is the query complexity when \(v\) is rational piecewise-linear; and do concavity, superadditivity, or a configuration-LP representation restore tractability? Those are precisely the kinds of continuous-optimization boundaries the programme seeks.
The weakest point is the value-oracle formulation. It is faithful to the paper’s own search model, where coalition values are learned by evaluating searched structures, but it is not yet a standard finite-input complexity problem. If a succinct formula for \(v\) is given to the algorithm, it may reveal the hidden bumps without searching their locations. The mirror therefore needs an explicit representation theorem—probably Lipschitz, piecewise-linear, or separation-oracle based—to support ordinary complexity claims. Even with that qualification, the continuous population mirror itself is strong: it preserves the coalition-formation problem and exposes a genuinely new, continuum-specific boundary in the paper’s central worst-case-guarantee question.
The anchor is Theorem 3, but its lower bound depends on exactly what continuization removes: independently valued, labelled subsets of agents.
In the paper, \(v_S\) is an arbitrary characteristic function. The proof works because, after omitting a second-level structure \(\{P,Q\}\), the values \(v_P\) and \(v_Q\) remain unrelated to every value already observed. A genuine high-multiplicity model cannot retain that independence when \(\tau\ll a\). Coalitions with the same type-mass vector must have the same value. With one type, for example, the entire game has the form \(v_S=g(|S|)\), not an arbitrary set function on \(2^A\). With \(\tau\) fixed, the finite high-multiplicity analogue has values indexed by type-count vectors, of which there are only \(\prod_t(N_t+1)\), rather than \(2^a\) independently unknown subset values. To preserve the paper’s arbitrary \(v_S\), one must make every agent its own type; then there is no meaningful high-multiplicity regime.
The proposed \(\mathrm{CWCS}_\infty\) avoids this problem only by making \(v\) an arbitrary real function of coalition mass. That is not an ordinary finite-input computational problem. The bump argument proves a generic no-free-lunch theorem for an infinite-dimensional value oracle: finitely many exact evaluations cannot certify an arbitrary unqueried continuous function. The same argument would apply to almost any continuous resource-allocation problem, even one with no coalitions. It is therefore not a continuum analogue of the paper’s finite search lower bound, but an artefact of withholding the representation of the objective.
If \(v\) is given by a finite description—say a rational piecewise-linear formula, a separation oracle, or a production function—then the hidden bumps are no longer unconstrained. Their breakpoints, slopes, bounds, or regularity assumptions become part of the input, and the question becomes one of optimizing that structured function. The paper’s premise that every coalition value must be observed has disappeared. If \(v\) remains an unrestricted oracle, the problem has no standard bit-complexity or input-size model. Thus the proposed mirror has a dilemma: arbitrary values preserve the oracle impossibility but yield no meaningful computational problem; finite representations yield a legitimate problem but not Theorem 3’s lower bound.
There is also a more basic continuum pathology. In the finite game every coalition structure has at most \(a\) nonempty coalitions, which is essential to the bound \(V(CS^\ast)\le a\max_S v_S\). A mass partition has no corresponding upper bound: the population can be split into arbitrarily many positive-mass coalitions. If coalition values contain a fixed positive setup component, welfare becomes unbounded under fragmentation. If one imposes \(v(x)=O(\lVert x\rVert)\), a minimum coalition mass, or an explicit bound on the number of coalitions, that is a substantial new modelling axiom and removes the combinatorial argument on which Theorem 3 rests.
The strongest rescue would be to impose per-capita scaling and a structured typed production function, then study something like
\[ \max_{\lambda\ge 0} \int v(x)\,d\lambda(x) \quad\text{subject to}\quad \int x\,d\lambda(x)=\mu . \]
That could be an interesting configuration or column-generation problem. But its central issue would be pricing and representation of typed coalition configurations, not partial search for an unknown characteristic function and certification by observing every coalition. It would be a new continuous coalition-optimization model, not a worthwhile mirror of this paper’s named result.
So the proponent has not supplied a computational continuous mirror of Theorem 3: the faithful version is an ill-posed oracle problem, while the well-posed versions lose the theorem’s defining information structure. The negative case is weaker against the broader possibility of inventing a useful typed coalition-formation model from scratch; the paper itself simply does not provide a sound anchor for one.
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.