Constraint Games: Framework and Local Search Solver

Game theory is a highly successful paradigm for strategic decision making between multiple agents having conflicting objectives. Since a few years, games have been studied in a computational perspective, raising new issues like complexity of equilibria or succinctness of representation. Indeed, the main representation for general games is still a n-dimensional matrix of exponential size called normal form. In this paper, we introduce the 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 she can control and a Constraint Optimization Problem defining her preferences. Since the preferences of a player depend on the decisions taken by the other players, each player may try to improve her position by choosing an assignment that optimizes her preferences. Pure Nash equilibria are situations in which no player may improve her preferences unilaterally. Constraint Games are thus a generic tool to model general games and can be exponentially more succinct than their normal form. We show the practical utility of the framework by modelling a few realistic problems and we propose an algorithm based on tabu search to compute pure Nash equilibria in Constraint games that outperforms the algorithms based on normal form. In addition, Constraint Games raise some interesting research issues that deserve further attention.