Soutenance mémoire
La théorie des jeux naît en tant que discipline au milieu du XXme siècle. On attribue souvent celle-ci à la publication, en 1944, de l’ouvrage « Theory of Games and Economic Behavior » du mathématicien John Von Neumann et de l’économiste Oskar Morgenstern [Neumann et Morgenstern, 1944], mais une des premières publications dans le domaine date de 1838 [Cournot, 1838]. Dans cet ouvrage, intitulé « Recherches sur les principes mathématiques de la théorie des richesses », Antoine-Augustin Cournot aborde, dans son analyse du duopole (l’étude d’un marché opposant deux entreprises), un concept de solution qui est une version restreinte de l’équilibre de Nash tel qu’il sera formulé par John Forbes Nash dans les années 1950 [Nash, 1950, Nash, 1951].
En 1945, l’US Airforce crée la RAND Corporation (acronyme de « Research and Development ») afin de comprendre les enjeux stratégiques du contexte militaire de l’époque, c’est-à-dire la guerre froide et les conflits nucléaires. Ce groupe a, dès le départ, réuni des chercheurs de toutes disciplines et rassemblé un grand nombre de personnalités scientifiques, notamment John Von Neumann, John Forbes Nash ou Lloyd Shapley. Les développements de la théorie des jeux au cours de la période 1945-1958 ont été tout à fait considérables, les enjeux n’étant rien de moins que d’éviter une escalade nucléaire conduisant à la destruction de la planète. L’équilibre de la terreur (ou destruction mutuelle assurée), élaborée durant cette époque de guerre froide, affirme que l’utilisation à grande échelle de l’arme nucléaire par l’Union soviétique ou les États-Unis provoquerait à coup sûr la destruction des deux camps. En effet, le premier à lancer l’attaque afin de détruire l’autre est en quelque sorte assuré d’être détruit à son tour, annulant complètement l’intérêt d’une telle attaque.
La théorie des jeux est un outil destiné à la compréhension de systèmes dans lesquels des individus agissent dans leur propre intérêt. Un jeu est une situation où ces individus doivent faire un choix parmi un certain nombre d’actions possibles, le tout en fonction de règles du jeu définies à l’avance. Le résultat de ces choix, effectués par les différents individus, mène à l’issue du jeu à laquelle est associée une récompense pour chacun des participants. Dans de tels systèmes, le résultat d’une action ne dépend pas seulement de la décision de l’individu l’ayant effectuée, mais également de celles prises par les autres. La théorie des jeux permet d’analyser le comportement d’un individu qui doit prendre une décision, en tenant compte des décisions que peuvent prendre les autres individus de manière plus ou moins indépendante. Par exemple, pour un automobiliste devant décider entre deux chemins pour se rendre de son domicile au travail, ce choix de chemin dépendra des décisions prises par les autres automobilistes empruntant le même itinéraire.
Existence et complexité des équilibres dans le jeu de placement
Introduction à la théorie des jeux
La théorie algorithmique des jeux [Nisan et al., 2007] est intéressée par la compréhension de l’ensemble du système lorsque celui-ci peut converger vers des situations rationnelles, appelées équilibres de Nash. L’équilibre de Nash, introduit en 1950 [Nash, 1950], est une notion centrale de solution pour les jeux stratégiques. La théorie algorithmique des jeux s’intéresse à la manière d’obtenir ce type d’équilibres ainsi qu’à la complexité de leur calcul. Cette théorie s’est principalement concentrée sur la caractérisation des équilibres dans des classes particulières de jeux [Rosenthal, 1973], la qualité des équilibres [Koutsoupias et Papadimitriou, 1999], certains algorithmes distribués convergeant vers des équilibres [Berenbrink et al., 2012].
Les différents contextes de jeux
La théorie des jeux permet d’analyser l’interaction d’entités rationnelles, appelées agents ou joueurs (un être humain, un animal, une entreprise, etc.), poursuivant des buts qui leur sont propres. Dans une situation d’interaction entre différents joueurs, nous pouvons dégager les propriétés suivantes, qui donneront lieu à des modèles différents :
• la relation existante entre les joueurs (possibilité d’établir des coalitions, jeu coopératif ou non coopératif ) ;
• le déroulement temporel du jeu (séquentiel ou simultané) ;
• les informations dont disposent les joueurs (information complète ou incomplète, parfaite ou imparfaite).
Les relations entre les joueurs
Il existe des jeux dits, jeux coopératifs, où l’on s’intéresse aux coalitions (aussi appelées alliances) que les joueurs peuvent former pour coordonner leurs actions dans un but commun. Le problème de ce type de jeux réside dans la répartition de la récompense du jeu au sein de la coalition [Shapley, 1953] et la tendance des joueurs à vouloir la quitter. En effet, il est rare que la coordination des actions des joueurs implique de meilleures récompenses pour l’ensemble des joueurs de la coalition. Les jeux coopératifs impliquent au contraire une part de sacrifice de l’intérêt propre d’un ou plusieurs joueurs au profit d’un bien-être commun, jugé supérieur. Nous ne développerons pas ce type de jeux, ce document se concentrant sur des jeux non coopératifs.
Par opposition aux jeux coopératifs, les jeux où aucune alliance n’est possible sont appelés jeux non coopératifs. Dans le cas d’un jeu non coopératif, les joueurs sont en concurrence les uns avec les autres, comme c’est le cas pour des jeux à deux joueurs tels que les échecs, pierre papier ciseau, etc., ou des jeux à plusieurs joueurs comme le poker ou un automobiliste dont le temps de trajet dépend du trafic routier, c’est-à-dire des autres automobilistes/joueurs. Le bien-être d’un joueur dépend alors des choix de ses concurrents. Attention jeu non coopératif ne veut pas dire que les joueurs ont des buts antagonistes, par exemple les automobilistes n’ont pas pour but de nuire aux autres, en revanche des joueurs de poker ou d’échec ont tout intérêt à conduire leur adversaire à la défaite. De plus, il ne faut pas automatiquement associer un jeu où les communications entre les joueurs sont possibles à un jeu coopératif, la communication n’implique pas forcément la possibilité de créer des coalitions.
Le déroulement du jeu
Notons dans un premier temps qu’un jeu peut être joué une seule ou plusieurs fois. Dans le premier cas il s’agit d’un jeu dit statique, dans le second nous parlons de jeu répété. Pour un jeu répété, nous avons alors un même jeu (même nombre de joueurs, mêmes ensembles d’actions, mêmes fonctions de récompense) répété à chaque étape. Le jeu peut se dérouler de manière simultanée ou séquentielle. Dans un jeu simultané, aussi appelé jeu stratégique, les joueurs choisissent leur action à effectuer en même temps que chacun des autres joueurs une fois pour toutes au début du jeu (ou à chaque début de tour de jeu dans le cas d’un jeu répété) et perçoivent les résultats du jeu en même temps. Au contraire, si un jeu implique des choix successifs de la part des joueurs nous sommes dans le cas d’un jeu séquentiel.
Les informations connues des joueurs
Quel que soit le type d’environnement auquel un joueur fait face, le jeu puisse être
• à information complète : le joueur connaît les règles du jeu, et tout le déroulement du jeu jusqu’à sa prise de décision ;
• à information incomplète (ou partielle) : un ou plusieurs de ces éléments est inconnu du joueur.
De plus, un jeu est dit à information parfaite lorsque chaque joueur a une connaissance de tout l’historique du jeu, des actions passées des autres joueurs et des récompenses associées.
|
Table des matières
Introduction
I Existence et complexité des équilibres dans le jeu de placement
1 Introduction à la théorie des jeux
1.1 Les différents contextes de jeux
1.2 Formalisation du concept de jeu
1.2.1 Jeux sous forme normale
1.2.2 Jeux sous forme extensive ou arbres de jeux
1.2.3 Équilibres de Nash purs et mixtes
1.3 Les jeux de potentiel et de congestion
1.3.1 Jeux de potentiel
1.3.2 Jeux de congestion
1.3.3 Un cas particulier de jeux de congestion : l’ordonnancement
1.4 Calcul d’équilibres
1.4.1 Classes de complexité pour les jeux de congestion
1.5 Conclusion
2 Jeu de placement
2.1 Le contexte général du jeu de placement
2.1.1 Analogie avec l’ordonnancement classique
2.1.2 Équilibres dans le contexte atomique et non atomique
2.2 Cas d’étude
2.2.1 Jeu de placement sans restrictions (ou asymétrique)
2.2.2 Jeu de placement symétrique (di;j = dj;i)
2.2.3 Jeu de placement symétrique non pondéré (di;j = 1)
2.3 Index des notations et conclusion
3 Équilibres du jeu de placement
3.1 Existence d’équilibres de Nash
3.1.1 Existence d’équilibres dans le jeu de placement asymétrique
3.1.2 Équilibres de Nash dans le jeu de placement symétrique
3.2 Calcul des équilibres de Nash
3.3 Structure des équilibres de Nash
3.3.1 Équilibres dans des cas particuliers de jeu de placement symétrique
3.3.2 Équilibres dans le jeu symétrique non pondéré atomique
3.4 Conclusion
II Techniques d’apprentissage appliquées à des jeux de congestion et de potentiel
4 Techniques d’apprentissage d’équilibres
4.1 Dynamique de meilleure réponse
4.2 Dynamique de réplication
4.2.1 Notations et algorithme LRI
4.2.2 Propriétés de l’algorithme
4.3 Minimisation de regret et problème de bandits manchots
4.3.1 Regrets et minimisation
4.3.2 Problème de Multi-Armed Bandit (ou Bandits Manchots)
4.3.3 Algorithme de minimisation de regret : UCB
4.4 Conclusion
5 Max-Cut et coordination d’interférences inter cellules
5.1 Coupe maximale dans un graphe non pondéré
5.1.1 Recherche d’une coupe maximale locale
5.1.2 Coupe localement maximale dans un graphe complet
5.1.3 Coupe maximum locale dans des graphes généraux
5.1.4 Autres topologies de graphes et simulations
5.1.5 Lien avec l’interférence inter cellule
5.2 Coordination d’interférences inter cellules
5.2.1 Modélisation du système
5.2.2 Apprentissage distribué des équilibres de Nash purs
5.2.3 Convergence vers un équilibre de Nash pur de l’algorithme
5.2.4 Expérimentations
5.3 Conclusion
6 Minimisation de regret pour prédire la probabilité de violation de la qualité de service
6.1 Modèle de détection des échecs
6.1.1 Scénario de la négociation
6.1.2 Les échecs de SLA
6.2 Algorithme de sélection de l’offre du client
6.2.1 Adaptation du modèle de détection d’échec de SLA au MAB
6.2.2 Adaptation de la dynamique de réplication
6.3 Algorithme de sélection d’offres de QoS des NSPs
6.4 Résultats de simulations
6.4.1 Modèle des simulations
6.4.2 Résultats
6.5 Conclusion
Conclusion
