Unlock document.
This document is partially blurred.
Unlock all pages and 1 million more documents.
Get Access
5 Mechanism Design
Problem 5.1 (Surplus extraction) Show that if buyers’values are independently dis-
tributed, then the seller cannot design an incentive compatible and individually ratio-
nal mechanism that extracts the whole surplus from buyers. (In doing this problem,
use only the results of Section 5.1 and not those from Section 5.2.)
Solution. Suppose that there exists a mechanism extracting all the surplus from
the buyers. We also assume that the supports of the buyer value distributions are
Because the buyers’values are independently distributed, when the buyer reports
ziwhen his true value is xi, his expected payoff is (see Section 5.1)
qi(zi)ximi(zi)
and
Incentive compatibility implies that
Ui(xi)qi(zi)ximi(zi)
Because the seller extracts all the surplus from all the buyers, Ui(xi) = Ui(zi) = 0
and for all iand for all xiand zi;
The inequality above implies qi(zi) (bizi)0;therefore qi(zi) = 0 if zi< bi.
So qi(zi)=1only if ziis the highest value. Note that the mechanism is incentive
Problem 5.2 (Optimal auction) There is a single object for sale and there are 2
potential buyers. The value assigned by buyer 1to the object X1is uniformly drawn
from the interval [0;1 + k]whereas the value assigned by buyer 2to the object X2
is uniformly drawn from the interval [0;1k];where kis a parameter satisfying
0k < 1. The two values X1and X2are independently distributed.
a. Suppose the seller decides to sell the object using a second-price auction with
a reserve price r: What is the optimal value of rand what is the expected revenue of
the seller?
b. What is the optimal auction associated with this problem?
17
Solution. Part a. Let the cumulative distribution for X1be F1(x1) = x1
1+kand
1 is
Z1+k
r
[m1(x1; r)] f1(x1)dx1=Z1+k
rrF2(r) + Zx1
r
yf2(y)dy1
1 + kdx1
=Z1+k
y1
where the first equality comes from (2.9) and G=F2.
The payment from buyer 2 is
Z1k
r
[m2(x2; r)] f2(x2)dx2=Z1k
rrF1(r) + Zx2
r
yf1(y)dy1
1kdx2
=Z1k
y1
The optimal reserve price rmaximizes the expected revenue below
E[m1(X1; r)] + E[m2(X2; r)] = Z1+k
rrr
1k+Zx1
r
y1
1kdy1
1 + kdx1
+Z1k
y1
Differentiating this with respect to r, we obtain
12r2+ 6r= 0
So we have r=1
2and the corresponding expected revenue for the seller is
1
Part b. The virtual valuation for buyer 1 with value x1is
The virtual valuation for buyer 1 with value x1is
18
Therefore the smallest value for bidder 1 that wins against x2is
y1(x2) = inf fz1: 1(z1)0and 1(z1) 2(x2)g
and
y2(x1) = inf fz2: 2(z2)0and 2(z2) 1(x1)g
Because 1and 2are increasing functions, the design problem is regular and by
Proposition 5.3, the optimal mechanism (Q; M)is given as
2
For i= 1;2,
Mi(x1; x2) = yi(xi)if Qi(x1; x2) = 1
Problem 5.3 (Dissolving a partnership) Two agents jointly own a firm and each has
an equal share. The value of the whole firm to each is a random variable Xiwhich
is independently and uniformly distributed on [0;1] :Thus in the current situation,
agent 1derives a value 1
2X1from the firm and agent 2derives a value 1
2X2from the
firm. Suppose that the two agents wish to dissolve their partnership and since the
firm cannot be subdivided, ownership of the whole firm would have go to one of the
two agents.
a. Consider the following procedure for reallocating the firm. Both agents bid
amounts b1and b2and if bi> bj, then igets ownership of the whole firm and pays
the other agent jthe amount bi. Find a symmetric equilibrium bidding strategy in
this auction.
b. Is the procedure outlined above e¢ cient? Is it individually rational?
c. Calculate each agent’s payments in the VCG mechanism associated with this
problem.
Solution. Part a. Let the symmetric equilibrium bidding strategy be (x). Given
the uniform distribution, 1(bi)is the probability of winning for bidder iwhen he
19
bids bi;and his expected payoff is
1(bi)1
2xibi+11(bi)E[(Xi)jbi; (Xi)> bi]
(y)
Maximizing this respect to biyields the first-order condition
1
At symmetric equilibrium bi=(xi)so the first-order condition becomes
1
xi
2
Using the integrating factor x2
i, we solve the equation above and have the solution
(x) = 1
Part b. Because the bidding function is strictly increasing, the buyer with a
higher valuation wins the firm, therefore the procedure above is e¢ cient.
The expected payment for buyer iwith value xiis
mi(xi) = xi(xi)(1 xi)Z1
xi
(y)
1xi
dy
=1
iZ1
1
so mi(0) <0therefore the procedure is individually rational.
Part c. Using formula (5.22), the payments in VCG mechanism are
MV
i(xi; xi) = W(i; xi)Wi(xi; xi)
=1
where the second equality comes from
Wi(xi; xi) = 0if xi> xi
1
20
Problem 5.4 (Negative externality) The holder of a patent on a cost reducing process
is considering the possibility of licensing it to one of two firms. The two firms are
competitors in the same industry and so if firm 1obtains the license, its profits will
increase by X1while those of firm 2will decrease by X2, where is a known
parameter satisfying 0< < 1:This is because if firm 1gets the license, firm 2will
have a cost disadvantage relative to firm 1. Similarly, if firm 2obtains the license, its
profits will increase by X2while those of firm 1will decrease by X1. The variables
X1and X2are uniformly and independently distributed on [0;1] :Firm 1knows the
realized value x1of X1and only that X2is uniformly distributed, and similarly for
firm 2.
a. Suppose that the license will be awarded on the basis of a first-price auction.
What are the equilibrium bidding strategies? What is the expected revenue of the
seller, that is, the holder of the patent?
b. Find the payments in the VCG mechanism associated with this problem. Are
the expected payments the same as in a first-price auction?
c. Suppose that the patent holder is a government laboratory and it wants to
ensure that the license is allocated e¢ ciently and that the net payments of the buyers
add up to zero, that is, the “budget” is balanced. What is the associated “expected
externality” mechanism for this problem? Is it individually rational? Does there
exist an e¢ cient, incentive compatible, and individually rational mechanism that also
balances the budget?
Solution. Part a. Let the symmetric equilibrium bidding strategy be (x):If the
firm iwith value xibids bi, his expected payoff is
Maximizing this respect to biyields the first-order condition
1
At symmetric equilibrium bi=(xi)so the first-order condition becomes
1
which could be rewritten as
xi
Therefore the equilibrium bidding strategy is
2x
The payment from bidder iwith valuation xiis
2x2
21
so the seller’s revenue is
0
1 +
2x2
idxi=1 +
3
Part b. The VCG payments in this problem are
MV
i(xi; xi) = W(0; xi)Wi(xi; xi)
=xiWi(xi; xi)
where the last equality comes from
So the seller’s revenue from the VCG mechanism is
0
0
y
xi
3
Therefore, we have ERI> E RV
Part c. As in Section 5.3, the “expected externality”mechanism for this problem
Q; MAis defined by
MA
i(xi; xi) = EXi[Wi(Xi; xi)] EXi[Wi(xi; Xi)]
2x2
where the second equality comes from
Wi(Xi; xi) = Xiif Xi> xi
Wi(xi; Xi) = 0if xi> Xi
Note that
mi(0) = Z1
0
MA
0
1
20x2
60
so it is individual rational.
Because VCG mechanism derived in Part b results an expected surplus, Proposi-
22
Problem 5.5 (A non-standard selling method) There is a single object for sale and
there are two interested buyers. The values assigned by the buyers to the object are
independently and uniformly distributed on [0;1] :As always, each buyer knows the
value he or she assigns to the object but the seller knows only that each is inde-
pendently and uniformly distributed. The seller assigns a value of 0to the object.
Suppose that the seller adopts the following selling strategy. She approaches one of
the buyers (chosen at random) and makes a “take-it or leave-it”offer at a fixed price
p1. If the first buyer accepts the offer, the object is sold to him at the offered price.
If the first buyer declines the offer, the seller then approaches the other buyer with
a “take-it or leave-it” offer at a fixed price p2. If the second buyer accepts the offer,
the object is sold to him at the offered price. If neither buyer accepts then the seller
keeps the object.
a. What are the optimal values of p1and p2?
b. What is the expected revenue to the seller if he adopts this selling scheme?
c.How does it compare to a standard auction? In particular, does the revenue
equivalence principle apply?.
Solution. Part a. If the seller choose p1and p2, his expected revenue is
Maximizing this respect to p1and p2yields the first-order conditions
If p1= 0, the expected revenue is 0, so it can not be a solution. Therefore
2
Part b. The expected revenue is
(1 p
83
8+3
811
21
2
=21
64
Part c. From Example 3.1, we know that the standard auctions has expected
revenue 1
3which is more than 21
64 . The selling scheme could also be viewed as a direct
mechanism (Q; M)where
Q1(x1; x2) = 1if x1p1
0if x1< p1
23
For i= 1;2;
However the mechanism does not have the same allocation rule as standard auc-
tions. For example, If x2> x1> p1;buyer 1 gets the object, while in standard
auction buyer 2 should get the object. As a result, the revenue equivalence principle
does not apply here.
24
