Yang Cai

Assistant Professor and William Dawson Scholar

News

I have moved to Yale University. I no longer update this webpage. Please visit this webpage instead.

Biography

I am an Assistant Professor and William Dawson Scholar at McGill University’s School of Computer Science.

Prior to joining McGill, I was a postdoc with Christos Papadimitriou at UC Berkeley. Before that, I finished my Ph.D. in the Theory of Computation group, Computer Science and Artificial Intelligence Lab at MIT under the supervision of Costis Daskalakis. I did my undergraduate study in the EECS department at Peking University.

Current students: Mingfei Zhao, Mashbat Suzuki (co-supervised with Adrian Vetta), Johannes Brustle, Paul Pereira (co-supervised with Doina Precup).

Interests

Theory of Computation
Economics and Computation
Learning
Online Algorithms
Logic

Education

PhD in Computer Science, 2013

MIT
BSc in Electrical Engineering and Computer Science, 2008

Peking University

Selected Publications

Jessie Huang, Fa Wu, Doina Precup, Yang Cai (2018). Learning Safe Policies with Expert Guidance. In NeurIPS.

PDF arXiv

Yang Cai, Constantinos Daskalakis (2017). Learning Multi-item Auctions with (or without) Samples. In FOCS.

PDF arXiv

Johannes Brustle, Yang Cai, Fa Wu, Mingfei Zhao (2017). Approximating Gains from Trade in Two-sided Markets via Simple Mechanisms. In EC.

PDF arXiv

Yang Cai, Mingfei Zhao (2017). Simple Mechanisms for Subadditive Buyers via Duality. In STOC, invited to the Special Issue of Games and Economic Behavior for STOC/FOCS/SODA.

PDF arXiv

Yang Cai, Nikhil R. Devanur, S. Matthew Weinberg (2016). A Duality Based Unified Approach to Bayesian Mechanism Design. In STOC, invited to the Special Issue of SIAM Journal on Computing for STOC and the 2017 Highlights of Algorithms.

PDF

Nicolas Bousquet, Yang Cai, Christoph Hunkenschröder, Adrian Vetta (2016). On the Economic Efficiency of the Combinatorial Clock Auction. In SODA.

PDF arXiv

Yang Cai, Constantinos Daskalakis, Christos Papadimitriou (2015). Optimum Statistical Estimation with Strategic Data Sources. In COLT.

PDF arXiv

Yang Cai, Constantinos Daskalakis, S. Matthew Weinberg (2013). Understanding Incentives: Mechanism Design becomes Algorithm Design. In FOCS, invited to the Special Issue of Games and Economic Behavior for STOC/FOCS/SODA.

PDF arXiv

Recent Publications

More Publications

Moshe Babaioff, Yang Cai, Yannai A. Gonczarowski, Mingfei Zhao. The Best of Both Worlds: Asymptotically Efficient Mechanisms with a Guarantee on the Expected Gains-From-Trade. In EC, 2018.

PDF arXiv

Yang Cai, Federico Echenique, Hu Fu, Katrina Ligett, Adam Wierman, Juba Ziani. Third-Party Data Providers Ruin Simple Mechanisms. 2018.

PDF arXiv

Yang Cai, Nikhil R. Devanur, Kira Goldner, R. Preston McAfee. Simple and Approximately Optimal Pricing for Proportional Complementarities. 2018.

Yang Cai, Constantinos Daskalakis, S. Matthew Weinberg. A Constructive Approach to Reduced-Form Auctions with Applications to Multi-Item Mechanism Design. 2017.

PDF arXiv

Yang Cai, Nikhil R. Devanur, S. Matthew Weinberg. A Duality Based Unified Approach to Bayesian Mechanism Design. In SIGECOM Newsletter, 2016.

PDF Source Document

Yang Cai, Ozan Candogan, Constantinos Daskalakis, Christos Papadimitriou. Zero-sum Polymatrix Games: A Generalization of Minmax. In Mathematics of Operations Research, 2016.

PDF Source Document

Nicolas Bousquet, Yang Cai, Adrian Vetta. Welfare and Rationality Guarantees for the Simultaneous Multiple-Round Ascending Auction. In WINE, 2015.

PDF arXiv

Yang Cai, Constantinos Daskalakis. Extreme-Value Theorems for Optimal Multidimensional Pricing. In GEB, 2015.

PDF Source Document

Yang Cai, Constantinos Daskalakis, S. Matthew Weinberg. Reducing Bayesian Mechanism Design to Algorithm Design. In Encyclopedia of Algorithms, 2015.

PDF Source Document

Gagan Aggarwal, Yang Cai, Aranyak Mehta, George Pierrakos. Biobjective Online Bipartite Matching. In WINE, 2014.

PDF

Teaching

Here is a list of courses I’ve previously taught:

COMP 362: Honours Algorithm Design. Winter 2018

COMP 360: Algorithm Design. Winter 2015, Fall 2016, Winter 2017, Fall 2017

COMP/MATH 553: Algorithmic Game Theory. Fall 2014, Fall 2016, Fall 2018

COMP 202: Foundations of Computing. Winter 2016

Contact

cai@cs.mcgill.ca
+1 (514) 398-7082
MC 324, McGill University, Montreal, Canada