(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-