d4-conf-ecai-2010-0069

The paper has no named theorem saying that finding a kernel\(^+\)-stable payoff is polynomial-time solvable or hard; its conclusion explicitly leaves the computational complexity open. The best named computational anchor for a positive mirror is Theorem 1 (Convergence), proved in this paper. It says that Algorithm 2’s sequence of side-payments converges to a payoff distribution in the kernel\(^+\): the agents’ strengths move toward equality, subject to the singleton-payoff floor. That is an algorithmic existence result, not a tractability result. The algorithm repeatedly evaluates strengths over coalitions, and the paper notes that this requires exponentially many coalition values in the finite model.

My lead is the Continuous Kernel\(^+\) Payoff Problem. Consider a large workforce or multiagent population whose members form coalitions to produce value. A type records everything relevant to coalition value and payoff: for example, the agent’s skills, costs, outside options, and bargaining parameters. Let \(T\) be the finite set of types, with mass distribution \(\mu\), where \(\mu_t\) is the fraction of the population of type \(t\). The intended regime has many agents and relatively few types: perhaps millions of agents drawn from tens or hundreds of recurring role profiles.

Let \(q\in[0,\mu]\) describe a coalition’s composition by type, and let \(V(q)\) be its worth. The instance includes the per-capita value \(W^\star\) of an optimal coalition structure, as in the paper’s two-stage setup: first select an optimal structure, then distribute its worth. Write \(a_t\) for a type-\(t\) agent’s singleton worth. A proposed payoff \(p_t\) is the payoff per unit of type-\(t\) mass. Define the normalized strength of type \(t\) as \(\sigma_t(p)=\sup_{q\in[0,\mu],\,q_t>0}\bigl(V(q)-\sum_s q_s p_s\bigr)\): the greatest excess among coalition compositions containing positive mass of that type.

The problem is: given \((T,\mu,V,W^\star,(a_t)_{t\in T})\) and a precision \(\epsilon>0\), find payoffs \(p_t\ge a_t\) such that \(\sum_t\mu_t p_t=W^\star\), and for every pair \(t,s\), both \(\sigma_t(p)+\epsilon\ge\sigma_s(p)\) or \(p_t=a_t\), and \(\sigma_s(p)+\epsilon\ge\sigma_t(p)\) or \(p_s=a_s\). In words, allocate the optimal structure’s value across the population so that types are in approximate global equilibrium, except where a type is already at its singleton floor. A solution is the payoff vector \(p\), with enough information to verify the budget balance and the strength comparisons. The feasibility condition is the objective: as in the paper, the task is to find a stable distribution, not maximize a second quantity.

This is a high-multiplicity version of the paper’s underlying payoff problem, not a change to fractional outcomes or to the stability criterion. Finite populations with \(n_t\) agents of each type give proportions \(\mu_t=n_t/n\); the coalition value and payoff sums can be normalized per population member. The continuous question asks whether the payoff guarantee from Theorem 1 survives in that limit and how to compute it. The type-composition strength is the limiting counterpart of the paper’s “best excess over coalitions containing this agent.” It also exposes the central computational issue: evaluating strengths means optimizing over coalition compositions, the continuous analogue of the paper’s exhaustive scan over coalitions.

For this stated problem, my tentative expectation is Class A when the type-composition strength problem has an efficient optimization method. The payment dynamics in Theorem 1 suggest a route: use a strength oracle to find imbalanced types, then transfer payoff while respecting singleton floors. With fixed or moderate \(\tau=|T|\), continuous optimization may make those strength calculations practical. That is a research conjecture, not a consequence of Theorem 1; the theorem gives no polynomial bound. For unrestricted value representations, pricing or equilibrium computation may instead be hard. There is no hardness result in this paper to support a Class B prediction.

The mirror covers the paper’s convergence result for computing a kernel\(^+\)-stable payoff, conditional on an optimal coalition structure. It does not claim to mirror coalition-structure generation, the externality extension, or Lemma 1’s inclusion of the core. Useful follow-up questions are whether a stable payoff always exists in the atomless model, whether an \(\epsilon\)-algorithm can be bounded in \(\tau\), input length, and \(1/\epsilon\), and how its guarantees relate to finite high-multiplicity instances.

My weakest point is the passage from individual agents to a continuum. Kernel\(^+\) compares named agents and permits them to have different payoffs, whereas the mirror assigns a common payoff to members of each type and defines strength through positive coalition mass. A single infinitesimal agent does not change a coalition’s mass profile, so this is a limiting version of the paper’s strength, not an identity already proved by it. The case survives as a credible question because it keeps the paper’s optimal-welfare target, coalition excesses, singleton floors, and cross-coalition transfers. It should be presented as a proposed high-multiplicity extension of Theorem 1, not as a result the authors have already established.