Théorie algorithmique des jeux

La théorie algorithmique des jeux ou théorie des jeux algorithmique (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. 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. Ce domaine est relativement récent et on peut situer son essor dans les années 2000. On peut citer quelques sous-domaines emblématiques de la théorie algorithmique des jeux. 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é. On peut par exemple citer l'enchère de Vickrey (ou enchère au second prix). 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. Un concept fondamental dans les jeux est celui d'équilibre, notamment d'équilibre de Nash.