Equilibrium Theory and Constraint Networks

This paper presents a new way to map a Constraint Satisfaction Problem (CSP) onto a non-cooperative game. Constraint Satisfaction Problems arise in many areas of Artificial Intelligence and have usually been tackled with backtracking based algorithms. The relevance of equilibrium theory in games with respect to the problem of finding a solution or a partial solution for a CSP is shown. The concepts of Nash equilibrium, admissible equilibrium and perfect equilibrium are examined. We prove that the solutions of a CSP are equilibrium points in pure strategy, both in the sense of Nash and in the sense of Selten. Finally, it is shown a CSP solution can be reached through a step by step evolutionary process, in which variables update the probability of assuming a value, considering what the other variables will do. Some computer experiments are reported in the paper. 1 Introduction Artificial intelligence (AI) has started to look very closely at game theory in the last years. Many typical a..