Automated Deterministic Auction Design with Objective Decomposition
It addresses the challenge of designing high-revenue, incentive-compatible deterministic auctions for multi-item scenarios, offering a scalable solution with incremental improvements over existing methods.
This paper tackles the automated design of deterministic auctions, which are more practical than randomized ones, by introducing OD-VVCA, an objective decomposition approach for Virtual Valuations Combinatorial Auctions. It achieves high revenue in multi-item auctions, outperforming baselines in large-scale settings.
Identifying high-revenue mechanisms that are both dominant strategy incentive compatible (DSIC) and individually rational (IR) is a fundamental challenge in auction design. While theoretical approaches have encountered bottlenecks in multi-item auctions, there has been much empirical progress in automated designing such mechanisms using machine learning. However, existing research primarily focuses on randomized auctions, with less attention given to the more practical deterministic auctions. Therefore, this paper investigates the automated design of deterministic auctions and introduces OD-VVCA, an objective decomposition approach for automated designing Virtual Valuations Combinatorial Auctions (VVCAs). Firstly, we restrict our mechanism to deterministic VVCAs, which are inherently DSIC and IR. Afterward, we utilize a parallelizable dynamic programming algorithm to compute the allocation and revenue outcomes of a VVCA efficiently. We then decompose the revenue objective function into continuous and piecewise constant discontinuous components, optimizing each using distinct methods. Extensive experiments show that OD-VVCA achieves high revenue in multi-item auctions, especially in large-scale settings where it outperforms both randomized and deterministic baselines, indicating its efficacy and scalability.