(the “single parameter”). The numbers ωi and vi can be thought of as the quantity received and the value per-unit of a good, respectively. A single-item auction is the special case in which each ω is either a standard basis vector or the all-zero vector. Keyword search auctions are also single-parameter, under the assumptions that every advertiser cares only about the probability ωi of a click on its sponsored link and has a common value vi for every such click.

An algorithm for a single-parameter problem is monotone if a greater bid begets a greater allocation: increasing the value of a bid (keeping the other bids fixed) can only increase the corresponding value of the computed ωi. For example, the “highest bidder” allocation algorithm for a single-good auction is monotone, while the “ second-highest bidder” allocation algorithm is not. In general, monotonicity characterizes implementability for single-parameter problems.

Myerson’s Lemma. 27 An allocation algorithm for a single-parameter mechanism design problem is implementable if and only if it is monotone.

Myerson’s Lemma is a useful solu-
tion to the first goal (G1) and reduces
implementable algorithm design to
monotone algorithm design. For ex-
ample, consider the following “rank-by-
weighted bid” allocation algorithm for
a keyword search auction. Advertisers’
bids are sorted in decreasing order, pos-
sibly after scaling by advertiser-specific
relevance factors, and ad slots are popu-
lated in this order. Assuming that the
probability of a click is higher in higher
slots, every such algorithm is mono-
tone: increasing one’s bid can only in-
crease one’s position in the ordering,
which in turn leads to an only higher
probability of a click. Thus, Myerson’s
Lemma guarantees an analog of the sec-
ond-price rule that extends the alloca-
tion algorithm into a truthful auction.a
a Modern search engines use allocation algo-
rithms that are similar to rank-by-weighted
bid algorithms. By historical accident, they
use a slightly different pricing rule than that
advocated by Myerson’s Lemma, although
the two pricing rules lead to comparable out-
comes and revenue at equilibrium. For details,
see Lahaie et al. 30

truthful
mechanisms
are—by design—
strategically
degenerate in
that the best
course of action
of a participant
does not depend
on the actions
taken by others.

single-parameter scheduling problem proposed by Archer and Tardos1 had been the most natural candidate for differentiating between the optimization power of monotone and arbitrary polynomial-time algorithms, but Dhangwatnotai et al. 14 recently gave a (randomized) polynomial-time monotone algorithm for the problem with approximate guarantee as good as the best-possible polynomial-time algorithm (assuming P ≠ NP).

Multiparameter Mechanism Design. Many important mechanism design problems are not single-parameter. Combinatorial auctions, 11 in which each participant aims to acquire a heterogeneous set of goods and has unrelated values for different sets, are a practical and basic example. Combinatorial auctions are used in practice to sell wireless spectrum (where the goods are different licenses), with auction designs by theoretical economists generating billions of dollars of revenue over the past decade. 11 Their complexity stems from “complements,” meaning goods that are more useful when purchased in tandem (for example, spectrum licenses for small but adjacent regions); and “substitutes,” meaning goods that are partially redundant (for example, two different but functionally identical licenses for the same region). Each bidder in a combinatorial auction has, in principle, an exponential number of private parameters—one private value for each subset of goods.

Multiparameter mechanism design is complex and our current understanding of goals (G1) and (G2) is primitive for most problems of interest. There are natural optimization problems for which there is a provable gap between the best-possible worst-case approximation ratio of implementable and arbitrary polynomial-time deterministic algorithms. This fact was first proved by Lavi et al.; 23 more recently, Papadimitriou et al. 33 showed that this gap can be as large as a polynomial in the number of bidders. Because of its importance and abundance of open questions, multiparameter mechanism design has been a hotbed of activity over the past few years. See Roughgarden35 for a survey of the primary research threads, including upper and lower approximation bounds for polynomial-time welfare maximization for combinatorial auc-