Speaker: Prof. Zhiyi Huang, Department of Computer Science, University of Hong Kong

Time: 19:00 p.m., September 18, 2023, GMT+8

Venue: Jingyuan No.5 Campus, Room 204

Abstract:

The celebrated optimal auction by Myerson (1981) relies on fine-grained knowledge of the bidders' value distributions. In reality, we can at best estimate such distributions from the available data. Is it possible to find a near-optimal solution despite the uncertainty of the distribution? If so, how much data is needed?

This is the first part of a three-lecture series on data-driven auction design. We will first introduce the sample complexity model for auction design proposed by Cole and Roughgarden (2014). Then, we will cover some basic tools, including several standard inequalities from statistics and information theory. Finally, we will explain how to use these basic tools to determine the optimal sample complexity (up to logarithmic factors) for optimal auction/pricing in the simplest single-item single-bidder case.

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.

Source: Center on Frontiers of Computing Studies