Bidding efficiently in Simultaneous Ascending Auctions using Monte Carlo Tree Search
Enchérir efficacement dans l'enchère ascendante simultanée en utilisant la recherche arborescente Monte Carlo
Résumé
Since its introduction in 1994 in the United States, the Simultaneous Ascending Auction (SAA) has become the privileged mechanism for spectrum auctions. As sometimes billions of euros are at stake in an SAA, and a mobile operator’s business plan highly depends on the auction outcome, establishing an efficient bidding strategy is crucial. Despite the importance of this problem, there is a lack of research dedicated to developing an efficient bidding strategy for the SAA. The intrinsic complexity of the SAA makes its analysis very challenging for auction theory and exact game resolution methods. Additionally, the mechanism introduces strategical issues such as the exposure problem, adding an extra layer of complexity to its study.This thesis proposes the use of Monte Carlo Tree Search (MCTS) to compute an efficient bidding strategy for the SAA. The six chapters of the thesis are structured as follows. The first chapter introduces spectrum auction mechanisms, highlighting their pros and cons. The second chapter details the bidding problem in the SAA, along with relevant related research.The third chapter provides a summary of adversarial search methods, with a specific focus on MCTS. Chapters four to six are dedicated to developing an efficient MCTS bidding strategy for the SAA. The fourth chapter considers a turn-based deterministic model of the SAA with perfect and complete information. Numerical experiments are only undertaken on small instances.The fifth chapter considers a n-player simultaneous move model of SAA with incomplete information. Extensive numerical experiments are undertaken on instances of realistic size. The sixth chapter extends the preceding game to incomplete information to introduce uncertainties. For each model, an algorithm that significantly outperforms state-of-the-art bidding strategies is proposed, notably by better tackling the exposure problem. Moreover, a final price prediction method is developed throughout the chapters, upon which each MCTS algorithm relies.
Depuis son introduction en 1994 aux Etats-Unis, l’enchère ascendante simultanée (SAA) est devenue le mécanisme privilégié pour les enchères du spectre licencié. Avec des investissements dépassant parfois le milliard d’euros, une stratégie d’enchérissement performante devient cruciale pour les opérateurs mobiles. Malgré son importance, il existe un manque de recherche dédiée à la création d’une stratégie d’enchérissement performante dans le cadre du SAA. La complexité intrinsèque du jeu associé à l’enchère SAA rend son analyse ardue pour la théorie des enchères et les méthodes exactes de résolution de jeux. De plus, ce mécanisme engendre des problèmes stratégiques tels que le problème d’exposition, ajoutant une couche de complexité supplémentaire à son étude. Cette thèse propose l’utilisation de la recherche arborescente de Monte Carlo (MCTS) pour calculer une stratégie d’enchérissement performante au sein du SAA. Les six chapitres de la thèse sont structurés comme suit. Le premier chapitre présente les mécanismes d’enchères du spectre licencié, soulignant leurs avantages et inconvénients. Le deuxième chapitre détaille le problème spécifique de l’enchérisseur dans le SAA, ainsi que certains travaux connexes. Le troisième chapitre propose une synthèse concise des méthodes traditionnelles de recherche dans les jeux avec des adversaires, en mettant particulièrement l’accent sur le MCTS. Les chapitres quatre à six sont dédiés à la création de l’algorithme MCTS pour calculer une stratégie performante. Le quatrième chapitre modélise l’enchère SAA comme un jeu au tour par tour à N-joueurs à information parfaite et complète, avec des expériences numériques sur des instances de petite taille. Le cinquième chapitre modélise l’enchère comme un jeu simultané à N-joueurs à information complète, avec des contraintes budgétaires et d’éligibilité, et les résultats sont obtenus sur des instances de taille réelle. Le sixième chapitre considère le jeu à information incomplète pour modéliser les incertitudes de la réalité. Pour chaque modèle, un algorithme surpassant largement ceux de la littérature est proposé, traitant notamment le problème d’exposition. De plus, une méthode de prédiction des prix finaux est développée tout au long des chapitres, sur laquelle chaque algorithme MCTS s’appuie.
Origine : Version validée par le jury (STAR)