Bidding Efficiently in Simultaneous Ascending Auctions With Incomplete Information Using Monte Carlo Tree Search and Determinization

In this article, we tackle the problem of designing an efficient bidding strategy for simultaneous ascending auctions (SAA). SAA is a well-known mechanism for allocating spectrum to mobile networks operators and has been used for example to allocate 5G licenses in many countries. Although the rules are relatively simple, there is no known optimal bidding strategy for SAA. In a previous work, we proposed a Simultaneous move Monte Carlo Tree Search-based algorithm named <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$SMS^{\alpha }$</tex-math></inline-formula> that we extend here to an incomplete information framework. We consider and compare three determinization approaches of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$SMS^{\alpha }$</tex-math></inline-formula>, and show how they are able to tackle four key strategic issues of SAA, namely, the exposure problem, the own price effect, the budget constraints and the eligibility management. Extensive numerical experiments on instances of realistic size and including an uncertain framework show that our extensions of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$SMS^{\alpha }$</tex-math></inline-formula> outperform state-of-the-art algorithms by achieving higher expected utility while taking less risks.