d4-conf-aaai-2015-0687

The strongest honest positive case is a continuous McQuillin value for an anonymous, high-multiplicity production game. An agent’s type records everything payoff-relevant: for example, production role, capacity, cost, and outside option. A society is a rational mass vector \(\mu\) over a fixed finite set \(K\) of such types. A large market might have thousands of small suppliers but only a handful of types; suppliers within a type are interchangeable. A coalition’s surplus can depend on its type composition and on the remaining suppliers forming a single rival coalition, so externalities remain part of the model.

My anchor is Theorem 2, proved in this paper. It says that if a value is additive and satisfies the Strong Null-Player Axiom, and can be computed in \(O(|N|)\) time on games in \(\Psi(N)\)—linear combinations of elementary games whose nonzero payoffs occur in one partition—then it can be computed in \(O(|N||T|)\) time on a game represented by a set \(T\) of Partition Decision Tree rules. The theorem further establishes that the externality-free, McQuillin, Macho-Stadler et al., and Myerson values all have this running time on PDT games. The proof uses path additivity and the ability to remove null players. The paper has no numbered computational hardness result to anchor on, so this algorithmic result is the strongest suitable anchor.

Here is the continuous problem I would hand to a prover. The instance consists of \(K\), a rational mass vector \(\mu\) with \(\sum_{j\in K}\mu_j=1\), and an explicitly represented rational polynomial \(f_\mu(x)\). For a coalition with type-mass vector \(x\), \(f_\mu(x)\) gives that coalition’s surplus when the complement forms one rival coalition; assume \(f_\mu(0)=0\). Compute the continuous McQuillin allocation: a payoff density \(a_j\) for each type \(j\), and hence total allocation \(A_j=\mu_j a_j\) to that type’s mass. A precise definition is the replica limit. For each admissible \(q\), create \(q\mu_j\) identical agents of type \(j\), and give a coalition \(S\) worth \(f_\mu(x(S))\), where \(x_j(S)=|S\cap N_j|/q\). If \(\phi_i^{(q)}\) is a clone’s finite McQuillin value, set

\[ a_j=\lim_{q\to\infty}q\,\phi_i^{(q)} =\int_0^1 \partial_j f_\mu(t\mu)\,dt, \qquad A_j=\mu_j a_j. \]

The solution is the exact type-allocation vector. For a sparse rational polynomial input, the displayed integral gives a direct exact algorithm, with running time polynomial in the polynomial representation, the number of types, and the bit lengths. The expected classification is Class A. It also satisfies efficiency: \(\sum_j A_j=f_\mu(\mu)\), by integrating the derivative of \(f_\mu(t\mu)\) along the population ray.

This retains the underlying question the authors study—how to allocate coalition surplus under externalities using the McQuillin extension. It does not treat fractional outcomes or random profiles as the continuization: population mass is the continuous object, and the allocation is the type-level limit of the finite value. The case is deliberately limited to McQuillin’s two-block slice, which is exactly the part of the game its formula reads. Natural further questions are whether the limit and an efficient computation extend to less smooth payoff functions, and whether analogous limits exist for values that depend on arbitrary partitions, such as Bolger, Myerson, or Hu–Yang.

The weak point is that this is not a continuous reformulation of the full PDT input class. PDT rules can distinguish named agents, and Theorem 2’s general algorithm benefits from removing null players; the proposed mirror instead uses anonymous type-mass payoff functions. So it does not transfer Theorem 2’s general algorithm into the continuum. Its claim is narrower: the McQuillin allocation problem remains recognizable and meaningful when many payoff-equivalent agents are represented by mass, and its replica limit is explicit.