Solutions to Jehle and Reny (3rd ed.), Chapter 9, 9.6-9.

36
By Huizhong Zhou, Western Michigan University
December, 2013
9.6. In the second-price and English auctions, each bidders bid is bi (vi ) = vi ,
the highest bidder j gets the object and pays cj (v) = max{vi , i = j}, and
the rest of the bidders pay nothing.
Denote v II the second largest value of v. Consider the following direct selling
mechanism (pi (v), ci (v)): pi (v) = 1 for vi > v II , pi (v) = 0 otherwise, and
v
ci (v) = pi (v)vi 0 i pi (x, vi )dx for all i. Clearly,
pi (v) is non-decreasing in
vi
vi , so is pi (vi ), and ci (v) = ci (0) + pi (vi )vi 0 pi (x)dx with ci (0) = 0, hence
the mechanism is incentive-compatible. Now, for any given v, pj (v) = 1 for
vj > v II , that is, the object is assigned
the individual with
vto
vj the highest
j
bid. And winner pays cj (v) = pj (v)vj 0 pj (x, vi )dx = vj vII 1dx = v II ,
and the others pay ci (v) = 0, i = j. The outcome is exactly the same as the
second-price sealed-bid or English auction.
Note that the distributions of the bidders values are not assumed to be
independent and symmetric. In fact, the seller doesnt have to know the
exact distribution functions.
In the equilibrium of the rst-price and Dutch auctions, each bidder bids
bi (vi ), which can be shown non-decreasing in vi and not grater than vi , and
the winner pays his own bid while the rest pay nothing.
Given v and bi (vi ), let bj (vj ) = max{b1 (v1 ), b2 (v2 ), , bn (vn )}. Consider a
direct selling mechanism (pi (v), ci (v)) such that pj (v) = 1 for vj bj (vj ),
pj (v) = 0 for vj < bj (vj ), and pi (v) = 0 for i = j; and ci (v) = pi (v)vi
vi
pi (x, vi )dx for all i. Obviously,
pi (v) is non-decreasing in vi , so is pi (vi ),
0
v
and ci (v) = ci (0) + pi (vi )vi 0 i pi (x)dx with ci (0) = 0. The mechanism is
therefore incentive-compatible. By construction of the probability assignment
functions, the object
bidder. The winner pays
vj is assigned to the highest
vj
cj (v) = pj (v)vj 0 pj (x, vj )dx = vj bj (vj ) 1dx = bj (vj ), and the rest pay
ci (vi ) = 0. The outcome is exactly the same as the rst-price auction.
In this mechanism, the distributions of the bidders values are not assumed
to be independent and symmetric either. However, the seller does have to
1

know the exact distribution functions in order to construct bi ().

9.7. Being incentive compatible, it must be true that u(v) = maxr[0,1] u(r, v) =
p(r)v c(r). We show that u(v, v) is convex. To see this, take v1 , v2
[0, 1], v1 = v2 . For any 0 1, writing v = v1 + (1-)v2 , we have
u(
v ) = max[
p(r)
v c(r)]
r

= max[(
p(r)v1 c(r)) + (1-)(
p(r)v2 c(r))]
r

max[
p(r)v1 c(r)] + (1-) max[
p(r)v2 c(r)]
r

= u(v1 , v1 ) + (1-)u(v2 , v2 ).
With the envelope theorem, u (v) = p(v), and u (v) = p (v) 0 due to
convexity of u().
9.8.
a). Let the equilibrium strategy of the all-pay with symmetric bidders be
b(v). First show that it is non-decreasing in v. A bidder with private value vj
wins the object with prob.{b(vi ) < b(vj ), i = j} G(b(vj )). If all the others
employ the equilibrium strategy, then it is the best response for j to adopt
the equilibrium strategy as well. Therefore we have G(b(vj ))vj b(vj )
G(b(z))vj b(z) and G(b(z))z b(z) G(b(vj ))z b(vj ). Adding the two
inequalities together and rearranging, we obtain (G(b(vj )) G(b(z)))(vj
z) 0, hence vj > z if and only if G(b(vj )) G(b(z)). Furthermore, the
distribution function is non-decreasing, thus vj > z if and only if b(vj ) b(z).
We therefore conclude that G = F N 1 , and to bid b(v) is equivalent to report
v.
If a bidder with private value v bids z, his expected payo is F N 1 (z)v b(z).
The derivative of the payo function w.r.t. z should be equal to zero when
evaluated at z = v. Thus we have (F N 1 ) v = b (v), which gives
v
b(v) =
xdF N 1 (x).
0

Or, applying the revenue equivalence theorem, a bidder with private value
v in the all-pay auction pays the same expected cost as in the rst-price
2

v
auction, which is 0 xdF N 1 (x). Since a bidder in the
auction pays
v all-pay
N 1
his own bid, winning or losing, his bid then must be 0 xdF
(x).
v
b). In the rst-price auction
a bidder with v bids 0 xdF N 1 (x)/F N 1 (v),
v
N 1
which is greater than 0 xdF
(x), as F N 1 (v) < 1. Since a bidder in the
all-pay auction has to pay his bid whether he wins or not, he bids lower than
when he doesnt have to pay if he doesnt get the object.
c) and d). The sellers expected revenue is
]

1 [ v
N 1
N
xdF
(x) f (v)dv = N (N 1)
0

v(1 F (v))F N 2 (v)f (v)dv,

which can be derived from the bids, as is shown above.

determined by applying the revenue equivalence principle.

Or it can be

9.9. Two bidders, second-price, all-pay auction.

Let (v) be the symmetric equilibrium bid. If the rst bidder who has a
private value v bids (z) or reports z while the second adopts the equilibrium
strategy, she will win with probability F (z) and lose with probability 1F (z).
In the former case she receives v and pays E[(v2 ) | v2 < z], which is
z
f (x)
(x)
dx.
F (z)
0
In the latter case, she pays her own bid (z). Her expected payo is
z
(
f (x) )
F (z) v
dx (1 F (z))(z).
(x)
F (z)
0
The derivative of the payo w.r.t. z, evaluated at z = v, should be equal to
zero. We have
vf (v) (v)f (v) + (v)f (v) (1 F (v)) (v) = 0,
which gives

(v) =
0

xf (x)
dx.
1 F (x)

Alternatively, applying the revenue equivalence theorem, we have

v
v
f (x)
F (v)
(x)
dx + (1 F (v))(v) =
xf (x)dx,
F (v)
0
o
3

where the right-hand side of the above equation is the expected payment of a
bidder with value v in a second price auction with 2 bidders. Dierentiating
the above identity w.r.t. v generates
(1 F (v)) (v) = vf (v),
which gives the same solution as we found earlier with a direct approach.
Still another alternative, which I had attempted, turned out to be incorrect
but instructive. In this auction, the seller collects (v) twice, where v =
min{v1 , v2 }, which has a density function g(x) = 2(1 F (x))f (x). Applying
the revenue equivalence theorem, we have
1
1
2(v)g(v)dv =
vg(v)dv.
0

It is straightforward that

v
(v) = ,
2
which seems to make sense but is incorrect. The thrust of the theorem is
equivalence of expected revenue from an individual with value v. Equivalence
of the expected revenue over v follows as a result of weighted averaging.
However, specics can be lost in averaging.
9.10. The expected private value to a bidder with value v now is v/2. The
symmetric equilibrium strategy should be such that 12 F N 1 (z)v (z) is
maximized at z = v. It is straightforward
that the equilibrium bid is half of
v
N 1
the regular rst-price bid, which is 0 xdF
(x)/(2F N 1 (v)). The expected
revenue is hence half of that in a rst-price auction.
9.11. Let r0 > 0 be the reserve. The probability assignment functions have
to satisfy
the following: pi (v) = 0 for vi r, i = 1, 2, ..., N and p0 (v) =

1 pi (v). Expression (9.12) on page 448 in the Text shall be modied as

follows,
}
[
]
1 1 {
N
N

1 Fi (vi )
R=

pi (v) vi
+ [1
pi (v)]r0 f (v)dv.
f
(v
)
i
i
0
0
i=1
i=1
The revenue maximizing mechanisms assignment functions are as follows,
{
1F (v )
i (vi )
1, if vi 1F
> max{r0 , vj fj (vj j )j } for all j = i;
fi (vi )
pi (v) =
0, otherwise.
4

(r)
The reserve is determined by r = r 1F
in the symmetric case. For the
f (r)

uniform distribution on [0, 1], r0 = 1/2.

9.12. With the identical distributions, MRi (vi ) > MRj (vj ) if and only if vi >
vj , hence the assignment functions of the revenue-maximizing mechanism
specied in 9.11 can be modied as
{
1, if vi > max{r0 , vj } for all j = i;
pi (v) =
0, otherwise,
which is the same as those in the rst-price auction with a reserve. Following
the revenue equivalence theorem, the optimal reserve is the same as in 9.11.
9.13. Assume that the object is worth v0 , 0 v0 < 2 to the seller. The
assignment functions should be modied as
{
1, if vi > max{v0 , max{r0 , vj }} for all j = i;
pi (v) =
0, otherwise,
The optimal reserve is to be determined by
r0

1 F (r0 )
= v0 .
f (r0 )

For F (v) = v 1 on [1, 2], (1 F (v))/f (v) = 2 v. So ro = 1 if v0 = 0,

ro = 1 21 if v0 = 1.
9.14. vi [ai , bi ] follows uniform distribution.
The virtual marginal revenue is as follows,
MRi = vi

1 Fi (vi )
= 2vi bi .
fi (vi )

The optimal probability assignment rule that pi = 1 if MRi > maxj=i {MRj , 0}
and pi = 0 otherwise translates to pi (v) = 1 if
vi > bi /2 + max{0, vj bj /2},
j=i

and pi (v) = 0 otherwise. But vi ai , hence pi (v) = 1 if vi > max{ai , bi /2 +

maxj=i {0, vj bj /2}}. Let ci (ai , vi ) = 0 for all vi , then
vi

ci (v) = pi (v)vi
pi (x, vi )dxi = max{ai , bi /2 + max{0, vj bj /2}}
j=i

ai

for the winner, and cj (v) = 0 for the others.

9.15.
a). In the second stage for player j to purchase if and only if vj > bi is the best
response to any bi . In the rst stage, given that i plays the specied strategy,
a deviation such that bj < bj (vj ) changes the outcome only if vi < bj (vj ) but
vi > bj . This change has no eect on js payo when vj < bi , but a loss when
vj > bi . Similarly, a deviation that bj > bj (vj ) changes the outcome only if
vi > bj (vj ) but vi < bj . This change has no eect on js payo when vj < bi .
When vj > bi , the deviation would induce individual i to say no instead of
yes, thus generate a gain. However, vj > bi and vi > bj can never occur,
because vj > bi (vi ) translates to MRj (vj ) > MRj (bi ) = max{0, MRi (vi )},
while vi > bj (vj ) implies MRi (vi ) > max{0, MRj (vj )}. The two inequalities
MRi (vi ) > max{0, MRj (vj )} and MRj (vj ) > max{0, MRi (vi )} contradict
each other.
b). The equilibrium maximizes the sellers revenues because p (v)i = 1 if
MRi (vi ) = max{MR1 (v1 ), MR2 (v2 )} > 0, pi (v) = 0 otherwise. It is not
always ecient. It is not ecient, for example, if v0 = 0, vi > 0 but
MRi (vi ) 0 for i = 1, 2, where v0 is the sellers value of the object. It
can also be inecient if vi > bj and vj < bi but vi < vj .
c). It is essentially the equilibrium strategies of the second-price auction. It
is always ecient.
d). It does not necessarily maximizes the sellers revenues because the object
is assigned to the one whose value is equal to max{v1 , v2 }, but not necessarily
to the one who generates the greatest non-negative marginal revenue, if the
distributions are not identical.
e). The strategies are the same as the original, except that MRi and MRj
are replaced with gi and gj . If gi gj , it is ecient because vj > bi if and
only if g(vj ) > g(vi ), which implies vj > vi . Here it is assumed that the value
of the object to the seller is zero.
6

9.16. If F is convex, then F = f 0 (assuming dierentiability). (1

F (x))/f (x)) = 1(1F (x))f /f 2 < 0, so x(1F (x))/f (x) is increasing.
Convexity of F is not necessary.
9.17. Let vi follow distribution Fi on [0, bi ], and vi and vj are mutually
independent. The sellers value of the object is assumed to be v0 0.
a). Ecient assignment functions must be such that pi (v) = 1 for i with
vi > max{v0 , vj , j = i}, and pi (v) = 0 otherwise. It is non-decreasing in vi
as well.
b). The cost functions are as follows,

ci (v) = ci (0, vi ) + pi (v)vi

vi

pi (x)dx, for i = 1, 2, ..., N.

These cost functions satisfy

ci (vi ) = ci (0) + pi (vi )vi

vi

pi (x)dx.
0

Therefore, {pi (v), ci (v)} specied in (a) and (b) is an ecient, IR and IC
direct selling mechanism.
c). Given the assignment functions, ci (v) = ci (0, vi ) + max{v0 , vj , j = i} for
i such that vi > max{v0 , vj , j = i}, and ci (v) = ci (0, vi ) otherwise. For
individual rationality, ci (0) 0. So the expected revenue is maximized at
ci (0) = 0, which can be achieved by setting ci (0, vi ) = 0 for all i.
d). The ecient, IR and IC direct selling mechanism specied in (a)-(c)
is exactly a second-price auction with a reserve equal to the sellers value.
The English auction is strategically equivalent to a second-price auction, and
hence exhibits the same properties. The rst-price and Dutch auctions are
not necessarily ecient if the the bidders are asymmetric.
9.18. Let pi (v), ci (v) be a deterministic, IC direct selling mechanism, where
private values are independent, taking values in [0, bi ].
a). Suppose pj (v) = 1 and pi (v) = 0 for i = j for a given v. Since pi is
non-decreasing, pi (x, vi ) = 0 for x < vi and pj (x, vj ) = 0 for some x < vj ,
given v. Let rj (vj ) max{x [0, bj ] | pj (x, vj ) = 0}. Now construct cost
7

functions as follows,
ci (v)

vi

= pi (v)vi

pi (x, vi )dx.
0

Clearly, ci (v) = 0 for i = j, and cj (v) = rj (vj ). That is, the winner pays
rj (vj ), which is independent of vj , and the others pay nothing.
Since the two mechanisms employ the same assignment functions, the expected
revenues are the same, as long as ci (0) = ci (0).
b) and c). Both rst-price and all-pay, rst-price auctions are deterministic.
By the revelation principle, there exist incentive-compatible direct mechanisms
that generate the same equilibrium outcomes as those auctions. These equivalent
mechanisms therefore are deterministic as well. Then the result applies. In
particular, if these auctions are symmetric, the required mechanism specied
by this result is a second-price auction.
9.19. The probability assignment functions of the optimal direct selling
mechanism are pi (v) = 1 if MRi (vi ) > max{0, MRj (vj )} for all j = i and
pi (v) = 0 otherwise. The payment functions are
vi

ci (v) = pi (v)vi
pi (x)dx = r (vi ),
0

if pi (v) = 1, and c (v) = 0 if pi (v) = 0, where r (vi ) is such that MRi (r ) =

maxj=i {0, MRj (vj )}. As MRi is assumed to be strictly increasing, vi > r .
If the winner submitted a report higher or lower than his true value but
still got the object, his payo would not be aected since his payment does
not depend on his own report. If he submitted a suciently lower value, he
would not be assigned the object and lose the net payo vi r > 0. For
the one who does not get the object in equilibrium, her payo would not
change if she instead submitted a report higher or lower than her true value
but still didnt get the object. However, if she reported a suciently higher
value and won the object, she would pay more than her value. To see this,
suppose pi (v) = 1 and pk (v) = 0. So MRi (vi ) > MRk (vk ) in equilibrium. If
player k reported bk so that MRi (vi ) < MRk (bk ), then she got the object and
had to pay r (vk ), which is determined by MRk (r (vk )) = MRi (vi ). Since
MRi (vi ) > MRk (vk ) and MRk is strictly increasing, vk < r (vk ).
8

9.20. Assume that vi [0, bi ] and vi s are independent. Let i be such that
MRi (i ) = 0. Such a i (0, bi ) exists and is unique since MRi (0) < 0,
MRi (bi ) > 0 and MRi is strictly increasing. The seller keeps the object if
and
only if v is such that MRi (vi ) 0 for all i. The probability of that event
is N
i=1 Fi (i ), which is strictly positive since i > 0.
9.21. Under the assumption of symmetry, all the four auctions employ
the same assignment functions that the object goes to the individual with
the highest value. Again by symmetry, vi > vj if and only if MR(vi ) >
MR(vj ). Therefore, the revenue-maximizing mechanism assigns the object to
the individual with the highest value as well. Let r be such that MR(r) = 0.
Then MR(vj ) > maxi=j {0, MR(vi )} is equivalent to vj > maxi=j {r, vi }. If
the four auctions set r as the reserve, then they employ exactly the same
assignment rule and hence are revenue maximizing.
9.22.
a). Since the equilibrium strategies are the same and increasing, the bidder
with the highest value wins the auction.
b). Bidder i with value equal to zero wins only if 0 > vj for all j = i, the
probability of which is zero. Suppose ci (0, vi ) > 0, then bidder i can simply
bid zero to reduce his cost, since the rule is such that no bidder ever pays
more than his bid.
c). Now this auction employs the same assignment rule and ci (0, vi ) = 0
as the standard rst-price or second-price auctions. Following the revenue
equivalence theorem, the expected revenue is the same as those auctions,
which is the expected value of the second largest value of v.
1
R=
vN (N 1)F N 2 (v)(1 F (v))f (v)dv
0
1
= N (N 1)
v v 2N 4 (1 v 2 )2vdv
0

= N (N 1)

4
4N 2

4N 1
=1
.
4N 2 1

9.23.
a). Telling the true value is a weakly dominant strategy, following the same
argument that is applied to a second-price auction.
b). The sellers expected revenue is twice of the expectation of the third-largest
value of N random variables,
1
1
[3|N ]
2E[Y
]=2
vg(v)dv = N (N 1)(N 2)
v(1F (v))2 F (v)N 3 f (v)dv,
0

which is 2(N 2)/(N + 1) if the distribution is uniform.

(Note that g(v) = 21 , not 16 .)
9.24.
a). With F (v) = v, v [0, 1] and n = N/2 bidders, the equilibrium strategy
of the rst-price auction is
v
v n1
1
v
2v
F
(x)
n1
b(v) =
dx = v = v .
xdF
(x) = v
n1
n1
F
(v) 0
(v)
n
N
0 F
b). The expected revenue from each winner is the expected value of the
second largest of n private values, which is
1
n1
N 2
[2|n]
E[Y
=
n(n 1)v(1 F (v))F n2 (v)f (v)dv =
=
.
n+1
N +2
0
Clearly, (N 2)/(N + 1) > (N 2)/(N + 2).
The result will be the same if a second-price auction is employed in the two
rooms, by the revenue equivalence theorem.
Intuitive explanations? If both mechanisms employ the second-price auction,
each bidder bids the same in both situations. The dierence in revenues
then is statistical in nature: The expectation of the third largest of 2N i.i.d.
random variables is greater than that of the second largest of N i.i.d. random
variables.
Suppose that the auction in 9.23 is a rst-price one, that is, the top two
bidders receive each object and pay their own bids, and the others pay
10

nothing. Now the probability assignment functions are the same as those
described in 9.23, and ci (0, vi ) = 0 in both auctions as well. Therefore,
the expected revenue is to be the same as is found in 9.23. One might
then argue that, with a larger number of participants, it is less likely to
win the object. Therefore, the bidders bid more aggressively when there are
more bidders. On the other hand, the bidders would bid less aggressively if
the second-highest bid can also win the object. On balance, the statistical
explanation still sounds more plausible.
9.25. Given that vi follows uniform distribution on [ai , bi ],
MRi (x) = x

1 (x ai )/(bi ai )
= 2x bi .
1/(bi ai )

Let the reserve price i be such that MRi (i ) = 0, or i = bi /2.

The specied sealed bid is essentially a second-price auction, with a modication
that the winner pays his reserve price in addition to the second-highest bid.
Accordingly, the bidders will subtract bi /2 from the bids that they would
otherwise submit in a second price auction without this modication. It is
known that truthful reporting is a weakly dominant strategy in a second
price auction, the bid in the modied auction therefore is i (vi ) = vi bi /2.
Now MRi (vi ) = 2vi bi = 2(vi ), therefore, pi (v) = 1 if i > max{0, j }
for all j = i is equivalent to pi (v) = 1 if MRi (vi ) > max{0, MRj (vj )} for all
j = i, which maximizes the expected revenues.

9.26. Suppose x that maximizes

vi (xi ) were not Pareto ecient. Then
there must exist a feasible allocation y X and a set of transfers such that
vi (yi ) + i vi (
xi ) with at least one strict inequality. Therefore

vi (yi ) + i =
vi (yi ) >
vi (
xi ),

where i = 0 is simply the fact that the total transfers among the members
themselves
net zero. The above inequality contradicts that x maximizes

vi (xi ). Therefore x must be Pareto ecient.

9.28. It is understood that the object to be auctioned o is single and
indivisible. Thus, X = {0, 1, 2, ..., N } and x X can be written as i X.
Write ti = vi , Ti = Vi and T = V , then the probability assignment and cost
functions in Denition 9.4 become
pi (v0 , vi , ..., vN ) and ci (v0 , vi , ..., vN ) for i = 0, 1, ..., N,
11

with

N
i=0

pi (v) = 1. It is exactly Denition 9.1.

In particular, the VCG mechanism with X = {0, 1, 2, ..., N } and vi (x, ti ) =

ti px (t) = vi pi (v) is equivalent to the second-price auction.
9.29. The new ex post cost functions, with the superscript omitted, are as
follows,
1
ci (ti ) = ci (ti )
cj (tj ).
N 1 j=i

Obviously, i ci (ti ) = 0. The expected utility of type ti who reports ri in

the new mechanism is
1
uVi CG (ri , ti ) +
cj ,
N 1 i=j
while the expected utility in the mechanism in Theorem 9.11 is
uVi CG (ri , ti ) + ci+1 .
The two objective functions dier only by a constant. Therefore, Theorem
9.11 applies to the new mechanism as well. Moreover, as cj 0, the new
mechanism is individually rational as well.
9.30.
b). Given that individual 2 reports truthfully, when individual 1 reports
his type truthfully, his gross utility is v1 (
x(t), t1 = 3) = t1 + 5 = 8 for
t2 = 1, 2, 3, 4, 5, 6, 7 and v1 (
x(t), t1 = 3) = 2t1 = 6 for t2 = 8, 9. Therefore, the
expected gross utility, v1 (3) = Et2 T2 [v1 (
x(t), 3)], is equal to (87+62)/9 =
68/9. If he instead reports r2 = 2, v1 (
x(r1 , t2 ), t1 = 3) = t1 + 5 = 8 for
t2 = 1, 2, 3, 4, 5, 6, 7, 8 and v1 (
x(r1 , t2 ), t1 = 3) = 2t1 = 6 for t2 = 9. Thus
v1 (r1 = 2, t1 = 3) = (8 8 + 6 1)/9 = 70/9. Values of v1 (r1 , t1 = 3) for
other values of reports can be similarly calculated and are presented in Table
1.
The last row of Table 1 displays u1 (r1 , t1 = 3) = v1 (r1 , t1 = 3) c1 (r1 ), where
c1 (r1 ) is the answer to (a). It reveals that reporting untruthfully can do no
better. (Individual 1s net expected utility is u1 (r1 , t1 = 3) + c2 , where c2 is a
constant across r1 .)
12

Table 1: v1 (r1 , 3, t2 ), v1 (r1 , 3) and u1 (r1 , 3) for r1 = 1, 2, ...9

1

t2
1
2
3
4
5
6
7
8
9

r1

8
8
8
8
8
8
8
8
8

8
8
8
8
8
8
8
8
6

8
8
8
8
8
8
8
6
6

8
8
8
8
8
8
6
6
6

8
8
8
8
8
6
6
6
6

8
8
8
8
6
6
6
6
6

8
8
8
6
6
6
6
6
6

8
8
6
6
6
6
6
6
6

8
6
6
6
6
6
6
6
6

v1 (r1 , t1 = 3)

72
9

70
9

68
9

66
9

64
9

62
9

60
9

58
9

56
9

c1 (r1 )

10
9

2
3

1
3

1
9

1
9

1
3

2
3

u
1 (r1 , t1 = 3)

62
9

64
9

65
9

65
9

64
9

62
9

59
9

55
9

50
9

However, truthful reporting is not a weakly dominant strategy, as is pointed

out in the Text. Take a strategy prole (r1 (), r2 ()), where r2 (t2 ) = 1 for all
t2 = 1, 2, ..., 9, and r1 (3) = 3. Now consider a deviation by player 1, r1 , where
r1 (3) = 8 and r1 (t1 ) = r1 (t1 ) for t1 = 3. Individual 1 with t1 = 3, reporting
truthfully
(playing r1 (3)), gets an expected payo v1 (r1 (3), 3) = t1 + 5 = 8,

as i (ri 5) 0 and hence x(r1 (3), r2 (t2 )) = S for all t2 . Since neither
individual is pivotal, c1 (r1 (3)) = 0 and c2 (r1 (3), r2 (t2 )) = 0. If individual 1
plays r1 (3) = 8 instead, the outcome still is x(r1 (3), r2 (t2 )) = S, and hence 1s
payo is the same v1 (r1 (3), 3) = t1 +5 = 8 for all t2 . His cost remains the same
as well, c1 (r1 (3)) = 0, as he is not pivotal. But now individual 2 is pivotal
and has to pay to individual 1 a cost equal to c2 (r1 (3), r2 (t2 )) = r1 (3)5 = 3.
Thus, by deviating from r1 (3) to r1 (3), individual 1 gets the same v1 and pays
the same zero cost, but he receives 1/3 more from individual 2 of any t2 , as
c2 (r1 , r2 (t2 )) c2 (r1 , r2 (t2 )) =

1
i=1

[c2 (r1 (i), r2 (t2 )) c2 (r1 (i), r2 (t2 ))]

1
= [c2 (r1 (3), r2 (t2 )) c2 (r1 (3), r2 (t2 ))]
9
1
= .
3
13


c). Write V (t) = 3i=1 (ti 5) and V1 (t1 ) = t2 + t3 10. If V (t) > 0 and
V1 (t1 ) > 0, or V (t) 0 and V1 (t1 ) 0, then c1 (t) = 0; if V (t) > 0 and
V1 (t1 ) 0, then c1 (t) = V1 (t1 ); and if V (t) 0 and V1 (t1 ) > 0, then
c1 (t) = V1 (t1 ). For all possible t T1 t2 T3 , Ti = {1, 2, ..., 9}, the costs to
be paid by individual 1 are presented in Table 2, wherein the last row gives
the expected costs, c1 (t1 ) = Et1 T1 [c1 (t)].
Table 2: c1 (t) and c1 (t1 )
t1
t2 + t3
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

Frequency
1
2
3
4
5
6
7
8
9
8
7
6
5
4
3
2
1
c1 (t1 )

0
0
0
0
0
0
0
0
0
1
2
3
4
0
0
0
0

0
0
0
0
0
0
0
0
0
1
2
3
0
0
0
0
0

0
0
0
0
0
0
0
0
0
1
2
3
0
0
0
0
0

0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0

0
0
0
0
0
0
2
1
0
0
0
0
0
0
0
0
0

0
0
0
0
0
3
2
1
0
0
0
0
0
0
0
0
0

40
81

22
81

8
81

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0

20
27

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

8
81

22
81

40
81

9.31.
a). If an individual has to contribute some time toward building either the
pool or bridge, then he can enjoy the time that he doesnt have to give up,
which is worth ki > 0, if neither project is undertaken.
b). Assuming that individual i of type ti reports r1 while all the others report
truthfully, his interim IR constraint is as follows

ui (ri , ti ) =
qi (ti )
[ pxi (ri , ti )vi (x, ti ) ci (ri , ti )] ki .
ti Ti

xX

14

c). x
(t) = S if i (ti + 5) max{ i 2ti , i ki }; x(t) = B if
i 2ti >
max{ i (ti + 5), i ki }; and x(t) = D otherwise.
d). The sucient condition for the existence of an IR and ecient mechanism
for quasi-linear utility functions is
N

q(t)(cVi CG (t)

i )

tT i=1

(
cVi CG i ) 0,

i=1

where

i = max [IRi (ti )

ti Ti

qi (ti )(vi (
x(t), ti ) cVi CG (t))].

ti Ti

In the case where the individuals have no ownership rights over their leisure
time, i = 0 for all i.
As cVi CG (t) 0, the sucient condition is always met for the case where
the individuals have no ownership rights. The sucient condition may be
violated if there are ownership rights. Example 9.8 and Exercise 9.33(d) are
two such examples.
The IR and ecient mechanism can be implemented by an IR-VCG mechanism,
wherein each individual reports his type, the social state is x(t) and individual
i pays
CG
CG
cVi CG (ti ) i cVi+1
(ti+1 ) + cVi+1

N
1 V CG
(
c
j ).
N j=1 j

9.32. The assumption needed for this proposition is that, for every i, the
value function vi (x, ti ) is non-decreasing in ti for all states x X. Examples
9.3-9.7 satisfy this assumption.
With the VCG mechanism, given t, individual is utility is

ui (
x(t), ti ) =
vj (
x(t), tj )
vj (
xi (ti ), tj ).
j

j=i

Let t be such that ti ti and tj = tj for j = i. Clearly,

vj (
x(t), tj ).
x(t), ti ) =
vj (
x(t ), tj )
ui = ui (
x(t ), ti ) ui (
j

15

If x(t ) = x(t), then ui = vi (

x(t ), ti ) vi (
x(t), ti ) 0, since vi (x, ti ) is

non-decreasing in ti . If x(t ) = x(t), then

vj (
x(t ), tj )
vj (
x(t), tj )
vj (
x(t), tj ),
j

where the rst inequality is due to the fact that x(t ) is ecient for t while
x(t) is not, and the second is the result previously derived for the case where
x(t ) = x(t). Thus ui (
x(t), ti ) is non-decreasing in ti for all ti Ti , hence
Eti Ti [ui (
x(t), ti )] is non-decreasing as well.
9.33.
a). In Example 9.7, IR1 (t1 ) = 10 for all t1 and IR2 (t2 ) = 0 for all t2 , which
essentially introduces an additional state D such that v1 (D, t1 ) = 10 and
v2 (D, t2 ) = 0 for all t1 and t2 . Since x(t) > 10 for all t, the allocation rule is
not aected by replacing IR1 (t1 ) = 0 with IR1 (t1 ) = 10. Therefore, the VCG
externality costs inicted by individual 1 to individual 2 are not changed.
However, the externality costs caused by the presence of 2 on 1 are dierent
duo to IR1 = 10. For example, when t = (1, 1), x(t) = S and v1 (S, 1) = 6.
But x1 (1) = D and v1 (D, 1) = 10, hence cV2 CG (1, 1) = 10 6 = 4. Table 3
lists cV2 CG (t) for all t and cV2 CG (t2 ).
Table 3: Values of cV2 CG (t1 , t2 ) and cV2 CG (t2 )
t2

b). c1 =

t1
1
2
3
4
5
6
7
8
9

4
3
2
1
0
1
2
3
4

4
3
2
1
0
1
2
3
0

4
3
2
1
0
1
2
0
0

4
3
2
1
0
1
0
0
0

4
3
2
1
0
0
0
0
0

4
3
2
1
0
0
0
0
0

4
3
2
2
0
0
0
0
0

4
3
4
2
0
0
0
0
0

4
6
4
2
0
0
0
0
0

cV2 CG (t2 )

20
9

16
9

13
9

11
9

10
9

10
9

11
9

13
9

16
9

cV1 CG (t1 )/9 = 10/27, c2 = 40/27, and expected revenue = 50/27.

c). From the Text, 1 = 46/9 and 2 = 34/9. As c1 + c2 > 1 + 2 ,

the desired mechanism runs an expected surplus and can be implemented
16

as follows. The allocation rule: pS (t) = 1 if t1 + t2 10, and pB (t) = 1 if

t1 + t2 > 10. The costs of individual i of type ti are
C1 (t1 ) = c1 (t1 )46/9
c2 (t2 )+40/27(50/274/3)/2 = c1 (t1 )
c2 (t2 )35/9,
C2 (t2 ) = c2 (t2 )+34/9
c1 (t1 )+10/27(50/274/3)/2 = c2 (t2 )
c1 (t1 )+17/27.
d). With IR1 =13, a social state, D=do not build either swimming pool or
bridge, becomes relevant, and x(t) is as follows.

D, if t1 + t2 3;
x(t) = S, if 3 < t1 + t2 10;

B, otherwise.
The VCG costs and expected costs are presented in Tables 4 and 5.
Table 4: Values of cV1 CG (t1 , t2 ) and cV1 CG (t1 )
1

t2
1
2
3
4
5
6
7
8
9

t1

6
7
0
0
0
1
2
3
4

6
0
0
0
0
1
2
3
0

0
0
0
0
0
1
2
0
0

0
0
0
0
0
1
0
0
0

0
0
0
0
0
0
0
0
0

0
0
0
0
0
0
0
0
0

0
0
0
1
0
0
0
0
0

0
0
2
1
0
0
0
0
0

0
3
2
1
0
0
0
0
0

cV1 CG (t1 )

23
9

12
9

3
9

1
9

1
9

3
9

6
9

U1V CG (1) = Et2 T2 [v1V CG (1, t2 )] cV1 CG (1) = 68/9 23/9 = 5,

U2V CG (1) = Et1 T1 [v2V CG (t1 , 1)] cV2 CG (1) = 42/9 23/9 = 19/9.
1 = 13 min{U1V CG (t1 )|t1 T1 } = 13 U1V CG (1) = 8, and 1 = 0 19/9 =
19/9. 1 + 2 = 53/9, while cV1 CG + cV2 CG = 49/81 + 244/81 = 293/81 <
53/9. The IR-VCG mechanism does not run a surplus.
17

Table 5: Values of cV2 CG (t1 , t2 ) and cV2 CG (t2 )

1

t1
1
2
3
4
5
6
7
8
9

t2

0
0
5
4
3
2
2
3
4

0
6
5
4
3
2
2
3
0

7
6
5
4
3
2
2
0
0

7
6
5
4
3
2
0
0
0

7
6
5
4
3
1
0
0
0

7
6
5
4
3
1
0
0
0

7
6
5
5
3
1
0
0
0

7
6
7
5
3
1
0
0
0

7
9
7
5
3
1
0
0
0

cV2 CG (t2 )

23
9

25
9

29
9

27
9

26
9

26
9

27
9

29
9

32
9

9.34. The expected cost in the VCG mechanism is as follows.

qi (ti )cVi CG (t).

cVi CG (ti ) =
ti Ti

The expected costs of other related mechanisms are presented below.

CG
CG
cBB-V
(ti ) = E[
cVi CG (ti ) cVi+1
(ti+1 )]
i

CG
= cVi CG (ti )
qi+1 (ti+1 )
cVi+1
(ti+1 )
ti+1 Ti+1

CG
cIR-V
(ti )
i

CG
cVi+1
,

cVi CG (ti )

E[
cVi CG (ti )

cVi CG (ti )

CG
cVi+1
(ti+1 )

CG
cVi+1

N
1 V CG

(
c
j )]
N j=1 j

N
1 V CG

(
cj
j ).
N j=1

IR-V CG
(ti )
The cost function cB
i (ti ) introduced in the Text on page 474 is simply ci
V CG
IR-V CG
B
CG
(t
(t
)
are
c

(t
)
and
c

(t
),
c

with all i = 0. Clearly, all cBB-V

i)
i
i
i
i
i
i
i
plus a distinct constant.

9.35. Let (pxAi (t), cAi (t)) and (pxBi (t), cBi (t)) be two mechanisms such that
pxAi (ti ) = pxBi (ti ) for all x X and all i. If ui (0|A) = ui (0|B), then cAi (0) =
18


cBi (0), since ui (0|k) = xX pxki (0)vi (x, 0) cki (0), k = A, B, and pxAi (0) =
pxBi (0). That cAi (ti ) = cBi (ti ) follows immediately from Theorem 9.14, which
states that cAi (ti ) cAi (0) = cBi (ti ) cBi (0).
It follows directly that
E[RA ] =

E[
cAi (ti )] =

i=1

E[
cBi (ti )] = E[RB ].

i=1

9.36.
a). Ignoring the zero probability event of t1 = t2 , let the probability assignment
function be pI1 (t) = 1 if t1 > t2 and pI1 (t) = 0 otherwise, where state I
refers to sole ownership by individual 1. Thus the VCG externality costs are
cVi CG (t) = tj if ti > tj , and zero otherwise, i, j = 1, 2, i = j.

cVi CG (ti )

ti

=
o

1
tj dtj = t2i , and UiV CG (ti ) =
2

ti

1
ti dtj cVi CG (ti ) = t2i .
2

1
1
i (i ) = max (i ti t2i ) = i2 .
ti [0,1]
2
2
It is known that E[
cVi CG (t1 )]+E[
cV2 CG (t2 )] = 1/3. For the specied mechanism,
it is required that 12 /2 + (1 1 )2 /2 1/3, or

3
1
3
1

1 +
.
2
6
2
6
With asymmetric ownership shares, it requires greater compensations to
induce the individuals with larger shares to give up the status quo, and
hence is harder to implement an IR and ecient allocation.
b). For N partners with ownership shares i for partner i, the ecient
probability assignment functions are pjj (t) = 1 if tj > ti for all i = j, and
pji (t) = 0 otherwise; and pki (t) = 0 for k = j and all i.
The ecient probability assignment rule allocates the business to the partner
with largest ti of t. Let tI and tII denote the largest and the second largest
19

value, respectively, of t1 , t2 , ..., tN , then cVi CG (t) = tII if ti = tI , cVi CG (t) = 0

otherwise.
ti
N 1 N
V CG
ci (ti ) =
x(N 1)F N 2 (x)f (x)dx =
t .
N i
0
1
N 1
cVi CG (ti )dti =
E[R] =
.
N +1
0
i
ti
1
V CG
Ui
(ti ) =
ti (N 1)F N 2 (x)f (x)dx cVi CG (ti ) = tN
.
N i
0
i (i ) = max (i ti
ti [0,1]

1 N
N 1 NN1
ti ) =
i .
N
N
2N

As (i ) = iN 1 and (i ) = N 11 iN 1 > 0, i (i ) is convex in i , so

is () = i i (i ). Given and , = , let = + (1 ) ,

0 < < 1, then max{i } < max{max{i }, max{i }} and min{i } >
min{min{i }, min{i }}, reecting reduced asymmetry of ownership shares.
And convexity of implies that ( ) ()+(1)( ) max{(),
( )}. In particular, for a perfectly symmetric distribution of shares, i.e.,

such that
i = 1/N for all i, (
) () for all . In conclusion,
greater symmetry in ownership shares reduces subsidies and makes it easier
to implement an ecient allocation.
We have yet to show that there exists a non-empty set A in the (N
1)-dimensional simplex, such that () E[R] for A. Dene (N )
as follows,
N

( N1 ) N 1
1
(
)
= ln
= ln(N + 1) ln N
ln N.
(N ) ln
1
E[R]
N 1
N +1
Expanding ln(N + 1) around N , we obtain
ln(N + 1) = ln N +

1
1 2

(N ),
N
2N 2

where 0 < (N ) < 1. Thus,

(N ) =

1
1 2
1

(N )
ln N.
2
N
2N
N 1
20

As ln N > 1 for N 3, it is clear that (N ) < 0, or (

) < E[R], for
N 3. Weve already found in (a) that (
) < E[R] for N = 2. Therefore,
for N 2, such a set A exists around
. That is, balanced budget can be
implemented for ownership shares A.

21