为双买家联合广告拍卖设计低悔悟学习算法，兼顾激励相容与收益最大化。
Selling Joint Ads: A Regret Minimization Perspective
- 基于自适应离散化构造机制空间学习策略，解决大规模动作空间难题。
- 随机环境下实现 $O(T^{3/4})$ 悔悟界，平滑对抗下达 $O(T^{2/3})$
- 揭示两类设置下最优悔悟率下界为 $Ω(√T)$，填补理论空白
受在线零售启发，我们研究将一个物品（如广告位）出售给两个不可排除的买家（如商家与品牌）的问题。此场景刻画了商家与品牌协同出价以推广产品的情形，双方均从广告展示中获益。机制收集双方出价并决定是否分配及支付金额，由此引发复杂的激励相容约束，例如如何分配支付。本文从在线学习视角出发，寻求收益最大化的激励相容机制，面临重大技术挑战：动作空间（所有可能机制类）极大，且收益映射函数高度不规则，排除标准离散化方法。在随机设定下，设计高效学习算法，达到 $O(T^{3/4})$ 悔悟界；该方法基于机制空间的自适应离散化，非自适应方案无法实现亚线性悔悟。在对抗设定下，利用问题的非利普希茨性，证明任何学习算法都无法获得超过事后最优固定机制一半的收益。随后考虑 $σ$-平滑对抗者，构建高效算法，实现 $O(T^{2/3})$ 悔悟界，并基于对指数级专家的紧凑编码。最后证明，在随机与平滑设定下，任何学习算法的悔悟率下界均为 $Ω(√T)$，从而缩小了两类问题的极小极大悔悟率范围。
原文摘要 · Abstract (English)
Motivated by online retail, we consider the problem of selling one item (e.g., an ad slot) to two non-excludable buyers (say, a merchant and a brand). This problem captures, for example, situations where a merchant and a brand cooperatively bid in an auction to advertise a product, and both benefit from the ad being shown. A mechanism collects bids from the two and decides whether to allocate and which payments the two parties should make. This gives rise to intricate incentive compatibility constraints, e.g., on how to split payments between the two parties. We approach the problem of finding a revenue-maximizing incentive-compatible mechanism from an online learning perspective; this poses significant technical challenges. First, the action space (the class of all possible mechanisms) is huge; second, the function that maps mechanisms to revenue is highly irregular, ruling out standard discretization-based approaches. In the stochastic setting, we design an efficient learning algorithm achieving a regret bound of $O(T^{3/4})$. Our approach is based on an adaptive discretization scheme of the space of mechanisms, as any non-adaptive discretization fails to achieve sublinear regret. In the adversarial setting, we exploit the non-Lipschitzness of the problem to prove a strong negative result, namely that no learning algorithm can achieve more than half of the revenue of the best fixed mechanism in hindsight. We then consider the $σ$-smooth adversary; we construct an efficient learning algorithm that achieves a regret bound of $O(T^{2/3})$ and builds on a succinct encoding of exponentially many experts. Finally, we prove that no learning algorithm can achieve less than $Ω(\sqrt T)$ regret in both the stochastic and the smooth setting, thus narrowing the range where the minimax regret rates for these two problems lie.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。