15 papers
Cogentic: Multi-Agent Orchestration for Automated Proof Discovery
Yang Cai, Vineet Gupta, Yanchen Jiang +4
We present Cogentic, a multi-agent harness for automated proof discovery on open research problems. While frontier language models can generate strong mathematical ideas in a singl…
Efficiency of Generalized Proportional First-Price Auctions Under Auto-bidding
Yang Cai, Vineet Gupta, Yanchen Jiang +4
Auto-bidding is now widely adopted in online advertising platforms, allowing advertisers to specify high-level campaign objectives--such as maximizing total value subject to a retu…
Efficient Online Inverse Optimization with Regret
Yang Cai, Anupam Gupta, Vineet Gupta +7
We give a deterministic algorithm for online inverse linear optimization with regret , uniform in the horizon and time per round. A bound of this order was obtaine…
Accelerating Min-Max Optimization via Power-Law Stepsizes
Yue Wu, Weiqiang Zheng, Yang Cai +1
We revisit the convergence guarantees of the Extragradient (EG) method for unconstrained biaffine min-max optimization. It is known that EG with a fixed stepsize achieves a $Θ(T^{-…
Last-Iterate Convergence of Anchored Gradient Descent
Yang Cai, Weiqiang Zheng
We study the monotone inclusion problem , where is monotone and Lipschitz, and is maximally monotone, a framework that encompasses monotone variational ineq…
A New Lower Bound for the Random Offerer Mechanism in Bilateral Trade using AI-Guided Evolutionary Search
Yang Cai, Vineet Gupta, Zun Li +1
The celebrated Myerson--Satterthwaite theorem shows that in bilateral trade, no mechanism can be simultaneously fully efficient, Bayesian incentive compatible (BIC), and budget bal…
Is Online Linear Optimization Sufficient for Strategic Robustness?
Yang Cai, Haipeng Luo, Chen-Yu Wei +1
We consider bidding in repeated Bayesian first-price auctions. Bidding algorithms that achieve optimal regret have been extensively studied, but their strategic robustness to the s…
Asymptotic Universal Alignment: A New Alignment Framework via Test-Time Scaling
Yang Cai, Weiqiang Zheng
Aligning large language models (LLMs) to serve users with heterogeneous and potentially conflicting preferences is a central challenge for personalized and trustworthy AI. We forma…
Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Games
Yang Cai, Constantinos Daskalakis, Haipeng Luo +2
Learning and computation of equilibria are central problems in game theory, theory of computation, and artificial intelligence. In this work, we introduce proximal regret, a new no…
From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications
Yang Cai, Haipeng Luo, Chen-Yu Wei +1
The convergence of online learning algorithms in games under self-play is a fundamental question in game theory and machine learning. Among various notions of convergence, last-ite…
On Separation Between Best-Iterate, Random-Iterate, and Last-Iterate Convergence of Learning in Games
Yang Cai, Gabriele Farina, Julien Grand-Clément +4
Non-ergodic convergence of learning dynamics in games is widely studied recently because of its importance in both theory and practice. Recent work (Cai et al., 2024) showed that a…
Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms
Yang Cai, Gabriele Farina, Julien Grand-Clément +4
Self-play via online learning is one of the premier ways to solve large-scale two-player zero-sum games, both in theory and practice. Particularly popular algorithms include optimi…
On Tractable -Equilibria in Non-Concave Games
Yang Cai, Constantinos Daskalakis, Haipeng Luo +2
While Online Gradient Descent and other no-regret learning procedures are known to efficiently converge to a coarse correlated equilibrium in games where each agent's utility is co…
Near-Optimal Policy Optimization for Correlated Equilibrium in General-Sum Markov Games
Yang Cai, Haipeng Luo, Chen-Yu Wei +1
We study policy optimization algorithms for computing correlated equilibria in multi-player general-sum Markov Games. Previous results achieve convergence rate to a c…
Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games
Yang Cai, Gabriele Farina, Julien Grand-Clément +4
We study last-iterate convergence properties of algorithms for solving two-player zero-sum games based on Regret Matching (RM). Despite their widespread use for solving rea…