Strategizing Against No-Proximal-Regret Learners and the Efficiency of Auctions under Gradient Dynamics

In repeated principal-agent games, external-regret learners (e.g., MWU) allow full surplus extraction in dynamic auctions and suffer suboptimal CCE Price of Anarchy (PoA), while swap-regret learners cap payoffs at Stackelberg or Myerson bounds. Yet swap-regret minimization incurs high overhead on continuous convex sets; autobidders instead run Online Gradient Descent (OGD). Cai et al. (STOC 2026) showed Projected OGD achieves $O(\sqrt{T})$ proximal regret and converges to Proximal Correlated Equilibria (PCE). Whether No-Proximal-Regret and OGD learners are manipulable, and whether PCE breaks CCE barriers in asymmetric auctions and autobidding, remained open. We resolve both via a variational characterization: (1) Every $\rho$-weakly convex ($\rho < 1$) proximal map on compact convex $\mathcal{X} \subset \mathbb{R}^d$ is cyclically monotone; on finite supports or 1D intervals the closure of $\Phi_{\text{prox}}(\mathcal{X})$ equals cyclically monotone maps into $\mathcal{X}$ (a poly-size LP on polytopes), while $1/2$-weakly convex potentials collapse pure PCE to CE. (2) In 1D concave games, $V_{\text{OGD}} \le V_{\text{Prox}} = V_{\text{Swap}} = \text{Stack}$ (beating linear swap); under 2-type bait-and-switch, dual MWU enables cross-type extortion ($> \text{Rev}_{\text{Mye}}$) while primal 1D OGD clips at the boundary, and $\dim(\mathcal{X}) \ge 2$ vortices yield strict separations ($1/3 < 1/2 < 1$). (3) In raw bid space, revenue is at most $\text{Rev}_{\text{Mye}}$ in 1D SPA and $K=2$ binary menus, while $m$-menus ($p \le a v_H$) satisfy $\text{Rev}_{\text{Prox}}^{(m)}(\mathcal{D}) = \mathbb{E}[v] - \Theta(1/m) < \mathbb{E}[v]$. (4) Discretized simplex PCE yields $\lim_{M\to\infty}\text{PoA}_{\text{PCE}} = 1$ in asymmetric First-Price Auctions, and 2D dual PCE yields tight $\text{PoA}_{\text{PCE}} \to 2$ in Budget+RoS autobidding.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-12
DOI
https://doi.org/10.5281/zenodo.24163662
Primary Topic
Auction Theory and Applications
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Strategizing Against No-Proximal-Regret Learners and the Efficiency of Auctions under Gradient Dynamics

Xuanyang Zhang
Zenodo (CERN European Organization for Nuclear Research)
Auction Theory and Applications
preprint

Strategizing Against No-Proximal-Regret Learners and the Efficiency of Auctions under Gradient Dynamics

Xuanyang Zhang
preprint en

Abstract

In repeated principal-agent games, external-regret learners (e.g., MWU) allow full surplus extraction in dynamic auctions and suffer suboptimal CCE Price of Anarchy (PoA), while swap-regret learners cap payoffs at Stackelberg or Myerson bounds. Yet swap-regret minimization incurs high overhead on continuous convex sets; autobidders instead run Online Gradient Descent (OGD). Cai et al. (STOC 2026) showed Projected OGD achieves $O(\sqrt{T})$ proximal regret and converges to Proximal Correlated Equilibria (PCE). Whether No-Proximal-Regret and OGD learners are manipulable, and whether PCE breaks CCE barriers in asymmetric auctions and autobidding, remained open. We resolve both via a variational characterization: (1) Every $\rho$-weakly convex ($\rho < 1$) proximal map on compact convex $\mathcal{X} \subset \mathbb{R}^d$ is cyclically monotone; on finite supports or 1D intervals the closure of $\Phi_{\text{prox}}(\mathcal{X})$ equals cyclically monotone maps into $\mathcal{X}$ (a poly-size LP on polytopes), while $1/2$-weakly convex potentials collapse pure PCE to CE. (2) In 1D concave games, $V_{\text{OGD}} \le V_{\text{Prox}} = V_{\text{Swap}} = \text{Stack}$ (beating linear swap); under 2-type bait-and-switch, dual MWU enables cross-type extortion ($> \text{Rev}_{\text{Mye}}$) while primal 1D OGD clips at the boundary, and $\dim(\mathcal{X}) \ge 2$ vortices yield strict separations ($1/3 < 1/2 < 1$). (3) In raw bid space, revenue is at most $\text{Rev}_{\text{Mye}}$ in 1D SPA and $K=2$ binary menus, while $m$-menus ($p \le a v_H$) satisfy $\text{Rev}_{\text{Prox}}^{(m)}(\mathcal{D}) = \mathbb{E}[v] - \Theta(1/m) < \mathbb{E}[v]$. (4) Discretized simplex PCE yields $\lim_{M\to\infty}\text{PoA}_{\text{PCE}} = 1$ in asymmetric First-Price Auctions, and 2D dual PCE yields tight $\text{PoA}_{\text{PCE}} \to 2$ in Budget+RoS autobidding.

Zenodo (CERN European Organization for Nuclear Research)
Auction Theory and Applications
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon