Mechanisms for multi-unit auctions

The strongest positive case is a Class A mirror of Proposition 4.3, with one important scope qualification: the mirror is of the welfare-allocation problem computed by the paper’s mechanisms, not a claim that ordinary individual-level VCG truthfulness survives unchanged in an atomless population.

My lead problem is the continuous high-multiplicity version of \(k\)-minded multi-unit welfare maximization. Consider a large procurement market with \(N\) small buyers and only \(\tau\ll N\) valuation types: for example, many hospitals, retailers, or computing customers using a small number of standardized demand templates. A type \(\theta\) is a complete \(k\)-minded valuation description, namely bids \((q_{\theta,j},p_{\theta,j})\), with \(v_\theta(q)=\max\{p_{\theta,j}:q_{\theta,j}\le q\}\). The society is a rational mass vector \(\mu\), where \(\mu_\theta\) is the fraction of buyers of type \(\theta\). The item supply must scale with population: the input gives a rational per-capita supply \(\rho\), corresponding to \(m=N\rho\) items in a finite realization.

The named anchor is Proposition 4.3, proved in this paper rather than cited. It states:

If \(A\) is a maximal-in-range algorithm for multi-unit auctions achieving an approximation ratio better than \(1-\frac1n\), then \(A\) cannot run in polynomial time unless \(P=NP\).

The proof uses the standard reduction from knapsack. A polynomial-time MIR algorithm would omit some complete allocation from its range; valuations can then be chosen so that the omitted allocation is uniquely optimal, while every allocation in the range loses a factor of at least \(1-\frac1n\). The proposition is the paper’s formal lower bound behind its claim that a fully polynomial-time truthful VCG-based approximation scheme is impossible.

The corresponding continuous problem, which I would call \(\mathrm{CMU}\text{-}\mathrm{Welfare}_\infty\), is:

Given \(\Theta\), rational masses \(\mu_\theta\), per-capita supply \(\rho\), and \(k\)-minded valuations \(v_\theta\), choose nonnegative masses \(x_{\theta,q}\), where \(x_{\theta,q}\) is the mass of type-\(\theta\) agents receiving the integral bundle \(q\), to maximize
\[ W(x)=\sum_{\theta\in\Theta}\sum_q x_{\theta,q}v_\theta(q) \]
subject to
\[ \sum_q x_{\theta,q}=\mu_\theta \quad\text{for every }\theta, \qquad \sum_{\theta,q}q\,x_{\theta,q}\le \rho. \]

It is enough to include \(q=0\) and the \(k\) demand quantities appearing in each type’s bids, since intermediate quantities do not improve a step valuation. A solution is the allocation-mass vector \(x\), either exactly optimal or within a specified multiplicative factor \(1-\varepsilon\) of the optimum.

This is recognisably the same problem: identical goods, monotone normalized \(k\)-minded valuations, a common supply constraint, and maximization of total welfare. The only population change is that many indistinguishable bidders are represented by mass. Crucially, \(q\) remains integral for every recipient: we are not giving one buyer a fractional bundle. We are splitting a continuous mass of identical buyers among different integral bundles.

The high-multiplicity dictionary is direct. If a finite auction has \(n_\theta\) bidders of type \(\theta\), then \(\mu_\theta=n_\theta/N\) and \(\rho=m/N\), where \(N=\sum_\theta n_\theta\). Any finite allocation induces \(x_{\theta,q}\) by dividing bundle counts by \(N\). Conversely, any rational \(x\) can be realized exactly after clearing denominators by taking sufficiently many clones. Thus the continuous problem is not merely a weighted restatement: it is the limit in which the indivisibility of individual bidders disappears while the indivisibility of each allocated bundle remains.

For this regime, I expect the problem to be in Class A. The displayed formulation is a linear program with \(O(\tau k)\) variables and rational coefficients, so exact optimization is polynomial in \(\tau\), \(k\), and the encoding length. The knapsack hardness in Proposition 4.3 disappears because its combinatorics are carried by individually distinct bidders. In the high-multiplicity regime those bidders become divisible masses of a small number of valuation types. The continuous feasible set is precisely the convexified allocation of integral bundles, not an artificial fractionalization of the goods.

This also gives the paper’s MIR discussion a meaningful continuous interpretation. The feasible mass-allocation set is fixed independently of the values \(p_{\theta,j}\), and the LP maximizes welfare over that fixed range. It is therefore the allocation oracle that a continuum MIR mechanism would need. The expected research questions are whether the exact LP solution admits a clean continuum VCG payment interpretation; how to round it back to a prescribed finite population \(N\) with a sharp additive welfare guarantee; what happens when \(\tau\) or \(k\) grows; and whether black-box access to the type valuations recreates a communication or query lower bound.

The mirror deliberately does not cover the paper’s full strategic claim. With atomless individuals, a single buyer has measure zero, so ordinary unilateral VCG externalities and dominant-strategy truthfulness require a separate cohort-level or positive-mass formulation. If the authors regard named-bidder incentives as essential rather than as a wrapper around welfare maximization, they may reject this as an extension rather than a direct mechanism mirror. That is the weakest point.

Nevertheless, the underlying optimization question is faithful and substantial. It covers the paper’s central \(k\)-minded multi-unit allocation problem and turns its named NP-hardness boundary into a precise continuization question: does the hardness of Proposition 4.3 survive when the population has finitely many repeated valuation types? In this natural regime, the best prediction is that it does not—the problem becomes an exact polynomial-time LP.