研究带预算限制的多轮差别定价拍卖中如何优化出价策略。
Learning to Bid in Discriminatory Auctions with Budget Constraints
- 通过构建有向无环图，将出价问题转化为最短路径求解，实现高效学习。
- 在带预算约束下，达到与预算比例相关的次线性后悔，且不依赖上下文数量。
- 算法可扩展至大量或无限上下文场景，适合实际拍卖系统部署。
我们研究单个投标人参与多单位差别定价（按价支付）拍卖中的重复出价问题，每轮效用为价值减去α倍支付，其中α∈[0,1]为资本成本参数。投标人需在T轮内最大化累计效用，受总预算B限制。该问题挑战性高：动作空间随最大需求量M呈指数增长，且估值向量（上下文）随时间变化。通过分解各单元的效用，我们提出基于有向无环图最短路径的多项式时间学习算法，在完整信息与仅反馈收益的带货设置下均实现次线性后悔。在带货设置中，由于完全交叉学习机制——观察到实际上下文下的选择动作效用，即可推知该动作在所有反事实上下文下的效用——后悔率与上下文数量无关。当平均归一化每轮预算ρ = B/(MT) < 1时，我们设计了耦合的原-对偶算法：基于对偶调整边权的图方法进行原始更新，同时使用在线梯度下降更新对偶变量，实现ρ近似次线性后悔。最后，我们提供了每轮时间和空间复杂度与上下文数量无关的实现，支持在大规模甚至无限上下文空间下的可扩展性。
原文摘要 · Abstract (English)
We study repeated bidding in multi-unit discriminatory (pay-as-bid) auctions for a single bidder with per-round utility equal to value minus $α$ times payment, where $α\in[0,1]$ is a cost-of-capital parameter. The bidder aims to maximize cumulative utility over $T$ rounds subject to a total budget $B$. The problem is challenging even without budgets: the action space is exponential in $M$, the maximum demand of the bidder and the valuation vector (context) varies over time. Exploiting a decomposition of utility across units, we develop polynomial-time learning algorithms based on shortest paths in a directed acyclic graph, obtaining sublinear regret under both full-information and bandit feedback. In the bandit setting, the regret is independent of the number of contexts due to complete cross-learning: observing the utility of the chosen action under the realized context reveals the utility for the same action under all counterfactual contexts. With budget constraints, when the average normalized per-round budget $ρ=\frac{B}{MT}<1$, we design a coupled primal-dual algorithm in which the DAG-based procedure uses dual-adjusted edge weights for primal updates, while online gradient descent updates the dual variable, yielding $ρ$-approximate sublinear regret. Finally, we give implementations whose per-round time and space are independent of the number of contexts, enabling scalability to large or even infinite context spaces.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。