CA——oCPX中PID对效率的影响讨论

本文简单讨论oCPX中PID对效率的影响

本文的 oCPX 场景设定

本文设定广告主出价点在 ROI 上 ，计费点在 CPC 上
共 $N$ 个广告主
每个广告主有一个自己的ROI，且这个ROI是广告主私有价值的真实表达
为简化讨论，假设每个广告主的预算无限
假定预估值是准确的（比如PCOC是1.0，如果不准确可以优化预估模型，本文不讨论这个问题）

单次拍卖下oCPX的效率讨论

假设在单次拍卖下，每个广告主的真实表达是ROI，此时社会福利为：
$$ \sum_{i=1}^N CTR_i\cdot CVR_i \cdot Price_i \cdot \frac{1}{ROI_i} $$
- 其中 $i$ 表示广告主索引
显然此时按照下面的公式排序是最优的：
$$eCPM_i = CTR_i\cdot CVR_i \cdot Price_i \cdot \frac{1}{ROI_i}$$
PID会在出价上增加一个PID系数 $k_i$，即：
$$Bid_{\text{cpc}} = CVR_i \cdot Price_i \cdot \frac{1}{ROI_i} \cdot \color{red}{k_i}$$
- $k_i$ 与广告主当前达成情况有关，与当前请求流量价值无关
- 显然可以看出，不同广告主的 $k_i$ 不同，此时按照 $eCPM_i = CTR_i\cdot Bid_{\text{cpc}}$ 的排序无法保证社会福利最大化了
实际上，可以证明，对于单次拍卖下，当广告主在这次请求上都表达出自己的真实ROI时，无论如何扰动出价（即任何调价策略），只要不是所有广告主的 $k_i$ 完全相同，都无法保证社会福利最大化

多轮拍卖下oCPX的效率讨论

多轮拍卖下的oCPX设定 ：广告主的ROI出价是一个投放周期内的均值，仅需要保证广告主全天的ROI即可
ROI出价下，广告主对流量没有没有除ROI外的倾向 ：由于ROI出价下，广告主已经表达了自己对流量价值的真实评估 ，所以可以假定广告主对整个周期内流量是没有除ROI外的倾向的，即所有流量价值都可通过统一的ROI来表达
- 注意：这里是因为广告主出价已经在ROI上了，可以认为全周期内流量价值是无倾向的 ，如果出价点只到CPS上或还有更深的转化点，则无法假设全周期内流量均匀（比如CPS出价下，按照天粒度为周期出价，则可能出现早上的均单价高于晚上的均单价的情况，此时ROI在全天不是完全统一的）
不调价才能保证社会福利最大化 ：由于可以假定整个周期内广告主的ROI是真实的且不变的，所以我们认为每一次请求，广告主的真实ROI是不变的，由此问题可转化为单次拍卖下oCPX问题 ，根据前面单次拍卖下oCPX的效率讨论结论可以知，不调价才能保证社会福利最大化

PID的作用

对不准确预估值进行修正 ：可以部分修正预估值不准确的情况，特别是均值
- 比如模型保障的是7天的PCOC，单天的无法保证，但oCPX周期为一天
- 比如某个广场突然开了一个演唱会，广告主的预估值不再能表达真实值
降低随机波动带来的影响 ：可以减少因为随机波动导致的广告主ROI无法达成的情况
- 正常的随机波动可能导致某一段时间内欠成本或超成本（即使预估值准确），PID的引入可以在欠成本时刻意提升出价、超成本时刻意降低出价，使得ROI成本在有限的竞价轮次内尽快达成

附录：预估值准确了为什么还需要PID？

如果无限拉长周期 ，在预估值 $CVR_i \cdot Price_i$ 准确（特别是保证PCOC为1）的情况下，无需调整出价（直接按照PID系数 $k_i=1$ 来出价），在无限次拍卖下 ，统计意义上广告主的ROI是可以保证达成的，这一点由大数定理来保证；
在现实场景中，每个广告主拍卖次数是有限的，且广告主的后验转化率在有限的周期内等会在期望附近波动（这是随机性导致的，即使预估模型足够准确也会出现）。此时如果不调整出价 ，无法保证在单个有限拍卖次数的周期内能达成ROI
- 具体表现为：广告主长远来看ROI是达成的 ，但是广告主的ROI在一个周期内超成本 ，在另一个周期内欠成本 ，来回波动
- 解决方案：针对后验转化率 ，对出价系数进行调整，比如PID方法 ，尽量保证每个周期内都能达成

附录：预算有限的情况下结论一样吗？

预算有限的情况下，以上结论不成立：此时广告主可以有取舍，在不同流量上会有不同的ROI出价，有选择的对流量进行取舍，从而提升平台整体的的社会福利
- 预算有限场景的举例：
  - 两个广告主A，B；两个请求（请求1,2依次发生）
  - 广告主A预算为10，对请求1福利为10，广告主A对请求2福利为9；
  - 广告主B预算为20，对请求1福利为10，广告主B对请求2福利为1；
  - 则广告主A在请求1上不花钱（说假话），且在请求2上花10整体社会福利为19，广告主A在请求1上说真话时社会福利为11

CA——oCPX产品赔付机制的讨论

本文简单讨论oCPX产品赔付机制

参考链接：

百度赔付规则

赔付统计周期
- 3个自然日，今日投放，则未来3天内都是统计周期
赔付条件
- 1）在返款统计周期内转化数累计≥5；
- 2）超出广告主预期消费20%，（实际消费-预期消费）／预期消费>20%；
- 3）在返款核算评估期间，每天修改广告单元出价的次数≤2次；
赔付金额
- 1）预期消费 =（目标成本1 * 对应转化数）+（目标成本2 * 对应转化数）+ …（目标成本n*对应转化数）
- 2）返款金额 = 实际消费 - 预期消费

字节赔付规则

赔付统计周期
- 5个自然日，今日投放，则未来5天内都是统计周期
赔付条件
- 1. 超成本比例：转化成本超过目标成本的20%以上（举例：目标成本10元，转化成本≥12元）
- 1. 赔付时间范围：以广告计划首次投放出去的时间为起始，至之后的3个自然日内（投放时间以平台统计为准）
- 1. 修改要求：每天修改广告计划出价或定向其中任意一个的次数不能超过2次
- 1. 转化数量要求（不含一键起量、账户优选起量的转化数），这里不同的媒体平台和计费模式不同
    - oCPM场景，一般在2-6个转化不等，oCPC场景，要求大于31个转化才赔付
- 1. 广告主无异常作弊等操作行为
赔付金额
- 1. 总预期消耗 =（目标成本1 * 对应转化数）+（目标成本2 * 对应转化数）+ …
- 1. 赔付金额 = 总实际消耗 - 总预期消耗

快手赔付规则

赔付统计周期
- 14个自然日，今日投放，则未来14天内都是统计周期，其中直播推广的商品点击等场景是2个自然日
赔付条件
- 超过120%
- 同一天内修改次数小于等于两次（注意是同一天内小于等于2次，任意一天不满足都不赔付）
- 转化数超过一定阈值
赔付金额
- 同字节和百度

趣头条赔付规则

赔付统计周期
- 3个自然日，今日投放，则未来3天内都是统计周期
赔付条件
- 单元所在赔付周期内，实际转化成本超过目标出价的20%以上（举例：目标出价30元，则在单元实际成本>36元时享有赔付资格）；
- 在一个赔付周期内，单元的出价（含目标出价、深度转化出价、目标次留率）及单元定向，每天修改次数分别不超过2次，如超过则所在周期失去赔付资格；
  - 注意这里是赔付周期内不能修改超过2次（其他公司常用每天不超过2次）
- 赔付周期内转化数超过一定阈值
赔付金额
- 同字节和百度

拼多多

无赔付（截止到25年4月）

整体总结

赔付统计周期
- 一般在3-14天不等（主要是面临转化归因慢的问题）
赔付条件
- 超过120%（主要是避免因为正常波动导致的超成本）
- 同一天内改价次数不能超过2次（主要用于防止广告主频繁改价作弊，同时也防止出价目标变化太快，系统来不及调整）
- 赔付周期内有一定的转化数（减少广告主不回传/说假话）
赔付金额
- 赔付金额 = 总实际消耗 - 总预期消耗 = 总实际消耗 - （目标成本1 * 对应转化数）+（目标成本2 * 对应转化数）+ …（主要是保证广告主改价的体验）

一些特殊场景的oCPX赔付规则思考

子问题：在订单闭环、广告主广告理解能力弱、对平台信任度低、广告主订单数据特别稀疏的场景中，可以如下设置赔付规则？
赔付周期：
- 1天为周期赔付（促进广告主信任和理解）
赔付条件：
- 超成本就赔付（促进广告主理解和信任，120%赔付下给广告主的解释成本较高，后续可以逐步尝试）
- 转化数无要求（闭环情况下，广告主无法说假话）
- 消耗金额给与一定要求（防止广告主投放中途为了赔付而关闭投放）
- 改价次数尽量少（防止目标波动）
赔付金额：
- 规则设计：赔付金额 = 总实际消耗 - （总转化数 * 当日最大目标成本）
- 这样设计的好处有：
  - 能起到不鼓励广告主改价的效果，因为从赔付金额计算方式来看，广告主改价一定是亏的（有效促进系统稳定性）
  - 方便系统统计和归因（不需要记录成本改价时间和订单具体归因时间，部分订单是难以归属上准确时间的）
  - 容易给到广告主解释（比如11点改价，那么10:59点击带来的11:02分下单的订单如何归因？广告主理解成本较高）
- 这样设计的坏处有：
  - 这种情况不鼓励广告主改价，从而广告主可能也不愿意向上提价（这里通过提价后系统给扶持来部分缓解）
  - 系统策略可能hack规则不论广告主是否改价都按照最高价收（需要注意为了价格杠杆考虑，也为了广告主利益考虑，不应该按照最高价出价，而应该在每个时刻都按照广告主当前设置目标出价）

CA——多任务学习总结

多任务学习，multi-task learning

参考链接：

多任务学习的结构

预估任务中一般包含ESMM及扩展，MMoE及相关变体
NLP中的MoE则是挑选部分网络，会丢弃部分网络

多任务学习的损失函数权重设置

基于人工经验的人工优化

一般思想是对齐损失函数均值，并按照业务偏好有所倾斜，如果愿意花时间尝试，往往能拿到不错的结果

基于贝叶斯推论的权重优化

基于不确定性的权重设置方法（Uncertainty Weighting）
基本公式
$$
L(\mathbf{W}, \sigma_1, \sigma_2,…,\sigma_K) = \sum_{k=1}^K \frac{1}{2\sigma^2}L(\mathbf{W}) + \log \sigma^2
$$
- 上述公式可通过推导得出Multi-Task Learning Using Uncertainty to Weigh Losses for Scene Geometry and Semantics
  - 可以推导，无论是回归问题还是分类问题（也可以是分类和回归问题的混合），都可以按照上面的方法设置损失函数（分类问题证明中会使用到一个近似值，不是严格推导）
  - 推导是在假设
- $\sigma$ 是可学习的参数，初始设置固定值，然后使用梯度更新学习即可
- 使用简单，实际使用时效果也确实不错，建议人工调参也可以在先使用该方案拿到权重量级后继续

帕累托最优权重优化

原始论文：Multi-Task Learning as Multi-Objective Optimization
内积的含义：向量A到向量B的投影长度与向量B长度的乘积
Algorithm1展示的是，对于两个任务的情况，图示展示了二维向量的情况，可以通过判断向量之间的关系确定求解 $\alpha$ 的方式
- Algorithm2中的FrankWolfeSlover算法则是对Algorithm1的多任务扩展
其他参考，阿里巴巴多任务学习帕累托最优论文：A Pareto-Efficient Algorithm for Multiple Objective Optimization in E-Commerce Recommendation

损失函数优化

损失函数归一化

可用于解决由于不同任务损失函数量级差异带来的问题

普通版本

$$
L_{norm} = \frac{L_k(\mathbf{W})}{L_0(\mathbf{W_0})}
$$

使用各个任务自己的第一次输出的损失函数作为基础损失函数，其中 $L_0(\mathbf{W_0}$ 为第一次计算loss的到的损失函数

滑动平均版本

$$
L_{base} = \alpha L_{base} + (1-\alpha) L_k \\
L_{norm} = \frac{L_k(\mathbf{W})}{L_{base}} \\
$$

使用滑动平均来记录基础损失函数，该方案可进一步减少由于初始化损失误差过大带来的问题

梯度归一化（GradNorm）

原始论文：GradNorm: Gradient Normalization for Adaptive Loss Balancing in Deep Multitask Networks
核心思想是对各任务的损失函数进行加权($w_i$)求和得到更新共享参数的损失函数
“GradNorm”这个名字的由来是因为权重 $w_i$ 是与梯度2范数的期望等有关的？
公式中 $w_i$ 是各个任务损失函数对共享参数损失函数的权重，该权重初始值为1，在训练过程中逐步更新，每一步最后都保持该权重加和为 $T$ （ $T$ 为任务数量，即保证权重均值为1）
问题：文中没有明确各个任务各自的参数如何更新，猜测各自更新即可

最佳实践

一般情况下，根据业务特点，尽量使用类似于ESMM结构
权重设置尝试次序：
- 对损失函数进行归一化（梯度归一化好像效果一般？）
- 权重设置时，先使用不确定性权重（Uncertainty Weighting）跑一版，得到基线
- 在Uncertainty Weighting的基础上，人工可以根据业务需要微调，可以偏向于需要的任务
- 帕累托最优实现复杂，且不一定有收益
  - 复杂体现在：需要在每个batch上重新求解最优化问题，得到当前的loss权重（用上一个batch的梯度求解这一个batch的最优权重）

CA——各种拍卖机制总结

参考链接：
- 万字长文，漫谈广告技术中的拍卖机制设计（经典篇）

Myerson拍卖

Myerson机制就是单物品拍卖下，可以获得最大化期望收益的最优机制

from 万字长文，漫谈广告技术中的拍卖机制设计（经典篇）
Myerson机制就是可以获得最大化期望收益的最优机制。首先定义虚拟估值 $\varphi_i(v_i) = v_i - \frac{1-F_i(v_i)}{f_i(v_i)}$，它和私有估值以及分布有关；然后可以论证在满足DSIC的机制空间上对期望收益最大化 ，可以等同于在同一个空间对期望虚拟福利最大化 ，这样原本关心的收益最大化问题就转变为了分配最优化问题， $Rev = \max\sum_{i=1}^n \varphi_i(v_i) x_i$，与前文2.1.章节中 $SW = \max\sum_{i=1}^n v_i x_i$ 相比仅仅是将私有估值 $v_i$ 转换为对应的虚拟估值 $\varphi_i(v_i)$，其他分配规则的细节以及扣费规则都与社会福利最大化一模一样；最后只需要保证 $\varphi_i(v_i)$ 是单调的，即私有估值的分布 $F_i(v_i)$ 是正则分布 ，许多常见分布基本都是正则分布，例如normal、lognormal、uniform and exponential distributions等；非正则分布包括多峰分布和长尾分布，分配的单调性是机制DSIC性质的前提。论证过程可详见文献
可以发现虚拟估值 $\varphi_i(v_i)$ 可能为负，在分配的过程中如果遇到 $\varphi_i(v_i) < 0$ 的竞拍者会被剥夺竞拍资格，如果所有竞拍者的虚拟估值均为负，则流拍，所以 $\varphi_i^{-1}(0)$ 即虚拟估值为0的逆函数起到了个性化保留价的功能。如果假设所有竞拍者的私有估值服从独立但不同分布，则不仅会有各自不同的保留价，还会遇到如实报价情况下报价高，但虚拟估值不一定高，导致没有竞得更好的资源位，也好理解，此时虚拟估值代表了个性化自己和自己对比的报价意愿强烈程度；如果假设所有竞拍者的私有估值服从独立同分布，因为估值分布相同则虚拟估值函数 $\varphi$ 也相同，又因为估值分布 $F$ 服从正则分布，则 $\varphi$ 严格递增，那么虚拟估值最高的竞拍者就是私有估值最高的竞拍者，这样虚拟福利最大化机制就和带有保留价 $\varphi_i^{-1}(0)$ 的二价机制相同，回答上文提到的两个竞拍者估值服从独立同分布 $[0,1]$ 均匀分布的例子，$\varphi_i^{-1}(0)=\frac{1}{2}$ S确实是最优保留价。以下是单物品拍卖的几个机制对比：

VCG

Vickrey-Clarke-Groves (VCG)

普通的VCG

WVCG

Weighted Vickrey-Clarke-Groves (WVCG)，带权重的VCG机制，是对原始VCG的改进，收入高于VCG机制

VVCA

SW-VCG

SW-VCG, Score-Weighted VCG
原始论文：Learning-Based Ad Auction Design with Externalities: The Framework and A Matching-Based Approach
博客：KDD’23 | Score-Weighted VCG：考虑外部性的智能拍卖机制设计

GSP

一些对比 from 万字长文，漫谈广告技术中的拍卖机制设计（经典篇）：

普通的GSP

uGSP

Utility-based Generalized Second Price auction (uGSP)，最早提出于论文 Optimising trade-offs among stakeholders in ad auctions, Microsoft Research, 2014. 是对GSP的一种扩展，其分配规则中的排序公式为：
$$ r_i(b_i) = \lambda_1 \times b_i \times pCTR_i + o_i $$
- 其中 $o_i$ 表示其他效用指标，比如作者使用了 $o_i = \lambda_2 \times pCTR_i + \lambda_3 \times pCVR_i$
支付规则与GSP相同，都是通过下一位的排序分反算计费

wGSP

wGSP（weighted GSP，weighted体现在广告质量分的引入），排序时会在出价上乘以这个权重 $\beta \cdot bid$ 来排序

mGSP

mGSP（myerson GSP）机制，将Myerson保留价技术直接应用到wGSP机制上

from 万字长文，漫谈广告技术中的拍卖机制设计（经典篇）
和单物品拍卖的设计思路类似，Myerson保留价最核心的虚拟估值依赖广告主的私有估值分布，系统可以酌情根据独立同分布的颗粒度进行假设的调整，例如客户之间完全独立不同分布、相同搜索词的客户之间独立同分布、整体流量客户独立同分布等。因为广告系统是多轮拍卖系统，假设广告主是如实报价，则私有估值分布可以根据广告主历史报价进行不同粒度的分布拟合，从而得到虚拟估值。有了虚拟估值和保留价，在分配规则方面有两种类型可做尝试：Eager模式，先过滤后排序，即先根据保留价过滤没有竞争力的广告主，再按照虚拟估值排序；Lazy模式，先排序后过滤。Eager模式对最高报价无法胜出保留价的情形更友好，Lazy模式对第2高报价无法胜出保留价的情形更友好，多数情况下Eager模式在提营收方面会比Lazy更有优势

aGSP

aGSP（anchoring GSP）机制，是对mGSP机制一种松弛方式

from 万字长文，漫谈广告技术中的拍卖机制设计（经典篇）
第二种是aGSP（anchoring GSP）机制，是对mGSP机制一种松弛方式，业务落地过程中虚拟估值的求逆计算和私有估值的正则分布要求等均会让机制实现不够简洁且解释性较差，略牺牲效果的情况下精简机制设计也是可接受的迭代方向。首先保留价的计算方法和mGSP机制相同，一般保留价的颗粒度会选择数据积累较为充分的粒度。其次主要差异点就是将虚拟估值由 $\varphi_i(v_i) = v_i - \frac{1-F_i(v_i)}{f_i(v_i)}$ 简化为 $\varphi_i(v_i) = v_i - r_i$，如果假设私有估值分布是均匀分布，化简的表达式就非常接近，求逆也方便，而且业务含义与myerson思路很吻合，报价竞争力更多看重每个广告主超出个性化保留价的那部分

rGSP

rGSP（reserve GSP）机制，是对aGSP机制更加进一步的松弛

from 万字长文，漫谈广告技术中的拍卖机制设计（经典篇）
因为有文献提出，为了解决私有估值和虚拟估值趋势不一致问题，虚拟估值可以仅用于个性化保留价的过滤，分配和扣费依然按照私有估值进行，这样虽然对营收有折损但是机制实现更加简洁且易解释

iGSP

iGSP（iterated GSP）可以最大限度保证 existence of efficient equilibria，但也仅限2个资源位同时拍卖，如果遇到3个及以上就仍然是一个 open question，不过还算乐观的情况是移动端的资源位往往较少

sGSP

原始论文：Revenue analysis of a family of ranking rules for keyword auctions
sGSP(squashing GSP)

from 万字长文，漫谈广告技术中的拍卖机制设计（经典篇）
另外一类不是在报价因子上做文章，而是在wGSP的广告质量点击率上做文章，通过对广告质量点击率进行挤压，也能达到提升营收的效果，这类机制叫做sGSP（squashing GSP）机制。分配规则是按照 $\beta^s_i b_i$ 进行排序，其中 $s$ 就是挤压因子，扣费规则按照 $p_i = \frac{\beta^s_{i+1} b_{i+1}}{\beta^s_i} = \left( \frac{\beta_{i+1}}{\beta_i} \right)^s b_{i+1}$。该挤压因子能够体现三方面的结论：1）Efficiency视角：当 $s=1$ 是社会福利最大化及Efficiency最大化，凡是 $s \neq 1$ 的调节都提升平台的短期收入，从而影响广告主价值；2）Relevance视角：只要 $s$ 往大调节，整体点击率就会提升，相关性就会变好；3）Revenue视角，当相邻广告质量随排序递减即 $\frac{\beta_{i+1}}{\beta_i} < 1$ ，在不改变排序的情况下调小 $s$，$p_i$变大，利好营收增加，当相邻广告质量随排序递增即 $\frac{\beta_{i+1}}{\beta_i} < 1$，在不改变排序的情况下调大 $s$，$p_i$变大，利好营收增加。这一方案为了进一步挖掘营收空间，可以升级为分位置调控挤压因子等，具体详见文献

Deep GSP

Deep Neural Auction (DNA)

NMA

原始论文：NMA: Neural Multi-slot Auctions with Externalities for Online Advertising, 2022, ArXiv preprint, Meituan

(RegretNet)Optimal Auctions through Deep Learning

(AMA)Affine maximizer auction

参考论文：A Scalable Neural Network for DSIC Affine Maximizer Auction Design, NeurIPS 2023, PKU，Spotlight

附录：一些特殊拍卖

BDFPA

折价一价拍卖(bid-discount first-price auction,BDFPA)，来源于文章Budget-Constrained Auctions with Unassured Priors: Strategic Equivalence and Structural Properties, Tencent

PFPA

pacing first-price auction

BROA

Bayesian revenue-optimal auction

BDSPA

bid-discount second-price auction

PSPA

pacing second-price auction

综合对比

集资拍卖相关

(JAMA)Joint-Bidding-in-Ad-Auctions

参考论文：Joint Bidding in Ad Auctions, pp 344–354, TAMC 2024, Meituan

(JRegNet)Joint Auction in the Online Advertising Market

参考论文：Joint Auction in the Online Advertising Market, KDD 2024, Meituan

CA——Truthful-Auctions-for-Automated-Bidding-in-Online-Advertising

本文研究智能出价下的Truthful拍卖

参考链接：
- 论文原文：Truthful Auctions for Automated Bidding in Online Advertising, IJCAI 2023, Alibaba
- 官方博客：自动出价下机制设计系列 (二) ：面向私有约束的激励兼容机制设计

目标及思路

研究自动出价下的 Truthful 拍卖机制（即：也称为激励兼容（incentive-compatible）或说真话（truth-telling）的拍卖机制）
- Truthful拍卖机制需要同时满足：激励兼容性 和 个体理性
  - 激励兼容性（Incentive Compatibility, IC） ：竞拍者通过报告其真实估价获得的效用不低于任何其他策略下所能获得的效用。这意味着对于竞拍者来说，诚实是最好的策略
  - 个体理性（Individual Rationality, IR） ：如果竞拍者赢得拍卖，他支付的价格不会超过他对该物品的真实估价。因此，他的净收益（即他的估价减去支付的价格）将是非负的。即使竞拍者没有赢得拍卖，由于他没有支付任何费用，他的净收益也是零或正数
设定场景：商家设定ROI + 预算约束（传统的拍卖模型不再适合这种新的广告范式）
分配：采用排名分数作为确定 item 分配的标准，这与广义第二价格（GSP）拍卖的思想相似
计费：在保证私人约束的真实性方面，设计了一个关键ROI ，即在不超出预算约束的情况下能够赢得最多 item 的最大ROI，这等价于将预算转换为与ROI相同的维度，从而允许论文找到一个紧约束，限制竞拍者获得额外效用，并利用该紧约束防止虚假报告

场景定义及讨论

自动出价（auto-bidding）：广告主向平台提交其高层优化目标和约束条件，然后由机器学习算法驱动的出价代理代表广告主在每次广告拍卖中做出详细的出价决策。借助自动出价工具，广告主可以在高层面上根据其财务约束优化其整体广告目标
传统的拍卖模型 ：在传统模型中，广告主对 item （即广告展示）具有私人价值，并在每次拍卖中进行相应的策略性出价
自动出价场景的拍卖模型 ：自动出价中，广告主的私人信息实际上是其整个广告活动的约束条件 ，公开信息是用户的潜在行为（如点击和转化 ，这些行为可以被视为广告主对 item 的公开价值，因为此时通过预估模型可以将CTR和CVR预估出来）；机制设计的目标是找设计一种新的广告拍卖模型，以激励广告主在** item 价值公开的情况下如实揭示其高层私人约束**
论文自动出价场景定义 ：广告主提交预算和投资回报率（ROI）要求作为其 （私人）约束 ，并旨在最大化在一定时期内从多次拍卖中获得的累积价值
论文主要内容：
- 提出了一种自动出价（即价值最大化的竞拍者具有私人约束作为私人信息，而 item 的价值是公开的（即CTR，CVR等公开））下的拍卖模型
- 研究了在公开价值设置下，预算和ROI这两个私人约束的真实性条件，为Truthful拍卖的分配和支付的可行空间提供了完整的特征描述
- 基于推导出的真实性条件，论文设计了一类用于自动出价的真实广告拍卖机制
- 实验评估拍卖机制在社会福利和收入方面的有效性

整体分析

在线广告系统

在线广告拍卖系统的工作过程如图1所示
从广告主的角度来看，它可以描述如下：
- 广告主在选择优化目标（例如，最大化点击或转化）并设置成本约束（例如，每日预算、目标投资回报率（ROI）和每次点击的最大成本）。广告主要求其实现的ROI（定义为获得的价值与支付的比率）高于其目标ROI
- 根据广告主的配置，自动出价代理代表广告主在多次拍卖中做出出价决策。当每次用户展示出现时，自动出价代理参加广告拍卖以竞争广告展示机会
- 自动出价代理会预测每个请求下，用户展示为广告主带来的价值（点击率或转化率），并在考虑成本约束的情况下为每次展示/点击出价
- 在多次拍卖中，广告主可以查看累积的拍卖结果，包括花费的预算、获得的展示、点击、转化和平均成本。广告主可以进一步调整其自动出价设置以实现其广告目标
自动出价服务的在线广告与传统在线广告的不同：
- 广告主仅在出价配置中报告优化目标和约束 ，而不是每次拍卖的细粒度出价
- 广告主仅评估多次拍卖的累积长期表现和成本 ，而不是每次单独拍卖的结果
- 由于在线平台可以访问广告中产生的所有数据，因此可以合理地声称特定广告主对请求位置展示/点击的货币价值可以精确计算（公开信息）
由于广告主和在线平台的行为模式在自动出价中发生了显著变化，论文需要研究自动出价下的新机制
注：接下来论文主要研究展示计费的场景

拍卖模型

拍卖场景定义：
- 有 $n$ 个广告主在 $m$ 个时间段内竞争 $m$ 个 item（用户展示），每个时间段只出现一个 item
- 广告主是价值最大化（value-maximizing）的竞拍者，他们在支付不超出其财务约束的情况下关心其分配到的展示的累积价值
- 每个广告主 $i$ 具有预算（ $B_{i}\geq 0$ ）和ROI（ $R_{i}>0$ ）约束，这些是私人信息（在机制设计文献中也称为类型 $t_{i}=(B_{i},R_{i})$ ）
- 所有广告主的类型概况为 $\mathbf{t}=(t_{i})_{i=1}^{n}$ ，类型概况的空间为 $\mathcal{T}=\prod_{i=1}^{n}\mathcal{T}_{i}$ ，其中 $\mathbf{t}\in\mathcal{T}$ 且 $\mathcal{T}_{i}={\cal B}_{i}\times{\cal R}_{i}$ ；除竞拍者 $i$ 之外的其他竞拍者的报告类型为 $\mathbf{t}_{-i}=(t_{1},\ldots,t_{i-1},t_{i+1},\ldots,t_{n})$ ，且 $\mathcal{T}_{-i}=\prod_{k\neq i}^{n}\mathcal{T}_{k}$
- 假设广告主对 item 的估值是平台的公开信息 ，使用 $v_{i,j}>0$ 表示广告主 $i$ 对 item $j$ 的估值
机制设计：在收集所有竞拍者的预算和ROI后，在线平台采用某种拍卖机制（ $\mathcal{A},\mathcal{P}$ ）来决定广告分配和支付
- 其中 $\mathcal{A}$ 表示（随机化的）分配规则 $\mathcal{A}:\mathcal{T}\rightarrow[0,1]^{n\times m}$
- $\mathcal{P}$ 表示（随机化的）支付规则 $\mathcal{P}:\mathcal{T}\rightarrow\mathbb{R}^{n}$
- 具体来说，对于报告的类型概况 $\mathbf{t}^{\prime}\in\mathcal{T}$ ，竞拍者 $i$ 被分配到 item $j$ 的概率表示为 $a_{i,j}(\mathbf{t}^{\prime})$ ，竞拍者 $i$ 的预期支付表示为 $p_{i}(\mathbf{t}^{\prime})$ 。对于任何 item $j\in[m]$ ，分配约束为 $\sum_{i=1}^{n}a_{i,j}(\mathbf{t}^{\prime})\leq 1$
- 一些变量和符号说明：
  - 竞拍者 $i$ 在这些拍卖中的累积价值为:
    $$v_{i}(\mathbf{t}^{\prime})=\sum_{j=1}^{m}v_{i,j}a_{i,j}(\mathbf{t}^{\prime}),$$
  - 其实现的ROI为（注：如果 $p_{i}(\mathbf{t}^{\prime})=0$ ，则视为 $+\infty$ ）:
    $$ \text{ROI}_{i}(\mathbf{t}^{\prime}):=\frac{v_{i}(\mathbf{t}^{\prime}) }{p_{i}(\mathbf{t}^{\prime})} $$
具有预算和ROI约束且真实类型为 $t_{i}=(B_{i},R_{i})$ 的竞拍者在报告 $t^{\prime}_{i}$ 时的效用定义为
$$u_{i}\left(t_{i},\mathbf{t}^{\prime}\right)=\begin{cases}v_{i}(\mathbf{t}^{\prime}),\text{if }p_{i}(\mathbf{t}^{\prime})\leq B_{i}\text{ 且 }\text{ROI}_{i}(\mathbf{t}^{\prime})\geq R_{i},\\ \ -\infty,\text{otherwise},\end{cases}$$
- 其中类型概况 $\mathbf{t}^{\prime}=(t^{\prime}_{i},\mathbf{t}^{\prime}_{-i})$
论文的目标是设计满足激励相容（IC）和个体理性（IR）条件的真实拍卖机制

论文设定下的一些定义

定义 2.1 一个拍卖机制是占优策略激励相容（DSIC）的，如果 $\forall i\in[n]$ ， $t_{i},t^{\prime}_{i}\in\mathcal{T}_{i},\mathbf{t}_{-i}\in\mathcal{T}_{-i}$ ： $u_{i}(t_{i},(t_{i},\mathbf{t}_{-i}))\geq u_{i}(t_{i},(t^{\prime}_{i},\mathbf{t}_{-i}))$
定义 2.2 一个拍卖机制是个体理性（IR）的，如果 $\forall\mathbf{t}\in\mathcal{T}$ ， $i\in[n]$ ： $p_{i}(\mathbf{t})\leq B_{i}$ 且 $\text{ROI}_{i}(\mathbf{t})\geq R_{i}$ 。（注：这个定义与传统定义完全相同）
在线平台通常有一些需要最大化的目标。两个常见的设计目标是收入和社会福利。收入定义为竞拍者支付的总和，即 $\sum_{i}p_{i}(\mathbf{t})$ 。对于社会福利，论文需要一个同义的指标，即流动性福利（Liquid welfare），定义为在不违反IR约束的情况下可以从竞拍者中提取的最大收入 ，以纳入财务约束的存在。在论文的背景下，流动性福利可以定义为：
$$\text{LW}=\sum_{i\in[n],u_{i}(t_{i},\mathbf{t}^{\prime})\geq 0}\min\left(\frac{v_{i }(\mathbf{t}^{\prime})}{R_{i}},B_{i}\right).$$

真实性条件的特征

预算的真实性的条件

特殊说明：为了满足预算上的激励相容性（IC）属性，论文需要确保竞拍者不会通过报告较小或较大的预算来获得更高的效用 ，以防止虚假报告：
- 由于报告较小的预算不会导致竞拍者超出其原始预算约束，因此减少预算所获得的效用应该减少；
- 对于报告较大预算并获得更高价值的竞拍者 ，论文需要通过收取费用使其超出原始预算约束（注：这里的原始预算约束是其真实预算约束），从而导致负无穷的效用
定理 3.1 一个拍卖机制在预算 $B$ 上是占优策略激励相容（DSIC）的，仅当 $\forall i\in[n]$ ， $R\in\mathcal{R}_{i}$ ， $\mathbf{t}_{-i}\in\mathcal{T}_{-i}$ 时：
- （1） $v_{i}\left((B,R),\mathbf{t}_{-i}\right)$ 在 $B$ 上是非递减的；
- （2）如果对于 $B^{\prime}>B$ ， $v_{i}\left((B^{\prime},R),\mathbf{t}_{-i}\right)>v_{i}\left((B,R),\mathbf{t}_{-i}\right)$ ，则
  $$p_{i}\left((B^{\prime},R),\mathbf{t}_{-i}\right)>B.$$
  - 理解：ROI不变的情况下，更多的收益意味着需要付出更多的钱。如果预算大与B导致获得的收益大比预算B时的大，则一定要付出比B更多的钱；当然，如果没有因为预算变大而获得比预算B下更多的收益，则计费是可以不用大于预算B的
- 注意：不是当且仅当，是必要条件

ROI的真实性条件

ROI也可以同预算相关我们可以通过类似的陈述来说明ROI，表明竞拍者没有动机虚假报告其ROI
定理 3.2 一个拍卖机制在ROI $R$ 上是占优策略激励相容（DSIC）的，仅当 $\forall i\in[n]$ ， $B\in\mathcal{B}_{i}$ ， $\mathbf{t}_{-i}\in\mathcal{T}_{-i}$ 时：
- （1） $v_{i}\left((B,R),\mathbf{t}_{-i}\right)$ 在 $R$ 上是非递增的；
- （2）如果对于 $R^{\prime}<R$ ， $v_{i}\left((B,R^{\prime}),\mathbf{t}_{-i}\right)>v_{i}\left((B,R),\mathbf{t}_{-i}\right)$ ，则
  $$\text{ROI}_{i}\left((B,R^{\prime}),\mathbf{t}_{-i}\right)<R.$$
  - 理解：预算不变的情况下，更多的收益意味着更小的ROI
- 注意：不是当且仅当，是必要条件

ROI和预算下的真实性条件

说明：定理3.1和3.2中条件（1）所需的单调性属性与具有私人估值的准线性竞拍者的真实性条件（例如Myerson引理）相似，但条件（2）揭示了它们的基本差异：为了防止虚假报告，必须通过收取费用来打破至少一个约束（导致负无穷的效用）
- 这里第二个条件是与Myerson引理最大的不同
定理3.1和3.2自然地为二维类型 $(B,R)$ 的DSIC提供了必要条件。以下结果表明，这些条件也提供了充分条件。也就是说，如果竞拍者无法通过虚假报告其一个约束来获得更高的效用，那么虚假报告两个约束也无法获得更高的效用
- 注：仅包括 $(B,R)$ 两个维度，所以称为二维类型
定理 3.3 一个拍卖机制在预算和ROI上都是占优策略激励相容（DSIC）的，当且仅当它满足定理3.1和3.2

From 自动出价下机制设计系列 (二) ：面向私有约束的激励兼容机制设计:
上述引理中的单调递增/递减是非严格的。引理3与引理4自然地构成了 $(B,R)$ 双参数DSIC的必要条件。论文进一步证明了，它们实际上也构成了充要条件，也就是说，当竞拍者无法通过在单参数上的虚报获得更高效益时，也同样无法通过双参数上的同时虚报来获得更高的效益
- 详细证明还需要再思考

可行分配规则的结构（Structures of Feasible Allocation Rule）

本节描述了可行的分配规则应该长什么样

可行的分配规则定义：如果分配规则 $\mathcal{A}$ 是可行的，则存在一个支付规则 $\mathcal{P}$ 使得机制 $\mathcal{A},\mathcal{P}$ 满足 Truthful（这里 Truthful 指的是拍卖机制能够激励参与者诚实地报告他们的估值或偏好）
- 可行分配规则的集合是我们可以搜索真实拍卖的空间，尽管可能存在多个构成可行分配规则 $\mathcal{A}$ 的真实拍卖的支付规则（问题：一个分配规则应该对应唯一的DSIC的拍卖规则吧？），但下面的定理允许论文专注于最大支付规则
- 在激励相容的或者说是 truthful（真实的）的机制下，参与者的最佳策略是根据他们对物品的真实价值进行出价，而不是试图通过策略性出价来获得优势。而 最大支付规则 则指的是一种特定的支付规则，它确保了机制的激励兼容性，并且在这种规则下，支付额度是在保证机制真实性的前提下的最大值
- 定义这种规则有助于简化拍卖机制的设计与分析

定理3.4 ：对于一个可行的分配规则 $\mathcal{A}$，下面的计费机制 $\mathcal{P}$ 对于所有的 $i\in[n],(B_{i},R_{i})\in\mathcal{T}_{i}$，$\boldsymbol{t}_{-i}\in\mathcal{T}_{-i}$，构成一个真实的拍卖机制（注意：这里不是唯一的 Truthful 拍卖机制）：
$$
p_{i}\left((B_{i},R_{i}),\boldsymbol{t}_{-i}\right)=\min\left(\frac{v_{i}\left((B_{i},R_{i}),\boldsymbol{t}_{-i}\right)}{R_{i}},B_{i}\right),
$$
- 定理3.4的证明（注：论文的证明都在附录里）：由于 $\mathcal{A}$ 是可行的，存在对应的 $\mathcal{P}^{\prime}$，使得 $(\mathcal{A},\mathcal{P}^{\prime})$ 是一个满足DSIC和IR条件的机制。注意到 $p_{i}(B_{i},R_{i})=\min\left(\frac{v_{i}(B_{i},R_{i})}{R_{i}},B_{i}\right)$ 是从竞拍者 $i$ 的类型 $(B_{i},R_{i})$ 中提取的最大可能支付，以满足竞拍者的ROI和预算要求。也就是说，$p^{\prime}_{i}(B_{i},R_{i})\leq p_{i}(B_{i},R_{i})$。另一方面，增加某个类型的支付不会破坏原本满足的定理3.1和3.2中的条件。因此，将支付从 $p^{\prime}_{i}$ 修改为 $p_{i}(B_{i},R_{i})=\min\left(\frac{v_{i}(B_{i},R_{i})}{R_{i}},B_{i}\right)$ 满足竞拍者的预算和ROI 要求，并保持DSIC条件，因此 $(\mathcal{A},\mathcal{P})$ 是一个真实的机制
定理3.5 ：一个分配规则 $\mathcal{A}$ 可以导出一个真实的拍卖机制，当且仅当对于所有的 $\boldsymbol{t}\in\mathcal{T}$，$i\in[n]$：
- （1）累积价值 $v_{i}\left((B,R),\boldsymbol{t}_{-i}\right)$ 在 $R=R_{i}$ 时关于 $B$ 是非递减的，并且在 $B=B_{i}$ 时关于 $R$ 是非递增的；
- （2）如果 $v_{i}\left((B_{i},R_{i}),\boldsymbol{t}_{-i}\right)>\lim_{B\to B_{i}^{-}}v_{i}\left((B,R_{i}),\boldsymbol{t}_{-i}\right)$，则
  $$
  v_{i}\left((B_{i},R_{i}),\boldsymbol{t}_{-i}\right)\geq B_{i}\times R_{i};
  $$
  - 理解：实际上应该是等于号吧？
- （3）如果 $v_{i}\left((B_{i},R_{i}),\boldsymbol{t}_{-i}\right)>\lim_{R\to R_{i}^{+}}v_{i}\left((B_{i},R),\boldsymbol{t}_{-i}\right)$，则
  $$
  v_{i}\left((B_{i},R_{i}),\boldsymbol{t}_{-i}\right)\leq B_{i}\times R_{i}.
  $$
- 定理3.5的证明 ：
  - 充分条件方向：可以通过应用定理3.3和3.4来验证
  - 必要条件方向：条件(1)直接来自定理3.3。为了证明条件(2)，如果 $v(B_{i},R_{i}) \lt B_{i}\times R_{i}$，则 $p(B_{i},R_{i})\leq \frac{v(B_{i},R_{i})}{R_{i}} \lt B_{i}$，这与定理3.3在 $B^{\prime}_{i}\to B^{-}_{i}$（表示某个 $B^{\prime}_{i} \lt B_{i}$ 无限接近 $B_{i}$）时矛盾。条件(3)的分析类似
    - 问题：如何理解条件(2)的证明？若 $v_{i}\left((B_{i},R_{i}),\boldsymbol{t}_{-i}\right) > v_{i}\left((B^-_i,R_{i}),\boldsymbol{t}_{-i}\right)$，则$p(B_{i},R_{i}) \gt B^-_i = B_i$，进一步有：$ v_{i}\left((B_{i},R_{i}),\boldsymbol{t}_{-i}\right) \geq p(B_{i},R_{i}) \times R_i \geq B_i \times R_i $

定理3.5完全描述了可行分配规则的条件。在本小节中，论文将进一步利用定理3.5所指示的可行分配规则的结构，为真实拍卖设计提供更多指导
根据定理3.5，累积价值 $v$ 与项 $B\times R$ 之间的关系严格描述了该类型是否与其邻近类型共享相同的累积价值，这使论文能够更清晰地表示 $v$ 的结构。固定预算，随着ROI的减少，分配给该类型的累积价值应增加，注意项 $B\times R$ 随着 $R$ 的减少而减少；然而，定理3.5中的条件（3）要求，如果在此过程中累积价值严格增加，则其值不应超过 $B\times R$ 。因此，必须存在某个阈值ROI，使得增加的累积价值与减少的 $B\times R$ 相交，并且累积价值不能再增加。基于上述观察，论文定义
$$\operatorname{thr}_{i}(B,\mathbf{t}_{-i})=\sup_{R\in\mathcal{R}_{i}}\left(v_{i} \left((B,R),\mathbf{t}_{-i}\right)\geq B\times R\right)$$
- 说明：这里 $\sup_{R\in\mathcal{R}_{i}}$ 表示 $\operatorname{thr}_{i}(B,\mathbf{t}_{-i})$ 是一个ROI值
- 如果所考虑的集合非空且有界，否则为 $0$ 。结果表明，分配给该阈值ROI的累积价值正好是 $B\times R$
定理 3.6 $\forall i\in[n]$ ， $\mathbf{t}_{-i}\in\mathcal{T}_{-i}$ ， $B_{i}\in\mathcal{B}_{i}$ ， $R_{i}\leq\operatorname{thr}_{i}(B_{i},\mathbf{t}_{-i})$ ：
$$v_{i}\left((B_{i},R_{i}),\mathbf{t}_{-i}\right)=\operatorname{thr}_{i}(B_{i},\mathbf{t }_{-i})B_{i}.$$
然后，我们可以将不同的预算组合在一起，以获得二维类型空间中可行分配的完整特征。由于所有高于阈值ROI的类型的累积价值 $v \lt B\times R$ ，根据thr函数的定义，它们无法满足定理3.5中的条件（2），因此被迫与具有较小预算的邻近类型共享相同的累积价值
定理 3.7 $\forall i\in[n]$ ， $\mathbf{t}_{-i}\in\mathcal{T}_{-i}$ ， $B_{i}\in\mathcal{B}_{i}\backslash{0}$ ， $R_{i}>\operatorname{thr}_{i}(B_{i},\mathbf{t}_{-i})$ ：
$$v_{i}((B_{i},R_{i}),\mathbf{t}_{-i})=\lim_{B\to B_{i}^{-}}v_{i}\left((B,R_{i}),\mathbf{t }_{-i}\right).$$
由于低于（定理3.6）和高于（定理3.7）ROI阈值的类型都已被完全描述，如果给定 $\operatorname{thr}_{i}(B_{i},\mathbf{t}_{-i})$ 并且 $\mathbf{t}_{-i}$ 固定，则整个类型空间上的累积价值可以完全定义。论文在图2中提供了一个示例来说明这些特征。对于低于阈值ROI曲线且具有相同预算 $B$ 的类型（即位于同一垂直线上的类型），它们共享相同的累积价值 $\operatorname{thr}_{i}(B)\times B$ 。对于曲线上的每个类型，其累积价值等于其具有较小预算的邻近类型的累积价值，直到达到其对应的ROI阈值上的某个类型。这相当于水平向左搜索以找到其对应的ROI阈值上最接近的类型，其中沿此水平搜索的所有类型共享相同的累积价值
论文已经证明，当其他竞拍者的概况固定时，每个可行的二维累积价值函数（其输入为 $(B,R)$ ）可以由一维阈值ROI函数（其输入为 $B$ ）表示，但尚不清楚哪些一维阈值ROI函数可以表示可行的累积价值函数。根据定理3.5中的条件（1），当 $R$ 无限接近于 $0$ 时，不同 $B$ 的累积价值应增加，这表明 $\operatorname{thr}_{i}(B,\mathbf{t}_{-i})\times B$ 需要在 $B$ 上是非递减的。由于每个从非递减的 $\operatorname{thr}_{i}(B,\mathbf{t}_{-i})\times B$ 映射的累积价值函数都满足定理3.5，这成为可行 $\operatorname{thr}_{i}$ 函数的唯一要求
推论 3.8 存在一个双射映射 $m:\mathcal{G}\rightarrow\mathcal{V}$ ，其中
$$
\begin{align}
(m\circ g)(B,R)=
\begin{cases}g(B) &\text{if }R\leq\frac{g(B)}{B},\\
g\left(\sup\limits_{B^{\prime}\leq B}\left\{R\leq\frac{g(B^{\prime})}{B^{ \prime}}\right\}\right) &\text{otherwise,}\end{cases}
\end{align}
$$
- 为了方便表示，论文记 $g_{i}(B_{i},\mathbf{t}_{-i})=\operatorname{thr}_{i}(B_{i},\mathbf{t}_{-i})\times B_{i}$ 。论文记 $\mathcal{V}$ 为当 $i$ 和 $\mathbf{t}_{-i}$ 固定时的可行累积价值函数空间，即 $v_{i}:T_{i}\rightarrow\mathbb{R}^{+}$ ，并记 $\mathcal{G}$ 为非递减函数 $g:\mathbb{R}^{+}\rightarrow\mathbb{R}^{+}$ 且 $g(0)=0$ 的空间
- 其中论文定义 $\sup\varnothing=0$
- 换句话说，给定任何一维非递减函数且 $g(0)=0$ ，我们可以通过上述映射过程将其转换为可行的累积价值函数

Truthful 拍卖设计

推导出的可行分配规则的结构引发了一种价值分组现象。从上述给定阈值ROI曲线找到某个类型的累积价值的过程来看，阈值ROI曲线上的每个类型与两组类型共享相同的累积价值：垂直位于其下方的类型，以及水平位于其右侧且高于其对应阈值ROI的类型，如图2所示。这种复杂的价值分组现象是由真实性条件而非优化要求强制执行的。正如论文在图2中所观察到的，由于水平搜索在遇到阈值ROI曲线上的类型时终止，分组形状由不同 $B_{i}$ 的 $thr_{i}(B_{i},\mathbf{t}_{-i})$ 的相对排名决定。然而，尽管 $thr_{i}(B_{i},\mathbf{t}_{-i})$ 需要保持 $g(B)$ 非递减，但它本身不需要单调，这导致水平搜索的终止和分组形状的不规则。这也使得难以推导出共享相同分配的类型的闭式条件。此外，尽管分组类型的累积价值被迫相同，但它们的支付是根据定理3.4计算的，导致分组类型之间的支付不同，并且收入相对于阈值ROI是非线性的
上述价值分组现象的特征，即分组形状的不规则性和支付的非线性，使得任何分析或数学规划方法都难以采用。为了实现可行且可实施的拍卖设计，论文提出了一类基于新设计的排名分数函数的简单真实拍卖
Truthful 拍卖算法：
- 对于每个 item ，竞拍者根据其虚拟出价 $b_{i,j}$ 进行排名，虚拟出价定义为 $v_{i,j}$ 乘以某个预定义的非递增函数 $f_{i,j}(R_{i})$ 的排名分数（第2行）
- 然后，item 暂时分配给每个具有最高虚拟出价的竞拍者（第3-6行）
- 在确定每个竞拍者 $i$ 的候选分配集 $A_{i}$ 后，论文计算竞拍者 $i$ 在 item $j\in A_{i}$ 中排名第一的相应ROI要求 $r_{i,j}$ ，即竞拍者 $i$ 需要报告 $R_{i}\leq r_{i,j}$ 以保持在 item $j$ 中排名第一（第8行）
  - 注意，这里使用逆运算和第二高价 $c_j$ 是为了按照二价计费的思想，计算刚好保证拿到第一位竞胜位置需要的ROI
- 第9行中的关键ROI是论文保证真实性的关键设计，它计算竞拍者可以报告的最大ROI以赢得 $A_{i}$ 中的足够 item 并花费其预算。直观地说，关键ROI模拟了竞拍者在其预算约束下的最佳响应ROI，这不涉及并因此独立于其真实的ROI约束。论文自然地利用这个关键ROI，它将预算转换为与ROI相同的维度，作为阈值ROI函数，并根据第3节中的真实性条件设计其余部分
  - 关键ROI的理解：关键ROI是一个针对预算的虚拟的ROI，即赢得足够多的物品以消耗完预算的最大ROI ，每个用户 $i$ 都有一个关键ROI $R_i^c$ ，如果用户按照关键ROI去作为阈值，则对于竞胜所需 $r_{i,j} \geq R_i^c$ 的 item $j$ 都会被分配给用户 $i$。对于用户 $i$，要求所有被分配的 item 都按照其价值和关键ROI来售卖 $p_{i,j} = \frac{v_{i,j}}{R_i^c}$。最终挑选的关键ROI $R_i^c$ 是且使得用户总支出收入刚好大于用户设置的预算 $B_i$ 的最大关键ROI（注意：相同预算下，关键ROI越大，能分配到的 item 就越少 ，所以其他条件不变情况下，预算越小，分配到的 item 越多，关键ROI就越大）
- 第10-11行旨在保证 $A_{i}$ 中剩余 item 的价值正好等于竞拍者的预算乘以计算的关键ROI（定理3.6）
  - 问题：$d$ 是左边减去右边的差值吗？【是的】
  - 问题：如何理解移除竞胜ROI与关键ROI相等的 item ？【是因为这样可以精准的使得左右两边相等，即剩余 item 的价值正好等于竞拍者的预算乘以计算的关键ROI】
  - 问题：清除的 item 卖给谁呢？
- 第12-13行旨在保证ROI大于相应关键ROI的类型将根据其报告的ROI进行分配（定理3.7）并获得所有 $r_{i,j}\geq R_{i}$ 的 item
  - 如果商家设置的ROI小于关键ROI，则说明预算对应的虚拟ROI大于商家ROI，也就是预算时紧约束，需要将小于关键ROI的部分 item 清除出去
  - 问题：清除的 item 卖给谁呢？
- 第14行根据定理3.4确定每个竞拍者的支付。由于其低时间复杂度，算法1具有良好的实现可扩展性
定理 4.1 如果预定义的函数 $f_{i,j}(R)$ 在 $R$ 上是非递增的，则算法1对应的拍卖机制是真实的
- 论文的证明通过找出并验证算法1的相应 $g(B)$ 和阈值ROI函数来进行。我们可以根据拍卖目标和广告活动前的先验知识（如竞拍者的类型分布和即将到来的 item 的信息）为竞拍者和 item 设计个性化的 $f_{i,j}(R)$

Experiments

在本节中，论文使用合成数据进行了实验，以验证论文提出的拍卖机制的性能。（注意：没有真实上线验证）

Experiment Setup

论文进行了两组实验，分别针对独立同分布（i.i.d.）和非独立同分布（non-i.i.d.）的竞拍者。论文通过改变竞拍者和 item 的数量来模拟需求和供应的变化。所呈现的结果是50次运行的平均值。论文根据广告市场中的常见波动选择分布参数，并对 $v_{i,j}$ 的下界进行归一化
- 对称竞拍者 竞拍者是对称的， $v_{i,j}\sim U[1,4]$ ， $B_{i}\sim U[40,80]$ ， $R_{i}\sim U[1,3]$ ，其中 $U[a,b]$ 表示范围 $[a,b]$ 内的均匀分布
- 混合竞拍者 对于 $v_{i,j}$ 、 $B_{i}$ 和 $R_{i}$ ，存在低分布和高分布作为竞拍者的可能类型。具体来说， $v_{i,j}\sim U[1,2]$ 或 $v_{i,j}\sim U[2,3]$ ， $B_{i}\sim U[20,40]$ 或 $B_{i}\sim U[80,100]$ ， $R_{i}\sim U[1,2]$ 或 $R_{i}\sim U[2,3]$ 。这些类别的组合形成了8组竞拍者
基线拍卖 由于现有的机制无法保证预算和ROI的激励相容性（IC）属性，论文考虑了常见的重复拍卖形式：第一价格拍卖和第二价格拍卖。由于它们的非真实性（见论文的完整版本），论文在这些拍卖中引入了虚假报告
- 重复第一价格和第二价格拍卖 ：拍卖者为每个 item 举行第一价格（第二价格）拍卖，竞拍者 $i$ 对 item $j$ 出价 $\frac{v_{i,j}}{R_{i}}$ 。拍卖者将 item 分配给排名最高且有剩余预算支付的竞拍者，并收取第一价格（第二价格）支付。论文通过经典的最佳响应动态模拟竞拍者的虚假报告行为，以真实概况为起点。在重复第一价格（第二价格）拍卖中，竞拍者没有动机虚假报告其预算。论文计算最佳响应ROI为在历史拍卖中实现最高效用的最小ROI
- 非真实最优基线 ：通过线性规划可以计算出最优离线收入，其中论文将每个竞拍者 $i$ 对 item $j$ 的支付设置为 $\frac{v_{i,j}\times a_{i,j}}{R_{i}}$ ，并且其总支付不超过 $B_{i}$
评估指标 论文考虑收入和社会福利作为优化目标。由于定理3.4中的支付公式（Eq.2）与方程（Eq.1）中社会福利的定义一致，当没有竞拍者获得负无穷效用时，收入和社会福利的指标将相同，因此论文将在结果中仅报告收入。此外，由于广告主在不同时间段内的拍卖表现可能波动，公平性也应被考虑，以保持竞拍者参与拍卖的意愿。使用社会福利替代传统的估值函数，公平性定义为
$$\text{fairness}=\min_{i\in[n]}\min\left(\frac{v_{i}(\boldsymbol{t}^{\prime})}{R_{i}},B_{i}\right).$$
排名分数函数 论文采用形式为 $f_{i,j}(R)=\alpha_{i,j}\times e^{-\beta R}$ 的排名分数，其中 $\alpha_{i,j}$ 从修正的正态分布 $N(\mu_{i},\sigma_{i}^{2})$ 中抽取， $\beta,\mu_{i},\sigma_{i}$ 是预设参数。在 $f(R)$ 中， $\beta$ 用于调整ROI对等效出价的影响， $\alpha$ 保持不同竞拍者的排名分数在可比范围内。由于当某些竞拍者赢得过多 item 时， item 可能会被丢弃（算法1中的第13行），为了避免社会福利和收入的损失，论文应在供应充足时为其他竞拍者提供非平凡的获胜机会，这是通过 $\alpha\sim N(\mu_{i},\sigma_{i}^{2})$ 中的随机性提供的。对于每个自动出价环境，论文为遵循相同分布的竞拍者设置相同的排名分数函数参数，并选择在该环境中收入较好的参数

实验结果

实验结果如下：
对称竞拍者 ：Figure 3(a)报告了论文的真实拍卖（称为DSIC）和基线拍卖在不同竞拍者数量下的收入，Figure 3(b)报告了 item 数量变化时的收入。论文的真实拍卖比第一价格和第二价格拍卖实现了更好的收入，并且通常实现了接近最优基线90%以上的收入。值得注意的是，当 item 过多时，第一价格拍卖的收入明显下降，这也导致了公平性的下降（Figure 3(c)）。这是因为竞拍者在面对一些低价未售出的 item 时过度增加了其报告的ROI，导致所有支付按比例减少。在Figure 3(c)中，论文报告了在固定40个竞拍者的情况下，不同 item 数量下的公平性结果，如Figure 3(b)所示。正如排名分数函数中所设计的，论文的拍卖不会将过多的 item 分配给某个竞拍者，以避免 item 浪费，因此在 item 数量在600到1200之间时，比最优基线实现了更好的公平性。当 item 短缺时（Figure 3(c)中的200/400个 item ），论文的真实拍卖由于追求收入而在一定程度上损害了公平性。我们可以通过不同的排名分数函数参数 $\beta$ 来控制公平性和收入之间的权衡。Figure 3(d)报告了在400个 item 的情况下，不同 $\beta$ 的一组收入和社会福利表现。为了实现更高的收入，不可避免地会在不同竞拍者之间进行歧视性分配，并在 item 不充足时损害公平性
混合竞拍者 ：论文展示了在非独立同分布设置中选择适当排名分数函数的重要性。论文选择了三组排名分数函数，分别在三种典型设置中表现良好：40个混合竞拍者，200/1000/1600个 item ，并在其他两种设置中测试它们的表现。结果如图4所示，其中DSIC- $n$ 表示在设置 $n$ 中表现良好的真实拍卖。DSIC-n机制仅在设置 $n$ 中表现良好，原因应来自于实现高收入所需的不同分配方法。例如，为了在 item 短缺时实现高收入（设置1），DSIC-1拍卖将大多数 item 分配给具有高价值和低ROI的竞拍者，导致在设置2和3中将这些竞拍者分配过多的 item 而忽略其他竞拍者

附录：思考

智能出价中保成本技术是否还需要？
- 答案是不需要。当前这种拍卖方式下，并不需要使用控制算法去保成本，假定预估值足够准确的情况下，按照 $v_{i,j} \times f_{i,j}(R_i)$ 反算对应位置上的出价即可，这里常见是使用 $v_{i,j} \times \frac{1}{R_i}$ 作为出价公式
是否有部分 item 无法卖出去？
- 目前看是的，特别是当广告主的 ROI和关键ROI（即预算）之间差异较大时

CA——拍卖机制设计概述

注：论文主要参考自万字长文，漫谈广告技术中的拍卖机制设计（经典篇）等资料，有一些自己的思考

参考链接：
- 万字长文，漫谈广告技术中的拍卖机制设计（经典篇）

名词解释

竞拍者 ：需求方，在广告系统中就是广告主
机制拍卖中的一般假设 ：一般假设竞拍者是理性的，即满足个体理性（收益非负），且有能力通过调整自己的策略来获得更高的收益，
私有信息（Private Value） ：也称为私有估值 ，竞拍者对物品、广告位的估值一般是私有信息，一些论文也称为Type类型 ，该信息是外部不可知的
- 一些机制设计的目标就是诱导竞拍者在博弈中真实表达自己的私有信息（所以要设计他们说真话是他们的最优策略的机制）
拍卖机制 ：包含分配规则（Allocation Rule）和计费规则（Payment Rule）两个部分
效用（Utility） ：一般是价值减去支出即效用函数 = 广告主获得的价值 - 广告主的支付价格，即 $u = v - p$
广告主偏好 ：通常包含效用最大化（Utility Maximizer）和价值最大化（Value Maximizer）两种类型
社会福利（Social Welfare） ：指的是整体广告主的价值和，单个广告主对单个广告位置的价值 = 广告主获得广告位的概率 * 广告位对广告主的价值
- $n$ 个竞拍者的社会福利可表示为 $SW = \sum_{i=1}^n v_i x_i$，其中 $x_i$ 是竞拍者 $i$ 获得物品的分配概率，$v_i$ 是竞拍者 $i$ 对该物品的估值
- 社会福利的另一个视角：广告主效用为0时（即商家说真话且按照一价计费时），社会福利等于买家从广告主手里获得的收入 ，所以社会福利也可以表达为在满足 IR 的情况下，社会福利等于买家可以从广告主手里获得的最大收入
流动性福利（Liquid welfare）【未找到精确定义，待补充】 ：流动性福利是指存在预算约束情况下的社会福利（目前看到的都是预算约束下的流动性社会福利定义），表示在不违反财务约束的情况下可以从竞拍者中提取的最大收入 ，Auto-bidding and Auctions in Online Advertising: A Survey, 202408, Google 中有相关的定义（Truthful Auctions for Automated Bidding in Online Advertising, IJCAI 2023, Alibaba 中有ROI约束+预算约束下的定义）
- $n$ 个竞拍者的流动性福利可表示为$\text{LW}=\sum_{i\in[n],u_{i}(t_{i},\mathbf{t}^{\prime})\geq 0}\min\left(\frac{v_{i }(\mathbf{t}^{\prime})}{R_{i}},B_{i}\right)$，其中 $R_i,B_i,v_i(\mathbf{t}^{\prime})$ 分别表示广告主设置的ROI，预算和广告主的累计价值 ，关于社会福利和流动性福利的更多讨论见附录
有效机制（efficient mechanism） ：社会福利最大化的机制是对资源最有效率的配置方式，所以该类型的机制也叫有效机制
最优机制（optimal mechanism） ：平台收入最大化的机制称为最优机制
拍卖机制的目标 ：使得广告主竞价博弈收敛结果符合平台预期（平台预期包括平台收益、社会福利等）
- 常见的目标包括社会福利最大化和平台营收最大化
激励相容（Incentive Compatibility） ：鼓励竞拍者讲真话
优势策略激励相容（Dominant-Strategy Incentive Compatibility，简称DSIC） ：不管其他智能体如何报告自己的私有信息，如实报告（即讲真话）都是每个广告主的最优决策，即说真话时广告主效用最大化（效用最大化类型的用户）；
贝叶斯纳什激励相容（Bayes-Nash Incentive Compatibility，简称BIC） ：如果其他广告主是如实报告自己的私有信息的，那么广告主最优反应也是如实报告
完全信息设定 ：参与者知道其他参与方的真实类型
不完全信息设定 ：参与者只知道其他参与方的类型分布（而不是真实类型）
博弈均衡 ：博弈均衡是博弈论中的一个核心概念，它描述了在给定的博弈规则下 ，参与者选择某种策略后所达到的一种均衡状态（稳定状态）。在这种状态下 ，每个参与者都无法通过单方面改变自己的策略来获得更好的结果。换句话说，博弈均衡是一种策略组合 ，使得任何一个参与者都没有动机去单方面改变自己的策略
- 纳什均衡 Nash Equilibrium（NE） ：在完全信息设定下的，一种在给定其他参与者策略时，任何单个参与者都没有动机去改变自己的策略的均衡状态
  - 囚徒困境是一个典型的纳什均衡，两者都选择说真话就是囚徒困境的纳什均衡状态
- 贝叶斯纳什均衡 Bayesian Nash Equilibrium（BNE） ：一种在不完全信息设定下得，一种在给定其他参与者策略和类型分布（注意：只知道类型分布，不知道真实类型）时，没有参与者有动机单独改变其策略的均衡状态
  - 贝叶斯纳什均衡可以看做是对纳什均衡的一个扩展，用于处理不完全信息的情况
- 优势策略均衡 Dominant Strategy Equilibrium（DSE） ：一种在完全信息或不完全信息设定下得，无论其他参与者选择什么策略 ，每个参与者策略总有自己的最优策略的均衡状态
  - 如果存在优势策略均衡，则它一定是唯一的纳什均衡 ，因为每个参与者都有明确的最佳行动，不受其他参与者行为的影响
  - 优势策略均衡一定是一个纳什均衡
- 注：一个好的机制下，博弈结果可以有一个均衡 ，也可以有多个均衡 ，但不能是非均衡的
直接显示机制（direct-revelation mechanism） ：要求参与者直接如实报告自己的私有信息（例如在拍卖中直接出价，而非通过复杂的行为间接传递信息）
- 直接显示机制不一定满足 DSIC ：实际上，参与者会报告一个自己的类型空间中的值（不一定是真实的），即
- 直接显示机制不一定存在均衡状态 ：可能竞拍者会来回调整他的报价，尝试拿到更优的收益
- 注意：在一些书籍或博客中，会表达直接显示机制要求竞拍者如实报价 ，这会让人误以为直接显示机制都是 DSIC 的，我的理解是这并不代表机制是 DSIC 的，要求只是表达一个期望，要求了竞价者也不一定会如实上报
可实施的分配规则 ：对于一个分配规则x ，如果存在一个扣费规则p ，使得直接显示机制 (x, p) 是满足 DISC 性质的，那么就称这个分配规则x是可实施的；

理想的拍卖机制是怎样的？

高效率保证 ：多项式时间（一般近似线性）内完成分配和扣费两个计算过程
- 为了可以应用，这个规则一般不可以做松弛
高效果保证 ：存在均衡 ，且均衡结果满足引导预期 ，社会福利最大化或平台营收最大化；
- 为了保证高效率保证 ，这个要求可以被松弛，主要是涉及到分配规则
  
  from 万字长文，漫谈广告技术中的拍卖机制设计（经典篇）
  因为最优分配问题本质是一个背包问题，而背包问题是NP困难问题，分配规则不可能在多项式时间内被实现，所以往往采用启发式的贪心算法，也就是业界常用的排序策略。这样分配问题就转化为了排序问题，例如论文开头Rankscore计算公式的设计，可以获得高效率的近似最优解
高动机保证 ：优势策略激励相容（DSIC） ，即如实报价是参与者的优势策略（注意此时均衡不仅存在，而且是以最严格的优势策略均衡（DSE）的形式存在）；
- 为了保证高效率保证 ，这个要求也可以被松弛，主要涉及到扣费规则
  from 万字长文，漫谈广告技术中的拍卖机制设计（经典篇）
  - Myerson引理证明当分配规则确定 ，扣费规则就是唯一的、且有明确的表达式 ，假设该表达式是a。可是实际环境非常复杂，或因为计算效率问题，或因为业务约束问题，导致实际采用的扣费规则没有用a，却用了b，那么DSIC就会被破坏
  - 但是非DSIC机制就一定很糟糕吗？答案非也。前文提到，优势策略均衡是最理想的均衡结果 ，机制设计的底限是要有均衡的预期 ，有均衡预期就有足够假设来预测智能体的行为，那么机制结果就能有效推演。所以非DSIC机制也可以有不错的均衡性质 ，它们在实际中很常见
  - 例如广告拍卖机制中，假设广告主偏好模式是Utility Maximizer ，平台优化目标是社会福利最大化 ，那么只有VCG机制满足 DSIC ，GSP机制不满足 DSIC ，但是也不妨碍GSP机制盛行，详细内容下文会重点介绍
个人理解：
- 拍卖机制能最大化社会福利的前提是竞拍者真实报告自己的类型，否则无法实现，故而要尽量保证 DSIC 才能尽量做到社会福利最大化

Myerson 引理

分配规则 ：一个分配规则是可实施 ，当且仅当它是单调的；
扣费规则 ：如果分配规则是单调的，那么存在唯一的扣费规则 ，使得直接显示机制是 DSIC 的，且这个扣费规则有明确的表达式

拍卖形式的分类

单物品拍卖和多物品拍卖 ：按拍卖品数量划分，有些文章也称为单位置拍卖和多位置拍卖
单参数拍卖和多参数拍卖 ：按照竞拍者报价数量划分，注意是一次拍卖中，上报多个估值还是上报一个估值划分
单轮拍卖和多轮拍卖 ：按照竞拍论述划分

from 万字长文，漫谈广告技术中的拍卖机制设计（经典篇）
轮数越多，竞拍者的私有信息Type会越来越成为公有信息，使得竞拍者能有更多的信息做决策从而调整报价策略。虽然多轮拍卖更加契合实际广告拍卖场景，广告主一笔预算往往会参与很多轮的请求报价，但是多轮的机制设计比单轮复杂很多，一般简化为单轮拍卖形式进行分析讨论
无约束拍卖和有约束拍卖 ：按照竞拍者目标是否带着约束划分

from 万字长文，漫谈广告技术中的拍卖机制设计（经典篇）
有约束是指在广告主追求营销目标最大化的同时会带有指标约束，例如预算约束或者ROI约束等，这样广告主报价策略会从短期收益最大化调整为长期收益最大化，这对机制性质也会带来不小挑战
注意：一般的广告拍卖场景中（包括万字长文，漫谈广告技术中的拍卖机制设计（经典篇）），一般都将广告的经典机制设计范畴规约在“异质多物品、单参数、单轮和无约束”拍卖形式下（简称多物品拍卖）

社会福利最大化的拍卖机制

社会福利最大化的机制是对资源最有效率的配置方式，所以该类型的机制也叫有效机制（efficient mechanism）

SW最大化-单物品拍卖的有效机制

二价计费（Second-price auction，简称SP）机制，也叫 Vickrey auction，是社会福利最大化的 DSIC 机制

SW最大化-多物品拍卖下VCG和GSP机制比较

VCG机制

多物品拍卖下，若想要实现社会福利最大化 ，分配规则应该按照报价从高到低排序，第 $i$ 高报价的竞拍者获得第 $i$ 好的物品，此时，通过Myerson引理可以证明，满足DSIC的唯一支付公式是VCG扣费方式：
$$ p_i = \sum_{j=i}^k b_{j+1} \frac{\alpha_j - \alpha_{j+1}}{\alpha_i} $$
- 付费是该竞拍者赢得广告位后，给其他广告主带来的收益损失是该竞拍者需要支付的费用；直观理解为：从自己获得的这一物品起，后续所有物品上对其他人造成的损失和（因为后面每个竞拍者都因为竞拍者 $i$ 的存在而后移一位，所以可以如上式表示社会福利），一般的论文中，也常常也表示为：
  $$ p_i = SW_{-i} - (SW - v_i x_i) $$
  - $SW_{-i}$ 是竞拍者 $i$ 不参与竞拍时的其他人获得的总社会福利
  - $SW - v_i x_i$ 是竞拍者 $i$ 参与竞拍时的其他人获得的总社会福利 ， $SW$ 则表示包括竞拍者 $i$ 在内的总体社会福利
多物品拍卖下的Vickrey–Clarke–Groves auction（简称VCG机制）是单物品拍卖下的Vickrey auction（也称SP机制）有效升级，下图准确表示了 VCG 机制是满足 DSIC 的：
- $z$ 表示估值分布，$v$ 表示真实估值，$b$ 表示报价；$x(z)$ 表示分配结果（对应为点击率），$p(v)$ 或 $p(b)$ 表示计费结果
- 三列分别为出真实价值 $b = v$，出高价 $b > v$ 和出低价 $b < v$ 的情况
- 第一行表示不同出价 $b$ 下获得的价值，第二行表示支付金额，第三行表示效用(Utility) = 价值 - 支付，即 $u = v\cdot x(b) - p(b)$
- 阶梯函数是因为在不同的位置，点击率不同，但同一个位置，随着出价变化，点击率是相同的
- 图中绿色部分就是收益部分（注：第三行第二列中绿色区间还要减去阴影部分才可以），显然说真话是效用是最大的
多物品拍卖下，若目标是社会福利最大化 ，则VCG机制是满足 DSIC 机制的唯一机制
- 单物品拍卖下，若目标是社会福利最大化 ，SP机制是满足 DSIC 机制的唯一机制
- 单物品拍卖下，若目标是平台收入最大化 ，Myerson拍卖机制是满足 DSIC 机制的机制（并非唯一？）
VCG机制的缺点 ：
- 计算复杂 ：运行效率低下，运算复杂（比如一些场景中需要做listwise的CTR预估）
- 平台收入低 ：平台收入较低（比GSP等都低，可以认为是常见的收入最低的拍卖形式，唯一的优点是满足 DSIC）
- 解释成本高 ：给广告主解释困难

GSP机制

GSP机制（Generalized second-price auction）分配规则和VCG一样，按照下一位出价计费：
$$ p_i = b_{i+1} $$
类似上面 VCG 机制的分析图，下图展示了 GSP 机制的分析情况：
- 可以看到，报高价没有正向收益（第三行第二列），但是报低价有可能获得更高的效用（第三行第三列和第三行第一列的绿色区域孰高孰低不一定）
广告主是效用最大化类型时，GSP虽然不是 DSIC 的，但是其有不错的均衡性质（机制要求均衡且均衡状态满足机制目标即可，不一定要 DSIC ，DSIC 是个非常强的性质），GSP包含两个视角的均衡 ：
- Pure Nash Equilibrium under Full-Information Setting ：完全信息设定下的纳什均衡？
- Bayesian Nash Equilibrium under Partial-Information Setting ：不完全信息设定下的贝叶斯纳什均衡？
  
  from 万字长文，漫谈广告技术中的拍卖机制设计（经典篇）
  以前者（理解：这里指Pure Nash Equilibrium under Full-Information Setting）为例，假设多轮竞价交互之后广告主的估值成为公有信息，GSP机制达到的一种均衡结果是广告主会认为保留当前位置是最优策略，不愿意与比他顺位高的人换位置，不然利润受损，这种均衡叫 locally envy-free equilibrium（也称symmetric Nash equilibrium），对应广告主的报价策略不再是如实报价，详细可见文献
GSP优点缺点总结 ：
- 计算简单 ：仅需一个简单公式，容易落地
- 平台收入高 ：收入更高，对照VCG和GSP的分析图中第二行可得
- 容易解释 ：按照下一位出价计费，简单易懂
- DSIC讨论 ：在广告主是效用最大化类型时，GSP不是 DSIC的（有文献提到，在广告主是Value最大化类型时，GSP机制是 DSIC 的）
- 均衡性讨论 ：GSP存在多个均衡，GSP的其中一个均衡结果和VCG等价（注：此时因为扣费大于VCG，所以平台营收会比VCG更高）
  - 问题：这里的与VCG等价是说，在这个均衡状态下，大家都会说真话吗？存在部分竞拍者会试探低价吧？

SW最大化-GSP机制关于点击率的升级

下面的内容主要考虑关于点击广告（按点击售卖的广告）场景，目标还是如何优化社会福利，更好的实现社会福利最大化，提高资源分配效率

GSP

普通的GSP认为点击率只与广告位置有关，与广告主无关，未考虑不同竞拍者（广告实体）的点击率在同一个位置会不同
下文中也称广告自身的点击率为广告质量分

wGSP

wGSP（weighted GSP）引入一个与竞拍者 $i$ 相关的点击率 $\beta_i$（也称为广告质量分）
- 注：wGSP并没有假设广告在不同位置会有不同的广告质量分（理解：这里的质量分是与广告位置无关的，用户和广告之间的匹配分数）
此时社会福利是（$n$ 个广告主， $k$ 个资源位）：
$$ SW = \sum_{i=1}^n \sum_{j=1}^k v_i \beta_i \alpha_j $$
广告主的效用是：$u_i = \beta_i \alpha_j(v_i - p_i)$，注：效用也是效用最大化类型广告主的优化目标
wGSP分配规则 ：按照 $\beta b $ 排序
wGSP计费规则为：
$$ p_i = \frac{\beta_{i+1} b_{i+1}}{\beta_i} $$

iGSP

wGSP没有考虑广告在不同位置会有不同的广告质量分（点击率），实际上，不同位置上、同一位置不同上下文情况下广告的点击率均会有不同
iGSP（iterated GSP）考虑了广告在不同位置会有不同的广告点击率，但仅仅可以在做到2个资源位同时拍卖的情况下，最大限度保证 existence of efficient equilibria ，3个资源位的情况还没解决
- 问题：如何理解最大限度保证 existence of efficient equilibria？
iGSP分配规则 ：逐个位置拍卖，逐个位置预估考虑到上下文、位置因素下的每个广告主的点击率 $\gamma_{ij}$，然后按照价高者得
iGSP计费规则 ：每次拍卖时，对当前拍卖位置的首位广告主（当前位置竞胜者）进行二价计费：
$$p_{1j} = \frac{\gamma_{2j}b_2}{\gamma_{1j}}$$
竞胜后的广告主不参与下一轮位置竞争，遍历拍卖至资源分配完
iGSP的总结：相对于wGSP，拍卖流程更复杂，但因为考虑到广告在不同位置下的质量分，会使得社会福利更优（资源配置效率更高）

平台收入最大化的拍卖机制

满足 DSIC 性质，且使得平台收入最大化（Revenue最大化，简称Rev最大化）的机制称为 最优机制（optimal mechanism）

Rev最大化-VCG与GSP的平台收入比较

GSP的收入更高，对平台来说，GSP机制更受欢迎
GSP机制不再是 DSIC 的（从前文看，广告主有隐瞒估值，刻意报低价的动机），但GSP机制有均衡性质（注意：均衡结果是最起码的要求，否则从长期博弈结果来看短期的平台营收都不可持续）

from 万字长文，漫谈广告技术中的拍卖机制设计（经典篇）
换个角度解释这个现象，GSP机制不是DSIC的，广告主有隐瞒估值低报价的动机，所以长期来看会随着广告主低报价整体社会福利不如VCG，使得虽然在分蛋糕方面GSP有优势但在做大蛋糕方面存在不利因素，此消彼长，长期看平台营收GSP一定会打折扣。GSP有不错的均衡性质尚且如此，更何况其他粗暴魔改扣费规则的机制了，所以事情看来没有那么简单

Rev最大化-单物品拍卖的最优机制

SP机制：Second Price，二价计费
SP+保留价机制：二价计费，同时带有保留价，当低于保留价时，不售卖，高于保留价时，保留价参与二价计算（即广告主计费不会低于保留价）
Myerson机制：可以获得最大化期望收益的最优机制
- 注：在竞拍者私有估值服从独立同步分布时，Myerson拍卖机制等价于SP+保留价 $\varphi_i^{-1}(0)$ 机制
其他补充：

from 万字长文，漫谈广告技术中的拍卖机制设计（经典篇）
首先定义虚拟估值 $\varphi_i(v_i) = v_i - \frac{1-F_i(v_i)}{f_i(v_i)}$，它和私有估值 $v_i$ 以及分布 $F$ 有关；然后可以论证在满足DSIC的机制空间上对期望收益最大化 ，可以等同于在同一个空间对期望虚拟福利最大化 ，这样原本关心的收益最大化问题就转变为了分配最优化问题， $Rev = \max\sum_{i=1}^n \varphi_i(v_i) x_i$，与前文章节中 $SW = \max\sum_{i=1}^n v_i x_i$ 相比仅仅是将私有估值 $v_i$ 转换为对应的虚拟估值 $\varphi_i(v_i)$，其他分配规则的细节以及扣费规则都与社会福利最大化一模一样；最后只需要保证 $\varphi_i(v_i)$ 是单调的，即私有估值的分布 $F_i(v_i)$ 是正则分布 ，许多常见分布基本都是正则分布，例如normal、lognormal、uniform and exponential distributions等；非正则分布包括多峰分布和长尾分布，分配的单调性是机制DSIC性质的前提。论证过程可详见文献
可以发现虚拟估值 $\varphi_i(v_i)$ 可能为负，在分配的过程中如果遇到 $\varphi_i(v_i) < 0$ 的竞拍者会被剥夺竞拍资格，如果所有竞拍者的虚拟估值均为负，则流拍，所以 $\varphi_i^{-1}(0)$ 即虚拟估值为0的逆函数起到了个性化保留价的功能。如果假设所有竞拍者的私有估值服从独立但不同分布，则不仅会有各自不同的保留价，还会遇到如实报价情况下报价高，但虚拟估值不一定高，导致没有竞得更好的资源位，也好理解，此时虚拟估值代表了个性化自己和自己对比的报价意愿强烈程度；如果假设所有竞拍者的私有估值服从独立同分布，因为估值分布相同则虚拟估值函数 $\varphi$ 也相同，又因为估值分布 $F$ 服从正则分布，则 $\varphi$ 严格递增，那么虚拟估值最高的竞拍者就是私有估值最高的竞拍者，这样虚拟福利最大化机制就和带有保留价 $\varphi_i^{-1}(0)$ 的二价机制相同，回答上文提到的两个竞拍者估值服从独立同分布 $[0,1]$ 均匀分布的例子，$\varphi_i^{-1}(0)=\frac{1}{2}$ S确实是最优保留价。以下是单物品拍卖的几个机制对比：

Rev最大化-多物品拍卖下GSP的改造

Myerson拍卖无法应对多物品拍卖位置，实际上，自1981年Myerson拍卖问世以来，至今没有找到多物品拍卖设定下的最优拍卖机制，多物品拍卖设定下的最优拍卖机制（满足 DSIC 的收益最大化拍卖）设计是一个开放性问题
在多物品拍卖场景，广告多坑位拍卖一般围绕改造 GSP 机制来近似实现最优结果，具体来说，是将Myerson机制和GSP机制结合起来

mGSP

mGSP（myerson GSP）机制，将Myerson保留价技术直接应用到wGSP机制上

from 万字长文，漫谈广告技术中的拍卖机制设计（经典篇）
和单物品拍卖的设计思路类似，Myerson保留价最核心的虚拟估值依赖广告主的私有估值分布，系统可以酌情根据独立同分布的颗粒度进行假设的调整，例如客户之间完全独立不同分布、相同搜索词的客户之间独立同分布、整体流量客户独立同分布等。因为广告系统是多轮拍卖系统，假设广告主是如实报价，则私有估值分布可以根据广告主历史报价进行不同粒度的分布拟合，从而得到虚拟估值。有了虚拟估值和保留价，在分配规则方面有两种类型可做尝试：Eager模式，先过滤后排序，即先根据保留价过滤没有竞争力的广告主，再按照虚拟估值排序；Lazy模式，先排序后过滤。Eager模式对最高报价无法胜出保留价的情形更友好，Lazy模式对第2高报价无法胜出保留价的情形更友好，多数情况下Eager模式在提营收方面会比Lazy更有优势

aGSP

aGSP（anchoring GSP）机制，是对mGSP机制一种松弛方式

from 万字长文，漫谈广告技术中的拍卖机制设计（经典篇）
第二种是aGSP（anchoring GSP）机制，是对mGSP机制一种松弛方式，业务落地过程中虚拟估值的求逆计算和私有估值的正则分布要求等均会让机制实现不够简洁且解释性较差，略牺牲效果的情况下精简机制设计也是可接受的迭代方向。首先保留价的计算方法和mGSP机制相同，一般保留价的颗粒度会选择数据积累较为充分的粒度。其次主要差异点就是将虚拟估值由 $\varphi_i(v_i) = v_i - \frac{1-F_i(v_i)}{f_i(v_i)}$ 简化为 $\varphi_i(v_i) = v_i - r_i$，如果假设私有估值分布是均匀分布，化简的表达式就非常接近，求逆也方便，而且业务含义与myerson思路很吻合，报价竞争力更多看重每个广告主超出个性化保留价的那部分

rGSP

rGSP（reserve GSP）机制，是对aGSP机制更加进一步的松弛

from 万字长文，漫谈广告技术中的拍卖机制设计（经典篇）
因为有文献提出，为了解决私有估值和虚拟估值趋势不一致问题，虚拟估值可以仅用于个性化保留价的过滤，分配和扣费依然按照私有估值进行，这样虽然对营收有折损但是机制实现更加简洁且易解释

一些讨论

机制设计应该关注用户体验 ：相对免费资源位置，付费资源位置本质是在牺牲用户体验，换取社会福利和平台收入，机制设计时还需要考虑用户体验，否则如果用户失去对付费资源的关注度，则平台将彻底失去流量变现机会
未来方向：
- 广告主偏好：论文主要是以效用Utility最大化为目标，后续可考虑以价值Value最大化为目标的情况
- 结合自动出价（Auto-Bidding）：自动出价的场景越来越多，但相关的机制研究较少
- 基于学习的机制（数据驱动）
- 生成式拍卖

附录：社会福利和流动性福利的讨论

社会福利（Social Welfare） ：指的是整体广告主的价值和，单个广告主对单个广告位置的价值 = 广告主获得广告位的概率 * 广告位对广告主的价值
- $n$ 个竞拍者的社会福利可表示为
  $$SW = \sum_{i=1}^n v_i x_i$$
  - 其中 $x_i$ 是竞拍者 $i$ 获得物品的分配概率，$v_i$ 是竞拍者 $i$ 对该物品的估值
- 社会福利的另一个视角：广告主效用为0时（即商家说真话且按照一价计费时），社会福利等于买家从广告主手里获得的收入 ，所以社会福利也可以表达为在满足 IR 的情况下，社会福利等于买家可以从广告主手里获得的最大收入
  - 对最大的理解 ：这里最大是指刚好满足 IR，即商家效用为0时的值，是社会福利定义里面针对约束而言的“最大”，拍卖机制中常说的社会福利最大化的“最大”是分配效率
  - 机制拍卖的目标 ：这个视角同时暗示了，平台收入小于等于社会福利 ，平时我们拍卖机制设计中，最大化社会，一方面在提升资源分配率 ，另一方面也等价于是在提升平台收入空间（因为在IR约束下，平台收入不会超过社会福利）
流动性福利（Liquid welfare）【未找到精确定义，待补充】 ：流动性福利是指存在预算约束情况下的社会福利（目前看到的都是预算约束下的流动性社会福利定义），表示在不违反财务约束的情况下可以从竞拍者中提取的最大收入 ，Auto-bidding and Auctions in Online Advertising: A Survey, 202408, Google 中有相关的定义（Truthful Auctions for Automated Bidding in Online Advertising, IJCAI 2023, Alibaba 中有ROI约束+预算约束下的定义）
- $n$ 个竞拍者的流动性福利可表示为
  $$\text{LW}=\sum_{i\in[n],u_{i}(t_{i},\mathbf{t}^{\prime})\geq 0}\min\left(\color{red}{\frac{v_{i }(\mathbf{t}^{\prime})}{R_{i}}},B_{i}\right)$$
  - 其中 $R_i,B_i,v_i(\mathbf{t}^{\prime})$ 分别表示广告主设置的ROI，预算和广告主的累计价值
  - 注意，其实 $\color{red}{\frac{v_{i }(\mathbf{t}^{\prime})}{R_{i}}}$ 就是ROI出价下的社会福利，为了方便理解，可以推导出价点在ROI上的商家的曝光 $j$ 上的私有价值等于 $CTR_{ij} \times CVR_{ij} \times Price_{ij} \times \frac{1}{ROI}$，而广告主 $i$ 的累计收益为 $\color{red}{v_i(\mathbf{t}^{\prime})} = \sum_j CTR_{ij} \times CVR_{ij} \times Price_{ij}$
流动性福利和社会福利的本质是一样的（可以理解为是同一个指标在不同场景下的不同定义），都是在满足一定约束条件下，买家可以从广告主手里获得的最大收入（这里的最大是针对约束而言的）
- 社会福利 ：只有 IR 约束 ，这个 IR 约束主要针对出价，出价就是商家的私有价值，可以是 ROI 约束 或 CPA 约束
- 流动性福利 ：除了 IR 约束，还有预算约束
- 在预算约束无限时（或不生效时） ，社会福利等价于流动性福利 ，此时有:
  $$SW = LW = \sum_{i\in[n],u_{i}(t_{i},\mathbf{t}^{\prime})\geq 0} \color{red}{\frac{v_i(\mathbf{t}^{\prime})}{R_i}}$$

CA——生成式拍卖-Contextual-Generative-Auction(CGA)

参考链接：
- 原始论文：Contextual Generative Auction with Permutation-level Externalities for Online Advertising, KDD 2025, Alibaba
- 博客：KDD’25 | 生成式拍卖：感知排列外部性的整页优化机制 - 阿里妈妈技术的文章 - 知乎

整体思路总结（摘要）

问题提出 ：传统的拍卖机制（如GSP）依赖于独立的点击率（CTR）假设，未能考虑其他同时被展示 item 的影响（即外部性）。近年来，基于学习的拍卖机制（learning-based auctions）在高维上下文特征编码方面取得了进展。然而，现有方法受限于“预测后分配”的设计范式，仅在候选广告集内建模Set-level外部性（the candidate ad set），未能考虑最终分配的序列上下文，导致次优结果
论文解法 ：论文提出了上下文生成拍卖（Contextual Generative Auction，CGA），这是一个在多槽广告拍卖中引入Permutation-level外部性的新框架。基于论文理论推导的最优解结构，CGA将分配和支付的优化解耦。论文构建了一个自回归生成模型用于分配，并将激励兼容性（IC）约束重新表述为最小化支持梯度计算的事后遗憾（ex-post regret），从而实现最优支付规则的端到端学习
有效性论证 ：大量的离线和在线实验表明，CGA在平台收入和CTR方面显著优于现有方法，同时有效逼近了具有近乎最大收入和最小遗憾的最优拍卖

前置讨论

最优广告拍卖 ：目标是在满足经济属性（如激励兼容性（IC）和个体理性（IR））的同时最大化平台收入。当然，线上部署时还要考虑在线部署的计算复杂性约束
传统的广告拍卖（不考虑外部性）：同时考虑广告主的出价和广告的点击率（CTR）。广义第二价格（GSP）拍卖由于其可解释性和易于实现的特点，长期以来一直是广告拍卖的基准，并进一步演变为诸如 uGSP 和 DeepGSP 等变体。尽管现有方法表现出显著的性能，但 GSP 采用的独立 CTR 假设（即用户的点击仅取决于广告本身）限制了模型的预测能力，因为它忽略了其他同时被展示的广告。实际上，呈现给用户的结果页面包含多个广告，用户在做出决策之前会比较价格和外观等因素；因此，其他同时被展示的广告会影响目标广告的 CTR
外部性 ：外部广告的影响被定义为在线广告中的外部性。关于用户行为的实证研究也表明，最优的广告拍卖设计必须考虑外部性
基于学习的拍卖方法（如深度神经拍卖（DNA）和加权 VCG（SW-VCG）），被提出以更好地捕捉外部性并提升平台收入。然而，这些方法受到“预测后分配”设计范式的限制，因为预测过程仍然对分配结果中的上下文信息一无所知。本质上，这些方法仅对候选广告集中的信息进行建模（Set-level外部性），未能纳入影响最终分配中每个广告 CTR 的序列上下文（Permutation-level外部性），从而导致次优的分配。推荐系统中的重排序研究同样考虑了展示列表中的广告相关性。然而，它们专注于提升整体用户反馈，忽略了广告主的策略行为，因此未能纳入 IC 和 IR 等经济约束，阻碍了它们在在线拍卖环境中最大化收入的适用性
为在线广告平台设计具有Permutation-level外部性的最优拍卖面临三个关键挑战：
- (i) 现有的“预测后分配”设计范式无法在预测广告价值时感知序列上下文
- (ii) 采用类似 VCG 的方法遍历所有排列可以实现最优分配，但其高计算复杂性使其无法适用于在线应用。挑战在于如何在排列空间的阶乘级别内高效探索最优序列
- (iii) IC 条件要求每个广告主的预期价值随其出价非递减。虽然大多数现有方法确保更高的出价能为广告主赢得相同或更高的广告位，但Permutation-level外部性可能导致更高的广告位产生更低的 CTR。如图1所示，来自淘宝平台的工业数据表明，广告的Permutation-level CTR 并不随其分配的广告位单调递增。因此，在Permutation-level外部性下设计具有 IC 约束的广告拍卖是一个 non-trivial 的问题
论文提出了上下文生成拍卖（CGA） ，旨在优化平台收入并保证经济属性(IC和IR)。CGA 的框架遵循论文从理论上推导出的最优 DSIC（占优策略激励兼容）拍卖的结构，将分配和支付的优化解耦。CGA 采用生成器-评估器（G-E）范式来捕捉Permutation-level外部性。具体来说，生成器利用自回归方法生成广告序列作为分配，由训练过的评估器指导，评估器在广告序列中细化上下文交互。此外，直接计算最优支付规则是不可行的，因为 CGA 的分配规则是通过生成模型实现的。受多物品拍卖设计中使用神经网络有效恢复解析解的启发，论文将 IC 约束 重新表述为 要求广告拍卖的预期事后遗憾为零 ，并通过最小化可微分的事后遗憾来学习最优支付规则
论文的主要贡献总结如下：
- 论文提出了具有Permutation-level外部性的多广告位拍卖问题，并从理论上推导出最优的 DSIC 拍卖，为生成拍卖设计提供了理论保证
- 为了建模Permutation-level外部性，论文打破了基于学习的拍卖中的“预测后分配”设计范式，引入了一个自回归生成模型，直接生成分配。基于最优机制的结构，提出的 CGA 利用 G-E 范式优化分配，并通过最小化可微分的事后遗憾来学习最优支付规则
- 在大规模工业数据和在线 A/B 测试中的实验表明，CGA 在平台收入和 CTR 方面优于现有方法，并有效逼近了具有近乎最大收入和可忽略遗憾的最优 DSIC 拍卖

问题定义及讨论

多槽拍卖与Permutation-level外部性

多槽拍卖。在线广告的广告拍卖可以抽象为一个典型的多槽拍卖设计问题。形式上，当用户请求到达时，有 $n$ 个广告主竞标 $k$ 个广告位，每个广告主 $i$ 根据其点击广告 $ad_{i}$ 的私人价值 $v_{i}$ 提交一个出价 $b_{i}$ 。广告主 $i$ 的私人价值是从分布 $f_{i}(\cdot)$ 中独立抽取的， $F_{i}(\cdot)$ 表示概率密度函数（pdf） $f_{i}(\cdot)$ 的累积分布函数（cdf）。令 $\boldsymbol{v}=(v_{1},v_{2},\cdots,v_{n})$ 表示所有广告主的价值分布， $\boldsymbol{v}_{-i}$ 表示排除元素 $a_{i}$ 的价值分布，类似地定义 $\boldsymbol{b}$ 和 $\boldsymbol{b}_{-i}$ 。拍卖者，即广告平台，知道分布 $f=(f_{1},f_{2},\cdots,f_{n})$ （从历史数据中推导），但不知道真实的价值分布 $\boldsymbol{v}$
给定出价分布 $\boldsymbol{b}$ 、用户特征向量 $\boldsymbol{u}$ 以及所有广告特征向量的集合 $\boldsymbol{X}=(\boldsymbol{x}_{1},\boldsymbol{x}_{2},\cdots,\boldsymbol{x}_{n})$ ，广告拍卖机制被形式化为 $\mathcal{M}(\mathcal{A}(\boldsymbol{b};\boldsymbol{X},\boldsymbol{u}),\mathcal{P}(\boldsymbol{b};\boldsymbol{X},\boldsymbol{u}))$ 。分配规则 $\mathcal{A}$ 决定广告位的分配，表示为分配矩阵 $\boldsymbol{A}=(a_{ij})_{n\times k}\in\{0,1\}^{n\times k}$ ，其中 $a_{ij}=1$ 表示广告 $i$ 被分配到广告位 $j$ ，否则 $a_{ij}=\mathbf{0}$ 。注意，一个广告最多分配到一个广告位，每个广告位必须分配一个广告，因此可行的分配矩阵 $\boldsymbol{A}$ 满足 $\sum_{j=1}^{k}a_{ij}\leq 1,\forall i$ 和 $\sum_{i=1}^{n}a_{ij}=1,\forall j$ ；支付规则 $\mathcal{P}$ 决定每个广告的支付，表示为支付向量 $\boldsymbol{p}=(p_{i})_{n}\in\mathbb{R}^{n}$
Permutation-level外部性。广告拍卖中的外部性意味着获胜广告的效用也受到其他获胜广告的影响[15]。对于多槽广告拍卖，外部性效应体现在广告的CTR中。具体来说，CTR模型可以抽象为从广告特征和用户特征映射到用户点击广告概率的函数。论文进一步考虑一个排列感知的CTR模型 $\Theta$ ，它以分配 $\boldsymbol{A}$ 和相关特征为输入，并捕捉 $\boldsymbol{A}$ 内的广告间影响。注意，模型 $\Theta$ 是排列感知的，这意味着即使两个分配包含相同的广告集，如 $\boldsymbol{A}_{1}=(ad_{1},ad_{2},ad_{3})$ 和 $\boldsymbol{A}_{2}=(ad_{3},ad_{2}.ad_{1})$ ，不同的排列会导致广告 $ad_{2}$ 的外部影响差异。形式上，论文将广告 $ad_{i}$ 的CTR表示为 $\Theta(\boldsymbol{x}_{i};\boldsymbol{A},\boldsymbol{X},\boldsymbol{u})$ 。为简化表示，令 $\Theta_{i}(\boldsymbol{b};\boldsymbol{X},\boldsymbol{u})=\Theta(\boldsymbol{x}_{i};\mathcal{A}(\boldsymbol{b};\boldsymbol{X},\boldsymbol{u}),\boldsymbol{X},\boldsymbol{u})$ 。Permutation-level外部性通过模型 $\Theta$ 从分配 $\boldsymbol{A}$ 到CTR的映射过程中编码
问题表述。给定机制 $\mathcal{M}(\mathcal{A},\mathcal{P})$ ，具有估值 $v_{i}$ 的广告主的预期效用为：
$$u_{i}(v_{i};\boldsymbol{b};\boldsymbol{X},\boldsymbol{u})=(v_{i}-p_{i}(\boldsymbol{b};\boldsymbol{X},\boldsymbol{u}))\cdot\Theta _{i}(\boldsymbol{b};\boldsymbol{X},\boldsymbol{u}).$$
考虑到广告主可以通过虚报其价值来最大化其效用，论文引入广告拍卖的两个基本属性以确保广告平台的稳定性：主导策略激励兼容性（DSIC，或IC）和个体理性（IR）
定义1 ：一个拍卖是DSIC或IC的，如果每个广告主通过如实报告其价值来最大化其效用，无论其他广告主如何报告。形式上，
$$u_{i}(v_{i};v_{i},\boldsymbol{b}_{-i};\boldsymbol{X},\boldsymbol{u})\geq u_{i}(v_{i};\boldsymbol{b}_{i},\boldsymbol{b}_ {-i};\boldsymbol{X},\boldsymbol{u}),\forall i\in[n],\forall v_{i},\boldsymbol{b}_{i}\in\mathbb{R}^{+}.$$
定义2 ：一个拍卖是IR的，如果每个广告主的支付不超过其提交的出价。形式上，
$$p_{i}(\boldsymbol{b};\boldsymbol{X},\boldsymbol{u})\leq b_{i},\forall i\in[n].$$
目标是找到一个拍卖机制 $\mathcal{M}$ ，最大化广告平台的预期收入：
$$\mathbb{E}_{\boldsymbol{v}\sim F}Rev^{\mathcal{M}}(\boldsymbol{b},\boldsymbol{X},\boldsymbol{u})=\sum_{i=1}^{n }p_{i}(\boldsymbol{b};\boldsymbol{X},\boldsymbol{u})\Theta_{i}(\boldsymbol{b};\boldsymbol{X},\boldsymbol{u}),$$
同时需要满足IC和IR约束，可以表述为问题（1） ：
$$
\begin{align}
\max_{\mathcal{M}(\mathcal{A},\mathcal{P})}\mathbb{E}_{\boldsymbol{v}\sim F} Rev^{ \mathcal{M}}(\boldsymbol{b},\boldsymbol{X},\boldsymbol{u}),\\
\text{s.t.} \ \text{ IC and IR constraints.}
\end{align}
$$

最优多槽拍卖

为了解决上述具有IC和IR约束的收入最大化拍卖设计问题，一种直观的方法是遵循著名的Myerson拍卖[26]。Myerson拍卖可以适应Permutation-level外部性的设置如下：
定义3 ：（具有Permutation-level外部性的Myerson拍卖）：
- 分配：
  $$\mathcal{A}\in\text{argmax}_{\boldsymbol{A}}\sum_{i=A_{i}}^{A_{k}}\hat{\phi}( \boldsymbol{b},F_{i})\Theta(\boldsymbol{x}_{i};\boldsymbol{A},\boldsymbol{X},\boldsymbol{u});$$
- 支付：
  $$p_{i}=\begin{cases}b_{i}-\frac{\int_{0}^{b_{i}}\Theta_{i}(\boldsymbol{t}, \boldsymbol{b}_{-i};\boldsymbol{X},\boldsymbol{u})d\mathbf{t}}{\Theta_{i}(\boldsymbol{b};\boldsymbol{X},\boldsymbol{u})}&if \ \Theta_{i}(\boldsymbol{b};\boldsymbol{X},\boldsymbol{u})>0;\\ 0,&\text{Otherwise},\end{cases}$$
- 其中 $\hat{\phi}(0,F_{i})$ 表示熨平虚拟价值函数（ironed virtual value function），它在 $v$ 中是单调的，注意这里用户的私有价值是点击价值，所以排序时要乘以CTR $\Theta(\boldsymbol{x}_{i};\boldsymbol{A},\boldsymbol{X},\boldsymbol{u})$
  - 熨平虚拟价值函数（ironed virtual value function）：当虚拟价值函数非单调时，通过“熨平”（ironed）处理使其单调（用常数替代非单调区间使其单调），熨平后的函数简化了优化问题，确保机制设计的可实施性
回顾Myerson引理，如下述定理1所述。注意，引入Permutation-level外部性与传统的Myerson拍卖不同，因为它根据分配结果影响每个广告的CTR。因此，广告 $ad_{i}$ 的出价增加并不一定会增加其CTR，因为分配结果中的广告间影响可能会违反定理1的单调分配要求。论文通过证明，即使存在Permutation-level外部性，如果分配规则最大化虚拟福利，Myerson引理中的单调分配条件仍然成立，如引理1所示。由于篇幅限制，论文将证明放在附录A.1中
定理1 ：（Myerson引理）。对于单参数环境，分配规则 $\mathcal{A}$ 是可实现的，如果存在支付规则 $\mathcal{P}$ 使得机制 $\mathcal{M}(\mathcal{A},\mathcal{P})$ 是DSIC的。以下两个命题成立：
- （1）分配规则是可实现的，当且仅当它是单调的
- （2）如果分配规则 $\mathcal{A}$ 是单调的，则存在唯一的支付规则 $\mathcal{P}$ 使得机制 $\mathcal{M}(\mathcal{A},\mathcal{P})$ 是DSIC的。它由下式给出：
  $$\mathcal{P}_{i}(\boldsymbol{b}_{i},\boldsymbol{b}_{-i})=b_{i}\mathcal{A}_{i}(b_{i},\boldsymbol{b}_{-i}) -\int_{0}^{b_{i}}\mathcal{A}_{i}(\boldsymbol{t},\boldsymbol{b}_{-i})d\mathbf{t}.$$
引理1 ：（具有Permutation-level外部性的单调分配）。对于每个广告 $ad_{i}$ 和 $\boldsymbol{b}_{-i}$ ，获得的CTR $\Theta(\boldsymbol{x}_{i};\mathcal{A}(b_{i},\boldsymbol{b}_{-i}),\boldsymbol{X},\boldsymbol{u})$ 在其出价 $b_{i}$ 中是非递减的（或者说 $\mathcal{A}$ 是单调的），如果分配规则 $\mathcal{A}$ 最大化预期虚拟福利
定理2 ：对于单参数环境，在DSIC拍卖空间中最大化预期收入等于最大化预期虚拟福利
基于定理1、定理2和引理1，我们可以推导出推论1，即定义3中具有Permutation-level外部性的Myerson拍卖构成了问题（1）的最优解
推论1 ：广告拍卖机制 $\mathcal{M}$ ，由定义3中的分配规则 $\mathcal{A}$ 和支付规则 $\mathcal{P}$ 表征，代表了具有Permutation-level外部性的最优机制，能够在满足IC和IR约束的同时最大化平台的预期收入

拍卖设计作为基于学习的问题

直接实现定义3中的分配规则 $\mathcal{A}$ 涉及枚举所有排列以选择最大化虚拟福利的排列，计算复杂度为 $P(n,k)=\frac{n!}{(n-k)!}$ （$n$ 个广告主竞标 $k$ 个广告位）。然而，对于在线广告，以淘宝为例，其中 $n\approx 50$ 和 $k\approx 5$ ，高计算复杂度无法满足在线实时推理需求。因此，论文将拍卖机制参数化为 $\mathcal{M}^{\text{w}}=\langle\mathcal{A}^{\text{w}_{a}},\mathcal{P}^{\text{w}_ {p}}\rangle$ ，参数为 $\text{w}_{a}$ 和 $\text{w}_{p}$ ，并通过解决学习问题来确定这些参数
为了在基于学习的拍卖中施加IC约束并确保优化过程的可微性，类似于基于学习的多物品拍卖的原始工作，论文引入了每个广告主的事后遗憾概念，以量化偏离IC条件的程度。具体来说，广告主 $ad_{i}$ 的事后遗憾定义为通过虚报 $b^{\prime}_{i}$ 可以获得的最大效用增加：
$$rgt_{i}(v_{i},\boldsymbol{X},\boldsymbol{u})=\max_{b^{\prime}_{i}}{u_{i}(v_{i};b^{ \prime}_{i},\boldsymbol{b}_{-i};\boldsymbol{X},\boldsymbol{u})-u_{i}(v_{i};\boldsymbol{b};\boldsymbol{X},\boldsymbol{u})}.$$
因此，当且仅当每个广告主 $ad_{i}$ 的事后遗憾为零时，IC约束得到满足。给定从分布F中抽取的 $L$ 个估值样本，论文得到广告主 $ad_{i}$ 的经验事后遗憾：
$$\widehat{rgt}_{i}=\frac{1}{L}\sum_{l=1}^{L}rgt_{i}(v^{\prime}_{i}, \boldsymbol{X},\boldsymbol{u}).$$
然后论文将拍卖设计问题（1）重新表述为问题（3） ，即最小化预期负收入，约束条件是每个广告主 $ad_{i}$ 的经验事后遗憾为零：
$$
\begin{align}
&\ \min_{\text{w}}-\mathbb{E}_{v\sim F}Rec^{\mathcal{M}^{\text{w}}}\\
&\text{s.t.} \ \widehat{rgt}_{i}=0, \forall i\in[n].
\end{align}
$$

CGA 架构说明

本节详细讨论上下文生成拍卖（CGA）。为了克服“预测后分配”范式在捕捉Permutation-level外部性方面的局限性，CGA采用了生成器-评估器（G-E）架构，如图2所示。生成器利用自回归模块，感知已建立的先前上下文以生成广告序列。评估器估计整个广告序列中的排列感知奖励，通过策略梯度引导生成器实现最优分配。对于在线推理，仅部署生成器，确保广告分配期间的计算延迟最小。此外，引入了一个专用的PaymentNet模块来学习最优支付规则，通过优化可微的事后遗憾进行训练

生成器：自回归生成模块

根据定理2和推论1，生成器的目标是从 $n$ 个候选广告中生成长度为 $k$ 的广告序列 $A$ ，以最大化预期虚拟福利。论文开发了一个自回归生成模块，包括两个关键组件：排列不变的集级编码器和排列等变的解码器。排列不变性[42]是一种架构属性，其中输出对输入的排列保持不变，DNA已证明其在提高广告拍卖平台收入方面的有效性。排列等变性[42]意味着任何输入的排列都会导致输出的相同排列。该属性在自动拍卖设计中被广泛采用[31, 18, 10]，Qin等[30]证明了其在提高基于学习的拍卖的泛化能力方面的有效性。(注：这里刻意保留论文引用序号方便查看原文)
排列不变的集级编码器。广告编码器旨在通过建模Set-level外部性来增强每个广告的表示。它编码候选广告集并提供上下文嵌入 $\boldsymbol{c}$ 作为解码器的初始输入。首先，论文采用自注意力层来捕捉 $n$ 个候选广告之间的相互影响，生成每个广告 $i$ 的集级增强嵌入 $\boldsymbol{h}_{i}$ ：
$$[\boldsymbol{h}_{1},\boldsymbol{h}_{2},\cdots,\boldsymbol{h}_{\boldsymbol{n}}]=self\cdot attention([\boldsymbol{e}_{1}, \boldsymbol{e}_{2},\cdots,\boldsymbol{e}_{\boldsymbol{n}}]),$$
其中 $\boldsymbol{e}_{i}$ 表示广告 $a_{i}$ 的嵌入。由于编码器处理的是无序的广告集，上述注意力层排除了位置编码，论文对 $\boldsymbol{h}_{i},i\in[n]$ 进行求和池化，确保改变输入广告的排列保持相同的输出上下文嵌入 $\boldsymbol{c}$ ：
$$\boldsymbol{c}=MLP([\sum_{i=1}^{n}\boldsymbol{h}_{i};\boldsymbol{h}_{\boldsymbol{u}}]),$$
其中 $\boldsymbol{h}_{\boldsymbol{u}}$ 表示用户表示
排列等变的自回归解码器。为了解决拍卖设计中“预测后分配”范式的局限性，论文引入了一个自回归解码器。该模型有效地捕捉输出广告序列的联合分布[4]以生成广告序列。给定上下文嵌入 $\boldsymbol{c}$ ，概率生成模型学习每个广告序列 $\boldsymbol{A}_{m}$ 的条件概率 $p(\boldsymbol{A}_{m}|\boldsymbol{c})$ 。在推理过程中，模型根据此条件概率从其输出空间中选择特定的分配。在多槽拍卖设置中， $\boldsymbol{A}_{m}$ 由 $k$ 个广告组成： $a_{A_{m_{1}}},a_{A_{m_{2}}},\cdots,a_{A_{m_{k}}}$ ，且 $a_{A_{m_{l}}}$ 不是独立的，自回归解码器使用乘积规则对联合输出分布进行建模：
$$p(a_{A_{m_{1}}},a_{A_{m_{2}}},\cdots,a_{A_{m_{k}}}|\boldsymbol{c})= p(a_{A_{m_{1}}}|\boldsymbol{c})p(a_{A_{m_{2}}}|\boldsymbol{c},a_{A_{m_{1}}})\cdots$$ $$p(a_{A_{m_{k}}}|\boldsymbol{c},a_{A_{m_{1}}},a_{A_{m_{2}}},\cdots,a_{A_{m _{k-1}}}).$$
论文进一步采用GRU单元来建模每个候选广告 $a_{i}$ 在槽 $t\in[k](a_{A_{m_{0}}}=\emptyset)$ 的条件概率 $p(a_{i}|\boldsymbol{c},a_{A_{m_{1}}},\cdots,a_{A_{m_{l-1}}})$ 。在解码开始时，上下文嵌入 $\boldsymbol{c}$ 初始化GRU的隐藏状态，并将表示“开始”的特殊标记作为初始输入馈入GRU。迭代地，第 $t$ 个GRU单元公式化为：
$$\boldsymbol{s}_{t}=GRU(\boldsymbol{s}_{t-1},\boldsymbol{h}_{\mathcal{A}_{1}-1}), t=1,2,\cdots,k,$$
其中 $\boldsymbol{h}_{\mathcal{A}_{1}-1}$ 表示在槽 $t-1$ 中选择的广告的编码表示（ $\boldsymbol{h}_{\mathcal{A}_{0}}=START$ ）， $\boldsymbol{s}_{t-1}$ 表示先前的上下文信息（ $\boldsymbol{s}_{0}=c$ ）。因此，给定槽 $t$ 的状态 $\boldsymbol{s}_{t}$ ，论文得到每个候选广告 $a_{i}$ 的分配概率 $z_{i}^{t}$ （公式（5））：
$$z_{i}^{t}=softmax([MLP([\boldsymbol{s}_{t};\boldsymbol{h}_{i}])+e^{w}\tilde{\phi}_{i}]_{t=1}^{n })_{i},$$
- 其中 $w$ 是一个可学习参数，使得 $e^{w}$ 保持正数，确保更高的虚拟价值导致更大的分配概率，与最大化虚拟福利的目标一致。在槽 $t$ 之前分配的广告被屏蔽，基于 $\boldsymbol{z}^{t}$ 的采样策略确定分配到槽 $t$ 的广告。此采样仅在训练期间进行，以探索多样化的序列生成策略。在推理过程中，选择 $\boldsymbol{z}^{t}$ 中值最高的广告。此选择过程重复 $k$ 次以生成长度为 $k$ 的广告序列，表示为 $\boldsymbol{A}=\left[\boldsymbol{a}_{A_{1}},\boldsymbol{a}_{A_{2}},\cdots,\boldsymbol{a}_{A_{k}}\right]$
此外，由于生成器中的MLP和GRU单元在每个状态-广告对上操作，并且编码器满足排列不变性，解码器表现出排列等变性

评估器：排列感知预测模块

评估器的目标是预测广告分配 $\boldsymbol{A}$ 中每个广告 $\boldsymbol{a}_{A_{i}}$ 的排列感知CTR $\Theta(\boldsymbol{x}_{i};\boldsymbol{A},\boldsymbol{X},\boldsymbol{u})$ 。评估器以分配嵌入 $\boldsymbol{H}_{\boldsymbol{A}}=\left[\boldsymbol{h}_{A_{1}},\boldsymbol{h}_{A_{2}},\cdots,\boldsymbol{h}_{A_{k}}\right]$ 、用户嵌入 $\boldsymbol{e}_{u}$ 和点级CTR $\boldsymbol{\alpha}_{\boldsymbol{A}}\in[0,1]^{k}$ 为输入，并输出排列感知CTR。每个广告 $\boldsymbol{a}_{A_{i}}$ 的嵌入 $\boldsymbol{h}_{A_{i}}$ 来自生成器的编码器，如公式（4）所定义。由于CGA在三阶段广告系统（匹配、预测和拍卖）的末尾运行，为了充分利用在前几个阶段捕捉到的用户兴趣，评估器利用从预测阶段输出的点级CTR $\boldsymbol{\alpha}_{\boldsymbol{A}}$ ，并构建一个Permutation-level广告编码器来估计个性化的外部性感知校准向量 $\boldsymbol{y}_{\boldsymbol{A}}\in(0,2)^{k}$ 。这两个向量随后逐元素相乘以获得排列感知CTR： $\Theta_{\boldsymbol{A}}=min(\boldsymbol{\alpha}_{\boldsymbol{A}}\odot\boldsymbol{y}_{\boldsymbol{A}},1)$
具体来说，论文采用Bi-LSTM层和多头自注意力层来编码广告序列嵌入 $\boldsymbol{H}_{\boldsymbol{A}}$ ，其中Bi-LSTM有效捕捉双向序列信息，而自注意力有效捕捉序列中远距离广告之间的交互。形式上，自注意力层的序列表示定义为：
$$\boldsymbol{H}_{\boldsymbol{A}}^{\boldsymbol{s}}=softmax\left(\frac{\mathcal{Q}_{\boldsymbol{A}}\boldsymbol{K}_{\boldsymbol{A }}^{\top}}{\sqrt{d}}\right)\boldsymbol{V}_{\boldsymbol{A}},$$
其中 $d$ 表示嵌入的维度， $\mathcal{Q}_{\boldsymbol{A}},\boldsymbol{K}_{\boldsymbol{A}},\boldsymbol{V}_{\boldsymbol{A}}$ 表示查询、键和值矩阵，它们从分配嵌入 $\boldsymbol{H}_{\boldsymbol{A}}$ 和位置编码 $\boldsymbol{P}\boldsymbol{E}_{\boldsymbol{A}}$ 的线性变换中得出。论文采用的位置编码机制遵循中的正弦版本，赋予自注意力层辨别排列信息的能力
接下来，论文通过Bi-LSTM层获得 $\boldsymbol{H}_{\boldsymbol{A}}$ 的前向输出状态 $\boldsymbol{H}_{\boldsymbol{A}}^{f}$ 和后向输出状态 $\boldsymbol{H}_{\boldsymbol{A}}^{b}$：
$$\boldsymbol{H}_{\boldsymbol{A}}^{f} =\text{Bi-LSTM}_{\text{forward}}(\boldsymbol{H}_{\boldsymbol{A}})$$ $$\boldsymbol{H}_{\boldsymbol{A}}^{b} =\text{Bi-LSTM}_{\text{backward}}(\boldsymbol{H}_{\boldsymbol{A}}).$$
为简洁起见，论文省略了Bi-LSTM的实现细节，包括输入门、遗忘门、输出门和单元状态

支付计算

根据推论1，最优支付在定义3中定义，其中积分项可以重写为期望：
$$\int_{0}^{b_{i}}\Theta_{i}(t,\boldsymbol{b}_{-i};\boldsymbol{X},\boldsymbol{u})dt=b_{i}E_{t_{i}-U[0,b_{i}] }[\Theta_{i}(t_{i},\boldsymbol{b}_{-i};\boldsymbol{X},\boldsymbol{u})],$$
可以使用蒙特卡罗采样进行近似。然而，注意 $\Theta_{i}(t_{i},\boldsymbol{b}_{-i};\boldsymbol{X},\boldsymbol{u})=\Theta(\boldsymbol{x}_{i};\mathcal{A}(t_{i}, \boldsymbol{b}_{-i};\boldsymbol{X},\boldsymbol{u}),\boldsymbol{X},\boldsymbol{u})$ 。处理每个样本需要调用生成器 $\mathcal{A}$ 和评估器 $\Theta$ ，导致推理期间的高计算成本。减少样本数量可以缓解这一问题，但会增加支付方差，直接影响平台收入和广告主效用
受[11]中神经网络在多物品拍卖设置中有效逼近最优机制的成功应用启发，论文引入PaymentNet来学习最优支付规则。具体来说，输入包括分配嵌入 $\boldsymbol{H}_{\boldsymbol{A}}\in\mathbb{R}^{K\times d}$ 、自排除出价分布 $\boldsymbol{B}^{-}=[\boldsymbol{b}_{-\boldsymbol{A}_{1}},\boldsymbol{b}_{-\boldsymbol{A}_{2}},\cdots,\boldsymbol{b}_{- \boldsymbol{A}_{k}}]\in\mathbb{R}^{K\times(k-1)}$ ，以及预期价值分布 $\boldsymbol{Z}\cdot\Theta\in\mathbb{R}^{L\times 1}$ ，其中 $\boldsymbol{Z}=[ z^{1}_{\boldsymbol{A}_{1}},z^{2}_{\boldsymbol{A}_{2}},\cdots,z^{k}_{\boldsymbol{A}_{k}} ]$ 表示公式（5）中定义的分配概率， $\boldsymbol{\Theta}=[\Theta_{\boldsymbol{A}_{1}},\Theta_{\boldsymbol{A}_{2}},\cdots,\Theta_{\boldsymbol {A}_{k}}]$ 表示评估器估计的排列感知CTR。此外，为了满足IR约束，如定义2所述，PaymentNet采用sigmoid激活函数计算支付率 $\tilde{\boldsymbol{p}}\in[0,1]^{k}$ ，随后输出支付 $\boldsymbol{p}=\tilde{\boldsymbol{p}}\odot\boldsymbol{b}$ 。形式上，支付率定义为：
$$\tilde{\boldsymbol{p}}=\sigma(r(r(\lfloor\boldsymbol{H}_{\boldsymbol{A}};\boldsymbol{B}^{-};\boldsymbol{Z}\cdot\Theta \rfloor))),$$
其中 $\sigma(\cdot)$ 和 $r(\cdot)$ 分别表示具有sigmoid和ReLU激活函数的全连接层

优化与训练

根据推论1，最优分配规则仅需要最大化虚拟福利，并且与支付规则无关。因此，论文将G-E框架和PaymentNet的优化解耦，这保持了CGA的最优性

G-E框架的优化

在G-E框架中，评估器负责捕捉Permutation-level外部性并引导生成器获得最优分配
首先进行评估器训练 ：使用 List-wise 广告点击数据训练评估器 $\Theta$ 至收敛。每个样本 $l\in\mathcal{D}$ 是暴露给用户的长度为 $k$ 的广告序列，标签 $y^{l}_{i}\in\{0,1\}$ 表示用户是否点击了第 $i$ 个广告。二元交叉熵损失定义为：
$$\mathcal{L}_{E}=-\frac{1}{|\mathcal{D}|}\sum_{l\in\mathcal{D}}\sum_{i=1}^{k}(y ^{l}_{i}\log\theta^{l}_{i}+(1-y^{l}_{i})\log(1-\theta^{l}_{i})),$$
- 其中 $\theta^{l}_{i}$ 表示评估器预测的广告序列 $l$ 中第 $i$ 个广告的排列感知CTR
在训练评估器 $\Theta$ 至收敛后，论文冻结其参数并使用来自评估器的奖励通过策略梯度训练生成器。在每个槽 $t$ ，上下文信息 $\boldsymbol{s}_{t}$ 作为状态，生成器输出的分配概率 $z^{t}_{i}$ 作为动作。由于 $\boldsymbol{s}_{t}$ 仅编码先前的上下文，为了捕捉双向上下文信息，论文使用训练有素的评估器来估计完整广告序列 $\boldsymbol{A}$ 中每个候选广告的排列感知奖励。类似于，论文将此排列感知奖励分解为两部分
自身奖励（Self-Reward）：与最优分配的目标一致，论文使用评估器 $\Theta$ 来估计每个选定广告 $a_{A_{i}}$ 的预期虚拟福利，称为自我奖励：
$$r^{self}_{A_{i}}=\hat{\phi_{i}}\cdot\Theta_{i}(\boldsymbol{b};\boldsymbol{A},\boldsymbol{u}).$$
外部奖励（External-Reward）：每个选定的广告不仅贡献其奖励，还由于Permutation-level外部性影响其他广告的CTR。类似于经典VCG机制中应用的边际贡献，论文将此外部效应建模为外部奖励：
$$r^{external}_{A_{i}}=\sum_{j\in\boldsymbol{A}_{-i}}\tilde{\phi_{j}}\Theta_{j}(\boldsymbol{b}; \boldsymbol{A},\boldsymbol{u})-\sum_{j\in\boldsymbol{A}_{-i}}\tilde{\phi_{j}}\Theta_{j}(\boldsymbol{b}_{-i}; \boldsymbol{A}_{-i},\boldsymbol{u}),$$
- 其中 $\boldsymbol{A}_{-i}$ 表示排除 $a_{A_{i}}$ 的广告序列
结合上述两个奖励，论文得到选择 $a_{A_{i}}$ 的排列感知奖励，定义为：
$$
\begin{align}
r_{A_{i}} &=r^{self}_{A_{i}}+r^{external}_{A_{i}} \\
&=\hat{\phi_{i}}\Theta_{i}(\boldsymbol{b};\boldsymbol{A},\boldsymbol{u})+\sum_{j\in\boldsymbol{A}_ {-i}}\tilde{\phi_{j}}\Theta_{j}(\boldsymbol{b};\boldsymbol{A},\boldsymbol{u})-\sum_{j\in\boldsymbol{A}_{-i}} \tilde{\phi_{j}}\Theta_{j}(\boldsymbol{b}_{-i};\boldsymbol{A}_{-i},\boldsymbol{u})\\
&=\sum_{j\in\boldsymbol{A}}\tilde{\phi_{j}}\Theta_{j}(\boldsymbol{b};\boldsymbol{A},\boldsymbol{u })-\sum_{j\in\boldsymbol{A}_{-i}}\tilde{\phi_{j}}\Theta_{j}(\boldsymbol{b}_{-i};\boldsymbol{A}_{-i}, \boldsymbol{u}).
\end{align}
$$
最后，生成器的损失函数定义为：
$$\mathcal{L}_{G}=-\frac{1}{|\mathcal{D}|}\sum_{s\in\mathcal{D}}\sum_{i\in k}r_{ A^{s}_{i}}\log z_{A^{s}_{i}},$$
- 其中 $s$ 表示数据集 $\mathcal{D}$ 中的一个样本，代表请求的候选广告集， $A^{s}_{i}$ 表示生成器基于输入广告集 $s$ 输出的广告分配中的第 $i$ 个广告， $z_{A^{s}_{i}}$ 表示Generator 公式（5）中的分配概率

PaymentNet的优化

在训练生成器 $\mathcal{A}$ 和评估器 $\Theta$ 至收敛后，论文冻结其参数，然后应用增广拉格朗日方法来解决约束优化问题（3）以优化PaymentNet。增广拉格朗日函数定义为：
$$\mathcal{L}_{P}=-\frac{1}{|\mathcal{D}|}\sum_{s\in\mathcal{D}}(\sum_{i\in k} \mathcal{P}_{i}(\boldsymbol{A}^{s})\Theta_{i}(\boldsymbol{A}^{s})-\sum_{i\in k}\lambda_{i} \widehat{rgt}^{s}_{i}-\frac{\rho}{2}\sum_{i\in k}(\widehat{rgt}^{s}_{i})^{2}),$$
- 其中 $\boldsymbol{A}^{s}$ 表示冻结生成器 $\mathcal{A}$ 基于广告集 $s$ 的输入输出的分配， $\lambda_{i}$ 表示拉格朗日乘数， $\rho>0$ 表示IC惩罚项的超参数
类似于[11]，基于上述拉格朗日函数（10）的优化过程包括
- （i）更新PaymentNet： $\boldsymbol{w}_{\boldsymbol{p}}^{\boldsymbol{n}\boldsymbol{e}\boldsymbol{w}}=\textit{argmin}_{\lambda\boldsymbol{w}\rho} \mathcal{L}_{P}(\boldsymbol{w}_{\boldsymbol{p}}^{\sigma Id};\boldsymbol{\lambda}^{\sigma Id})$
- （ii）更新拉格朗日乘数： $\boldsymbol{\lambda}^{\boldsymbol{n}\boldsymbol{e}\boldsymbol{w}}=\boldsymbol{\lambda}^{\sigma Id}+\rho\ \overline{r} \boldsymbol{g}^{\intercal}(\boldsymbol{w}_{\boldsymbol{p}}^{\boldsymbol{n}\boldsymbol{e}\boldsymbol{w}})$
注意问题（3）是非凸的。因此，上述拉格朗日方法不能保证收敛到全局最优。然而，实验结果表明，优化后的CGA可以逼近最优收入，且遗憾最小，如原始论文第5.2节实验所述

Experiments

在本节中，论文进行了离线实验和在线A/B测试，以评估CGA的有效性，主要关注以下问题：
- RQ1 ：与现有广告拍卖相比，CGA在平台收入和CTR等关键指标上的表现如何？
- RQ2 ：与集级和无外部性相比，建模Permutation-level外部性的效果如何？
- RQ3 ：CGA的各种设计如何影响其性能？
- RQ4 ：论文提出的CGA在高效部署的实际广告拍卖场景中表现如何？

Experiment Setup

数据集

在离线实验中，论文使用从2024年1月期间从领先的电子商务平台淘宝收集的真实日志来评估CGA的性能。训练集包括从1月20日至1月23日随机选择的500,000次拍卖，涉及1,100,875个唯一广告主，而测试集包括从1月25日随机选择的100,000次拍卖，涉及452,671个唯一广告主。对于数据集中的每个拍卖样本，广告系统选择大约30个广告主作为拍卖阶段的候选者，他们提交出价以竞争广告位。论文在离线实验中设置广告位数量 $k=3$

基线方法

论文将CGA与代表性的拍卖机制进行比较。基线方法根据外部性建模的粒度分为三组
无外部性（W/O externalities） ：
- GSP ：GSP根据出价和预测CTR的乘积对广告进行排名，不建模外部性
Set-level外部性（Set-level externalities） ：
- DNA ：在GSP的基础上，DNA通过建模候选广告的Set-level外部性来预测每个广告的排名分数，并相应地进行分配，不考虑广告列表中广告之间的相互影响
- SW-VCG ：SW-VCG将多槽拍卖设计形式化为广告和广告位之间的最大加权二分匹配问题，仅捕捉候选广告的Set-level外部性以估计边权重
Permutation-level外部性（Permutation-level externalities） ：
- 具有Permutation-level外部性的VCG拍卖（VCG）：VCG选择最大化社会福利的广告排列进行分配，并结合支付规则以满足IC。论文使用CGA的评估器评估所有候选广告的排列，使VCG能够捕捉Permutation-level外部性
- EdgeNet ：EdgeNet利用Transformer替换DNA的集编码器，并采用贪婪策略依次分配广告，建模部分Permutation-level外部性
- Optimal ：为了评估CGA对理论上界的逼近，根据推论1，论文通过遍历所有排列以最大化虚拟福利并使用蒙特卡罗采样计算支付来构建此基线

性能指标

论文考虑以下指标来分别衡量平台收入、用户体验和广告主的事后遗憾
- 每千次展示收入： $\text{RPM}=\frac{\sum click\textit{$\times$payment}}{\sum impression}\times 1000$
- 点击率： $\text{CTR}=\frac{\sum click}{\sum impression}$
- IC指标： $\Psi=\frac{1}{|D|}\sum_{s\in D}\sum_{i\in k}\frac{\overrightarrow{rg^{i}_{i}}}{ u_{i}(v^{i}_{h},\boldsymbol{b}^{s};\boldsymbol{X}^{i},\boldsymbol{u}^{s})}$ ，其中 $\overrightarrow{rg^{i}_{i}}$ 在公式（2）中定义。这是广告拍卖机制IC测试的常用指标[7, 23, 25, 33]，衡量广告主通过操纵出价可以获得的效用相对增加。与[38]中的评估过程一致，论文对每个广告主的出价进行反事实扰动，将 $b_{i}$ 替换为 $a\times b_{i}$ ，其中 $a\in{0.2\times j\mid j=1,2,\cdots,10}$

实现

在CGA中，论文将特征的嵌入大小设置为8。为了从不同的表示子空间中捕捉更丰富的信息，所有注意力层都使用具有4个注意力头的多头注意力机制。外部性感知校准向量 $\boldsymbol{\gamma_{A}}$ 和支付率 $\hat{\boldsymbol{p}}$ 使用具有128和32大小隐藏层的MLP得出。CGA使用Adam优化器以1e-3的学习率和512的批量大小进行训练。所有基于学习的基线方法通过网格搜索调整超参数，探索学习率{1e-5, 1e-4, 1e-3, 1e-2}、批量大小{256, 512, 1024, 2048}和隐藏大小{8,16,32,64}

离线比较（RQ1 & RQ2）

CGA和基线-Optimal涉及铁虚拟价值函数，这需要了解每个广告主的价值分布 $f_{i}(\cdot)$ 。从历史数据中估计 $f_{i}(\cdot)$ 在现有研究中已有充分覆盖[6, 21, 27, 28]。论文不深入探讨此估计，因为CGA专注于使用生成模型捕捉Permutation-level外部性，与分布估计技术无关。为了避免分布估计方法在比较实验中的偏差，遵循[22]，论文预设每个广告主的价值的条件分布为均匀分布和指数分布 ，并相应地重新生成出价。对于SW-VCG，由于其预测的广告分数 $Scr_{i}$ 旨在拟合虚拟价值，论文直接将 $Scr_{i}$ 设置为 $\hat{\phi}_{i}$ 进行比较
在上述两种分布下的实验结果如表I所示。论文的主要观察结果如下：
- (1) 随着外部性建模从无外部性到集级再到Permutation-level，拍卖性能在三个指标上都有所提高（更高的RPM和CTR，更低的遗憾）5。这突显了在拍卖设计中建模细粒度外部性的重要性（RQ2）。为了进一步研究外部性的影响，论文在CTR预测任务上进行了比较实验。结果如表2所示，其中“无外部性”表示使用点级pCTR，“集级”表示使用集级广告编码器（如第3.2节所述）替换评估器的Permutation-level广告编码器。结果表明，具有Permutation-level外部性的评估器提高了预测值的准确性，解释了拍卖指标的改进
- (2) 与基于枚举的基线-Optimal相比，CGA实现了约95%的收入最大化，且事后遗憾可忽略不计。这表明CGA能够高效地进行广告分配，并紧密逼近最优拍卖机制

消融研究（RQ3）

为了验证CGA各种设计考虑的有效性，论文构建了以下变体：
- CGA- $\Theta$ 移除了评估器 $\Theta$ ，并使用点级CTR来评估每个广告分配的虚拟福利
- CGA（端到端）直接使用公式（10）中的 $\mathcal{L}_{P}$ 训练生成器和PaymentNet。相比之下，CGA首先训练生成器至收敛，冻结其参数，然后训练PaymentNet
- CGA- $r^{self}$ 移除了生成器损失函数 $\mathcal{L}_{G}$ 中的自我奖励 $r^{self}$ （公式（7））
- CGA- $r^{external}$ 移除了生成器损失函数 $\mathcal{L}_{G}$ 中的外部奖励 $r^{external}$ （公式（8））
- CGA- $\tilde{\phi}$ 将虚拟价值 $\hat{\phi_{i}}$ 替换为 $b_{i}$ 在 $\mathcal{L}_{G}$ 中
结果如表3所示，论文观察到：
- (1) CGA- $\Theta$ 表现不如CGA，表明生成器本身无法完全捕捉Permutation-level外部性，因为自回归模型仅感知先前的上下文。G-E框架通过策略梯度将完整的序列知识提炼到生成器中
- (2) CGA（端到端）表现较差。一个可能的原因是CGA使用PaymentNet来学习最优支付，因此在端到端训练时，收入梯度必须通过PaymentNet才能到达生成器，这使得收敛到最优分配变得复杂。此外，推论1确保解耦优化保持最优性，因此生成器可以专注于最大化虚拟福利
- (3) CGA- $r^{self}$ 表现最差，因为缺少每个选定广告的自身价值增量。CGA优于CGA- $r^{external}$ ，因为它使用外部奖励来建模每个选定广告对最终分配列表的影响
- (4) 估计价值分布 $\hat{f}(\cdot)$ 需要对出价策略进行经验假设，因为广告平台只能观察到出价，导致估计的 $\hat{f}(\cdot)$ 存在偏差。为了评估移除价值分布对CGA性能的影响，论文构建了变体CGA- $\tilde{\phi}$ 。如表3所示，CGA- $\tilde{\phi}$ 在收入（2.6%）和CTR（1.9%）方面仅略有下降。这一小幅下降可能是由于CGA对外部性的建模，捕捉了广告间的相关性，并通过其他广告主的出价部分反映了缺失的价值分布信息

在线A/B测试（RQ4）

为了验证CGA在现实世界中的有效性，论文通过在线A/B测试将CGA与完全部署在淘宝广告系统中的DNA进行比较。表4展示了2023年8月19日至8月25日期间使用2%总生产流量进行的在线A/B测试结果。CGA在RPM上实现了3.2%的提升，同时在线响应时间（RT）每请求平均增加了3毫秒（相对增加1.6%），表明CGA能够通过生成模型高效探索分配空间并提升平台收入。此外，广告主的投资回报率（ROI）提高表明，CGA的收入提升并非来自虚高的支付，而是通过捕捉Permutation-level外部性优化广告分配，这一点从CTR和总商品交易额（GMV）的显著提升中得到了证明

结论

一句话总结 ：论文提出了上下文生成拍卖（CGA），旨在将Permutation-level外部性引入在线多槽广告拍卖中
方案细节 ：论文的主要理论结果表明，经典的Myerson拍卖在适应Permutation-level外部性时保持了它的最优性。这一见解推动了CGA框架的设计，该框架将分配和支付的优化解耦。具体来说，论文开发了一个具有G-E学习范式的自回归生成模型来优化分配，并通过将IC约束量化为预期事后遗憾来学习最优支付
有效性论证 ：大量的离线和在线实验验证了CGA的有效性
特别说明 ：CGA的自回归生成过程不限于特定的生成模型，可以适应各种先进的解决方案
未来展望 ：未来的研究将扩展这种上下文生成机制，以整合来自不同渠道的异构 item 。

Hexo——Next主题搜索窗口无法弹出

参考博客： https://www.sqlsec.com/2017/12/hexosearch.html

问题描述

有时候会遇到在Mac上Next主题窗口无法弹出的问题
问题分为两类
- 一类为找不到 search.xml 文件：加载 search.xml 时错误为404
- 另一类为文章中有特殊字符：加载 search.xml 检查时错误为304

解决方案

404类

修改最外层配置文件./_config.yml,添加以下语句(实测这一步非必须)
1
2
3
4
5
search:
path: search.xml
field: post
format: html
limit: 10000

安装搜索插件

1	npm install hexo-generator-searchdb --save

304类

304状态说明是加载文件存在，但是无法正常解析文件
直接用浏览器访问 search.xml 文件链接，然后查看文件解析异常出现在哪个地方，然后删除特殊字符即可
- 个人理解，从哪个文件不能搜索，特殊字符就出现在哪个文件中
- 说明：目前还没遇到过这种情况，后面遇到会再补充

NLP——困惑度-Perplexity

本文主要介绍困惑度（Perplexity，简称为 PPL）在语言模型评估中的作用

困惑度的整体说明

困惑度（Perplexity，PPL）本质是交叉熵损失 $H(p|q)$ 的一个等价指标
$$\text{Perplexity} = e^{H(p|q)}$$
- 其中 $H(p|q)$ 衡量真实标签和模型输出概率之间的差异
语言模型中损失函数即交叉熵损失，此时有 $loss = H(p|q)$，即：
$$\text{Perplexity} = e^{\text{loss}}$$
- 特别是预训练和 SFT 阶段，一般符合这个情况，RL 阶段则根据不同的损失归一化方式有所不同
- 注：一般语言模型中是先计算单个样本的困惑度（对应指数上是单个样本的 Loss），然后再平均后上报
- 参考链接：How to calculate perplexity for a language model using Pytorch, StackOverflow
  1
  perplexity = torch.exp(loss)
给测试集的句子赋予较高概率值的语言模型较好，在测试集上困惑度越小，模型越好
当一个语言模型训练完成后，测试集中的句子（一般是正常的自然语言句子）出现概率越高越好，概率越大，困惑度越小

单文档困惑度的定义

给定模型 $\mathcal{M}$，测试文档 $d = (w_{1}, w_{2},\cdots,w_{N})$，则模型 $\mathcal{M}$ 下评估测试文档 $d$ 的困惑度 $\text{Perplexity}_\mathcal{M}(d)$ 原始定义为：
$$
\begin{align}
\text{Perplexity}_\mathcal{M}(d) &= P_\mathcal{M}(d)^{-\frac{1}{N}} \\
&= P_\mathcal{M}(w_{1}, w_{2},\cdots,w_{N})^{-\frac{1}{N}}
\end{align}
$$
常常会使用以下形式：
$$ \text{Perplexity}_\mathcal{M}(d) = \exp\left (-\frac{1}{N}\log P_\mathcal{M}(w_{1}, w_{2},\cdots,w_{N})\right ) $$
进一步有：
$$
\begin{align}
\text{Perplexity}_\mathcal{M}(d) &= \exp\left (-\frac{1}{N}\log P_\mathcal{M}(w_{1}, w_{2},\cdots,w_{N})\right ) \\
&= \exp\left (-\frac{1}{N}\log\prod_{n=1}^{N}P_\mathcal{M}(w_{n}|w_1,\cdots,w_{n-1})\right ) \\
&= \exp\left (-\frac{1}{N}\sum_{n=1}^{N}\log P_\mathcal{M}(w_{n}|w_1,\cdots,w_{n-1})\right ) \\
\end{align}
$$
- 计算时，常常使用上面加法的形式
以上多种形式等价，两边取对数在变成自然数的指数即可证明：
- 取对数：
  $$
  \begin{align}
  Log(\text{Perplexity}_\mathcal{M}(d) ) &= -\frac{1}{N}\log P_\mathcal{M}(w_{1}, w_{2},\cdots,w_{N}) \\
  \end{align}
  $$
- 变指数：
  $$
  \begin{align}
  \text{Perplexity}_\mathcal{M}(d) &= e^{-\frac{1}{N}\log P_\mathcal{M}(w_{1}, w_{2},\cdots,w_{N})} \\
  &= \exp\left (-\frac{1}{N}\log P_\mathcal{M}(w_{1}, w_{2},\cdots,w_{N})\right ) \\
  \end{align}
  $$
- 特别说明，一些地方会将对数和指数的底同时换成 2，实际上从推导上看，可以换成任意底数

多文档困惑度的定义

基本思路：将多文档拼接起来，视作单个文档，然后计算困惑度即可（但需要考虑文档间词概率相互独立）
以上是一个文档的表述，对于多个文档 $D = (d_{1}, d_{2},\cdots,d_{M})$ ，其中 $d_m = (w_{1}^{m}, w_{2}^{m},\cdots,w_{N_{m}})$，则多文档的困惑度定义为：
$$
\begin{align}
\text{Perplexity}_\mathcal{M}(D) &= P_\mathcal{M}(D)^{-\frac{1}{\sum_{m=1}^{M}N_{m}}} \\
&= \left(\prod_{m=1}^{M} P_\mathcal{M}(d_{m})\right)^{-\frac{1}{\sum_{m=1}^{M}N_{m}}}
\end{align}
$$
- 文档之间互相独立，所以能推出上面的结论
也常常写作如下形式
$$
\begin{align}
\text{Perplexity}_\mathcal{M}(D) &= \exp\left(-\frac{1}{\sum_{m=1}^{M}N_{m}}\sum_{m=1}^{M}\log P_\mathcal{M}(w_{1}^{m}, w_{2}^{m},\cdots,w_{N_{m}}^{m})\right) \\
\end{align}
$$
进一步可得
$$
\begin{align}
\text{Perplexity}_\mathcal{M}(D) &= \exp \left ( -\frac{1}{\sum_{m=1}^{M}N_{m}}\sum_{m=1}^{M}\log P_\mathcal{M}(w_{1}^{m}, w_{2}^{m},\cdots,w_{N_{m}}^{m}) \right ) \\
&= \exp \left ( -\frac{1}{\sum_{m=1}^{M}N_{m}}\sum_{m=1}^{M}\log\prod_{n=1}^{N_{m}}P_\mathcal{M}(w_{n}^{m}|w_{1}^{m},\cdots,w_{n-1}^{m}) \right ) \\
&= \exp \left ( -\frac{1}{\sum_{m=1}^{M}N_{m}}\sum_{m=1}^{M}\sum_{n=1}^{N_{m}}\log P_\mathcal{M}(w_{n}^{m}|w_{1}^{m},\cdots,w_{n-1}^{m}) \right ) \\
\end{align}
$$
注意：多个文档的困惑度不是简单的等于所有文档困惑度的积或和 ，而是等于把所有文档合并成一个大文档,大文档的困惑度则是最终所有文档的困惑度
特别说明：一些地方也会使用平均法，使用每个文档的平均困惑度代表示多文档的困惑度

LDA 的困惑度

LDA中 $w_{1},w_{2},\cdots,w_{n}$ 在参数已知的情况下是互相独立的,则有
$$
\begin{align}
\text{Perplexity}_\mathcal{M}(d) &= e^{-\frac{1}{\sum_{m=1}^{M}N_{m}}\sum_{m=1}^{M}\log P_\mathcal{M}(w_{1}^{m}, w_{2}^{m},\cdots,w_{N_{m}}^{m})} \\
&= \exp \left ( -\frac{1}{\sum_{m=1}^{M}N_{m}}\sum_{m=1}^{M}\log P_\mathcal{M}(w_{1}^{m}, w_{2}^{m},\cdots,w_{N_{m}}^{m}) \right ) \\
&= \exp \left ( -\frac{1}{\sum_{m=1}^{M}N_{m}}\sum_{m=1}^{M}\log\prod_{n=1}^{N_{m}}P_\mathcal{M}(w_{n}) \right ) \\
&= \exp \left ( -\frac{1}{\sum_{m=1}^{M}N_{m}}\sum_{m=1}^{M}\log\prod_{n=1}^{N_{m}}\sum_{k=1}^{K}P_\mathcal{M}(w_{n}=t|z_{n}=k;\mathcal{M})P_\mathcal{M}(z_{n}=k|d=d_{m};\mathcal{M})\right ) \\
&= \exp \left ( -\frac{1}{\sum_{m=1}^{M}N_{m}}\sum_{m=1}^{M}\log\prod_{n=1}^{N_{m}}\sum_{k=1}^{K}\theta_{m,k}\phi_{k,t}\right ) \\
&= \exp \left ( -\frac{1}{\sum_{m=1}^{M}N_{m}}\sum_{m=1}^{M}\log\prod_{n=1}^{N_{m}}\theta_{m,:}\phi_{:,t}\right ) \\
&= \exp \left ( -\frac{1}{\sum_{m=1}^{M}N_{m}}\sum_{m=1}^{M}\sum_{n=1}^{N_{m}}\log\theta_{m,:}\phi_{:,t}\right ) \\
\end{align}
$$
其中 $\phi_{k,t}$ 表示单词t在主题k中出现的概率，$\theta_{m,k}$ 表示主题k在文档m中出现的概率
$\sum_{k=1}^{K}\theta_{m,k}\phi_{k,t} = (\theta_{m,:}\phi_{:,t})$ 就是单词t出现在文档m中的概率(对隐变量主题k积分)
上面式子中 $(\theta_{m,:}\phi_{:,t})$ 就是两个向量的内积，在这里: $\theta_{m,:}$ 代表行向量，表示当前文档 $d_{m}$ 的主题分布, $\phi_{:,t}$ 代表列向量,表示当前每个主题生成词 $w_{t}$ 的概率
计算公式的代码可参考L-LDA模型的实现GitHub仓库: Labeled-LDA-Python 中的perplexity函数和log_perplexity函数

CA——Feature-Hashing

参考文献: Feature Hashing for Large Scale Multitask Learning, 2009, Yahoo! Research
特征哈希(Feature Hashing)常用于数据特征降维，同时尽量保留原始特征的表达能力

论文贡献

给出了一种高维数据降维方法，特征哈希(Feature Hashing)
严格证明了特征哈希的可用性

Background

一种构造组合特征的方法是笛卡尔乘积
计算广告领域往往有数十亿的高维特征
一种表达方式是使用词表法，对每个特征从词表里面进行查询
- 缺陷一：拓展问题，每次拓展词表时难度较大(难以进行模型升级，因为特征维度在变化)
- 缺陷二：无法处理词表中不存在的特征(Unknown特征)
一般的降维方法容易带来特征表达能力的损失

特征哈希

哈希函数定义(参考自博客：https://blog.csdn.net/qjf42/article/details/82387559)

def feature_hashing(features, m):
	"""
	Args:
		features: 输入特征序列，可以是数字，字符串(本质还是数字)
		m: 输出的特征维度，通常是2**26(vw),2**20(scikit-learn)
	Returns:
		m维的（稀疏）向量
	"""
	# 这里的x一般是稀疏表示的（如：scipy.sparse.csr_matrix），这里是为了方便说明
	x = np.zeros(m)
	for feature in features:
		# hash_func_1保证散列尽量平均且散列速度快
		idx = hash_func_1(feature) % m 
		# 这里在原始论文中
		sign = hash_func_2(feature) % 2
		if sign == 1:
			x[idx] += 1
		else:
			x[idx] -= 1
	return x

输出特征维度一般为 $m = 2^24$ 等，是一个认为给定的数字

与词表法比较：
- 解决了模型升级时的特征拓展问题(增加新特征时，特征的维度不会变化)
- 解决了Unknown特征问题(个人理解：因为hash函数不管是什么特征，都可以一视同仁)
- 无需查表，节省了查表的时间(个人理解：其实查表时一般实现方式也是用哈希表构建索引，所以这里不能算是优势)
- 完成了降维(这里是把字典法里面对邮件或者文档的id也算作一个特征，这个特征one hot表示一下将会造成数据维度变得非常大？但是id算做特征有什么意义吗？)

一些说明

冲突总会发生，也就是说不同一个特征总有一定的概率被映射到同一个维度(即两个不同特征的idx值可能相等)上
Paper中的垃圾邮件过滤模型实验证明：冲突造成的损失漏召率在 $m=2^22$ 时影响约为1%，接近不做hash时的效果(特征维度在不做hash约为 $2^{25}$)且在 $m=2^{18}$ 时为1.12%，也只升高了一点点
另外：无论如何，总有特殊情况，比如重要的特征如用户的性别特征“男”和“女”二者可能被映射到同一个维度上
- 这里编码时是男:(1, 0), 女(0, 1)这样的，所以如果二者映射到同一个维度上，那么这两个特征丢失了原本的表达能力
- 真实环境中如果遇到这些问题将会很难调试，如果找到了相关的问题，可以通过修改映射函数的输入参数字符串等方式来错开两个特征
特征哈希本身可以类比于机器学习中的核技巧,所以特征哈希也称为哈希技巧

一些理解

知乎用户

参考Ainika Peng的博客：https://www.zhihu.com/question/264165760/answer/279676705
一般而言这类技术是为了解决两个问题：
- 一是将categorical的特征编码为模型可理解的格式 ，这是个基础问题。One-Hot Serializing就可以达到这个效果，例如将训练样本中出现过的的每个deviceid按顺序递增编号（比如deviceid@xxx:1 -> feature@10000:1）
  - 缺点1：这个映射表需要传递给引擎端，在prediction的时候照着再查一遍，数据量大且数据结构设计不好的时候很费时间；
  - 缺点2：有些频次很低的特征置信度不高，单独出现对模型无益（甚至over-fitting）。这时候可以使用按频次截断技术进行降维。比如微软在deep crossing中提到的特征工程方法：只保留曝光最多的10k个campaign id编码为0-9999，其余的id全部编码为10000，但辅以poCTR等连续特征作为辅助。事实上这是一种手工的Hashing方法
- 二是尽可能在保留有效信息的基础上降低训练和预测过程的时间复杂度
自动Hashing方法的好处是：
- 只要训练和预测时使用的hashing方法一致，对同一个特征的编码结果即一致，因此引擎预测或提供数据dump的时候无需查找编码表。所以其最大优点在于数据一致性和速度提升，这在极大规模特征和在线学习中至关重要
我们说的Hashing算法一般而言均特意设计为低碰撞率
- 因此一般hashing算法本身不会大幅降低特征维度，自然也不会大幅损失特征信息。真正可能存在问题的是hashing之后的降维过程
- 一个非常常见的陷阱是string哈希到int64后取模m，试图将特征压缩至m维one-hot空间。在这种情况下，对于不知情的随机hashing过程，不同特征的碰撞率为1/m。举个例子，对于“性别”特征，将male哈希为一个int64，female哈希为另一个int64，很难发生碰撞；但如果你试图使用mod2将其压缩，如果你的算法哈希出的这两个int64奇偶性相同，则会导致特征失效。在你有很多feature需要哈希而又不清楚hashing算法细节的情况下，这在概率意义上是很容易发生的
  - 这里的mod2是极端举例，其实m的取值小于原始维度的情况下都有一定概率造成冲突
因此我们会更倾向于所谓的embedding算法
- 例如将70万维的userid通过weight embedding到32维的连续值特征上（不同于传统hashing的低维离散值特征）。这意味着训练过程更加复杂（有更多的weight需要optimize）；但对于预测过程，其特征性能十分良好且时间复杂度得以降低。同时，由于连续值特征空间的表达能力大幅高于离散值特征空间，整个模型的表达能力并不会明显下降，也基本不会发生离散hashing的碰撞问题
- 当然，如果是FM这类倾向于接受离散值的模型，手工serializing+精心设计的hashing是较好的选择
优点：
- 训练和预测的时间复杂度大幅降低；
- 数据的一致性强，不存在同一个特征今天编码成这个、明天编码成那个的情况，便于跟踪单特征效果；
- 对new feature可以直接编码并加入训练，无需等待编码表统计并反馈；
- 降低feature space大小，（精心设计可以）降低over-fitting的几率
缺点
- 在不清楚hashing function细节的情况下，容易导致特征碰撞失效，且难以排查；
- 难以通过hashing出的特征反推源特征；
- embedding会降低模型的可解释性。

Joe Zhou

Stay Hungry. Stay Foolish.

GitHub E-Mail