一个田螺突然就

中文版

研究的问题：
这篇论文探讨的核心问题是如何设计一个激励相容的拍卖机制，以最大化拍卖人的预期收益。尽管理论上在单件物品拍卖中已有较为成熟的解决方案，但在多件物品拍卖中，如何设计最优拍卖机制仍然是一个挑战。近年来，深度学习方法在这方面取得了显著进展，但现有研究通常只关注固定数量的竞拍者和物品，或者将拍卖限制为对称形式。本研究通过将竞拍者和物品的公共上下文信息纳入拍卖学习框架，克服了这些限制。

研究的对象：
研究对象是具有上下文信息的拍卖设计，即在拍卖中，每个竞拍者和物品都有相关的上下文信息。这些上下文信息能够在一定程度上描述不同的竞拍者和物品，使得拍卖更接近实际情况。例如，在电子商务广告中，有大量具有各种特征的竞拍者和物品（即广告位），每个拍卖都涉及不同数量的竞拍者和物品。

使用的技术：
论文提出了CITransNet，这是一个基于上下文集成的Transformer神经网络，用于最优拍卖设计。CITransNet结合了出价信息、竞拍者上下文和物品上下文，开发拍卖机制。它建立在Transformer架构上，能够捕捉拍卖中不同竞拍者和物品之间复杂的相互影响。CITransNet在出价和上下文上保持排列等变性，即竞拍者（或物品）在出价信息和竞拍者上下文（或物品上下文）中的任何排列都会导致拍卖结果的相同排列。此外，CITransNet的参数数量不依赖于拍卖规模（即竞拍者和物品的数量），使其有潜力泛化到具有不同竞拍者或物品的各种拍卖中。

English Version

Research Problem:
The central problem explored in this paper is how to design an incentive-compatible auction mechanism to maximize the auctioneer’s expected revenue. Although theoretical approaches have provided optimal solutions for single-item auctions, designing optimal mechanisms for multi-item auctions remains a challenge. Recently, deep learning methods have made significant progress in this area, but existing studies typically focus on a fixed set of bidders and items or restrict auctions to be symmetric. This study overcomes these limitations by integrating public contextual information of bidders and items into the auction learning framework.

Research Object:
The research object is auction design with contextual information, where each bidder and item in the auction is equipped with relevant contextual information. This contextual information can describe different bidders and items to some extent, making the auctions closer to practical scenarios. For instance, in e-commerce advertising, there are a large number of bidders and items (i.e., ad slots) with various features, and each auction involves a different number of bidders and items.

Used Technology:
The paper proposes CITransNet, a Context-Integrated Transformer-based neural network for optimal auction design. CITransNet integrates bidding information, bidder contexts, and item contexts to develop an auction mechanism. It is built upon the Transformer architecture, capturing the complex interplay among different bidders and items in an auction. CITransNet maintains permutation-equivariance over bids and contexts, meaning any permutation of bidders (or items) in the bidding profile and bidder contexts (or item contexts) will cause the same permutation of auction results. Moreover, the number of parameters in CITransNet does not depend on the scale of the auction (i.e., the number of bidders and items), giving CITransNet the potential to generalize to auctions with various bidders or items.

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)是递增的。那么：

1.

如果广告商受预算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。

2.

如果广告商受目标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。

3.

如果进一步，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)是递增的。那么：

1.

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

2.

如果广告商受目标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})$的遗憾界。

模型与预备知识

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

算法与定义

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

实验设计

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

研究结果

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

未来研究方向

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

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})$的遗憾界。

模型与预备知识

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

算法与定义

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

实验设计

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

研究结果

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

未来研究方向

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

Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics

• budget-pacing multiplier $\mu_{t}^{B^{*}}$ is any $\mu \in[0, \frac{\bar{v}}{\rho}-1]$ with $Z_{t}^{B}(\mu)=\rho,$ or o if no such μ exists.
• ROI-pacing multiplier $\mu_{t}^{R^{*}}$ is any $\mu \in[0, \gamma-1]$ wih $Z_{t}^{R}(\mu)=\rho_{t}(\mu)$ or o if no such μ exists.
• pacing multiplier $$\mu_{t}^{}:=max {\mu_{t}^{B^{}}, \mu_{t}^{R^{}} } ≥0$$
  Thus, our notion of regret is defined as follows: $Reg(T) \triangleq \sum_{t \in[T]} V_{t}(\mu_{t}^{})-\sum_{t \in[T]} V_{t}(\mu_{t})$

1. 遗憾值基准定义（Defn 14）

   • 首先定义了价值优化乘数（value - optimizing multipliers），包括预算pacing乘数(\mu_{t}^{B*})和ROI pacing乘数(\mu_{t}^{R*})。这些乘数是基于每轮的情况来定义的，用于确定出价策略。
   • 遗憾值(Reg(T))被定义为(Reg(T)\triangleq\sum_{t\in[T]}V_{t}(\mu_{t}^{*}) - \sum_{t\in[T]}V_{t}(\mu_{t}))，其中(V_{t}(\mu_{t}))表示在第(t)轮使用乘数(\mu_{t})时的价值函数，([T])表示从1到(T)的轮次集合。这个定义是为了在复杂的对抗环境下，避开标准基准导致的“花或省困境”（spend - or - save dilemma），从而能够合理地衡量算法与最优策略之间的差距。

2. 遗憾值界定的证明思路（Theorem 16）

   • 证明算法2的遗憾值是有界的。证明过程主要是将算法2的更新规则解释为对辅助函数(H_{t}^{R})和(H_{t}^{B})应用随机梯度下降（SGD）。
   • 然而，这个过程面临一些挑战。例如，在多约束情况下，更新规则比较复杂，并且辅助函数具有一些特殊性质，如ROI辅助函数(H_{t}^{R})不是凸函数等。通过巧妙地处理这些问题，比如处理只有较大乘数有反馈的情况，最终得出遗憾值(Reg(T))的上界为(Reg(T)\leq O\left(\sqrt{T}\left(\log T+\sum_{t = 1}^{T} \sigma_{t}^{R}+\sum_{t = 1}^{T} \sigma_{t}^{B}\right)\right))，其中(\sigma_{t}^{R})和(\sigma_{t}^{B})是与ROI和预算约束相关的随机变量的标准差。这表明算法2能够在双约束环境下有效地控制个体遗憾值，使其不会无限制地增长。

3. 平稳随机环境下的推论（Corollary 19）

   • 在平稳随机环境下（即拍卖的价值、成本等相关参数是平稳分布的情况），进一步分析算法的性能。
   • 得出推论(\lim_{T\rightarrow\infty}\frac{Reg(T)}{T}=0)，这意味着在这种较为理想的环境中，算法2相对于最佳固定出价的遗憾值是渐进式的。即随着轮次(T)的增加，个体遗憾值与轮次(T)的比值趋近于零，表明算法能够更好地收敛，在长期运行中能够有效地优化出价策略，使其性能接近最优固定出价策略。