22 papers
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…