Speaker

Andrew Chi-Chih Yao (Tsinghua University)

　　Title

A Simple O(1)-Approximate Maximal Revenue Auction 

　　Time

　　Venue

N204

　　Abstract

 It is a challenging open problem whether there is a simple mechanism for n-bidder k-item auctions that can always achieve constant-approximate maximal revenue. In this talk, we resolve the question in the affirmative.  The approach we employ also leads to other interesting results on auctions, such as the power of randomization, and the relation between Bayesian and dominant strategy optimal revenues.  The results apply to all distributions, regular or irregular. 

　　Affiliation

Andrew Chi-Chih Yao is a member of the US National Academy of Sciences, the American Academy of Arts and Sciences, and the Chinese Academy of Sciences. He received many honors and awards such as the George Polya Prize and the Donald Knuth Prize. In 2000, he received the A.M. Turing Award for outstanding contributions to the theory of computation, including pseudo random number generation, cryptography, and communication complexity.