Conception de mécanismes
La conception de mécanismes, parfois appelée théorie des jeux inverse, est l'ingénierie des règles d'interaction de manière à ce que des agents égoïstes, agissant rationnellement, produisent les résultats souhaités par le concepteur.
Definition
La conception de mécanismes est l'étude de la manière de définir les règles d'une interaction multi-agents — qui peut faire quoi et comment les résultats et les paiements sont déterminés — afin que le comportement à l'équilibre d'agents rationnels et égoïstes atteigne un objectif souhaité tel que l'efficacité ou la véracité.
Scope
Ce sujet couvre la conception de protocoles d'interaction pour des agents stratégiques : le choix social et l'agrégation des préférences, les objectifs d'efficacité et de compatibilité des incitations (véracité), le principe de révélation, les enchères (y compris l'enchère au second prix de Vickrey et le mécanisme de Vickrey-Clarke-Groves), ainsi que les aspects algorithmiques et computationnels de la mise en œuvre des mécanismes. Il aborde la manière d'aligner les incitations individuelles sur les objectifs collectifs. L'analyse descriptive du comportement des agents dans des jeux fixes est traitée dans le cadre de la théorie des jeux.
Core questions
- Comment les règles d'interaction peuvent-elles être conçues de manière à ce que les agents soient incités à déclarer leurs véritables préférences ?
- Que dit le principe de révélation concernant la restriction de l'attention aux mécanismes véridiques ?
- Comment les enchères allouent-elles efficacement les biens entre les agents ayant des évaluations privées ?
- Quels sont les coûts computationnels de la mise en œuvre de mécanismes souhaitables ?
Key concepts
- choix social et agrégation des préférences
- compatibilité des incitations (véracité)
- implémentation en stratégie dominante
- principe de révélation
- enchères
- enchère au second prix de Vickrey
- mécanisme de Vickrey-Clarke-Groves (VCG)
- efficacité et rationalité individuelle
Key theories
- Compatibilité des incitations et l'enchère au second prix
- L'enchère au second prix (à pli cacheté) de Vickrey, où le gagnant paie le deuxième prix le plus élevé, fait de l'offre véridique une stratégie dominante, illustrant comment une conception minutieuse des règles peut susciter un comportement honnête de la part d'agents égoïstes.
- Mécanismes de Vickrey-Clarke-Groves
- La famille VCG généralise l'idée du second prix aux problèmes d'allocation complexes, en facturant à chaque agent son externalité de sorte que la déclaration véridique soit une stratégie dominante et que le résultat efficace soit sélectionné.
- Principe de révélation
- Le principe de révélation montre que tout résultat réalisable par un certain mécanisme peut également être atteint par un mécanisme direct véridique, permettant aux concepteurs de se concentrer sur des mécanismes compatibles avec les incitations sans perte de généralité.
Clinical relevance
La conception de mécanismes sous-tend les enchères de publicité en ligne et de recherche sponsorisée, les enchères de spectre et de ressources, les marchés électroniques et les systèmes d'appariement, ainsi que l'allocation des ressources computationnelles, en concevant des règles selon lesquelles les agents stratégiques sont conduits à des résultats efficaces et véridiques.
History
La conception de mécanismes est issue de la théorie économique, avec l'analyse des enchères de Vickrey (1961) et les contributions ultérieures de Clarke et Groves formant la famille VCG. À partir de la fin des années 1990, l'informatique a ajouté l'étude de la tractabilité computationnelle et de l'approximation, donnant naissance à la conception algorithmique de mécanismes, exposée dans des textes tels que Algorithmic Game Theory (2007).
Key figures
- William Vickrey
- Edward H. Clarke
- Theodore Groves
- Noam Nisan
- Tim Roughgarden
Related topics
Seminal works
- vickrey1961
- shoham2009
- nisan2007
Frequently asked questions
- Pourquoi la conception de mécanismes est-elle appelée théorie des jeux inverse ?
- La théorie des jeux prend les règles d'une interaction comme données et analyse comment les agents rationnels se comporteront. La conception de mécanismes fonctionne à l'inverse : elle part d'un résultat souhaité et conçoit les règles de manière à ce que le comportement rationnel des agents produise ce résultat, d'où l'appellation de théorie des jeux inverse.
- Pourquoi une enchère au second prix encourage-t-elle les offres véridiques ?
- Dans une enchère au second prix de Vickrey, le gagnant paie le deuxième prix le plus élevé plutôt que le sien. Cela supprime toute incitation à sous-estimer une offre : miser votre vraie valeur ne peut que vous aider à gagner lorsque cela en vaut la peine et ne vous fait jamais surpayer, de sorte que l'offre honnête devient une stratégie dominante.