d4-journals-jair-2006-0027

The strongest positive case is for a high-multiplicity version of the paper’s social-welfare resource-allocation problem. Picture a national delivery platform with hundreds of thousands of small, standardized depots and a few dozen recurring operating profiles. A type records the depot’s complete MDP and its resource requirements, capacity costs, and limits. Its mass is the fraction of depots with exactly that profile, so \(N\) can be much larger than the support size \(\tau\). The platform allocates non-consumable equipment once, before operations begin; each depot receives an integral bundle and then follows a policy for its own MDP. Inventory scales with the population, while welfare is measured per depot. This is close to the paper’s setting: agents interact through shared resources, and their transitions and rewards are independent after allocation.

Here is a precise continuous problem, Continuum MDP Bundle Welfare. The input is a finite type set \(T\), rational masses \(\mu_t\) summing to \(1\), each type’s resource-parameterized MDP and local capacity limits, and a per-capita stock \(\bar b_o\) for each resource \(o\). For each type \(t\), let \(W_t\) be its locally feasible integral resource bundles, and let \(V_t(w)\) be the maximum expected discounted reward that type can earn using bundle \(w\). Choose nonnegative masses \(y_{t,w}\), where \(y_{t,w}\) is the fraction of society made up of type \(t\) depots assigned bundle \(w\). Require
\[ \sum_{w\in W_t} y_{t,w}=\mu_t \quad\text{for every }t, \qquad \sum_{t\in T}\sum_{w\in W_t} y_{t,w}w_o\leq \bar b_o \quad\text{for every }o. \]
The decision question is whether such an assignment can achieve
\[ \sum_{t\in T}\sum_{w\in W_t} y_{t,w}V_t(w)\geq Y. \]
A solution gives the bundle masses and, for each used bundle, an MDP policy attaining its value. Bundles remain integral for every depot: only the fraction of a type receiving each bundle can be fractional. For a finite population of \(N\) depots, the dictionary is \(y_{t,w}=n_{t,w}/N\), with total inventory \(N\bar b_o\). Thus the model keeps the paper’s discrete per-agent choices while making the population the continuous object.

My anchor is Theorem 3, proved in this paper. It says that deciding whether a given finite MDP with resource and capacity constraints has a feasible policy whose expected total discounted reward from \(\alpha\) is at least a given rational \(Y\) is NP-complete. The paper proves membership using its result that a stationary deterministic policy suffices, and proves hardness by reduction from KNAPSACK. In that construction, choosing action \(a_i\) corresponds to taking item \(i\): its resource cost is the item’s cost and its discounted reward contribution is the item’s value.

The continuous problem contains that anchor exactly. Use one type with mass \(1\), the MDP from the KNAPSACK construction, the same local capacity bound, and one unit of each resource per depot in the per-capita stock. Global supply then does not bind, but each depot still faces the original local capacity constraint. Assigning all mass to a bundle reaches \(Y\) exactly when the original MDP has a feasible policy reaching \(Y\). Splitting the mass among bundles cannot change the answer: an average reward at least \(Y\) requires at least one feasible bundle whose value is at least \(Y\). So this is a hardness-transfers case, in the programme’s Class B sense. The combinatorics live in the actions and local capacity constraint, not in population size; the continuum does not erase them, even at \(\tau=1\).

The paper also gives a natural computational foothold for the broader problem. Its Section 4 formulates joint allocation and planning as an MILP with a binary decision for each agent-resource pair, instead of enumerating each agent’s resource bundles. In the continuous version, the welfare master problem is linear over bundle or policy masses, but those columns are exponential in the resource or action choices, and their values come from MDP planning. Theorem 3 is a warning that this pricing or valuation work need not be easy in general. That makes the mirror useful even without a tractability claim: it poses the same computational question in a high-multiplicity regime and invites sharper results in parameters such as \(\tau\), the number of resource types, and the capacity structure. The paper’s numbered hardness result is my only anchor; the MILP result supports the model but is not a separate numbered anchor.

This mirror covers the local policy-choice hardness in Theorem 3 and its role inside the paper’s welfare-maximizing allocation model. It does not claim to continuize the paper’s VCG payments, truthfulness analysis, distributed implementation, or privacy construction.

The weakest point is that Theorem 3 is a single-agent result; it does not itself establish anything about a large society. The population interpretation is a lift of that result, supported by the paper’s separate multiagent allocation model, rather than a population theorem the authors prove. I think the lift is still one the authors would recognize: repeated depots with complete shared MDP types, pooled supplies, and welfare-maximizing allocation preserve the paper’s central problem. But the positive case is strongest as a faithful high-multiplicity formulation with hardness intact, not as evidence that population continuization makes this particular problem easier.