d4-conf-sagt-2014-0018

The strongest positive case is a narrow mirror of Theorem 3.4, proved in this paper. It says that in proportional allocation games with independent draws of bidders’ concave, nondecreasing valuation functions, every pure Bayes–Nash equilibrium has expected social welfare at least half the expected optimum; equivalently, its price of anarchy is at least \(1/2\). The paper proves an equilibrium-efficiency bound, not a computational-complexity classification. So no result in it qualifies as a strict ChoCo anchor of the kind “in P” or “NP-hard.” Theorem 3.4 is the best named result to anchor a continuous analogue to.

A plausible high-multiplicity regime is a large resource market—say, a service with millions of users but a few dozen recurring demand curves. A type is a user’s complete valuation function \(v_t\); mass \(\mu_t\) is the fraction of users with that valuation. The number of users is much larger than the support size \(\tau\). To keep per-user allocations meaningful as the population grows, normalize resource supply per capita. That is a co-modification of the model, but the target remains the population: a distribution over user types competing through the same proportional-bid mechanism.

Here is a concrete continuous problem. Given rational masses \(\mu_t>0\), summing to one, and rational concave piecewise-linear valuation functions \(v_t\) on nonnegative per-capita allocations, find a pure equilibrium of the atomless proportional-bid market. Each user of type \(t\) bids \(b\); the aggregate bid intensity is \(B=\int b\,d\mu\), and the user’s allocation density is \(b/B\), so total resource use is \(\int (b/B)\,d\mu=1\). A type-symmetric pure equilibrium returns bids \(b_t\), with \(B=\sum_t\mu_t b_t>0\), such that for every type \(t\) and every alternative bid \(y\geq0\),
\[ v_t(b_t/B)-b_t \;\geq\; v_t(y/B)-y. \]
A single user has zero mass, so deviating does not change \(B\). The output is the bids and a certificate of these inequalities.

For the non-satiated, positive-shadow-price cases, this problem reduces to the concave allocation program
\[ \max_{x_t\geq0}\ \sum_t\mu_t v_t(x_t) \qquad\text{subject to}\qquad \sum_t\mu_t x_t=1. \]
Let \(p>0\) be its resource constraint’s shadow price and \(x_t^\star\) an optimum. Set \(b_t=p x_t^\star\); then \(B=p\). Optimality gives \(x_t^\star\in\arg\max_{q\geq0}\bigl(v_t(q)-pq\bigr)\), exactly the condition that makes \(b_t\) a best response. In fact, every pure atomless equilibrium satisfies this same optimality condition, so its welfare is optimal. With \(K\) valuation segments and input bit length \(L\), the piecewise-linear case is an LP of size polynomial in \(\tau,K,L\). This is a plausible Class A computational question: compute the continuous equilibrium, with price of anarchy \(1\).

That makes the mirror relevant to Theorem 3.4’s subject—equilibrium welfare in the same mechanism—and uses continuity of the population, not merely the already-divisible resource. It also generates useful follow-ups: how quickly does finite-population inefficiency disappear as the largest individual’s mass shrinks? What changes with budget constraints or correlated equilibria?

The soft spot is substantial: atomlessness removes each user’s strategic effect on the aggregate bid. The proposed limit therefore turns the finite-player \(1/2\) guarantee into efficiency, rather than preserving the theorem’s bound. The per-capita resource normalization also changes the model’s scaling. This is a defensible limit question, but it is not a continuation of the paper’s proof, and the paper supplies no computational-hardness result for it.