d4-conf-aaai-2015-0392

The strongest case is the paper’s welfare-approximation result, not its auction-equilibrium bounds. Theorem 2.3, proved in this paper using the configuration LP and a rounding argument, says: if every agent has an \(\MOPH\)-\(k\) valuation, there is a polynomial-time algorithm, given demand oracles for the valuations, that returns an allocation whose welfare is within a factor \(k+1\) of optimal. This is a genuine algorithmic anchor. The paper has no named hardness theorem for welfare maximization, so I would not use its unnumbered hardness discussion as a second anchor.

A plausible high-multiplicity setting is a large advertising exchange. There are many advertisers but relatively few distinct campaign valuation profiles over a fixed menu of slot, time, and region categories. Advertisers with the same complete valuation function form one type; let \(\mu_t\) be the fraction of advertisers of type \(t\). To keep the market nondegenerate as the population grows, category \(j\) has \(q_j\) interchangeable impressions per advertiser, so a population of size \(N\) has \(Nq_j\) copies. This supply scaling is a co-modification, but it preserves the paper’s allocation question: which bundles should go to which valuation types to maximize welfare? An individual still receives an integral bundle; only the mass of a type may be divided among different bundles.

I would hand the following problem to a prover:

Continuous \(\MOPH\)-\(k\) Welfare Allocation. An instance consists of \(m\) item categories, a finite set \(T\) of \(\tau\) valuation types with binary-rational masses \(\mu_t\geq 0\) summing to \(1\), binary-rational per-capita supplies \(q_j\geq 0\), and a normalized monotone \(\MOPH\)-\(k\) valuation \(v_t:2^{[m]}\to\mathbb{Q}_{\geq 0}\) for each type, accessible through a demand oracle as in Theorem 2.3. Find an optimal mass allocation \(x_{t,S}\geq 0\), where \(x_{t,S}\) is the fraction of the whole population of type \(t\) assigned the integral bundle \(S\subseteq[m]\). Require \(\sum_{S\subseteq[m]}x_{t,S}=\mu_t\) for every type and \(\sum_{t\in T,\,S\ni j}x_{t,S}\leq q_j\) for every category \(j\), and maximize \(\sum_{t\in T,\,S\subseteq[m]}x_{t,S}v_t(S)\). The empty bundle allows some mass to receive nothing. A solution is an optimal value and a feasible allocation, which can be represented by its nonzero entries.

I expect this problem to be tractable (Class A) in the same demand-oracle model. It is a linear program with exponentially many bundle variables but only \(\tau+m\) type and supply constraints. Its dual pricing step asks, for each type, for a bundle maximizing \(v_t(S)-\sum_{j\in S}p_j\), precisely a demand query. Thus column generation or ellipsoid methods give a polynomial-time route in \(m,\tau\), and the rational input length \(L\), counting demand-oracle calls. The type masses are not fractional bundles: they describe how much population receives each whole bundle.

The finite-market bridge is direct. For replications \(N\) making \(N\mu_t\) and \(Nq_j\) integral, use \(N\mu_t\) advertisers of type \(t\) and \(Nq_j\) copies of category \(j\). Integer bundle counts, divided by \(N\), give feasible points of the continuous problem. The continuous optimum is the configuration-LP optimum per advertiser; Theorem 2.3’s \(k+1\)-approximation is the paper’s finite-market rounding result. Further questions include how the integer-to-continuous welfare gap behaves as \(N\) grows, and whether one can improve the finite-market guarantee using the optimal mass allocation.

This mirrors only Theorem 2.3’s welfare-maximization problem. It does not extend the paper’s price-of-anarchy results or its expressiveness results about the \(\MOPH\) hierarchy. The authors should recognize the underlying question: their algorithm already solves the configuration LP before rounding it. The mirror makes the population interpretation explicit and treats that mass allocation as a feasible outcome in its own right, rather than as a relaxation for named agents.

The weak point is that this is an algorithmic mirror, not a test of whether discrete hardness disappears: the paper supplies no named hardness anchor here. Its continuous problem is also close to reinterpreting the configuration LP the paper already uses. And the market relies on replicated item categories with per-capita supply; the paper’s original model has a fixed set of indivisible goods. The case stands if large markets with repeated inventory and a small number of complete valuation types are accepted as a sensible regime for the authors’ welfare problem.