Adaptive Pricing in Combinatorial Auctions

• 成果类型: Article; Early Access
• 署名作者: Lahaie, Sebastien; Lubin, Benjamin
• 署名单位: Alphabet Inc.; Google Incorporated; Boston University
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.2024.4993
• 发表日期: 2025
• 关键词: Combinatorial auctions; adaptive pricing; polynomial prices; Market clearing

摘要

We introduce the first adaptively priced iterative combinatorial auction design, which gradually extends price expressiveness as the rounds progress. This mechanism achieves both high efficiency and fast convergence across a wide range of valuation domains. We implement our auction design using polynomial prices, show how to detect when the current price structure is insufficient to clear the market, and show how to correctly expand the polynomial structure to guarantee progress. An experimental evaluation confirms that our auction is competitive with bundle-price auctions in domains where these excel, namely multiminded valuations, but also performs well in domains favorable to linear prices, such as valuations with pairwise synergy.