Un algorithme pour la résolution d'un jeu bi-matriciel

Session : PM / Programmation Mathématique
Vendredi 12 février 10:30 - 11:30 Salle : RP10
Aicha Anzi, Ramzi Kasri, Hicham Lenouar et Radjef Mohammed Said

La recherche de l'équilibre de Nash est le problème le plus fréquent dans la théorie des jeux. L'équilibre qui consiste à prendre une seule décision (pure) peut ne pas exister, il sera question alors de chercher l'équilibre en stratégies mixtes qui constitue une distribution de probabilité sur tout l'ensemble de stratégies. Pour ce dernier, Nash a montré qu'il existe toujours dans le cas d'un jeu sous forme normale. Dans ce travail,Dans ce travail, nous nous sommes intéressés à la recherche de cet équilibre dans le cas d'un jeu bi-matriciel, c'est-à-dire un jeu fini à deux joueurs, sous forme normale et à somme non nulle. Pour ce faire nous avons utilisé une technique d'optimisation non convexe qui est la programmation DC (Difference of Convex) ainsi que l'algorithme DC (DCA). Nous avons d'abord reformulé le jeu bi-matriciel sous forme d'un PCL. Puis, nous avons transformé ce dernier en un problème d'optimisation pour lequel nous avons considéré quatre formulations toutes non convexes. Ces formulations ont donné naissance à quatre versions de DCA que nous implémentées et testées sur des jeux bi-matriciels dont l'équilibre est déjà connu dans la littérature et comparées en utilisant des jeux simulés aléatoirement. Nous avons effectué également une étude comparative avec un autre algorithme de résolution des jeux bi-matriciels.

Mots clés : Jeu bi-matriciel, Equilibre de Nash, Problème de complémentarité, Programmation DC, DCA