在重复采购拍卖中,平台通过学习上下文信息优化选择供应商,兼顾效率与激励兼容。
Contextual Procurement Auctions with Bandit Learning
- 设计独立于出价的探索-承诺机制,确保策略最优且可实现真实报价。
- 提出冻结支付UCB算法,在保证近似真实激励下达到最优福利遗憾率。
- 适用于需要平衡学习效率与投标人激励的动态市场设计场景。
我们研究生产者具有私有成本的重复采购拍卖,平台需学习根据上下文选择各生产者的价值。以福利遗憾衡量性能:相对于完全信息下的最优规则,累计总盈余损失。自然的UCB分配规则在诚实出价下可达到$ ilde{O}( oot{2}{ngT})$的福利遗憾,但其自适应的、依赖出价的学习路径本身无法保证诚实性。为获得精确激励,我们首先设计一种出价无关的探索-承诺机制,采用经验阈值支付,该机制是主导策略真实,且遗憾率为$ ilde{O}((ng)^{1/3}T^{2/3})$。随后引入冻结支付UCB,从初始的出价无关探索中估计支付,但继续使用UCB进行分配学习。在满足真报价路径裕度条件下,该算法近似真实,每轮平均偏离收益为$ ilde{O}(T^{-1/4})$(固定$n, g$)。在诚实出价下,其福利遗憾仍为$ ilde{O}( oot{2}{ngT})$,匹配标准UCB速率。下界表明此遗憾-激励权衡在冻结关键支付类中紧致。
原文摘要 · Abstract (English)
We study repeated procurement auctions in which producers have private costs and the platform must learn the context-dependent value of selecting each producer. We evaluate performance by welfare regret: the cumulative loss in total surplus relative to the full-information efficient rule that knows the context-dependent values and true producer costs. The natural UCB allocation rule achieves $\widetilde O(\sqrt{ngT})$ welfare regret under truthful bids, but its adaptive, bid-dependent learning path does not by itself ensure truthfulness. To obtain exact incentives, we first design a bid-independent explore-then-commit mechanism with empirical threshold payments; it is dominant-strategy truthful and has $\widetilde O((ng)^{1/3}T^{2/3})$ regret. We then introduce frozen-payment UCB, which estimates payments from initial bid-independent exploration but continues allocation learning by UCB. Under a truthful-path margin condition, the frozen-payment UCB is approximately truthful with an average per-round deviation gain $\widetilde O(T^{-1/4})$ for fixed $n$, $g$. Under truthful bidding, it achieves $\widetilde O(\sqrt{ngT})$ welfare regret, matching the UCB rate. A lower bound shows that this regret-incentive tradeoff is tight within the frozen critical-payment class.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。