10 citations · 17 across the 24 of their papers we have counts for
29 papers
Competitive Equilibrium for Linear Chores is CLS-complete
Qian Liu, Shinuo Ma, Yixin Tao +2
The competitive equilibrium (CE) is a fundamental concept for markets, with applications to efficient and fair allocation of resources. We consider the fundamental question of comp…
Algorithmic Collusion and the Complexity of Information-Value-Free Equilibria
Ioannis Anagnostides, Weiqiang Zheng
A (coarse) correlated equilibrium (CE) is information-value-free (IVF) if a player can match the payoff obtained from recommendations by committing to a fixed action. Motivated by…
Optimal Alternating Regret for Online Learning and Games
Yixin Tao, Weiqiang Zheng
We settle the minimax-optimal alternating regret, a regret notion motivated by alternating learning dynamics in games, for both online linear optimization (OLO) and online convex o…
From Compensation Design to Budget-Feasible Mechanisms: A Constant Approximation for Subadditive Valuations
Ioannis Anagnostides, Kshipra Bhawalkar, Christopher Liaw +3
Budget-feasible mechanism design is a classic framework introduced by Singer, but there is still a wide gap between existing upper and lower bounds. In this paper, we significantly…
Compensation Design
Ioannis Anagnostides, Kshipra Bhawalkar, Christopher Liaw +5
We introduce compensation design, the problem of designing payment rules that incentivize high-quality contributions in decentralized environments. Here, a budget-constrained princ…
Gradient Dynamics in First-Price Auctions: Iterative Strategy Elimination via Cubic Potentials
Mete Şeref Ahunbay, Weiqiang Zheng, Tao Lin
We show that in discretised first-price auctions with complete information, if the buyers learn to bid with online gradient ascent, in time-average the outcome is (almost) the effi…
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…
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…
Fisher Meets Lindahl: A Unified Duality Framework for Market Equilibrium
Yixin Tao, Weiqiang Zheng
The Fisher market equilibrium for private goods and the Lindahl equilibrium for public goods are classic and fundamental solution concepts for market equilibria. While Fisher marke…
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 Best Responses to Learning: Investment Efficiency in Dynamic Environment
Ce Li, Qianfan Zhang, Weiqiang Zheng
We study the welfare of a mechanism in a dynamic environment where a learning investor can make a costly investment to change her value. In many real-world problems, the common ass…
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…
COMAL: A Convergent Meta-Algorithm for Aligning LLMs with General Preferences
Yixin Liu, Argyris Oikonomou, Weiqiang Zheng +2
Many alignment methods, including reinforcement learning from human feedback (RLHF), rely on the Bradley-Terry reward assumption, which is not always sufficient to capture the full…
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…
Learning Thresholds with Latent Values and Censored Feedback
Jiahao Zhang, Tao Lin, Weiqiang Zheng +3
In this paper, we investigate a problem of actively learning threshold in latent space, where the unknown reward depends on the proposed threshold and latent value $v…
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…
Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedback
Yang Cai, Haipeng Luo, Chen-Yu Wei +1
We revisit the problem of learning in two-player zero-sum Markov games, focusing on developing an algorithm that is uncoupled, convergent, and rational, with non-asymptotic converg…
Doubly Optimal No-Regret Learning in Monotone Games
Yang Cai, Weiqiang Zheng
We consider online learning in multi-player smooth monotone games. Existing algorithms have limitations such as (1) being only applicable to strongly monotone games; (2) lacking th…
Beyond the Worst Case: Semi-Random Complexity Analysis of Winner Determination
Lirong Xia, Weiqiang Zheng
The computational complexity of winner determination is a classical and important problem in computational social choice. Previous work based on worst-case analysis has established…