Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2407.11715 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929422195490816 |
|---|---|
| author | Pacaud, Alexandre Bechler, Aurélien Coupechoux, Marceau |
| author_facet | Pacaud, Alexandre Bechler, Aurélien Coupechoux, Marceau |
| contents | For decades, Simultaneous Ascending Auction (SAA) has been the most widely used mechanism for spectrum auctions, and it has recently gained popularity for allocating 5G licenses in many countries. Despite its relatively simple rules, SAA introduces a complex strategic game with an unknown optimal bidding strategy. Given the high stakes involved, with billions of euros sometimes on the line, developing an efficient bidding strategy is of utmost importance. In this work, we extend our previous method, a Simultaneous Move Monte-Carlo Tree Search (SM-MCTS) based algorithm named $SMS^α$ to incomplete information framework. For this purpose, we compare three determinization approaches which allow us to rely on complete information SM-MCTS. This algorithm addresses, in incomplete framework, the four key strategic issues of SAA: the exposure problem, the own price effect, budget constraints, and the eligibility management problem. Through extensive numerical experiments on instances of realistic size with an uncertain framework, we show that $SMS^α$ largely outperforms state-of-the-art algorithms by achieving higher expected utility while taking less risks, no matter which determinization method is chosen. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_11715 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Bidding efficiently in Simultaneous Ascending Auctions with incomplete information using Monte Carlo Tree Search and determinization Pacaud, Alexandre Bechler, Aurélien Coupechoux, Marceau Computer Science and Game Theory For decades, Simultaneous Ascending Auction (SAA) has been the most widely used mechanism for spectrum auctions, and it has recently gained popularity for allocating 5G licenses in many countries. Despite its relatively simple rules, SAA introduces a complex strategic game with an unknown optimal bidding strategy. Given the high stakes involved, with billions of euros sometimes on the line, developing an efficient bidding strategy is of utmost importance. In this work, we extend our previous method, a Simultaneous Move Monte-Carlo Tree Search (SM-MCTS) based algorithm named $SMS^α$ to incomplete information framework. For this purpose, we compare three determinization approaches which allow us to rely on complete information SM-MCTS. This algorithm addresses, in incomplete framework, the four key strategic issues of SAA: the exposure problem, the own price effect, budget constraints, and the eligibility management problem. Through extensive numerical experiments on instances of realistic size with an uncertain framework, we show that $SMS^α$ largely outperforms state-of-the-art algorithms by achieving higher expected utility while taking less risks, no matter which determinization method is chosen. |
| title | Bidding efficiently in Simultaneous Ascending Auctions with incomplete information using Monte Carlo Tree Search and determinization |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2407.11715 |