Deep Learning-powered Iterative Combinatorial Auctions

07/12/2019
by   Jakob Weissteiner, et al.
0

In this paper, we study the design of deep learning-powered iterative combinatorial auctions (ICAs). We build on the work by Brero et al. (2018), who have successfully integrated support vector regression (SVR) into the preference elicitation algorithm of an ICA. However, their SVR-based approach also has its limitations because the algorithm requires solving the auction's winner determination problem (WDP) given predicted value functions. With expressive kernels (like gaussian, exponential or high degree polynomial kernels), the WDP cannot be solved for large domains. While linear or low-degree polynomial kernels have better computational scalability, these kernels have limited expressiveness. In this work, we address these shortcomings by using deep neural networks (DNNs) instead of SVRs for learning bidders' valuation functions. Our main contribution is to show that the resulting maximization step of DNNs consisting of rectified linear units as activation functions can always be reformulated into a mixed integer linear program (MILP). Preliminary simulation results indicate that even two-hidden-layer-fully-connected DNNs with a small number of hidden units lead to higher economic efficiency than kernelized SVRs with a comparable or even smaller runtime.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset