COMP326/COMP559 Tutorial Sheet 8 Solutions
1. Consider the second price auction with a single item and two bidders with valuations
v1, v2 ∼ U [0, 1]. Fix the bid, b1, of bidder 1. Suppose that bidder 2 bids truthfully.
(a) Let X = X(b1) be the random variable representing the payment for bidder 1 (the
randomization comes from v2 ∼ U [0, 1]). Compute E[X].
Hint: use E[X] =
∫∞
0 Pr[X ≥ z]dz.
(b) This is a truthful auction. Compute p1(b1) = b1 · x1(b1)−
∫ b1
0 x1(z)dz.
Hint: notice that x1(z) = Pr[v2 ≤ z].
If your computations are correct the two (expected) payments should be the same.
Solution:
(a) We set b2 = v2 because bidder 2 bids truthfully. Then,
X =
{
v2, if v2 ≤ b1
0, if v2 > b1
Pr[X ≥ z] =
{
b1 − z, if 0 ≤ z ≤ b1
0, if z > b1
0 1b1
z z
Figure 1: b1 is fixed. Those are possible positions of z.
For the computation of Pr[X ≥ z], notice that if z > b1, there is no way that bidder
1 pays at least z and therefore Pr[X ≥ z] = 0 in that case. If z ≤ b1, the situation
that the payment of bidder 1 is at least z appears when v2 ≤ b1 (so bidder 1 wins)
and v2 ≥ z (so that his payment is not less than z) and overall, the probability that
v2 is between z and b1 is b1−z. Having Pr[X ≥ z], we can compute E[X] as follows:
E[X] =
∫ ∞
0
Pr[X ≥ z]dz =
∫ b1
0
(b1 − z)dz =
(
b1z − z
2
2
)∣∣∣∣b1
0
=
b21
2
.
(b) It is x1(z) = Pr[v2 ≤ z] = z, for 0 ≤ z ≤ 1, and x1(z) = 1, for z > 1. Then we have,
p1(b1) = b1 · x1(b1)−
∫ b1
0
x1(z)dz = b
2
1 −
∫ b1
0
zdz = b21 −
z2
2
∣∣∣∣b1
0
=
b21
2
.
2. (Optional) Consider the second price auction with reserve price 12 with a single item and
two bidders with valuations v1, v2 ∼ U [0, 1]. Fix the bid, b1, of bidder 1. Suppose that
bidder 2 bids truthfully.
(a) Let X = X(b1) be the random variable representing the payment for bidder 1 (the
randomization comes from v2 ∼ U [0, 1]). Compute E[X].
Hint: use E[X] =
∫∞
0 Pr[X ≥ z]dz.
1
(b) This is a truthful auction. Compute p1(b1) = b1 · x1(b1)−
∫ b1
0 x1(z)dz.
Hint: notice that x1(z) = Pr[v2 ≤ z] only if z ≥ 12 , otherwise it is 0.
If your computations are correct the two (expected) payments should be the same.
Solution:
(a) We set b2 = v2 because bidder 2 bids truthfully. It is easy to check that if b1 <
1
2
then E[X] = p1(b1) = 0. So, we consider the case that b1 ≥ 12 . Then,
X =

1
2 if v2 <
1
2
v2, if
1
2 ≤ v2 ≤ b1
0, if v2 > b1
Pr[X ≥ z] =

b1 if z <
1
2
b1 − z, if 12 ≤ z ≤ b1
0, if z > b1
0 11
2
b1
z z z
Figure 2: b1 is fixed. Those are possible positions of z.
For the computation of Pr[X ≥ z], notice that if z > b1, there is no way that bidder
1 pays at least z and therefore Pr[X ≥ z] = 0 in that case. If z ≤ 12 , the payment of
bidder 1 is always at least z as long as v2 ≤ b1, so Pr[X ≥ z] = b1 in that case. If
1
2 < z ≤ b1, the payment of bidder 1 is at least z when z ≤ v2 ≤ b1 (so bidder 1 wins
and pays v2 ≥ z) and the probability that v2 is between z and b1 is b1 − z. Having
Pr[X ≥ z], we can compute E[X] as follows:
E[X] =
∫ ∞
0
Pr[X ≥ z]dz =
∫ 1
2
0
b1dz+
∫ b1
1
2
(b1−z)dz = b1z|
1
2
0 +
(
b1z − z
2
2
)∣∣∣∣b1
1
2
=
b21
2
+
1
8
.
(b) Note that
x1(z) =

0 if z < 12
z if 12 ≤ z ≤ 1
1 if z > 1
Recall that we have assumed that b1 ≥ 12 , so we have,
p1(b1) = b1 · x1(b1)−
∫ b1
0
x1(z)dz = b
2
1 −
∫ b1
1
2
zdz = b21 −
z2
2
∣∣∣∣b1
1
2
=
b21
2
+
1
8
.
3. Apply Myerson’s Optimal mechanism to the case of a single item and a single bidder with
valuation v which is drawn from the uniform distribution in [0, 2], i.e. v ∼ U [0, 2]. What
is the profit/revenue in this case?
What do you expect the Myerson’s Optimal mechanism to be in the same setting where
v ∼ U [0, 1]? What is the profit/revenue in this case?
Solution: First note that the cumulative distribution of v is F (z) = 12z, for z ∈ [0, 2],
and the probability density function of v is f(z) = 12 , for z ∈ [0, 2]. Then we can compute
the virtual valuation as follows:
φ(v) = v − 1− F (v)
f(v)
= v − 1−
1
2v
1
2
= 2v − 2 .
2
Then we run VCG. VCG gives the item to the bidder only when 2v− 2 ≥ 0, so only when
v ≥ 1. In the case that v ≥ 1, VCG payment is p′ = 0 which results in an actual payment
of
p = φ−1(p′) = φ−1(0) = 1 .
This is the auction with reserve price 1. If X is the random variable representing the
profit, X = 0 if v < 1 and X = 1 if v ≥ 1. Moreover, Pr[v ≥ 1] = 1− F (1) = 12 .
E[X] = 1 · Pr[v ≥ 1] = 1
2
.
If v ∼ U [0, 1], the Myerson’s Optimal mechanism is the auction with reserve price 12 . The
profit is 14 as we have seen in the lectures.
References
[1] N. Nisan, T. Roughgarden, E. Tardos, and V.V. Vazirani. Algorithmic Game Theory. Cam-
bridge University Press, 2007.
3

欢迎咨询51作业君