Scholarlink

In this paper, we revisit the problem of approximating a pacing equilibrium in second-price auctions, introduced by Conitzer, Kroer, Sodomka, and Stier-Moses [Oper. Res. 2022]. We show that finding a constant-factor approximation of a pacing equilibrium is PPAD-hard, thereby strengthening previous results of Chen, Kroer, and Kumar [Math. Oper. Res. 2024], which established PPAD-hardness only for inverse-polynomial approximations.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Constant Inapproximability of Pacing Equilibria in Second-Price Auctions

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Xi Chen,
  • Yuhao Li

摘要

In this paper, we revisit the problem of approximating a pacing equilibrium in second-price auctions, introduced by Conitzer, Kroer, Sodomka, and Stier-Moses [Oper. Res. 2022]. We show that finding a constant-factor approximation of a pacing equilibrium is PPAD-hard, thereby strengthening previous results of Chen, Kroer, and Kumar [Math. Oper. Res. 2024], which established PPAD-hardness only for inverse-polynomial approximations.