1EE228a - Lecture 21 - Spring 2006Auctions and VCG AllocationGiven by Prof. Jean Walrand (wlr@eecs); scribed by Jingyi Shao (shao14@eecs)AbstractIn this lecture, we study several types of auctions, and we introduce the Envelope Theorem (E.T.) to analyze the payoffsfor the auctions. The expected payoff in each case is found to be the expectation of the second highest valuation. The Vickrey-Clarke-Grove (VCG) allocation mechanism is used in a generalized scenario of the auctions, and it produces a dominant strategywith the resulting Nash Equilibrium also being efficient. Finally, we discuss some applications of auctions to network Quality ofService (QoS) pricing.I. INTRODUCTIONAuction is a way to sell an item. It can be formulated as a bilateral combinatorial problem or game, in which each biddertries to maximize some payoff function according to the rules of the auction. For example, in real estate, a house may be soldthrough an auction. The bidders or buyers, Alice and Bob, have their own valuation of the house, v1and v2, respectively, andthey will place their bids, b1and b2according to the auction rules, which will decide who wins the bid (usually the one with thehigher or the highest bid), and the amount the winner shall pay for the house. Note that neither the valuation nor the bid of eachperson is necessarily the same as the ”true worth” (in some sense) of the item.In this lecture, we first study two kinds of auctions, sealed bid with first price and sealed bid with second price. We introducethe Envelope Theorem to study the payoffs for the auctions, and show both of the expected payoffs in an incomplete but symmetricrelaxation of the auctions is the expected value of the second highes valuation.Then, we look at the Vickrey-Clarke-Grove (VCG) allocation mechanism for general auctions, and discuss applications of itto network Quality of Service (QoS) pricing.II. AUCTIONSThere are many forms of auctions with different rules. Different auctions may give different strategies and even differentpayoffs. In this section, we will look at two most basic types of auctions.A. Sealed bid with first priceIn the sealed bid with first price type of auction, the bidders place their bids once simultaneously (by putting their bids insealed envelopes. The bids will be examined by some neutral party to determine the winner). The bidder with the highest bidwins the auction, and he (or she) pays the highest bid price (namely his (or her) own bid) for the sale item.Suppose Alice has valuation of the item, v1, and makes bid, b1, the net payoff of Alice is (v1− b1)1{b1> b2}, where 1{}is the indication function and b2is the only other bid, say by Bob who has valuation, v2.In this type of auction, there is no dominate strategy. The best bid for Alice will depend on Bob’s bid, and vice versa.b1= min(v1, b2+ ²)b2= min(v2, b1+ ²)where ² is some small positive number. The intuition is that Alice wants to outbid Bob by just a small amount provided that herbid does not exceeds her valuation; and vice versa. There is, however, a unique Nash Equilibrium.b1= min(v1, v2+ ²)b2= min(v2, v1+ ²)Fig. 1 shows an example of the curves b2(b1) and b1(b2), and the resulting Nash Equilibrium point.Since Alice and Bob’s personal valuations are not known to the other person, nor are their bids (since the bids were sealed)it is not possible to make the best bids, nor is it practical to achieve the Nash Equilibrium. To obtain a practical solution, wecan modify or relax the assumption a bit. Each of the bidders instead of having a deterministic valuation, has a range of possiblevaluation values according to some probability distribution. We will further assume that the valuation distributions of the biddersare i.i.d. (independent and identically distributed) with cdf (cumulative distribution function) F () and pdf (probability densityfunction) f (). We call this the incomplete information but symmetric relaxation. Let Z = max(V1, V2, ..., Vn), where there aren bidders and Vi(a random variable) is the valuation of bidder i.Theorem 1: Alice (bidder 1) should bid b(V1) = E[Z|Z ≤ V1]. In particular, the expected payoff is the expected value ofthe second highest valuation.For example, assume Alice and Bob bid on a house, and their valuation is uniformly distributed on [1, 2] (i.i.d.). Alice shouldbid1+v2where v is her valuation. If there are n bidders including Alice, she should bid1+(n−1)vn.Before we prove Theorem 1, we introduce the Envelope Theorem, which will be used in later proofs.2Fig. 1. The trade-off of payoff curves.Theorem 2: (Envelope Theorem) Let F (x, y) be some differentiable function. Assume H(x) = maxyF (x, y) = F (x, y(x)).ThenddxH(x) =∂∂xF (x, y)|y=y(x)Fig. 2 shows a picture of the Envelope Theorem (E.T.), which says the slope of H(x) (the black curve) is the same as thepartial derivative with respect to x of F (x, y) evaluated at the maximum point over y for each x.Fig. 2. Illustration of the Envelope Theorem.We won’t prove the Envelope Theorem here, and we will just look at some examples that demonstrate it.Example 1:Let F (x, y) = x2− y2+ 2xy. Then H(x) = maxyF (x, y) = 2x2= F (x, x). Note that H0(x) = 4x. Also,∂∂xF (x, y) =2x + 2y. Hence,∂∂xF (x, y)|y=x= 4x = H0(x).Example 2:Let F (x, y) = xf(y) − w y where y can be interpreted as quantity of input, x as output price, w as input cost, and f(y) asquantity of output. Then H(x) = maxyF (x, y) = F (x, y(x)) where xf0(y(x)) = w. Hence H(x) = xf (y(x)) − wy(x), sothatH0(x) = f(y(x)) + xf0(y(x))y0(x) − wy0(x)= f(y(x)) (1)Also,∂∂xF (x, y) = f (y). Hence,∂∂xF (x, y)|y=y(x)= H0(x).Example 3:Let F (x, y, w) = xf (y) − wy. Then H(x, w) = maxyF (x, y, w) = F (x, y(x, w), w) where xf0(y(x, w)) = w.Hence H(x, w) = xf(y(x, w)) − wy(x, w), so that∂∂xH(x, w) = f(y(x, w)) + xf0(y(x, w))y0(x, w) − wy0(x, w).Also∂∂xF (x, y, w) = f(y).Hence,∂∂xF (x, y, w)|y=y(x)=∂∂xH(x, w).3Similarly,∂∂wF (x, y, w)|y=y(x)= −y(x, w) and∂∂wH(x, w) = xf0(y(x, w))∂∂wy(x, w) − y(x, w) − w∂∂wy(x, w) =−y(x, w), so that∂∂wH(x, w) =∂∂wF (x, y, w)|y=y(x).We now prove Theorem 1.Proof: Let B = max(b2, ..., bn).Alice chooses b1= b to maximize F (b, v) = (v − b)P (B ≤ b). Her payoff is H(v) = maxbF (b, v). Hence, by E.T.,H0(v) = P (B ≤ b)|b=b(v)= P (Z ≤ v) since the person with higher valuation can place higher bid and still have positivepayoff.Thus, H(v) =Rv0P (Z ≤ v)dx = (v − b(v))P (Z ≤ v),
View Full Document
Unlocking...