Automated Deterministic Auction Design with Objective Decomposition
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916331776901120 |
|---|---|
| author | Duan, Zhijian Sun, Haoran Xia, Yichong Wang, Siqiang Zhang, Zhilin Yu, Chuan Xu, Jian Zheng, Bo Deng, Xiaotie |
| author_facet | Duan, Zhijian Sun, Haoran Xia, Yichong Wang, Siqiang Zhang, Zhilin Yu, Chuan Xu, Jian Zheng, Bo Deng, Xiaotie |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_11904 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Automated Deterministic Auction Design with Objective Decomposition Duan, Zhijian Sun, Haoran Xia, Yichong Wang, Siqiang Zhang, Zhilin Yu, Chuan Xu, Jian Zheng, Bo Deng, Xiaotie Computer Science and Game Theory Machine Learning 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. |
| title | Automated Deterministic Auction Design with Objective Decomposition |
| topic | Computer Science and Game Theory Machine Learning |
| url | https://arxiv.org/abs/2402.11904 |