Algorithmic Game Theory Lecture on Prophet Inequality and Auction Design
In this lecture on Algorithmic Game Theory, Mingfei Zhao discusses the Prophet Inequality and its application to single-item auctions. The lecture covers the concept of Prophet Inequality, strategies to guarantee expected payoffs, and different auction designs such as the Bulow-Klemperer Theorem and Prior-Independent Auctions. It also explores the challenge of designing auctions when bidder distributions are unknown, emphasizing the importance of prior-independent auction design.
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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Comp/Math 553: Algorithmic Game Theory Lecture 15 Mingfei Zhao
Menu Recap: Prophet Inequalities Bulow-Klemperer Theorem Single Sample
Prophet Inequality Prophet Inequality [Krengel-Sucheston-Garling 79]: There exists a strategy guaranteeing: expected payoff 1/2 E[maxi i]. In fact, a threshold strategy suffices. - Proof: On board; proof by Samuel-Cahn 1984. - Remark: Our lower-bound only credits units of value when more than one prize is above . This means that factor of applies even if, whenever there are multiple prizes above the threshold, the strategy picks the smallest one.
Application to Single-item Auctions (contd) Here is a specific auction whose allocation rule satisfies (*) : 1. Set reserve price ri = i-1 ( ) for each bidder i. 2. Give the item to the highest bidder i who meets her reserve price (if any), and charge him the maximum of his reserve ri and the second highest bid. Interesting Open Problem:How about anonymous reserve? We know it s between [1/4, 1/2], can you pin down the exact approximation ratio? Another auction whose allocation rule satisfies (*) is the following sequential posted price auction: 1. Visit bidders in order 1, ,n 2. Until item has not been sold, offer it to the next bidder i at price i-1( )
Prior-Independent Auctions
Another Critique to the Optimal Auction What if bidder distributions are unknown? When there are enough past data, it may be reasonable to assume that the distributions have been learned. But, if the market is thin, we may not be confident about bidders distributions. Can we design auctions that do not use any knowledge about the distributions, but perform almost as well as if they knew everything about the distributions? Active research agenda, called prior-independent auction design.
Bulow-Klemperer Theorem [Bulow-Klemperer 96] Consider any regular distribution F and integer n : Remarks: 1. Vickrey auction is prior-independent 2. Theorem implies that more competition is better than finding the right auction format.
Proof of Bulow-Klemperer Consider another auction M with n+1 bidders: 1. Run Myerson on the first n bidders. 2. If the item is unallocated, give it to the last bidder for free. This is a DSIC mechanism. It has the samerevenue as Myerson s auction with n bidders. It s allocation rule always gives out the item. Vickrey Auction also always gives out the item, but always to the bidder who has the highest value (also with the highest virtual value). Vickrey Auction has the highest virtual welfare among all DSIC mechanisms that always give out the item!
Bulow-Klemperer Theorem [Bulow-Klemperer 96] Consider any regular distribution F and integer n : Corollary: Consider any regular distribution F and integer n :
Prior Independent vs. Single Sample Consider the auction with single item and single bidder. What can mechanism designer do if he has no information about distribution? Assume there is a single sampleof the bidder s value distribution. Using this sample as a reserve price gives at least half of the optimal revenue if the distribution is regular! (proof on board) For multiple non-i.i.d. bidders, if there is a single sample for each bidder, Vickrey with reserve gives good approximation to optimal revenue (not shown here).
