Calcul des Equilibres par la Programmation par Contraintes

Abstract

L’équilibre de Nash est le concept de solution le plus connu et le plus étudié en théorie des jeux non coopératifs. Cependant, le calcul de cet équilibre est connu pour ^etre un probl`eme NP difficile. Ces derni`eres années, on recense quelques travaux novateurs ayant abordé la question du calcul de cet équilibre en utilisant les outils de la programmation par contraintes. Par conséquent, l’objectif fixé pour ce travail est de présenter dans un premier temps une synth`ese de ces travaux, puis par la suite, exploiter la définition de l’équilibre de Nash en tant que situation du jeu o`u chaque joueur choisit une stratégie de meilleure réponse pour représenter le probl`eme de calcul d’un équilibre de Nash en stratégies pures sous forme d’un probl`eme de satisfaction de contraintes. Ce mod`ele sera illustré sur quelques classes particuli`eres de jeux. Nash’s equilibrium is the best-known and most studied solution concept in non-cooperative game theory. However, calculating this equilibrium is known to be a difficult NP problem. In recent years, we have identified some innovative works that have addressed the question of calculating this equilibrium using the tools of constraint programming. Consequently, the objective set for this work is to first present a synthesis of this work, then subsequently, to exploit the definition of Nash equilibrium as a game situation where each player chooses a strategy of best answer to represent the problem of calculating a Nash equilibrium in pure strategies in the form of a constraint satisfaction problem. This model will be illustrated on some particular classes of games.