No-Regret Algorithms in non-Truthful Auctions with Budget and ROI Constraints

广告商越来越多地使用自动竞价来优化其在在线广告平台上的广告活动。自动竞价在各种约束条件下优化广告主的目标，例如平均投资回报率和预算约束。在本文中，我们研究了在平台运行任何混合的一价和二价拍卖时，设计在线自动竞价算法以在投资回报率和预算约束下优化价值的问题。 我们考虑以下随机设置：在每一轮中都有一个物品出售。在每一轮中，买家提交竞价，并运行拍卖以出售物品。我们关注一个买家，可能有预算和投资回报率的约束。我们假设买家的价值和最高竞争出价在每一轮中都是从某个未知（联合）分布中独立同分布地抽取的。我们设计了一种低遗憾竞价算法，满足买家的约束条件。我们的基准是最佳利普希茨函数将价值映射到出价所能实现的目标价值，这足以最好地响应许多不同的价值和最高竞争出价之间的相关结构。我们的主要结果是一种具有完全信息反馈的算法，保证与最佳利普希茨函数相比具有近似最优的 $\tilde O(\sqrt T)$ 遗憾。我们的结果适用于各种拍卖，尤其是任何一价和二价拍卖的混合（价格是第一和第二价格的凸组合）。此外，我们的结果适用于既追求价值最大化的买家，也适用于追求准线性效用最大化的买家。 我们还研究了强盗设置，在其中我们展示了一价拍卖的遗憾下限为 $\Omega(T^{2/3})$，展示了完全信息和强盗设置之间的巨大差异。当价值分布已知且独立于最高竞争出价时，我们还设计了一种具有 $\tilde O(T^{3/4})$ 遗憾的算法。

设计在线自动竞标算法以优化价值，同时满足ROI和预算约束，适用于混合一二价拍卖。

设计一种低遗憾出价算法，满足买家的约束条件，可以在全信息反馈下保证接近最优的表现。

该算法适用于混合一二价拍卖，并且对于价值最大化的买家和准线性效用最大化的买家都适用。在买家的价值和最高竞标价之间有多种不同的相关结构时，最优Lipschitz函数可以实现最佳响应。

与本文相关的研究包括其他在线竞标算法，以及拍卖理论和机器学习算法的应用研究。