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.
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.
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.
Couvre les fondamentaux de la théorie des jeux, l'équilibre de Nash et les interactions stratégiques dans les systèmes multi-agents.
Explore les méthodes de pénalité quadratiques pour l'optimisation avec des contraintes imposées à l'aide de fonctions de pénalité.
Explore les classes de complexité P et NP, les algorithmes pratiques, les problèmes non polynomiaux et la vérification efficace des solutions.
As large, data-driven artificial intelligence models become ubiquitous, guaranteeing high data quality is imperative for constructing models. Crowdsourcing, community sensing, and data filtering have long been the standard approaches to guaranteeing or imp ...
It's been a little more than 40 years since researchers first suggested exploiting quantum physics to build more powerful computers. During this time, we have seen the development of many quantum algorithms and significant technological advances to make th ...
Artificial Intelligence often relies on information obtained from others through crowdsourcing, federated learning, or data markets. It is crucial to ensure that this data is accurate. Over the past 20 years, a variety of incentive mechanisms have been dev ...