Title: Prior-Independent Optimal Auctions

Auctions are widely used in practice. While also extensively studied in the literature, most of the developments rely on significant assumptions about common knowledge on the seller and buyers' sides. In this work, we study the fundamental problem of designing optimal prior-independent selling mechanisms. In particular, the seller faces buyers whose values are drawn from an unknown distribution, and only knows that the distribution belongs to a particular class. We analyze a competitive ratio objective, in which the seller attempts to optimize the worst-case fraction of revenues garnered compared to those of an oracle with knowledge of the distribution. Our results are along two dimensions. We first characterize the structure of optimal mechanisms. Leveraging such structure, we then establish tight lower and upper bounds on performance, leading to a crisp characterization of optimal performance for a spectrum of families of distributions. In particular, our results imply that a second price auction is an optimal mechanism when the seller only knows that the distribution of buyers has a monotone increasing hazard rate, and guarantees at least 71.53% of the optimal revenue against any distribution within this class. Furthermore, a second price auction is near-optimal when the class of admissible distributions is that of those with increasing virtual values (aka regular). Under this class, it guarantees a fraction of 50% of optimal revenues and no mechanism can guarantee more than 55.6%. (joint work with Amine Allouah)

 

Link to paper: https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3124738

 

Bio:

Omar Besbes is an Associate Professor in the Decision, Risk, & Operations division at the Graduate School of Business, Columbia University. His primary research interests are in the area of data-driven decision-making, with a focus on applications in pricing and revenue management, e-commerce, online advertising, and service systems. His research has been recognized by various prizes including the 2012 INFORMS Revenue Management and Pricing Section prize, the 2013 M&SOM best paper award and the 2017 M&SOM young scholar award. He serves on the editorial boards of Operations Research and Management Science.

Omar is a graduate of Ecole Polytechnique (France) and received a M.Sc. from Stanford University in 2000 and a Ph.D. from Columbia University in 2008. Before joining Columbia, he was on the faculty at the Wharton School, University of Pennsylvania.