978-0123745071 Chapter 4 Mechanism Design

Unlock access to all the studying documents.

View Full Document

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)ximi(zi)

and

Incentive compatibility implies that

Ui(xi)qi(zi)ximi(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) (bizi)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;1k];where kis a parameter satisfying

0k < 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?

Solution. Part a. Let the cumulative distribution for X1be F1(x1) = x1

1+kand

1 is

Z1+k

[m1(x1; r)] f1(x1)dx1=Z1+k

rrF2(r) + Zx1

yf2(y)dy1

1 + kdx1

=Z1+k

where the first equality comes from (2.9) and G=F2.

The payment from buyer 2 is

Z1k

[m2(x2; r)] f2(x2)dx2=Z1k

rrF1(r) + Zx2

yf1(y)dy1

1kdx2

=Z1k

The optimal reserve price rmaximizes the expected revenue below

E[m1(X1; r)] + E[m2(X2; r)] = Z1+k

rrr

1k+Zx1

1kdy1

1 + kdx1

+Z1k

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

Part b. The virtual valuation for buyer 1 with value x1is

The virtual valuation for buyer 1 with value x1is

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

For i= 1;2,

Mi(x1; x2) = yi(xi)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

bids bi;and his expected payoff is

1(bi)1

2xibi+11(bi)E[(Xi)jbi;  (Xi)> bi]

(y)

Maximizing this respect to biyields the first-order condition

At symmetric equilibrium bi=(xi)so the first-order condition becomes

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

(y)

1xi

iZ1

so mi(0) <0therefore the procedure is individually rational.

Part c. Using formula (5.22), the payments in VCG mechanism are

i(xi; xi) = W(i; xi)Wi(xi; xi)

where the second equality comes from

Wi(xi; xi) = 0if xi> xi

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

At symmetric equilibrium bi=(xi)so the first-order condition becomes

which could be rewritten as

Therefore the equilibrium bidding strategy is

The payment from bidder iwith valuation xiis

2x2

so the seller’s revenue is

1 + 

2x2

idxi=1 + 

Part b. The VCG payments in this problem are

i(xi; xi) = W(0; xi)Wi(xi; xi)

=xiWi(xi; xi)

where the last equality comes from

So the seller’s revenue from the VCG mechanism is

Therefore, we have ERI> E RV

Part c. As in Section 5.3, the “expected externality”mechanism for this problem

Q; MAis defined by

i(xi; xi) = EXi[Wi(Xi; xi)] EXi[Wi(xi; Xi)]

2x2

where the second equality comes from

Wi(Xi; xi) = Xiif Xi> xi

Wi(xi; Xi) = 0if xi> Xi

Note that

mi(0) = Z1

20x2

60

so it is individual rational.

Because VCG mechanism derived in Part b results an expected surplus, Proposi-

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

Part b. The expected revenue is

(1 p

83

8+3

811

21

=21

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 x1p1

0if x1< p1

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.