Publications

Yang Cai, Weiqiang Zheng (2026). Asymptotic Universal Alignment: A New Alignment Framework via Test-Time Scaling. The 43rd International Conference on Machine Learning (ICML).

arxiv

Dirk Bergemann, Yang Cai, Jinzhao Wu, Konstantin Zabarnyi (2026). The Near-Optimality of Two-Part Tariffs for Nonlinear Pricing. Proceedings of the 27th ACM Conference on Economics and Computation (EC).

Yang Cai, Haipeng Luo, Chen-Yu Wei, Weiqiang Zheng (2026). Is Online Linear Optimization Sufficient for Strategic Robustness?. Proceedings of the 27th ACM Conference on Economics and Computation (EC).

arxiv

Yang Cai, Constantinos Daskalakis, Haipeng Luo, Chen-Yu Wei, Weiqiang Zheng (2026). Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Games . Proceedings of the 58th Annual ACM SIGACT Symposium on Theory of Computing (STOC).

arxiv

Yang Cai, Constantinos Daskalakis, S. Matthew Weinberg (2026). An Algorithmic Framework for Black-Box Reductions from Bayesian Mechanism Design to Algorithm Design.
Includes results from several earlier papers, one of which received the 🏆 FOCS 2022 Test of Time Award.

PDF DOI

Yixin Liu, Argyris Oikonomou, Weiqiang Zheng, Yang Cai, Arman Cohan (2026). COMAL: A Convergent Meta-Algorithm for Aligning LLMs with General Preferences. The 14th International Conference on Learning Representations (ICLR).

arxiv

Yang Cai, Haipeng Luo, Chen-Yu Wei, Weiqiang Zheng (2025). From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications. The 39th Conference on Neural Information Processing Systems (NeurIPS).

arxiv

Yang Cai, Kshipra Bhawalkar, Zhe Feng, Christopher Liaw, Tao Lin (2025). A Unified Approach to Submodular Maximization Under Noise. The 39th Conference on Neural Information Processing Systems (NeurIPS).

arxiv

Yang Cai, Alkis Kalavasis, Katerina Mamali, Anay Mehrotra, Manolis Zampetakis (2025). What Makes Treatment Effects Identifiable? Characterizations and Estimators Beyond Unconfoundedness. The 38th Annual Conference on Learning Theory (COLT) — 🏆 Best Paper Award.

arxiv

Yang Cai, Siddharth Mitra, Xiuyuan Wang, Andre Wibisono (2025). On the Convergence of Min-Max Langevin Dynamics and Algorithm. The 38th Annual Conference on Learning Theory (COLT).

arxiv

Yang Cai, Gabriele Farina, Julien Grand-Clément, Christian Kroer, Chung-Wei Lee, Haipeng Luo, Weiqiang Zheng (2025). Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games. The 13th International Conference on Learning Representations (ICLR).

arxiv

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 (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 32nd 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 32nd 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 20th 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 20th 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 19th 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 Conference on 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. Proceedings of the 58th IEEE 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 18th 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 48th 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 27th 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. The 28th Annual 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 15th 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. Proceedings of the 54th IEEE 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 24th 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 24th 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. Proceedings of the 53rd IEEE 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 44th Annual ACM symposium on Theory of computing (STOC).

PDF DOI arXiv

Yang Cai, Constantinos Daskalakis (2011). Extreme-Value Theorems for Optimal Multidimensional Pricing. Proceedings of the 52nd IEEE 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 22nd 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. Proceedings of the 24th IEEE Annual Symposium on Logic In Computer Science (LICS).

PDF DOI