d4-conf-wine-2014-0031

My strongest case is a narrow mirror of Theorem 1: the paper proves here that computing Shapley values for knapsack budgeted games is NP-hard. In the discrete game, each agent has an integer length \(\ell_i\) and value \(w_i\), and for capacity \(B\), a coalition \(S\) is worth the maximum total value of a subset of \(S\) whose total length is at most \(B\). The proof uses Shapley efficiency: summing all agents’ shares gives \(v(N)\), the optimum knapsack value, so a polynomial-time Shapley computation would solve classical knapsack. [Theorem 1 in the paper](https://www.cs.cmu.edu/~arielpro/comsoc-14/papers/BhagatKimMuthukrishnanWeinsberg2014.pdf)

A plausible high-multiplicity setting is a very large staffing cooperative that assigns technicians to a deployment under a total-hours budget. A technician’s type is their standardized pair \((\ell_t,w_t)\): hours consumed and contribution value. A type’s mass \(\mu_t\) is its fraction of the available workforce. For instance, a pool might have hundreds of thousands of technicians but only dozens of standardized credential and contribution profiles. The deployment budget scales with the pool: if the population has size \(n\), the total capacity is \(nb\), for per-capita capacity \(b\). This is a property of the scenario, not a claim that every staffing pool has high multiplicity.

I would give the prover this problem, which I’ll call Continuum Knapsack Shapley Allocation. An instance consists of rational type masses \(\mu_t\geq 0\) summing to \(1\), integer lengths \(\ell_t\) and values \(w_t\), and a rational per-capita budget \(b\geq\max_t\ell_t\). For available population mass \(x\), define its value per population unit by
\[ V_b(x)=\max\left\{\sum_t w_t y_t:\ 0\leq y_t\leq x_t,\ \sum_t\ell_t y_t\leq b\right\}. \]
Here \(y_t\) is the selected mass of type \(t\). The question is to compute the exact per-agent allocation \(\sigma_t\) for every type, where
\[ \sigma_t=\int_0^1 D_tV_b(\alpha\mu)\,d\alpha, \qquad D_tV_b(x)=\lim_{\delta\downarrow0} \frac{V_b(x+\delta e_t)-V_b(x)}{\delta}. \]
The derivative is taken where it exists; the piecewise-linear value function has only finitely many breakpoints along the integration path. Type \(t\)’s total allocation is \(\mu_t\sigma_t\). This is a population-continuous problem: \(y_t\) is the selected mass within a type cohort, while each actual technician is still selected or not selected.

The Shapley connection is a replication-limit claim. For population size \(n\) with \(n\mu_t\) technicians of each type and capacity \(nb\), an individual’s position in a uniformly random ordering approaches a uniform \(\alpha\in[0,1]\); the preceding population approaches \(\alpha\mu\). The individual’s marginal contribution then approaches the derivative in the formula. Establishing that the finite Shapley shares converge to these \(\sigma_t\), including at ties, is part of the mirror’s formal work. The allocation is efficient in the continuum sense:
\[ \sum_t\mu_t\sigma_t=V_b(\mu), \]
by integrating the change in \(V_b(\alpha\mu)\) along the population path.

I expect this mirror to be Class A. Sort types by density \(w_t/\ell_t\). As \(\alpha\) increases, the marginal density in the fractional knapsack changes only at \(O(\tau)\) breakpoints, so each \(D_tV_b(\alpha\mu)\) is constant between breakpoints. The integral can therefore be computed exactly with polynomially many rational operations in the number of types \(\tau\) and input bit length. The further questions are whether the finite-population Shapley shares converge with a useful error bound, and how the answer changes when the budget remains fixed instead of scaling with population.

This case covers Theorem 1 only. Its weakest point is that Theorem 1’s knapsack reduction can use many distinct item types; it does not establish hardness in the regime \(n\gg\tau\). Also, an atomless population has no canonical ordinary Shapley value without a limiting convention. The proposed mirror makes that convention explicit through replicated finite games and per-capita capacity scaling. That is a substantial, recognizable continuation of the paper’s random-arrival fairness question, but the authors and a referee would need to accept the replication limit as the right continuous form.