Efficient algorithmic methods for Nash equilibria computation
From LRDE
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
- Auteurs
- Antoine Leblanc
- Type
- techreport
- Année
- 2007
- Numéro
- 0745
- Mots-clés
- Nash equilibria TOP algorithms
Résumé
L'un des principaux problèmes rencontrés lors de la recherche d'équilibres de Nash est le manque d'efficacité des principaux algorithmes. La plupart ont des complexités en pire cas de l'ordre de O(4^n) . Il n'est de plus que peu probable de réussir à améliorer ces algorithmes, qui sont pour la plupart relativement vieux. Cette étude détaille tout d'abord les algorithmes principaux en spécifiant leurs avantages et inconvénients, puis présente un nouvel algorithme développé au LRDE basé sur une approche géométrique : le calcul du TOP en dimension d .