10 Mechanism Design with Interdependent Values
All of the problems below concern the following environment. Suppose that there are
two potential buyers for one indivisible object. Each buyer’s private value Xifor
the object is drawn at random from the set X=f10;20g:Buyers’values are jointly
distributed as follows:
Pr [10;10] = Pr [20;20] = 0:2
Pr [10;20] = Pr [20;10] = 0:3
where Pr [x1; x2]denotes Pr [X1=x1; X2=x2].
Problem 10.1 (Generalized VCG mechanism) What is the generalized VCG mech-
anism (Q;M)for the environment specified above? Determine the expected revenue
from this mechanism.
Solution. The buyers’values are symmetric and private but correlated. Consider
a direct mechanism (QA;MA). Recall that Qi(x)is i’s probability of winning the
object when signals xare reported. And Mi(x)includes i’s payment upon “winning”
and “losing” separately. In what follows, these components are written as Miw(x)
and Mil(x);respectively.1
Buyer i’s beliefs about buyer j’s signal conditional on his own are given by Bayes’
buyers i= 1;2. Define
to be i’s expected payo¤ when his value is xi, he reports a value of ziand the other
buyer jreports truthfully.
The seller’s expected revenue in the truth-telling equilibrium of this mechanism
(if it exists) is the weighted sum of the payments taken from each buyer ifor each
pair of signals x, where weights come from the probability with which each bidder
wins Qi(x)and the probability of the signals P r[x]:
x
iQA
The generalized Vickrey-Clarke-Groves (VCG) mechanism (Q;M)is shown in
the table below.
x Q(x)M
iw(x)M
il(x)
10;10 1
2;1
210 0
1In Chapter 5, Mi(x)was i’s expected payment and did not depend on who won the object.
43
The buyers have private values so the discrete version of the single crossing condi-
tion (10.4) clearly holds and Proposition 10.1 says that truth-telling is an equilibrium.
The seller’s expected revenue in the truth-telling equilibrium is computed from (18),
above:
E[R] = Pr[10;10] (1
210 + 1
20) + (1
210 + 1
20)
+ Pr[10;20]f(0 10 + 1 0) + (1 10 + 0 0)g
Problem 10.2 Consider the following mechanism. If both buyers report values z1=
z2= 20, then pick a buyer randomly with probability 1
2, say this is buyer i, and give
him the object for a price of Mi= 20. The other buyer jpays nothing. If both report
values z1=z2= 10, again pick a buyer randomly with probability 1
2, say i, and give
him the object for a price of Mi= 19:The other buyer, say j, pays Mj= 9 without,
of course, getting the object. If one buyer reports zi= 20 and the other xj= 10, then
give the object to buyer ifor a price Mi= 20;The other buyer jreceives a transfer
of 6;that is, Mj=6:
a. Show that the mechanism described above is incentive compatible and individ-
ually rational.
b. What is the expected revenue in the truthful equilibrium of this mechanism?
c. Does the mechanism have other (non-truthful) equilibria?
Solution. Call this mechanism (Q;M). Then
x Q(x)Miw(x)Mil(x)
10;10 1
2;1
219 9
10;20 0;1 20 6
Part a. Truth-telling is incentive compatible (IC) for buyer iif for all xi; zi2 Xi
Ui(xi; xi)Ui(zi; xi)(IC)
where Uiwas defined in (17), above. To verify this condition, it is su¢ cient to consider
only buyer 1 and only z16=x1. That is, we need to show U1(10;10) U1(20;10) and
44
U1(20;20) U1(10;20).
2(10 19) + 1
2(9)
= 0
U1(20;10) = 0:61
=7
U1(20;20) = 0:41
= 0
U1(10;20) = 0:41
= 0
So, (IC) is satisfied. And individual rationality (IR),
Ui(xi; xi)Ui(xi)0;(IR)
is clearly also satisfied. Note that this mechanism is e¢ cient and it extracts the entire
surplus.
Part b. The mechanism is IC and IR, so truth-telling is an equilibrium. The
seller’s expected revenue in the truth-telling equilibrium is computed from (18),
above:
Part c. No, there are no other equilibria. First note that a low-valued buyer will
never report a value of 20 because his payo¤ from doing so is
So each buyer must report 10 when his value is 10. Next suppose one buyer reports
10 with probability > 0when his value is 20. Then the other buyer’s payo¤ when
his value is 10 is
which violates individual rationality. So each buyer must report 20 when his value is
20.
Problem 10.3 (Crémer-McLean mechanism) What is the Crémer-McLean mecha-
nism Q;MCfor the environment specified above?
45
Solution. The construction of the Crémer-McLean (CM) mechanism is explained in
the proof of Proposition 10.2. By symmetry of the value structure, we can restrict
attention to buyer 1. The vector of buyer 1’s expected payo¤s in the truth-telling
equilibrium of the VCG mechanism is
u
1U
1(10;10)
U
1(20;20) =0:40+0:60
0:40+0:610 =0
6
The matrix of buyer 1’s conditional beliefs is
11(10 j10) 1(20 j10)
This matrix has full row rank, so there is a unique solution to
1c1=u
1
namely,
c1=c1(10)
The CM mechanism is (Q;MC)where
MC
Buyer 2’s payments are analagous. The mechanism is summarized in the table below.
The payments made in zero-probability events may be anything; they are written as
in the table.
x Q(x)MC
1w(x)MC
1l(x)MC
2w(x)MC
2l(x)
10;10 1
2;1
228 18 28 12
10;20 0;1 12 28
Problem 10.4 (Non-negativity payo¤ constraint) For the environment specified above,
does there exist a mechanism that (a) is incentive compatible and individually ratio-
nal; (b) gives each buyer a non-negative payo¤ for every realization of the values; and
(c) extracts all the surplus from the buyers?
Solution. No, there is no such mechanism. In the last two mechanisms, the buyers
sometimes made negative payments (that is, the seller paid money to them). Suppose
this is not allowed:
Mik(x)0i= 1;2k=w; l: (NN)
A revenue-maximizing mechanism will solve the problem
max
Q;ME[R]subject to (IC), (IR) and (NN):(P)
46
This is a linear programming problem. After working it out, you will see that the
best mechanism is a posted price of 20, as given in the table below. The expected
revenue is easily calculated as
Pr[at least one player has a value of 20]20 = 16:
x Q(x)Miw(x)Mil(x)
10;10 0;0x0
10;20 0;1 20 0
20;10 1;0 20 0
47