Game Theory and Applications

Patrick Maillé

Ce cours présente les outils de base servant à modéliser les interactions entre participants avec des objectifs non-alignés. La donnée de ces participants, de leurs préférences, et de leur état de connaissance de l'interaction définit un jeu non-coopératif, pour lequel nous étudierons la notion capitale d'équilibre (de Nash). On étudiera en particulier les jeux de routage (applications au transport) et les enchères (application aux enchères Google pour les mots-clé).

Mots-clés

Optimisation, Jeu non-coopératif, Equilibre de Nash

Prérequis

Connaissances de base en probabilité (ex : notion de probabilité conditionnelle) et en analyse (calcul de dérivées). Les étudiants doivent être habitués à des raisonnements rigoureux.

Contenu

• Définition d'un jeu à partir de problèmes en télécoms (jeux à deux joueurs : jamming game, réseaux sociaux, collusion entre opérateurs)
  • notion de stratégie, d’utilité, de joueur
  • jeux simples : dilemme du prisonnier, bataille des sexes, jeu d’évitement
  • diversité des contextes d’utilisation : faut-il payer ou non son ticket de bus ? Pourquoi annoncer une pénurie d’essence conduit-il à une pénurie d’essence ?
  • notion d’équilibre de Nash (stratégies pures ou mixtes)
  • notion de meilleure réponse
  • résultats d'existence
• Jeux de routage
  • notion d’équilibre de Wardrop, liens avec l’optimisation
  • prix de l’anarchie : combien perd-on à cause de l’égoïsme des utilisateurs ?
  • comment réduire le prix de l’anarchie avec des péages ?
• Les enchères Google (comment Google fait-il de l’argent ?)
  • principes des enchères, enchères au premier et au second prix
  • propriétés d’incitation, d’efficacité, mécanismes Vickrey-Clarke-Groves
  • les mécanismes actuellement utilisés : Generalized Second Price

Compétences acquises

A l'issue du cours, les étudiants seront capables de :

• modéliser les préférences d'acteurs sous forme d'une fonction d'utilité
• représenter les interactions à l'aide d'une matrice pour un jeu fini
• anticiper l'issue d'une interaction via le concept d'équilibre de Nash
• analyser l'impact d'une décision (règle) sur l'issue des interactions, et optimiser cette décision