Optimal Mechanism for Auctions: Myerson's Insights
Exploring the optimal mechanism for auctions, focusing on Myerson's Auction for distributions with strictly increasing virtual valuations. Understand the key concepts and strategies for maximizing auctioneer revenue in a Bayes-Nash equilibrium. Discover the characterization of Bayesian Nash Equilibrium (BNE) and the generalization version of Myerson's optimal mechanism that removes the requirement of increasing virtual valuations. Explore the new variables in quantile space and dive into payment and allocation functions.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Auction Seminar Optimal Mechanism Presentation by: Alon Resler Supervised by: Amos Fiat
Review Myerson Auction for distributions with strictly increasing virtual valuation: Solicit a bid vector from the agents. Allocate the item to the bidder with the largest virtual value , if positive, and otherwise, do not allocate. Charge the winning bidder i, if any, the minimum value she could bid and still win, i.e. 1. 2. ( ) ib i 3. ( ) 1max(0,{ ( )} b j i i j j 2
Review we defined the virtual value of agent i to be: 1 ( ) F v = ( : ) i v i v i v i i ( ) f i i We saw that when the bidders values drawn from independent distributions with increasing virtual valuations the Myerson auction is optimal, i.e. it maximized the expected auctioneer revenue in Bayes-Nash equilibrium 3
Review 4
Review Characterization of BNE: Let A be an auction for selling a single item, where bidder i s value is drawn independently from . If is a BNE, then for each agent i: The probability of allocation is monotone increasing in The utility is a convex function of with ( ) i i u v iv u v = iF iV ( ) 1,..., n iv ( ) a v 1. i i iv 2. ( ) ( ) a z dz i i i 0 The expected payment is determined by the allocation probabilities: ( ) i i p v v a v = 3. v v i i i = ( ) ( ) ( ) a z dz za z dz i i i i 0 0 5
Today issues: We will show a generalization version of Myerson s optimal mechanism, that doesn t require that virtual valuations be increasing. We will see one examples 6
Optimal Mechanism Our goal now is to derived the general version of Myerson s optimal mechanism, that doesn t require that virtual valuations be increasing. We will a change in variables to quantile space, and define: ) ( : v F q = = 1q ( : ) q ( ) v F = ( ): p q ( ( )) p v q The payment function: = ( ): a q ( ( )) a v q The allocation function: ( ) a F v f v = ( ( )) ( ) a v Notice that: 7
Optimal Mechanism Given any and we have: 0 v = ( ) F v q 0 0 v 0 = ( ) = ( p q ) ( ) p v a v vdv 0 0 0 v q 0 0 a F v vf v dv a q v q dq = = ( ( )) ( ) ( ) ( ) 0 0 = ( ) f v dv dq = ( ) q F v ( ) a F v f v = ( ( )) ( ) a v 8
Optimal Mechanism From this formula, we derive the expected revenue from this bidder. Let Q be the random variable representing this bidder s draw from the distribution in quantile space, i.e., Q=F(V) [Notice that ]. Then, 0 Q 1 q 1 0 = a q v q dqdq [ ( )] p Q ( ) ( ) 0 0 0 Reversing the order of integration, we get 9
Optimal Mechanism 1 1 a q v q [ ( )] = p Q ( ) ( ) dq dq 0 0 q 1 1 a q a q R q dq = = ( )(1 ) ( ) q v q dq ( ) ( ) 0 0 = ( ) (1 ) ( ) q v q R q Where is called the revenue curve. It represents the expected revenue to a seller from offering a price of v(q) to a buyer whose value V is drawn from F. 10
Optimal Mechanism Integrating by parts 1 1 a q R q dq ( ) [ ( )] p Q = ( ) ( ) R q a q ( ) 0 0 1 a q R q dq ( ) a Q R Q ( )] = = ( ) [ ( ) 0 iF , o h Explanation: R(1) = 0 and because is on we get, (0) ( (0)) a a v a F = = i = = 1 ( (0)) (0) 0 a 11
Optimal Mechanism To summarizing, we proved a lemma: Consider a bidder with value V drawn from distribution F, with Q=F(V). Then his expected payment in a BIC auction is a Q R Q ( )] [ ( )] p Q [ ( ) ( )] = = a Q R Q [ ( ) Where is the revenue curve. ( ) (1 ) ( ) R q q v q = 12
Optimal Mechanism = ( ) Lemma: let Then, q F v 1 ( ) F v = = ( ) v '( ) v R q ( ) f v Proof: d dq d dq = = + '( ) ((1 ) ( )) q v q (1 ) ( ) v q R q v q = ( ) q F v From and we get: ( ) ( ) v q F q = 1 1 ( ) F v = + v ( ) f v 13
Optimal Mechanism As we discussed in David s class (two weeks ago), allocation to the bidder with the highest virtual value (or equivalently, the largest R (q)) yields the optimal auction, provided that virtual valuations are increasing. Hedva Observation: = Let be the revenue curve with ( ) (1 ) ( ) R q q v q = . Then is (weakly) increasing ( ) F v ( ) '( ) v R q = q if and only if R(q) is concave. (a function is concave if it s derivative is increasing ). 14
Optimal Mechanism To derived an optimal mechanism for the case when R(q) is not concave envelope of ( ) R q ( ) R q ( ) R q ( ) g q Definition: is the infimum over concave functions such that for all . ( ) ( ) g q R q q ( ) R ( ) R ( ) R [0,1] Passing from to is called ironing. can also be interpreted as a revenue curve when randomization is allowed. Definition: The iron virtual value of bidder i with value is: ( ) i v q ( ) i i v R q = ( ) i 15
Myerson auction with ironing Now we can replace virtual values with ironed virtual values to obtain an optimal auction even when virtual valuations are not increasing. Definition: The Myerson auction with ironing: Solicit a bid vector b from the bidders. 1. Allocate the item to the bidder with the largest value of ( ) i 2. ib , if positive, and otherwise do not allocate. Charge the winning bidder i, if any, her threshold bid, the 3. minimum value she could bid and still win. 16
Optimal Mechanism Theorem: The Myerson Auction described above is optimal, i.e., it maximized the expected auctioneer revenue in Bayes-Nash equilibrium when bidders values are drawn from independent distribution. Proof:The expected profit from a BIC auction is = R Q = p Q a Q ( ) ( )( ( )) i i i i i i ( i a Q R Q = ) ( ) i i i i 17
Proof cont. + a Q a Q ( )( ' ( i )) '( ) ( ) ( ) R Q R Q R Q i i i i i i i i i i i (add and subtract ). a Q = a Q ( )( ' ( R )) ( )( ( )) Q R Q i i i i i i i i i i a Q R Q ( )] [ ( ) ( )] = a Q R Q [ ( ) 18
Proof cont. Consider choosing a BIC allocation rule to maximize the first term: ( ) ) ( ( i ,..., )( ) . Q Q R Q 1 n i i i This is optimized by allocating to the bidder with the largest , if positive. Moreover, because is concave, this is an increasing allocation rule and hence yields a dominant strategy auction. ( ) = ( ) v R q i i i R ( ) 19
Proof cont. Notice also that iR () is constant in each interval of non- concavity of , and hence in each such interval () R ( ) ia q ia q = is constant and thus . ( ) 0 Consider now the second term: In any BIC auction, () ia ia q ( ) 0 must be increasing and hence for all q. But for all q and hence the second term is non- ( ) ( ) R q R q positive. Since the allocation rule that optimized the first term has whenever , it ensures that the second ( ) 0 a q = ( ) R q R q ( ) term is zero, which is best possible. + a Q a Q ( )( ' ( i )) '( ) ( ) ( ) R Q R Q R Q i i i i i i i i i i i 20
The advantage of just one more bidder One of the downside of implementing the optimal auction is that it requires that the auctioneer know the distributions from which agents values are drawn. The following result shows that in instead of knowing the distribution from which n independently and identical distributed bidders are drawn, it suffices to add just one more bidder into the auction. 21
Theorem Let F be a distribution for which virtual valuations are increasing. The expected revenue in the optimal auction with independently and identical distributed bidders with values drawn from F is upper bounded by the expected revenue in a Vickrey auction with n+1 independently and identical distributed bidders with values drawn from F. 22
Proof The optimal (profit-maximizing) auction that is required to sell the item is the Vichrey auction (this follows from the lemma we saw in previous class, which says that for any auction, the expected profit is equal to the expected virtual value of the winner). Second, observe that one possible n+1 bidder auction that always sells the item consist of, first, running the optimal auction with n bidders, and then, if the item is unsold, giving the item to the n+1 st bidder for free. 23
First example: War of Attrition 24
War of attrition (Reminder) In Liran s class we considered the war of attrition: this single item auction allocates the item to the player that bids the highest, charges the winner the second-highest bid, and charge all others players their bid. Notice that in this auction the bidders decides at the beginning of the game when to drop out. 25
War of attrition (Reminder) Formulas that we derived in Liran s class that we will need for today: Let be a symmetric strictly increasing equilibrium strategy, Then: Expected payment of an agent in a war-of-attrition auction in which all bidders use is And 26
Dynamic war of attrition A more natural model is for bidders to dynamically decide when to drop out. The last player to drop out is then the winner of the item. With two players this is equivalent to the model discussed in Liran s class: The equilibrium strategy := how long a player with ( ) v value v waits before dropping out. 27
Dynamic war of attrition v v ( ) ( ) F w f w = = ( ) v ( ) w dw wh w dw satisfies: 1 0 0 ( ) f w ( ) ( ) f w Where is the hazard rate of ( ) 1 ( ) F w F w = = h w the distribution F. (it followed from the equilibrium we found in Liran s class: ). 28
Dynamic war of attrition We rederive this here without the use of revenue equivalence. To this end, assume that the opponent plays . The agent s utility from playing when his value is v is: () ( ) w w = ( ) ( ) F w ( ) ( ) z f z dz ( | ) u w v ( ) vF w w 0 Differentiating with respect to w, we have: ( | ) u w v w vf w = ( ) w = + ( ) ( ) f w ( ) ( ) w f w ( ) ( ) vf w w F w ( ) w ( ) ( ) F w 29
Dynamic war of attrition = w v For this to be maximized at , we must have = ( ) ( ) ( ) v vf v F v implying v v ( ) ( ) f w F w 0 0 = = ( ) v ( ) wh w dw w dw 30
Dynamic war of attrition ( ) v With three players strategy has two component, and ( , ) y v . ( ) v For a player with value v, he will drop out at time if no one else dropped out earlier. Otherwise, if another player dropped out at time + ( ) y ( ) v , our player will continue until time ( ) y ( , ) y v . 31
Dynamic war of attrition The case of two players applied at time y implies that in equilibrium v y v zh z dz = ( , ) ( ) y ( )1 f z Since the update density has the same hazard ( ) F y z y rate as f. Unfortunately there is no equilibrium once there are three players 32
Dynamic war of attrition To see this, suppose that players 2 and 3 are playing and , and player 1 with value v plays (, ) ( ) v () ( ) v instead of . Then 2 2 0 ( | ) u v v ( | ) v ( ) ( ( ) F v ( )) u v C v v 2 Since with probability , the other two players outlast player ( ) F v ( ) v ( ) v 1 and then he pays an additional for naught. 2 v 2 ( ) f z dz C And with probability for some constant C, v both of the others players drop out first. 33
Dynamic war of attrition Thus, it must be that 2 2 ( ) v ( ) ( ) v C F v And for any k we have: C C v k v k 2 2 ( ) ( ) 2 2 ( ) ( ) F v k F v (since is non-increasing function). ( ) F v 34
Dynamic war of attrition / v Summing from k=0 to : v v ( ) ( + ) 2 ) + + = 1) ) ( ) v ( ) ( ) ( ... ( ( ( ) v v v v v v ( ) = = 2 2 2 ( ) v (0) ( ) ( ) CF v CF v v = ( ) v 0 2 ( ) v ( ) CF v v And hence: Finally, we observe that is not equilibrium since a ( ) v = 0 player, knowing that the other players are going to drop out immediately, will prefer to stay in. 35
