Adaptive Pricing in Combinatorial Auctions

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.