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作业君