d4-conf-aaai-2010-0044

My lead is Theorem 4 (printed as 【定理4】). Proved in this paper, it says that the decision version of DCOP-based Coalition Structure Generation is NP-complete: given a DCOP and a threshold, decide whether some partition of the agents into coalitions has social surplus at least that threshold. The proof reduces a constraint-optimization decision problem whose constraint values are nonnegative. In those instances the grand coalition is optimal, so the hardness already includes optimizing the actions inside one coalition; it is not just the cost of searching over partitions.

A natural high-multiplicity setting is a large emergency-response workforce drawn from a finite catalogue of standardized roles. A type \(t\) specifies the responder’s action set, per-capita action rewards, and pairwise coordination rewards with other roles and actions. These details are shared by everyone of that type. The mass \(\mu_t\) is the fraction of the workforce in that role, with \(\sum_t\mu_t=1\). The paper itself motivates its model with rescue teams; here the regime is a large reserve workforce with many responders but relatively few distinct role profiles, so \(N\gg\tau\). Each responder still chooses one discrete action. Fractions arise because the continuum contains mass of responders, not because an individual takes a fractional action.

Call the mirror Mean-field DCOP-CSG-\(\epsilon\). Its input is rational type masses \(\mu_t\), finite action sets \(D_t\), rational per-capita rewards \(r_t(d)\), a symmetric rational role-pair interaction table \(\psi_{tu}(d,e)\), and rational precision \(\epsilon>0\). The pair term is normalized by population size so welfare stays finite as the workforce grows. The task is to return a coalition structure and pure action assignment with welfare within \(\epsilon\) of the optimum.

Precisely, let \(\theta(x)\) be the type of person \(x\) in a unit-mass population, let \(a(x)\in D_{\theta(x)}\), and let \(\mathcal P\) partition the population into coalitions. If \(x\sim_{\mathcal P}y\) means they are in the same coalition, the welfare is
\[ W(\mathcal P,a)=\int_0^1 r_{\theta(x)}(a(x))\,dx +\frac12\int_0^1\int_0^1 \mathbf 1[x\sim_{\mathcal P}y]\, \psi_{\theta(x)\theta(y)}(a(x),a(y))\,dx\,dy. \]
A solution is a feasible partition and action assignment whose welfare is at least \(\mathrm{OPT}-\epsilon\). It can be represented by the action-mass vectors \(z^j_{td}\) for each positive-mass coalition \(j\), plus residual singleton mass \(z^0_{td}\), satisfying \(\sum_{j\ge0,d}z^j_{td}=\mu_t\). The quadratic interaction term applies within each positive-mass coalition; singleton mass still earns its unary reward. Finite rational representations can approximate the optimum by treating sufficiently small groups as singletons.

I expect hardness to transfer (Class B). The paper’s proof puts the hard combinatorics in the action assignments of a DCOP with nonnegative rewards, not in a requirement to distinguish a large population of individual agents. A plausible transfer is to make one continuum type of mass \(1/n\) for each variable in the reduction, scale the rational rewards to account for the mass normalization, and add strong pairwise same-action and same-coalition rewards within each type. Those rewards make each type’s mass act as one cohort; the nonnegative cross-type rewards make joining the grand coalition optimal. The remaining choice of one action per type recovers the original DCOP decision. This is a route to a reduction, not a hardness theorem for the mirror as stated.

The case is credible because the mirror still partitions agents into coalitions and values each coalition by the optimum of an internal, pairwise-interaction problem. It asks a computational question about a continuous population, rather than making outcomes or uncertainty continuous. It covers Theorem 4’s exact CSG hardness question only; it does not claim a continuous counterpart of the paper’s approximation guarantees.

The weak point is that this homogeneous-role mirror changes the interaction structure: a role-pair table describes standardized interactions across a population, whereas the paper allows an individual-level constraint graph. The hardness witness also has \(\tau\) growing with the input, and the cohesion terms make the transfer argument work. A referee might accept this as a meaningful high-multiplicity regime of the authors’ problem but reject it as a direct limit of their general DCOP model. That limits the scope of the claim; it does not remove the underlying question of whether DCOP-based coalition formation remains hard when its agents are role cohorts.

Natural next questions are whether bounded treewidth of the role interaction graph helps, whether splitting type mass changes the approximation guarantees, and whether hardness transfers without the added cohesion terms.