Constraint Games for Modeling and Solving Pure Nash Equilibria, Price of Anarchy and Pareto Efficient Equilibria

International audienceFor a variety of automated collective decision systems, Pure Nash Equilibria [4] are a satisfactory and concrete solution concept since any agent will likely be satisfied by the outcome. However, it is well known that the problem is hard [3]. In addition, maximizing a social welfare function is a desirable but also more complex property to compute, since it involves a comparison with the whole set of equilibria. In order to quantify the efficiency of an equilibrium, concepts like Pareto efficiency, Price of Stability or Price of Anarchy are usually used. All these concepts are computationnaly intensive, even for relatively small games. Constraint Games [2] are a new framework in which utilities are represented by Constraint Optimization Problems. Not only it gives compact models, but also they are very intuitive and readable. We have built a solver based on Constraint Programming which is orders of magnitude faster than the current state-of-the-art Gambit [1]. This solver is based on tree-search, and the players' preferences are implemented as global constraints with a dedicated filtering algorithm. In this paper, we propose to compute optimal and Pareto-optimal Nash equi-libria. By adding constraints to express the social welfare function, the classical branch & bound optimization of Constraint Programming is able to find efficiently optimal equilibria of a game. Price of Anarchy and Price of Stability can be computed by finding the maximally efficient centralized situation and comparing respectively with the minimally and maximally efficient equilibria. Pareto efficient equilibria can be found simply by adding a Pareto constraint to the problem. We also show experimentally that our approach is highly competitive. References 1. Richard D McKelvey, Andrew M McLennan, and Theodore L Turocy. Gambit: Software tools for game theory, version 16.0.0 edition, 2016. 2. Thi-Van-Anh Nguyen and Arnaud Lallouet. A complete solver for constraint games