Constraint Games revisited

1 Introduction

Game theory [Fudenberg and Tirole, 1991] is a highly successful paradigm for modeling interactions and decision in presence of multiple agents. In the classical model [Von Neumann and Morgenstern, 1944; Nash, 1951], all agents, called players, play an action simultaneously and are given a reward, or utility, which depends also on the actions of the other players. The decision problem consists in finding which action each agent should play. Since each agent is able to control his action, he would rather choose the one which gives him a maximal reward knowing the actions taken by the other players. Whenever all players are unable to improve unilaterally their reward by changing their own action, the situation is called a Nash equilibrium, which is the best known solution concept for this decision problem.

This model with actions and utility is classically represented by an utility matrix for each player. Unfortunately, the size of these matrices grows exponentially with the number of players, which makes the representation tractable only for small games. This has motivated the introduction of compact representations like Graphical Games [Kearns et al., 2001], Boolean Games [Harrenstein et al., 2001], ActionGraph Games [Jiang et al., 2011] or the more recent Constraint Games [Nguyen et al., 2013; Nguyen and Lallouet, 2014] where action space and utilities are described using Constraint Programming. A related scheme is the one of Asynchronous DCOP [Grinshpoun et al., 2013; Wahbi and Brown, 2016] in which all players share the same constraints but with different costs.

In Constraint Games, user preferences are represented by a Constraint Satisfaction Problem (CSP) or a Constraint Optimization Problem (COP) whose respective satisfaction and maximization define preferred situations. Constraint Games are able to model easily a wide variety of games, from classical games of the Gamut suite [Nudelman et al., 2004] to games in more specialized fields like network or scheduling games [Nguyen and Lallouet, 2014]. An algorithm called Conga (and hereinafter called Conga 1.0) based on treesearch is used to explore the space of joint players actions and proposes two improvements over naive search. The first one is a memoization of previously encountered best responses in order to eliminate duplicate computations. The second one is a lazy pruning of inconsistent solutions obtained by comparing the theoretical and actual counting of deviations in a node's subspace and backtracking when all deviations have been evaluated. It improves over the previous state-of-the-art solver Gambit [McKelvey et al., 2016]. However, although effective and theoretically sound, this pruning only works well in practice at the very last levels of the search tree (level n or sometimes n-1 if n is the number of variables), opening the way to further improvements.

In this paper, we propose to consider the player's preference as a global constraint and we provide a complete understanding of its filtering. We prove first that the complete filtering up to arc-consistency is intractable and we further propose for it an approximation scheme. This new vision no longer relies on an ad-hoc algorithm but instead allows to fully reuse the framework of Constraint Programming. We have implemented a new solver called Conga 2.0 to demonstrate the efficiency of this improved filtering, showing a great improvements over Conga on a selection of games.

In addition, the handling of graphical games in our new framework is straightforward. By giving the dependency graph, we are able to limit the scope of the global preference constraints to the variables it actually depends on. It allows to handle games with a high number of players very efficiently. Since the global constraint is triggered by the player's objective, the solver is also able to take advantage of some hidden dynamic dependencies. It happens in particular in disjunctive cases when we are in a situation where a subset of the dependencies are enough to assign the objective.

2 Background

For a family of sets E = (Ei)i∈I and a subset J ⊆ I of indices, we denote by E|J = (Ej)j∈J the projection of E on J and by EJ the Cartesian product ∏j∈J Ej .

2.1 Game Theory

In this paper, we are only interested in static games of complete and perfect information.

Definition 1 (Game).

A game is a 3-tuple G = (P, A, u) where:

• P is a finite set of players.
• A = (Ai)i∈P where Ai ̸= ∅ is the set of actions that can be played by player i. We call strategy the choice of an action by Player i and strategy profile a tuple s = (si)i∈P where si ∈ Ai. The set of strategy profiles is denoted by AP .
• u = (ui)i∈P where ui : AP → R is the utility function of player i.

We denote by s-i a strategy profile for all players but i, and by (si, s-i) = s the strategy profile obtained by concatenation of si and s-i. It is implicitely assumed that all players want to maximize their own utility. The standard representation of the utility function of a player is a n-dimensional matrix representing the value associated to each strategy profiles of the game.

Example 1 (Wolf, Lamb and Cabbage Game (WLC)).

Three agents, Wolf (W), Lamb (L) and Cabbage (C) receive an invitation for a party. Each of them has the choice to come or not at this event. Each agent has his own preferences about meeting the others participants. Wolf would be happy to see Lamb but is indifferent about Cabbage's presence. Lamb would like to see Cabbage but only if Wolf is not coming. And Cabbage is a plant and is indifferent to everything. This can be translated in numerical preferences as depicted in Figure 1. The action of P coming to the party corresponds to p and the reverse to p. For instance w, l and c represent respectively the action of coming for Wolf, Lamb and Cabbage. The complete representation of the game requires 3 × 23 = 24 integers.

The basic solution concept for a static game is called Nash equilibrium and corresponds to a state where each player has no incentive to change his strategy assuming the other players do not change theirs. Note that various other solution concepts have been proposed in the litterature, among them the mixed Nash equilibrium [Nash, 1951] is one of the most popular. A best response for Player i corresponds to the situation where the player play his best option according to the others players (who have already fixed their strategies).

Definition 2 (Best Response).

A strategy profile s is a best response for player i if and only if ∀s′i ∈ Ai, ui(s) ≥ ui((s′i , s-i)).

Definition 3 (Pure Nash Equilibrium).

A strategy profile s is a Pure Nash Equilibrium (or PNE) if and only if s is a best response for all players.

We call NE(G) the set of pure Nash equilibria of a game G.

Example 2 (Example 1 continued).

The WLC game has 3 PNE. The first one happens when all players choose not to come to the party (wlc). The two others happens when Wolf chooses to come and Lamb to skip (wlc and wlc). In this case, Lamb is indifferent to the venue of Cabbage.

2.2 Constraint Games

Constraint Programming is a way to naturally represent and solve combinatorial problems. Let V be a set of variables having D = (Dx)x∈V as domains. A constraint c = (W, T) is defined over a subset W ⊆ V by a relation given by a table T ⊆ DW . A Constraint Satisfaction Problem (CSP) is a triple (V, D, C) where C is a set of constraints. Its solutions sol(C) are the tuples which satisfy all the constraints, i.e. sol(C) = {t ∈ DV | ∀(W, T) ∈ C, t|W ∈ T}. Preferred solutions can be chosen by giving an optimization condition min(x) or max(x) where x ∈ V .

Constraint Games [Nguyen and Lallouet, 2014] are a way to give games a compact representation by using Constraint Programming to represent utility functions. In a Constraint Game, the strategy of a player is represented by the joint values of the variables he owns, and utility by an optimization condition.

Definition 4 (Constraint Game).

A Constraint Satisfaction Game (or CSG) is a 4-tuple (P, V,D,G) where P is a finite set of players, V is a finite set of variables composed of a family of disjoint sets (Vi)i∈P for each player and a set VE of existential variables disjoint of all the players variables, D is defined as for CSP, and G = (Gi)i∈P is a family of CSP on V representing the goal of each player.

Note that [Nguyen and Lallouet, 2014] has introduced satisfaction and optimization variants of Constraint Games. A Constraint Optimization Game (COG) is a variant (P, V, D, G, opt) where opt = (opti)i∈P and ∀i ∈ P, opti ∈ V is the variable whose value defines the utility function ui of Player i. All players want to maximize their utility. Without further information, we simply call COGs Constraint Games. In addition, Constraint Games are able to represent easily hard constraints that define situations which are globally possible or forbidden [Rosen, 1965]. PNE and best responses can only be seeked in the satisfiable part of the hard constraints.

It is easy to prove that they provide a large increase in expressivity since it is impossible to find a matrix representation for a game with hard constraints by giving unsatisfiable profiles any numerical value for utility. However, they also change the set of equilibria: some of them may be forbidden by the hard constraints and new ones may appear if the best response that would have occured without the hard constraints is actually unsatisfiable. In this paper, we will only consider games without hard constraints.

A variable x ∈ Vi is said to be controlled by player i. The meaning of a Constraint Game (P, V,D,G, opt) is a game (P,A, u) in which the set of actions of a player i is defined by the different assignments of his controlled variables: Ai = DVi . In full generality, the handling of existential variables is related to a precise definition with the ceteris paribus principle [Bienvenu et al., 2010]. For the purpose of this paper, we consider that they are all functionnally determined by the assignment of controlled variables and thus any problem state is fully defined by such an assignment (in particular, the variables opti are assigned). Amore general treatment of this problem is left for future work. We denote by VC = V \VE the set of controlled variables and by A-i = DVC\Vi the set of states of all players but i. When a profile s satisfy the goal Gi of Player i, the utility ui of this player is given by the value of the variable to be maximized: ui(s) = opti. If a profile s does not satisfy the goal Gi, then this profile is never preferred by Player i. In this case, it is equivalent to consider that its associated utility is assigned to ui(s) = -∞.

Example 3 (Example 1 continued).

We can express the WLC game by a Constraint Satisfaction Game. First we can remark that each player has only two strategies and dichotomic preferences, thus making this problem expressible with boolean games [Harrenstein et al., 2001; Bonzon et al., 2006]. We name xW , xL and xC the respective optimization variables of Wolf, Lamb and Cabbage. Then we can state using boolean algebra notations: xW = wl, xL = wlc + wl and xC = 0.

In a Constraint Game, the notion of best response and PNE are the same as in matrix games. We recall from [Nguyen and Lallouet, 2014] that determining whether a game has a PNE in a Constraint Satisfaction Game is ΣP2 -complete.

2.3 Game Solving

Not many algorithms have been proposed to find PNE. The Gambit solver [McKelvey et al., 2016] proposes an enumeration procedure for finding PNE called enumpure. It simply checks all strategy profiles for being a PNE as shown in procedure Enum of Algorithm 2.1. The Enum procedure calls for each strategy profile a function isNash which checks for each player with the function Deviation whether the current strategy is a best response or not for this player. The main interest of this algorithm is that it provides a complete search which outputs all equilibria. This naive algorithm has not been improved until recently by the Conga 1.0 algorithm [Nguyen and Lallouet, 2014] for Constraint Games. Conga 1.0 is a tree-search algorithm which memorizes the best responses already found and uses a counter for pruning some actions that are never best responses.

Algorithm 2.1 Enum

1: procedure ENUM(game: G = (P,A, u)) 2: for all s ∈ AP do 3: if isNash(s) then 4: print(s) 5: function ISNASH(strategy profile: s): boolean 6: for all i ∈ P do 7: if Deviation(s, i) then return false 8: return true 9: function DEVIATION(strategy profile: s, player: i): boolean 10: for all s′i ∈ Ai, s′i ̸= si do 11: if ui(si, s′-i) > ui(s) then return true 12: return false

3 Preferences as Global Constraints

Although more efficient than the Enum algorithm used in Gambit, the Conga 1.0 algorithm can be still improved by using constraint propagation instead of an ad-hoc pruning algorithm. We propose a new solver for Constraint Games also based on a tree search where a player can own multiple variables which are instanciated separately by a regular Constraint Programming solver. Note that there is a main search tree which defines the region of the search space where an equilibrium is seeked. Like in Constraint Programming, a search state S is defined by giving each variable a current domain: S = (Sx)x∈V with Sx ⊆ Dx. We use the notations Si = S|Vi and S-i = S|VC\Vi . Search consists in a series of domain reductions with an alternation of deterministic consistency steps and non-deterministic branching steps [Rossi et al., 2006].

We propose to implement as constraints the preferences of the players. For this, it is useful to consider how preferences are defined from the goal of the players. Preferences have been widely studied in the litterature from the point of view of knowledge representation, especially using logic [von Wright, 1963; Bienvenu et al., 2010]. Generally, it is widely accepted that a preference is a preorder ≽ on a set of outcomes Ω. It does not have to be total. We have s ≽ s′ whenever s is preferred to s′ . A utility function Ω → R as defined in games defines a natural preference where s ≽ s′ ↔ u(s) ≥ u(s′ ). But games also add a notion of controllability: an outcome can only be compared to a controllable one, thus making the preorder partial.

For a Constraint Game (P, V,D,G, opt), the set of outcomes is defined by the search space DV , and the preference associated to a player is induced by the utility given by the value of his optimization variable. Since Player i only controls the variables Vi, we can fully describe his preference relation by giving the preferred outcomes for each uncontrollable situation defined by the other players, i.e. the set of best responses in Ai of Player i associated to each partial state of A-i. This relation has been introduced in [Gottlob et al., 2005] in the context of graphical games under the name of Nash constraint. The Nash constraint Ni of Player i is defined by Ni = (VC, {(si, s-i) | s-i ∈ A-i ∧ ∀s′i ∈ Ai, u((si, s-i)) ≥ u((s′i , s-i))}). Theorem 4.3 of [Gottlob et al., 2005] adapted to Constraint Games states that NE = sol(⋃{Ni | i ∈ P}).

(a) Nash Constraint NLamb

(b) Ext. Nash constraint eNLamb

Figure 2: Nash constraints for Lamb in extension

In this paper, we propose to implement players preferences using global constraints and study filtering algorithms for them. The Nash constraint Ni contains at least one entry for each partial profile in A-i. This property makes it unsuitable for filtering values from the other players' variables. Moreover, its representation in extension is exponential.

Example 4 (Example 1 continued).

The Nash constraint for Lamb is defined in Figure 2(a). Note that if Wolf and Cabbage are not coming, Lamb is indifferent and thus has both coming and not coming as best responses.

Since the Nash constraints Ni contains all best responses of Player i for all the uncontrollable situations defined by the other players joint strategies, any strategy for i that does not belong to the projection Ni|Vi is called a never best response. We first state an intractability result:

Proposition 1. In a Constraint Satisfaction Game, deciding whether an assignment nbr ∈ Ai for Player i is a never best response is ΠP2 -complete.

Proof. Membership is immediate.

For hardness, we reduce a QCSP [Bordeaux and Monfroy, 2002] Q = ∀X∃Y C to a 2-players 0-sum CSG G = ({1, 2}, V1 = X ∪ {x, a}, V2 = Y ∪ {y, b},G = (a = b)∨(C∧(Y ̸= nbr)∧(x = y)) where Y ̸= nbr stands for the assignment of Y is different of the tuple nbr and x, y, a, b are new variables whose domain contains at least two elements. Since the game is 0-sum, we only need to specify the goal G for Player 1 and take Player 2's goal as the negation of G.

If Q is valid, then for all sX ∈ DX , there is a sY ∈ DY such that C is true. Let vx and va be the respective values of x and a set by Player 1. If sY = nbr, then Player 2 assigns b ̸= va. If sY ̸= nbr, then Player 2 assigns y = vx. Hence nbr is a never best response.

Conversely, if Q is not valid, then it does exist a tuple sX ∈ DX such that forall sY ∈ DY , C is false. If sY = nbr, then Player 2 assigns b = va. If sY ̸= nbr, then Player 2 assigns b ̸= va. Hence nbr is a best response.

Arc-consistency filtering amounts to removing all values involved only in tuples which are never best responses. From Proposition 1 and the exponential representation argument, we infer that filtering the Nash constraint to arc-consistency is intractable even for dichotomic preferences. Thus we introduce three approximations in order to keep the problem tractable. We recall that a propagator for a constraint is a function that is i) correct, ii) contracting, iii) monotonic, and iv) singleton complete [Apt, 1999]. The respect of these properties ensures the correct behavior of the propagator when placed in the solver.

The first approximation consists in using only the objective value. We call extended Nash Constraint eNi = (VC ∪ {opti}, {(s, oi) | s ∈ Ni}) the Nash constraint Ni augmented with the value of the player's objective (see Figure 2(b)). Instead of removing exact inconsistent values, we will remove inconsistent objective values. The actual pruning on decision variables is done by back-propagation of arc-consistency through the constraints defining the objective. It means that we can approximate eNi by ooNi (objective optimal Nash constraint) defined by ooNi = (VC ∪ {opti}, {(s, oi) | ∃(s′ , oi) ∈ eNi ∧ oi ∈ eNi|opti }). However, only looking at the objective value is not enough. In different regions of the seach space, two tuples s and s′ may have the same objective value oi for Player i despite s is a not a best response for s-i and s′ is one for s′-i , hence the approximation.

Still, computing the exact objective values can be difficult because the subspace generated by the variables Vi of Player i may be huge. In our second approximation, we replace the set of exact objective values by the interval where they lie. This is defined by the constraint mooNi = (VC ∪ {opti}, {(s, oi) | ∃(s′ , o′i ) ∈ eNi, oi ≥ o′i }). Since sol(eNi) ⊆ sol(ooNi) ⊆ sol(mooNi), any filtering of mooNi is correct with respect to eNi. Note that we only need to update the lower bound because we have a maximization problem.

Since consistent objective value correspond to one best response, the minimum bound of the objective should be set to the maximum value of the minimum bound of the best responses on the current search state S:

Thus we need to find (or approximate) the maximin of the objective on the current subspace. The exact computation of this maximin on a search state S requires a traversal of the subspace S-i, and for each tuple, a test for deviation in Ai. Unfortunately, a traversal of S-i is too costly. The third approximation consists in using arc-consistency to reject impossible objective values.

To implement this filtering, we use an auxiliary solver with Branch & Bound on a tree-search limited to Player i's variables to maximize the minimum value of the objective on the subspace at a node n of the main search tree. In order to compute deviations for Player i, all variables of Vi are reset to their original domain Ai, including those which were assigned before n. The domain of the variables of the other players are given by S-i (some are already assigned at node n and some are not). Whenever the minimum bound of the objective is pruned to a value b, a new constraint opti > b is posted for the rest of the search. For a search state S, we replace in formula (1) the traversal of the search space S-i by an arc-consistency check. This amounts to compute MmAC(S), the best estimation arc-consistency can provide for the maximum value of the minimum bound of the objective: MmAC(S) =maxsi∈Ai lb(AC((si, S-i))) where AC denotes arc-consistency applied to a search state. Formally, the operator BBi : DV → DV implemented by the global constraint is defined by:

When all variables are assigned, computing deviations amounts to checking whether a complete assignment is a best response for Player i.

Proposition 2. BB is a propagator for eNi.

Proof. Let S and S′ be two search states. First, because AC is correct, we have MmAC(S) ≤ Mm(S). Then, if some value is pruned by MmAC, then it has to be pruned also by Mm.

• correctness: S ∩ NE ⊆ BB(S). Take s ∈ S ∩ NE and suppose s ̸∈ BB(S). Let s|opti = oi and let αi = MmAC(S). Since s ̸∈ BB(S), we have oi < αi. Then there exists s′i ∈ Ai such that (s′i , s-i)|opti = o′i > oi. Hence we have oi < αi ≤ o′ i and (s′i , s-i) is a deviation for s and s ̸∈ NE, contradiction.
• contractness: BB(S) ⊆ S. Since the propagator only remove values, contractness is always true.
• monotony: S ⊆ S′ → BB(S) ⊆ BB(S′ ). Take s ∈ BB(S), we have s ∈ S since BB is contracting and s ∈ S′ by definition. Let s|opti = oi, αi = MmAC(S) and βi = MmAC(S′ ). Since s ∈ BB(S), we have αi ≤ oi. Since AC is monotonic, we have βi ≤ αi. Thus βi ≤ oi and s ∈ BB(S′ ).
• singleton completeness: ensured by construction.

4 Experiments

We have implemented a new solver for Constraint Games on top of the constraint solver Choco v4 [Prud'homme et al., 2017]. This new solver is composed of an interface to post goals for the different players and the implicit post of the new global constraints as defined in Section 3. An important aspect is that it does not require a modification of the classical Constraint Programming framework (search and consistency).

The scope of the preference constraint for Player i is the set of all controlled variables VC plus Player i's optimization variable opti. However, the propagator is called whenever the objective of the player has been updated. Upon the call, it revises opti by launching a new search tree in a distinct solver only on the variables of Vi, having copied the current state S-i of all the other players' variables. During this search, Branch & Bound is applied to the lower bound of the objective and the approximation of its maximin value on the current subspace S-i is returned. For all experiments, we have applied a lexicographic heuristics on the choice of variables and a min value heuristics on the choice of the values.

We have performed experiments on classical games of the Gamut suite [Nudelman et al., 2004]: Minimum Effort Game (MEG), Travelers Dilemma (TD), Dispersion Game (DG), Collaboration Game (CG), ArmRaces (AR), ElFarol Bar Game (EFBG) [Arthur, 1994] and Colonel Blotto (CB)

[Roberson, 2006]. For space reasons, we invite the reader to refer to the original papers to get a full description of the games. They represent a wide range of games, with many, few or no equilibria. In all games, the parameters are given by two numbers: the number of players and the number of actions. For example, "MEG 5.5" denotes the Minimum Effort Game with 5 players, each one having 5 actions. One exception is the Colonel Blotto game for which the second number is the number of battlefields and the last one the number of troops each player can deploy.

We have compared our new approach (called Conga 2) to the complete enumeration of the search space (hereafter called enum) as implemented in the Gambit solver [McKelvey et al., 2016] and to a custom reimplementation of the Conga algorithm (hereafter called Conga 1) as described in [Nguyen and Lallouet, 2014]. The results are presented in Table 1. All times are given in seconds and we applied a maximum runtime of 10 minutes to get the complete set of PNE for each problem. All instances for which the given solver has reached a timeout are indicated by "-". Experiments have been run on a Intel Xeon E5-1660 with 32 GB of RAM, Java 8 and Windows 7.

We can see that Conga 2.0 is most of the time better than Conga 1.0, reaching up to three orders of magnitude on MEG. Exceptions are the Dispersion Game and Arm Race for which there is little propagation. We have presented the results in order to show the limits of each technique when staying under the time limit of 10 minutes.

5 Graphical Aspects

When the utility of a player only depends on a subset of the other players, the game is called graphical [Kearns et al., 2001]. More formally, for a profile s ∈ AP and two players i and j, we say that ui(s) is independent of j if ∀s′j ∈ Aj, ui(s) = ui(s-j, s′j ). If this is not true, then i depends on j for s, denoted by i ◁s j. We denote by depi(s) = {j | i ◁s j} the set of dependencies of Player i for the state s. For E ⊆ AP , we note depi(E) = ⋃s∈E depi(s). Finally, Player i statically depends on Player j, denoted by i ◁ j if j ∈ depi(AP ). A minimal dependency which occurs only in a strict subspace of AP is called dynamic.

Example 5 (Example 1 continued).

Since Wolf only depends on Lamb and Lamb on Wolf and Cabbage, the WLC game is actually a graphical game, as depicted in Figure 3. By using this dependency scheme, we are able to reduce the size of the matrices to one 1×2, one 2×2 and one 2 × 2 × 2, for a total amount of 14 integers. Interestingly, the WLC game owns a dynamic dependency: when Wolf is coming, Lamb does not depend on Cabbage anymore. It is reflected in the Lamb formula xL = wlc +wl for which l is a best response to w whatever the value of c.

The main purpose of graphical games is to save space in the matrix representation, and also to speed-up the computation of equilibria [Vickrey and Koller, 2002; Ortiz and Kearns, 2002]. We can build the oriented graph of dependencies between player D = (P, {(i, j) | i ◁ j}). If this graph is not a clique, then the game is graphical. In this case, it is possible to limit the scope of each global constraint to its associated player and his set of dependencies. It ensures an increased performance in the checking of deviations without relying on a specialized algorithm. When checking for deviations, only the state of the dependent variables is injected in the second solver. In addition, because our global constraint is triggered on updates of the objective, it is able to detect on-the-fly dynamic dependencies. Note that this kind of dependencies may also occur in non-graphical games.

In our implementation, we provide the dependency graph as a part of the model. We have performed experiments on classical graphical games: Public Good Game (PGG), Threshold Game of Complement (TGC) [Jackson, 2008] and Road Game (RG) [Vickrey and Koller, 2002]. All games have a fixed number of strategies, which is 2 for PGG and TGC, and 4 for RG. Each model has been run on different topologies with different node degrees. In the circle topology (C), each node is of degree 2 and the only parameter is the number of players. For the tree topology (T), T 21.4.3 means that the game has 21 players connected by a tree of maximal degree 3 on 4 levels. The last topology is the complete bipartite graph (B) whose parameter is the number of players. The results are shown in Table 2, also with a timeout of 10 minutes. In all cases but one, adding the graphical information is highly beneficial. It demonstrate the efficiency of the approach even for graphs of relative high degrees.

6 Conclusion

In this paper, we have proposed a more elegant and efficient vision of Constraint Games. We have fully modeled the potential constraint pruning available in Game Theory, and proved its intractability. We have proposed an efficient filtering algorithm in the general and graphical cases and demonstrated experimentally its efficiency over the state-of-the-art game solver Conga 1.0 [Nguyen and Lallouet, 2014]. However, the main interest of this new approach is to bring game theory closer to the elegant framework of Constraint Programming by viewing agent preferences as constraints.

So far, we limited ourselves to the design of a complete solver because only this type of solver is able to be used as a basis for computing more specialized Nash equilibria, like those optimizing a Social Welfare function or Pareto efficient. Also completeness is required to compute Price of Anarchy and Price of Stability. We did not include theses aspects for lack of space. Another open question is the extension of our filtering to games with hard constraints. As is, our filtering is incorrect in presence of hard constraints because the expected deviation may not be satisfiable. As a consequence, the solver becomes incomplete. In future work, we will also be interested in the computation of one equilibrium, emphasizing the role of a good heuristics and opening comparisons with best response dynamics [Ceppi et al., 2010].