Autobidding

发表于 2024-07-26 更新于 2025-01-27 分类于 research

Autobidding with Constraints

VCG是在二价上衍生的，所以如果二价不是AIC，那么VCG也不是AIC

价值最大化出价者在真实拍卖中的最优出价策略

Theorem 1. Bidding strategy $b(i)$ gives a solution which has value at least OPT minus value of $2|C|$ impressions and violates each constraint by at most $2|C|$ 1 impressions if and only the auction is truthful.
最近，有一系列研究聚焦于在线广告中受自动出价（例如目标每次行动成本出价者和目标广告支出回报率出价者）驱动的价值最大化出价者。Aggarwal 等人（2019 年）描述了价值最大化出价者在真实拍卖中的最优出价策略，并表明在最坏情况下，VCG 拍卖的福利可能只有最优社会福利的二分之一。Balseiro 等人（2021b）；Deng 等人（2022 年，2021 年）展示了如何在有价值最大化出价者的拍卖中使用提升和保留价格来提高福利效率。Balseiro 等人（2021a，2022a）描述了在各种信息结构下，有或没有预算约束的价值最大化者的收益最优单阶段拍卖。除此之外，还有其他相关工作研究略有不同的出价模型，例如 Babaioff 等人（2021 年）；Goel 等人（2019 年，2014 年）；Golrezaei 等人（2021 年）研究具有投资回报率约束的效用最大化者，以及 Fadaei 和 Bichler（2016 年）；Wilkens 等人（2017 年，2016 年）研究具有每次拍卖目标约束的价值最大化出价者。
一些设置参考：
定义 2.第一价格节奏均衡（FPPE）是一个 BFPM 元组（ $(\alpha, x)$ ），每个出价者 i 的节奏乘数 $\alpha_{i}$ ，出价者 i 和好 j 的分数分配 $x_{i j}$，具有以下附加属性：•（无需不必要的pacing）如果对于每个投标人$i\in N$，有$\sum_{j\in M}x_{ij}p_{j}\lt B_{i}$，那么$\alpha_{i}=1$。

摘要：

本文探讨了在线广告领域中自动出价（Autobidding）的重要性，并将其视为广告商优化广告活动的关键工具。作者提出了在一般仿射成本约束下进行性能出价的基本问题，并为多槽诚实拍卖中的一般出价问题设计了最优的单一代理出价策略。主要贡献是展示了出价与拍卖设计之间的紧密联系，即出价公式是最优的当且仅当底层拍卖是诚实的。此外，研究了当所有广告商采用最优自动出价时的系统视图，证明了在一般情况下，所有广告商的出价代理之间存在均衡。主要结果表明，在任何数量的一般仿射约束下，广告商在出价代理均衡中获得的总价值（转化次数）不少于通过不考虑任何拍卖激励或提供任何广告商保证的集中式广告分配方案所能生成的总价值的1/2。

要点：

提出了设计最优出价算法的问题，研究了出价与底层拍卖的互动。
证明了在多广告商采用自动出价的情况下，存在一个系统均衡。
证明了“无序的代价”（Price of Anarchy）界限，即在均衡状态下，广告商获得的总价值至少是集中式分配方案的一半。

实验方法：

本文通过理论分析和数学建模来探讨自动出价策略。
使用线性规划和对偶性来推导出最优出价公式。
利用乘法权重更新（MWU）方法来计算出价公式并据此出价。
通过扩展液态福利（liquid welfare）的定义，并使用收费论证来证明“无序的代价”结果。

不足：

文章主要关注理论分析，并未提供实验验证或实际应用案例。
对于自动出价策略在实际广告系统中的表现和效果缺乏实证研究。

展望：

未来的研究可以探索自动出价策略在不同广告平台和不同市场条件下的实际效果。
可以进一步研究如何结合机器学习技术来优化自动出价策略，以适应不断变化的市场环境。
考虑在更复杂的拍卖设置中，如多物品拍卖或有多种类型的广告位时，自动出价策略的表现和优化问题。

$$
\max\sum_{i,s}x_{is}ctr_{is}v_{i}
$$
$$
\forall c, \sum_{i,s}x_{is}ctr_{is}cpc_{is}\leq B_{c}+\sum_{i,s}x_{is}ctr_{is}v_{ic}
$$
$$
\forall i,\sum_sx_{is}\leq1
$$
$$
\forall i,s,x_{is}\in{0,1}
$$

KDD2021 | USCB:展示广告约束出价问题的通用解决方案 (qq.com)

https://mp.weixin.qq.com/s/XxYJYZ4VR5bQBYtJEtpQsw

https://mp.weixin.qq.com/s/p4LdXKM3KCIU5cMg77olxg

证明过程（对偶）

Incentive Compatibility in the Auto-bidding World

声明 5.4：在连续查询模型中，如果每次查询的拍卖是真实的，那么统一出价策略是每个自动出价代理的最优策略。

这些声明是论文中理论分析的重要组成部分，它们为证明主要定理提供了基础。

2

定理 2.1：对于预算设置（当所有广告商都受预算限制）和tCPA设置（当所有广告商都受tCPA限制），我们有SPA不是AIC的。也就是说，有一些情况下，广告商通过误报其约束可以获得好处。

Theorem 2.1. For the budget setting (when all advertisers are budgeted-constrained) and for the tCPA-setting (when all advertisers are tCPA-constrained), we have that SPA is not AIC. That is, there are some instances where an advertiser benefits by misreporting its constraint.
$$
\text{Remark 3.1 (Uniform Bidding). If the per-query action is truthful, then uniform bidding is the}\\textit{optimal policy for the autobidder. Thus, b}_a(q)=\mu+v_a(q)\text{ for some }\mu>0.\textit{ We formally prove this in Claim 5.4}
$$

3

备注 3.1（统一投标）。如果每个查询拍卖是真实的，那么统一竞价是自动投标者的最优策略。因此，对于某个μ > 0，ba(q) = μ·va(q)。我们在权利要求5.4中正式证明了这一点。

备注 3.2（价值函数信息）因此，我们的模型通过实验捕获了自动投标者在他们对市场有足够的了解后的行为。Therefore, our model captures how auto-bidders behave once they have learned enough about the market through experimentation.

定义 3.3（自动出价激励兼容性，AIC）：如果对于每一个子博弈完美均衡（SPE），我们有 Va(Ba; Ba) ≥ Va(B′ a; Ba) 和 Va(Ta; Ta) ≥ Va(T′ a; Ta) 对于每一个 Ba, B′ a, Ta, T′ a，那么拍卖规则被称为自动出价激励兼容（AIC）。

声明 3.1（统一出价）：如果每次查询的拍卖是真实的（如SPA），那么统一出价是自动出价代理的最优策略。因此，ba(q) = µ · va(q) 对于某个 µ > 0。我们在声明 5.4 中正式证明了这一点。

声明 3.2（价值函数信息）：在我们的模型中，自动出价者拥有对其代理的查询价值函数的了解，这意味着每个自动出价者对他们面临的出价格局有很好的了解。在实践中，自动出价者已经在多轮拍卖中进行了互动，在那里他们进行实验和学习。因此，经过足够多轮的实验后，每个自动出价者对他们的出价格局有了很好的了解。因此，我们的模型捕捉了自动出价者在通过实验了解了市场后的行为。这个假设在自动出价文献中相当标准（参见例如，Aggarwal 等人（2019年）；Feng 等人（2023年））。

4

定理 4.1：假设至少有两个受预算限制的广告商或两个受tCPA限制的广告商；那么FPA不是AIC的。

Theorem 4.1. Suppose there are at least two budget-advertisers or two tCPA-advertisers; then FPA is not AIC.

定理 4.2：当FPA被限制只能使用统一出价策略时，FPA是AIC的。

Theorem 4.2. FPA restricted to uniform bidding is AIC.

引理4.4：

声明 4.3：在其他自动出价者固定的情况下，存在一个乘数 µa ≥ 0，使得以下出价策略是最优的：

ba(q) =[\begin{cases} \mu_a v_a(q) & \text{if } \mu_a v_a(q) \geq \max_{a’ \neq a} b_{a’}(q) \ 0 & \text{otherwise} \end{cases} ]

这个结果无论广告商是受预算限制还是受tCPA限制都成立。

推论4.6：如果FPA和两个预算广告的自动嵌入不是AIC，那么使用相同的查询集和两个tcpa -广告器进行自动嵌入也不是AIC。

只要解 r 相对于预算和目标的比率是单调的，那么拍卖对于给定估值是 AIC。

定义 4.12（统一出价均衡）：自动出价代理子博弈的统一出价均衡对应于出价乘数 µ1, …, µN，使得每个自动出价代理 a 选择的统一出价策略 µa 在所有可行的统一出价策略中最大化问题（12），并且如果广告商 a 的约束不是紧的，则 µa 获得其最大可能值。

引理 4.13（Conitzer 等人（2022a）中定理 1 的内涵）。给定一个具有一般约束的Autobiding实例，如(13)所示，存在唯一的统一竞价均衡，所有广告商的竞价乘数在所有可行的统一竞价配置文件中都是最大的。

Lemma 4.13 (Extension of Theorem 1 in Conitzer et al. (2022a)). Given an instance of Autobidding with general constraints as in (13), there is a unique uniform bidding equilibrium, and the bid multipliers of all advertisers are maximal among all feasible uniform bidding profiles.

备注 4.14：康茨等人。(2022a) 显示了 FPA 中预算的单调性属性，收入和福利的投标均衡均匀。相反，在我们的工作中，我们专注于每个广告商的单调性。

Remark 4.14. Conitzer et al . (2022a) show monotonicity properties of budgets in FPA with uniform bidding equilibrium for the revenue and welfare. Instead, in our work, we focus on monotonicity for each advertiser.

定理 5.5（拍卖等价结果）：假设自动出价代理在SPA中使用统一出价策略，并且类似地，在FPA中使用如声明4.3中定义的简单出价策略。那么，在任何子博弈均衡中，SPA的拍卖结果（分配和定价）与FPA相同。

定理 5.6：假设至少有两个受预算限制的广告商或两个受tCPA限制的广告商；那么，即使在连续查询模型中，SPA也不是AIC的。

Theorem 5.6. Suppose that there are at least two budget-advertisers or two tCPA-advertisers; then, even for the continuous-query model, SPA is not AIC.

定理 5.7：给定两个广告商，让µ1和µ2是自动出价代理子博弈中的均衡出价乘数。还假设h(q) = v1(q) / v2(q)是递增的。那么：

如果广告商受预算B1和B2的限制，那么µ1 = B2 * E[z1(z≥r)] / E[z1(z ≤ r)]，并且µ2 = µ1 * r，其中r是以下隐式函数的解： r * E[1[z ≥ r)] / E[z1(z ≤ r)] = B1 / B2。

如果广告商受目标T1和T2的tCPA限制，我们有µ1 = T1 * E[1(z≤r)] / E[1(z≥r)]，并且µ2 = µ1 * r，其中r是以下隐式函数的解： r * E[1(z ≥ r)] / E[z1(z ≥ r)] * E[1(z ≤ r)] / E[z1(z ≤ r)] = T1 / T2。

如果进一步，v2在q上是非递减的，并且h是凹函数，并且广告商要么都是受预算限制，要么受tCPA限制，那么SPA是AIC的。

定理 5.8：考虑一个满足假设5.1的诚实拍卖（x, p）。如果有至少两个受预算限制的广告商或两个受tCPA限制的广告商，那么这个诚实拍卖不是AIC的。

Theorem 5.8. Consider a truthful auction (x, p) satisfying Assumption 5.1. If there are at least two budget-advertisers or two tCPA-advertisers, then the truthful auction is not AIC.

定理 5.9：考虑一个满足假设5.1的诚实拍卖（x, p），并假设有要么两个受预算限制的广告商，要么两个受tCPA限制的广告商。让µ1和µ2是自动出价代理在子博弈均衡中使用的出价乘数。进一步假设h(q) = v1(q) / v2(q)是递增的。那么：

如果广告商受预算B1和B2的限制，那么µ1 = B1 * E[p1(rz,1)]，并且µ2 = r * µ1，其中r是以下隐式函数的解： E[rp1(z / r, 1)] / E[zp1(r / z, 1)] = B1 / B2。

如果广告商受目标T1和T2的tCPA限制，我们有µ1 = T1 * E[zg(z / r)] / E[rp1(z / r)]，并且µ2 = µ1 * r，其中r是以下隐式函数的解： E[x1( r / z, 1)] / E[zx1(z / r, 1)] * E[rp1(z / r, 1)] / E[zp1( r / z, 1)] = T1 / T2。

[Arxiv20, UESTC/Baidu, Bin Li] Incentive mechanism design for ROI-constraint (多物品，ROI private, 用控制方法保证IC，无性能保证)

Budget Pacing in Repeated Auctions: Regret and Efficiency without Convergence

假设每个代理使用梯度下降算法（也可以认为是一种PID算法）来控制budget花费的
速度，考虑value maximizer，结论对一类core auction（包括一、二价）均成立
证明对参竞个体来说使用此算法的收益regret上界（benchmark是相较于最好的控制
预算花费速度的pacing multiplier）
当每个代理都使用此算法时，近似达到1/2的最优社会福利，不要求策略收敛到均衡
对于二价拍卖，当每个代理的regret都比较小时（不使用文章中的算法），并不一定
说明整体的福利是高的，可能会arbitrarily bad
Regret上界证明由SGD证明改编，1/2的bound与前一类不考虑动态的工作中的1/2
的证明思路有相似之处

研究背景

在线广告市场的发展：在线广告在市场中占比重大，广告通过拍卖分配，广告商面临复杂决策，需分配预算并制定出价策略。
预算管理服务的重要性：平台提供自动化预算管理服务，通过预算调整帮助广告商控制支出，调整参数以匹配目标预算，降低进入门槛，平台更易管理预算。

研究问题

在几乎所有广告商支出由自动出价代理控制且同时学习调整出价的情况下，整体市场结果如何，以及这在多大程度上取决于底层拍卖的细节。

主要贡献

提出算法及证明：提出基于梯度的预算调整算法（Algorithm 1），证明当所有代理使用该算法时，预期液体福利至少是最优预期液体福利的一半，且不依赖于算法收敛到均衡。
个体遗憾保证：分析算法在满足单调性价比（MBB）条件的拍卖中的个体性能，证明代理总价值相对于完美调整序列具有一定的遗憾界，在随机环境中，相对于最佳固定调整乘数具有$O(T^{3/4})$的遗憾界。

模型与预备知识

分配问题：重复拍卖，卖家有单单位商品出售，多个代理参与，每个代理每轮有价值，价值独立同分布且可能相关，可行分配集向下封闭。
拍卖与预算：每轮使用拍卖机制，代理观察价值后出价，拍卖有分配和支付规则，代理有固定预算，目标支出率定义为预算与时间的比值，代理使用动态出价策略。
核心拍卖：结果适用于核心拍卖，包括第一价格、第二价格和广义第二价格拍卖等，核心拍卖需满足个体理性和特定的福利最大化条件。
单调性价比：拍卖机制满足单调性价比，即增加出价导致分配增加时，单位新分配的支付增加至少等于所需的最小出价。
代理目标：定义价值最大化和效用最大化两种代理目标，本文主要关注价值最大化，即最大化总价值并受预算和出价约束。
液体福利：衡量福利的指标，考虑非准线性代理效用，定义为代理对分配的最大支付意愿，目标是最大化平台的预期液体福利。

算法与定义

预算调整算法：基于随机梯度下降，代理维护调整乘数，根据乘数和价值确定出价，每轮根据支出更新乘数，算法不会过早耗尽预算且出价不超过价值。
广义调整算法：满足不超价出价、乘数为0时出价为价值等条件的可测出价算法。
完美调整序列：每轮预期支出等于目标支出率的调整乘数序列，用于衡量个体遗憾。

实验设计

数据来源：使用2022年4月7天内从Bing广告平台收集的活动和拍卖数据，包含预算、出价、点击概率等信息。
模拟过程：对参与拍卖次数少于1000次的活动保留原始出价，其他活动模拟算法执行生成新出价，计算目标支出率和步长，使用估计的点击率和简化拍卖规则模拟拍卖结果，计算总遗憾。

研究结果

理论结果：算法在不依赖收敛的情况下实现了较好的整体市场效率和个体性能保证，液体福利至少是最优的一半，个体遗憾界在不同环境下有不同表现。
实验结果：模拟实验表明，算法在多玩家同时学习环境中，遗憾率小于$T^{3/5}$，后悔值随拍卖次数增加近似线性增长，估计第二价格拍卖的后悔率为$O(T^{0.58})$，第一价格拍卖为$O(T^{0.55})$。

未来研究方向

探索能否将结果扩展到其他算法，满足个体和整体保证，如改进个体遗憾界同时保持液体福利保证。
研究所有代理是否能同时实现零遗憾，以及在非真实拍卖中改进遗憾界，特别是在随机和对抗环境中的表现。