d4-conf-aaai-2012-0380

The strongest positive case is a population version of the paper’s linear bottleneck games, anchored on Theorem 5.2, proved here. The paper does not name a hardness result, so a constructive algorithmic result is the right anchor. The theorem says: for a linear bottleneck game \(G=(N,\omega,\mathcal T)\), take an optimal solution \(\widehat W\) to LP (4) and an optimal dual solution \(\widehat\gamma\) to LP (5). The coalition structure \(CS\) represented by \(\widehat W\), with payoffs \(x_j^i=\widehat\gamma_i\widehat W_j\) for \(i\in A_j\) and zero otherwise, is an imputation, and \((CS,x)\) belongs to the optimistic core. The construction immediately preceding the theorem says both LP solutions, and hence the outcome, can be computed efficiently. Thus the anchor is a constructive polynomial-time result, although Theorem 5.2’s printed statement is the stability guarantee rather than a complexity-class claim.

A credible high-multiplicity setting is a large platform coordinating interchangeable units of production or service capacity across recurring task templates. There may be millions of suppliers but only a few dozen complete types: a type records a supplier’s resource weight, task eligibility, and other features relevant to payoffs and deviations. Each task template \(j\) requires resource contributions from a fixed set \(A_j\) of types and earns value in proportion to its bottleneck contribution. This is a plausible regime for the paper’s combinatorial-optimization motivation: the number of agents is much larger than the number of distinct resource-and-eligibility profiles. The paper’s fractional resources do not themselves make its population continuous; the mirror here puts the population on a type space.

I would give a prover the following lead question, Continuous LBG Optimistic-Core Allocation. An instance is a finite type set \(T\), with \(|T|=\tau\), rational masses \(\mu_t\geq 0\) summing to \(1\), per-unit resource weights \(\omega_t\), and an explicit finite list of task templates \(j=1,\ldots,M\). Each task has a required type set \(A_j\subseteq T\) and a nonnegative value rate \(\pi_j\); as in the paper, require distinct task supports and a singleton task for each type. A unit of throughput \(W_j\) consumes \(W_j\) resource from every required type and produces value \(\pi_jW_j\). The task allocation is constrained by
\[ \sum_{j:t\in A_j}W_j\leq \mu_t\omega_t \qquad \text{for every }t\in T. \]
The question is to return a welfare-maximizing feasible \(W\), together with a payoff allocation in the optimistic core. A candidate allocation is supported by type prices \(\gamma_t\geq0\) satisfying
\[ \sum_{t\in A_j}\gamma_t\geq\pi_j \qquad \text{for every }j, \]
with the primal and dual objectives equal. Pay each type \(\gamma_t\) per unit of resource its members contribute, distributing that payment proportionally among contributing members. Stability means no measurable coalition—any chosen submass of each type—can profitably withdraw resources, create new task throughput, and satisfy the paper’s optimistic compensation rule for affected nondeviators.

I expect this problem to be tractable for an explicit task list: it is the same pair of rational LPs, now with type capacities \(\mu_t\omega_t\), and should take polynomial time in \(\tau\), \(M\), and the input bit length. The proof obligation is to show that the dual-price stability argument in Theorem 5.2 covers every mass-valued deviation. This is a proposed extension, not a result established in the paper. It preserves the underlying bottleneck production and optimistic stability question; it does not merely make outcomes fractional.

The soft spot is the co-modification of the task model. In the paper, a task’s participants are specific named players; here they are interchangeable members of required type classes, so a template can be carried out at population scale. That is natural for replicated suppliers and recurring tasks, but would not faithfully mirror a network where each vertex or edge has a unique role. I would limit the claim to Theorem 5.2 and this LBG setting, not extend it to the conservative- or refined-core results. Further questions are whether the dual-price proof handles all measurable deviations without extra assumptions, how the continuum solution corresponds to finite replications of the type masses, and what happens when the task family is succinct or exponentially large.