Data-driven Auction Design III: Learnability of Product Distributions and Strong Revenue Monotonicity
- Prof. Zhiyi Huang, University of Hong Kong
- Time: 2023-09-22 19:00
- Host: Dr. Shaofeng Jiang
- Venue: Room 204, Courtyard No.5, Jingyuan
Abstract
The space of distributions and the space of solutions are equally important in the original formulation of the general learning problem. However, most subsequent research on the generalization of learning problems has focused on the complexity of the solution space, while allowing the distribution space to be arbitrarily complicated. In the auction problem, the bidders' value distributions are independent (otherwise Myerson's auction is no longer optimal in the first place). Is the optimal sample complexity of auctions determined by the complexity/simplicity of the distribution space rather than the solution space?
The last part of this lecture series will introduce two new techniques to answer the above question affirmatively. We will show that product distributions over finite supports are learnable using polynomially many samples, and we will characterize the tight sample complexity for learning them with respect to standard metrics for distributions. Next, we will introduce the concept of strong revenue monotonicity of auctions, which naturally suggests a new notion of "distance" between value distributions tailored for the auction problem. Finally, we will explain how to use the new techniques to determine the sample complexity of all single-parameter auctions and outline how they yield tight or state-of-the-art sample complexity for multi-parameter auctions, optimal stopping problems, etc.
Biography
Zhiyi is an associate professor of Computer Science at the University of Hong Kong. He works broadly on Theoretical Computer Science and Algorithmic Game Theory, with a focus on optimization and decision-making under uncertainty. Before joining HKU, Zhiyi was a postdoc at Stanford University from 2013 to 2014, working with Tim Roughgarden. He obtained his Ph.D. from the University of Pennsylvania under Sampath Kannan and Aaron Roth in 2013. During grad school, Zhiyi interned at Microsoft Research Redmond under Nikhil R. Devanur in the summers of 2011 and 2012. Before that he got a bachelor degree from the first "Yao Class" under Andrew Yao at Tsinghua University in 2008. Zhiyi was the recipient of the Best Paper Awards of FOCS 2020 and SPAA 2015, an Excellent Young Scientists Fund (HK & Macau) by NSFC, an Early Career Award by RGC Hong Kong, and a Morris and Dorothy Rubinoff Dissertation Award.