Yang Cai wins Test of Time Award at FOCS 2022

November 2, 2022

Yang Cai has won the 2022 FOCS Test of Time Award (https://focs2022.eecs.berkeley.edu/tot.html) with Constantinos Daskalakis and S. Matthew Weinberg for their article “Optimal Multi-dimensional Mechanism Design: Reducing Revenue to Welfare Maximization”, FOCS 2012.

The paper presents a general reduction that converts a large class of revenue maximization problems in multidimensional mechanism design to a class of welfare maximization problems in the general framework of the Vickrey-Clarke-Groves (VCG) mechanism in the Bayesian setting. The VCG mechanism is incentive compatible, so the transformation takes care of all the incentive and pricing issues hence freeing the designer from handling these issues allowing him to focus on the algorithmic problem of solving the resulting optimization problem. The methods introduced in this paper provide a crucial bridge between two areas of economic mechanism design, and play an important role in the modern treatment of algorithmic methods in mechanism design.

The FOCS Test of Time Award recognizes papers published in past Annual IEEE Symposia on Foundations of Computer Science (FOCS) for their substantial, lasting, broad, and currently relevant impact. Papers may be awarded for their impact on Theory of Computing, or on Computer Science in general, or on other disciplines of knowledge, or on practice.