GSP 赞助购物中自动出价均衡的计算复杂度是什么？

答案分为精确与近似两种情况

这篇论文要回答的是：在 GSP 赞助购物拍卖中计算一个自动出价均衡有多难。这类拍卖允许同一个出价人拥有多件商品，让它们竞争同一批广告位。答案取决于目标是精确均衡还是近似均衡。论文证明，计算精确均衡属于 FIXP，即由代数电路给出的函数的精确不动点所对应的复杂度类。计算 γ-近似均衡属于 PPAD；当 γ 在输入规模上是反多项式时，该问题还是 PPAD 难的，因此在这一精度下近似问题是 PPAD 完全的。

这两项结果分别针对论文研究的两种约束模型给出：预算约束（ABE-B）和投资回报率约束（ABE-R）。此前提出这一拍卖模型的工作只处理了 ROI 约束的情形，因此预算约束情形是本文新开辟的领域。论文还证明，两种模型下均衡总是存在，并且总存在一个均衡在分配空间上具有多项式规模的支撑，也就是说，它可以写成多项式个确定性分配上的分布，而不必覆盖指数级大的全部合法排序集合。

困难性在单场拍卖内部就已出现

此前关于第二价格拍卖中节奏控制（pacing）与自动出价均衡的困难性结果，依赖的是包含许多并行拍卖的市场，其计算难度来自拍卖之间的相互作用。论文指出，当拍卖数量固定时，第二价格拍卖的精确节奏均衡是可高效计算的。这一对比引出了本文回答的问题：计算困难是否可能出现在单场 GSP 赞助购物拍卖内部？

论文的归约表明，确实可能。由于所有商品进入同一个全局排序，归约中互不相关的部分所包含的商品，可能影响某个小装置（gadget）中商品所支付的价格；而仅靠拉开名义价值量级并不能阻止这种干扰，因为出价人的乘数是内生的。归约通过两种手段处理这一问题：保证每个近似均衡中都满足局部定价，以及复制输出商品，使局部价格差异在出价人总支付中的影响压过其他装置中商品的贡献和允许的近似误差。两个困难性归约即使所有商品都被展示、所有点击率都相等时也成立。

每个出价人拥有多件商品改变了支付规则

在经典赞助搜索中，广告主通常只为单个链接出价，因此分配就是把出价人匹配到广告位。在赞助购物中，零售商可能为同一个查询推广多件商品，因此同一个出价人可以赢得多个广告位，分配变成把“出价人—商品”对分配到广告位，价值同时取决于出价人和被展示的商品。论文用 n 个出价人、K 个点击率递减的广告位，以及每个出价人 m_i 件按价值降序排列的商品来刻画这一情形。

支付规则是“无自我定价”的 GSP：一件商品支付的是排序中下一位属于其他出价人的最高出价，因此出价人自己的商品不能为彼此定价。论文指出，这与 Google Ads 等主要广告平台描述的设计一致：同一账户下符合条件的多个关键词不会互相竞争。自动出价通过统一出价策略进入模型：每个出价人只选一个乘数 α_i，对每件商品按 α_i 乘以该商品价值出价，而不是为每件商品单独出价。自动出价均衡就是这些乘数的一个组合，再加上一个在分配上的合法随机平局规则。

有些均衡无法写成有理数

论文分别构造了预算约束下和 ROI 约束下的 GSP 赞助购物拍卖实例，其中自动出价均衡必然是无理数。这影响我们如何理解精确结果：精确均衡可能无法用有理数表示，因此一个只输出精确有理数据的算法无法覆盖所有实例。

这正是论文把近似视为自然松弛的原因，也是近似问题需要单独的成员性与困难性结果的原因。论文在讨论部分还指出，其无理数实例产生的均衡乘数涉及平方根，但仅有这些实例并不能给出一个归约，用来证明某个精确均衡比较问题是 Square-Root-Sum 难的。

分位数耦合把支撑控制在多项式规模

从先前工作继承的存在性证明是非构造性的：它既不能推出精确均衡可以只支撑在多项式个纯分配上，甚至不能把近似问题的计算纳入 TFNP。论文用一个构造补上了这一缺口：把分配表示为一系列分组插入，为每次插入构造合法的边缘分布，再用一个共同的分位数把这些边缘分布耦合为多项式个排列及其概率上的联合分布。

在每个不动点上，每个获得正概率的排列都满足出价一致性。该构造避免显式表示指数级大的分配空间，这正是它能在两种约束模型下都给出多项式支撑保证的原因。作者称，据其所知，这是首次用分位数耦合来建立均衡计算的复杂度上界；他们预计这一技术也适用于其他需要把局部选择分布耦合为全局可行结果的问题。

离散化支付把精确电路转化为 PPAD 成员性

近似均衡的 PPAD 成员性结果，是通过改造 Filos-Ratsikas 等人的优化门框架得到的。作者从用于精确均衡的代数电路出发，把非线性的支付计算替换为受控的离散化，使其可以用分段线性函数实现。该构造精确保留出价一致性以及预算或 ROI 可行性，只允许在最大节奏控制条件上出现近似。

论文称，据其所知，这是首次把线性 OPT 框架用于证明那些可能只有无理精确解的均衡问题的近似版本的 PPAD 成员性。当 γ 在输入规模上是反指数时成员性成立，而当 γ 是反多项式时困难性成立；论文的开放问题正位于这两个区间之间。

固定参数与常数精度仍是开放问题

困难性归约使用了不断增长的出价人数、商品数以及正点击率广告位数。这为某些情形下的多项式时间算法留出了空间，例如出价人数、每个出价人的商品数或正点击率广告位数固定时；作者猜想这类限制能恢复可处理性，并指出近期关于买家数或商品数固定时第二价格拍卖市场精确节奏均衡的多项式时间结果是有希望的方向。任何这类算法都必须能处理代数数输出，因为有理均衡未必存在。

近似阈值同样没有解决。归约把各个门放在彼此分离的出价区间中，区间乘性宽度为 c = 1 + Θ(1/n)，这使整体取值范围保持有界，但留下的局部间隔只有 Θ(1/n)。若把区间放宽到常数宽度，就会产生指数级的取值范围，并且在当前的放大论证下需要指数多件商品。因此，常数 γ 下的困难性仍然开放；反多项式困难性排除了 FPTAS，除非所有 PPAD 问题都有多项式时间算法；两种情形是否存在 PTAS 也仍未解决。精确问题的下界同样开放：若能强化到 FIXP 难，再结合成员性结果，就能得到 FIXP 完全性。

实际判断的关键在精度而非可解性

这篇论文中最影响判断的区分是精确计算与近似计算，而不是两种约束模型之间的差别。ABE-B 与 ABE-R 得到同样的处理，也落在同样的位置：精确均衡属于 FIXP，反指数精度下近似均衡属于 PPAD，反多项式精度下近似问题是 PPAD 难的。读者比较这两种设定时，不应根据这些结果预期其中一种比另一种更容易。

第二个区分是困难性与不可行性。反多项式精度下的 PPAD 困难性排除了 FPTAS，除非所有 PPAD 问题都可在多项式时间内求解，但它并不排除 PTAS，论文明确把这一问题留作开放。结合多项式支撑保证，整体图景是：均衡数量充足且可以紧凑表示，而把均衡计算到很紧的精度，与归约出发的那类 PPAD 完全问题一样难。作者指出的开放前沿是结构性限制，例如固定出价人数、每个出价人的商品数或正点击率广告位数，而不是预算约束与 ROI 约束之间的差别。

本文引用的文献