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