YANG CAI --- (Pronounce like: ['Young 'Tsai] )

Email: cai at cs dot mcgill dot ca

I am an Assistant Professor 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 PhD at the Theory of Computation group, Computer Science and Artifitial Intelligence Lab at MIT under the supervision of Costis Daskalakis. I did my undergraduate study in the EECS department at Peking University.

I am interested in algorithmic game theory, applied probability, online algorithms and logic.

I will be teaching COMP/MATH 553: ALGORITHMIC GAME THEORY in the Fall Semester, 2014!

Publications

Algorithmic Game Theory

Simultaneous Bayesian Auctions and Computational Complexity
Yang Cai and Christos Papadimitriou
In the 15th ACM conference on Economics and computation, EC 2014.
Designing Markets for Daily Deals
Yang Cai, Mohammad Mahdian, Aranyak Mehta and Bo Waggoner
In the 9th Conference on Web and Internet Economics, WINE 2013. [arxiv]
Understanding Incentives: Mechanism Design becomes Algorithm Design
Yang Cai, Constantinos Daskalakis and S. Matthew Weinberg.
In the 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013. [arxiv]
Reducing Revenue to Welfare Maximization: Approximation Algorithms and other Generalizations
Yang Cai, Constantinos Daskalakis and S. Matthew Weinberg.
In the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013. [arxiv]
Invited to Games and Economic Behavior (Special Issue for STOC/FOCS/SODA 2013).
Simple and Nearly Optimal Multi-Item Auctions Yang Cai and Zhiyi Huang.
In the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013. [arxiv]
Optimal Multi-Dimensional Mechanism Design: Reducing Revenue to Welfare Maximization
Press Coverage: MIT News
Yang Cai, Constantinos Daskalakis and S. Matthew Weinberg.
In the 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012. [arxiv]
An Algorithmic Characterization of Multi-Dimensional Mechanisms
Yang Cai, Constantinos Daskalakis and S. Matthew Weinberg.
In the 44th ACM Symposium on Theory of Computing, STOC 2012. [arxiv]
Extreme-Value Theorems for Optimal Multidimensional Pricing
Yang Cai and Constantinos Daskalakis.
In the 52nd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2011. [arxiv]
Invited to Games and Economic Behavior (Special Issue for STOC/FOCS/SODA 2011.)
On Optimal Multidimensional Mechanism Design
Yang Cai, Constantinos Daskalakis and S. Matthew Weinberg.
Newsletter of the ACM Special Interest Group on E-commerce, 10(2), 2011, Newsletter.
On Minmax Theorems for Multiplayer Games
Yang Cai and Constantinos Daskalakis.
In the ACM-SIAM Symposium on Discrete Algorithms, SODA 2011.

Logic

A Tight Lower bound for Streett Complementation Yang Cai and Ting Zhang.
In the Foudation of Software Technology and Theoretical Computer Science, FSTTCS 2011. [arxiv]
Tight Upper Bounds for Streett and Parity Complementation Yang Cai and Ting Zhang.
In the 20th Conference on Computer Science Logic, CSL 2011.
An Improved Lower Bound for the Complementation of Rabin Automata
Yang Cai, Ting Zhang and Haifeng Luo.
In the 24th Annual IEEE Symposium on Logic in Computer Science, LICS 2009.

Miscellaneous

API Hyperlinking via Structual Overlap Fan Long, Xi Wang and Yang Cai.
In the 7th joint meeting of European Software Engineering Conference and the ACM SIGSOFT
Symposium on the Foundations of Software Engineering, ESEC/FSE 2009.

Ph.D. Thesis

Mechanism Design: a New Algorithmic Framework
My Ph.D. Thesis, MIT, EECS Department, June 2013.
Honorable Mention of the George M. Sprowls Award (for best MIT doctoral theses in CS)
SIGEcom Doctoral Dissertation Award runner-up

Manuscripts

Biobjective Online Bipartite Matching
Gagan Aggarwal, Yang Cai, Aranyak Mehta and George Pierrakos

Contact