d4-conf-sigecom-2012-0032

The best anchor is Corollary 3.2, proved in this paper by extending the preceding argument. It says that in a sequential first-price auction where each round sells a set of items simultaneously and bidders are unit-demand, the mixed Bayes–Nash price of anarchy is at most \(2e/(e-1)\approx 3.16\). This is a welfare guarantee, not a runtime or hardness result; the paper has no named theorem about computing equilibria or classifying a problem as polynomial-time or NP-hard.

A continuous mirror I would put to the authors is Continuous Sequential Matching PoA. An instance has an ordered list of \(m\) item classes and a finite support \(T\) of valuation types. Type \(t\) has a complete unit-demand value vector \(v_t\in\mathbb{Q}_{\ge 0}^m\), and occupies mass \(\mu_t\in\mathbb{Q}_{>0}\), with \(\sum_t\mu_t=1\). Round \(j\) sells supply \(q_j\) of item class \(j\), where supply is measured as a fraction of the population. Remaining agents submit first-price bids; the highest bids receive the available mass, ties at the cutoff are split proportionally, and winners leave subsequent rounds. Each individual still receives at most one item; a type’s fractional allocation records what share of its mass receives each item. Strategies may depend on type and observed round history, and equilibrium means no infinitesimal agent can improve expected utility by changing their strategy.

The benchmark welfare is
\[ \operatorname{OPT}(\mu,q)= \max_{\alpha\ge 0}\sum_{t\in T}\sum_{j=1}^{m}v_{tj}\alpha_{tj} \quad\text{subject to}\quad \sum_j\alpha_{tj}\le\mu_t,\qquad \sum_t\alpha_{tj}\le q_j. \]
The question is whether every mixed Bayes–Nash equilibrium of this continuous auction has expected welfare at least \(\operatorname{OPT}(\mu,q)/(2e/(e-1))\), and, if not, what the worst-equilibrium ratio is. A solution is a proof of the bound for all such instances or a counterexample equilibrium; finding the exact supremum would sharpen the result.

The regime is a large matching market: many agents seek one service or slot, there are many copies of each slot class, and agents with the same full valuation vector are interchangeable. With \(n\) agents, the discrete approximants have about \(n\mu_t\) agents of type \(t\) and \(nq_j\) copies of item class \(j\). Thus \(n\) grows while the number \(\tau=|T|\) of distinct value vectors can remain small. Scaling supply with population is the necessary co-modification that keeps welfare per capita meaningful. This mirrors the paper’s matching-market welfare question rather than making the outcome space itself the continuous object.

I expect the positive result to survive, perhaps with a stronger bound: in an atomless population, one agent’s deviation does not change later aggregate histories, which may make the paper’s deviation argument easier to adapt. In the programme’s trichotomy, this is closest to Class A, though that label is imperfect here: the anchor concerns equilibrium welfare, not computational complexity. The mirror covers the matching-market guarantee only; it does not claim to continuize the matroid results or the paper’s equilibrium calculation in Theorem 2.1.

The weak point is substantial: atomlessness removes an individual’s ability to affect later information and play. That is part of what makes the sequential Bayesian game in the paper difficult, so the authors might regard this as a meaningful large-market limit but still a different auction model. The follow-up questions are whether every continuous equilibrium can be approximated by equilibria of the finite auctions, whether the bound remains valid with correlated types, and what the tight continuous price of anarchy is.