arXiv:2611.04475 · v1

On the Complexity of Exact Autobidding Equilibria

首次提交 2026-11-03 16:05

版本更新 2026-11-03 16:05

雷达观测 2026-11-04 23:40

摘要

Autobidding equilibria link advertisers' value multipliers or participation probabilities through aggregate budget and return-on-investment (ROI) constraints. We establish the exact computational complexity of finding these equilibria across several canonical settings: exact equilibrium computation is $\mathsf{FIXP}$-complete for second-price ROI pacing, budget- or ROI-constrained generalized second-price (GSP) sponsored shopping, and second-price throttling. Furthermore, approximating the equilibrium control vector in distance to a true equilibrium is $\mathsf{FIXP}_{a}$-complete when the target accuracy is provided as input.

作者备注：Full version with appendices