17 Packages and Positions
Problem 17.1 (Ine¢ ciency without package bidding) Suppose that there are two
objects, aand b, for sale and two bidders with the following values
a b ab
x1y z 2
x22 2 2
where yand zare parameters that lie between 0and 1:Argue that an ascending
auction format in which bidders can only bid on aand bindividually, and not on the
package ab; cannot allocate e¢ ciently. (Note: Without package bidding, the price of
the package ab is necessarily the sum of the prices of the individual objects aand b.)
Solution. Consider the ascending auction format described in Section 17.1 with
increments “. Without loss of generality, let 0< z y < 1so that an e¢ cient
allocation gives ato bidder 1 and bto bidder 2 (or also the reverse when y=z).
Problem 17.2 (Gross Substitutes) Show that if bidder iwith value vector xisatisfies
the gross substitutes condition (defined on page 241) then xisatisfies the substitutes
condition (defined in (16.6)). Equivalently, show that the gross substitutes condition
implies that xi(S)is submodular.
Solution. This argument is taken from the proof of Lemma 5 in Gul and Stacchetti
(1999).2Take A2 K,T 63 Aand S T and let M > x(K)be a price at which goods
are too expensive. Define a price vector
Recall that values are monotone: if ABthen x(A)x(B). As a result, T [fAg 2
D(p). For each “0, define a price vector
2Gul, F. and E. Stacchetti (1999), “Walrasian Equilibrium with Gross Substitutes,” Journal
of Economic Theory, 87, 95–124.
62
Define a critical price for good Aby
By construction we have
Also for “>”we have qT(“)pand T [fAg 2 D(p)so by gross substitutes there
must be a set C2D(qT(“)) with T C. Goods outside T [ fAgare too expensive
Together (20) and (21) give
Define a price vector
>
<
“a=A
a=qT
a(“)g. On the
other hand, all other goods are unaffordable so C S [ fAgand S [ fAg 2 D(qS).
Because of this latter fact, we have
Combining this with (22) gives the substitutes condition (16.6):
Problem 17.3 (Complements) Suppose that the objects in K=fa1; a2; b1; b2gare
sold via the ascending proxy auction. There are five interested bidders Bidder 1has
use only for objects a1and b1; bidders 2and 3have use only for objects a2and b2;
bidder 4has use only for b1and b2; and bidder 5 has use only for objects a1and a2.
Specifically, the values attached by the bidders to these bundles are
x1(a1b1) = 10
x2(a2b2) = 20
x3(a2b2) = 25
x4(b1b2) = 10
x5(a1a2) = 10
63
All other combinations (or packages) are valued at zero. (The specification is the
same as in Problem 16.2.)
a. Show that the gross substitutes condition is violated.
b. Show that it is not an equilibrium for each bidder to report truthfully to his
proxy.
Solution. Part a. Suppose p(a1) = 10; p(b1)=0; p0(a1) = 10; p0(b1)=1. Then
gross substitutes condition.
Part b. If all the other bidders are reporting truthfully, bidder 3 would do better
Problem 17.4 (Identical objects) Consider a situation in which Kidentical units are
to be allocated among Nidentical buyers. Each buyer has the same K-dimsional value
vector x;where x(k)denotes the total value from obtaining kunits. Suppose that the
units have decreasing marginal values— that is, x(k+ 2) x(k+ 1) x(k+ 1)
x(k):An allocation is then simply a vector of the form s=s1; s2; :::; sNwhere si
is the number of units awarded to buyer i: For any IN; define the surplus function
w(I) = maxsPI
i=1 x(si):Show that wis submodular, that is, for any I < J < N
w(I+ 1) w(I)w(J+ 1) w(J)
(Note: This is just a specialization of Lemma 17.1 to the case of identical objects and
identical buyers.)
Solution. It is su¢ cient to prove that w(I+ 1) w(I)w(I+ 2) w(I+ 1) :
When there are Iwinners, the welfare is maximized by allocation r1; : : : ; rIwhere
the ith winner has riunits. Similarly, (s1; : : : ; sI+1)is the allocation maximizing the
i= 1; : : : I + 1 and ti+1 tifor i= 1; : : : I + 2.
which means losing one unit when there are more units is better than losing one unit
when there are less units.
one, so
and the ith winner has less units when there are more winners
64
Third, we have
ss0xs0+ 1xs0 x(s)xs0(26)
because
x(s)xs0= [x(s)x(s1)] + [x(s1) x(s2)] +
where the inequality comes from (23). Roughtly, (27) means the losing ss0units
is better than ss0times the welfare loss by decreasing one units.
Then we have
I+1
X
I
X
Thus,
w(I+ 1) w(I)xsI+1
I
X
i=1 risixsi+ 1xsi
xsI+1
I
X
65
But the right-hand side of the inequality is no less than
xtI+2+sI+1 tI+2xsI+1xsI+1 1
sI+1 xsI+1xsI+1 1
=xtI+2+tI+2 xsI+1xsI+1 1
=xtI+2
I+1
X
where the first, fourth and sixth inequalities come from (??) and (27), the second and
fifth equalities come from (23), and the third inequality comes from (24) and (27).
Roughly speaking, the intuition is as follows. The second row is the welfare
increase by changing from allocation (r1; : : : ; rI)to (s1; : : : ; sI+1);and the third row
break this welfare increase into two parts, the welfare increase from the new winner
Problem 17.5 (GSP) Three positions are to be assigned among four bidders. The
positions have “click” values of 1> 2> 3:Each of the four bidders have “per-
click” values of x1> x2> x3> x4:These values are commonly known and so we are
considering a situation with complete information.
a. Find an equilibrium of the sealed-bid generalized second-price auction (GSP).
b. Is the equilibrium unique? If not, characterize all equilibria of the GSP.
Solution. Part a. Consider the following strategies:
b1=x1
b2=M1(x)=1=1
1
[(12)x2+ (23)x3+3x4]
2
3
66
Each bidder makes the same payment as in the VCG mechanism. Bidder 1 will not
deviate to slot 2 for value v1(2) because
v1(1) = 1x1[(12)x2+ (23)x3+3x4]
Similarly, none of the other bidders wish to win different slots at the associated prices.
Part b. Here we follow Varian (2007) closely.
Let I=f1;2;3;4gbe the set of bidders and K=f1;2;3;4gthe set of slots, with
a rate of 4= 0 clicks for the fourth slot. An outcome of the auction is a mapping
:K!I. An outcome is supported by some equilibrium bids if the following hold:
8k2K k(x(k)b(k+1))0
The first line is the individual rationality condition; the next two lines are incentive
compatibility conditions; and the last must hold for good kto be assigned to bidder
It is clear that the equilibrium is not unique. Suppose is an equilibrium outcome
supported by bids b. Then bidder (1) can bid !b(1) for any ! > 1and it is still an
or equivalently
where pkbk+1 for k= 1;2;3;4. To show that this condition characterizes a subset
of equilibria, we must show that it implies the equilibrium conditions above.
Claim. Condition (29) implies the conditions (28) and that is e¢ cient (that is,
it is the identity mapping).
Proof of claim. To show the first line of the equilibrium conditions, note that
4= 0 so
The second line is a special case of (29). To show that is the identity mapping, it
is su¢ cient to show that x(k)x(k+1). For any k; ` the condition gives
x(`)(`k)`p`kpk:
67
Adding these gives
so (k)(`)if and only if k`. So the slots are assigned e¢ ciently and we can
write kinstead of (k). To show that fourth line holds (decreasing prices), note that
k(xkpk)k1(xkpk1)
can be rearranged for
pk1k1pkk+xk(k1k)
The second inequality uses the first line of the equilibrium conditions: xkpk.
Finally, to show that the third line holds:
This completes the proof.
Second claim. If the condition (29) holds between kand k1and between kand
k+ 1 for all k, then it holds for all pairs.
Sketch of proof. Suppose it holds between 1 and 3 and between 2 and 3. We will
only show that it also holds between 2 and 3. Adding
and
gives
which is the condition for k= 1; ` = 3. For the other direction, add
to get
which completes the sketch. Finally, we can use this claim to characterize prices in
symmetric equilibria. The conditions between kand k+ 1 are
k(xkpk)k+1(xkpk+1)and k+1(xk+1 pk+1)k(xk+1 pk)
68
where each of the lines above is equivalent and kk+1=k. So, the set of symmetric
equilibrium bids is given by the following inequalities:
x3b4x4
x2(1 3) + b43b3x3(1 3) + b43
This completes the characterization of symmetric equilibria of the GSP auction.
Random-outcome equilibria. There are also equilibria with random outcomes, ei-
ther because some winning bids are tied or because players are randomizing. Suppose
each bidder ibids independently according to a random variable Biwith no mass
points. Then i’s payoff to bidding bis
3
X
k=1
where Ykis the kth highest order statistic of the other bidders’bids. These strategies
form a Nash equilibrium if, for all i2I, all b; b02suppBiand all b00 62 suppBiwe
have
69