Saviez-vous que lorsque vous regardez des films, partagez des photos ou même lisez cet article via votre smartphone, vous utilisiez une denrée très chère et convoitée nommée « fréquence » ? Saviez-vous que cette ressource limitée était vendue sous la forme de bouquets lors d’enchères, comme un Picasso ?
Depuis plus de 20 ans, les opérateurs s’arrachent les fréquences de téléphonie mobile au cours d’enchères sanglantes – la dernière grande en date étant les enchères 5G en 2020, et celles pour la 6G devraient avoir lieu vers 2030.
En effet, de la même manière qu’un peintre a besoin de plusieurs couleurs afin de dresser ses plus belles toiles, un opérateur mobile a besoin d’une grande palette de fréquences afin d’offrir une bonne qualité de service.
Ces bandes de fréquences sont majoritairement attribuées sous la forme de licences à travers des enchères, véritable champ de bataille de la capacité, du débit et de la couverture mobile. Au vu des sommes d’argent mises en jeu – Orange a déboursé 854 millions d’euros pour l’enchère France 5G – ainsi que les implications stratégiques, il est fondamental pour un opérateur mobile d’établir une bonne stratégie d’enchérissement.
De nos jours, ces stratégies se fondent essentiellement sur l’expérience humaine des opérateurs. En s’armant des nouvelles méthodes de l’intelligence artificielle, notamment de l’apprentissage par renforcement, certains opérateurs tentent de calculer la stratégie optimale et ainsi remporter la bataille des fréquences.
Ces 20 dernières années, le mécanisme d’enchère privilégié pour la vente de ces fréquences est le simultaneous ascending auction (SAA). Il a par exemple été utilisé pour l’allocation des fréquences 5G en Allemagne, au Portugal, en Italie ou au Royaume-Uni, et on pense qu’il jouera un rôle central dans l’attribution des fréquences 6G.
Ses deux créateurs, Robert Wilson et Paul Milgrom, ont reçu le prix de sciences économiques de la Banque de Suède en mémoire d’Alfred Nobel en 2020, notamment pour les récompenser de leurs travaux sur le SAA.
Dans la suite de cet article, nous vous expliquons les règles du SAA, ses complexités stratégiques… et la solution que nous proposons pour calculer une bonne stratégie d’enchérissement.
Les règles d’une simultaneous ascending auction
Ce qui fait sans doute la grande popularité du SAA est la relative simplicité de ses règles. Elle étend l’enchère anglaise à la vente multiobjets.
Majoritairement représentée dans les films pour la vente d’œuvres d’art, par exemple pour des tableaux, l’enchère anglaise permet la vente d’un seul objet. Les participants soumettent des offres croissantes au cours de l’enchère correspondant au prix auquel ils sont prêts à payer le tableau. À la fin de l’enchère, le tableau est vendu au prix de la dernière offre (donc la plus élevée) à celui l’ayant soumise.
Le SAA correspond à la vente simultanée de plusieurs objets via des enchères anglaises séparées et concurrentes (une enchère anglaise pour chaque objet). Le SAA se déroule en plusieurs tours. Chaque tour, les participants soumettent leurs offres simultanément sur chaque objet. À la fin de chaque tour, le gagnant temporaire de chaque objet est annoncé. Si plusieurs participants soumettent simultanément la même meilleure offre, le gagnant temporaire de l’objet est tiré aléatoirement parmi eux. Toutes les enchères anglaises se clôturent en même temps, lorsqu’aucune nouvelle offre n’a été soumise pendant un tour.
Une variante de ce mécanisme d’enchères SAA s’appelle simultaneous clock auction, qui a souvent été utilisé pour attribuer les marchés de l’électricité et les quotas d’émissions de CO₂, entre autres.
Le problème d’exposition
Malgré la simplicité de ses règles, plusieurs complexités stratégiques émanent du SAA. La plus problématique est le problème d’exposition.
Illustrons ce problème par un exemple simple. Supposons une vente aux enchères de tubes de peinture. J’aimerais pouvoir peindre un ciel bleu avec des nuages. Il faut alors que j’acquière deux tubes : un de couleur bleue et l’autre de couleur blanche. L’enchère se passe mal et je finis par n’acquérir qu’un tube de couleur blanche mais pas de peinture bleue car les tubes étaient plus chers qu’estimés. J’aurais donc dépensé une grande partie de mes économies pour peindre uniquement en blanc sur une toile blanche, ce qui me limite grandement artistiquement. Cette situation où l’on se retrouve à payer trop cher certaines couleurs car on espérait remporter d’autres couleurs complémentaires correspond au problème d’exposition.
[Plus de 85 000 lecteurs font confiance aux newsletters de The Conversation pour mieux comprendre les grands enjeux du monde. Abonnez-vous aujourd’hui]
Similairement aux couleurs, les bandes de fréquences admettent aussi des complémentarités. Par exemple, les fréquences basses peuvent transmettre de l’information sur de plus grandes distances et traverser des obstacles denses plus facilement que les fréquences hautes. Cependant, elles offrent un débit plus faible. Afin d’offrir une bonne qualité de service, il est donc essentiel pour un opérateur d’avoir ces deux bandes de fréquences.
Ce risque d’exposition est d’autant plus inquiétant pour les opérateurs qu’une enchère de spectre (comme ce fut le cas des enchères 5G en France) se déroule généralement qu’une fois, ne laissant pas de place à l’erreur.
Modéliser ce processus d’enchères SAA grâce aux arbres de décision
Afin de calculer la meilleure stratégie d’enchérissement possible, nous modélisons le SAA sous la forme d’un arbre de décision.
Cet arbre comporte deux types de nœuds : les « nœuds de décisions » et les « nœuds chances ». À chaque nœud de décision, un participant doit soumettre une unique offre parmi plusieurs possibles, chacune représentée par une arête sortante.
Afin de conserver l’aspect simultané de l’enchère au sein de l’arbre de décision, il ne faut pas qu’un participant puisse connaître les arêtes déjà sélectionnées dans l’arbre (les offres déjà soumises par les concurrents) au cours d’un même tour avant la fin de celui-ci. À la fin d’un tour, les offres de tous les participants sont généralement dévoilées. L’information dont dispose un participant doit donc rester la même au long d’un tour d’enchère, et évolue à la fin du tour.
Pour modéliser cette incertitude, on utilise la notion d’ensemble d’information. Un tel ensemble regroupe des états potentiels dans lesquels se trouve l’enchère du point de vue d’un participant. Les « nœuds chance », quant à eux, représentent les tirages aléatoires en cas d’égalité des plus grandes offres soumises. Nous représentons ci-dessous un exemple d’arbre de décision entre trois opérateurs français.
Calcul de la stratégie d’enchérissement par l’IA
L’idéal serait de pouvoir explorer l’intégralité de l’arbre de décision. Cependant, cela est impossible car il est beaucoup trop grand. Par exemple, l’arbre de décision correspondant à l’enchère 5G en Italie en 2018 comporte au moins 1035 nœuds et 102470 branches. Cela est énorme si on compare au nombre d’atomes dans l’univers qui est « juste » de 1080 !
Pour pallier ce problème, on ne va explorer qu’une petite partie de l’arbre de décision : cette partie est appelée « arbre de recherche ». On la construit itérativement à travers une méthode appelée Monte Carlo Tree Search ou MCTS pour faire court – c’est notamment sur cette méthode que repose le fameux algorithme AlphaGo qui a battu Lee Sedol, le meilleur joueur du monde de Go, en 2016.
Le MCTS est un algorithme d’apprentissage par renforcement – une des branches principales de l’IA et une forme d’apprentissage qui est incontournable pour l’apprentissage dans le domaine mathématique des jeux. Elle combine les méthodes standards de Monte-Carlo avec les méthodes traditionnelles de recherche dans les jeux avec des adversaires.
La première méthode permet d’estimer différents indicateurs de performance (tel que le gain espéré, c’est-à-dire la valeur des licences obtenues moins le prix final estimé de celles-ci) sur le placement de chaque offre par un opérateur à un nœud de décision spécifique de l’arbre de recherche. Ces indicateurs sont calculés grâce à de nombreuses simulations d’enchères (des enchères SAA sont jouées en simulant un certain comportement pour chaque opérateur) et des méthodes statistiques.
La seconde méthode permet d’élargir l’arbre de recherche en se focalisant sur les parties de l’arbre de jeu qui sont pertinentes par rapport à l’estimation faite des différents indicateurs de performance (par exemple, se concentrer sur les parties de l’arbre de jeu qui maximise les gains des différents opérateurs). Ceci permet de construire un arbre de recherche qui explore essentiellement les parties prometteuses de l’arbre de jeu.
Après quelques millions d’itérations, nous sélectionnons l’offre qui maximise un indicateur intégrant à la fois le gain espéré et les risques d’exposition encourus. La solution trouvée ainsi n’est pas forcément la meilleure solution, mais une bonne solution.
En fait, pour ce type de problèmes de la théorie des jeux, il est très difficile de définir mathématiquement ce qu’est la « meilleure » solution !
Notre algorithme a obtenu des résultats prometteurs : il permet en effet à un opérateur d’obtenir un plus grand gain tout en prenant moins de risques que les algorithmes existants. L’article est en cours de revue par les pairs.
Autrement dit, notre algorithme suggère de ne pas nécessairement enchérir sur la plus belle palette de fréquences mais sur celle, compte tenu de l’estimation des préférences adverses, qu’on pourrait avoir au meilleur prix.
Cet article est publié en partenariat avec le laboratoire d’Orange Innovation.