CS364A: Algorithmic Game Theory
Lecture #4: Algorithmic Mechanism Design∗
Tim Roughgarden†
October 2, 20131

Knapsack Auctions

Next we design DSIC mechanisms for knapsack auctions. These will be single-parameter
environments, so Myerson’s Lemma will apply.

1.1

Problem Definition

In a knapsack auction, each bidder i has a publicly known size wi (e.g., the duration of a
TV ad) and a private valuation (e.g., a company’s willingness-to-pay for its ad being shown
during the Super Bowl). The seller has a capacity W (e.g., the length of aPcommercial break).
The feasible set X is defined as the 0-1 n-vectors (x1 , . . . , xn ) such that ni=1 wi xi ≤ W . (Asusual, xi = 1 indicates that i is a winning bidder.) Other situations such knapsack auctions
model include bidders who want files stored on a shared server, data streams sent througha shared communication channel, or processes to be executed on a shared supercomputer.
(When there is a shared resource with limited capacity, you have a Knapsack problem.)
Note that k-item auctions (k identical copies of a good, one per customer) is the special casewhere wi = 1 for all i and W = k. Here, different bidders can have different sizes.
Let’s try to design an awesome auction using our two-step design paradigm. Recall that
we first assume without justification that bids equal values and then decide on our allocation
rule. Then we pay the piper and devise a payment rule that extends the allocation rule toa DSIC mechanism.
∗ c2013, Tim Roughgarden. These lecture notes are provided for personal use only. See my book Twenty
Lectures on Algorithmic Game Theory, published by Cambridge University Press, for the latest version.
†
Department of Computer Science, Stanford University, 462 Gates Building, 353 Serra Mall, Stanford,
CA 94305. Email: tim@cs.stanford.edu.

1

1.2

A Surplus-Maximizing DSIC Mechanism

Since awesome auctions are supposed to maximize surplus, the answer to the first step isclear: define the allocation rule byx(b) = arg max
XnX

bi x i .

(1)

i=1

That is, the allocation rule solves an instance of the Knapsack problem1 in which the item
(i.e., bidder) values are the given bids b1 , . . . , bn , and the item sizes are the a priori known
sizes w1 , . . . , wn . By definition, when bidders bid truthfully, this allocation rule maximizes
the social surplus.

1.3

Critical Bids

Myerson’s Lemma (parts (a) and (b)) guarantees the existence of a payment rule p such thatthe mechanism (x, p) is DSIC. This payment rule is easy to understand. Fix a bidder i andbids b−i by the other bidders. Since the allocation rule is monotone and 0-1, the allocation
curve xi (·, b−i ) is extremely simple: it is 0 until some breakpoint z, at which point it jumps
to 1 (Figure 1). Recall the payment formulapi (bi , b−i ) =`Xzj · jump in xi (·, b−i ) at zj ,

(2)

j=1

where z1 , . . . , z` are the breakpoints of the allocation function xi (·, b−i ) in the range [0, bi ]Thus, if i bids less than z, it loses and pays 0. If i bids more than z, it pays z · (1 − 0) = z.
That is, i pays its critical bid — the lowest bid it could make and continue to win (holding
the other bids b−i fixed). Note this is exactly what’s going on in the Vickrey auction.

1.4

Intractability of Surplus Maximization

The mechanism proposed in Section 1.2 maximizes social surplus, assuming truthful bids
— an assumption justified by its DSIC property. The mechanism thus solves the surplusmaximization problem with unknown data (the vi ’s) as well as if this data was known apriori. But is the mechanism awesome in the sense of the Vickrey auction (Lecture 2)?
Recall this means:(1) DSIC.
(2) Surplus-maximizing, assuming truthful bids.
1
An instance of the Knapsack problem is defined by 2n + 1 numbers: item values v1 , . . . , vn , item sizes
w1 , . . . , wn , and a knapsack capacity W . The goal is to compute the subset of items of maximum total valuethat has total size at most W . See any undergraduate textbook for more details.

2

x(z)
1

0

z

Figure 1: A monotone 0-1 allocation rule.
(3) Runs in polynomial time.
The answer is no. The reason is that the Knapsack problem is NP-hard. Thus, there isno polynomial-time implementation of the allocation rule in (1), unless P = N P . Thus,
properties (2) and (3) are incompatible.
The fact that there is no awesome knapsack auction (assuming P 6= N P ) motivates
relaxing at least one of the above three goals. But which one? First, note that relaxing theDSIC condition will not help at all, since it is the second two properties that conflict.
A perfectly valid approach, which won’t get much airtime in this course, is to relax thethird constraint. This is particularly attractive for knapsack auctions, since the allocation
rule (1) can be implemented in pseudopolynomial time using dynamic programming (again,
see any undergraduate algorithms textbook for details). More generally, if your instances are
small or structured enough and you have enough time and computing power to implement
optimal surplus-maximization, by all means do so — the resulting allocation rule is monotoneand can be extended to a DSIC mechanism.2

2

Algorithmic Mechanism Design

2.1

The Holy Grail: DSIC For Free

Algorithmic mechanism design is one of the initial and most well-studied branches of algorithmic game theory, and we won’t have time to do it justice. The dominant paradigm inalgorithmic mechanism design is to relax the second constraint (optimal surplus) as little
as possible, subject to the first (DSIC) and third (polynomial-time) constraints. For singleparameter environments, Myerson’s Lemma implies that the following goal is equivalent:
design a polynomial-time and monotone allocation rule that comes as close as possible tomaximizing the social surplus.
Be warned, though, that the payments also need to be computed, which generally requires solving n
more surplus-maximization problems (one per player). See also Exercise 16.
23One of the reasons there has been so much progress in algorithmic mechanism design overthe past 15 years is that, on a technical level, it bears a strong resemblance to the relatively
mature field of approximation algorithms. The primary goal in approximation algorithms is todesign algorithms for NP-hard problems that are as close to optimal as possible, subject to apolynomial-time constraint. Algorithmic mechanism design (for single-parameter problems)
has exactly the same goal, except the algorithms must additionally obey a monotonicity
constraint. Myerson’s Lemma implies that algorithmic mechanism design boils down toalgorithm design in an oddly restricted (via monotonicity) “computational model” — theentire game-theoretic aspect of the design goal is neatly compiled into a relatively intuitive
extra constraint on the allocation rule.
It should be clear what the “holy grail” in algorithmic mechanism design is: for as many
NP-hard problems of interest as possible, to match the best-known approximation guaranteefor (not necessarily monotone) approximate surplus maximization algorithms — or even thebest-possible approximation guarantee, subject to P 6= N P . That is, we would like the
DSIC/monotone constraint to cause no additional surplus loss, beyond the loss we alreadyhave to suffer due to the polynomial-time constraint. Recall that we’ve been spoiled so far:with exact surplus-maximization, the DSIC/monotone constraint is satisfied “for free”, andexact surplus-maximization with unknown data reduces to exact surplus-maximization withknown data. Does an analogous reduction hold for approximate surplus maximization?

2.2

Knapsack Auctions (Reprise)

To explore the question above in a concrete setting, let’s return to knapsack auctions. There
are a number of heuristics for the knapsack problem that have good worst-case performanceG
guarantees. For example, consider the following allocation
P rule x , which given bids bchooses a feasible set — a set S of winners with total size i∈S wi at most the capacity W— via a simple greedy algorithm. We assume, without loss of generality, that wi ≤ W forevery i (it is harmless to delete bidders i with wi > W ).
(1) Sort and re-index the bidders so that3
b2
bn
b1
≥
≥ ··· ≥.
w1
w2
wn
(2) Pick winners in this order until one doesn’t fit, and then halt.4(3) Return either the step-2 solution, or the highest bidder, whichever creates more surplus.5
What makes a bidder attractive is a high bid and a small size. We trade these off by ordering bidders
by “bang-per-buck” — the value contributed per unit of capacity used.
4
One can also continue to follow the sorted order, packing any further bidders that happen to fit — thiswill only do better.
5
The reason for this step is that the solution in step 2 might be highly suboptimal if there a very valuable
and very large bidder. One can also sort the bidders in nondecreasing bid order and pack them greedily —this will only do better.
3

4

The above greedy algorithm is a 21 -approximation algorithm for the Knapsack problem,
which gives the following guarantee.
Theorem 2.1 Assuming truthful bids, the surplus of the greedy allocation rule is at least
50% of the maximum-posible surplus.
Proof: (Sketch.) Consider truthful bids v1 , . . . , vn , known sizes w1 , . . . , wn , and a capacity
W . Suppose, as a thought experiment, we relax the problem so that a bidder can be chosen
fractionally, with its value pro-rated accordingly. For example, if 70% of a bidder withvalue 10 is chosen, then it contributes 7 to the surplus. Here is a greedy algorithm for this“fractional knapsack problem”: sort the bidders as in step (1) above, and pick winners in thisorder until the entire capacity is fully used (picking the final winner fractionally, as needed).
A straightforward exchange argument proves that this algorithm maximizes the surplus over
all feasible solutions to the fractional knapsack problem.
Suppose in the optimal fractional solution, the first k bidders in the sorted order win
and the (k + 1)th bidder fractionally wins. The surplus achieved by steps (1) and (2) in thegreedy allocation rule is exactly the total value of the first k bidders. The surplus achievedin step (3) in the greedy allocation rule is at least the total value of the (k + 1)th bidder. The
better of these two solutions is at least half of the surplus of the optimal fractional solution,
which is at least the surplus of an optimal (non-fractional) solution to the original problem.
The greedy allocation rule is even better under additional assumptions. For example, if
wi ≤ αW for every bidder i, with α ∈ (0, 21 ], then the approximation guarantee improves to1 − α, even if the third step of the algorithm is omitted.
We know that surplus-maximization yields a monotone allocation rule; what about approximate surplus-maximization? At least for the greedy allocation rule above, we still havemonotonicity (Exercise 18).
You may have been lulled into complacency, thinking that every reasonable allocation
rule is monotone. The only non-monotone rule we’ve seen in the “second-highest bidderwins” rule for single-item auctions, which we don’t care about anyways. Warning: natural
allocation rules are not always monotone. For example, for every  > 0, there is a (1 − )approximation algorithm for the Knapsack problem that runs in time polynomial in the input
and 1 — a “fully polynomial-time approximation scheme (FPTAS)”. The rule induced by
the standard implementation of this algorithm is not monotone, although it can be tweaked
to restore monotonicity without degrading the approximation guarantee (see the Problems
for details). This is characteristic of work in algorithmic mechanism design: consider an NPhard optimization problem, check if the state-of-the-art approximation algorithm directly
leads to a DSIC mechanism and, if not, tweak it or design a new approximation algorithm
that does, hopefully without degrading the approximation guarantee.

5

2.3

Black-Box Reductions

Algorithmic mechanism design has been extremely successful for the single-parameter problems we’ve been discussing so far. The state-of-the-art approximation algorithms for suchproblems are generally either monotone or can redesigned to be monotone, like in the caseof knapsack auctions mentioned above and in the problems. This success has been so
widespread as to suggest the question:
Is there a natural single-parameter problem for which the best approximation guarantee
achievable by a polynomial-time algorithm is strictly better than the best approximation guarantee achievable by a polynomial-time and monotone algorithm?
Of course, a negative answer would be especially exciting — it would imply that, as with exact
surplus-maximization, the monotonicity/DSIC constraint can always be added “for free”.
One way of proving such a sweeping positive result would be via a “black-box reduction”: ageneric way of taking a possibly non-monotone polynomial-time algorithm and transmuting it
into a monotone polynomial-time algorithm without degrading the approximation guarantee.
Such a reduction would be very interesting even if the approximation factor suffered by aconstant factor.
Recent work by Chawla et al. [1] shows that there is no fully general black-box reductionof the above type for single-parameter environments. There might well be large and important subclasses of such environments, though, for which a black-box reduction exists. For
example, does such a reduction apply to all downward-closed environments where, like in allof our examples so far, giving a bidder less stuff cannot render an outcome infeasible?63

The Revelation Principle

3.1

The DSIC Condition, Revisited

To this point, our mechanism design theory has studied only DSIC mechanisms. We reiteratethat there are good reasons to strive for a DSIC guarantee. First, it is easy for a participant
to figure out what to do in a DSIC mechanism: just play the obvious dominant strategy.
Second, the designer can predict the mechanism’s outcome assuming only that participants
play their dominant strategies, a relatively weak behavioral assumption. Nevertheless, nonDSIC mechanisms like first-price auctions can also be useful in practice.
Can non-DSIC mechanisms accomplish things that DSIC mechanisms cannot? To answer
this question, let’s tease apart two separate assumptions that are conflated in our DSIC
definition:(1) Every participant in the mechanism has a dominant strategy, no matter what its private
valuation is.
If the DSIC constraint is weakened to an implementation in Bayes-Nash equilibrium, then there arequite general black-box reductions. We’ll discuss these in more advanced lectures.
66

(2) This dominant strategy is direct revelation, where the participant truthfully reports allof its private information to the mechanism.
There are mechanisms that satisfy (1) but not (2). To give a silly example, imagine a singleitem auction in which the seller, given bids b, runs a Vickrey auction on the bids 2b. Everybidder’s dominant strategy is then to bid half its value.

3.2

Beyond Dominant-Strategy Equilibria

Suppose we relax condition (1). The drawback is that we then need stronger assumptions topredict the behavior of participants and the mechanism’s outcome; for example, we might
consider a Bayes-Nash equilibrium with respect to a common prior (see Problem 6 on firstprice auctions) or a Nash equilibrium in a full-information model (see Problem 3 on the GSP
sponsored search auction). But if we’re willing to make such assumptions, can we do better
than with DSIC mechanisms?
The answer is “sometimes, yes.” For this reason, and because non-DSIC mechanisms
are common in practice, it is important to develop mechanism design theory beyond DSIC
mechanisms. We’ll do this in more advanced lectures. A very rough rule of thumb is that,for sufficiently simple problems like those in our introductory lectures, DSIC mechanisms
can do anything non-DSIC mechanisms can. In more complex problems, like some discussed
in the advanced lectures, weakening the DSIC constraint (e.g., to implementation in BayesNash equilibrium) often allows you accomplish things that are provably impossible for DSIC
mechanisms (assuming participants figure out and coordinate on the desired equilibrium).
DSIC and non-DSIC mechanisms are incomparable in such settings — the former enjoystronger incentive guarantees, the latter better performance guarantees. Which of these ismore important will depend on the details of the application.

3.3

The Revelation Principle and the Irrelevance of Truthfulness

The Revelation Principle states that, given requirement (1) in Section 3.1, there is no needto relax requirement (2): it comes “for free.”
Theorem 3.1 (Revelation Principle) For every mechanism M in which every participant has a dominant strategy (no matter what its private information), there is an equivalentdirect-revelation DSIC mechanism M 0 .
Proof: The proof uses a simulation argument; see Figure 2. By assumption, for every
participant i and private information vi that i might have, i has a dominant strategy si (vi )in the given mechanism M .
Construct the following mechanism M 0 , to which participants delegate the responsibilityof playing the appropriate dominant strategy. Precisely, (direct-revelation) mechanism M 0
accepts sealed bids b1 , . . . , bn from the players. It submits the bids s1 (b1 ), . . . , sn (bn ) to themechanism M , and chooses the same outcome (e.g., winners of an auction and selling prices)that M does.
7

v1	
  
v2	
  
.	
  
.	
  
.	
  
.	
  
.	
  
.	
  
.	
  

s1(v1)	
  M’	
  s2(v2)	
  
.	
  
.	
  
.	
  
.	
  
.	
  

M	
  

outcome	  (same)	
  outcome	  sn(vn)	
  vn	
  Figure 2: Proof of the Revelation Principle. Construction of the direct-revelation mechanism
M 0 , given a mechanism M with dominant strategies.
Mechanism M 0 is DSIC: If a participant i has private information vi , then submitting abid other than vi can only result in M 0 playing a strategy other than si (vi ) in M , which can
only decrease i’s utility. The point of Theorem 3.1 is that, at least in principle, if you design a mechanism tohave dominant strategies, then you might as well design for direct revelation (in auctions,truthful bidding) to be a dominant strategy.
Many equilibrium concepts other than dominant-strategy equilibria, such as Bayes-Nashequilibria, have their own Revelation Principle. Such principles state that, given the choiceof incentive constraints, direct revelation is without loss of generality. Thus, truthfulness per
se is not important; what makes mechanism design hard is the requirement that a desired
outcome (without loss of generality, truthful reporting) in an equilibrium of some type.
Varying the choice of equilibrium concept can lead to quite different mechanism design
theories, with stronger equilibrium concepts (like dominant-strategy equilibria) requiring
weaker behavioral assumptions but with narrower reach than weaker equilibrium concepts(like Bayes-Nash equilibria).

References[1] S. Chawla, N. Immorlica, and B. Lucier. On the limits of black-box reductions in mechanism design. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing(STOC), pages 435–448, 2012.

8