Contrainte Jeux: modélisation et Jeux Résolution avec Contraintes
Thi-Van-Anh Nguyen · HAL (Le Centre pour la Communication Scientifique Directe) · 2014
This thesis presents a topic at the interface of game theory and constraint programming. More precisely, we focus on modeling games in a succinct way and then computing their solutions on these compactly encoded games thanks to constraint programming. For a long period of time, game theory has suffered a modeling difficulty due to the lack of compact representations for encoding arbitrary games. The basic game representation is still an n-dimensional matrix called normal form which stores utilities of all players with all joint strategy profiles. The matrix however exponentially grows with the number of players. This also causes a solving difficulty for computing solutions in games.In the thesis, we introduce a novel framework of Constraint Games to model strategic interaction between players. A constraint game is composed of a set of variables shared by all the players. Among these variables, each player owns a set of decision variables he can control and constraints expressing his utility function. Constraint games is a generic tool to model general games and can be exponentially more succinct than their normal form. We also show the usefulness of the framework by modeling a few classical games as well as realistic problems. The main solution concept defined for constraint games is Pure Nash Equilibrium. It is a situation in which no player has an incentive to deviate unilaterally. It has been well-known that finding pure Nash equilibrium is computationally complex. Nevertheless, we have achieved to build an efficient solver called ConGa which includes various ways for solving constraint games.