| paper | d4-conf-aaai-2007-0097 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: \(D\) exists for every admissible input; exact computation and deciding \(D\ge q\) are polynomial-time solvable for every fixed \(K\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational type masses \(\mu_t\), a fixed maximum team size \(K\), team-size densities \(\rho_g\), and values \(w_g(a)\) for teams with type-count vector \(a\), compute the limiting average total coalition value per agent over uniformly chosen partitions with those team-size densities.
A high-multiplicity coalition-formation model with types \(t\in T\), population mass \(\mu_t\), bounded-size teams, type-composition values \(w_g(a)\), and team densities \(\rho_g\); the objective is the expected total value per agent under a uniform partition.
Covers Theorem 1's configuration-average bound for bounded team sizes and type-based coalition values; leaves the anytime optimization algorithm, its pruning and runtime guarantees, and the empirical results without mirrors.
My positive case is narrow but genuine. This paper has no numbered theorem establishing a complexity class for coalition structure generation; its NP-completeness statement is background, and its headline speedups are empirical. The best named anchor is Theorem 1, proved in this paper’s appendix. For a fixed coalition-size configuration \(G\), it says that the average total value of all coalition structures with that configuration is the sum, over the coalition sizes in \(G\) (including repetitions), of the average value of a coalition of that size. The paper uses this identity to calculate lower bounds that help its algorithm prune the search space. Rahwan et al. (2007) had noted the identity, but this paper supplies the proof.
A plausible high-multiplicity regime is a large fleet of autonomous service agents repeatedly assembled into small teams. Agents with the same capabilities, resources, goals, and coalition values belong to the same type. The population is a distribution \(\mu\) over a small finite type set \(T\), with many agents per type. Coalition value depends on the types in the team, not on the names of its members. That is a recognizable instance of the paper’s coalition-formation problem, and treating the population as type masses is natural when the relevant question is how teams composed from the fleet perform on average.
The continuous problem I would hand to a prover is Typed Configuration-Average CSG. An instance consists of type masses \(\mu_t\geq 0\) summing to \(1\); a fixed maximum team size \(K\); nonnegative coalition values \(w_g(a)\), where \(a\in\mathbb Z_{\geq0}^{T}\) records the counts of each type in a size-\(g\) team; and rational coalition-count densities \(\rho_g\geq0\), with \(\sum_{g=1}^{K}g\rho_g=1\). Here \(\rho_g\) is the number of size-\(g\) teams per unit of population.
The question is: in the limit of large populations with type proportions tending to \(\mu\) and coalition-size counts per agent tending to \(\rho_g\), what is the average total coalition value per agent over uniformly chosen partitions with those coalition sizes? The answer, and hence a solution to the problem, is
\[ \sum_{g=1}^{K}\rho_g \sum_{\substack{a\in\mathbb Z_{\geq0}^{T}\\ \sum_t a_t=g}} \frac{g!}{\prod_{t\in T}a_t!} \left(\prod_{t\in T}\mu_t^{a_t}\right)w_g(a). \]
For fixed \(K\), this is exactly computable in time polynomial in the explicit coalition-value table and the bit length of the rational inputs. A finite coalition sampled from a large typed population has an asymptotically multinomial type composition; the formula takes that expected value for each team size and sums over the coalition-size densities. The average is also a lower bound on the best coalition structure in that configuration, just as the paper uses its discrete average to bound the optimum.
This mirrors Theorem 1, not the paper’s whole optimization problem. It is a tractable, Class A style result for a real computational subproblem in the paper’s algorithm. It does not show that maximizing coalition value over all partitions is tractable in the continuum, nor does it transfer the paper’s anytime runtime or empirical guarantees. Natural further questions are whether the finite-population correction gives useful bounds at moderate multiplicity, whether these average bounds help an anytime optimizer over typed societies, and what happens when coalition sizes grow with the population.
The weak point is that this mirror covers a bound-calculation step rather than optimal coalition structure generation itself. It also assumes bounded team sizes and explicit type-composition values; arbitrary identity-dependent values or macroscopic coalitions fall outside it. Those limits make the positive claim modest, but the underlying average-value question remains a credible continuous-population analogue of a named result the paper actually proves and computes with.
The negative case is that Theorem 1 is a weak anchor for a complexity programme. It proves an averaging identity for a fixed finite set of agents whose coalition values \(v(C)\) are explicitly supplied. The paper uses that identity to compute bounds inside an optimizer; it does not establish a complexity result for a separately formulated average-value problem. Its NP-completeness claim is background, and its headline runtime claims are empirical.
The proposed typed question is well defined, but its continuous formula is the limit of a finite calculation. With \(N_t\) agents of each type, a random size-\(g\) coalition has type composition \(a\) with probability \(\prod_t \binom{N_t}{a_t}/\binom{N}{g}\); as the type proportions converge, this tends to the stated multinomial probability. Given the table \(w_g(a)\), computing the mean is a table calculation. It does not address the hard step in the paper: finding the best partition or showing that these averages let an anytime optimizer prune effectively. The average remains a lower bound on the maximum, but that fact alone supplies no continuous counterpart to the paper’s optimization guarantees.
That criticism does not defeat the best nearby mirror. For a large fleet of interchangeable agents with bounded team size and value determined by team composition, one can let \(y_{g,a}\) be the density of teams of composition \(a\), then maximize \(\sum_{g,a} w_g(a)y_{g,a}\) subject to \(\sum_{g,a} a_t y_{g,a}=\mu_t\) for each type \(t\). This is a natural high-multiplicity coalition-formation model, and for fixed \(K\) it is a finite linear program. The paper’s arbitrary coalition values and unbounded coalition sizes do not specify this model, but the programme explicitly permits a plausible type-based regime and its natural co-modifications.
So the strongest honest case against is about the anchor’s limited value: its direct mirror is an asymptotic expected-value calculation, not a mirror of the paper’s central search problem. I cannot make the universal claim that no worthwhile continuous mirror exists. The typed coalition-density formulation is plausible enough that this negative case remains weak.
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.