Stage de recherche - Théorie des jeux algorithmiques : calculs d'équilibres F/H

votre rôle

La théorie des jeux est une branche des mathématiques permettant l’analyse des situations d’interactions stratégiques où des preneurs de décisions rationnels, appelés joueurs, s’influencent par le biais de leurs décisions.

A quoi peut-on s’attendre dans une telle situation ? Une stabilité décisionnelle est-elle envisageable ?  Afin de répondre à ces questions, plusieurs concepts de solutions, tel que l’équilibre de Nash, ont été proposés et étudiés. Certains critères de stabilité permettent notamment d’introduire des recommandations aux joueurs (équilibres corrélés) ou de la robustesse à des perturbations ou « mutations » dans les stratégies (ex. équilibres parfaits, équilibres évolutionnaires).

Néanmoins, le calcul de tels équilibres est un problème souvent délicat et plusieurs approches algorithmiques (ex. résolution de systèmes d’inégalités polynomiales, méthodes homotopiques, etc.) ont été proposées [1]-[3] pour les Nash (et certains perfectionnements) mais d’autres concepts tels que les équilibres généralisés nécessitent des techniques différentes [4] typiquement issues de l’optimisation.

Ce stage a pour objectif l’implémentation, l’analyse et l’amélioration d’algorithmes de calculs d’équilibres pour les jeux non-coopératifs en vue de leur introduction dans un outil numérique. Dans le cadre de ces travaux, nous souhaitons approfondir l’utilisation de la méthode homotopique pour la recherche d’équilibres de Nash (calculant un chemin de solutions depuis un problème « simple » et typiquement utilisée en optimisation). On cherchera à comprendre en détail le mécanisme de sélection d’équilibre et ses possibles évolutions, le lien avec la théorie développée par Harsanyi & Selten [5], le rôle des croyances initiales des joueurs et son potentiel pour une résolution efficace de jeux issus d’applications.

Références

[1] Berg, Exclusion Method for Finding Nash Equilibrium in Multiplayer Games, 2017, AAAI.

[2] von Stengel, Finding Nash Equilibria of Two-Player Games, arXiv:2102.04580, 2021.

[3] Herings et al., A Differentiable Homotopy to Compute Nash Equilibria of n-Person Games, Economic Theory, vol. 18, no.1, 2001.

[4] Kim, Equilibrium Computation of Generalized Nash Games: A New Lagrangian-Based Approach,
arXiv:2106.00109, 2022.

[5] Harsanyi et al., A General Theory of Equilibrium Selection in Games, MIT Press, 1998.