Report

COMP/MATH 553 Algorithmic Game Theory Lecture 5: Myerson’s Optimal Auction Sep 17, 2014 Yang Cai An overview of today’s class Expected Revenue = Expected Virtual Welfare 2 Uniform [0,1] Bidders Example Optimal Auction Revelation Principle Recap S1(b1 ) b1 b2 . . . . . . S1( ) S2( ) . . . . . . S2(b2 ) bn S n( ) Sn(bn) Original Mechanism M x(s1(b1), s2(b2),...,sn(bn)) New Mechanism M’ Revenue Maximization Bayesian Analysis Model A single-dimensional environment, e.g. single-item The private valuation vi of participant i is assumed to be drawn from a distribution Fi with density function fi with support contained in [0,vmax]. We assume that the distributions F1, . . . , Fn are independent (not necessarily identical). In practice, these distributions are typically derived from data, such as bids in past auctions. The distributions F1 , . . . , Fn are known in advance to the mechanism designer. The realizations v1, . . . , vn of bidders’ valuations are private, as usual. Revenue-Optimal Auctions [Myerson ’81 ] Single-dimensional settings Simple Revenue-Optimal auction What do we mean by optimal? Step 0: What types of mechanism do we need to consider? In other words, optimal amongst what mechanisms? Consider the set of mechanisms that have a dominant strategy equilibrium. Want to find the one whose revenue at the dominant strategy equilibrium is the highest. A large set of mechanisms. How can we handle it? Revelation Principle comes to rescue! We only need to consider the directrevelation DSIC mechanisms! Expected Revenue = Expected Virtual Welfare Revenue = Virtual Welfare [Myerson ’81 ] For any single-dimensional environment. Let F= F1 × F2 × ... × Fn be the joint value distribution, and (x,p) be a DSIC mechanism. The expected revenue of this mechanism Ev~F[Σi pi(v)]=Ev~F[Σi xi(v) φi (vi)], where φi (vi) := vi- (1-Fi(vi))/fi(vi) is called bidder i’s virtual value (fi is the density function for Fi). Myerson’s OPTIMAL AUCTION Two Bidders + One Item Two bidders’ values are drawn i.i.d. from U[0,1]. Vickrey with reserve at ½ • If the highest bidder is lower than ½, no one wins. • If the highest bidder is at least ½, he wins the item and pay max{1/2, the other bidder’s bid}. Revenue 5/12. This is optimal. WHY??? Two Bidders + One Item Virtual value for v: φ(v)= v- (1-F(v))/f(v) = v- (1-v)/1= 2v-1 Optimize expected revenue = Optimize expected virtual welfare!!! Should optimize virtual welfare on every bid profile. For any bid profile (v1,v2), what allocation rule optimizes virtual welfare? (φ(v1), φ(v2))=(2v1-1, 2v2-1). • If max{v1,v2} ≥ 1/2, give the item to the highest bidder • Otherwise, φ(v1), φ(v2) < 0. Should not give it to either of the two. This allocation rule is monotone. Revenue-optimal Single-item Auction Find the monotone allocation rule that optimizes expected virtual welfare. Forget about monotonicity for a while. What allocation rule optimizes expected virtual welfare? Should optimize virtual welfare on every bid profile v. - max Σi xi(v) φi (vi). , s.t Σi xi(v) ≤ 1 Call this Virtual Welfare-Maximizing Rule. Revenue-optimal Single-item Auction Is the Virtual Welfare-Maximizing Rule monotone? Depends on the distribution. Definition 1 (Regular Distributions): A single-dimensional distribution F is regular if the corresponding virtual value function v- (1-F(v))/f(v) is nondecreasing. Definition 2 (Monotone Hazard Rate (MHR)): A single-dimensional distribution F has Monotone Hazard Rate, if (1-F(v))/f(v) is non-increasing. Revenue-optimal Single-item Auction What distributions are in these classes? - MHR: uniform, exponential and Gaussian distributions and many more. - Regular: MHR and Power-law... - Irregular: Multi-modal or distributions with very heavy tails. When all the Fi’s are regular, the Virtual Welfare-Maximizing Rule is monotone! Two Extensions Myerson did (we won’t teach) What if the distributions are irregular? - Point-wise optimizing virtual welfare is not monotone. - Need to find the allocation rule that maximizes expected virtual welfare among all monotone ones. Looks hard... - This can be done by “ironing” the virtual value functions to make them monotone, and at the same time preserving the virtual welfare. We restrict ourselves to DSIC mechanisms - Myerson’s auction is optimal even amongst a much larger set of “Bayesian incentive compatible (BIC)” (essentially the largest set) mechanisms. - For example, this means first-price auction (at equilibrium) can’t generate more revenue than Myerson’s auction. Won’t cover them in class. - Section 3.3.5 in “Mechanism Design and Approximation”, book draft by Jason Hartline. - “Optimal auction design”, the original paper by Roger Myerson.