Fast Iterative Combinatorial Auctions via Deep Reinforcement Learning

📄 arXiv: 2610.30667v1 📥 PDF

作者: Luis F. Paul Tosta, Quinn Arnold, Gianluca Brero

分类: cs.GT, cs.LG

发布日期: 2026-10-22

💡 一句话要点

提出FastCombo以解决迭代组合拍卖中的价格发现问题

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 深度强化学习 组合拍卖 价格发现 在线优化 马尔可夫决策过程 神经网络 拍卖效率 经济调度

📋 核心要点

  1. 现有的迭代组合拍卖方法在拍卖轮次上成本高，尤其是贝叶斯定价方法依赖于单步目标，导致效率低下。
  2. FastCombo通过离线学习价格策略，利用强化学习优化拍卖过程，旨在减少清算所需的期望轮次。
  3. 实验表明，FastCombo在一项实验中将期望轮次从1.85降低至1.65，并在多个领域中显著提高了在线价格选择效率。

📝 摘要（中文）

迭代组合拍卖广泛应用于频谱分配、运输和工业采购，但每轮拍卖的成本较高。本文提出FastCombo，一种基于深度强化学习的顺序价格发现方法。与基于贝叶斯定价的基准相比，FastCombo显著减少了拍卖轮次，并通过离线学习价格策略，利用单次神经网络前向传播进行在线价格更新。实验结果表明，FastCombo在多个领域中实现了竞争性的清算，同时将在线价格选择时间减少了约300-900倍。

🔬 方法详解

问题定义：本文旨在解决迭代组合拍卖中价格发现的高成本问题。现有方法如贝叶斯定价虽然有效，但依赖于单步优化，导致拍卖轮次过多，效率低下。

核心思路：FastCombo的核心思路是通过深度强化学习离线学习价格策略，优化拍卖过程中的决策。该方法通过赋予查询未来决策的信用，减少在线推理的复杂性。

技术框架：FastCombo将单一目标的期望轮次最小化问题建模为部分可观察的马尔可夫决策过程，训练一个递归的竞标者-物品图策略。整体流程包括离线学习阶段和在线价格更新阶段，后者通过单次神经网络前向传播实现。

关键创新：FastCombo的主要创新在于其离线学习的价格策略和高效的在线更新机制。这与传统方法的逐步优化形成鲜明对比，显著提高了拍卖效率。

关键设计：在设计中，FastCombo使用了递归神经网络结构，优化了损失函数以适应拍卖策略的学习，并通过完整的拍卖轨迹进行训练，确保策略的有效性。

📊 实验亮点

实验结果显示，FastCombo在一项实验中将期望轮次从1.85降低至1.65，相较于传统贝叶斯方法，在线价格选择时间减少了约300-900倍，展现了其在效率上的显著提升。

🎯 应用场景

FastCombo的研究成果在频谱分配、运输调度和工业采购等多个领域具有广泛的应用潜力。通过提高拍卖效率和降低成本，该方法能够为相关行业带来显著的经济效益，并推动智能拍卖系统的发展。

📄 摘要（原文）

Iterative combinatorial auctions are used in spectrum allocation, transportation, and industrial procurement, but rounds are costly. We introduce FastCombo, a deep reinforcement learning approach to sequential price discovery. Bayesian pricing has sharply reduced auction rounds even against subgradient benchmarks tuned with hindsight for each instance, but relies on a one-step objective and repeated online inference and optimization. We prove that greedily maximizing immediate clearing probability can require arbitrarily more rounds in expectation than an informative policy, even with the true valuation distribution known. FastCombo learns price policies offline, assigning credit to queries for the future decisions they enable and producing each online price update with a single neural-network forward pass. We formulate the objective of minimizing expected rounds to clearing in single-minded auctions as a partially observable Markov decision process and train a recurrent bidder-item graph policy over complete auction trajectories. In a one-item experiment, all five trained policies learn an informative opening, reducing expected rounds from 1.85 to 1.65 relative to the tested Bayesian one-step rule. Across four domains from the Combinatorial Auction Test Suite, FastCombo achieves competitive clearing while reducing measured online price-selection time per auction by a factor of roughly 300-900 relative to the standard Bayesian baseline. These results demonstrate the value of learning sequential price policies for both information acquisition and online computational efficiency.