Théorie algorithmique des jeux
La théorie algorithmique des jeux ou théorie des jeux algorithmique[1] (en anglais, algorithmic game theory ou AGT) est un domaine entre les mathématiques, l'informatique théorique et l'économie. Plus précisément, ce domaine est une étude de certains aspects de l'économie et de la théorie des jeux d'un point de vue quantitatif et algorithmique.
Description et historique
L'émergence d'Internet a motivé l'étude des phénomènes de compétitions et de coopération sur de grands réseaux, et c'est l'origine de la théorie algorithmique des jeux[2]. Ce domaine est relativement récent et on peut situer son essor dans les années 2000[2].
Sujets
On peut citer quelques sous-domaines emblématiques de la théorie algorithmique des jeux.
MĂ©canismes d'incitation
La théorie des mécanismes d'incitation, ou Mechanism Design consiste à définir des mécanismes, c'est-à -dire des règles de jeux, pour assurer que des joueurs rationnels arrivent à un certain objectif. Un exemple concret est celui des enchères : les joueurs sont les enchérisseurs, la valeur que chacun associe au lot est privée et le but est de définir les règles de l'enchère en vue d'optimiser un objectif, par exemple le revenu du vendeur, l'équité, ou un indicateur de la valeur globale pour la société[2].
On peut par exemple citer l'enchère de Vickrey (ou enchère au second prix).
Efficacité des équilibres
Dans de nombreux jeux, on peut définir deux sortes d'objectifs, un objectif personnel, que chaque joueur essaye de maximiser et un objectif global comme un indicateur du bien commun. Une branche de la théorie algorithmique des jeux consiste à comparer la valeur de l'objectif global selon que les joueurs jouent pour optimiser leur objectif personnel ou qu'ils coopèrent pour maximiser l'objectif global. Plus précisément, on s’intéresse à des situations d'équilibre du jeux en version compétition, comme un équilibre de Nash, et à leur efficacité comparée à la valeur optimale.
On parle en particulier de prix de l'anarchie, notamment dans les contexte des réseaux.
Complexité du calcul des équilibres
Un concept fondamental dans les jeux est celui d'équilibre, notamment d'équilibre de Nash. Ces équilibres sont définis de façon non-constructive, et la question se pose de savoir si, étant donné un jeu, on peut calculer de façon centralisée et efficace un équilibre.
La classe de complexité nommée PPAD correspond aux calculs de certains de ces équilibres[2].
Notes et références
- Référence pour le second nom : Claire Mathieu, « Support du cours « Théorie des jeux algorithmique » au Collège de France, le 12 décembre 2017 », sur Collège de France.
- Tim Roughgarden, « Algorithmic game theory », Communications of the ACM, vol. 53, no 7,‎ , p. 78-86 (DOI 10.1145/1785414.1785439, lire en ligne)
Voir aussi
Bibliographie
- Johanne Cohen, « Jeux classiques en théorie algorithmique des jeux », dans Habilitation à Diriger les Recherches : Théorie des graphes, et de l’approximation pour le routage, la coloration et l’apprentissage d’équilibres. (lire en ligne)
- Tim Roughgarden, Lectures Notes on Algorithmic Game Theory Stanford CS364A, Fall 2013, (lire en ligne)