Active Learning Supported Iterative Combinatorial Auctions
摘要
In deep learning-based iterative combinatorial auctions (DL-ICA), bidders do not have to report valuations for all bundles up front. Instead, DL-ICA iteratively asks bidders to report their value for specific bundles and determines the allocation of the items using a winner determination problem. In the process, bidder profiles are modeled using neural networks. However, due to the relatively small number of reported bundles, DL-ICA may not always realize the optimal winner allocation, resulting in reduced economic efficiency. In this work, we improve the economic efficiency, i.e., the social welfare, of DL-ICA by optimizing the underlying machine learning-based elicitation algorithm. To this end, we introduce two different active learning-based initial sampling strategies, called GALI and GALO. GALI ensures an optimal coverage of the entire bundle space during sampling, while GALO tries to find bundles with a high diversity of the bidders’ value estimated by the underlying neural network. By doing so, our work extends the scope of active learning, which was previously constrained to small pool sizes. We show how linear programs can be used for active learning to handle pool sizes larger than \(10^{30}\) samples. We prove the correctness of our approach theoretically and verify its performance experimentally.