Huang Zhiyi, Associate Professor of the Department of Computer Science, the University of Hong Kong, will give a lecture entitled “Strong Revenue (Non-)Monotonicity of Single-parameter Auctions” from 2:00 to 3:30 p.m. on June 7th.

This is one of the lecture series hosted by the Gaoling School of Artificial Intelligence, Renmin University of China (RUC). The lecture will be held online through Tencent Meeting (ID: 436-538-314).

Introduction:

Huang 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, and dabbles in the theoretical aspects of related fields, including Machine Learning, and Computer Networks. Since joining HKU in 2014, Zhiyi has received the Early Career Award from the Research Grant Council of Hong Kong in 2014, and the Best Paper Award of SPAA in 2015. Before joining HKU, he 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, and received the Morris and Dorothy Rubinoff Dissertation Award. Before that, Zhiyi was the recipient of the Simons Graduate Fellowship in Theoretical Computer Science from 2012 to 2013, and interned at Microsoft Research Redmond under Nikhil R. Devanur in the summers of 2011 and 2012. Prior to his Ph.D. studies, Zhiyi graduated from the first "Yao Class" under Andrew Yao at Tsinghua University in 2008.

Abstract:

Consider Myerson’s optimal auction with respect to an inaccurate prior, e.g., estimated from data, which is an underestimation of the true value distribution. Can the auctioneer expect getting at least the optimal revenue w.r.t. the inaccurate prior since the true value distribution is larger? This so-called strong revenue monotonicity is known to be true for single-parameter auctions when the feasible allocations form a matroid. We find that strong revenue monotonicity fails to generalize beyond the matroid setting, and further show that auctions in the matroid setting are the only downward-closed auctions that satisfy strong revenue monotonicity. On the flip side, we recover an approximate version of strong revenue monotonicity that holds for all single-parameter auctions, even without downward-closedness. As applications, we get sample complexity upper bounds for single-parameter auctions under matroid constraints, downward-closed constraints, and general constraints. They improve the state-of-the-art upper bounds and are tight up to logarithmic factors.