Title: Combinatorial Auctions via Machine Learning-based Preference Elicitation
Abstract: Combinatorial auctions (CAs) are commonly used to allocate multiple items among bidders with complex valuations. Since the value space grows exponentially in the number of items, practical CAs can only elicit a small amount of information from the bidders. Prior work has shown that current designs often fail to elicit the most relevant values of the bidders, thus leading to inefficiencies. We address this problem by introducing a new elicitation paradigm that uses machine learning to identify which values to query from the bidders. Based on this elicitation paradigm, we design a new CA where payments are determined so that bidders’ incentives are aligned with allocative efficiency. We validate our design experimentally in several large-scale domains, and we show that it achieves high allocative efficiency even when only few values are elicited from the bidders. Lastly, we extend our approach to the case where bidders only report bounds on their values and show that high efficiency can still be achieved.
