Keywords: Mots-clefs-Constraint Programming, Game theory, Nash Equilibrium, Search strategy topologies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 Other backtracking search and methods . . . . . . . . . 20 Local search . . .

Nouvelles techniques pour les Contraints Games

Cette thèse présente de nouvelles techniques pour les Constraint Games. La manière de résoudre un Constraint Game est repensée en terme de propagation de contraintes. Les préférences des joueurs sont maintenant considérées comme des contraintes globales permettant une intégration transparente dans les solveurs de contraintes ainsi que d'améliorer l'efficacité du framework. Notre nouveau solveur ConGA est diffusé en open source 1 . Celui-ci est plus rapide que les travaux connexes et est capable de trouver tous les équilibres de Nash, et cela même dans des jeux avec 200 joueurs voir 2000 pour certains jeux graphiques.

Grâce à cette perspective, le framework a pu être utilisé pour résoudre un problème de routage dans le domaine des télécommunications. Les aspects centralisé et décentralisé ont été étudiés. La comparaison de ces derniers est très importante pour évaluer la qualité de service dans les applications multi-utilisateurs. L'évaluation de cette dernière peut être très coûteuse, c'est pourquoi nous proposons plusieurs techniques permettant d'améliorer la résolution de ce problème et ainsi d'améliorer la résolution du problème.

Constraint Games revisited

This thesis revisits the Constraint games framework by rethinking their solving technique in terms of constraint propagation. Players preferences are considered as global constraints making transparently the integration in constraints solvers. It yields not only a more elegant but also a more efficient framework. We release our new solver ConGA in open source 1 . Our new complete solver is faster than previous state-of-the-art and is able to find all pure Nash equilibrium for some problems with 200 players or even with 2000 players in graphical games.

This new perspective enables us to tackle real-worlds Telecommunication problems. This problem is solved with a centralized perspective and a decentralized one. The comparison of the two last approaches is really important to evaluate the quality of service in multi-users application, but computationally consuming. That is why, we propose new techniques in order to improve the resolution process.

Motivations and context

Artificial intelligence has a long story of modeling and solving problems. Most of the time, the problems tackled are not easy. Implementing them, cleanly and efficiently can be challenging. Multiples frameworks having each their own specificities and domains of applicability facilitating this solving process exist. Each framework has its own way to express problems. Three of the most important frameworks are Boolean satisfiability (or SAT), Integer Linear Programming (or ILP) and Constraint Programming (or CP). SAT and ILP allow expressing problems in a uniform way using either clauses or linear (in)equations. Their languages are restricted to a few instructions set. Constraint Programming works a bit differently. It has an extensible language where a basic element can be any relation. More generally, Constraint Programming is a successful generic paradigm to solve combinatorial problems [START_REF] Wallace | Practical Applications of Constraint Programming[END_REF]. Through time, Constraint Programming has shown its ability to solve problems of the frontier with Operational Research. Especially large-scale problems from industry like scheduling for industrial product line [START_REF] Régin | A Filtering Algorithm for Global Sequencing Constraints[END_REF][START_REF] Bergman | MDD Propagation for Sequence Constraints[END_REF], planning [START_REF] Baptiste | Constraint-Based Scheduling and Planning[END_REF], nurse scheduling in hospitals [START_REF] Demassey | A Cost-Regular Based Hybrid Column Generation Approach[END_REF][START_REF] Schaus | Scalable Load Balancing in Nurse to Patient Assignment Problems[END_REF], Bin-Packing [START_REF] Schaus | Cardinality Reasoning for Bin-Packing Constraint : Application to a Tank Allocation Problem[END_REF] and even crew management in transportation [START_REF] Lorca | Using Constraint Programming for the Urban Transit Crew Rescheduling Problem[END_REF]. Vehicle Routing Problems (VRP) [START_REF] Shaw | Using constraint programming and local search methods to solve vehicle routing problems[END_REF] is one of the famous applications of CP. In VRP a set of drivers have to visit a set of customers, while some regulation constraints have to be fulfilled on vehicles, customers, drivers and so on. The goal of VRP is to find a configuration which minimizes the cost. The VRP is somehow the same as the problem solved by GPS navigation softwares such like Waze [START_REF]Maps and Traffic[END_REF]. A navigation software proposes routes to users to guide them from a starting point to a destination. The routes are recommended in real time, taking into account the current roads' congestion and so the others users' routes. A navigation software targets a different kind of solutions than the ones sought in VRP. While VRP is a mono-objective optimization, routing applications' goal is different due to the multiples objectives intrinsically present through users. Their goal is to make all users satisfied with their routes. A user is going to be satisfied if he does not see any visible improvement to the route recommended by the system (i.e. if the system gives his best possible options). For instance, anyone using this application does not want to follow a route which is not optimal for himself, even if it is for a common interest.

The need to provide a high quality of service for navigation software companies is intensified by a competitive environment. Many applications using different systems are available. For instance, if a user can get a better route from a competitor, then the next times he will probably use the other application to be routed. The global problem of such routing application is related to game theory [START_REF] Von | Theory of Games and Economic Behavior[END_REF], which is a mathematical field modeling interactions between multiples agents (also called players). Game theory has found many applications such in scheduling [START_REF] Gairing | Computing Nash equilibria for scheduling on restricted parallel links[END_REF], economics [START_REF] Roth | The economist as engineer : Game theory, experimentation, and computation as tools for design economics[END_REF] and even biology [START_REF] Hammerstein | Game theory and evolutionary biology[END_REF]. A game is the central concept of game theory. The latter models a situation composed of players having each a possible set of actions, which, gives a certain level of satisfaction (or utility). Players' utilities are often expressed with numerical preferences but are not limited to it.

Representing a game is not an easy task. Historically, a game is modeled by providing a matrix giving a value to all the possible situations for each agent. This representation requires a lot of memory. Especially, its exponential memory requirement makes it quickly intractable in practice. For example, given 1000 users with two routes each, requires 2 1000 integers which is about 10 300 . In comparison, the number of fundamental particles in the observable universe is about 10 80 . That is why compact representation like Constraint Games [START_REF] Nguyen | Constraint Games : Framework and Local Search Solver[END_REF], were developed . Constraint Games is a way to represent games by using Constraint Programming. Constraint Programming provides a high level language to model problems like the VRP, or even some other domain problems such data mining [START_REF] De Raedt | Constraint programming for itemset mining[END_REF], model checking [START_REF] Esparza | Model checking LTL using constraint programming[END_REF] and QCSP [START_REF] Gent | QCSP-Solve : A solver for quantified constraint satisfaction problems[END_REF][START_REF] Benedetti | QCSP Made Practical by Virtue of Restricted Quantification[END_REF]. This high level language is an advantage to model complex problems and to revise the solutions sought when the model changes. For example, model users' choices on a dynamic network can be complicated. And especially when an unexpected event happens. For instance in, the closed roads have to be removed from the potential solutions. Under the matrix form, all algorithms need to be revised which is a potential source of errors and can be tedious. While with Constraint Programming, it is a bit different : only a constraint forbidding this situation has to be added. The declarative way to express problems makes the revisions easier.

Routing applications try to propose optimal routes to users in order to provide a high level of services. Mono-objective optimization is not suited for this kind of problems. An optimal solution based on one objective may not satisfy the users. In general users care more about their own preferences than a global one. This situation corresponds to a game solution concept which is a Nash equilibrium. A situation is said to be at Nash equilibrium when no player can improve its utility by changing his strategy alone.

Finding a Nash equilibrium is not easy and belongs to the class of NPcomplete problems [START_REF] Gottlob | Pure Nash Equilibria : Hard and Easy Games[END_REF]. This complexity issue makes the brute force methods

Thesis contributions

The main thesis's contribution is to improve the current Constraint Game model from users' experience, by providing a simple and unified representation in constraint solvers. The state of the art algorithm for finding Nash equilibriums is also improved in practice. This contribution comes with a solver which has shown also is applicability to real problem instances in network optimization. In detail, the following outcomes have been achieved :

-A new view of Constraint Games by transparently embedding it into Constraint Programming solvers [START_REF] Palmieri | Constraint Games revisited[END_REF][START_REF] Lallouet | Constraint Games for Modeling and Solving Pure Nash Equilibria, Price of Anarchy and Pareto Efficient Equilibria[END_REF]. We propose to construct for each player a global constraint, which encapsulates its preferences and removes the states which cannot be a Nash equilibrium. In other hand, this transparent view eases the solver maintainability and enables to reuse all recent advances in the field for free. The second contribution is to improve the algorithm from [START_REF] Nguyen | A Complete Solver for Constraint Games[END_REF]. The problem's complexity and more precisely the arc consistency is characterized. Afterwards, we identify the tractable approximations of the problem to define an algorithm which helps to the detection of non solution. The practical interest of such approach has been shown on some classical game theory benchmarks. -A problem coming the from telecommunication area has been solved using the Constraint Games solver. In it, a set of demands (for instance network packets) has to be routed through a network. The goal was to provide a routing minimizing the network's congestion and cost, while each demand has to be routed to its minimum cost individually. Also, networking problems are a large playground for game theory. For instance, in modern applications such the internet, many customers buy bandwidth in the network. The goal is thus to provide a good service to all the users by giving them a high level of satisfaction. Nash equilibriums are well suited for this kind of problems thanks to its stable and its local optimality for all agents. In addition, game theory allows computing measures evaluating the potential of decentralized algorithms against a global optimization problem. We used these measures to evaluate our problems the potential of decentralization. These contributions were published in [START_REF] Palmieri | Constraint Games for stable and optimal allocation of demands in SDN[END_REF] and in [START_REF] Lallouet | Constraint Games for Modeling and Solving Pure Nash Equilibria, Price of Anarchy and Pareto Efficient Equilibria[END_REF]. -A contribution outside this thesis's scope which consists of the study of a heuristic search for constraint optimization problems [START_REF] Palmieri | Objective as a Feature for Robust Search Strategies[END_REF]. In this article, we have shown that using the objective variable within a decision process helps to make better choices.

Thesis organization

The thesis organization is quite classical. A background's overview including Constraint programming and Game theory is given in the two first chapters. Afterward, the following chapters constitute the contributions and can all be read separately. The reader is encouraged to first have a glance at the background before reading the contributions. Three chapters are composing the contributions. The first one focuses on Constraint Games and some modelling aspects. The second contribution presents an elegant way to integrate games in constraint solvers and a new algorithm avoiding to explore non-solutions and its complexity. Finally, the last chapter presents an industrial use case in telecommunication networks. We also provide two appendices. One is presenting the constraint games solver released in open source. The second appendix contains a work which has been done during this thesis but outside its scope. It concerns the usage of the objective variable in constraint optimization problems. The objective variable has been shown as an advantage to solve problems efficiently.

Première partie

Definition 1 (Constraint Satisfaction Problem) A CSP is a pair P = (X, C) where X = {x 1 , x 2 , ..., x n } is a set of variables and C = {C 1 , C 2 , ..., C m } is a set of constraints. A variable x i is associated with a domain D(x i ), representing all of its possible values. A constraint C i contains a set of all its allowed tuples defined over a subset S C i ⊆ X of variables.

A constraint can either be defined explicitly (also called by extension) by providing all the tuples characterizing the constraint solution, or with a formula which defines the constraint. A simple example is the difference constraint which can be expressed in extension with a formula (see Example 1). A solution is a tuple of values (a 1 , a 2 , ..., a n ) such that the assignments x 1 = a 1 , x 2 = a 2 ..., x n = a n respect all the constraints. Example 1 (Constraint example) Suppose you have a problem with 2 variables x 1 and x 2 having as domain the set {0, 1, 2}. A difference constraint is set over x 1 and x 2 . Thus x 1 and x 2 cannot take the same value. Two ways are possible to specify this constraint :

1. in extension by providing all possibles tuples(i.e. constraint' solutions) :

{x 1 , x 2 } ∈ {{0, 1}, {0, 2}, {1, 0}, {1, 2}, {2, 0}}, {2, 1}
2. by a formula :

x 1 = x 2
An objective which has to be optimized can be added to a CSP. A CSP with an objecive is called a Constraint Optimization problem (COP). A COP is useful to rank the solutions or to add preferences between them. A solution with a better objective value is going to be preferred against another one which has a lower objective value.A Constraint Optimization problem (COP) is a pair (P, F O ), where P is a CSP and F O is an objective function that has to be optimized. All solutions to a COP are not equivalent, as their overall quality is determined by the objective value F O (sol).

Example 2 (Map coloring) Imagine we wish to color the map shown in Figure 2.1 with 5 colors or less. This map is made up of 9 countries which have to be colored.

To model this problem we need 9 variables denoted by X {1,2,...,9} to determine each country's color. The domain of each X variable is the set {1, 2, 3, 4, 5}.

The maps' coloration has to respect some constraints : the color of each country has to be different from its neighbors : ∀i, j, i = j ∈ |X| 2 : X i = X j For example, Italy's color has to be different from the country where it has a border such as Switzerland, Austria, and Slovenia.

The problem contains an optimization condition : the number of colors used has to be minimized : minimize (max(X))

This problem can be translated into another domain which is graph theory. This perspective makes the problem easier to understand and to represent. To transfer the problem into graph domain, an incompatibility graph is built (see Figure 2.

2). The graph is constructed such that a vertex represents a country and each border between two countries is symbolized by an edge. More precisely, the

X 1 X 2 X 4 X 5 X 6 X 7 X 8 X 9 X 3 1 2 3 4 5 6 7 1,2,3, 4,5 1,2,3, 4,5 1,2,3, 4,5 1,2,3, 4,5 1,2,3, 4,5 1,2,3, 4,5 1,2,3, 4,5 #var domain 8 9 1,2,3, 4,5 1,2,3, 4,5
Figure

-A graph view of the map coloring problem

nodes X 1 , X 2 , ..., X 9 respectively represent the countries Germany, Czech Republic, Poland, Switzerland, Austria, Slovakia, Italy, Slovenia, and Hungary. The two representations in Figure 2.1a and 2.2 are equivalent.

The solving process for a CSP or a COP generally involves two mechanisms : the filtering and the exploration. The filtering mechanism removes inconsistent variables' values while the exploration enumerates by a search tree the remaining possibilities. #var domain

8 9 4 3 X 1 X 2 X 4 X 5 X 6 X 7 X 8 X 9 X 3 Figure 2.

-An optimal solution for the map coloring problem into graph domain

When a problem is solved with constraint programming three mechanisms have an effect on the performances : the model which determines the search space which has to be explored, the way to explore it and how the inconsistent values are detected by the filtering mechanism. We describe each of these mechanisms and what has been done to improve the efficiency in the following sections.

Modeling

Efficient models drastically impact the solving performances by reducing the search space and also the way to tackle the problem [START_REF] Freuder | Modeling : the final frontier[END_REF][START_REF] Régin | Modeling problems in constraint programming[END_REF][START_REF] Smith | Handbook of Constraint Programming[END_REF]. Building efficient models is not an exact science but it resembles more to art. In other words, given two models solving the same problem, it is impossible to determine which one is going to perform better a priori. The only way to get a comparison is to obtain it experimentally. Nonetheless some general advice about modelling can be given : "less variable is better" or "less constraints is better". Reducing the number of variables is going to curtail the problem size and potentially the search space to explore, while reducing the number of constraints is going to reduce the number of required propagation, which slow down the global process.

However while building a model, this one can still be analyzed to improve it. A way to do that is to capture symmetries.

Symmetries.

In mathematics symmetries are part of group theory. A good analogy between the two fields can be found in [START_REF] Gent | Groups and Constraints : Symmetry Breaking during Search[END_REF]. A symmetry corresponds to identify identical permutation or search state thereafter removing the redundant part. In other words, a problem P can have variables which express the same things or which just corresponds to the same solution or inconsistency, this is called a symmetry (see Example 3).

Example 3 (difference constraint and symmetries) X and Y are two variables which have to be different and have both as domain the set {0, 1, 2}. The possibles solutions are the couples : {{0, 1}, {0, 2}{1, 0}{1, 2}, {2, 0}, {2, 1}} Suppose now that your variables are interchangeable. Then the order does not matter. In that case, you can identify a symmetry over the two variables. For instance the solutions {0, 1}, {1, 0} are symmetric and equivalent. A simple way to break this symmetry is to force an order among the variables. This order can be imposed by the constraint : X < Y Many people have been interested to identify and remove new kinds of symmetries. This includes the exposure of new kind of symmetries [START_REF] Smith | Symmetry and Search in a Network Design Problem[END_REF][START_REF] Gent | Conditional Symmetry Breaking[END_REF][START_REF] Petrie | Symmetry Breaking in Graceful Graphs[END_REF][START_REF] Law | Symmetry Breaking Constraints for Value Symmetries in Constraint Satisfaction[END_REF] and new methods to handle it [START_REF] Ramani | Automatically Exploiting Symmetries in Constraint Programming[END_REF][START_REF] Walsh | General Symmetry Breaking Constraints[END_REF]. Specialization of filtering algorithms were proposed too, to handle symmetries during the filtering step [START_REF] Régin | The Symmetric Alldiff Constraint[END_REF].

Model relaxation

Sometimes building an efficient model is not enough.

Constraints can make the problem impossible or too difficult to be satisfiable. It is said that the problem is over-constrained [START_REF] Van Hoeve | Over-constrained problems[END_REF]. A famous application example is the Radio Link Frequency Assignment problem [START_REF] Cabon | Radio Link Frequency Assignment[END_REF]. From an industrial point of view, finding the optimal solution may not be the first target. Instead, finding at least one solution is very important, and even if this solution may do not be exact, due to the hardness of constraints. Multiples methods have been envisaged to solve such problems like maximizing the number of satisfied constraints (often called MaxCSP [START_REF] Freuder | Partial Constraint Satisfaction[END_REF]). This method was refined by associating a weight to each constraint making the objective to maximize the weighted sum over the satisfied constraints (also called Weighted CSP [START_REF] Larrosa | Node and Arc Consistency in Weighted CSP[END_REF]). Also, in the literature the problem can be found as constraint satisfaction with preferences [START_REF] Rossi | Preferences in Constraint Satisfaction and Optimization[END_REF]. The violation's cost can be also put on the variable assignment itself [START_REF] Beldiceanu | Cost Evaluation of Soft Global Constraints[END_REF]. Another way to handle this, is Possibilistic CSP [START_REF] Schiex | Possibilistic Constraint Satisfaction Problems or "How to handle soft constraints ?[END_REF]. A possibilistic CSP assigns a possibility degree to each constraint expressing how desirable its satisfaction is. More information about these relaxations can be found in [START_REF] Meseguer | Soft Constraints[END_REF].

Propagation and filtering algorithms

The core reasoning of constraint programming is the propagation. It consists into removing inconsistent values of the problem letting only the feasible part remaining.

Filtering algorithm.

A filtering algorithm is associated with a constraint.

It aims to remove inconsistent values from variables' domain (see Example 4) given the constraint relation. A filtering algorithm has to catch the constraint property, to ensure solution's coherence. For instance, the difference constraint in map coloring problem (see Example 4) has to remove the inconsistent value (i.e. the one already taken) and to ensure that a solution respects the difference property.

The global problem's consistency is ensured by the propagation mechanism. The propagation mechanism ensures no more deduction can be made by reaching a fixed point. This is ensured by transmitting those domain reductions through the constraints network. It consists in arranging the propagators' execution, in order to find new value to remove. Usually, it corresponds to store events in a queue in order to check if these newly modifications impact the CSP's state. This process is iterated until no new modification arises, then a fix-point is reached. The propagation mechanism can be variable or constraint oriented. It depends on which event is triggered by the propagation and thus which need to be revised. The variable oriented propagation is shown in algorithm 1. In this algorithm, when a variable is removed from the Queue, all its propagators have to be triggered. This action is done sequentially by the revise function. Then, the newly modified variables have to be added to the queue. The process is stopped when no more variables are in the queue.

Algorithm 1 Variable oriented propagation algorithm

1: Q ← init_queue_with_all_variables() 2: while Q ¬ ∅ do 3: v ← remove(Q) 4: modif ied_variables ← trigger_propagators(v) 5:
Q.enqueu(modif ied_variables) 6: end while Propagators also known as filters are filtering algorithm implementation. Propagators have been studied in a formal way to determine what is a correct behavior and which properties they have to ensure (see definition 2, more details can be found in [START_REF] Schulte | Finite Domain Constraint Programming Systems[END_REF]).

Example 4 (Example 2 continued : filtering algorithm)

The Figure 2.4 summarizes the filtering of the difference constraint. To begin, orange color (value 1) was given to the node 5. This modification is propagated to the other variables through the constraints network in order to remove inconsistent values. Since the connected vertices have to be different, then the value 1 is removed from the domain of X 1 , X 2 , X 4 , X 6 , X 7 , X 8 and X 9 .

Definition 2 (Propagator properties)

In order to make constraints propagation well-behaved propagators are decreasing and monotonic.

X 1 X 2 X 4 X 5 X 6 X 7 X 8 X 9 X 3 1 2 3 4 5 6 7
1,2,3, Also, different filtering algorithm may have different filtering power. The filtering algorithm can be simple such as a simple deletion for impossible values or may be more complex like the AllDiff constraint (also called difference constraint) [START_REF] Régin | A Filtering Algorithm for Constraints of Difference in CSPs[END_REF]. The latter is implemented by a matching algorithm in a bipartite graph. When the filtering algorithm has been triggered, the cost to run it is a bit more but it allows to prune sometimes exponential parts of the search space. The Alldiff constraint [START_REF] Régin | A Filtering Algorithm for Constraints of Difference in CSPs[END_REF] was the first global constraint. A constraint is said to be global if its scope has an unfixed number of variables. The difference constraint has shown that a global point of view can help to find a stronger algorithm to filter inconsistent values and thus be more efficient while solving problems. However, it is not always the case and depends on how the constraint can be decomposed [START_REF] Narodytska | Reformulation of global constraints[END_REF][START_REF] Bessiere | Circuit Complexity and Decompositions of Global Constraints[END_REF]. Decomposing a global constraint can bring some benefits from multiples point of view : developer does not need to implement new constraints and can reuse the previous codes. Also, a decomposition can be more efficient than the original global constraint because the constraint is going to be awaken fewer times. All these concepts rely on the filtering power (also called consistency) of the decomposition which itself depends on the constraint's decomposability.

Consistency

Filtering algorithms can act differently to provide different filtering power. This concept is called consistency [START_REF] Mackworth | Consistency in Networks of Relations[END_REF][START_REF] Bessiere | Constraint Propagation[END_REF]. The consistency is a widely studied topic. Most of the time, it is a compromise between exploration's speed of new nodes and a stronger but slower filtering algorithm which is going prune more the search space. Multiples kinds of consistencies exist. The most known are the bound consistency and arc consistency.

Definition 3 (Arc consistency)

A CSP is said to be arc consistent if for all couple of variables (X i , X j ), i, j ∈ X, i = j, and ∀v i ∈ D(X i ), it exists a value v j ∈ D(X j ) such that the instantiation {(X i , v i ), (X j , v j )} satisfies all the constraints.

Note that if you consider each constraint alone (i.e you do not intersect constraint together, or add objective in consideration), then the arc consistency is the highest reachable consistency.

Definition 4 (Bound consistency)

A constraint is said bound consistent iif ∀x ∈ X, the domain's upper bound x and the domain's lower bound x are a support in C(X). A constraint network is said bound consistent if all its constraint in it are bound consistent.

Higher degree of consistencies have shown promising results to solve some problems like in graphs [START_REF] Bliek | Path Consistency on Triangulated Constraint Graphs[END_REF][START_REF] Hell | Duality and polynomial testing of tree homomorphisms[END_REF]. Ones of the most famous are the k-consistency, Path consistency which is a special case of k-consistency [START_REF] Mackworth | Consistency in Networks of Relations[END_REF] and the Singleton Arc consistency (SAC) [START_REF] Prosser | Singleton Consistencies[END_REF]. This last one has received more attention this recent years by being practically improved by restricting the consistency procedure [START_REF] Wallace | Neighbourhood SAC : Extensions and new algorithms[END_REF][START_REF] Paparrizou | On Neighborhood Singleton Consistencies[END_REF].

Definition 5 (Singleton arc consistency) The value a of a variable x i is singleton arc consistency if and only if the problem restricted to x i = a is arc consistent. A CSP is singleton arc consistent if every value of every variable is singleton arc consistent.

The consistency for satisfaction is not the only topic studied for propagators. Instead, while solving a COP the objective value can be back-propagated to prune more the search space. Specialized filtering algorithms taking into account the objective value have been proposed. For instance the global cardinality constraint [START_REF] Régin | Arc Consistency for Global Cardinality Constraints with Costs[END_REF], in routing problems [START_REF] Sellmann | Cost-based Filtering for Shorter Path Constraints[END_REF][START_REF] Gualandi | Resource Constrained Shortest Paths with a Super Additive Objective Function[END_REF], in problem where the objective is express through a sum constraint [START_REF] Régin | Inequality-sum : a global constraint capturing the objective function[END_REF] and for the round robin problem [START_REF] Henz | Global constraints for round robin tournament scheduling[END_REF]. A more general approach was proposed in [START_REF] Focacci | Cost-Based Domain Filtering[END_REF] and relies on global constraint linear relaxation in order to have a bound provided by the dual of linear programming.

Exploration

When solving a problem, the propagation mechanism alone maybe not powerful enough to find a solution or to prove a dead end. In such case, an exploration of the remaining space has to be done. Many algorithmic techniques and their variants exists to explore the search space : backtracking search, local search and dynamic programming. We review here the different main techniques used to explore the search space.

Systematic search and heuristics

A backtrack search [START_REF] Golomb | Backtrack Programming[END_REF] is a search procedure to solve combinatorial problems. The simplest version of backtracking search builds a search tree associated with a Dept First Search algorithm (DFS). This search tree begins at the root node with an empty set of decisions. Then the successors nodes are construct with respect to the decisions. A decision can be anything which reduces the problem, three ways are most used :

-enumeration : creates as many branches as the number of possible value for the selected variable -binary choice : instantiates a variable to one of its possible value. Then, when the decision is backtracked, the opposite choice is considered, e.g. if the decision in an assignment to a value, then the opposite choice is going to be the current domain without this value.

-domain splitting : separates the variable's domain into two sets which do not necessarily instantiate a variable.

Note that a variable which is already instantiated cannot be part of a decision. A naive way to use backtracking search is just to consider lexicographic order to select the couple (variable/value). This ordering is called search strategy, heuristic or even sometimes branching rule. An example of the execution of a backtracking algorithm is given in Example 5.

Example 5 (Search tree exploration) This example does not show a complete tree but instead how the exploration and propagation work. It is built on the map coloring example (see example 2). The search tree (see Figure 2.5(g)) is

built by giving the references to the corresponding images. The initial step (Figure 2.5(a)), shows the triggering of the initial propagation which detects no inconsistent values. Since a fixed point is reached, and nothing more can be deduced, an exploration is done in order to solve the problem.

The first strategy's decision is shown in Figure 2. 5(b). It selects the variable X 5 and assigns it a value of 1. Then, this decision is propagated, removing the impossible values : 1 is removed from all the neighbors of X 5 . Note that the negated decision and its propagation corresponds to the Figure 2.5(c). This negated decision is taken into account when the DFS algorithm is going to backtrack from the state shown in Figure 2. 5(b). Again, a fix-point is reached conducting the exploration be continued since not all variables are instantiated. Afterwards, X 1 is instantiated to the value 2 (see Figure 2.5 (d)), and again this decision is propagated through the neighbourhood of the variable yielding to remove the value 2 from the domain of the variable X 2 , X 3 and X 4 . Few steps later (see 2.5(f)) , a solution is found. This solution corresponds to the optimal one like shown in example 2.

The ordering has a huge impact on the resolution time either to find a solution or to completely explore the search space [START_REF] Smith | Value Ordering for Finding All Solutions[END_REF][START_REF] Palmieri | Parallel strategies selection[END_REF]. Heuristics can be divided into two categories : dedicated searches which are specialized for one given problem. Often dedicated searches exploit problems structures and problems' knowledge unknown by the solver. This knowledge is required to solve industrial problems. Dedicated heuristics have been applied to a wide range of problems including scheduling [START_REF] Vilim | Failure-Directed Search for Constraint-Based Scheduling[END_REF], network design [START_REF] Le | Robust and Parallel Solving of a Network Design Problem[END_REF], traveling salesman problem [START_REF] Fages | The salesman and the tree : the importance of search in CP[END_REF], software defined network [START_REF] Palmieri | Constraint Games for stable and optimal allocation of demands in SDN[END_REF], rectangle packing [START_REF] Simonis | Search Strategies for Rectangle Packing[END_REF] and many others. However, such problem's knowledge, while appealing, is not always available nor possible. That is one of the main motivations for the development of black-box constraint solvers. In such solvers, a generic search is provided, letting only as a concern to users to build an efficient model. The first autonomous search was based on the first fail principles [START_REF] Robert | Increasing tree search efficiency for constraint satisfaction problems[END_REF][START_REF] Barbara | Trying harder to fail first[END_REF] where the goal is to try to fail as soon as possible in the exploration in order to reduce the search tree size. Knowing how to fail as soon as possible cannot be computed efficiently in practice and relies on criterion like selecting the variable having the smallest domain size. Notwithstanding the experimental efficiency of such criterion, the complexity of CSP, which are generally NP-complete makes theses criterion being heuristic. In other words, it does not exist a unique criterion : some are going to perform well in some kind of problems while others will have better performances in others. A lot of attention has been put to find new criterion to solve more efficiently some problems [START_REF] Lecoutre | Reasoning from last conflict(s) in constraint programming[END_REF][START_REF] Pesant | Counting-Based Search : Branching Heuristics for Constraint Satisfaction Problems[END_REF][START_REF] Gay | Conflict ordering search for scheduling problems[END_REF][START_REF] Palmieri | Parallel strategies selection[END_REF][START_REF] Zitoun | Search strategies for floating point constraint systems[END_REF][START_REF] Fages | Making the first solution good ![END_REF][START_REF] Palmieri | Objective as a Feature for Robust Search Strategies[END_REF]. Notably, in Constraint Programming, activity-based search (ABS) [START_REF] Michel | Activity-based search for black-box constraint programming solvers[END_REF], impact-based search (IBS) [START_REF] Refalo | Impact-Based Search Strategies for Constraint Programming[END_REF] and weighted degrees (Wdeg) [START_REF] Boussemart | Boosting systematic search by weighting constraints[END_REF] are well known state-of-the-art search strategies for combinatorial problems. Three state-of-the-art Search Strategies are briefly described here. All these strategies share a common procedure, the value of variable is selected such that a solution can be quickly found, while the variable selection tries to minimize the search tree. For a more complete description please refer to their original publications. [START_REF] Refalo | Impact-Based Search Strategies for Constraint Programming[END_REF] selects the variable whose choice is expected to provide the largest search space reduction. IBS considers the cardinality ratio reduction of the Cartesian product of the domains (called the impact). Thus the main feature of this Search Strategy uses variables' domains.

Impact Based Search (IBS)

More formally, let x be a variable, and v be a value belonging to the current domain D(x). Let P bef ore (resp. P af ter ) be the cardinality of the Cartesian product

X 1 X 2 X 4 X 5 X 6 X 7 X 8 X 9 X 3 1 2 3 4 5 6 7
1,2,3,

X X 4 X X 6 X 7 X X 9 X 3 X 1 X 2 X 4 X 5 X 6 X 7 X 8 X 9 X 3 1 2 3 4 5 6 7 4,5 1,2,3, 4,5 1,2,3, 4,5 1,2,3, 4,5 1,2,3, 4,5 1,2,3, 4,5 1,2,3, 4,5 #var domain 8 9 1,2,3, 4,5 1,2,3, 4,5 1 2 3 4 5 6 7 1,2,3, 4,5 1,2,3, 4,5 1,2,3, 4,5 1,2,3, 4,5 1,2,3, 4,5 1,2,3, 4,5 1,2,3, 4,5 #var domain 8 9 1,2,3, 4,5 1,2,3, 4,5 1 2 3 4 5 6 7 1,2,3, 4,5 1,2,3, 4,5 1,2,3, 4,5 1,2,3, 4,5 1 1,2,3, 4,5 1,2,3, 4,5 #var domain 8 9 1,2,3, 4,5 1,2,3, 4,5 X 1
X 2 X 4 X 5 X 6 X 7 X 8 X 9 X 3 1 2 3 4 5 6 2 1,2,3, 4,5 1,2,3, 4,5 1,2,3, 4,5 1 1,2,3, 4,5 1,2,3, 4,5 #var domain 8 9 1,2,3, 4,5 1,2,3, 4,5 X 1
1,2,3,

X X 4 X X 6 X 7 X X 9 X 3 1 2 3 4 5 6 4,5 1,2,3, 4,5 1,2,3, 4,5 1,2,3, 4,5 1 1,2,3, 4,5 1,2,3, 4,5 #var domain 8 9 1,2,3, 4,5 1,2,3, 4,5 X 1
X 4 X 5 X 6 X 7 X 8 X 9 X 3 X 1 1 2 3 4 5 6 7 2 3 1 4 1 2 3 #var domain 8 9 4 3 X 1 X 2 X 4 X 5 X 6 X 7 X 8 X 9 X 3 b) a) c) d) e) f) a c d e f b g) Figure 2 7 1,2,3, 4,5 1,2,3, 4,5 1,2,3, 4,5 1,2,3, 4,5 1 1,2,3, 4,5 1,2,3, 4,5 #var domain 8 9 1,2,3, 4,5 1,2,3, 4,5 X 2
.5 -Search tree of the domains before (resp. after) the application of the decision x = v. The impact of a decision is :

I(x = v) = 1 - P af ter P bef ore
Let Ī(x = v) be the average impact of the decision x = v. Then, this impact of a variable x with current domain D(x) is computed by the following formula :

Īx = v∈Dx 1 -Ī(x = v)
At each node, the free variable having the largest impact is assigned to its value having the smallest impact. Note that this search is an adaptation of pseudo-cost-based search from mixed integer programming.

Activity Based Search (ABS) [144]

selects the most active variable per domain value. A variable's activity is measured by counting how often its domain is reduced during the search. Thus, once again, the feature of this Search Strategy uses the domains of the variables. More formally, the number of modification of the variable x is monitored and stored in A(x). A(x) is updated after each decision with the following rule :

∀x ∈ Xs.t.|D(x)| > 1 : A(x) = A(x) × γ ∀x ∈ X 0 : A(x) = A(x) + 1
X 0 represents the set of variables reduced by the decision and γ ∈ [0, 1] is the decay parameter. ABS maintains an exponential moving average of activities by variables' value. At each node, ABS selects the variable with the highest activity and the value with the least activity.

Weighted Degree (WDeg) [START_REF] Boussemart | Boosting systematic search by weighting constraints[END_REF] uses the constraint graph to make de- cisions. WDeg counts the number of failures ω c for each constraint c . WDeg features are the constraint graph and the fail counters. WDeg first computes, for each variable x, the value wdeg(x), which is the weighted (ω) sum of the constraints involving at least one non-assigned variable. WDeg then, selects the variable having the highest ratio |D(x)| wdeg(x) .

Portfolio method. New heuristics' interest is not limited to only solve more efficiently some classe of problems. Actually, a practical interest coming from economics exist. In economics, a portfolio is a financial product which tries to provide the best and safest investment by betting on multiples stocks option. Portfolios methods were built because the trading market is not predictable so it is unknown how to invest money. To mitigate an investment and decrease the possible losses bet is done on multiples options. In combinatorial optimization, this kind of reasoning is applied and was first brought in [START_REF] Bernardo A Huberman | An economics approach to hard computational problems[END_REF]. The strategies have different performances on different problems. The minimal possible run-time of the three strategies is obtained by taking the minimum run time of all of them at each time. Basically by running these three strategies in parallel the run time corresponds to the minimum of all the strategies. What is important to underline is that no strategy is dominating another one.

The expected speedup can be supra linear [START_REF] Hamadi | Combinatorial Search -From Algorithms to Systems[END_REF]. With this method, higher performances are reaches when the chosen heuristics are orthogonal. This technique was brought to the fore when SATZilla [START_REF] Xu | SATzilla : Portfolio-based Algorithm Selection for SAT[END_REF] the first solver adopting a portfolio approach has won many prices at the SAT competition. An excellent survey about algorithm selection problem can be found in [START_REF] Kotthoff | Algorithm Selection for Combinatorial Search Problems : A Survey[END_REF]. Also this variability among the different method brought different studies, notably one which underlined the heavy tail phenomena [START_REF] Gomes | Heavy-Tailed Phenomena in Satisfiability and Constraint Satisfaction Problems[END_REF]. In fact, some researches have put in evidence that ideally, it exists a subset of variables to instantiate making the problem easier to solve [START_REF] Kautz | Dynamic Restart Policies[END_REF]. This has motivated the ideas of restarts. A restart consists in make multiples short runs during the search in order to learn features or criterion about the problem. This learning step is then useful to consider earlier the variables making the problem harder [START_REF] Kautz | Dynamic Restart Policies[END_REF]. Also nogood can be learned from failures. During the exploration, the search strategy detects inconsistencies (i.e. a set of couples (variable/value)). This chain of affectations is called nogood. Nogood can help to solve more efficiently a problem by detecting inconsistencies which have been learned previously. Learning nogoods in general is a difficult task. The required space is exponential. Researches have been done in that sense to compress the representation as well as to deduce more thing from conflicts [START_REF] Dechter | Learning While Searching in Constraint-Satisfaction-Problems[END_REF][START_REF] Katsirelos | Generalized NoGoods in CSPs[END_REF][START_REF] Lecoutre | Recording and Minimizing Nogoods from Restarts[END_REF]. Coordination between the search, nogoods learning and restart have been actively studied to improve searches efficiency [START_REF] Jimmy | Increasing Nogoods in Restart-Based Search[END_REF][START_REF] Glorian | Combining Nogoods in Restart-Based Search[END_REF].

Other backtracking search and methods

Since the first backtracking algorithm [START_REF] Golomb | Backtrack Programming[END_REF] multiples revisions and possible improvements of backtracking algorithms were proposed. Dynamic backtracking [START_REF] Matthew | Dynamic Backtracking[END_REF] is a way to avoid to explore the same dead end in the search tree by using nogoods. Ginsberg's dynamic backtracking algorithm (DBT), always puts the variable that has most recently been assigned a value on the right-hand side of the implication and only keeps nogoods whose left-hand sides are currently true. In this method, a nogood is deleted once the left-hand-side implication contains more than one variable-value pair that does not appear in the current set of assignment. The required space to implement dynamic backtracking is o(n 2 d). A generalization was proposed in [START_REF] Bayardo | A Complexity Analysis of Space-Bounded Learning Algorithms for the Constraint Satisfaction Problem[END_REF] to the i t h variable. The complexity analysis states that storing all nogoods is not tractable due to the space requirement.

Limited Discrepancy Search(LDS) [START_REF] William | Limited Discrepancy Search[END_REF] is another backtracking search. Given a heuristic, LDS explores the search tree by considering first the heuristic choices which are not the negations. LDS explores the search space until the limit of negation allowed have been explored. For a given binary heuristic, it is assumed that a left branch is the choice made by the heuristic while the right branch is the negation and thus a default choice. LDS considers that a heuristic guides well the exploration and thus explores first the part which is the most promising regarding the heuristics decisions. In other words, the negation are not the good decisions to continue. The explored branches are going to be explored by increasing number of negations. The first branch is the one having only left branches, the seconds are going to be the ones having chosen exactly one right branch etc. Another version of LDS but bounded was proposed in [START_REF] Walsh | Depth-bounded Discrepancy Search[END_REF].

Other backtracking techniques were proposed, notably an Hybrid Best-First Search [START_REF] Allouche | Anytime Hybrid Best-First Search with Tree Decomposition for Weighted CSP[END_REF] which combine Depth first search usually done by simple backtracking and Best first search.

MDD solvers

In recent years, another sub-paradigm of search space explo- ration was proposed. Multivalued Decision Diagram (MDD) is a compressed data structure. MDDs are interesting because they provide fast operations [START_REF] Perez | Efficient Operations On MDDs for Building Constraint Programming Models[END_REF] which most of the time are linear. Fast operation, in addition with efficient construction [START_REF] Perez | Constructions and In-Place Operations for MDDs Based Constraints[END_REF] has shown promising result in solving multiples real-life problems [START_REF] Bergman | Decision Diagrams for Optimization[END_REF][START_REF] Kell | An MDD Approach to Multidimensional Bin Packing[END_REF][START_REF] Roy | Enforcing Structure on Temporal Sequences : The Allen Constraint[END_REF].

Local search

Many world applications cannot be solved by a complete and systematic search. Local search methods are very famous to solve Constraint Satisfaction Problems, because of their efficiency and thus despite their incompleteness (see [START_REF] Holger | Local Search Methods[END_REF][START_REF] Van | Constraint-based local search[END_REF] ). In opposition to a complete and systematic search used by the combination of a search strategy and a DFS algorithm, a local search is able to explore more diverse space in a given amount of time. While a complete and systematic search has to explore an entire sub-tree before exploring another part, a local search is able to modify at any time, any choice during its decision process. Therefore, a local search can revise earlier a bad decision compared to a systematic search.

Many applications have been successfully solved with local search methods, including vehicle routing [START_REF] Shaw | Using constraint programming and local search methods to solve vehicle routing problems[END_REF] and job-shop scheduling [START_REF] Beck | Combining constraint programming and local search for job-shop scheduling[END_REF].

Local Search techniques are based on a simple and general idea : For starting, an initial point which is a complete variables assignment is randomly chosen. Then it iteratively moves to a neighbor solution. Deciding which neighbor will be chosen is performed by an evaluation of a heuristic function. The process is iterated until a termination criterion is reached. It could be the detection of a solution or user-specific such as the max steps or time exceeded. Game theory is a successful paradigm to model interactions between multiples agents. Originally formalized in [START_REF] Zermelo | Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels[END_REF][START_REF] Von | Theory of Games and Economic Behavior[END_REF], game theory has found early some applications in economy [START_REF] Matthew | Social and Economic Networks[END_REF], politics [START_REF] Steven | Game theory and politics[END_REF], wireless network [START_REF] Charilas | A survey on game theory applications in wireless networks[END_REF]. Even a biologist, John Maynard Smith was rewarded for his work using game theory [START_REF] Maynard | Evolution and the Theory of Games[END_REF]. The central notion in game theory is game in which the strategic behaviors are represented. Game theory provides an analytic framework to analyze it. The analysis of strategic behavior(like in games) happens more than it is though. Daily life choices involve decision making process (like in Example 7). This process depends on the knowledge about the situation, the possibles cooperation etc. In this chapter, game theory background is provided to understand our contributions.

Taxonomy of game's Categories

A game is the central notion in game theory. It represents a situation in which a set of players (also called agents) have to decide an action (or strategy) among a possible set. When all players have chose their strategy, they are given a reward (also called utility).

Definition 6 (Game)

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

-P is a finite set of players. -A = (A i ) i∈P where A i = ∅ 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 = (s i ) i∈P where s i ∈ A i . The set of strategy profiles is denoted by A P . -u = (u i ) i∈P where u i : A P → R is the utility function of player i.

Example 7 (Introductory example : Battle of the sexes)

The Battle of the sexes [START_REF] Osborne | A Course in Game Theory[END_REF] is a game composed of two players. A couple has planned to go out at evening. The wife would like to go to the opera, while the husband wants to watch soccer on TV. They can go to different places, but they rather prefer to stay together. They did not choose yet where to go and cannot communicate together. Knowingly of this situation they have to go somewhere and hopping to find each other.

Besides the mathematical definition of a game, its nature and how it can be studied is dependent on multiples concepts. The different point of views such the interactions and the possible games' knowledge are described here.

Players interactions : static and dynamic

Games can be played with different interactions modes between players. The interactions specify how a game is played. Two mains modes exist : static and dynamic games.

A game is said to be static (also called simultaneous) if the players' strategies are played only once, and simultaneously. The Example 8 shows the battle of the sexes (Example 7 continued) as a static game.

Example 8 (Example 7 continued as a static game)

The battle of the sexes shown previously is traditionally a static game. It is played once and players chose the actions at the same time. The players' payoffs and the possibles actions characterizing the game are described here.

-P = W, M Unlike static games, dynamic games have a sequence of actions, i.e. a player will chose an action before the other ones choose theirs.

A simple and well know dynamic game is the "Tic Tac Toe". In this game, two players have to choose a sequence of moves in order to win. The first player succeeding to align 3 circles or crosses in a row, a column or a diagonal wins. The game can be finished on a draw, if no player can put 3 elements contiguously. An example of "Tic Tac Toe" progress is shown in the Figure 3.1. First the player playing cross begins, then it is the turn to the one playing circle and so on, until the end of the game is reached.

Cooperation and selfishness

Game theory focuses on studying problems in which players' goals depend on others players' actions. A crucial characteristic to identify is thus cooperation between players. Mainly two kinds of behaviors have been studied : cooperation and selfishness. In cooperative games, several players may collaborate to achieve their goals together. In opposition, in non-cooperative games, all players are self-interested and focus only on their goals. Each player just wants to optimize his own utility no matter what happens with the others Non-cooperative games, which are a crucial class in game theory, capture many research interests. A simple example of non-cooperative game has been shown in Example 7.

Cooperative game theory (also called coalition game) provides an approach to analyze and to describe a structural behavior of players and their payoffs. Cooperative game theory analyzes the behavior of player when they can build coalitions. A coalition is simply a subset of the set of players coordinating their strategies in order to play. In a coalition, the players agree on how the total payoff is to be divided among the members. A cooperative game [START_REF] Sh Driessen | Cooperative games, solutions and applications[END_REF] consists of a set of players plus a characteristic function specifying the value created by the different coalitions in the game.

Example 9 (Battle of the sexes as a collaboration game)

The Battle of the Sexes shown in Example 7 is adapted here as a cooperative game :

-P = {Husband, W if e} -There are 3 possible coalitions : C 1 = {wif e} and C 2 = {man} and

C 3 = {wif e, man}
-the utility function of each coalition is :

-v(C 1 ) = (v W if e ) where v W if e = 0 ∨ v W if e = 2 ∨ v Husband = 3 -v(C 2 ) = (v Husband ) where v Husband = 0 ∨ v Husband = 2 ∨ v Husband = 3 -v(C 3 ) = (v W if e , v Husband ) where v i = 2 ∨ v i = 3 =3
As opposition to the classical battle of the sexes, when a coalition is formed by the man and the wife, then they do not consider anymore to go somewhere where the other is not. Going alone somewhere, is dominated by going anywhere together.

Game's knowledge

Another important point is how the players know what happens in the game. In fact, two levels of knowledge exist : the one about the others players and the knowledge about the game itself.

In a game with imperfect information, players are simply unaware of the actions chosen by the other players. However, it is known who is participating to the game, the possibles strategies and the possible players' preferences. In incomplete information games, players may or may no the other players' strategies and preferences. The Example 10 illustrates these by different situations based on the Battle of the sexes Example 10 (Battle of the sexes with different knowledge) Four different situations of the battle of the sexes are given here to understand the impact of imperfect and incomplete information in games.

-Imperfect and incomplete information : The Wife(resp Husband) does not know if the Husband(resp Wife) is part of the game and his preferences.

-Perfect and incomplete information : The Wife(resp Husband) is part of the game but her(resp his) preferences are not known.

-Imperfect and complete information : The Wife(resp Husband) does not know if the Husband(resp Wife) is part of the game but knows her (resp his) preferences.

-Perfect and complete information : Everything is known : who is part of the game and the preferences.

This section has given the different games models and situation which are well known, in the next section we are going to see how to represent games.

Games' representations

Uniform representations are required to use algorithm in games. Until now, the representation of games was not evoked. In this section, the techniques used to represent games are listed. Especially the ones which are fully expressive, which means that any game can be represented in it.

Extensive representations

In this section we list the extensive representation (i.e. where all the possibilities are listed).

Normal form

The standard game representation of a static game is normal form [START_REF] Fudenberg | Game Theory[END_REF], which is an n-dimensional matrix stating all utilities of all players for all joint strategy profiles in the game. Also, in a sense, the normal form is the most fundamental representation in game theory, because of the others representations of finite games can be encoded in it. An example of normal form representation is given in the Figure 3.2. It corresponds to the Battle of the sexes as shown in Example 7. The possible actions of the Wife (name W here) are O and S on the columns, while the possible actions of Husband (named H here) are the ones on the lines. In an informal way, the player M is going to choose the column, while the W one is choosing the line. Their decisions are going to characterize their rewards. For instance, when W and H choose O and P , they are going to be respectively rewarded by 3 and 2. The Wolf Lamb Cabbage Game is described into numerical preferences in the Example 11.

Example 11 (Wolf Lamb 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. The action of P coming to the party corresponds to p and the reverse to p.

-P ={ W, L, C} where W , L and C represent respectively the Wolf, Lamb and Cabbage. -Players can either choose to come to the party which corresponds to p or the reverse p. For each agent we respectively denote for the Wolf, the Lamb and the Cabbage their actions by w, l, c.

-u W (w, l, c) = 1, u L (w, l, c) = 0, u C (w, l, c) = 0...
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 × 2 3 = 24 integers. We intentionally do not combine all the players into on big matrix in order have a better understanding of the example and the required size.

The normal form is fully expressive but not compact. For instance, to represent a game composed of 100 players and all having only 2 strategies, the normal form requires to store 100 2 numbers. But it is not the only weakness, games become totally unstructured and flat complicating their modelling especially for big games.

-WLC game in normal form

As mentioned earlier, representing a game can be challenging in term of memory. This need brought people to find new compact representation like Graphical games [START_REF] Michael | Graphical Models for Game Theory[END_REF] or Action Graph Games [START_REF] Jiang | Action-Graph Games[END_REF]. These representations factorize the normal form by catching a property and are able to compact it.

Graphical game :

A graphical game only represents the useful interactions between players. In other words, if two players' actions are independent, then, in a graphical game, the action are not directly stored. Graphical games are kind of reduced normal form embedding a graph indicating how and which players interact together. The graph which represents the interaction is constructed such that each vertex is a player and a player is linked into another one if its utility depends on the action of the other player. Any node of the graph (or player) has a local matrix which depends on the interactions between the other players (i.e. its neighbors).

Example 12 (Wolf Lamb Cabbage game as a graphical game) 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.4. 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. Also, there is no more need to store the preferences of the cabbage since it has always the same preference.

The required matrices are now :

The memory consumption of graphical games is reduced only if the largest neighbors degree d is inferior to the number of players n. Hence, if d ≪ n, then the graphical representation is significantly more compact than the normal form.

Wolf

Goat Cabbage Lamb's payoff However, it also means that this representation does not fit well to games that are not separable, i.e. when there exists a full interaction between all players. In this games, the size would exactly the same as the normal form size.

Action graph game

Action Graph Game (AGG) is a representation fully expressive and at least as compact as graphical games. AGGs catch symmetries of interactions between players and compacts their identical strategies. This is useful for specific kind of game where the players' utilities do not depend on who is taking the action but instead on the number of players choosing an action. These kind of games are called anonymous. AGGs are represented thought a directed graph with a set of nodes A, a set of edges E, and a set of agents N = {1, ...n}. Identical tokens are given to each agent i ∈ N . To play a game, each agent i simultaneously places his token on a node a i ∈ A i , where A i ∈ A . Each node in the graph corresponds to an action available to one or more of the agents. Each agent's utility is calculated according to an arbitrary function of the node he chooses and the numbers of tokens placed on the neighbor'nodes. The WLC game in AGG form is given in Example 13.

Example 13 (Wolf Lamb Cabbage as an AGG)

The Wolf, Lamb, and Cabbage have to choose among their respective actions on their set of nodes A W , A l and A C . They can either choose to come (e.g. W ) or not (e.g. ¬W by placing a token on their corresponding node. Then a function on each node is going to compute the utility knowing the actions of the neighbors. For instance, in the figure 3.5 the set of actions for the Wolf denoted by A W are {W, ¬W }. He can either place a token on W or on ¬W to determine if he comes or not. Afterwards, his reward is going to be computed according to the choices of its neighbors nodes. For instance if the Wolf choose W then his rewards depend on l or ¬l, depending on where the Lamb has put his token.

Combinatorial games

In this part, game's representations coming from combinatorial techniques are presented. Two main approaches exist : Boolean Games based on Boolean satisfiability (or SAT) theory and Constraint Games based on constraint programming (see Chapter 2). Only Boolean games are presented, instead, the chapter 4 is dedicated to the Constraint Games which is the approach used in our contributions. We also refer the Distributed Constraint Optimization Problems(DCOP) which can sometimes resemble or solve the same problematic as in game theory. Compactness is one of the main advantages of such approaches. The players' utilities are not directly stored but instead formulas are provided to compute it on fly. Also, the resolution system relies on solvers, which are optimized to be efficient at solving combinatorial problems.

Boolean games

Boolean games were initially proposed in [START_REF] Harrenstein | Boolean Games[END_REF]. In such games, each player own a set of variables and a SAT problem which defines its satisfaction.

Definition 7 (Boolean games)

A boolean game is a 3-tuple (P, V, Σ) where :

-P = {1, ..., n} is a finite set of players -V = (V i ) i∈P such that i = j ↔ V i ∩ V j = ∅ where V i is a set of propositional
variables controlled by player i -Σ = {φ 1 , ..., φ n } is the set of goals, where each φ i is a satisfiable formula for player i

The WLC game in a Boolean game form is presented in the Example 14.

Example 14 (Example 11 as Boolean game)

The WLC game can be express by a Boolean Game. First, it can be underlined that each player has only two strategies and dichotomic preferences, thus making this problem expressible with boolean games [START_REF] Harrenstein | Boolean Games[END_REF][START_REF] Bonzon | Boolean Games Revisited[END_REF]. We name x W , x L and x C the respective optimization variables of Wolf, Lamb and Cabbage. Then we can state using boolean algebra notations : x W = wl, x L = wlc + wl and x C = 0.

Logical propositions can sometimes be not enough to properly provide a compact representation, that's why boolean games preferences were extended with CP-net [START_REF] Boutilier | CP-nets : A Tool for Representing and Reasoning with Conditional Ceteris Paribus Preference Statements[END_REF][START_REF] Bonzon | Compact Preference Representation for Boolean Games[END_REF]. Boolean games concentrate a lot of attention these last years. Especially by adapting some well known results of game theory. For instance dependencies of graphical games to Boolean games [START_REF] Bonzon | Dependencies between players in Boolean games[END_REF], cooperative Boolean games [START_REF] Dunne | Cooperative Boolean games[END_REF], iterative Boolean games [START_REF] Gutierrez | Iterated Boolean Games[END_REF], incomplete or imperfect information [START_REF] Grant | Manipulating Boolean Games through Communication[END_REF][START_REF] De | Modelling incomplete information in Boolean games using possibilistic logic[END_REF] or even possibilitic games [START_REF] De | Possibilistic Boolean Games : Strategic Reasoning under Incomplete Information[END_REF]. New concepts were also envisaged. The structure provided by combinatorial games made people think differently and that why some concepts emerged like partial cooperation between player [START_REF] Grubshtein | Partial Cooperation in Multi-agent Local Search[END_REF] or the concept of variables' control [START_REF] Gerbrandy | Logics of propositional control[END_REF][START_REF] Belardinelli | Relaxing Exclusive Control in Boolean Games[END_REF][START_REF] Wiebe Van Der Hoek | On the logic of cooperation and propositional control[END_REF] which is also related to imperfect information or partial collaboration.

Distributed Constraint Optimization Problem (DCOP).

Distri- buted Constraint Optimization Problem consists of a distributed optimization problem through agents. The main concern of such approach is to keep privacy of agents' preferences (or variable assignment). In such representation, a search is done by passing message (usually preferences) between agents in order to agree on a solution.

A Distributed Constraint Optimization Problem is defined by a set of agents controlling each a set of variables defined over a domain. Each variable assignment is defined by a cost and an operator that aggregates all of the individual costs for all possible variable assignments. The objective of a DCOP is to have each agent assigned values to its associated variables in order to either minimize or maximize a cost for a given assignment of the variables. Multiples questions related to game theory were tackle by DCOP and its asymmetric variant like the solution sought : Nash equilibrium [START_REF] Litov | Distributed Search for Pure Nash Equilibria in Graphical Games : (Extended Abstract)[END_REF][START_REF] Grubshtein | Finding a Nash Equilibrium by Asynchronous Backtracking[END_REF][START_REF] Grinshpoun | Asymmetric Distributed Constraint Optimization Problems[END_REF][START_REF] Levit | Distributed Constrained Search by Selfish Agents for Efficient Equilibria[END_REF]or even mechanism design [START_REF] Levit | Distributed Constrained Search by Selfish Agents for Efficient Equilibria[END_REF].

Solution concept and their algorithms

So far, the solutions in games have not been expressed. In games, solution concepts (also called equilibrium) have been discussed for decades, resulting in many solutions concepts with different properties [START_REF] Osborne | A Course in Game Theory[END_REF]. One of the most fundamental equilibria is the Nash equilibria [START_REF] Nash | Non-cooperative Games[END_REF], which models a situation where no player has an incentive to change his decision unilaterally. Finding a Nash equilibrium is a satisfaction problem in which players are in a best response statement. In other words, it consists in finding a state where no players can improve its current satisfaction by changing alone its strategy. In this thesis, we focus only on Pure Nash equilibrium because it has the advantage of giving a deterministic decision for the players and thus being easily applicable in real world applications. Various other solution concepts have been proposed in the literature. Among them the most popular are : the mixed Nash equilibrium [START_REF] Nash | Non-cooperative Games[END_REF], Bayesian Nash equilibrium [START_REF] John | Games with incomplete information played by "Bayesian" players, I-III Part I. The basic model[END_REF] and correlated equilibrium [START_REF] Robert J Aumann | Correlated equilibrium as an expression of Bayesian rationality[END_REF]. However, we do not detail these concepts since they are not directly related to this thesis.

In this section, classical solution concepts are listed and described.

Pure Nash equilibrium

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. A best strategy for a player is usually called a best response. Given the choice of a strategy by the other players, a best response for a player is the choice of the (or one of the) strategy which has the best reward for this player.

Definition 8 (Best Response) A strategy profile s is a best response for player i if and only if ∀s

′ i ∈ A i , u i (s) ≥ u i ((s ′ i , s -i )).
Pure Nash equilibrium (PNE) can be rephrased in term of better response : a situation is at Nash equilibrium if it does not exist any better response for any player, in other words it does not exist a strategy giving a better utility. For finding PNE in games, a generic algorithm is described in Algorithm 2. 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 [START_REF] Nguyen | A Complete Solver for Constraint Games[END_REF] 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. For reasoning on basic Boolean games, the first methods for computing all PNE (or core elements) have been proposed by [START_REF] De | Using Answer Set Programming for Solving Boolean Games[END_REF] by using disjunctive answer set programming [START_REF] Brewka | Answer set programming at a glance[END_REF]. Their idea is to transform a Boolean game into an answer set program. Henceforth, by using the saturation techniques [START_REF] Baral | Knowledge Representation, Reasoning and Declarative Problem Solving[END_REF], the obtained answer set will coincide with the set of PNE (or the cores).

Example 15 (Pure Nash equilibrium in WLC game) In Figure 3.6 a box is colored in red if it is a best response for the given player. For instance, let's take the Lamb's payoff, and a configuration such that the Wolf and Cabbage are coming (column w, c in the Lamb's payoff). The action not coming is a best response in this situation since it has a better payoff than coming. The intersection of the sets of best responses gives us the set of PNEs. The WLC game has 3 PNEs. The first one happens when all players do not come to the party (wlc). The two others when Wolf chooses to come and Lamb to skip (wlc and wlc).

A summary of complexities for finding a PNE for different representations is shown in table 3.1. In this table s corresponds to the number of strategy, n to the number of players and d to the maximum degree in the graph of graphical games.

Representation PNE complexity space complexity normal form game NP-complete [78]

s n graphical game NP-complete [

for all s ′ i ∈ A i , s ′ i = s i do 17: if u i (s i , s ′ -i ) > u i (s) then return true 18: end if 19:
end for 20:

return false 21: end function Definition 9 (Pareto Efficiency) A strategy profile s ∈ A i of a game is said to be weakly Pareto efficient if there does not exist any s ′ ∈ A i such that u i (s) > u i (s ′ ), for all i ∈ P.

Note on best response concept :

The concept of best response can be abstracted in multiples ways. The best responses simply state if a player is satisfied or not. In general, numerical preferences are given, but it can be extended to any notion. For instance, if a player has multiple objectives, then the best responses could be the Pareto frontier which corresponds to the states where each objective alone are not improvable without making another one worse (see definition 9).

Best response dynamic

Best Response Dynamic also called Iterated Best Response (IBR) is an incomplete method to find a Nash equilibrium, it is analogous to local search in Constraint programming (see Section 2.3). This algorithm is quite simple (see Algorithm 3), and is very efficient in practice to find a PNE if it exists. The idea of this algorithm is to first take a random configuration of players' strategies and then to make randomly deviates a player to its best response until a Nash Equilibrium is reached. end while 6: end procedure

Algorithm 3 IBR

Pareto Nash equilibrium

In a game even if a Nash equilibrium is found, it is not always a desirable state for the players. Concepts on the top of Nash equilibrium have been studied. For instance Pareto efficiency (see definition 9), or Pareto optimality, which is a state of resources allocation in which it is impossible to make any one individual better off without making at least one individual worse. That is, a Pareto Optimal outcome cannot be improved upon without damaging at least one player. Pareto optimality has been widely used as the most fundamental solution concept for multi-objective optimization problems and has also been applied for games [START_REF] Sen | Towards a pareto-optimal solution in general-sum games[END_REF].

Definition 10 (Pareto Nash Equilibrium [78])

A Pure Nash Equilibrium is a Pareto Nash Equilibrium if there does not exist a PNE s ′ such that ∀i ∈ P, u i (s ′ ) > u i (s)

A Pareto Nash Equilibrium is simply a multi-objective optimization problem on the top of the Nash equilibrium. In other words, the Pareto efficiency is applied to the players' objectives at Nash equilibrium. Obviously, if it exists a Nash Equilibrium then a Pareto Nash exists too. An example of Pareto Nash equilibrium is given in Example 16. In games it filters the equilibriums which are dominated according to the Pareto criterion.

Strong Nash equilibrium

A Strong Nash equilibrium (SNE) is a special case of Nash equilibrium. A strategy profile is a SNE means no coalition (including the grand coalition, i.e., all players collectively) can profitably deviate from the prescribed profile. This immediately implies that any SNE is both Pareto efficient and a Nash equilibrium. Also, it is stable with regard to the deviation of any coalition. Note that a SNE is also Pareto Nash. An example of a Strong Nash equilibrium is given in Example 16. In the second matrix (see Figure 3.7a) the utility of the SNE has changed. The 3 PNEs still exist but not the SNE anymore. At the same time, two Pareto-PNEs (colored in orange) exist and are reached when both players play either simultaneously s 1 or s 2 . P 1 s 1 (P 1 ) s 2 (P 1 ) s 3 (P 1 )

P 2 s 1 (P 2 ) (3, 3) (0, 0) (0, 0) s 2 (P 2 ) (0, 0) (1, 3) (0, 0) s 3 (P 2 ) (0, 0) (0, 0) (0, 0) (a) Strong Nash equilibrium example P 1 s 1 (P 1 ) s 2 (P 1 ) s 3 (P 1 ) P 2 s 1 (P 2 ) (3, 1) (0, 0) (0, 0) s 2 (P 2 ) (0, 0) (1, 3) (0, 0) s 3 (P 2 ) (0, 0) (0, 0) (0, 0) (b) Pareto Nash equilibrium

Nash equilibrium relaxations

In general cases, finding a Pure Nash equilibrium is not an easy task. That why people try to find relaxations to make the problem more tractable or to ensure that the problem has a solution.

Mixed Nash equilibrium

In a PNE, players choose a unique strategy. This choice is sometimes a bit restrictive and especially because it can makes games solutionless. Nonetheless, PNEs are good since they force players to play in a deterministic way which is easier to take into consideration to build real applications. A Mixed Nash Equilibrium is less restrictive than a PNE it allows to put a probability distribution over the set of strategies for each player. The relaxation is done over the choices players' strategies. A player can select multiple strategies if it improves its expected payoff.

A wonderful result which was found by Nash [START_REF] Nash | Non-cooperative Games[END_REF] is showing that in any game it exists a Mixed Nash equilibrium. Latter, it was shown that finding a Nash equilibrium belongs to PPDA complexity class [START_REF] Daskalakis | The complexity of computing a Nash equilibrium[END_REF] and even if the game has only 2 players. PPDA complexity means that in it always exist a solution but might be hard to find.

Definition 11 (expected utility) The expected utility of player i under the mixed strategy profile σ, denoted by u

i (σ), is u i (σ) = Π s∈S u i (s) Σ j∈P σ j (s j )
where σ j (s j ) denotes the probability that j plays s j Definition 12 (Mixed Nash Equilibrium) A mixed strategy profile σ is a Mixed Nash Equilibrium if ∀i ∈ P, σ i ∈ argmax σ i u i (σ i , σ -i ), where σ -i is a tuple of mixed strategy of the other players, except i.

Example 17 (Battle of the sexes continued)

In this game, there are 2 PNEs which are reached when both players are going to the same place, which can be either Opera or Soccer. Let's check if it exists another mixed Nash equilibrium. This method relies on a simple linear algebra. To do so, we are going to solve a Figure 3.8 -Mixed Nash equilibrium computation linear system. The unknown part of the problem is going to be the probability distribution over each strategy. Suppose that column's mixed strategy assigns probability weight q to O and (1-q) to S. The figure 3.8 shows how the distribution of probability is done. Then :

row's expected payoff from M against (1, 1 -q) = q × 3 + (1 -q) × 0 = 3q (3.1) row's expected payoff from W against (1, 1 -q) = q × 0 + (1 -q) × 2 = 2 -2q (3.2)
These expected payoff have to be equal, we must have 3q = 2 -2q or q = 2 5 . The probability distribution over the second player can be obtained in the same way.

To summarize, if now a Mixed Nash equilibrium is sought, then the probability distribution over the row is ( 2 5 , 3 5 ).

Best responses relaxation.

A way to relax Nash equilibrium is to weaken the best response concept. This relaxation is also known as ǫ -N ash and falls in the category of approximate Nash equilibrium [START_REF] Bubelis | On equilibria in finite games[END_REF]. It corresponds to a strategy profile that approximately satisfies the condition of Nash equilibrium.

Definition 13 (ǫ-approximate Nash equilibrium) A strategy profile (x 1 , ..., x n is an ǫ-approximate if for every player i and every action a in the support of

x i , E[u i (a, x i )] ≥ E[u i (b, x i )] -ǫ for any action b ∈ A i
In other words, the concept of best response is relaxed by enlarging the zone of players' satisfaction. Many researches have been done to find good algorithms for this approximations schema using different techniques [START_REF] Babichenko | Approximate Nash Equilibria via Sampling[END_REF][START_REF] Hémon | Approximate Nash equilibria for multi-player games[END_REF][START_REF] De | Exact and heuristic methods for solving Boolean games[END_REF]. The potential of such method an if the approximation scheme was possible was also studied [START_REF] Lipton | Playing large games using simple strategies[END_REF][START_REF] Daskalakis | A note on approximate Nash equilibria[END_REF][START_REF] Rubinstein | Inapproximability of Nash Equilibrium[END_REF][START_REF] Skopalik | Inapproximability of pure nash equilibria[END_REF].

Game relaxations

Recently another approach was proposed, this one consists into relax the Nash equilibrium concept by weakening the number of satisfied players. The authors call it a local equilibrium because it consists into maximizing the number of satisfied players [START_REF] Gutierrez | Local Equilibria in Logic-Based Multi-Player Games[END_REF] in a game.

Quantifying the efficiency of equilibrium

Some equilibriums are more desirable than others. In many cases, the efficiency of a solution can be evaluated by an external measure called social welfare function which should be optimized. This global function is used to compute the bestcentralized solution (by discarding the players' objectives). Afterwards, it is possible to quantify the loss of efficiency induced by the selfish behavior of the players. These measures are computed by considering the ratio "best-centralized solution / best equilibrium" for the Price of Stability (PoS) and "best-centralized solution / worst equilibrium" for the Price of Anarchy (PoA). The best equilibrium is the one giving the highest value for the social welfare function among all equilibriums.

P oA = min s∈equilibriums W elf are(s) max s∈S W elf are(s) P oS = max s∈equilibriums W elf are(s) max s∈S W elf are(s)
Where s is a state, S the set of all possible states and welf are(s) corresponds to the social welfare function associated to a state s.

Example 18 (Computation of PoA and PoS)

The toy example showed in Figure 3.7aa is considered again. This example has 3 PNEs and 1 SNE. Suppose now that the social welfare function is simply the sum of all the players' utility over plus one. As recall, the worse equilibrium regarding to the social welfare function is the oen obtained when the players 1 and 2 play both the strategy s 2 . In comparison, according to the social welfare function the best centralized solution which is also an equilibrium is reached when the players play all s 1 . Then the PoA is equal to 1+0+0 1+3+3 =1 7 and the PoS is equals to 1+3+3 1+3+3 = 1.

Games example

This section provides few examples of classical games. Most of them are part of the Gamut library [START_REF] Nudelman | Run the GAMUT : A Comprehensive Approach to Evaluating Game-Theoretic Algorithms[END_REF]. When a game comes from another source, the original publications are given as reference. We separate the description of classical games and the graphical ones. Note that a list of games can be found on Wikipedia 1

Classical games

-Minimum Effort Game (MEG) : is a coordination game which demonstrates the coordination with multiple equilibrium. The equilibrium will be reached if all players choose the same strategy. In this game, given an identical strategy set A for each player, his payoff is determined by the formula a + b × Mc × E where E is the player's effort and M is the minimum effort of all the players. a,b, c are the parameters of the game.

-Traveler Dilemma (TD) : An airline loses n suitcases belonging to n different travelers. All the suitcases are identical and contain the same items. All the travelers are told to claim the value of their suitcase between 2 and 100 (They can not discuss each other). If any travelers write down the lowest value, he will get an extra value $n, and the remaining travelers will get an minus value $n. All travelers would like to maximize the value they would be reimbursed by the airline.

-Collaboration Game (CG) : is a game where players have to collaborate to get the highest utility. Players have to chose among a set of actions. The highest payoffs are for all outcomes in which every player chooses the same action. PNEs are the situations where the players choose the same strategy.

-Dispersion Game (DG) : is a game where players do not want to collaborate and is the opposite of the Collaboration game. Players have to chose among a set of actions. In this game the players want as much as possible to not share a strategy. The highest payoffs are for all outcomes in which every player chooses a distinct strategy/ -Arm Race (AR) : is a common game in economics literature. An arms race, in its original usage, is a competition between two or more states to have the best armed forces. Each party competes to produce more weapons, larger military, superior military technology. In this game Payoffs in this game are symmetric and calculated by using the formula -C(x) + B(x-y) where x is the level of arms the player in question has chosen, y is the level of arms his opponent has chosen, and C and B are user-specified functions.

-ElFarol Bar Game (EFBG) [START_REF] Arthur | Complexity in Economic Theory. Inductive Reasoning and Bounded Rationality[END_REF] : is a kind of coordination game. In this game, there is a particular, finite population of people. Every Thursday night, all of these people want to go to the El Farol Bar. However, the El Farol is quite small, and it's no fun to go there if it's too crowded. So much so, in fact, that the preferences of the population can be described as follows with k an integer with a possible range between 1 and 100 :

-If less than k% of the population go to the bar, they'll all have a better time than if they stayed at home -If more than k% of the population go to the bar, they'll all have a worse time than if they stayed at home.

It is necessary for everyone to decide at the same time whether they will go to the bar or not.

-Colonel Blotto (CB) [START_REF] Roberson | The Colonel Blotto Game[END_REF] : is a type of two-person zero-sum game in which the players are tasked to simultaneously distribute limited resources over several objects (or battlefields). In the classic version of the game, the player devoting the most resources to a battlefield wins that battlefield, and the gain (or payoff) is then equal to the total number of battlefields won.

Graphical games :

-Public Good Game(PGG) [START_REF] Matthew | Social and Economic Networks[END_REF] :This game is useful to analyze the behavior of players when they can share a good. For instance, the action might be learning how to do something, where that information is readily communicated ; or buying a book or other product that is easily lent from one player to another. Taking action 1 is costly, and a player would prefer that a neighbor take the action rather than having to do it himself or herself ; but taking the action and paying the cost is better than having nobody take the action.

-Threshold Game of Complement (TGC) [START_REF] Matthew | Social and Economic Networks[END_REF] :This game is a bit in opposition with the PGG. In some situations, a player has an increasing incentive to take a given action as more neighbors take the action. In particular, consider situations in which the benefit to a player from taking action 1 compared to action 0 (weakly) increases with the number of neighbors who choose action 1.

-Road Game (RG) [ This chapter presents the Constraint Games framework and gives related extensions. The extensions such as the hard constraints, the shared variables and the uncontrolled variables are useful to provide a higher power of expressivity in Constraint games. The new concepts provided concern mainly modelling part of games. Especially, we study the impact on equilibriums of these new concepts and how to compute it.

Constraint Games framework

Constraint Games [START_REF] Nguyen | A Complete Solver for Constraint Games[END_REF][START_REF] Nguyen | Contrainte Jeux : modélisation et Jeux Résolution avec Contraintes)[END_REF] are a way to give games a compact representation by using Constraint Programming to represent utility functions.

Definition 14 (Constraint Satisfaction 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 non empty sets (V i ) i∈P for each player and a set V E of existential variables disjoint of all the players variables, D are the domains' variable defined as for CSP, and G = (G i ) i∈P is a family of CSP on V representing the goal of each player.

In Constraint Games, the set of players' actions are represented by the joint values of the variables he controls, and its utility by a function valuing players' actions.

Definition 15 (Strategy)

A strategy s i for player i is an assignment of the variables V i which he is controlling.

Definition 16 (Strategy profile) A strategy profile s = (s i ) i∈P is the given of a strategy for each player

In constraint satisfaction games, players' satisfactions are expressed by Boolean utility. In other words, the preferences are either "yes" or "no". The Boolean utility function of player i over a strategy profile s is set to 1 if s satisfies the goal of i and to 0, otherwise.

Definition 17 (CSG's utility) Let u i (s) be the utility function of player

i over s, u i (s) = 1 ↔ s ∈ sol(G i ) and u i (s) = 0 ↔ s / ∈ sol(G i ).
Note that [START_REF] Nguyen | A Complete Solver for Constraint Games[END_REF] has introduced satisfaction and optimization variants of Constraint Games. A Constraint Optimization Game (COG) is a variant (P, V, D, G, opt) where opt = (opt i ) i∈P and ∀i ∈ P, opt i ∈ V is the variable whose value defines the utility function u i of Player i. In a constraint optimization game, all players want to maximize their utility.

Definition 18 (COG's utility) Let u i (s) be the utility function of player

i over s, then u i (s) = -∞ ↔ s / ∈ sol(G i ) and u i (s) = s|x i ↔ s ∈ sol(G i ) where opt i = max(x i ).
In other words, when a profile s satisfy the goal G i of Player i, the utility u i of this player is given by the value of the variable to be maximized : u i (s) = opt i . By changing the definition of utility for COGs, the others notions remain the same as for CSGs Example 19 (Location game) This game comes from [START_REF] Nguyen | Contrainte Jeux : modélisation et Jeux Résolution avec Contraintes)[END_REF] and is an adaptation from [START_REF] Hotelling | Stability in competition[END_REF]. A group of n ice cream vendors would like to choose a location numbered from 1 to m for their stand in a street. Each vendor i wants to find a location l i . He already has fixed the price of his ice cream to p i and we assume there is a customer's house at each location. The customers choose their vendor by minimizing the sum of the distance between their house and the vendor plus the price of the ice cream. Note that if two vendors have the same final price then a customer is going to choose the first one by lexicographic order. This game can be modeled by the following constraint game model : A set of players :

P = {1, .., n}
For each player i, the location of his stand is determined by a variable l i with a domain the {1, ..., m} :

∀i ∈ P, V i = {l i }, D(l i ) = {1, ..

., m}

A variable cost ij determines the cost for the customer j to come to the vendor i. The cost is computed as the addition between the ice cream's price and the cost to come to the vendor :

∀c ∈ {1, .., m}, ∀i ∈ P, cost ij = p i + dist(l i , m),
Each customer selects the vendor with the minimal cost. An indicator boolean variable min c , for all customer c determines the minimal cost giving all vendors. The first constraint specifies which cost is minimal, while the second ensures that the indicator variable is set to 1 if the cost is minimal.

∀c ∈ {1, .., m}, min c = min(cost 1c , ..., cost nc ) ∀c ∈ {1, .., m}, min c = min(cost ic ) ← (choice ic = 1)
The customers can go only to one vendor : ∀c ∈ {1, .., m},

i∈P choice ic = 1
The goal of each vendor is to maximize their utility which is computed as their price times the number of customers coming :

∀i ∈ P, G i = max(p i × m c=1 choice ic )
We denote by s-i the projection of s on V -i = V \V i . When a player can improve his satisfaction by changing the assignment of the variables he can control, then he has a beneficial deviation.

Definition 19 (Beneficial deviation) Given a strategy profile s, a player i has a beneficial deviation if ∃s

′ i ∈ S i such that u i (s ′ i , s -i ) > u i (s , s -i )
A tuple s is a best response for player i if this player is not able to make any beneficial deviation. In other words, it corresponds to the tuples which give the the maximum value to sol(G i ).

Definition 20 (Best response) A strategy profile s(s i , s -i ) is a best response (abbreviated BR) for player i if and only if ∀s

′ i , u i (s i , s -i ) ≥ u i (s ′ i , s -i )
The main solution concept defined for Constraint Games is pure Nash equilibrium. A variable x ∈ V i 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 :

Definition 21 (Nash equilibrium) A strategy profile s is a Pure Nash Equilibrium (abbreviated PNE) of the Constraint games if and only if no player has a beneficial deviation, i.e. s is a best response of all players.

A i = D V i . We denote by V C = V \V E the set

of controlled variables and by

A -i = D V C \V i
the set of states of all players but i.

Constraint games examples

We give briefly here some examples of games expressed with Constraint games.

Example 21 (Minimum effort game (MEG) [START_REF] Nudelman | Run the GAMUT : A Comprehensive Approach to Evaluating Game-Theoretic Algorithms[END_REF]) It is a coordination game which demonstrates the coordination with multiple equilibriums. The equilibriums are reached when all players choose the same strategy. In this game, given an identical strategies set A for each player, his payoff is determined by the formula a + b × Mc × E where E is the player's effort and M is the minimum effort of all the players. a, b, c are the parameters of the game.

The following existential variables are used to model this game by constraint games.

-M stands for the minimum effort of all players.

-∀i ∈ P, p i stands for the payoff of player i. MEG can be modeled as follows :

-P = {1, . . . , n} -∀i ∈ P, V i = {e i } -∀i ∈ P, D(e i ) = A -∀i ∈ P, G i contains the following constraints : -M = min(e 1 , . . . , e n ) -p i = a + b × M -c × e i -∀i ∈ P, the optimization condition opt i = max(p i )
Example 22 (Travelers Dilemma (TD) [START_REF] Nudelman | Run the GAMUT : A Comprehensive Approach to Evaluating Game-Theoretic Algorithms[END_REF] ) An airline loses n suitcases belonging to n different travelers. All the suitcases are identical and contain the same items. All the travelers are told to claim the value of their suitcase between 2 and 100 (They can not discuss each other). If any travelers write down the lowest value, he will get an extra value $n, and the remaining travelers will get an minus value $n. All travelers would like to maximize the value they would be reimbursed by the airline. TD has only one PNE when all players take the minimal number as their strategy.

The following existential variables are used to model this game by constraint games.

-y stands for the minimal value chosen by all the travelers.

-∀i ∈ P, choice i is a boolean variable which is set to 1 if the value of player i is minimal, otherwise, it is set to zero. -∀i ∈ P, p i stands for the payoff of player i. TD can be expressed as follows :

-P = {1, . . . , n} -∀i ∈ P, V i = {x i } -∀i ∈ P, D(x i ) = {2, . . . , 100} -∀i ∈ P, G i contains the following constraints : -y = min(x 1 , . . . , x n ) -∀i ∈ P, choice i = 1 ⇔ x i = y -choice i = 1 → p i = x i + n -choice i = 0 → p i = x i -n -∀i ∈ P, the optimization condition opt i = max(p i )

Example 23 (Collaboration Game (CG) [152]) In a collaboration game, the highest payoffs are for every player who chooses the same action. Each player has to choose an action between 1 and m. Then for each player his rewards corresponds to the number of players having chosen the same strategy as him. CG has as many PNE as player actions

The following existential variables are used to model this game by constraint games.

-∀i ∈ P, c i stands for the action choose by each player. c i is a variable having a domain the set {1, ..., m} -∀i, j ∈ P, e ij is a boolean variable which takes the value 1 if c i )c j stands for the action choose by each player. c i is a variable having a domain the set {1, ..., m} -∀i ∈ P, p i stands for the payoff of player i. CG can be expressed as follows. In this model, the constraint count specifies how many times the value of -∀i, j ∈ P, e ij = 1 ↔ c i = c j -∀i ∈ P, p i = j∈P e ij -∀i ∈ P, the optimization condition opt i = max(p i )

Variable control

Uncontrolled variables

So far, the handling of Nash equilibrium in constraint games is related to the precise definition of the ceteris paribus principle [START_REF] Bienvenu | From Preference Logics to Preference Languages, and Back[END_REF] (i.e. games where players' actions and rewards are clearly defined). However, in full generality, this principle might be violated. In real-world, often the information available is incomplete and or imperfect. This arises, as soon as a state is not well defined, because of for example of unknown parameters in a game. A simple and famous example is the poker Texas Hold'em. In this game, the information is incomplete and imperfect. A player does not know opponents' cards and few others on the table are hidden. Each player knows only his own cards, the number of tokens he has, the amount of token of each other player and the two cards on the table. Given that, each player has to take decisions in order to bet on his possible victory (i.e. the best card) and win the maximum amount of tokens.

The location game depicted in Example 24 is another game with incomplete information. Until now, in the location game, if a customer has the choice between two vendors having the same price, it was settled that he goes to the first one by lexicographic order. This assumption simplifies the situation and could be unrealistic. Especially, in reality, a customer's choice can be arbitrary and many possibilities can be considered. If the assumption is no longer considered, then, he may go to the vendor having the best ice cream or the nicest storefront. This is associated with customers' belief but is subject to each player's interpretation. As formulated in the game, customers' choices might be unknown from players. The variables associated with the customers' choice remain free and are not instantiated and that even if all players have chosen their strategies. Most of the time, to valuate the utility functions, it is required to know everything about the players' choices and the environment. An unknown could affect the utility function making a player uncertain about customers' choice and thus about his own choice.

Example 24 (Location games with unknown variables' values)

In the location game previously exposed, it is supposed that if two vendors' cost are the same for a customer, then, the latter is going to the first one by lexicographic order. However, in this example, this assumption is not true anymore. The players know the other players strategies but not all the customers choices making potentially dilemma like in the Figure 4 In this figure, the two players : the orange and the yellow have to choose where to put their stand. There is a customer at each position and the green arrows correspond to the customers' choice. An example of dilemma is exposed in this Figure : the player orange has the position 1 and the yellow the position 5, then sellers do not know where the customer at the position 3 wish to go. The cost is the same and therefore this criterion is not enough to make a decision. As it is, the players cannot completely compute their best responses. The outcome result has multiples issues and thus is not determined. The customer can either goes to the orange's stand or to the yellow one.

Given a strategy profile, it is possible that it remains non instantiated variables. These variables are called free variables. These variable can represent unknown from the nature or hidden players strategies.

In fact, two kinds of free variables exists :

-unknown players' strategies e.g. Texas Hold'em. In other words, a player may not know the variables' values of the others players.

-unknown environment variables e.g. the location game. This situation corresponds to an unknown variable which is not controlled by any player like how the customers behave in the location game.

In constraint games, the unknowns correspond to unknown variables values during the resolution. In other words, even if all the decision variables have been instantiated, it remains some variables which are not. Players have to decide their actions without knowing completely the game's issue. They give a semantic to the variables which are not instantiated. Often, the resolution of such problems relies on prior knowledge like beliefs, if it is available. The beliefs may take different forms like a probability distribution over the unknown variables values or a symbolic behavior. For instance, a player may think that another vendor has better advertising than him or a stand which looks better. Beliefs impact the utility function's computation and thus because it decides how to consider the free variables values which possibly change the objective value.

Symbolic behaviors can be often simulated by computing statistics measures like average, means, min, max on the player's utility function. The possibles statistics are computed on the free variables knowing a strategy profile. For instance, a pessimistic player would take the minimum reward over all the possibles values which are not possibly controlled by himself.

Example 25 (Example 24 continued with beliefs) While in the previous cases, the game was assumed to be totally defined. It can arise that players cannot decide where a customer goes. Instead, each of them may have beliefs about customers behaviors. For instance, the yellow player can be optimistic, while the orange is pessimistic. Therefore, both are believing that if a customer has a choice, then he would go to the yellow player.

The In the same way, the yellow player is going to deviate to the same position as the orange player (Figure 4.3c to Figure4.3d). In that case, the yellow player is going be visited by all the customers according to the players' beliefs.

Players' beliefs impact the players' rewards because free variables may change the players' utility making the best responses beliefs dependent, as well as the set of Nash equilibriums.

More generally, a belief can be abstracted by a function f . f takes as input a strategy profile, a player plus the existential variables of a games and output a preference. The f -function is used to evaluate the subspace of the existential variable plus the strategy profile.

A f -beneficial is a beneficial deviation for games with free variables. Note that a f -beneficial deviation without free variable is a beneficial deviation and thus a f -beneficial deviation is a generalization of a beneficial deviation.

Definition 22 (f -beneficial deviation)

Let f be a function such that f : (s, V E ) → R. Given a strategy profile s, and V E the set of existential variables, a player i has a f -beneficial deviation if

∃s ′ i ∈ S i , such that f ((s ′ i , s -i ), V E ) > f ((s , s -i ), V E )
The other concepts remain the same by changing a deviation by a f -beneficial deviation. A Nash equilibrium with free variables has to respect the concept of f -beneficial deviation. In other words, a situation is at Nash equilibrium if no player has a f -beneficial deviation.

f -function : The f function is an arbitrary function which can simulate any kind of behavior from a cautious player by a using a minimum function to enthusiastic one by using a maximum function. Probabilistic behaviors can also be includeed within the f function.

Related work

The question about knowledge and uncertainty in games has already been addressed in Boolean games and in different manner. In [START_REF] Grant | Manipulating Boolean Games through Communication[END_REF] the authors Especially by the possibility to manipulate games when the information in not complete.

In [START_REF] Ågotnes | Verifiable Equilibria in Boolean Games[END_REF], the authors model uncertainty by extending the framework of Boolean games with a set of observable action variables for every agent (i.e. not all variables are observable). Possibilistic logic has been also considered in [START_REF] De | Modelling incomplete information in Boolean games using possibilistic logic[END_REF]. Or more recently by considering incomplete information for negotiation between agents [START_REF] Gutierrez | Imperfect information in Reactive Modules games[END_REF][START_REF] Grandi | Equilibrium Refinement through Negotiation in Binary Voting[END_REF][START_REF] Bulling Et Koen | Boolean Negotiation Games[END_REF].

Shared ownership of variables

Originally in games, players exercise a unique control over a set of variables (or strategies) in order to achieve a unique goal.

It may happen however that the unique control is too restrictive as for example in a modified version of the location game (see Example 26). The motivation in location game to share variable come from the situation in which a shopping mall is built. The stakeholders represented by each vendor in the project have to agree on a location. This location is going to depend on the other stores' location as well as on the stakeholders' preferences. The location's choice is going to be decided by a consensus (i.e. a group of people). Shared control of variables has been firstly proposed in boolean games in [START_REF] Gerbrandy | Logics of propositional control[END_REF]. In this article, the authors propose an extension to the CL-PC logic [START_REF] Pauly | A Modal Logic for Coalitional Power in Games[END_REF] as well as a complete axiomatization of an extension including the shared control of boolean propositions. This concept has been also studied and extended in [START_REF] Belardinelli | Relaxing Exclusive Control in Boolean Games[END_REF] to iterated boolean games.

Example 26 (Location game with shared variables) In this example of location game, the vendors can have multiple stores and can store can be shared by multiple players.

When a store is shared, the benefits are redistributed equally among the owners. Each player chooses the value of the variables he owns, including the shared variables too. A Nash equilibrium with a shared variable has to respect the preferences of each player. In the Example 26, there is no Nash equilibrium. Each player would like to shift closer to the other player's store in order to increase its utility. For instance, in Figure 4.4a the yellow players would prefer to shift the shared store to the left as shown in Figure 4.4b. Whereas, the orange one prefers to shit on the other side as shown in Figure 4.4c. The players who own a shared variable need to agree on the value taken by the shared variable. That is why the concept of partial cooperation or negotiation [START_REF] Wiebe Van Der Hoek | On the logic of cooperation and propositional control[END_REF][START_REF] Grubshtein | Partial Cooperation in Multi-agent Local Search[END_REF][START_REF] Ze'evi | Socially Motivated Partial Cooperation in Multi-agent Local Search[END_REF][START_REF] Zivan | Partial cooperation in multi-agent search[END_REF] is related to the concept of a shared variable. This concept has been mostly studied in DCOP but it is different since the players cannot share a variable and have privacy concern.

Shared variable implementation

Besides, the fact that this concept has been already proposed, we review here the possibles implementation of shared variables and its impossibility to translate into normal form. The concept of shared variable is not easily representable inside a matrix. For instance, suppose the simplest game, where a binary variable is shared by two players. A matrix representing the possible strategies is presented in Figure 4.5. A single variable which can either take the value symbolized by S 1 or S 2 , is depicted here. Each player can either choose S 1 or S 2 . However, nothing constraints the players to choose the same strategy at the same time. An implicit constraint exists : the strategy's value of P 1 has to be the same as P 2 . This is a hard constraint and cannot be simply added in the normal form (see section 4.3). As it is, the matrix does not respect the semantic of a shared variable, since its value has to be the same for all the players. For instance, players preferences are different : P 1 wishes to play S 1 while P 2 would prefer S 2 . In the matrix form, this impossibilities impact the equilibriums and creates inconsistencies as for example by the strategy profile (S 1 ,S 2 ) which is inconsistent : the shared variable cannot take two different values. While the normal form cannot represent shared variables, in constraint games two implementations are considered here : one with duplicated variables and another one where the variables are not duplicated but shared among players.

Model 1 : duplicating the variables. The first simplest model is to duplicate the shared variables to retrieve the case of unique control. Then, to make the agents agree on their choices an equality constraint is added over the duplicated variables to ensure that it does not exist any inconsistency. An inconsistency for a shared variable would be to have multiple values (e.g. the shared store is going to be at two locations at the same time). However, this model is not valid. It does not compute the Nash equilibriums anymore. When the check for players' deviations is computed, the controlled variables which include the shared one need to be uninstantiated in order to compute valid deviations. Instead, during the search procedure, if one of the players has a shared variable instantiated (or a restricted domain), then the equality constraint is going to force the other variables' copy to take the same range of values. Therefore, while seeking the best responses, the search space is constrained by this equality constraint and not valid anymore because incomplete. The player has to check his deviation is forced to have the same value for the shared variables and cannot compute properly his deviations. For instance, let's take the situation depicted in Figure 4.4a. The orange player wants to check his possible deviation knowing the choices of the yellow player. With the current model, the yellow variables values are reported. However, the equality constraint imposes to the shared store to be at position 7 because of the instantiation of the copy of the variable (own by the yellow). Instead, the orange player wishes to shift the shared store to the right like in the position as in Figure 4.4c. The best responses are then only computed on the non shared variable making the solutions inconsistent. This simple model does not respect game with the shared variable semantic.

Model 2 : sharing the variables. The second model is to relax the assumption of unique control and to share the ownership of variable among multiples players. Now, the shared variables are not duplicated in the model but remain unique. While the players need to check their deviations, the shared variable being controlled by the player is relaxed and part of the subspace of deviations check. The constraint games semantics is kept. For instance, let's take the situation depicted in Figure 4.4b. The orange player wants to check his possible deviation knowing the choices of the yellow player. With the current model, the variables own by the player are relaxed in order to check the deviations. Then the player is free to choose the location of the shared store and thus to compute his best responses correctly.

Hard constraints

Only fully expressive representations (i.e. which can represent any games) have been presented until here. However, it is sometimes not enough to model a problem. For example in the location game, some physical constraints may restrict the possible players' positions. Two stores cannot be located exactly at the same position.

Modeling these physical constraints in games requires to forbid positions by adding new constraints to the model. Hard constraints define situations which are globally not possible or forbidden [START_REF] Rosen | Existence and Uniqueness of Equilibrium Points for Concave n-Person Games[END_REF]. 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 as shown in the Example 4.9.

Example 27 (Hard constraints and normal form)

This example is taken and adapted from [START_REF] Nguyen | Contrainte Jeux : modélisation et Jeux Résolution avec Contraintes)[END_REF]. We consider the following CG :

-the set of players is P = {X, Y, Z}.

-each player owns one variable :

V X = {x},V Y = {y} and V Z = {z} with D x = D z = 0, 1, 2, D y = 0, 1.
-one hard constraint is post :

C = {alldif f (x, y, z)}
In this example, the notation x i is used when the variable x takes the value i. To ease the understanding, the players have not any goal. When a strategy profile is reachable then their utility is equal to 1. The strategies which are not possible, an utility of -∞ is given. The normal form associated to this game is as follows : The only possible strategies are when the players have all a different value for their variables. This happens only for 4 profiles : (x 0 , y 1 , z 2 ), (x 1 , y 0 , z 2 ), (x 2 , y 0 , z 1 ), (x 2 , y 1 , z 0 ). These strategy profiles are the PNEs of the game. However, the hard constraint encoding creates equilibriums which should not exist. For instance when the strategy profile (x 0 , y 0 , z 0 ) is an equilibrium whereas it should not.

y 0 , z 0 y 1 , z 0 y 0 , z 1 y 1 , z 1 y 0 , z 2 y 1 , z 2 x 0 -∞ -∞ -∞ -∞ -∞ 1 x 1 -∞ -∞ -∞ -∞ 1 -∞ x 2 -∞ 1 1 -∞ -∞ -∞ Figure 4.6 -X's payoff x 0 , z 0 x 1 , z 0 x 2 , z 0 x 1 , z 0 x 1 , z 1 x 1 , z 2 x 2 , z 0 x 2 , z 1 x 2 , z 2 y 0 -∞ -∞ -∞ -∞ -∞ 1 -∞ 1 -∞ y 1 -∞ -∞ 1 -∞ -∞ -∞ 1 -∞ -∞ Figure 4.7 -Y's payoff x 0 , y 0 x 0 , y 1 x 1 , y 0 x 1 , y 1 x 2 , y 0 x 2 , y 1 z 0 -∞ -∞ -∞ -∞ -∞ 1 z 1 -∞ -∞ -∞ -∞ 1 -∞ z 2 -∞ 1 1 -∞ -∞ -∞
PNEs and best responses are defined in the satisfiable part of the hard constraints. Hard constraints may change the set of best responses and the set equilibriums (see Example 28). The two spaces : with and without hard constraints can be totally different. With and without hard constraints the best responses are changed.

It is not easy to characterize a priory how the equilibriums are going to be impacted by hard constraints. Some of them may be forbidden while new ones may appear whether the best responses that would have occurred without hard constraints are actually unsatisfiable. this example, we are considering a simple version of Location game. Instead of have to choose a vendor, the rewards is going to be share among them. The figure 4.10 shows the effects of hard constraints on the Nash equilibrium for the Location Game. In this instance, two vendors : the orange and the yellow choose a position between 1 and 5. A constraint forbidding the two vendors to have the same position has been added. The Figure 4.10a shows how the players would have been at Nash equilibrium without the hard constraints addition. Their best option is to share the location 3. This is going to ensure them a reward of 2.5. In this picture their best responses are computed on the entire space. In other words, the players while computing their possibilities are considering all the positions from 1 to 5. Hence, their highest utility is reached when they are going to choose the position 3.

In the Figures 4.10b and 4.10c, it is for the players forbidden to have the same position. Their best responses space is reduced. For instance in the Figure 4.10b, the orange player cannot take the position 3. Instead, when he is computing his best responses, then the only possible strategy evaluated are going to be {1, 2, 4, 5}. The position 3 is not anymore considered. Therefore, the best responses are changed. The best options for the orange player are now the positions 4 and 2. The equilibriums are this changed with the addition of the hard constraint. While without hard constraint there is only one equilibrium, with the hard constraint this one does not exist anymore and 4 new equilibriums appear. Two are shown in the Figure 4.10b and c. The two other can be obtained by inverting the players.

Conclusion

In this chapter we have shown the power of constraint games, their power of modeling. We have shown extensions providing more expressivity to constraint games such as the hard constraints. Also, we have shown that the uncontrolled variables are related to incomplete and imperfect information. In addition, we investigate the concept of shared variables by showing that this concept is not easily representable by a matrix. Instead this concept can easily integrated into the framework thanks to the best response computation mechanism. In this chapter, we present a new way to see the games. This perspective consider a Nash equilibrium as a set of global constraints embedding players' preferences. An efficient method to compute the Nash equilibrium and the characterization of its complexity is also proposed.

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 instantiated 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 sought. Like in Constraint Programming, a search state S is defined by giving each variable a current domain :

S = (S x ) x∈V with S x ⊆ D x . w c l 0 0 0 0 0 1 0 1 1 1 0 0 1 1 0 (a) Nash Constraint N Lamb w c l utility 0 0 0 0 0 0 1 0 0 1 1 1 1 0 0 1 1 1 0 1 (b) Ext. Nash constraint eN Lamb Figure 5.

-Nash constraints for Lamb in extension

We use the notations

S i = S| V i and S -i = S| V C \V i .
Search consists in a series of domain reductions with an alternation of deterministic consistency steps and non-deterministic branching steps [START_REF] Rossi | Handbook of Constraint Programming (Foundations of Artificial Intelligence)[END_REF].

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 literature from the point of view of knowledge representation, especially using logic [START_REF] Henrik | The logic of preference[END_REF][START_REF] Bienvenu | From Preference Logics to Preference Languages, and Back[END_REF]. 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 D V , 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 V i , 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 A i of Player i associated to each partial state of A -i . This relation has been introduced in [START_REF] Gottlob | Pure Nash Equilibria : Hard and Easy Games[END_REF] in the context of graphical games under the name of Nash constraint. The Nash constraint N i of Player i is defined by

N i = (V C , {(s i , s -i ) | s -i ∈ A -i ∧ ∀s ′ i ∈ A i , u((s i , s -i )) ≥ u((s ′ i , s -i ))}). Theorem 4.3 of [78] adapted to Constraint Games states that NE = sol( {N i | i ∈ P}).
We propose to implement players preferences using global constraints and study filtering algorithms for them. The Nash constraint N i 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. Since the Nash constraints N i 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 N i | V i is called a never best response. We first state an intractability result : Proposition 1 In a Constraint Satisfaction Game, deciding whether an assignment nbr ∈ A i for Player i is a never best response is Π P 2 -complete.

Proof 1 Membership is immediate.

For hardness, we reduce a QCSP [START_REF] Bordeaux | Beyond NP : Arc-Consistency for Quantified Constraints[END_REF]

Q = ∀X∃Y C to a 2-players 0-sum CSG G = ({1, 2}, V 1 = X ∪ {x, a}, V 2 = 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. Conversely, if

If Q is valid, then for all s X ∈ D X , there is a s Y ∈ D Y such that C is true. Let v x
Q is not valid, then it does exist a tuple s X ∈ D X such that forall s Y ∈ D Y , C is false. If s Y = nbr, then Player 2 assigns b = v a . If s Y = nbr, then Player 2 assigns b = v a . 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 [START_REF] Krzysztof | The Essence of Constraint Propagation[END_REF]. 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

eN i = (V C ∪ {opt i }, {(s, o i ) | s ∈ N i }) the Nash constraint N i
augmented with the value of the player's objective (see Figure 5.1(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 eN i by ooN i (objective optimal Nash constraint) defined by

ooN i = (V C ∪ {opt i }, {(s, o i ) | ∃(s ′ , o i ) ∈ eN i ∧ o i ∈ eN i | opt i }).
However, only looking at the objective value is not enough. In different regions of the search space, two tuples s and s ′ may have the same objective value o i 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 V i 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

mooN i = (V C ∪ {opt i }, {(s, o i ) | ∃(s ′ , o ′ i ) ∈ eN i , o i ≥ o ′ i }).
Since sol(eN i ) ⊆ sol(ooN i ) ⊆ sol(mooN i ), any filtering of mooN i is correct with respect to eN i . 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 :

M m(S) = max s i ∈A i min s -i ∈S -i (s i , s -i )| opt i (1)
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 A i . 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 V i are reset to their original domain A i , 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 opt i > 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 M m AC (S), the best estimation arc-consistency can provide for the maximum value of the minimum bound of the objective : M m AC (S) = max s i ∈A i lb(AC((s i , S -i ))) where AC denotes arcconsistency applied to a search state. Formally, the operator BB i : D V → D V implemented by the global constraint is defined by :

BB i (S) = S opt i = S opt i ∩ [M m AC (S)..ub(S opt i )] S x = S x , ∀x = opt i
When all variables are assigned, computing deviations amounts to checking whether a complete assignment is a best response for Player i. -singleton completeness : ensured by construction.

Example 30 (Example 11 continued)

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 x L = wlc + wl for which l is a best response to w whatever the value of c. By checking earlier the possible deviation, our propagator is able to find this kind of dependencies in order to prune the search space.

Nash propagator applicability

We discuss here about the Nash constraint. Especially about its filtering algorithm completeness and validity. It has been said, that hard constraints modify the search space. Especially, Nash equilibriums can be moved, created, or even removed (see section 4.3).

Actually, when a game contains hard constraints, those make in general the Nash constraint no longer valid. The inference made by the Nash constraint, it is made by supposing that the other players cannot affect a player strategy (i.e. making it impossible).

The outputted solutions are still Nash equilibrium but the completeness is not anymore guaranteed.

Example 31 (Nash propagator invalidity) This example shows a game where the Nash constraint does not guarantee anymore the completeness of the search. A Nash equilibrium is removed by the constraints. Two players X and Y respectively own the variables x and y which can either take values 0 or 1. The goal of player X is to maximize 3X + Y while Y 's goal is to maximize Y -X. A hard constraint forbids the players to chose the same value for their variables. The game is expressed with the following constraints and variables :

- The entire search tree is developed in Figure 5.

P = {X, Y } -D(x) = D(y) = {0, 1} -G x = M ax(3X + Y ) -G y = M ax(Y -X)

When a node is crossed, it means that it is forbidden by a hard constraint (x=0 ∧ y=0 or x=1 ∧ y=1). The problem here is the initial propagation deletes a Nash equilibrium. When X tries different configuration for its variable then he realizes that he has an incentive to always assign 1 to x (when he plays 1, he has at least 3 while by playing 0 the minimal utility is going to be 0. Thus the propagator updates the objective's lower bound to 1.

The problem is that Y does the same reasoning and both consider that the minimum utility reachable is higher than what they can get. Therefore, both objectives bounds are updated making all states inconsistent. It also, removes the two Nash equilibriums.

Related work

A related scheme is the one of Asynchronous DCOP [START_REF] Wahbi | A Distributed Asynchronous Solver for Nash Equilibria in Hypergraphical Games[END_REF] in which all players share the same constraints but with different costs. Also, in this work, the authors propose to work directly on the action themselves, while we restrict the action based on the objective. Furthermore, we characterize how to reach arc consistency for the Nash constraint. From this, we propose a tractable and efficient filtering for the Nash constraint.

Our work can be also seen as an opening of Singleton arc consistency but based on the objective value. In the original singleton arc consistency, each variable's value is checked whether the constraints are still satisfiable. In games, it is a bit different since without hard constraints all the search space is satisfiable. Instead, an inference on the objective value is feasible. This method is also valid in single objective optimization but a strong condition which is to have a problem without hard constraints.

Experiments

We have implemented a new solver for Constraint Games on top of the constraint solver Choco v4 [START_REF] Prud'homme | Choco Documentation[END_REF]. 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 5.1. 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 V C plus Player i's optimization variable opt i . However, the propagator is called whenever the objective of the player has been updated. Upon the call, it revises opt i by launching a new search tree in a distinct solver only on the variables of V i , 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.

Game Param. #PNE enum

We have performed experiments on classical games of the Gamut suite [START_REF] Nudelman | Run the GAMUT : A Comprehensive Approach to Evaluating Game-Theoretic Algorithms[END_REF] : Minimum Effort Game (MEG), Travelers Dilemma (TD), Dispersion Game (DG), Collaboration Game (CG), ArmRaces (AR), ElFarol Bar Game (EFBG) [START_REF] Arthur | Complexity in Economic Theory. Inductive Reasoning and Bounded Rationality[END_REF] and Colonel Blotto (CB) [START_REF] Roberson | The Colonel Blotto Game[END_REF]. We invite the reader to refer to the sections 4.1 and 3.4 and 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 [START_REF] Richard D Mckelvey | Gambit : Software tools for game theory[END_REF] and to a custom re-implementation of the Conga algorithm (hereafter called Conga 1 ) as described in [START_REF] Nguyen | A Complete Solver for Constraint Games[END_REF]. The results are presented in Table 5.1. All times are given in seconds and we applied a maximum run-time 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.

Graphical Aspects

When the utility of a player only depends on a subset of the other players, the game is called graphical [START_REF] Michael | Graphical Models for Game Theory[END_REF]. More formally, for a profile s ∈ A P and two players i and j, we say that u i (s) is independent of j if ∀s ′ j ∈ A j , u i (s) = u i (s -j , s ′ j ). If this is not true, then i depends on j for s, denoted by i ⊳ s j. We denote by dep i (s) = {j | i ⊳ s j} the set of dependencies of Player i for the state s. For E ⊆ A P , we note dep i (E) = s∈E dep i (s). Finally, Player i statically depends on Player j, denoted by i ⊳ j if j ∈ dep i (A P ). A minimal dependency which occurs only in a strict subspace of A P is called dynamic.

The main purpose of graphical games is to save space in the matrix repre-sentation, and also to speed-up the computation of equilibria [START_REF] Vickrey | Multi-Agent Algorithms for Solving Graphical Games[END_REF][START_REF] Ortiz | Nash Propagation for Loopy Graphical Games[END_REF]. 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) [START_REF] Matthew | Social and Economic Networks[END_REF] and Road Game (RG) [START_REF] Vickrey | Multi-Agent Algorithms for Solving Graphical Games[END_REF]. 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 5.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.

Conclusion

In this chapter, 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 [START_REF] Nguyen | A Complete Solver for Constraint Games[END_REF]. 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. 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. With the internet of things, all kinds of devices are going to communicate, from washing machines, lightbulbs to autonomous cars. By 2020, the forecasts estimate the number of connected devices to the internet is growing to over 31 billion [START_REF] Osseiran | The foundation of the mobile and wireless communications system for 2020 and beyond : Challenges, enablers and technology solutions[END_REF]. The amount of data transfer increases with the rise in the number of connected devices. Recently, Software Defined Networking (or SDN) is replacing traditional network routing because it allows fast and remote network reconfiguration, which enables a plethora of flexible architectures, like the upcoming network slicing [START_REF] Vassilaras | The Algorithmic Aspects of Network Slicing[END_REF]. SDN (see Figure 6.1) allows centralized control over a network of commuters in order to increase the overall performance. A full SDN controller is a nice source for many optimization problems [START_REF] Leguay | Online and Global Network Optimization : Towards the Next-Generation of Routing Platforms[END_REF] including online ones. Due to this dynamic aspect and the increasing size of the controlled networks, it is very likely that decentralized algorithms will be mandatory to provide both the expected quality of service and short time response. In this paper, we consider the independent routing of multiple demands across a network, also called the multicommodity flow routing problem. Each demand requires to be routed from a source to a destination in a network with limited capacity (i.e. each link has a limited capacity). The overall goal is to assign a route to each demand that minimizes the global cost of routing. This problem and other variants such as robust SDN networks have been studied for a long time [START_REF] Even | On the Complexity of Time Table and Multi-commodity Flow Problems[END_REF][START_REF] Capone | Detour planning for fast and reliable failure recovery in SDN with OpenState[END_REF] with some computational approaches including linear programming [START_REF] Azzouni | Neu-Route : Predictive dynamic routing for software-defined networks[END_REF]. A survey can be found in [START_REF] Mendiola | A Survey on the Contributions of Software-Defined Networking to Traffic Engineering[END_REF]. Interesting theoretical results have been found, like the one which states that when the problem has a sufficient size and capacity, all flows are actually routed along single-paths [START_REF] Puri | Algorithms for the Multiconstrained Routing Problem[END_REF]. This justifies the modern interest in unsplittable routing of demands. The demands are routed in a network with limited capacity constraining the shortest paths computations, which is known as a NP-complete problem. In our approach, we do not consider other side constraints such as must-pass/cannot-pass or redundant routing, although they can be easily introduced in our constraint model. However, we consider a congestion model increasing the cost of a link according to the traffic routed. Furthermore, SDN is based on a centralized vision of networking but this does not mean that all algorithms have to be centralized [START_REF] Orda | Competitive Routing in Multi-User Communication Networks[END_REF]. Indeed, with the growth of the size of the controlled zone and the large increase in the volume of the demands, decentralized algorithms will be necessary to achieve the expected level of performance for future SDN with millions of demands coming online. A common way of modeling agreement between a set of agents is to reach a Nash equilibrium. Also, some instances of the problem correspond to networks of aggregated traffic for which the users (often network providers) are very sensitive to the quality of service. This is why an allocation at Nash equilibrium is desirable as it ensures the user that his quality of service cannot be improved by any selfish move. While a centralized approach is sure to converge to an optimal solution, it is not guaranteed for Nash equilibriums. The equilibriums costs can be far from the global optimum. Braess's paradox [START_REF] Braess | On a Paradox of Traffic Planning[END_REF] is a good illustration. It states that in congested roads network, building a new route creates even more congestion due to the selfishness of agents. This degenerative behavior is one of the motivations to compute Price of Anarchy [START_REF] Fudenberg | Game Theory[END_REF] which allows to evaluate the potential loss of efficiency of decentralized algorithms (i.e. the loss of being at Nash equilibrium).

We propose two approaches for the centralized approach : a Constraint Programming (or CP) model and an Integer Linear Programming (or ILP) model using Column Generation. Only the Constraint Programming model is able to model closely the congestion problem and can be used to solve the problem to optimally. For this, we use a natural and dedicated heuristic based on increasing paths and a relaxation based on shortest path to prune efficiently the search space. Note that increasing path have been introduced as CP heuristics in [START_REF] Le | Robust and Parallel Solving of a Network Design Problem[END_REF].

The Constraint Programming model is implemented using the Choco constraint solver [START_REF] Prud'homme | Choco Documentation[END_REF] and the ILP one with CPLEX [START_REF]CPLEX User's Manual[END_REF]. The model computing the Nash equilibriums uses Constraint Games framework : ConGa which is an extension of the Choco solver for Constraint Games [START_REF] Palmieri | Constraint Games revisited[END_REF]. In the benchmarks, we show networks with hundreds or even thousands of commodities solved to optimality including the Nash equilibriums computations. These results show that practical use of game theory is now possible at industrial scale.

The chapter is organizing as follow : first we introduce the problem in Section 6, then in Section 6.1 and 6.2 we present the CP model and the heuristics used to compute a solution in practice. In section 6.3 we present the ILP model, in Section 6.4 the Constraint Games framework used to compute selfish routing, the Section 6.5 gives a literature review, in Section 6.6 the evaluation on a set of benchmarks on real-world and synthetic instances and lastly we present the conclusion.

Problem statement

A multicommodity path routing problem (MCPRP) consists of a graph defining a network and a set of commodities (flow demands) to be routed on this graph. We consider in this article the problem in which we compute for each demand a single route from the source to the destination node such that the sum of bandwidth routed by a link does not exceed its capacity. Congestion occurs when a link is taken and is reflected by a congestion cost which helps to ensure a homogeneous distribution of the routes. The overall objective is to minimize the sum of costs of the routed demands.

We assume we have a network N = (V, E), which is a directed graph composed of a set of vertices (or nodes) V and a set of edges (or links) E ⊆ V 2 . For each edge e = (x, y) ∈ E, we associate a cost cost(e) ∈ R + and a capacity cap(e) ∈ R + . Let D be the set of demands to be routed. For a demand d ∈ D, we define src(d) ∈ V and dst(d) ∈ V to be respectively the source and destination node, and bw(d) ∈ R + to be the required bandwidth for this demand.

A path is a sequence of nodes p = (v i ) i∈[0.

.n] such that ∀i ∈ 0..n-1, (v i , v i+1 ) ∈ E. We denote by src(p) the node v 0 and by dst(p) the node v n . We consider here only acyclic paths, i.e. such that i = j → v i = v j . By a slight abuse of notation, we write (x, y) ∈ p to denote that the arc (x, y) is taken in the path p.

A solution for the MCPRP is the assignment of a path path (d) to each demand d such that we ensure correctness : (d) and admissibility with respect to the capacity constraints :

∀d ∈ D, src(path(d)) = src(d) ∀d ∈ D, dst(path(d)) = dst
∀e ∈ E,   {d∈D | e∈path(d)} bw(d)   ≤ cap(e)

Congestion model

In order to ensure a good balance over the network, we incorporate to the model a model of congestion. Basically, congestion will increase the cost of a link when this link is close to saturation. For this, we define the load of an edge e to be : The congestion model we use for a given arc e has an exponential increase of the form :

load(e) =
cong(e) = exp (a × load(e) + b) (6.2)
In order to choose the parameters a and b, we pose some conditions on the function. First we should have a sufficiently high value of cong(e) when the load is 1. By sufficiently high we mean that a demand should not prefer to take a heavily congested link while there are some (maybe longer) available paths. It can be done by fixing this limit to the highest link cost of the network M axC. We then have the equation e a+b = M axC. Then, in order to set when the exponential starts to overtake on a linear increase, we impose a condition on the derivative to be 1 at a given point α. The derivative of the congestion function is given by cong ′ (x) = ae ax+b . If we impose that the derivative should be 1 for x = α, we get the equation ae aα+b = 1. By solving numerically these equations we get the values of a and b for a given problem. For example, in Figure 6.2 is a plot of the congestion function for M axC = 1000 and cong ′ (0.2) = 1. We assume that the same values of a and b are set for all the links of the network, although this can be easily changed.

Optimization

Solving a MCPRP P to optimality means finding a solution minimizing the global cost of the demands. For this, we first define the cost to route a demand. It is obtained by aggregating the cost of each traversed arc with the cost coming from congestion :

cost(d) = bw(d) × e∈path(d) (cost(e) + cong(e)) (6.3)
Then the cost of the whole problem is given by :

cost(P ) = d∈D cost(d) (6.4)
Note that this function is strictly monotonic, resulting in that each addition of demand increases the edge cost.

Constraint model

In order to implement this problem as a constraint program, we need to first represent paths, which will be the solutions of our problem. Then we need to link the computed paths to the network data : costs, capacity and provide a support to compute congestion.

Path modelling

A path is represented by an array path of |V | variables which correspond to the set of arcs in the path. Each variable's value corresponds to the node's successor (i.e. the next node along the path). The initial domain of a variable associated with a node v is given by the set of neighbors of v in the graph. In order to ensure the correct representation of a path, we use the global constraint subP ath(path, src, dst) which ensures that the node from src to dst form a valid subpath of the graph. This constraint is a variant of subCircuit. Unused nodes of the path point to themselves and an extra variable is appended to the array to indicate which vertex starts the path.

Example 32 (Path model) The figure 6.3 describes the model for finding a path having the node 2 as a source and the node 5 as the destination. In the beginning, the variables domains are filled with all the possibles neighbors including itself. For example, the node 0 can have as successor the nodes : 0, 1or2. Only the source and the destination are treated differently. Since a path can be seen as a circuit between the source and the destination nodes. That is why their domains are adapted : no self-loop for the source node(i.e. a successor is required) and the destination's successor is the source. A solution to the problem instance is depicted in the array line labeled by path. This array encodes the path [START_REF] Allouche | Anytime Hybrid Best-First Search with Tree Decomposition for Weighted CSP[END_REF][START_REF] Ågotnes | Verifiable Equilibria in Boolean Games[END_REF][START_REF] Arthur | Complexity in Economic Theory. Inductive Reasoning and Bounded Rationality[END_REF][START_REF] Krzysztof | The Essence of Constraint Propagation[END_REF][START_REF] Robert J Aumann | Correlated equilibrium as an expression of Bayesian rationality[END_REF]. It has to be read as follow : the node 0 has 0 as successor (not in the path), the successor's of 1 is 4, the successor's node of 2 is 1 ...

subP ath([v d 1 , . . . , v d n ]
, src (d), dst (d))

Graph model

In order to ensure that no link is overloaded and in order to compute congestion, we need to know which demands are routed by a given arc. In this model, we use a Boolean variable EdgeIsU sed d (i,j) which is true if the path [v d 1 , . . . , v d n ] assigned to demand d uses the arc (i, j). This connection is made with the following channeling constraints :

∀(i, j) ∈ E, ∀d ∈ D, EdgeIsU sed d (i,j) ↔ v d i = j
We compute the amount of bandwidth routed by an arc in a variable f (e) with the constraint :

∀e ∈ E, f (e) = d∈D EdgeIsU sed d e × bw(d)
We ensure that the capacity of each arc is not exceeded :

∀e ∈ E, f (e) ≤ cap(e)
Then we can compute the congestion of a given edge in a variable cong(e) :

∀e ∈ E, cong(e) = e a× f (e)

cap(e) +b

The cost cost (d) of routing a demand by a given path is given by the constraint : (d) × (cost(e) + cong(e)) (6.5)

∀d ∈ D, cost(d) = e∈E EdgeIsU sed d e × bw
A variable P roblemCost sums the costs to route all demands :

P roblemCost = d∈D cost(d) (6.6)
We shall minimize this variable. This model is quite standard and intuitive. It defines one Boolean variable by edge and by demand. Since the number of edges is quadratic in the number of vertices, this number may grow a lot for some large networks.

Heuristics and problem's relaxation

We have tried a variety of combinations of search strategy (or SS) and problem's relaxation to improve the resolution of this problem. In this chapter, we will refer to a particular combination by A/B/C where A is the variable selection strategy, B the value selection strategy and C the type of relaxation to compute the problem's bound, as explained below. At a given node of the search tree, some demands or some partial paths may already be assigned. Apart from classical CP heuristics, all heuristics and lower bound computations use the residual graph obtained by considering this part already fixed.

Residual graph

For each demand, a residual graph is maintained all along the search. This graph is the cornerstone to solve efficiently this problem. It is used by the search heuristics and the relaxation technique. A residual graph is modified incrementally at each search tree node. We refer as path the edges belonging to the path as it is in the current search tree (i.e. the instantiated variables) and as future path the path's part which is not instantiated in the search tree but computed by the Dijkstra algorithm. A residual graph is built such that :

-It exists a directed edge from the node i to j ↔ j ∈ D(V i ) -The cost of an edge is dynamically set and updated by the variables' values.

When a variable is instantiated(i.e. an edge is added to the path), the edge's minimal cost is updated by updating its bandwidth. For instance, when a demand goes through an edge, its congestion cost is automatically updated with the current demand's bandwidth and that for all residual graphs. However, it is not possible to take into account the congestion in future path. It means that two demands whose future path would take the same link act like if they do not create congestion in their future paths.

The residual graphs are constructed with the CP variables, therefore the graphs are modified at each decision or propagation automatically.

Example 33 (residual graph) Two demands d 1 and d 2 having each a bandwidth of 2, have to be routed in the 4 nodes networks shown in Figure 6.4. In this network, the cost of each edge is 0 and the congestion parameters are respectively a = 1 and b = -0.5. At first, the residual graphs are constructed at the root of the search tree (the edge sets representing the paths are empty). The costs are initialized only with the bandwidth induced by the demand. For instance in Figure 6.4a, the residual graph costs of d 1 are computed only knowing the bandwidth of d 1 , no assumption can be done about d 2 . The costs are thus 2 obtained by :2 × e 2 4 -0.5 . In the next step shown in Figure 6.4b, d 1 's path is continued with the edge between the node 0 and 1. This decision updates the cost of the residual graph of d 2 . The new cost is 2 × e 0.5 , it corresponds to the cost when the two demands take the same edge. In Figure 6.4b, d 2 is going through the same edge as d 2 , thus the residual graph of d 1 is updated.

Search strategies

Path-oriented problems are particularly sensitive to SS, and not surprisingly, a standard dynamic CP SS (denoted by CP in this chapter) like impact or activity would be of weak efficiency for this type of problem. Indeed, it is likely that this SS will label any node in the path without knowing if it could be linked to the source or destination. Therefore, we propose a variable's value selection strategy as well as three variable selection strategy, all dedicated to this SDN problem.

Value selection

For each variable, the value SS determines the path's direction. Since the goal is to find the best path for each demand, it would be inefficient to start the path in a wrong direction. We have chosen to label path variables in order of increasing path cost. In order to start with the most promising path, we maintain at each node of the search tree the shortest path to the destination in the residual

v d i = SP i (v d i ), if v d i ∈ SP d v d i = i, otherwise
Where SP d (v d i ) gives the successor of the node v d i for the demand d 's shortest path.

We call this value strategy SP (for Shortest_Path). It is done with Dijkstra's algorithm, considering the progression of the already assigned part of the other demands. This information on the best future path is used to choose the next node of the path when needed(i.e. the variable value). Note that the Dijkstra algorithm only considers the nodes of the paths already assigned at a given point of the search tree for computing the congestion. In particular, the congestion is not cumulative for two demands which share the same future link. The same idea has been implemented in [START_REF] Chabrier | Solving a Network Design Problem[END_REF] but with specific path variables.

Variable Selection

Once again, a variable strategy selecting the variables outside a path scope would be very inefficient, that why we choose to select the variables all along the paths. In other words, our variable selection respects the path order, it selects the next uninstantiated successor variable along the path. Note that this is a partial variable selector since it is only once the demand is chosen that the actual variable is determined by the next step to be extended. For the variable selection to be completely defined, we have considered three strategies for choosing the demand. The first one, called MB (for Max_Bandwidth), consists in routing the next remaining demand with the maximum bandwidth up to its completion. Then we have defined two strategies based on conflicts analysis. The strategies react on a solution (by MB for the first one) or when a fail occurs. For each demand and each link, we compute the marginal cost (with congestion) induced by the presence of the demand on this very link. The marginal cost corresponds to the difference between the cost with and without routing the demand, all being equals. Then, we sum up all these numbers for each demand along the taken path to obtain a score. The first one, called CO (for Conflict), chooses the demand of the highest score and develop its path up to the destination. The second one, called CO1 (for Conflict_1_Step), also chooses the demand of the highest score but only develops one step in the path before reconsidering the situation. In CO1, the conflicts are stored for each path variable for each demand and score are only computed for the uninstantiated variables.

MB Strategy.

Given the network in Figure 6.6a), MB selects the demand having the highest bandwidth to be routed. At first, d 1 is chosen and is instantiated from its source to its destination (see Figure 6.6b). Afterwards, the next demands to be instantiated are going to be iteratively d 2 and d 3 (Figure 6. 6c andd).

CO strategy. Given the network in Figure 6.7a), where a first solution has been found. CO analyses the conflicts in the solution to try to redirect the conflicting demands. In this solution the demands d 1 and d 2 are in conflict. The marginal The demand d 1 is the one having the highest score and thus selected to be routed (see Figure 6.7c). And then to finish the demand d 2 is the last one to be routed until its destination (see Figure 6.7d). After a solution was found, the solver backtrack until the Figure 6.8b. Then it selects the demands with the highest score and instantiates its first element on the path, which corresponds to the edge between the node 1 and 4 (see Figure 6.8c). Afterwards, d 3 has the highest score since the edge between the nodes 1 and 4 is not anymore considered for the demand d 1 . d 3 is routed by the edge between the nodes 1 and 3 (see see Figure 6.8d). This process is continued until all the destinations are reached (see Figure 6.8e)

Problem's relaxation

Relaxation techniques are commonly used in constraint optimization. However, CP solvers offer a restricted and uninformed version. When minimizing the variable P roblemCost and after having found a solution of value A, it simply adds to the remainder of the search the constraint P roblemCost < A. The CP solver is unaware of the problem structure. While efficient, it requires that the lower bound of P roblemCost to exceed A to cut the search tree and backtrack. In our case, the possible values of P roblemCost are strongly constrained by the current branch of the search tree leading to a node, but very loosely for the remaining part of the problem. In order to cut earlier, we need a better estimation of the lower bound of P roblemCost. This is done by adding to the lower bound the cost of individual routing along the path computed by the Dijkstra algorithm used for the value SS. We use the previously defined residual graph in which congestion is taken into account to estimate the cost lower bound of the current search tree state. We need this to provide a better yet safe estimate of the lower bound which does not exceed the future real cost. We call the classical CP branch & bound CP and the one which uses the bound provided by the shortest path SP.

Let [a Proof 3 Suppose by contradiction that the proposition is not correct and the equation is not sound. This statement implies that it exists at least one node's cost which is overestimated by the Dijkstra algorithm. The latter is either located on the instantiated nodes or on the future path. This is impossible because the given costs corresponds to the lower bound and are at worst underestimated. That is why Dijkstra algorithm and thus the computed path is computing correct lower bound for the shortest path algorithm.

Note that, due to the presence of link capacity constraints, a fail is triggered when Dijkstra algorithm is unable to find a path from the source to the destination [START_REF] Sellmann | Cost-based Filtering for Shorter Path Constraints[END_REF].

Example 36

The example in Figure 6.9 illustrates how the relaxation technique based on shortest paths works. Two demands : d 1 and d 2 have to be routed through a 5 nodes network (see Figure 6.9(a)). Each demand has a bandwidth of 2 and each arc in the network can transport 4 units of bandwidth. The two demands d 1 and d 2 have both the node 0 as source and respectively the nodes 3 and 4 as destination. The parameters of the congestion cost function are a = 1 and b = -0.5. To simplify the problem, each edge's cost is 0.

In each subfigure is depicted on the left the state of the current graph with the decisions already taken and on the right the residual graphs of d 1 and d 2 . The shortest path algorithm of each demand is computed on its own residual graph. Because it is implemented on the CP variables, the SP computation is aware of the current bandwidth and the successor variables in order to consider only feasible paths. 2.e 0.5

2.e 0.5 Figure 6.9 -Problem's relaxation example for SDN

In beginning of the problem resolution, the initial propagation is triggered updating the minimal reachable global cost. To do so, the cost of each demand is evaluated (see Figure 6.9a). The minimal possible cost corresponds to the demand shortest path without any added congestion due to other demands. For d 1 and d 2 it is obtained by the following computation : 2 × 2 × e 2 4 -0.5 = 4. For each demand, the shortest path's cost is 4. Then the problem is explored by instantiating a first edge for d 1 (Figure 6.9b). The cost is updated in the residual graphs. Taking the edge from the nodes 0 and 1 costs now 2 × e 0.5 , this update is done in the residual graph of d 2 . In the residual graph of d 1 only the possible path are updated : the node 2 cannot be taken anymore. The same process is repeated when the path of d 1 is continued (Figure 6.9c). Afterwards, it is the second demand which is routed (Figure 6.9d and Figure 6.9e). While taking these decisions, the residual graph of d 2 is updated by removing some edges. The edges of the residual graph of d 1 are not impacted since d 2 does not take the same edges. The solution found has a cost of 8. The Dijkstra relaxation help to state that it does not exist better solution since at the beginning the lower bound for the problem was also 8. The problem's exploration is thus finished.

A ILP model

ILP techniques are commonly used to solve multicommodity flow problems [START_REF] Barnhart | Using Branch-and-Price-and-Cut to Solve Origin-Destination Integer Multicommodity Flow Problems[END_REF], even in the context of SDN [START_REF] Paris | Controlling flow reconfigurations in SDN[END_REF]. However, the model we presented in Section 6.1 is not suited to an ILP formulation because it is very difficult to model paths as in CP. Instead, most formulations either use a flow model or use a pre-computation of paths for the different demands and associate a Boolean variable to each possible path. We will use this technique despite it yields an exponential number of variables because they can be generated on the fly using column generation.

Master Problem

First we reformulate the multicommodity flow problems with Boolean path variables in what we call a Master Problem, then we provide a linearization and the pricing problem used to introduce new columns. For each demand d ∈ D, we associate the set P d of all paths from src (d) to dst (d). By a slight abuse of notation, we also call p a Boolean variable associated to a path p ∈ P d because paths are only manipulated through their Boolean variable. Because a path is statically defined and because we need to sum up the bandwidths associated to the various arcs of the network in order to enforce the capacity constraints, we associate to a path variable p and each arc e ∈ E, a variable p e which is true if the arc e is taken by the path p. Note that this variable p e is used just to simplify the notation and does not belong to the implemented model. We ensure that exactly one path is chosen for each demand :

∀d ∈ D, p∈P d p ≥ 1 (6.8)
The capacity constraints become :

∀e ∈ E,

d∈D p∈P d p e × bw(d) ≤ cap(e) (6.9)
We aggregate all costs in the following expression to be minimized :

min e∈E d∈D p∈P d p e × bw(d) × (cost(e) + cong(e)) (6.10)
Where the congestion is defined by equations 6.1 and 6.2. There are two sources of non-linearity in these formulas. First the load of an arc uses an exponential function. It yields that it is easier to break up equation 6.10 in two for its linearization. A first part we call cost with congestion cwc(e) for a given arc e and a subsequent aggregation on the set of demands :

cwc(e) ≥ d∈D p∈P d p e × bw(d) × (cost(e) + cong(e)) (6.11)
Note that since we deal with a minimization problem, only the ≥ part of the equation is mandatory to enforce equality. Then the expression to be minimized is :

min e∈E cwc(e) (6.12)
But then a more subtle source of non-linearity is that, since the cost depends on the load and the load depends on the path chosen for each demand, we have to consider for the cost the cases where two or more demands are routed by the same arc. It yields a product between the Boolean variables p d e and p d ′ e for any pair d, d ′ ∈ D. We now address these two relaxations.

Column generation

The problem we get with a model based on paths and its subsequent linearization involves an exponential number of variables (since there are exponentially many paths between a source and a destination). Moreover, only one variable for each demand will be set to 1 because we seek a single path for each demand. It is impossible to represent all these variables but fortunately they can be generated on the fly (along with the constraints they are subject to) using Column Generation (see Figure 6.10).

Column Generation alternates between solving the linear Restricted Master Problem with a limited number of variables (or columns) and generating new Column generation methods were invented from the observation that often in problems many variables do not belong to the optimal solution and thus their values are set 0 and not used. The idea is to try to generate only the columns useful to solve optimally the problem. For instance in our problem, often only few paths are needed to find and prove the optimal solution.

A Pricing Problem is used to determine which column should be introduced. It yields either to add a new variable or to ensure that there are no further variables with negative dual feasibility i.e. which can potentially improve over the current solution. When no more columns can be generated, the linear solution is rounded to give an integer one.

We consider only column generation at the root node. This method can be incomplete unlike Branch and Price which is a bit different since it considers a tree obtained by solving the ILP problem for different sets of columns.

Linearisation of the master problem

What we call Linearized Master Problem (or LMP) is essentially a linear approximation of the Master Problem introduced above. It means that the solutions we will find with ILP are solutions to the approximate model and not exactly solutions of the original problem. However, if the linearization is good, it is likely that the solution paths for the demands will be the same as if the exact model was solved, although it cannot be ensured in all cases. In practice, we have not observed any difference.

The first thing to come is to transform the Boolean variables into continuous ones in the interval [0..1].

Piecewise linear approximation of the exponential function.

The second relaxation concerns the exponential function. We approximate it with multiples tangents. Let I be a set of numbers in [0..1]. For each point of the exponential curve (i, cong(i)) i∈I , a tangent t i (x) = a i x + b i is computed. In Figure 6.11 is depicted a 3-points approximation of an exponential function. The red lines correspond to the computed tangents approximating the function. The difference between the approximation and the real function is shown in light gray. In this zone, the congestion is underestimated and may induces less filtering. For the sake of simplicity, we use the same set I for all links of the network.

The approximation of the exponential correspond to the maximum value of these tangents max i∈I t i (load(e)). In order to get a linear formulation of the maximum, we can introduce for each arc e and each i ∈ I a variable cong i (e) giving the value of each tangent for a given load and one variable cong(e) for the maximal value. The cong i (e) reuses the definition of the load given in equation 6.1 :

∀e ∈ E, ∀i ∈ I, cong i (e) =   a i cap(e) d∈D p∈P d p e × bw(d)   + b i
And for each link, the following constraints are added :

∀e ∈ E, ∀i ∈ I, cong(e) ≥ cong i (e) (6.13)
Linearization of the products.

Unfortunately, when computing the cost with congestion cwc(e) of an arc e with equation 6.11, all demands crossing this arc actually cause the congestion to increase. If we develop the formula by mixing equations 6.11 and 6.13 with respect to each i ∈ I, it yields for a given edge e :

∀i ∈ I, cwc i (e) ≥ d∈D p∈P d p e × bw(d) ×   cost(e) +   a i cap(e) d ′ ∈D p ′ ∈P d ′ p ′ e × bw(d ′ )   + b i  
By splitting the linear and non-linear part we get :

∀i ∈ I, cwc i (e) ≥ (cost(e) + b i ) d∈D p∈P d p e × bw(d) + a i cap(e) d∈D p∈P d p e × bw(d) × d ′ ∈D p ′ ∈P d ′ p ′ e × bw(d ′ )
The last expression is quadratic because it contains a product between p e and p ′ e . To get a linear formulation, we introduce new Boolean variables pp ′ e for each arc e and each path p for d and each path p ′ for demand d ′ such that pp ′ e is true if and only if p and p ′ share e as common arc. Since we model only one simple path by demand, we can use another trick by summing all the path for each demand. The meaning of the pp ′ e can be reformulated as : pp ′ e is true if and only if it exists p and p ′ for respectively d and d ′ .

We implement the logical AND (see chapter 7 of [START_REF] Bisschop | AIMMS optimization modeling[END_REF]) by this set of linear constraints :

pp ′ e ≤ p∈P d p e , ∀e ∈ E (6.14) pp ′ e ≤ p ′ ∈P d ′ p ′ e , ∀e ∈ E (6.15) pp ′ e ≥ p∈P d p e + p ′ ∈P d ′ p ′ e -1, ∀e ∈ E (6.16)
Then the cost constraints can be reformulated as follows :

∀e ∈ E, ∀i ∈ I, cwc i (e) ≥ (cost(e) + b i ) d∈D p∈P d p e × bw(d) + a i cap(e) d∈D p∈P d d ′ ∈D p ′ ∈P d ′ pp ′ e × bw(d) × bw(d ′ )
As in equation 6. [START_REF] Belardinelli | Relaxing Exclusive Control in Boolean Games[END_REF] we aggregate all costs for the different tangents :

∀e ∈ E, ∀i ∈ I, cwc(e) ≥ cwc i (e)
And thus the expression to be minimized as in equation 6.12 becomes :

min e∈E cwc(e)

Pricing problem

The reduced cost for a given variable determines how the objective changes if the variable increase of one unit. A Linear problem is optimal if its reduced cost is 0. However, if the reduced cost is negative, the solution can enter the basis as a new column. If the reduced cost is greater or equal than zero, the lower bound for the optimal solution has been found, although this may not be an integer solution. Note that the reduced cost can be computed on each edge individually. In order to find an improving path for each demand, we could perform a shortest path computation with Dijkstra's algorithm on the graph where arcs are labeled with reduced costs. The new variable of the discovered path already implicitly exists, and we just compute it on the fly. When it is not possible to improve the LP solution, it will be also not possible to find a path such that the reduced costs are negative.

Note that in our problem the decision variables (i.e. the paths) are not directly present with a coefficient in the objective function but instead appear though pp ′ e . And thus, the coefficients of the decision variable do not appear in the pricing problem.

In order to formulate the dual, let us give names to the constraints of the problem. We consider only the constraints that are potentially affected by the introduction of a new column. Let us call ON E d the constraint given in equation 6.8, CAP e the capacity constraint given in equation 6.9, and AN D1 e , AN D2 e , and AN D3 e respectively the constraints in equations 6.14, 6.15 and 6.16. By using these dual values found when solving the RMP, we are able to define the graph of reduced costs for a given demand d. For each edge e and demand d, we have :

rcost d (e) = -CAP e × bw(d) + ( d ′ ∈D AN D1 e + AN D2 e -AN D3 e )
Then the pricing problem for each demand d become now finding a shortest path in the graph of reduced costs, i.e. which minimizes the following formula for a path p defined by its Boolean variables p e :

min ON E d + e∈E p e × rcost d (e)
Unfortunately, the network labelled with reduced costs has negative cycles and thus Dijkstra's algorithm cannot be used to find a shortest path. Since we are only interested in simple path (i.e. a path without cycle), the pricing problem can be solved through a new Integer Linear Problem by the following flow model. Like before, let p e be the (continuous) variable associated to the arc e.

The following constraints ensure that only one unit of flow comes out from the source of the demand d and nothing enters in, and the reverse for the destination.

e=(src(d),y)∈E

p e = 1 e=(x,src(d))∈E p e = 0 e=(x,dst(d))∈E p e = 1 e=(dst(d),y)∈E p e = 0
Here are the flow conservation constraints :

∀v ∈ V, e=(x,v)∈E p e - e ′ =(v,y)∈E p e ′ = 0
Then we state non-splittability and no-cycle constraints :

∀v ∈ V, e=(x,v)∈E p e ≤ 1 ∀v ∈ V, e=(v,y)∈E p e ≤ 1
The objective becomes :

min   ON E d + v∈V e=(v,y)∈E p e × rcost(e)  
We extract from this flow the minimum path and introduce the corresponding variable.

Solution

A solution for the ILP model when using Column Generation is not equivalent to a solution with the Constraint Programming model. First the approximation introduced by the linearization of the exponential function tend to underestimate the congestion. Thus the value of the objective may be lower for the ILP model even if the solution paths are the same. Second, we solve the ILP problem only when the Column Generation procedure has ended. It may happen that in some cases this procedure does not terminate in a reasonable time. Then the integer solution is not computed and we get no solution.

Constraint Games

Constraint games for SDN

The MCPRP defined in section 6 can be simply extended to a game by considering each demand as a player who wants to find the best route from source to destination. Then each player wants to minimize her/his own cost as defined in equation 6.3.

If we denote by S = D V the total search space and by N the set of Nash equilibria, we can define formally the welfare of the best centralized solution adapted to our cost minimization problem by W * = min{w(s) | s ∈ S}. The welfare of the best Nash equilibrium is defined in a similar way by N * = min{w(s) | s ∈ N } and the one of the worst one by n * = max{w(s) | s ∈ N }. Thus the Price of Stability is simply P oS = W * /N * and the Price of Arnarchy P oA = W * /n * . Note that usually the classical definitions of PoS and PoA yield a result greater than 1, this is not the case here because we have a minimization problem. Note that, we have used IBR as a heuristic to go from the first solution to the first equilibrium In our problem, the social welfare function is simply the global cost to be minimized as defined in equation 6.4. We proceed in two steps. First the best centralized solution is computed as a Constraint Optimization Problem, then the Nash equilibria using our Constraint Games solver. We can immediately see that PoS and PoA are asymetric in term of the relaxation technique we can implement. For PoS, the problem is still a minimization. Thus we can use the same relaxation technique as the one we use in the centralized version (equation 6.7).

For the PoA, we have a maximization problem. But each player still wants to minimize her/his cost. The situation is then to find a set of shortest paths of maximal global cost. The standard relaxation technique provided by the CP solver provides a loose upper bound for this problem by summing up all upper bounds of the costs of the edges. But we know that the upper bound is at most the cost of the longest path in the residual network. Unfortunately, computing the longest path is NP-complete in the general case, since it corresponds to determine if it exists an Hamiltonian cycle, which is NP-complete [START_REF] Garey | Computers and Intractability : A Guide to the Theory of NP-Completeness[END_REF]. This problem has been already addressed in CP [START_REF] Pham | Solving the Longest Simple Path Problem with Constraint-Based Techniques[END_REF] where the authors propose a model and a local search algorithm to solve this problem. In our case, we are interested in a polynomial sound algorithm. This is why we propose to approximate the longest path by a Maximum Spanning Tree (MST) in the residual graph. The MST is computed by considering the upper bound value of the cost of the edges. The algorithm is like Prim's algorithm, we add to all remaining edges the cost of the demand to compute congestion, then we start by taking the most costly edge and add edges linking a new node in descending order of cost. It is clear that the cost of the MST is always greater than the cost of the longest path.

Related work

Combinatorial methods. SDN allows fast and remote network reconfigu- ration and thus is a nice source for many optimization problems [START_REF] Leguay | Online and Global Network Optimization : Towards the Next-Generation of Routing Platforms[END_REF] including online ones. Due to this dynamic aspect and the increasing size of the controlled networks, it is very likely that decentralized algorithms will be mandatory to provide both the expected quality of service and short time response. A survey of most techniques can be found in [START_REF] Lisser | Multicommodity Flow Problems and Decomposition in Telecommunications Networks[END_REF]. Since then, many extensions have been considered like the very important case of demands coming online [START_REF] Harks | Competitive Online Multicommodity Routing[END_REF][START_REF] Paris | Controlling flow reconfigurations in SDN[END_REF], service provisioning [START_REF] Huin | Optimal Network Service Chain Provisioning[END_REF], energy-aware routing [START_REF] Huin | Energy-Efficient Service Function Chain Provisioning[END_REF], controller placement [START_REF] Qin | SDN Controller Placement at the Edge : Optimizing Delay and Overheads[END_REF][START_REF] Sanner | An evolutionary controllers' placement algorithm for reliable SDN networks[END_REF], fault prevention [START_REF] Tajiki | Joint QoS and congestion control based on traffic prediction in SDN[END_REF][START_REF] Capone | Detour planning for fast and reliable failure recovery in SDN with OpenState[END_REF] or even congestion-aware algorithm [START_REF] Song | A congestion avoidance algorithm in SDN environment[END_REF].

Concerning the specific CP framework and to our best of our knowledge, only a few works have been considered : a problem of Service Function Chaining deployment [START_REF] Liu | Constraint programming for flexible Service Function Chaining deployment[END_REF] and a general framework providing through CP a high-level programming language to model SDN problems [START_REF] Layeghy | SCOR : Constraint Programming-based Northbound Interface for SDN[END_REF].

Our article differs from these methods because first, we propose a CP model taking into account non-linear congestion. Then, we optimize our model by proposing a relaxation technique based on Dijkstra algorithm as well as fast heuristics to solve the problem to optimality.

Quality of service and Game theory

Quality of service (or QoS) is an important problem in SDN and has been addressed in multiples ways. From combinatorial methods with for example with genetic algorithms [START_REF] Tran | Multi-objective multi-constrained QoS Routing in large-scale networks : A genetic algorithm approach[END_REF], or even multiples linear programs [START_REF] Szymanski | Max-Flow Min-Cost Routing in a Future-Internet with Improved QoS Guarantees[END_REF] optimizing multiples criteria such as bandwidth or energy consumption. These criteria concern the whole network which is different from game theory wherein each flow is considered as a criterion. A mechanism design method for multicommodity flow games has been proposed [START_REF] José | Fast, Fair, and Efficient Flows in Networks[END_REF] . Nonetheless, Game theory studies have been mainly concentrated with routing games [START_REF] Roughgarden | Routing Games[END_REF] to model uncapacited networks in order to determine how selfish behaviors impact solutions and to quantify it by the price of anarchy [START_REF] José | Fast, Fair, and Efficient Flows in Networks[END_REF]. Other mathematical studies on more general networks and solution's degeneration have been done such as on on capacited network [START_REF] José | Selfish Routing in Capacitated Networks[END_REF], unsplittable flow [START_REF] Awerbuch | The Price of Routing Unsplittable Flow[END_REF]. And even on different model based on distributed games [START_REF] Peter | Differential QoS and pricing in networks : Where flow control meets game theory[END_REF][START_REF] Hayrapetyan | A network pricing game for selfish traffic[END_REF].

Our approach is different since we propose a model to compute the PNEs and POA. The two Relaxations are given to fast the exact computation of the PNEs and POA giving a more pratical way to this kind of problems.

Instances and experimental results

We have tested our framework on a library of instances called SNDlib [START_REF] Orlowski | SNDlib 1.0 -Survivable Network Design Library[END_REF] and a personal problem generator that is able to generate instances close to real ones. This problem and other variants such as robust SDN networks have been studied for a long time [START_REF] Even | On the Complexity of Time Table and Multi-commodity Flow Problems[END_REF][START_REF] Capone | Detour planning for fast and reliable failure recovery in SDN with OpenState[END_REF] with some computational approaches including linear programming [START_REF] Azzouni | Neu-Route : Predictive dynamic routing for software-defined networks[END_REF]. A survey can be found in [START_REF] Mendiola | A Survey on the Contributions of Software-Defined Networking to Traffic Engineering[END_REF]. Interesting theoretical results have been found, like the one which states that when the problem has a sufficient size and capacity, all flows are actually routed along single-paths [START_REF] Puri | Algorithms for the Multiconstrained Routing Problem[END_REF].

Generator

We have designed a generator to create synthetic problems that allow to test the algorithms against the different hypothesis. Several parameters allow obtaining a great variety of graphs. The generation process is mainly constituted of two phases :

-Generation of the topology, that is nodes as well as arcs and their respective costs ;

-Generation of demands, along with their bandwidth requests, which also determines the capacities of the arcs.

During the generation of the topology, N nodes nodes are created. Each of these nodes n i with i ∈ [1, N nodes ] is assigned to random coordinates in a fixed size space of topologyDimension dimensions. In case the boolean topologicalCost is set to true, the cost of an arc is given by the distance between the source and destination node. Note that for dimension 2, this is not sufficient to ensure that the resulting graph is planar. The size of the space in one given dimension is irrelevant, as we refer to it only with percentage. Each node is also assigned to a degree, randomly chosen in an interval [deg min , deg max ]. To obtain graphs similar to actual networks, we introduce hubs which are nodes of higher degree than regular nodes. Each node has a probability P hub of being a hub. If a node is a hub, then its degree is randomly chosen in a different interval [degh min , degh max ].

We first build a spanning tree over all nodes to ensure that the graph is fully connected, then we create the remaining links in the graph. For each node, we look for candidates, so the desired degree is reached. For a link to be created, we ensure that a) the other node is not already connected with this edge and b) its distance in the space is not greater than maxDistance, expressed as a percentage of the space size ( √ topologyDimension is the maximum). Using this process, it is possible that certain nodes do not reach the desired degree, but as the network grow larger, this situation becomes less and less likely to happen.

Once the topology is generated, N demands are generated. For each of these, a starting node is randomly selected, as well as a bandwidth in a [bw min , bw max ] interval. We then generate what we refer to as an "initial path". For that purpose, different strategies are available. [START_REF] Daskalakis | The complexity of computing a Nash equilibrium[END_REF][START_REF] Henz | Global constraints for round robin tournament scheduling[END_REF][START_REF] Schulte | Finite Domain Constraint Programming Systems[END_REF], [START_REF] Daskalakis | The complexity of computing a Nash equilibrium[END_REF][START_REF] Henz | Global constraints for round robin tournament scheduling[END_REF][START_REF] Schulte | Finite Domain Constraint Programming Systems[END_REF] initcost min , initcost max integer [START_REF] Henz | Global constraints for round robin tournament scheduling[END_REF][START_REF] Schulte | Finite Domain Constraint Programming Systems[END_REF], [200, The last node is then considered to be the destination node of the request. During the navigation, we only make sure to never reach a node that is already in the initial path. The second strategy consists in randomly selecting a destination node, and applying a shortest path algorithm to find the path from the source node to the destination node with the least number of hops. The path yielded by the algorithm is considered to be the initial path. Regardless of how the initial path is constructed, for each of its arc, there is a probability P bw that we increase its capacity of the amount of bandwidth of the request. The list of all generation parameters, as well as short description can be found in Table 6.1.

Settings and implementation issues Experimentation settings

Due to the large number of parameters of the generator, we have applied a benchmark method called combinatorial testing [START_REF] Nie | A Survey of Combinatorial Testing[END_REF][START_REF] Hnich | Constraint Models for the Covering Test Problem[END_REF] using the ACTS software [START_REF] Yu | ACTS : A Combinatorial Test Generation Tool[END_REF]. This technique allows for p parameters and a size c to generate a set of instances where all possibilities of combinations of parameters of cardinality c are inside the set. For example, if we have 3 Boolean parameters a, b and c, a complete test of all possibilities would require 2 3 = 8 tests. But if we decide to test only all combinations of pairs, we can achieve this with only 4 instances (see Figure 6.12). With our generator, by choosing an appropriate sampling of the Figure 6.12 -All pairs of parameters are covered by 4 tests intervals described in 6.1, we get roughly 500 instances to get a covering of all 3-sets of parameters. From these 500 instances, we have discarded those whose resolution lead to a timeout for all techniques. This gives a total of 123 instances which give a meaningful picture of the range of problems that can be solved.

The tests have been performed on a cluster of Intel Xeon E5-2690, each having 10 cores sequenced at 3GHz and 256 GB of RAM. We have computed experimental results for the CP approach described in Section 6.1 and the Constraint Game model of Section 6.4 with a timeout fixed at 1 hour.

A note on implementations

The CP model has been implemented using the Choco solver [START_REF] Prud'homme | Choco Documentation[END_REF], including the Constraint Game through our Choco extension called Conga [START_REF] Palmieri | Constraint Games revisited[END_REF]. Besides the search techniques and different heuristics and the relaxation technique described in Section 6.2, our first implementation was using the Ibex solver [START_REF] Chabert | Ibex An iInterval based EXplorer[END_REF][START_REF] Chabert | Contractor programming[END_REF] in association with Choco. Real variables linked to Ibex were used to model the computation of the load, congestion and costs while discrete decision variables remained in Choco. However, this was not efficient because the two solvers need to communicate through Java Native Interface. In addition, many auxiliary real variables and constraints(e.g. constraint for the congestion cost and auxiliary variable for the sum) were used to compute intermediate values through constraint propagation despite this part is purely functional. In addition, the cost is also obtained as a by-product of the shortest path algorithm since at the end of the search tree the sum over the demands costs computed by the Dijkstra algorithm is the real cost. Therefore, we have replaced all the auxiliary variables and constraints computing the objective value by a single global constraint which also encapsulates the Dijkstra algorithm. At the end, the model only contains path and capacity constraints and the global constraint computing the objective.

The Column Generation model has been implemented using CPLEX [START_REF]CPLEX User's Manual[END_REF] version 12 with its Python interface. At first we tried to post all constraints at the problem initialization for all possible paths. However, it was not efficient since it takes a lot of time to initialize. Since most of the constraints (i.e. consider all the edges in the graph) are useless to solve the problem, we instead choose to post the constraints on the fly along each path when it was required after having generated the columns.

Once again, in the following, when we are saying that an instance is solved it has different meaning when we are talking about CP or CG. For CP, an instance is solved when the optimal solution has been found and proved. For CG, the instance is considered as solved when the generation procedure is finished and the ILP problem solved within the generated columns. Because of that, Column Generation does not prove optimality. Because of the linearization, the objective values are most of the time different between the two techniques.

Experimental results

Constraint programming model

For the synthetic benchmarks, we have displayed the results in Figure 6.13. As a preliminary test, we have tried the pure CP heuristic based on impact [START_REF] Refalo | Impact-Based Search Strategies for Constraint Programming[END_REF] to measure the gap with the SP value heuristics. A problem which should be easy (13 nodes and 9 demands) is solved in less than 1 second by using the shortest path strategy, whereas the impact strategy took 878.969 seconds. Due to this, we have not displayed this CP/CP/CP heuristics in the figure and we only present results for the SP strategy.

For each instance, we have run the combinations MB/SP/CP and MB/SP/SP, and the two conflict variants CO/SP/SP and CO1/SP/SP. The plot in Figure 6. [START_REF] Belardinelli | Relaxing Exclusive Control in Boolean Games[END_REF] shows how many instances are solved in a specific delay. Clearly, the MB/SP/SP heuristics outperform the other ones. This is not surprising compared with the CP-style B&B, but it shows that a more dynamic heuristic based on conflicts is not effective on this type of problems. We also compared the performances of the different strategies on the unsolved instances. Since, the solver did not finish either because it did not prove the solution's optimality, or because it did not find any solution, the only valuable comparison is the current solution and the time to find a first solution.

The performances for finding a first solution of the different strategies are shown in Figure 6.14. This figure presents the time required to find a first solution for all instances and given the three CP strategies. The instances are sorted by increasing time. As we can see, the strategies are very good at finding a first solution and on most of the instances. The strategies provide comparable performances when the goal is to find a first solution. Another interesting comparison is about the performances of the strategies on unsolved instances for getting the best solution. The table 6.3 presents how many times a strategy has found the best current solution while it timeout. MB is the strategy finding most of the time the best solution after a timeout. It appears that these instances are hard for multiples reasons. First it not a simple parameter which makes those harder. An instance can be hard even with 30 nodes and 30 demands. A problem become hard when the back-propagation of the relaxation is not enough and requires a lot of search. This effect is visible in the Figure 6.13, while comparing the instance which benefit from the SP relaxation against the one using the CP one. Most of the time the strategies take time to prove the optimality of a solution.

In the following, we only compare with the MB/SP/SP heuristic. The time in seconds for real instances from the SNDlib are shown in Table 6.2 only for two heuristic combinations. The improved relaxation technique allows to solve many instances to optimality. Each instance is described by its name (which corresponds usually to a network in a particular country), then the number of demands, nodes and links of the network. The SAT and UNSAT instances are the one for which we can find the optimal solution or prove unsatisfiability. For some instances depicted as UNKOWN, our method was unable to find the optimal routing. But still the best solution can be reported. We have run the ILP model on the same synthetic instances as the CP model. In our model, the number of initial columns can be parametrized. We show in Figure 6.15 a cumulative plot comparing the number of instances solved with different initializations. Each method starts with a different number of path from 1 to 15. It appears that starting with an unique path gives better performances.

ILP model with Column Generation

A reason which can explain this behavior it that if too many path are generated at start, many constraints have to be added and it slows down the initial simplex iterations and the next ones for each demands.

The real instances from SNDlib are shown in Table 6.4 along with the ratio of objective value between CG and CP. Due to many timeouts, there is no meaningful conclusion to be analyzed.

Constraint programming against Column Generation

To get a very synthetic insight of the respective strengths of the two approaches, we have depicted a set of comparisons in Table 6 Furthermore, we extracted some meaningful synthetic instances presented in Table 6.6. These instances present different kinds of behavior. In a few instances, the CG approach is able to find a better solution in shorter time. Sometimes the CG generation procedure times out and we are not able to find an integer solution in the given time. But interestingly, even if the CG has finished his generation procedure and the CP model times out and fails to prove optimality, it happens that the integer solution found by CG is still worse than the one returned at the end by CP.

We can see that very often CP performs better. One possible explanation about the bad result of Column Generation is how the RMP is linearized. When a new variable is entering the problem, the objective constraint is not modified. And thus the computed reduced cost are less efficient to improve the linear solution. This in turn slows down the global resolution by forcing the generation procedure while it is not required. In addition, the generation of one column needs to solve a NP-complete problem and it has to be embedded in ILP since no shortest path algorithm is applicable due to the negative cycles (see section 6.3). In contrast, the CP model benefits from a good heuristic which guides well the search space exploration, and moreover it has a good relaxation to bound the objective value when the search tree is explored in order to close the nodes.

Constraint games

For the Constraint Game model, we have only used the combination MB/SP/SP, with and without improvement of the first solution by IBR. Results show that IBR improves relaxation technique by giving quickly a good first solution which is also an equilibrium. (up to 1482 players in the janos-us-ca instance) can be solved to optimality by Conga [START_REF] Palmieri | Constraint Games revisited[END_REF]. Interestingly and in contrast with the synthetic instances, we have observed that IBR slightly degrades the computation time, this is why we did not include the column in the table. We believe that in these problems, most first solutions computed by the MB heuristics were already at equilibrium, and thus adding IBR only adds another check. We report the results for the computation of PoA and PoS for small synthetic instances in Figure 6.17. In most instances, we observe that the PoA and PoS are very close, and also very close to the centralized optimum. It means that on these problems, a decentralized algorithm would be very interesting to implement if we assume it scales up to larger problems. We have used much smaller instances because the PoA is very difficult to reach. The upper bound computed for the Maximal Spanning Tree overestimates the longest path which also overestimates the longest shortest path. We pay these two approximations by a limited pruning of the search tree which has a major impact on the computation time.

Conclusion

This chapter includes two practical contributions. First we have modeled and solved efficiently the unsplittable multi-commodity flow routing problem with congestion in Constraint Programming and in ILP with Column Generation. We have provided an accurate branch and bound technique that allows to solve real-world size instances up to optimality. Our third contribution is a Constraint Game model that allows to evaluate the potential of decentralized routing in this context. We have found all Nash equilibria for problems with thousands of player thanks to the Constraint Game solver Conga. This is the first time that such large instances are solved up to optimality by a general-purpose Game Theory solver. In this chapter, we summarize the contents and the contributions of the thesis by discussing the results along with some possible directions for the future work.

Chapitre 7

Conclusion and perspectives

Conclusion

This thesis revisits the constraint game framework which was firstly studied in [START_REF] Nguyen | Contrainte Jeux : modélisation et Jeux Résolution avec Contraintes)[END_REF]. The baseline formalism of constraint games was provided through this previous work. In this thesis we are going further by studding two axes of work : the computation of Nash equilibrium and the resolution of real world application. This thesis provides a more practical interest in multiples points :

-Modelling and solving games. Many frameworks have been proposed to solve games. From Dedicated approaches like Action-Graph Games [START_REF] Jiang | Action-Graph Games[END_REF], or more recently others paradigms like Boolean games [START_REF] Harrenstein | Boolean Games[END_REF] or Constraints Games [START_REF] Nguyen | Constraint Games : Framework and Local Search Solver[END_REF] based on combinatorial methods have been proposed. Besides a concentration of interest into these approaches, modeling and solving games is not an easy task. All the cited methods rely on ad-hoc algorithms. They do not benefit from the recent advances of solvers. In conclusion, our contributions are first to give a new view of constraint games and in a second hand to prove the solver's efficiency by tackling a networking problem.

Perspectives

This thesis thesis has been guided by practical aspects yielding to the solver's implementation and multiples improvements to model and to solve games. During this work, we had think about multiples future work. For instance, in the Location Game (see Example 19), what happen if two vendors have to share a stand. This can arise if a conglomerate decide to build a shopping mall. The location of both store have to be decided conjointly. The computation of one equilibrium, emphasizing the role of a good heuristics and opening comparisons with best response dynamics [START_REF] Ceppi | Local Search Methods for Finding a Nash Equilibrium in Two-Player Games[END_REF]. Dedicated heuristics taking advantage of games structure is still an open question and belongs to the perspectives of this thesis. Also, the extension to new solution concepts like the mixed version of the Nash equilibrium is an important step for the solver adoption and for Constraint games.

Mixed Nash equilibrium. Finding a mixed Nash equilibrium is a hard task and has been shown recently NEXP-hard [START_REF] Ianovski | Complexity of mixed equilibria in Boolean games[END_REF]. Like underlined in [START_REF] Nugent | Behavioural Strategies in Boolean Games[END_REF] computing a Mixed Nash equilibrium requires to have all the valuation of each action in order to apply well-known methods. However, it requires an exponential memory space which is intractable for large games that why constraint games are a new way to think about that. The Mixed Nash equilibrium can be an extension of the solver. A mixed Nash equilibrium is simply a maximization of the expectation for all players separately. A way to do that would be to estimate the expectation, by sampling for instance (as in [START_REF] Babichenko | Approximate Nash Equilibria via Sampling[END_REF]). A challenge could be the complete enumeration of the mixed Nash equilibrium with this technique which has to be complete for this purpose. Also, a good compromise between the accuracy of the estimation and the time spent has to be found in order to propose a competitive method. Additionally, the other solution concepts could be investigated, like the one for Cooperation or Strong Nash equilibrium.

Shared variables.

Originally in games, players exercise unique control over a set of variables (or strategies) in order to achieve a unique goal. It may happen however that the unique control is too restrictive as in the meeting scheduling game (see Example 37).

Example 37 (Meeting scheduling) This problem is an adaptation from [140]

A set of agents want to schedule a set of meetings. Each has a set of compulsory attendees while a set of other participants are encouraged to assist. Each meeting has a starting time and a fixed duration. The starting time of each meeting is defined by the agents participating in it. The meetings have to respect some ordering constraints. For instance, a meeting has to start before noon due to participants in other time zones. A natural way is to let the attendees of a meeting control a unique decision variable. The variable ownership is going to be shared. Each agent is part of the decision process to specify the starting time of each meeting where he is involved. But many agents can be required for the same meeting and thus have to share the same variable.

However, a model expressed with a shared variable has no solution most of the time. The problem is that players sharing a variable have to agree completely on a solution. Which is very rare in practice. For example, the simple instance of meeting scheduling shown in Figure 7.1 does not have a Nash equilibrium. In this situation, if the players do not compromise together then the meeting M 2 is problematic. The black player would like to put it just after M 1 , while the blue one wishes to put it next to M 4 . Relaxation such as voting systems, partial cooperation can be studied in order be able to provide a solution. The challenge of this new concept is not limited to only the solution concept since it requires to be computed as fast as possible because of the potential large instances. The propagators can be studied in order to prune the search space and give better performances.

In summary, we are confident that an efficient solver as much as possible complete, open source, would be very appreciated in practice and by the community.

Annexe A

Objective criteria for robust search strategies

In this section we give the work done in this thesis but not directly related to the subject.

A.1 Objective Function and Search Strategy

Search strategies aim to reduce the search space, but additionally aim to find good solutions as quickly as possible. Most SSs choose the hardest variables to satisfy first, the main challenge being to find such variables. While most SSs decisions were based on variables domains, the constraint graph, etc, objectivevalue based decisions are rarely done in CP. One of the reasons is that, in CP, we cannot easily back-propagate the objective to the variables to make decisions as done in Mixed Integer Programming. But even if we can not have such exact information, not taking into account the variables impacting the objective value can lead to an exponential loss in time. This is shown by the following synthetic example.

Example Consider a COP having n + m variables and whose objective is the sum of the last m variables. This problem has an AllDifferent constraint [START_REF] Régin | A filtering algorithm for constraints of difference in CSPs[END_REF] over all the variables. Ignoring the objective value can lead to the search tree shown in Figure A.1 (left). In this example, the strategy focuses only on other features, without taking the objective into account. Whereas a strategy that considers the objective detects variables having high impact on the objective, and consider them earlier enabling a potential reduction of the search tree.

Moreover, we can find high quality solutions earlier and these solutions prune the search space more efficiently. As we can see, the processing of the m variables is repeated an exponential number of times (d n ). This is because the variables that impact the objective are chosen too late leading to a bigger search tree.

The search tree using the objective value as a feature is shown in Figure A.1 (right). The last m variables are selected higher in the search tree, yielding better solutions faster and allowing to close the search using the objective sooner. Finally, by using the objective value, we obtain a smaller search tree.

This simple example shows that the objective value allows to assign variables having high influence on the objective earlier and thus can help the solver to avoid considering useless parts of the tree. The idea is to consider as soon as possible the variables impacting the objective. We now define a new feature based on the objective, which we will use to define an objective-based search strategy.

Objective modifications as a feature

The proposed feature focuses on the objective bounds modifications by using a function ∆ O . The upper and lower bounds are separately considered as two different pieces of information. Let O be the objective variable to optimize. Let s and s -1 be respectively the current and the previous node of the search tree. Let ∆ O (resp. ∆ O ) be the upper (resp. lower) bounds difference between its value before and after the decision propagation. The function is defined as follows :

∆ O (s) = a × ∆ O + b × ∆ O
We choose to consider the upper and lower bounds separately. The choice of the parameters a and b defines the function behavior. The coefficients can take any value and correspond to the importance (positive or negative) given to each bound. For instance, in minimization problems, the coefficient a of lower bound modification corresponds to the weight for the consideration of removing the best potential solutions. While, the upper bound modification coefficient b, represents the weight to consider the deletion of the worst potential solutions.

Note that this function has a more fine-grained description of the objective than usual measures used in search strategies. Classic SSs monitor the modifications of the decision variables, but in general, treating differently the lower and upper bounds, has no meaning for such variables.

Objective-Based Selector (OBS)

We propose a new variable selector based on the ∆ O function : OBS. OBS first selects the variables having the highest impact on the objective with regard to the ∆ O function. To do so, the weighted sum of the ∆ O function values for each x ∈ X is monitored through ∆ O (x), and updated after each decision involving the variable x. The parameter γ is the degree of weighting decrease of the exponential moving average. The updated value ∆ O ′ (x) is processed as follow :

∆ O ′ (x) = ∆ O (x) * (1 -γ) + γ * ∆ O (x) γ At each decision, OBS selects the variable x ∈ X such that ∀y ∈ X, ∆ O (x) ≥ ∆ O (y).

Example

Consider the didactic COP defined by the variables (x 1 , x 2 , x 3 , x 4 ) having each as domain D = [START_REF] Ågotnes | Verifiable Equilibria in Boolean Games[END_REF][START_REF] Arthur | Complexity in Economic Theory. Inductive Reasoning and Bounded Rationality[END_REF] and an AllDifferent constraint on the 4 variables. The COP's objective is min x 3 + x 4 . We use the parameters (a = -1,b = 1) for the ∆ O function, in order to penalize lower bound modifications and reward upper bound modification.

The tree search from Figure A.2 shows the application of the objective based search strategy versus a lexicographic search. In this example, when a variable is selected, it is assigned to its minimum value. The lexicographic search on the left has more decisions than OBS on the right because it cannot identify which variable are important to satisfy the constraints and improve the objective.

At the beginning of the exploration, in the right tree showing OBS search, the variables x 1 , x 2 and x 3 are selected and set to their minimum values. Each of these assignments has an effect on the objective's bounds and thus modifies ∆ O . When the decision x 1 = 1 is propagated, ∆ O (x 1 ) is set to -2 because of the changes of the objective domain from [START_REF] Allouche | Anytime Hybrid Best-First Search with Tree Decomposition for Weighted CSP[END_REF][START_REF] Babichenko | Approximate Nash Equilibria via Sampling[END_REF] to [START_REF] Arthur | Complexity in Economic Theory. Inductive Reasoning and Bounded Rationality[END_REF][START_REF] Babichenko | Approximate Nash Equilibria via Sampling[END_REF]. The propagation of x 2 = 2 reduces the objective's domain from [START_REF] Arthur | Complexity in Economic Theory. Inductive Reasoning and Bounded Rationality[END_REF][START_REF] Babichenko | Approximate Nash Equilibria via Sampling[END_REF] to [START_REF] Awerbuch | The Price of Routing Unsplittable Flow[END_REF][START_REF] Babichenko | Approximate Nash Equilibria via Sampling[END_REF] implying ∆ O (x 2 ) = -2. When the variable x 3 is selected, the objective is instantiated to 7. This implies a ∆ O (x 3 ) = 0. A solution is found with the value 7, so the next solution has to be smaller than 7. Afterwards the decision x 3 = 3 is refuted and the search tree is backtracked to the decision x 2 = 2 which is refuted, implying x 2 = 2. Then x 3 which has the highest ∆ O value is selected and instantiated to its domain's minimal value : 2. Then x 4 is the next free variable with the highest ∆ O value, 0. We thus select x 4 and assign it to its smallest value, 3. We find a solution equal to 5. Finally, when this branch is closed, the decision x 1 = 1 is refuted and by applying the OBS selection, the branch leading to the best solution is explored. An important aspect of this search is that it is close to human intuition to choose first variables x 3 and x 4 since they belong to the objective.

x 1 = 1 x 1 = 2 x 1 = 3 x 2 = 2 x 3 = 1 x 1 = 2 x 2 = 4 x 3 = 1 x 3 = 1 x 1 = 1 x 2 = 2 x 2 = 3 x 3 = 2 x 3 = 2 x 2 = 3 x 3 = 2 x 2 = 2 x 3 = 3 x 3 = 3 x 1 = 1 x 3 = 1 x 3 = 2 x 3 = 1 x 4 = 2 x 1 = 3 x 1 = 1 x 2 = 2 x 3 = 2 x 4 = 3 x 2 = 2 x 3 = 3 x 3 = 3
Note that the maintenance of ∆ O values and the selection process are simple and not intrusive in solvers. Moreover, OBS does not need to change the constraints implementations.

Hybridization of search strategies

In this section we show how the objective and classical features can be combined together, to benefit from both. But most strategies should not be directly combined due to the range differences of their feature. For example, the IBS strategy has a value range between [0, 1], while ABS one is between [0, n]. We propose to normalize all these values to fit in the interval [0, 1] in order to combine them. Note that this applies to the ∆ O function as well.

Let S n (x) be the normalized value of a search strategy S based on a classical feature. And let ∆ n O (x) be the normalized values for OBS. We combine the two pieces of information with the following formula :

S O (x) = α * S n (x) + (1 -α) * ∆ n O (x)
The hybrid search strategy selects the variable maximizing S O . The values α and (1α) represent the importance given to each feature. Note that α is in [0, 1].

Example with ABS O : While the ABS strategy uses the A values, storing the activities involved by the variables, our modification of the value associated with each variable is the sum :

ABS O (x) = α * A n (x) + (1 -α) * ∆ n O (x)
This ABS O (x) value contains both pieces of information : the activity and the objective modifications.

Remarks : The hybridization of many others strategies is as simple as for ABS. For the following sections, we respectively denote the hybridized versions of ABS, IBS and W Deg by ABS O , IBS O and W Deg O .

A.2 Experiments

The Experimental Setting Configurations All experiments were done on a Dell machine having four Intel E7-4870 Intel processors and 256 GB of memory, running Scientific Linux. We implemented these new strategies in the Choco 4 CP solver [START_REF] Prud'homme | Choco Documentation[END_REF]. Each run used a time limit of 30 minutes. The strategies were warmed up with a diving step, using up to 1000 restarts, or by ensuring a certain number of decisions. The same warm up (method and seed) was used for all the methods, in order to avoid any bias.

Benchmarks

The experimental evaluation used on the MiniZinc Benchmark library [START_REF] Nethercote | MiniZinc : Towards a standard CP modelling language[END_REF], with benchmarks that have been widely studied, often by different communities, including template design, still life, RCPSP, golomb ruler, etc. Many problem specifications can be found in [START_REF] Et | CSPLib : a benchmark library for constraints[END_REF]. Every class of optimization problems from the MiniZinc library has been considered. Since the number of instances per family is huge, and has a large variance between families, we have randomly selected up to 10 instances per family. Such subset selection preserves the diversity of instances, and do not favor a specific kind of family in plots. The problems have been translated into the FlatZinc format, using the MiniZinc global constraints library provided by Choco-solver, which preserves the global constraints.

Plots

The scatters and curves presented in this section are in log scale. A scatter plot shows the comparison of two strategies instance by instance. The diagonal separates the instances where each method has performed better than the other. The points above (resp under) the line correspond to the instances where the ordinate (resp the abscissa ) strategy is less efficient. Larger is the gap between the axis line and the point, bigger is the difference between the strategies. Extreme points above and on the right correspond to the timeouts.

Terminology An instance is said to be solved, when the best solution has been found and its value proved to be optimal. The term solution quality is used when the search is incomplete, and only the best found solution can be judged.

OBS evaluation

Once again, the OBS selector is highly configurable : each bound can have its own coefficient impacting the selection process. The running time of several configurations with different bounds importance have been profiled. The values -1, 1 and 0 have been tested to respectively give : negative, positive, or no importance to the considered bound. All possible pairs of (a,b) from (-1, 0, 1) × (-1, 0, 1)\{(0, 0)} have been tested.

The performance of different OBS parameters are shown in Figure A.3. This cumulative plot shows how many instances can be solved by each method, for a given time limit. This plot shows that a negative cost to the lower bound outperforms zero or positive cost, regardless of the upper bound.

Configurations weighting the lower bound negatively solve approximately 50 more instances than the alternatives. The solution quality has been compared as well : Figure A.4 shows how many time a search has found the best solution (not necessarily optimal) compared to its alternatives. Once again, the searches weighting the lower bound negatively show better results. One intuitive explanation is that choosing the variables impacting the less the bound which has to be optimized, concentrates the search into the most promising parts and like shown in Example A.2 helps to back-propagate the objective to prune the tree search. Furthermore, the upper bound in optimization problems (here minimization, without loss of generality) does not have a big impact on resolution time. In addition to our previous intuitions, the upper bound seems to be very sensitive to initialization and to propagation. For instance in some constraints such as sum, which often determines the objective value, no arc consistency can be achieved in polynomial time. But, often, only the bounds are filtered, making less consistent the variations of this variable. Based on different OBS experiments, the configurations (a=-1,b=0) and (a=-1,b=-1) seem to be the most promising.

Evaluation of Hybrid Strategies

We tried the hybridization with all the OBS configurations in order to select the most promising one. The configuration (a = -1, b = 0) got better results within the hybridization, both in run-times and best objectives, which confirms our previous results. In the following, when no configuration is specified for OBS, then it means that the configuration (a = -1, b = 0) has been used. Like OBS, the hybridization method is configurable in different ways. More or less importance can be given to the objective, or to the classical feature. In order to find the best parameter α, different experiments have been done. shows how the objective feature impacts the search to find good solutions. It compares the number of times a search against its hybridized version has found a better solution. Unlike IBS, ABS and WDeg seem to benefit from the objective features, since their hybridized versions often find better solution than the original ones. For instance, the classical ABS find less than 10 better solution compared to its hybridized version which find more than 100 times.

To support again the interest of the hybridization method, we have extracted some interesting problem families in the From the different plots and table presented, we remark that IBS is an exception because neither the original nor the hybridized version dominates each other and thus does not benefit as much as other search strategies from the hybridization. Actually, IBS contains already some information about the objective bounds modifications. The impact is computed over all variables including the objective. This is why the combination of the two features does not lead to a domination, but only an improvement in several problems and a decrease in some others. The resulting search is an orthogonal search to IBS.

Overall evaluation

Figure A.9 shows how many instances were solved as a function of time over all strategies. Without any hybridization IBS is the best strategy. However, with the hybridization, ABS shows the best improvements and so ABS O become the best strategy. ABS O has the largest number of solved instances under the allotted time. Furthermore, the hybridized versions are very competitive and improve the number of solved instances. Such a result confirms that using the objective as feature leads to strong improvement in solving time.

Most of the time, in real life problems, the optimal solution cannot be found or proved due to time limits. That is why we now compare the capabilities of OBS and the hybridized versions to find good solutions under an allotted time. The new hybrid strategies are very competitive in finding good solutions under a given amount of time as well. Figure A.8 shows how many times a search strategy has found a strictly better solution than all the others. Searches using the objective feature are depicted in yellow and the others in blue.

ABS O surpass the others and was able to find 30 times a strictly better objective than the others, while its original version ABS never finds a better solution. IBS and OBS seem to be the second best search strategies in terms of score. The hybridization shows again its advantages since ABS O is strictly better than ABS. W Deg O slightly dominates W Deg and OBS has a good rank.

Miscellaneous discussions

The objective can be monitor in many different ways. The ∆ O (t) was not our only trial, we tried to monitor the changes through a qualitative function counting how many times a variable modifies either the lower or the upper bounds. On the Minizinc Library, the qualitative function was dominated by the quantitative one.

Furthermore the ∆ O (t) function was used to designed a value selector. Different variants have been tried : first to select the value minimizing ∆ O (t), with possibly different values for a and b. Second to select the value using the new value heuristic from [START_REF] Fages | Making the first solution good ![END_REF]. However, even if on some instances such as ghoulomb or openstack these selector showed a real improvement, they seem to globally be dominated in the Minizinc problems set by minVal. The definition of a good value heuristic seems to still be a challenge to solve.

Our experimental section shows that combining classic search strategies with our objective-based feature leads to better performances and the ability to solve new problems. It shows that for ABS and WDeg adding an objective-based feature seems to dominate their performance. Finally it shows that the objective as a feature can play an important role in finding a good solution faster, as already claimed [START_REF] Fages | Making the first solution good ![END_REF].

A.3 Related Work

The objective variable in COPs has already been considered in other fields such as max-SAT [START_REF] Heras | New inference rules for efficient Max-SAT solving[END_REF] to choose which literal to select, or in Soft-CSP for the decision value [START_REF] Larrosa | Solving weighted CSP by maintaining arc consistency[END_REF]. Large Neighborhood Search (LNS) framework also consider the objective : for example by changing the term of the weighted sum to minimize [START_REF] Lombardi | Cost impact guided lns[END_REF]. In constraint programming, the objective information is not yet well used. In [START_REF] Levasseur | A value ordering heuristic for weighted CSP[END_REF], the authors propose a heuristic for weighted constraint satisfaction problems based on the solution quality to guide the value selection during the search. In [START_REF] Chu | Learning Value Heuristics for Constraint Programming[END_REF], the authors propose a machine learning approach to learn the objective function from the variables' values, but not directly on the variables themselves.

More recently, counting based search has been adapted for optimization problems [START_REF] Pesant | Counting-Based Search for Constraint Optimization Problems[END_REF], the main idea being to consider objective-based solution density instead of a simple solution density. This is done by adding to each objective-based constraint an additional algorithm processing these values. Also, in MIP, the objective is widely used in the heuristic [START_REF] Gauthier | Experiments in mixedinteger linear programming using pseudo-costs[END_REF] : the variables having the best impact on the objective value of the relaxed problem are selected first. This approach differs from our, since CP does not have good relaxation as MIP and we consider the hybridization of the search strategies. A recent work [START_REF] Fages | Making the first solution good ![END_REF] uses the objective information in order to select the variable value, leaving the variable selection to another strategy. Our method differs from [START_REF] Fages | Making the first solution good ![END_REF] since we propose a variables selector, while [START_REF] Fages | Making the first solution good ![END_REF] proposed a value selector. Secondly, we are trying to learn on-the-fly all along the search tree which variable seems to be the most promising, unlike [START_REF] Fages | Making the first solution good ![END_REF]. In [START_REF] Fages | Making the first solution good ![END_REF] the value is selected by testing all the possible assignments of the variable's domains to determine after the propagation which value is the best. Moreover, our feature is more fine-grained because it can be determined how strongly to emphasize bound modifications, using positive or negative parameters. In addition, in this appendix we propose an hybridization of existing searches with the objective feature. More particularly our new strategies can be added into the set of available strategies to choose to solve a problem, even in online fashion [START_REF] Xia | Learning Robust Search Strategies Using a Bandit-Based Approach[END_REF].

A.4 Conclusion

We have demonstrated the need for using the objective variable as a feature for decisions within search strategies in constraint programming. We have defined a fine grain feature based on objective bound modifications. By using this new feature, we have designed a new variable selector named OBS. This new variable selector is not the most efficient, but it is able to overpass the existing ones on some class of problems. Moreover, we have proposed a hybridization method to combine our proposed objective-based feature with many existing search strategies. Our evaluation has shown that the hybridized searches give great results and are better than the original strategy in term of run time and solution quality. Some searches are dominated by their hybrid versions. Through this new perspective, we have shown that using the objective as a feature to make decisions can lead to strong results. In addition, further work can be done, for example, with non valued SSs like the ones using a ranking criteria such as COS [START_REF] Gay | Conflict ordering search for scheduling problems[END_REF]. Directly applying this work on such SSs is not trivial, and should be a next step.

For both the ∆ O (t) function and the hybridization, we consider here only a linear combination of the values. More complex combination scheme can be considered. For example, non linear function or ranking function could be studied.

Finally, parameter optimization methods [START_REF] Hutter | An evaluation of sequential model-based optimization for expensive blackbox functions[END_REF] could be used in order to find the best values of a, b and α for a given family of problem while solving it. buildModel method is the internal way to construct a game. This method provides as a parameter a model object in order to build the variables and the constraints. Also, when a game model is built, it has to call the super constructor. This call defines the number of players in the game. Then, when it associated with an instance of CongaSolver, it builds the players data-structures and then create the players objects. These players instances are used to define players behaviors, specify the players search strategies, their goals... Note that to build a game you need absolutely to use these functions. Conga builds the constraints, data-structures, and players through it.

An optional method defineObjective can be overridden. This function enables to define a function which has to be optimized, while seeking for Nash Equilibriums. Note also that the players are indexed from 1 to n in an array provided by the AbstractGameModel. The player 0 is a flag for the data structures or can be used to put any new behavior which cannot enter in the current framework (like a new player with a different behavior).

Wolf Lamb 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.

The game 's model code is provided in the following and can be found in the examples folder of the project. This last instruction is done by the function prepareAndGetSolver() which return a solver in the Choco sense. Most of the time, to ease the modelization part, factories are provided. These factories can be found in the folder src/factories

The following example shows how to find the Pure Nash Equilibrium in the WolfLambCabbage game using the LAST_LEVEL constraint. This last one is a version of the propagator proposed in [START_REF] Levasseur | A value ordering heuristic for weighted CSP[END_REF]. Another propagator named BOUND_CONSTRAINT can be used. This propagator is the new algorithm proposed in [START_REF] Mendiola | A Survey on the Contributions of Software-Defined Networking to Traffic Engineering[END_REF]. Also a possibility which can be helpful while debugging is to specify that the game has no constraints with NO_CONSTRAINT .

Finally, the function solve from the solver to find the Nash equilibriums of the game can be called. -IEquilibriumConcept : defines the concept which has to be computed. Most of the time it is the Nash equilibrium. It can be useful to extend the solver to other multi agent problems.

-ISearchPolicy : defines the search policy : how the exploration is made in the players' deviations search space. This Interface can be useful to define incomplete search or any new kind of search like Pareto Best response.

-PlayerDependenciesUpdater : this interface allows to create a graphical game and limit the number of time a player's constraint is awakened.

Going further

We list here some important class which may be useful to modify the solver behavior.

-VarHelperImpl is the implementation of the interface Varhelper which provides data structures to retrieves the variables and objectives of the different players. It can be useful to know if a variable or an objective is shared. You can then ask within this class if such case happens in the game.

-Executable is the interface to implement more general algorithms. You can find the examples in the enum AlgorithmFactory with for instance the algorithms NASH, IBR, PARETO_NASH, and the pricing function such POA or POS.

Gambit reader

If you are really attached to gambit solver, we provide a way to solve gambit representation through our solver. To use gambit you first have to define the global variable GAMBIT_PATH to specify where gambit executable is located. More information of this interface can be found in the class GambitNFGParser which take as input a normal form game as defined in gambit, and output a model in constraint game. The transformation used is quite simple, the matrix is transformed into table constraints.

Résumé Nouvelles techniques pour les Contraints Games

Cette thèse présente de nouvelles techniques pour les Constraint Games. La manière de résoudre un Constraint Game est repensée en terme de propagation de contraintes. Les préférences des joueurs sont maintenant considérées comme des contraintes globales permettant une intégration transparente dans les solveurs de contraintes ainsi que d'améliorer l'efficacité du framework. Notre nouveau solveur ConGA est diffusé en open source 1 . Celui-ci est plus rapide que les travaux connexes et est capable de trouver tous les équilibres de Nash, et cela même dans des jeux avec 200 joueurs voir 2000 pour certains jeux graphiques.

Grâce à cette perspective, le framework a pu être utilisé pour résoudre un problème de routage dans le domaine des télécommunications. Les aspects centralisé et décentralisé ont été étudiés. La comparaison de ces derniers est très importante pour évaluer la qualité de service dans les applications multi-utilisateurs. L'évaluation de cette dernière peut être très coûteuse, c'est pourquoi nous proposons plusieurs techniques permettant d'améliorer la résolution de ce problème et ainsi d'améliorer la résolution du problème.

Constraint Games revisited

This thesis revisits the Constraint games framework by rethinking their solving technique in terms of constraint propagation. Players preferences are considered as global constraints making transparently the integration in constraints solvers. It yields not only a more elegant but also a more efficient framework. We release our new solver ConGA in open source 1 . Our new complete solver is faster than previous state-of-the-art and is able to find all pure Nash equilibrium for some problems with 200 players or even with 2000 players in graphical games.

This new perspective enables us to tackle real-worlds Telecommunication problems. This problem is solved with a centralized perspective and a decentralized one. The comparison of the two last approaches is really important to evaluate the quality of service in multi-users application, but computationally consuming. That is why, we propose new techniques in order to improve the resolution process.

Mots-clefs-Constraint Programming, Game theory, Nash Equilibrium, Search strategy

6. 5

 5 Labeling of paths for two demands . . . . . . . . . . . . . . . . . . . . 6.6 Selection process of MB strategy . . . . . . . . . . . . . . . . . . . . . 6.7 Selection process of CO strategy . . . . . . . . . . . . . . . . . . . . . 6.8 Selection process of CO1 strategy . . . . . . . . . . . . . . . . . . . . 6.9 Problem's relaxation example for SDN . . . . . . . . . . . . . . . . . . 6.10 Column generation procedure . . . . . . . . . . . . . . . . . . . . . . . 6.11 Three pieces linear approximation of the exponential function . . . . . 6.12 All pairs of parameters are covered by 4 tests . . . . . . . . . . . . . . 6.13 Comparison of different CP heuristics on synthetic benchmarks . . . . 6.14 Comparison of the strategies for finding the first solution . . . . . . . 6.15 Comparison of different initialization of the Column Generation model102 6.16 Comparison Nash and and the different heuristics on synthetic benchmarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.17 Price of Anarchy and Price of Stability for small synthetic instances .7.1 An instance of the meeting scheduling . . . . . . . . . . . . . . . . . . A.1 (left) A search failing to consider the objective value. (right) An objective based search. . . . . . . . . . . . . . . . . . . . . . . . . . . A.2 Comparison of the search tree by a lexicographic search (top) and an objective based search (bottom) . . . . . . . . . . . . . . . . . . . . . A.3 Comparison of the number of solved instances for different OBS configuration. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.4 Comparison of the objective quality between different OBS configurations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.5 Running time comparisons of the hybrid strategies, with respect to the hybridization parameters. From left to right and the top to the bottom, the configurations of ABS with (0.25), (0.5), (0.75) and (0). A.6 Comparison of the original search against their hybridized version . . A.7 Comparison of the objective quality between search strategies and their hybridized versions. . . . . . . . . . . . . . . . . . . . . . . . . . A.8 Number of instances where each search strategy has found a strictly better objective compared to all the other. . . . . . . . . . . . . . . . A.9 Comparison of the number of instances solved by the different strategies as a function of time. . . . . . . . . . . . . . . . . . . . . . . . .

Figure 2 . 1 -

 21 Figure 2.1 -A maps and its optimal coloration

1

 1 Taxonomy of game's Categories . . . . . . . . . . . . . 24 Players interactions : static and dynamic . . . . . . . . 24 Cooperation and selfishness . . . . . . . . . . . . . . . . 26 Game's knowledge . . . . . . . . . . . . . . . . . . . . . 26 3.2 Games' representations . . . . . . . . . . . . . . . . . . 27 Extensive representations . . . . . . . . . . . . . . . . . 27 Combinatorial games . . . . . . . . . . . . . . . . . . . 31 3.3 Solution concept and their algorithms . . . . . . . . . . 33 Pure Nash equilibrium . . . . . . . . . . . . . . . . . . . 33 Best response dynamic . . . . . . . . . . . . . . . . . . 35 Nash equilibrium relaxations . . . . . . . . . . . . . . . 37 Quantifying the efficiency of equilibrium . . . . . . . . . 39 3.4 Games example . . . . . . . . . . . . . . . . . . . . . . 40

Figure 3 . 1 -

 31 Figure 3.1 -Tic tac toe possibilities

Figure 3 . 2 -

 32 Figure 3.2 -An example of bi-matrix representation, also called normal form

Figure 3 .

 3 Figure 3.3 -WLC game in normal form

Figure 3 . 4 -

 34 Figure 3.4 -Dependency graph of the WLC game.

Figure 3 . 5 -

 35 Figure 3.5 -Wolf Lamb Cabbage Game in AGG

Figure 3 . 6 -

 36 Figure 3.6 -Best response of WLC game in normal form

1 :

 1 procedure IBR(game : G = (P, A, u))

Example 16 (

 16 Pareto Nash and Strong Nash equilibrium) Consider the toy game in the Normal form, depicted in Figure 3.7. This example shows two games and aims to underline the differences between Strong Nash Equilibrium and Pareto Nash Equilibrium. Both situations have 3 PNEs which are on the diagonal. In the first matrix (see Figure 3.7a) a SNE is reached when both players are playing s 1 . This SNE is also a Pareto Nash since it corresponds to the best possible choice of the players among all possible combinations. The other equilibriums are only PNEs and not Pareto PNE because the SNE dominates the other equilibriums.

Figure 3 . 7 -

 37 Figure 3.7 -A toy example showing a SNE and Pareto efficiency

Example 20 (

 20 Example 19 continued) In the Figure 4.1, an instance of Location Game with 3 sellers and 14 customers is shown. The sellers are represented by the triangles, and their price are shown inside it. One customer is located at each position. Each green arrow represents a customer choice.

Figure 4 . 1 -

 41 Figure 4.1 -Players' deviations in the location game

  .

  2.

Figure 4 . 2 -

 42 Figure 4.2 -Location game with undetermined behavior

Figure 4 .

 4 3 presents some situations where the beliefs modify the utility of each player. The Figures 4.3a,c and d present how the players are going to interpret the customers' behavior. Each player's belief is symbolized by a colored arrow.The yellow (resp. orange) player's belief on customers behavior is symbolized by a yellow (resp. orange) arrow. In the Figure4.3a and Figure4.3c, it is unknown where the customer in position 3 would go. Instead both players believe that the customer is going to the yellow vendor located in position 5. That is why, the orange player deviates (Figure4.3a) of one position to the left to get another customer(Figure 4.3b).

Figure 4 . 3 -

 43 Figure 4.3 -Location game with beliefs

Figure 4 .

 4 4 presents an instance of Location game with one shared store. Two vendors : the orange and the yellow have each one store and share one. The stores are still symbolized by the triangle, and fill by the owners' color. Now a triangle might have multiple colors. This is the case for a shared store like the one in position 7 in the Figure4.4a.

Figure 4 . 4 -

 44 Figure 4.4 -Location game with a shared stand

Figure 4 . 5 -

 45 Figure 4.5 -One shared binary variable under the normal form.

Figure 4 . 8 -Figure 4 . 9 -

 4849 Figure 4.8 -Z's payoff

Example 28 (Figure 4 . 10 -

 28410 Figure 4.10 -Location game's solutions without and with hard constraints

5 . 1

 51 Preferences as Global Constraints . . . . . . . . . . . . 61 5.2 Nash propagator applicability . . . . . . . . . . . . . . 65 5.3 Related work . . . . . . . . . . . . . . . . . . . . . . . . 66 5.4 Experiments . . . . . . . . . . . . . . . . . . . . . . . . 67 5.5 Graphical Aspects . . . . . . . . . . . . . . . . . . . . . 68 5.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . 69

  and v a be the respective values of x and a set by Player 1. If s Y = nbr, then Player 2 assigns b = v a . If s Y = nbr, then Player 2 assigns y = v x . Hence nbr is a never best response.

Figure 5 . 2 -

 52 Figure 5.2 -An example of inconsistent filtering of preferences

Figure 6 . 1 -

 61 Figure 6.1 -Software Defined Networking

Figure 6 . 2 -

 62 Figure 6.2 -A plot of the congestion function for M axC = 1000 and cong ′ (0.2) = 1

Figure 6 . 3 -

 63 Figure 6.3 -Encoding of a path

Figure 6 . 4 -

 64 Figure 6.4 -Residual graph updates examples

Figure 6 . 5 -

 65 Figure 6.5 -Labeling of paths for two demands

Example 35 (

 35 Strategies in action) In this example, we show the selection process of the three strategies with SP value SS. Three demands d 1 , d 2 and d 3 with respectively a bandwidth of 4, 3 and 2 have to be routed in the 6-nodes network. To keep things easy, all edges have a capacity of 7, a cost of 0 and congestion parameters are set to a = 1 and b = -0.5. The selection process of MB, CO and CO1 are shown respectively in Figure 6.6, Figure 6.7 and Figure 6.8.

Figure 6 . 6 - 3 7 + 4 7 3 7 19 ∆(price d 2 ) = 2 × ( 7 × e 4 7 + 3 7 -0. 5 - 4 × e 4 7

 663431922743544 Figure 6.6 -Selection process of MB strategy

Figure 6 . 7 -∆(price d 1 ( 1 Figure 6 . 8 -

 671168 Figure 6.7 -Selection process of CO strategy

Figure 6 . 10 -

 610 Figure 6.10 -Column generation procedure

Figure 6 .

 6 Figure 6.11 -Three pieces linear approximation of the exponential function

Figure 6 . 17 -

 617 Figure 6.17 -Price of Anarchy and Price of Stability for small synthetic instances

Contents 7 . 1

 71 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . 107 7.2 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . 108

Figure 7 . 1 -

 71 Figure 7.1 -An instance of the meeting scheduling

Figure A. 1 -

 1 Figure A.1 -(left) A search failing to consider the objective value. (right) An objective based search.

Figure A. 2 -

 2 Figure A.2 -Comparison of the search tree by a lexicographic search (top) and an objective based search (bottom)

Figure A. 3 -Figure A. 4 -

 34 Figure A.3 -Comparison of the number of solved instances for different OBS configuration.

Figure A. 5 -

 5 Figure A.5 -Running time comparisons of the hybrid strategies, with respect to the hybridization parameters. From left to right and the top to the bottom, the configurations of ABS with (0.25), (0.5), (0.75) and (0).

Figure A. 6 -Figure A. 7 -

 67 Figure A.6 -Comparison of the original search against their hybridized version

Figure A. 5

 5 shows the comparison of different values of α on ABS. When OBS and ABS are not hybridized (α = 1 and α = 0), they clearly show orthogonal behaviors : the timeout are observed on different instances. By looking at the Figure A.5, it can be seen that ABS O (0.5) dominates the others : less timeout and better run-times are observed. Only a full comparison of ABS is presented here. We intentionally omit the remaining combinations to preserve clarity, but similar results are observed with the others hybridized strategies. The best combinations are reached when α = 0.5. Thus in the following, when we are going to talk about a hybridized version, it will be always with α = 0.5.The run-time and timeout comparisons between the others searches and their hybridized version are shown in Figure A.6. It is import to remark that W Deg O seems to outperform its original version, unlike IBS O which has an orthogonal behavior. The figure A.7

Figure A. 8 -

 8 Figure A.8 -Number of instances where each search strategy has found a strictly better objective compared to all the other.

Figure A. 9 -

 9 Figure A.9 -Comparison of the number of instances solved by the different strategies as a function of time.

  public class WolfLambCabbage extends AbstractGameModel { private final Short WOLF = 1, LAMB = 2, CABBAGE = 3; public void buildModel(Model s) { BoolVar[] isComing = s.boolVarArray("coming", players.length -1); IntVar[] utilities = s.intVarArray(players.length -2, 0, 2); for (int i = 0; i < isComing.length; i++) { players[i + 1].own(isComing[i]);

  public static void main(String[] args) { CongaSolver cg = new CongaSolver(new WolfLambCabbage()); cg.setConstraintBuilder(ConstraintFactory.LAST_LEVEL); Solver s =cg.prepareAndGetSolver(); s.solve(); } Multiples interfaces can be redefined to customize the solver behavior. A non exhaustive list is given here : -ConstraintBuilder : defines how to build for instance a Nash constraint (see ConstraintFactory for multiples examples)

Table 3 .

 3

	78]	s d+1

1 -Complexity to find a PNE for different games' representations Algorithm 2 Enum 1: procedure Enum(game : G = (P, A, u)) 2: for all s ∈ A P do 15: function Deviation(strategy profile : s, player : i) : boolean 16:

  215] : A road is being built from north to south through undeveloped land. n agents have purchased plots of land along the road. As the road reaches each agent's plot, the agent needs to choose what to build on his land. His utility depends on what he builds, on some private information about the suitability of his land for various purposes, and on what is built north, south, and across the road from his land. The agent can observe what has already been built immediately to the north of his land (on both sides of the road), but he cannot observe further north ; nor can he observe what will be built across from his land or south of it. Then he has to chose what to build in order to maximize his utility Hard constraints . . . . . . . . . . . . . . . . . . . . . . 57 4.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . 60

	Chapitre 4
	Constraint games

Contents 4.1 Constraint Games framework . . . . . . . . . . . . . . . 45 Constraint games examples . . . . . . . . . . . . . . . . 49 4.2 Variable control . . . . . . . . . . . . . . . . . . . . . . 50 Uncontrolled variables . . . . . . . . . . . . . . . . . . . 50 Shared ownership of variables . . . . . . . . . . . . . . . 54 4.3

  Proposition 2 BB is a propagator for eN i .Then there exists s′ i ∈ A i such that (s ′ i , s -i )| opt i = o ′ i > o i . Hence we have o i < α i ≤ o ′ i and (s ′ i , s -i ) isa deviation for s and s ∈ NE, contradiction. contractness : BB(S) ⊆ S. Since the propagator only remove values, contractness is always true. ′ by definition. Let s| opt i = o i , α i = M m AC (S) and β i = M m AC (S ′ ). Since s ∈ BB(S), we have α i ≤ o i . Since AC is monotonic, we have β i ≤ α i . Thus β i ≤ o i and s ∈ BB(S ′ ).

	5.2. Nash propagator applicability
	Proof 2 Let S and S ′ be two search states. First, because AC is correct, we have
	M m AC (S) ≤ M m(S). Then, if some value is pruned by M m AC , then it has to be pruned also by M m.
	64

-correctness : S ∩ NE ⊆ BB(S). Take s ∈ S ∩ NE and suppose s ∈ BB(S).

Let s| opt i = o i and let α i = M m AC (S). Since s ∈ BB(S), we have o i < α i .

-monotony : S ⊆ S ′ → BB(S) ⊆ BB(S ′ ). Take s ∈ BB(S), we have s ∈ S since BB is contracting and s ∈ S

Table 5 .

 5 1 -Runtime of the different methods on Gamut games

	Conga 1 Conga 2

  6.5 Related work . . . . . . . . . . . . . . . . . . . . . . . . 95 6.6 Instances and experimental results . . . . . . . . . . . . 96 Generator . . . . . . . . . . . . . . . . . . . . . . . . . . 96 Settings and implementation issues . . . . . . . . . . . 97 Experimentation settings . . . . . . . . . . . . . 97 A note on implementations . . . . . . . . . . . . 98 Experimental results . . . . . . . . . . . . . . . . . . . . 99 Constraint programming model . . . . . . . . . 99 ILP model with Column Generation . . . . . . 101 Constraint programming against Column Generation . . . . . . . . . . . . . . . . . . 103 Constraint games . . . . . . . . . . . . . . . . . 104 6.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . 106

  d 1 , . . . , a d i , . . . , a d n d ] be the path computed by the Dijkstra algorithm for a demand d from node a d i . We have a d 1 = src(d) and a d n d = dst(d) and ∀j < i, the value of a d j is given by the instantiated part of the path in [v d 1 , . . . , v d n ] (up to the current node of the search tree). The cost contribution of demand d is given by :

	cost(d) =	{e=(a d j ,a d j+1 ) | j<i}	bw(d) * (cost(e) + cong(e)) +
		{e=(a d j ,a d j+1 ) | i≤j<n d }	bw(d) * cost(e)	(6.7)
	Proposition 3 Given a monotonic cost function (see equation (6.3)), the bound
	given in equation 6.7 is sound.

  The first strategy, called random generation,

	Parameter	Type	Range used in the bench-
			marks
	N nodes	integer 50, 75, 100, 120, 140, 160, 180, 200, 500
	topologyDimension	integer 2
	topologicalCost	boolean true, f alse
	deg min , deg max	integer [1, 2, 4, 8], [2, 5, 7, 10]
	P hub	integer 0, 1, 5, 10, 20
	degh min , degh max	integer [25, 50, 75, 100], [25, 50, 75, 100]
	initbw min , initbw max integer

Table 6 .

 6 1 -Parameters of the generator consists in selecting a random number of hop h in the [hop min , hop max ] interval, and randomly navigating in the graph for h hops, starting from the initial node.

Table 6 .

 6

		120
	Number of Instances Solved	40 60 80 100						MB / SP / SP CO / SP / SP CO1 / SP / SP MB / SP / CP
		20
		0
		0	500	1000	1500	2000	2500	3000	3500
					Time (s)
	Figure 6.13 -Comparison of different CP heuristics on synthetic bench-
	marks

Table 6 .

 6 3 -Comparison of solutions on the unsolved instances

	solution
	first Time			CO1/SP/SP MB/SP/SP CO/SP/SP
	22 43 64 85 106 127	148 169 190 211 232 253 274 295 316 337 358 379 400 421 442
			#Solved instances
	Figure 6.14 -Comparison of the strategies for finding the first solution
	MB/SP/SP CO/SP/SP CO1/SP/SP
	# best sol	340	321	303

Table 6 .

 6 4 -Column Generation results on real-world instances from SNDlib

	40
	0 10 20 30 #instances solved								1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
	0	500	1000	1500	time	2000	2500	3000	3500
	Figure 6.15 -Comparison of different initialization of the Column Genera-
	tion model
	Instance #Demands #Nodes #Edges	CG	MB/SP/SP	Obj CP CG
	SAT
	dfn-bwin		90		10		45	456.742	0.670	1,000067618
	dfn-gwin		110		11		47	T O	0.746	N/A
	di-yuan		22		11		42	T O	0.472	N/A
	giul39		1471		39		172	T O	26.554	N/A
	india35		595		35		80	T O	8.739	N/A
	newyork		240		16		49	T O	3.486	N/A
	nobel-eu		378		28		41	T O	4.919	N/A
	norway		702		27		51	T O	7.962	N/A
	pdh		24		11		34	108.3804	0.553	1
	UNSAT
	geant		462		22		36	T O	2.550	N/A
	germany		662		50		88	T O	6.241	N/A
	janos-us		650		26		84	T O	3.605	N/A
	janos-us-ca		1482		39		122	T O	25.926	N/A

better run-time #better solution #better run-time and s

  .5. It simply shows how many times each method has found a better solution or finished the resolution before the other. From this table, we can see that in general the CP model performs better, but not all the time.

	Column generation	11	17	0
	Constraint Programming	124	382	11

#

Table 6 .

 6

		5 -Comparison between Column Generation and CP
	#Node #demands time CP time CG solution CP solution CG
	120	80	T O	1906.63	707329	704229
	180	90	T O	2245.03	956690	897772
	180	50	T O	2095.51	708083	683188
	100	30	2.29	T O	4564010	T O
	500	10	3.812	547.638	131182	133039
	40	20	1.87	208.979	84291.7	86397.5
	75	200	T O	182.183	914526	T O
	200	40	T O	1651.83	707515	713809

Table 6 .

 6 6 -Comparison between Column Generation and CP

instance #Demands #Nodes #Edges MB/SP/SP [NASH] MB/SP/SP

	SAT
	dfn-bwin	90	10	45	0.670	3.871
	dfn-gwin	110	11	47	0.746	5.681
	di-yuan	22	11	42	0.472	2.012
	giul39	1471	39	172	26.554	1571.197
	india35	595	35	80	8.739	215.716
	newyork	240	16	49	3.486	18.173
	nobel-eu	378	28	41	4.919	41.861
	norway	702	27	51	7.962	154.520
	pdh	24	11	34	0.553	2.016
	UNSAT
	geant	462	22	36	2.550	2.92
	germany	662	50	88	6.241	6.783
	janos-us	650	26	84	3.605	5.174
	janos-us-ca	1482	39	122	25.926	50.486

Table 6 .

 6 7 -Constraint Games results on real-world instances from SNDlibWe present in Table6.7 the run-time in second of the different strategies on the SNDlib instances. It is interesting to see that games of unprecedented size

		120
	Number of Instances Solved	40 60 80 100					MB / SP / SP CO / SP / SP CO1 / SP / SP [NASH] MB+IBR / SP / SP [NASH] MB / SP / SP MB / SP / CP
		20
		0
		0	500	1000	1500	2000	2500	3000	3500
					Time (s)
	Figure 6.16 -Comparison Nash and and the different heuristics on synthetic
	benchmarks

for Mo- deling and Solving Pure Nash Equilibria, Price of Anarchy and Pareto

  The way to see Constraint Games as a global constraint presented in this thesis(see chapter 5) allows modeling transparently games into solvers. In addition, to this new view, we have characterized the complexity of the arc consistency for the Nash constraint, and we have proposed an improvement to the algorithm for finding Nash equilibriums in a game. This new incremental algorithm infers never best responses as soon as possible in the search tree by back-propagating the objective value of each player.-Applications. Constraint games solver : ConGa has been used to solve real networking problem (see chapter 6). Especially, in such applications, a Nash equilibrium solution is really desirable. Its properties make the users satisfied with their situation, hence seen as a high quality of service for multi-user applications. In order to speed the resolution, we have proposed dedicated techniques such as a specialized branch and bound and two heuristics based on the problem's structure. These techniques have helped us to solve games with many players and strategies by improving the solving process's efficiency. -Solver release 1 . A solver for constraint games with its manual has been released. It includes explanations to use it and how to extend it. This is the first release of such solver in the community. Several parts of the work in this thesis have been validated by accepted papers in proceedings of international peer-reviewed conferences : -Palmieri, Anthony, and Arnaud Lallouet. "Constraint games revisited." International Joint Conference on Artificial Intelligence, IJCAI 2017. 2017. -Lallouet, Arnaud, and Anthony Palmieri. "Constraint Games

	Efficient Equilibria." 13th European Meeting on Game Theory,
	SING 2017. 2017 .
	-Palmieri, Anthony, and Guillaume Perez. "Objective as a Feature for
	Robust Search Strategies." International Conference on Principles and
	Practice of Constraint Programming. Springer, Cham, 2018.
	-Palmieri, Anthony, Arnaud Lallouet and Luc Pons. "Constraint Games

for stable and optimal allocation of demands in SDN." International

  Conference on Principles and Practice of Constraint Programming. Springer, Cham, 2018. -Palmieri, Anthony, Arnaud Lallouet and Luc Pons. "

Constraint Games for stable and optimal allocation of demands in SDN." Constraints

Journal 2019, to appear.

  Table A.1. In this Table, even if OBS is Family OBS ABS WDeg IBS ABS O W Deg O IBS O Table A.1 -Number of timeout in some families of instances. not the best strategy, it is often able to solve problems where classical strategies do not. Furthermore, this table shows the interest of the hybridization, which most of the time takes advantage and improve the search considering only one feature. A good example is talent scheduling problem, OBS has 8 timeouts and ABS 7, but the hybridized version have only 4.

	tdtsp	2	5	5	5	5	5	5
	prize-collecting	2	7	7	7	7	2	8
	2DBinPacking	7	8	8	8	6	8	8
	mrcpspmm	0	3	1	1	0	0	0
	mario	0	4	2	0	4	0	3
	tpp	7	7	10	10	5	10	10
	depot placement	3	7	7	1	4	6	4
	p1f	2	1	7	1	2	7	3
	table-layout	0	0	10	4	0	3	5
	filters	2	1	5	1	1	5	1
	amaze	4	3	5	4	3	5	4
	open stack	8	5	10	7	4	9	6
	talent scheduling	8	7	8	7	4	8	7

https ://en.wikipedia.org/wiki/List_of_games_in_game_theory

Example 29 (Example 11 continued)The Nash constraint for Lamb is defined in Figure5.1(a). Note that if Wolf and Cabbage are not coming, Lamb is indifferent and thus has both coming and not coming as best responses.

https ://github.com/palmieri-a/CONGA

Annexe B ConGa : Constraint Game solver

This project is a minimal working version of Constraint Game solver (or Conga). Conga is used to model games and especially to find Pure Nash equilibrium in it. The project can be found at https://github.com/palmieri-a/CONGA. Conga is based on Choco Solver which is a Constraint programming solver.

Using Conga should be easy for the ones who have already used a constraint solver. For the readers who have never used a Constraint solver, it is encouraged to read the Choco solver's documentation and its tutorial.

In the following, an example is provided to illustrate the new internal functions and behaviors in Conga. In this tutorial, the basic notions of constraint programming and game theory are supposed to be known. The tutorial is organized as follow, we first describe the general principles of the solver, then we show how to model a game, afterwards the possible customization and to finally present how to extend the solver.

Requirements Tools :

-JDK8+ -Maven 3+

Libraries :

-Choco Solver -JUnit (tests only) -Gambit (tests only)

Installation

To use Conga a jar including all the dependencies is provided on this repository. Otherwise the sources can be compiled directly with the following instructions.

Compiling from sources

After having downloaded the sources, the project can be compiled by launching the following command at the root of the project :

The above command compiles the sources and creates a jar including the dependencies. This jar can either be imported into another maven project, in your favorite IDE...

Functioning principles

Conga Solver is not a solver itself, but instead, it is an interface to create a model in Choco solver for games. Games or multi-agents systems are generally composed of two sides : the global situation and the agents' situation. That is why Conga is built around two solver instances. One is used to compute the players' deviations, while the second one explores all the possible global situations. A model is created in both solvers. To create and solve a game, two classes are crucial : AbstractGameModel* and CongaSolver.

-CongaSolver is an interface to solve and to manage the solving process of games. It is used to customize games' model, but only the game part. Further information are provided in the solver extensions.

-AbstractGameModel is the interface to implement games. It contains the necessary routines to create games' semantic.

Modeling your first game

This section presents how to model a simple game with Conga. The Wolf Lamb Cabbage (WLC) game is a simple game (see description above) used to illustrate the internal functions and how to find the Pure Nash Equilibriums.

Modeling

To model a game, the class AbstractGameModel has to be overridden. It imposes to implement the buildModel and to call to the super constructor which takes as parameter the number of players. The code above shows the basic routines to model a game. The Choco's API is used to build the variables and the constraints. Then the game semantic is given by the function own(Variable...) which is callable from a player. The players are a protected field in the class AbstractGameModel. For instance the line above specifies that the player i own the variable isComing [i].

players[i + 1].own(isComing[i]);

In the same way, for each player, an objective can be added by using the function setObjective(ResolutionPolicy, Variable). For instance the following code specifies that the WOLF wants to maximize the value of the variable utilities[WOLF -1].

Solving

We show here how to solve a game. The basic idea is to provide to an instance of the class CongaSolver a model to then compute the Nash equilibriums in it.