Optimizing resource allocation: An active learning approach to iterative combinatorial auctions

In deep learning-based iterative combinatorial auctions (DL-ICA), bidders are not required to report valuations for all bundles upfront. Instead, DL-ICA iteratively requests bidders to report their values for specific bundles and determines item allocation using a winner determination problem, with bidder profiles modeled by neural networks. However, due to the limited number of reported bundles, DL-ICA may not always achieve optimal winner allocation, leading to reduced economic efficiency. In this work, we enhance the economic efficiency, specifically the social welfare, of DL-ICA by optimizing the underlying machine learning-based elicitation algorithm. We introduce two novel active learning-based initial sampling strategies: GALI and GALO. GALI ensures optimal coverage of the entire bundle space during sampling, while GALO identifies bundles with high diversity in bidders' estimated values as determined by the neural network. This approach extends the application of active learning beyond small pool sizes. We demonstrate how linear programs can be utilized for active learning to manage pool sizes exceeding 1030 samples. Our approach is theoretically validated and experimentally verified, showcasing significant improvements in performance.

Authors

• Benjamin Estermann
• Stefan Kramer Johannes Gutenberg-Universität Mainz
• Roger Wattenhofer ETH Zurich
• Kanye Ye Wang University of Macau

Keywords

• Active learning
• Combinatorial auctions
• Deep learning