Publications

Yang Cai, Constantinos Daskalakis, Haipeng Luo, Chen-Yu Wei, Weiqiang Zheng (2024). On Tractable Φ-Equilibria in Non-Concave Games. The 38th Conference on Neural Information Processing Systems (NeurIPS).

arxiv

Yang Cai, Xiangyu Liu, Argyris Oikonomou, Kaiqing Zhang (2024). Provable Partially Observable Reinforcement Learning with Privileged Information. The 38th Conference on Neural Information Processing Systems (NeurIPS).

Yang Cai, Gabriele Farina, Julien Grand-Clément, Christian Kroer, Chung-Wei Lee, Haipeng Luo, Weiqiang Zheng (2024). Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms. The 38th Conference on Neural Information Processing Systems (NeurIPS).

arxiv

Yang Cai, Argyris Oikonomou, Weiqiang Zheng (2024). Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusion. The 41st International Conference on Machine Learning (ICML).

arxiv

Yang Cai, Yingkai Li, Jinzhao Wu (2024). Algorithmic Information Disclosure in Optimal Auctions. Proceedings of the 25th ACM Conference on Economics and Computation (EC).

arxiv

Yang Cai, Christopher Liaw, Aranyak Mehta, Mingfei Zhao (2024). The Power of Two-sided Recruitment in Two-sided Markets. Proceedings of the 56th Annual ACM SIGACT Symposium on Theory of Computing (STOC).

arxiv

Yang Cai, Zhe Feng, Christopher Liaw, Aranyak Mehta, Grigoris Velegkas (2024). User Response in Ad Auctions: An MDP Formulation of Long-Term Revenue Optimization. Proceedings of the ACM Web Conference (WWW).

arxiv

Yang Cai, Haipeng Luo, Chen-Yu Wei, Weiqiang Zheng (2024). Near-Optimal Policy Optimization for Correlated Equilibrium in General-Sum Markov Games. Proceedings of the 27th International Conference on Artificial Intelligence and Statistics (AISTATS Oral).

arxiv

Yang Cai, Haipeng Luo, Chen-Yu Wei, Weiqiang Zheng (2023). Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedback. The 37th Conference on Neural Information Processing Systems (NeurIPS).

arxiv

Yang Cai, Ziyun Chen, Jinzhao Wu (2023). Simultaneous Auctions are Approximately Revenue-Optimal for Subadditive Bidders. Proceedings of the 64th IEEE Symposium on Foundations of Computer Science (FOCS).

PDF arxiv

Yang Cai, Weiqiang Zheng (2023). Doubly Optimal No-Regret Learning in Monotone Games. The 40th International Conference on Machine Learning (ICML).

PDF arxiv

Yang Cai, Eric Xue (2023). Nearly Optimal Committee Selection For Bias Minimization. Proceedings of the 24th ACM Conference on Economics and Computation (EC).

PDF arxiv

Yang Cai, Jinzhao Wu (2023). On the Optimal Fixed-Price Mechanism in Bilateral Trade. Proceedings of the 55th Annual ACM SIGACT Symposium on Theory of Computing (STOC).

PDF arxiv

Yang Cai, Weiqiang Zheng (2023). Accelerated Single-Call Methods for Constrained Min-Max Optimization. The 11th International Conference on Learning Representations (ICLR).

PDF arxiv

Yang Cai, Argyris Oikonomou, Weiqiang Zheng (2022). Finite-Time Last-Iterate Convergence for Learning in Multi-Player Games. The 36th Conference on Neural Information Processing Systems (NeurIPS Oral).

PDF Video

Yang Cai, Argyris Oikonomou, Weiqiang Zheng (2022). Tight Last-Iterate Convergence of the Extragradient and the Optimistic Gradient Descent-Ascent Algorithm for Constrained Monotone Variational Inequalities.

PDF arxiv

Yang Cai, Constantinos Daskalakis (2022). Recommender Systems meet Mechanism Design. Proceedings of the 23rd ACM Conference on Economics and Computation (EC).

PDF DOI arxiv

Dirk Bergemann, Yang Cai, Grigoris Velegkas, Mingfei Zhao (2022). Is Selling Complete Information (Approximately) Optimal?. Proceedings of the 23rd ACM Conference on Economics and Computation (EC).

PDF DOI arxiv

Yang Cai, Argyris Oikonomou, Mingfei Zhao (2022). Computing Simple Mechanisms: Lift-and-Round over Marginal Reduced Forms. Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC).

PDF DOI arxiv

Yang Cai, Argyris Oikonomou, Weiqiang Zheng (2022). Accelerated Algorithms for Monotone Inclusions and Constrained Nonconvex-Nonconcave Min-Max Optimization. NeurIPS 2022 OPT Workshop.

PDF arxiv

Yang Cai, Argyris Oikonomou (2021). On Simple Mechanisms for Dependent Items. Proceedings of the 22nd ACM Conference on Economics and Computation (EC).

PDF DOI arXiv

Yang Cai, Kira Goldner, Steven Ma, Mingfei Zhao (2021). On Multi-Dimensional Gains from Trade Maximization. Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA).

PDF DOI arXiv

Yang Cai, Grigoris Velegkas (2021). How to Sell Information Optimally: An Algorithmic Study. 12th Innovations in Theoretical Computer Science Conference (ITCS).

PDF DOI arXiv

Yang Cai, Argyris Oikonomou, Grigoris Velegkas, Mingfei Zhao (2021). An Efficient $\varepsilon$-BIC to BIC Transformation and Its Application to Black-Box Reduction in Revenue Maximization. Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA).

PDF DOI arXiv

Yang Cai, Nikhil R. Devanur, S. Matthew Weinberg (2021). A Duality-Based Unified Approach to Bayesian Mechanism Design. SIAM Journal on Computing.

PDF DOI

Johannes Brustle, Yang Cai, Constantinos Daskalakis (2020). Multi-Item Mechanisms without Item-Independence: Learnability via Robustness. Proceedings of the 21st ACM Conference on Economics and Computation (EC).

PDF DOI arXiv

Yang Cai, Federico Echenique, Hu Fu, Katrina Ligett, Adam Wierman, Juba Ziani (2020). Third-Party Data Providers Ruin Simple Mechanisms. The 2020 SIGMETRICS/Performance Joint International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS).

PDF DOI arXiv

Yang Cai, Federico Echenique, Hu Fu, Katrina Ligett, Adam Wierman, Juba Ziani (2020). Third-Party Data Providers Ruin Simple Mechanisms. Proceedings of the ACM on Measurement and Analysis of Computing Systems.

PDF DOI

Yang Cai, Mingfei Zhao (2019). Simple Mechanisms for Profit Maximization in Multi-item Auctions. Proceedings of the 2019 ACM Conference on Economics and Computation (EC).

PDF DOI arXiv

Yang Cai, Nikhil R. Devanur, Kira Goldner, R. Preston McAfee (2019). Simple and Approximately Optimal Pricing for Proportional Complementarities. Proceedings of the 2019 ACM Conference on Economics and Computation (EC).

PDF DOI arXiv

Moshe Babaioff, Yang Cai, Yannai A. Gonczarowski, Mingfei Zhao (2018). The Best of Both Worlds: Asymptotically Efficient Mechanisms with a Guarantee on the Expected Gains-From-Trade. Proceedings of the 2018 ACM Conference on Economics and Computation (EC).

PDF DOI arXiv

Jessie Huang, Fa Wu, Doina Precup, Yang Cai (2018). Learning Safe Policies with Expert Guidance. Proceedings of the 32nd in Neural Information Processing Systems (NeurIPS).

PDF arXiv

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

PDF arXiv

Yang Cai, Constantinos Daskalakis (2017). Learning Multi-Item Auctions with (or without) Samples. 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS).

PDF DOI arXiv

Yang Cai, Mingfei Zhao (2017). Simple mechanisms for subadditive buyers via duality. Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC).

PDF DOI arXiv SIGecom Exchange

Johannes Brustle, Yang Cai, Fa Wu, Mingfei Zhao (2017). Approximating Gains from Trade in Two-sided Markets via Simple Mechanisms. Proceedings of the 2017 ACM Conference on Economics and Computation (EC).

PDF DOI arXiv

Yang Cai, Nikhil R. Devanur, S. Matthew Weinberg (2016). A duality based unified approach to Bayesian mechanism design. Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (STOC).

PDF DOI arXiv SIGecom Exchange

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

PDF DOI

Yang Cai, Constantinos Daskalakis, Matthew Weinberg (2016). Reducing Bayesian Mechanism Design to Algorithm Design. Encyclopedia of Algorithms.

PDF DOI

Nicolas Bousquet, Yang Cai, Christoph Hunkenschröder, Adrian Vetta (2015). On the Economic Efficiency of the Combinatorial Clock Auction. Proceedings of the 2016 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA).

PDF DOI arXiv

Yang Cai, Constantinos Daskalakis (2015). Extreme value theorems for optimal multidimensional pricing. Games and Economic Behavior.

PDF DOI arXiv

Yang Cai, Constantinos Daskalakis, Christos Papadimitriou (2015). Optimum Statistical Estimation with Strategic Data Sources. Conference on Learning Theory (COLT).

PDF arXiv

Nicolas Bousquet, Yang Cai, Adrian Vetta (2015). Welfare and Rationality Guarantees for the Simultaneous Multiple-Round Ascending Auction. Web and Internet Economics (WINE).

PDF DOI arXiv

Yang Cai, Christos Papadimitriou (2014). Simultaneous bayesian auctions and computational complexity. Proceedings of the fifteenth ACM conference on Economics and computation (EC).

PDF DOI

Gagan Aggarwal, Yang Cai, Aranyak Mehta, George Pierrakos (2014). Biobjective Online Bipartite Matching. Web and Internet Economics (WINE).

PDF DOI

Yang Cai, Constantinos Daskalakis, S. Matthew Weinberg (2013). Understanding Incentives: Mechanism Design Becomes Algorithm Design. 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS).

PDF DOI arXiv

Yang Cai (2013). Mechanism design : a new algorithmic framework. Ph.D. Thesis.

PDF

Yang Cai, Zhiyi Huang (2013). Simple and Nearly Optimal Multi-Item Auctions. Proceedings of the 2013 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA).

PDF DOI arXiv

Yang Cai, Constantinos Daskalakis, S. Matthew Weinberg (2013). Reducing Revenue to Welfare Maximization: Approximation Algorithms and other Generalizations. Proceedings of the 2013 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA).

PDF DOI arXiv

Yang Cai, Mohammad Mahdian, Aranyak Mehta, Bo Waggoner (2013). Designing Markets for Daily Deals. Web and Internet Economics (WINE).

PDF DOI arXiv

Yang Cai, Constantinos Daskalakis, S. Matthew Weinberg (2012). Optimal Multi-dimensional Mechanism Design: Reducing Revenue to Welfare Maximization. 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS).
FOCS 2022 Test of Time Award.

PDF DOI arXiv

Yang Cai, Ting Zhang (2012). Can Nondeterminism Help Complementation?. Electronic Proceedings in Theoretical Computer Science.

PDF DOI arXiv

Yang Cai, Constantinos Daskalakis, S. Matthew Weinberg (2012). An Algorithmic Characterization of Multi-Dimensional Mechanisms. Proceedings of the forty-fourth annual ACM symposium on Theory of computing (STOC).

PDF DOI arXiv

Yang Cai, Constantinos Daskalakis (2011). Extreme-Value Theorems for Optimal Multidimensional Pricing. 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS).

PDF DOI arXiv

Yang Cai, Constantinos Daskalakis, S. Matthew Weinberg (2011). On optimal multidimensional mechanism design. ACM SIGecom Exchanges.

PDF DOI

Yang Cai, Ting Zhang (2011). Tight Upper Bounds for Streett and Parity Complementation. Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL.

PDF DOI arXiv

Yang Cai, Constantinos Daskalakis (2011). On Minmax Theorems for Multiplayer Games. Proceedings of the 2011 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA).

PDF DOI

Yang Cai, Ting Zhang (2011). A Tight Lower Bound for Streett Complementation. IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS).

PDF DOI arXiv

Fan Long, Xi Wang, Yang Cai (2009). API hyperlinking via structural overlap. Proceedings of the 7th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on The foundations of software engineering (ESEC/FSE).

PDF DOI

Yang Cai, Ting Zhang, Haifeng Luo (2009). An Improved Lower Bound for the Complementation of Rabin Automata. 2009 24th Annual IEEE Symposium on Logic In Computer Science (LICS).

PDF DOI