Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Théorie algorithmique des jeux
Résumé
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Séances de cours associées (8)
Introduction à la théorie des jeux
Couvre les fondamentaux de la théorie des jeux, l'équilibre de Nash et les interactions stratégiques dans les systèmes multi-agents.
Méthodes de pénalité quadratiques: problèmes sonores
Explore les méthodes de pénalité quadratiques pour l'optimisation avec des contraintes imposées à l'aide de fonctions de pénalité.
Théorie de la complexité : P et NP
Explore les classes de complexité P et NP, les algorithmes pratiques, les problèmes non polynomiaux et la vérification efficace des solutions.
Publications associées (32)
Personnes associées (2)
Concepts associés (1)
Algorithmic mechanism design
Algorithmic mechanism design (AMD) lies at the intersection of economic game theory, optimization, and computer science. The prototypical problem in mechanism design is to design a system for multiple self-interested participants, such that the participants' self-interested actions at equilibrium lead to good system performance. Typical objectives studied include revenue maximization and social welfare maximization. Algorithmic mechanism design differs from classical economic mechanism design in several respects.