Konstantin Avrachenkov
email: konstantin.avratchenkov@inria.fr

Vikram Vikas

Singh

Stochastic Coalitional Better-response Dynamics and Strong Nash Equilibrium

Keywords: Strong Nash equilibrium, Coalitional better-response, Stochastic stability, Network formation games, Strongly stable networks Forte équilibre de Nash, Coalitionnelle meilleure réponse, Stabilité stochastique, Jeux de formation de réseau, Réseaux fortement stable

We consider coalition formation among players in an n-player finite strategic game over infinite horizon. At each time a randomly formed coalition makes a joint deviation from a current action profile such that at new action profile all players from the coalition are strictly benefited. Such deviations define a coalitional better-response (CBR) dynamics that is in general stochastic. The CBR dynamics either converges to a strong Nash equilibrium or stucks in a closed cycle. We also assume that at each time a selected coalition makes mistake in deviation with small probability that add mutations (perturbations) into CBR dynamics. We prove that all strong Nash equilibria and closed cycles are stochastically stable, i.e., they are selected by perturbed CBR dynamics as mutations vanish. Similar statement holds for strict strong Nash equilibrium. We apply CBR dynamics to the network formation games and we prove that all strongly stable networks and closed cycles are stochastically stable.

Introduction

Nash equilibrium is the most desirable solution concept in non-cooperative game theory. When a strategic game is played repeatedly over infinite horizon then the Nash equilibrium that is played in the long run depends on an initial action profile as well as the way all the players choose their actions at each time. Several discrete time dynamics have been studied in the literature to study the Nash equilibrium selection in the long run. Young [START_REF] Young | The evolution of conventions[END_REF] considered an n players strategic game where at each time all the players make a simultaneous move and each player chooses an action that is the best response to k previous games among the m, k ≤ m, most recent games in past. In general this dynamics need not converge to a Nash equilibrium, it may stuck into a closed cycle. Young [START_REF] Young | The evolution of conventions[END_REF] also considered the case where at each time with small probability each player makes mistake and chooses some non-optimal action. These mistakes add mutations into the dynamics. In general the mutations can be sufficiently small which leads to the definition of stability of Nash equilibrium as mutations vanish. This type of stability is known as stochastic stability. Young proposed an algorithm to compute the stochastically stable Nash equilibria. For 2 × 2 coordination games he showed that the risk dominant Nash equilibrium is stochastically stable. Kandori et al. [START_REF] Kandori | Learning, mutation, and long run equilibria in games[END_REF] considered a different dynamic model where at each time each player plays with every other player in pairwise contest. The pairwise contest is given by 2 × 2 symmetric matrix game and each player chooses an action which has higher expected average payoff. The mutations are present into dynamics due to wrong actions taken by the players. For 2 × 2 coordination games they showed that a risk dominant Nash equilibrium is stochastically stable. That is, for 2 × 2 coordination games the dynamics given by Young [START_REF] Young | The evolution of conventions[END_REF] and Kandori et al. [START_REF] Kandori | Learning, mutation, and long run equilibria in games[END_REF] selects the same Nash equilibrium. Fudenberg et al. [START_REF] Fudenberg | Evolutionary game dynamics in finite populations with strong selection and weak mutation[END_REF] proposed a dynamics where at each time only one player is selected to choose actions. The mutations with small probability also occur at each time. The risk dominant Nash equilibrium in 2 × 2 coordination games need not be stochastically stable under this dynamics.

The Nash equilibrium concept is inadequate for the situations where players can a priori communicate, being in a position to form a coalition and jointly deviate in a coordinated way. To capture such situations the strong Nash equilibrium (SNE) introduced by Aumann [START_REF] Aumann | Acceptable points in general cooperative n-person games[END_REF] is an adequate solution concept. From an SNE there is no coalition that can deviate to a new action profile such that at new action profile the actions of all players from outside of the coalition are same as at SNE and all the players from the coalition are strictly benefited. There is another equilibrium notion that is stronger than the SNE. Such equilibrium is called as strict strong Nash equilibrium (SSNE). From an SSNE there is no coalition that can deviate to a new action profile such that at new action profile the actions of all players from outside of the coalition are same as at SSNE and all the players from coalition get at least as much as at SSNE and at least one player is strictly benefited. It is clear that an SSNE is always an SNE. As motivated from the application of SNE in network formation games by Dutta and Mutuswami [START_REF] Dutta | Stable networks[END_REF] and SSNE in network formation games by Jackson and van den Nouweland [START_REF] Jackson | Strongly stable networks[END_REF], Jackson [START_REF] Jackson | Social and economic networks[END_REF] we restrict ourselves to only pure actions. A network that is stable against the deviations of all coalitions is called as strongly stable network and under top convexity condition on payoff functions it indeed exists as shown by Jackson and van den Nouweland [START_REF] Jackson | Strongly stable networks[END_REF]. An SNE need not always exist and in such case there exists some set of action profiles forming a closed cycle such that it is possible to reach from one action profile to another via sequence of improving deviations from the coalitions; and it is not possible to reach an action profile outside of the closed cycle from an action profile belonging to closed cycle via improving deviations from the coalitions.

There are many dynamics for equilibrium selection in the literature, as discussed before, describing various situations of the dynamic play. To the best of our knowledge so far no dynamics has been proposed that captures the situation where at each time players are allowed to form a coalition and make a move in a coordinated way. In this paper we propose a CBR dynamics where at each time players are allowed to form a coalition and make a joint deviation from the current action profile if it is strictly beneficial for all the members of the coalition. We assume that the coalition formation is random and at each time only one coalition can be formed. We also consider the situation where at each time the formed coalition makes wrong decision with small probability, i.e., they make a move to an action profile where all the players from the coalition are not strictly benefited. These mistakes work as mutations and add perturbations into CBR dynamics. We prove that the perturbed CBR dynamics selects all strong Nash equilibria and closed cycles in the long run as mutations vanish, i.e., all strong Nash equilibria and closed cycles are stochastically stable. For 2 × 2 symmetric coordination games this dynamics always selects a payoff dominant Nash equilibrium instead of risk dominant Nash equilibrium because a payoff dominant Nash equilibrium is an SNE. The similar CBR dynamics can be given for the case where each time a coalition deviate from a current action profile such that all players from the coalition are at least as well off at new action profile and at least one player is strictly better off. Under such dynamics all strict strong Nash equilibria and closed cycles are stochastically stable.

We apply CBR dynamics corresponding to SSNE to network formation games where nodes (players) of a network form a coalition and make a move to a new network if it offers each player at least as much as it is in the current network and at least one player gets strictly better payoff. The mutations are present due to the wrong decisions taken by the coalitions. We prove that all strongly stable networks and closed cycles are stochastically stable.

The paper is organized as follows. Section 2 contains the model and few definitions. We describe the CBR dynamics in Section 3. Section 4 contains the application of CBR dynamics to network formation games. We conclude our paper in Section 5. As a by-product, we give an algorithm to compute an SNE in Appendix A.

The Model

We consider an n-player strategic game whose components are defined as follows:

1. N = {1, 2, • • • , n} is a finite set of players.
2. A i is a finite set of actions of player i and its element is denoted by a i . We denote A = n i=1 A i as a set of all action profiles and a = (a 1 , a 2 , • • • , a n ) denotes an element of A. Let S be the set of all coalitions among players. For a coalition S ∈ S, define A S = i∈S A i whose element is denoted by a S and a -S denotes an action profile of players outside S.

u

i : A → R is a payoff function of player i. Specifically, player i receives payoff u i (a 1 , a 2 , • • • , a n ) when each player i, i = 1, 2, • • • , n, chooses action a i .
In non-cooperative games, the Nash equilibrium is stable against unilateral deviations, i.e., no player has an incentive to deviate unilaterally from it. But, the Nash equilibrium fails to capture the situation where a priori the players can communicate with each other. In such cases some of the players can form a coalition and jointly deviate from a current action profile if at new action profile each player from the coalition is strictly benefited. In some cases players also make a joint deviation from a current action profile if at new action profile all the players of coalition are at least as well off and at least one player is strictly better off. Such deviations lead to the definitions of strong Nash equilibrium [START_REF] Aumann | Acceptable points in general cooperative n-person games[END_REF] and strict strong Nash equilibrium which we define next. As motivated from the application of SNE in network formation games by Dutta and Mutuswami [START_REF] Dutta | Stable networks[END_REF] and application of SSNE in network formation games by Jackson and van den Nouweland [START_REF] Jackson | Strongly stable networks[END_REF], Jackson [START_REF] Jackson | Social and economic networks[END_REF] we restrict ourselves to pure actions.

Definition 2.1 (Strong Nash Equilibrium

). An action profile a * is said to be a strong Nash equilibrium if there is no S ∈ S and a ∈ A such that

1. a i = a * i , ∀ i / ∈ S. 2. u i (a) > u i (a * ), ∀ i ∈ S.
Let A(S, a) be the set of all action profiles reachable from a via deviation of coalition S. It is defined as,

A(S, a) = {a ′ |a ′ i = a i , ∀ i / ∈ S and a ′ i ∈ A i , ∀ i ∈ S}.
A coalition always has option to do nothing, so a ∈ A(S, a). Let I 1 (S, a) be the set of improved action profiles reachable from an action profile a via deviation of coalition S, i.e.,

I 1 (S, a) = {a ′ |a ′ i = a i , ∀ i / ∈ S and u i (a ′ ) > u i (a), ∀ i ∈ S}. (1)
For an improved action profile a ′ ∈ I 1 (S, a), an action profile a ′ S of all players from S is called as a better-response of coalition S against a fixed action profile a -S of the players outside S. Define, I 1 (S, a) = A(S, a) \ I 1 (S, a) as a set of all action profiles due to the erroneous decisions of coalition S. It is clear that a / ∈ I 1 (S, a), so a ∈ I 1 (S, a). That is, I 1 (S, a) is always nonempty for all S and a. An SNE need not always exist. In such a case there exists some set of action profiles lying on a closed cycle and all such action profiles can be reached from each other via an improving path. The definitions of closed cycle and improving path are as follows: Definition 2.2 (Improving Path). An improving path from a to a ′ is a sequence of action profiles and coalitions

a 1 , S 1 , a 2 , • • • , a m-1 , S m-1 , a m such that a 1 = a, a m = a ′ and a k+1 ∈ I 1 (S k , a k ) for all k = 1, 2, • • • , m -1.

Definition 2.3 (Cycles).

A set of action profiles C form a cycle if for any a ∈ C and a ′ ∈ C there exists an improving path connecting a and a ′ . A cycle is said to be a closed cycle if no action profile in C lies on an improving path leading to an action profile that is not in C.

Theorem 2.4. There always exists a strong Nash equilibrium or a closed cycle of action profiles.

Proof. An action profile is an SNE if and only if it is not possible for any coalition to make an improving deviation from it to another action profile. So, start at an action profile. Either it is SNE or there exists a coalition that can make an improving deviation to another action profile. In the first case result is established. For the second case the same thing holds, i.e., either this new action profile is an SNE or there exists a coalition that can make an improving deviation to another action profile. Given the finite number of action profiles, the above process either finds an action profile which is an SNE or it reaches to the starting action profile, i.e., there exists a cycle. Thus, we have proved that there always exists either an SNE or a cycle. Suppose there are no strong Nash equilibria. Given the finite number of action profile and non-existence of strong Nash equilibria there must exists a maximal set C of action profiles such that for any a ∈ C and a ′ ∈ C there exists an improving path connecting a and a ′ and no action profile in C lies on an improving path leading to an action profile that is not in C. Such a set C is a closed cycle.

An SSNE can be defined similarly. An action profile a * in Definition 2.1 is said to be SSNE if the condition 1 is same and the condition 2 is u i (a) ≥ u i (a * ) for all i ∈ S with at least one strict inequality. That is, a * is an SSNE if it is not possible for any coalition S ∈ S to deviate from a * to some a ∈ A such that the actions of all players outside S are same in both a and a * and at a all players from S are at least as well off as at a * and the payoff of at least one player at a is better than at a * . In this case, for the given action profile a and coalition S the set of improved action profiles I 2 (S, a) is defined as,

I 2 (S, a) = {a ′ |a ′ i = a i , ∀ i ∈ S, and u i (a ′ ) ≥ u i (a), ∀ i ∈ S, u j (a ′ ) > u j (a)
, for some j ∈ S}. (2) and I 2 (S, a) = A(S, a)\ I 2 (S, a). The definitions of improving path and cycles can be defined analogously to previous case. A result similar to Theorem 2.4 holds, i.e., there always exists at least an SSNE or a closed cycle of action profiles. An SSNE is always an SNE, i.e., the set of strict strong Nash equilibria is a subset of the set of strong Nash equilibria. An SNE is a weakly Pareto optimal and an SSNE is a Pareto optimal. Now, we give few examples illustrating the presence of SNE, SSNE and closed cycle.

b 2 a 1 a 2 (-2, -2) (-10, -1) (-1, -10) (-5, -5)
.

The above game represents a famous example of prisoner's dilemma. Here (a 2 , b 2 ) is the only Nash equilibrium that is not an SNE because both player can jointly deviate to (a 1 , b 1 ) where both of them are strictly better off. So, in this game there is no SNE and SSNE. The closed cycle of action profile is given in Figure 1 A directed edge (a 2 , b 2 ) 1 represents a deviation by coalition {1, 2}. The other directed edges of the closed cycle are similarly defined.

{1,2} ---→ (a 1 , b 1 ) of Figure
(a 1 , b 1 ) (a 2 , b 1 ) (a 2 , b 2 ) (a 1 , b 2 ) {2} {1} {2} {1,2} {1} Figure 1: Closed Cycle Example 2.6. Consider a two player game b 1 b 2 b 3 a 1 a 2 a 3    (4, 4) (0, 0) (0, 0) (0, 0) (4, 5) (1, 6) (0, 0) (2, 5) (6, 1)    .
This example has both SNE and closed cycle. The action profile (a 1 , b 1 ) is an SNE and the closed cycle is defined as below:

(a 2 , b 2 ) (a 2 , b 3 ) (a 3 , b 3 ) (a 3 , b 2 ) {2} {1} {2} {1} Figure 2: Closed Cycle But, (a 1 , b 1 )
is not an SSNE because according to the improved action profile set defined by (2), both player can make a joint deviation from action profile (a 1 , b 1 ) to (a 2 , b 2 ). But, if we change the payoff vector corresponding to (a 2 , b 2 ) from (4, 5) to (4 -α, 5) for α > 0 then (a 1 , b 1 ) is also an SSNE.

Dynamic play

We consider the situation where n players play the strategic game defined in Section 2. We assume that the players can a priori communicate with each other and hence they can form a coalition and jointly Inria deviate from the current action profile to a new action profile if new action profile is strictly beneficial for all members of coalition. We consider the coalition formation over infinite horizon. That is, at each time a coalition is randomly formed and it makes a deviation from current action profile to a new action profile such that at new action profile the actions of the players outside the coalition remain same as before and each player of the coalition is strictly benefited. If there is no such improved action profile for a coalition then it does not deviate. The same thing repeats at next stage and it continues for infinite horizon. Such deviations define a coalitional better-response (CBR) dynamics. We assume that the coalition formation is random and at each time only one coalition can be formed. If there are more than one improved action profiles for a coalition then each improved action profile can be chosen with positive probability. That is, the CBR dynamics is stochastic. The CBR dynamics defines a Markov chain over a finite set of action profiles A. We also assume that at each time selected coalition makes mistake and make a joint deviation to an action profile where all members of the coalition are not strictly benefited. This happens with very small probability. Such mistakes add mutations into CBR dynamics. The mutations add another level of stochasticity in the CBR dynamics and as a result we have perturbed Markov chain, see e.g., [START_REF] Avrachenkov | Singular perturbations of Markov chains and decision processes[END_REF][START_REF] Avrachenkov | Analytic perturbation theory and its applications[END_REF]. We are interested in the action profile which is going to be selected by the CBR dynamics as mutations vanish. We next describe the stochastic CBR dynamics as discussed above.

A stochastic CBR dynamics without mistakes

At each time t = 0, 1, 2, • • • a coalition S t is selected randomly with probability p St > 0. We assume that at each time selected coalition makes an improving deviation from current action profile a t , i.e., at time t + 1, the new action profile is a t+1 ∈ I 1 (S t , a t ) with probability p I1 (a t+1 |S t , a t ) where p I1 (•|S t , a t ) is a probability measure over finite set I 1 (S t , a t ). When there are no improving deviations for coalition S t then a t+1 = a t . Let X 0 t denotes the action profile at time t, then {X 0 t } ∞ t=0 is a finite Markov chain on set A. The transition law P 0 of the Markov chain is defined as follows:

P 0 (X 0 t+1 = a ′ |X 0 t = a
p S 1 {a ′ =a} (a ′ ), (3)
where 1 B is an indicator function for a given set B. It is clear that the strong Nash equilibria and closed cycles are the recurrent classes of P 0 . An SNE corresponds to an absorbing state of P 0 and a closed cycle corresponds to a recurrent class of P 0 having more than one action profiles. From Example 2.6 it is clear that in general the closed cycles together with strong Nash equilibria can be present in a game. In that case the CBR dynamics need not converge. In Example 2.6 the CBR dynamics need not converge to SNE (a 1 , b 1 ) because once CBR dynamics enter into closed cycle given in Figure 2 We call a game acyclic if it has no closed cycles. The acyclic games include coordination games. There exists at least one SNE for acyclic games from Theorem 2.4. For acyclic games the Markov chain defined by (3) is absorbing. Hence from the theory of Markov chain the CBR dynamics given in Section 3.1 will be at SNE in the long run no matter from where it starts [START_REF] Kemeny | Finite Markov Chains[END_REF].

A stochastic CBR dynamics with mistakes

Now, we assume that at each time t the selected coalition S t makes error in making a deviation from a t and as a result it moves to an action profile where some player(s) in the coalition S t are not strictly better off. We assume that at action profile a t , coalition S t makes error with f (S t , a t )ε probability, where f : S × A → (0, ∞) and 0 < ε < 1

M with M = max S∈S,a∈A f (S, a). The factor f (S t , a t ) shows the dependence of coalition S t and current action profile a t . The factor ε determines the probability with which players in general make mistakes. These mistakes add mutations to CBR dynamics and as a result we have perturbed Markov chain {X ε t } ∞ t=0 . So, at time t+1 with probability (1-f (S t , a t )ε)p I1 (a t+1 |S t , a t ) the perturbed Markov chain switches to a t+1 ∈ I 1 (S t , a t ) and with probability f (S t , a t )εp I 1 (a t+1 |S t , a t ) it switches to a t+1 ∈ I 1 (S t , a t ) ; p I 1 (•|S t , a t ) is a probability measure over finite set I 1 (S t , a t ). In the situation where there are no improved action profiles for coalition S t , then a t+1 = a t with probability 1 -f (S t , a t )ε and a t+1 ∈ I 1 (S t , a t )\ {a t } with probability f (S t , a t )εp I1\{a t } (a t+1 |S t , a t ); p I1\{a t } (•|S t , a t ) is a probability measure over finite set I 1 (S t , a t ) \ {a t }. The transition law P ε of perturbed Markov chain is defined as below:

P ε (X ε t+1 = a ′ |X ε t+1 = a) = S∈S;I1(S,a) =φ p S (1 -f (S, a)ε)p I1 (a ′ |S, a)1 I1(S,a) (a ′ ) + f (S, a)εp I1 (a ′ |S, a)1 I1(S,a) (a ′ ) + S∈S;I1(S,a)=φ p S (1 -f (S, a)ε)1 {a ′ =a} (a ′ ) + f (S, a)εp I1\{a} (a ′ |S, a)1 I1(S,a)\{a} (a ′ ) , (4)
for all a, a ′ ∈ A. Given all possible coalitional moves and nonzero mutations, it is possible to reach one action profile from another with positive probability in one step. This implies that the perturbed Markov chain {X ε t } ∞ t=0 is aperiodic and irreducible. Hence, there exists a unique stationary distribution µ ε for perturbed Markov chain. However, when ε = 0, there can be several stationary distributions corresponding to different SNEs or closed cycles. Such Markov chains are called singularly perturbed Markov chains [START_REF] Avrachenkov | Singular perturbations of Markov chains and decision processes[END_REF][START_REF] Avrachenkov | Analytic perturbation theory and its applications[END_REF]. We are interested in the action profiles to which stationary distribution µ ε assigns positive probability as ε → 0. This leads to the definition of a stochastically stable action profile.

Definition 3.1. An action profile a is stochastically stable relative to process P ε if lim ε→0 µ ε a > 0. We recall few definitions from [START_REF] Young | The evolution of conventions[END_REF]. From (4), we have P ε (a ′ |a) > 0 for all a, a ′ ∈ A. The one step resistance from an action profile a to an action profile a ′ = a is defined as the minimum number of mistakes (mutations) that are required for the transition from a to a ′ = a and it is denoted by r(a, a ′ ). From (4) it is clear that the transition from a to a ′ has the probability of order ε if a ′ / ∈ I 1 (S, a) for all S and thus has resistance 1 and is of order 1 otherwise, so has resistance 0. So, in our setting r(a, a ′ ) ∈ {0, 1} for all a, a ′ ∈ A. A zero resistance between two action profiles corresponds to a transition with positive probability under P 0 . One can view the action profiles as the nodes of a directed graph that has no self loops and the weight of a directed edge between two different nodes is represented by one step resistance between them. Since P ε is an irreducible Markov chain then there must exist at least one directed path between any two recurrent classes H i and H j of P 0 which starts from H i and ends at H j . The resistance of any path is defined as the sum of the weights of the corresponding edges. The resistance of a path which is minimum among all paths from H i to H j is called as resistance from H i to H j and it is denoted by r ij . The resistance from any action profile a i ∈ H i to any action profile a j ∈ H j is r ij because inside H i and H j action profiles are connected with a path of zero resistance. Here r ij = 1 because given all possible coalitional deviations it is always possible to reach from an action profile that belongs to H i to an action profile belonging to H j in exactly 1 mutation. Now we recall the definition of stochastic potential of a recurrent class H i of P 0 from [START_REF] Young | The evolution of conventions[END_REF]. It can be computed by restricting to a reduced graph. Construct a graph G where total number of nodes are the number of recurrent classes of P 0 (one action profile from each recurrent class) and a directed edge from a i to a j is weighted by r ij . That is, the resistance of a directed edge from a i to a j is 1. Take a node a i ∈ G and consider all the spanning trees such that from every node a j ∈ G, a j = a i , there is a unique path directed from a j to a i . Such spanning trees are called as a i -trees. The resistance of an a i -tree is the sum of the resistances of its edges. The stochastic potential of a i is the resistance of an a i -tree having minimum resistance among all a i -trees. The stochastic potential of each node in H i is same [START_REF] Young | The evolution of conventions[END_REF], which is a stochastic potential of H i . Suppose there are J number of recurrent classes of P 0 , then, an a i -tree will have J -1 number of edges and the resistance of each edge is 1. So, the resistance of each a i -tree is J -1. This implies that the stochastic potential of recurrent class H i is J -1 and this is true for all the recurrent classes. So, in our case the stochastic potential of all the recurrent classes of P 0 is same. Theorem 3.2. All strong Nash equilibria and closed cycles of an n-player finite strategic game are stochastically stable.

Proof. We know that the Markov chain P ε is aperiodic and irreducible. From ( 3) and ( 4) it is easy to see that lim

ε→0 P ε (a ′ |a) = P 0 (a ′ |a), ∀ a, a ′ ∈ A.
From ( 4) it is clear that, if P ε (a ′ |a) > 0 for some ε ∈ (0, ε 0 ], then we have

0 < ε -r(a,a ′ ) P ε (a ′ |a) < ∞.
Markov chain P ε satisfies all three required conditions of Theorem 4 in [START_REF] Young | The evolution of conventions[END_REF] from which it follows that as ε → 0, µ ε converges to some stationary distribution µ 0 of P 0 and an action profile a is stochastically stable, i.e., µ 0 a > 0 if and only if a is contained in a recurrent class of P 0 having minimum stochastic potential. We know that the recurrent classes of Markov chain P 0 are strong Nash equilibria or closed cycles and the stochastic potential of all the recurrent classes are same. Thus, all the strong Nash equilibria and closed cycles are stochastically stable.

Remark 3.3. Since the perturbed process P ε satisfies the conditions of Theorem 4 in [START_REF] Young | The evolution of conventions[END_REF] for all functions f (•), the stochastic stability of strong Nash equilibria and closed cycles is independent of f (•).

We can have a similar CBR dynamics without mistakes and with mistakes as given in Sections 3.1 and 3.2 respectively, if for all S ∈ S and a ∈ A the set of improved action profiles is I 2 (S, a) as defined by [START_REF] Avrachenkov | Singular perturbations of Markov chains and decision processes[END_REF]. We have the following result. Theorem 3.4. All strict strong Nash equilibria and closed cycles of an n-player finite strategic game are stochastically stable under corresponding CBR dynamics.

Proof. The proof follows from the similar arguments given in Theorem 3.2.

Equilibrium selection in coordination games

First we consider a 2 × 2 coordination game and discuss which Nash equilibrium is selected by CBR dynamics in the long run when probability of making mistakes vanish. We compare our equilibrium selection results in 2×2 coordination games with existing results from [START_REF] Kandori | Learning, mutation, and long run equilibria in games[END_REF], [START_REF] Young | The evolution of conventions[END_REF]. Later we discuss equilibrium selection results in general m × m symmetric coordination games.

Consider a 2 × 2 coordination game,

s 1 s 2 s 1 s 2   (a 11 , b 11 ) (a 12 , b 12 ) (a 21 , b 21 ) (a 22 , b 22 )   , where a jk , b jk ∈ R, j, k ∈ {1, 2} and a 11 > a 21 , b 11 > b 12 , a 22 > a 12 , b 22 > b 21 . A i = {s 1 , s 2 }, i = 1, 2.
Here (s 1 , s 1 ) and (s 2 , s 2 ) are two strict Nash equilibria. In this game there are two types of Nash equilibria one is payoff dominant and other one is risk dominant. If

a 11 > a 22 , b 11 > b 22 , then (s 1 , s 1 ) is payoff dominant and if a 11 < a 22 , b 11 < b 22 , then (s 2 , s 2 ) is payoff dominant.
In other cases payoff dominant Nash equilibrium does not exist. From [START_REF] Young | The evolution of conventions[END_REF], define,

R 1 = min a 11 -a 21 a 11 -a 12 -a 21 + a 22 , b 11 -b 12 b 11 -b 12 -b 21 + b 22 , R 2 = min a 22 -a 12 a 11 -a 12 -a 21 + a 22 , b 22 -b 21 b 11 -b 12 -b 21 + b 22 . If R 1 > R 2 , then (s 1 , s 1 ) is risk dominant Nash equilibrium and if R 2 > R 1 , then (s 2 , s 2
) is risk dominant Nash equilibrium. A payoff dominant Nash equilibrium is always an SNE. Hence, CBR dynamics always selects payoff dominant Nash equilibrium whenever it exists. When payoff dominant Nash equilibrium does not exist then both the Nash equilibria are strong Nash equilibria and in that case CBR dynamics selects both the Nash equilibria. While the stochastic dynamics by Young [START_REF] Young | The evolution of conventions[END_REF] always selects a risk dominant Nash equilibrium.

A 2 × 2 symmetric coordination game is considered by Kandori et al. [START_REF] Kandori | Learning, mutation, and long run equilibria in games[END_REF]. For this game a jk = b kj , j, k ∈ {1, 2}. In this case there always exists a payoff dominant Nash equilibrium. Hence CBR dynamics always selects payoff dominant Nash equilibrium which is the only SNE. While the stochastic dynamics by Kandori et al. [START_REF] Kandori | Learning, mutation, and long run equilibria in games[END_REF] always selects a risk dominant Nash equilibrium. Among symmetric coordination games if we go beyond 2 × 2 matrix games the result by Young [START_REF] Young | The evolution of conventions[END_REF] cannot be generalized, i.e., it need not select a risk dominant Nash equilibrium. Consider an example of 3 × 3 matrix game from [START_REF] Young | The evolution of conventions[END_REF],

s 1 s 2 s 3 s 1 s 2 s 3     
(6, 6) (0, 5) (0, 0)

(5, 0) (7, 7) (5, 5) (0, 0) (5, 5) (8, 8)

     .
Here (s 1 , s 1 ), (s 2 , s 2 ) and (s 3 , s 3 ) are three Nash equilibria. The stochastic dynamics by Young [START_REF] Young | The evolution of conventions[END_REF] selects (s 2 , s 2 ) that is not a risk dominant Nash equilibrium. A Nash equilibrium of an m × m symmetric coordination game is risk dominant if it is risk dominant in all pairwise contest [START_REF] Harsanyi | A general theory of equilibrium selection in games[END_REF]. For above 3 × 3 game, the Nash equilibrium (s 3 , s 3 ) is a risk dominant as well as a payoff dominant and also an SNE. Hence, CBR dynamics selects (s 3 , s 3 ). In fact for all m× m symmetric coordination game, CBR dynamics always selects a payoff dominant Nash equilibrium because it is an SNE.

Application to network formation games

In this section we consider the network formation games, see e.g., some recent books [START_REF] Jackson | Social and economic networks[END_REF], [START_REF] Dutta | Networks and Groups: Models of Strategic Formation[END_REF], [START_REF] Demange | Group Formation in Economics: Networks, Clubs, and Coalitions[END_REF]. In general, the networks which are stable against the deviation of all the coalitions are called as strongly stable networks. In the literature, there are two definitions of strongly stable networks. The first definition is due to Dutta and Mutuswami [START_REF] Dutta | Stable networks[END_REF] that is corresponding to SNE. The second definition is due to Jackson and van den Nouweland [START_REF] Jackson | Strongly stable networks[END_REF] that is corresponding SSNE. A strongly stable network according to the definition of [START_REF] Jackson | Strongly stable networks[END_REF] is also strongly stable network according to the definition of [START_REF] Dutta | Stable networks[END_REF]. The definition of a strongly stable network according to Jackson and van den Nouweland [START_REF] Jackson | Strongly stable networks[END_REF] are more often considered in the literature. We also consider the strong stability of networks according to Jackson and van den Nouweland [START_REF] Jackson | Strongly stable networks[END_REF]. We discuss the dynamic formation of networks over infinite horizon. We apply the CBR dynamics corresponding to SSNE to network formation games to discuss the stochastic stability of networks.

The model

Let N = {1, 2, • • • , n} be a finite set of players also called as nodes. The players are connected through undirected edges. An edge can be defined as a subset of N of size 2, e.g., {ij} ⊂ N defines an edge between player i and player j. The collection of edges define a network. Let G denotes a set of all networks on N . For each i ∈ N , let u i : G → R be a payoff function of player i, where u i (g) is a payoff of player i at network g.

To reach from one network to another requires the addition of new links or the destruction of existing links. It is always assumed in the literature that forming a new link requires the consent of both the players while a player can delete a link unilaterally. The coalition formation in network formation games has also been considered in the literature. Some players in a network can form a coalition and make a joint move to another network by adding or severing some links, if new network is at least as beneficial as the previous network for all the players of coalition and at least one player is strictly benefited (see [START_REF] Jackson | Strongly stable networks[END_REF], [START_REF] Jackson | Group formation in economic: Networks, clubs, and coalitions, chapter A survey of models of network formation: Stability and efficiency[END_REF]). We recall few definitions from [START_REF] Jackson | Strongly stable networks[END_REF] describing the coalitional moves in network formation games and the stability of networks against all possible coalitional deviations. Definition 4.1. A network g ′ is obtainable from g via deviation by a coalition S ∈ S as denoted by g → S g ′ , if

1. ij ∈ g ′ and ij / ∈ g then {i, j} ⊂ S. Inria 2. ij ∈ g and ij / ∈ g ′ then {i, j} ∩ S = φ.
The first condition of the above definition requires that a new link can be added only between the nodes which are the part of a coalition S and the second condition requires that at least one node of any deleted link has to be a part of a coalition S. We denote G(S, g) as a set of all networks which are obtainable from g via deviation by S, i.e., G(s, g) = {g ′ |g → S g ′ }.

Definition 4.2. A deviation by a coalition S from a network g to a network g ′ is said to be improving if

1. g → S g ′ , 2. u i (g ′ ) ≥ u i (g), ∀ i ∈ S (

with at least one strict inequality).

We denote I 2 (S, g) as a set of all networks g ′ which are obtainable from g by an improving deviation of S, i.e.,

I 2 (S, g) = g ′ |g → S g ′ , u i (g ′ ) ≥ u i (g), ∀ i ∈ S, u j (g ′ ) > u j (g) for some j ∈ S .
It is clear that g / ∈ I 2 (S, g) for all S. We denote I 2 (S, g) = G(S, g) \ I 2 (S, g) as a set of all networks which are obtainable from g due to erroneous decisions of S. This set is always nonempty as g ∈ I 2 (S, g) for all S. Definition 4.3. A network g is said to be strongly stable if it is not possible for any coalition S to make an improving deviation from network g to some other network g ′ .

A strongly stable network need not always exist and in that case there exists some set of networks lying on a closed cycle and all the networks in a closed cycle can be reached from each other via an improving path. An improving path and a closed cycle in network formation games can be defined similarly to Definitions 2.2 and 2.3, respectively. Theorem 4.4. There exists at least a strongly stable network or a closed cycle of networks.

Proof. The proof follows from the similar arguments used in Theorem 2.4.

Dynamic network formation

The paper by Jackson and Watts [START_REF] Jackson | The evolution of social and economic networks[END_REF] is the first one to consider the dynamic formation of networks. They considered the case where at each time only a pair of players form a coalition and only a link between them can be altered. We consider the situation where at each time a subset of players form a coalition and deviate from a current network to a new network if at new network the payoff of each player of the coalition is at least as much as at current network and at least one player has strictly better payoff. This process continues over infinite horizon. A coalition can make all possible changes in the network and as a result more than one link can be created or severed at each time. So, we consider the following network formation rules by Jackson and van den Nouweland [START_REF] Jackson | Strongly stable networks[END_REF] given below:

• Link addition is bilateral, i.e., forming a link between player i and player j requires the consent of both players.

• Link destruction is unilateral, i.e., severing a link between player i and player j requires that player i or player j or both agree to sever the link.

• At a time more than one link can be created or severed by the players.

The CBR dynamics corresponding to SSNE can be applied to dynamic network formation. That is, at time t a network is g t and a coalition S t is selected with probability p St > 0 and it makes an improving deviation to a new network that is at least as beneficial as g t for all players of coalition S t and at least one player of S t is strictly benefited. So, at time t + 1 network is g t+1 ∈ I 2 (S t , g t ) with probability p I2 (g t+1 |S t , g t ). If an improving deviation is not possible for selected coalition S t , then g t+1 = g t . The above process defines a Markov chain over state space G and its transition probabilities can be defined similarly to [START_REF] Avrachenkov | Analytic perturbation theory and its applications[END_REF]. In general this Markov chain is multichain whose absorbing set is either a strongly stable network or a recurrent class having more than one network is a closed cycle of networks. We can also assume that at each time selected coalition S t makes error with small probability f (S t , g t )ε. That is, g t+1 ∈ I 2 (S t , g t ) with probability (1 -f (S t , g t )ε)p I2 (g t+1 |S t , g t ) and g t+1 ∈ I 2 (S t , g t ) with probability f (S t , g t )εp I2 (g t+1 |S t , g t ). The transition probabilities of the perturbed Markov chain can be defined similarly to [START_REF] Demange | Group Formation in Economics: Networks, Clubs, and Coalitions[END_REF]. The presence of mutations makes the Markov chain ergodic for which there exists a unique stationary distribution. We are interested in the stochastically stable networks, i.e., the networks to which positive probabilities are assigned by the stationary distribution as ε → 0. The stochastic stability analysis similar to the one given in Section 3.2 holds here. Thus, we have the following result.

Theorem 4.5. All the strongly stable networks and closed cycles of a network formation game with the corresponding CBR dynamics are stochastically stable.

Proof. The proof follows directly from Theorem 3.4.

Conclusions

We introduce coalition formation among players in an n-player strategic game over infinite horizon and propose a CBR dynamics. The mutations are present in the dynamics due to erroneous decisions taken by the coalitions. We prove that all strong Nash equilibria and closed cycles of action profiles are stochastically stable, i.e., they are selected by the CBR dynamics as mutations vanish. Similar development holds for strict strong Nash equilibria. We applied CBR dynamics to network formation games and prove that all strongly stable networks and closed cycles of networks are stochastically stable.

Example 2 . 5 .

 25 Consider a two player game b 1

  ) = S∈S;I1(S,a) =φ p S p I1 (a ′ |S, a)1 I1(S,a) (a ′ ) + S∈S;I1(S,a)=φ

  then it will never come out of it. The closed cycle C = {(a 2 , b 2 ), (a 2 , b 3 ), (a 3 , b 3 ), (a 3 , b 2 )} is a recurrent class and (a 1 , b 1 ) is an absorbing state of Markov chain P 0 corresponding to the game given in Example 2.6.

RR n°8716

route des Lucioles -BP 93 06902 Sophia Antipolis Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

Acknowledgements

This research was sponsored by the European Commission within the framework of the CONGAS project FP7-ICT-2011-8-317672.

A Algorithm for computing strong Nash equilibrium

We give a finite step algorithm that computes an SNE whenever it exists. If an SNE does not exist then in finite number of steps the algorithm confirms that there is no SNE. From the definition of SNE an action profile a is an SNE if there is no improved action profile a ′ = a for any coalition S ∈ S, i.e., I 1 (S, a) = φ for all S ∈ S.

Algorithm 1

1: Choose a ∈ A.

2: Choose S ∈ S.

Go to Step 20

if |A S | = 0 then 13: S = S \ S.


Matthieu Courgeon
email: courgeon@enib.fr

Céline Clavel
email: clavel@limsi.fr

Jean-Claude Martin
email: martin@limsi.fr

Modeling Facial Signs of Appraisal During Interaction; Impact on Users' Perception and Behavior

Keywords: [I.3.7] Animation, [H.5.2] Evaluation/methodology, GUI virtual characters, facial animation, model, affective computing

Interactive virtual characters are expected to lead to an intuitive interaction via multiple communicative modalities such as the expression of emotions. Generating facial expressions that are consistent with the interaction context is a challenge. This paper presents our interactive facial animation system based on the Component Process Model, generating facial signs of appraisal during a real-time interactive game. We describe a study comparing our model to the categorical approach of facial animation of emotion. Participants interacted with a virtual character in three conditions: no expression of emotion, an expression of a categorical emotion, and expressions of sequential signs of appraisal. The character in the appraisal condition was reported as being more expressive than in the other two conditions and was reported as experiencing more mental states. In addition, using appraisal signs modified the way participants interacted with the character (participants played slower after some emotions were expressed by the agent, i.e. pride and sadness).

INTRODUCTION

Given the important role of emotion signaling in social relationships, humans must be able to accurately encode and decode emotional states that change extremely rapidly [START_REF] Scherer | The Component Process Model: architecture for a comprehensive computational model of emergent emotion A Blueprint for Affective Comp[END_REF]. Similarly to humans, virtual characters (hereafter VC) often express emotions using facial expressions. VCs are commonly used in interactive applications such as games or e-learning environments. Several studies have revealed the importance of VC having a proper emotion model, dynamics and facial expressions to be well perceived and accepted by the participants [START_REF] Pelachaud | Modelling Multimodal Expression of Emotion in a Virtual Agent[END_REF]. The underlying models of emotion constitute a challenge in affective computing research [START_REF] Ibister | Evaluating affective interactions Introduction to special issue of International journal of human-computer studies[END_REF] and endowing VC with subtle expressivity requires theoretical and empirical studies [START_REF] Suzuki | Subtle expressivity for characters and robots International Journal of Human-Computer Studies, Special issue on subtle expressivity for characters and robots[END_REF].

VC are used as tools for conducting experiments on how humans perceive communicative signals [START_REF] Bailenson | Immersive Virtual Environment Technology as a Methodological Tool for Social Psychology[END_REF][START_REF] Der Pütten | It doesn't matter what you are! Explaining social effects of agents and avatars Computers in[END_REF][START_REF] Vogeley | Artificial humans Psychology and neuroscience perspectives on embodiment and nonverbal communication Original[END_REF][START_REF] Likowski | Modulation of facial mimicry by attitudes[END_REF]. Most of these systems rely on prototypical expressions of a small set of basic emotions, such as anger, sadness, joy, fear, surprise and disgust [START_REF] Ekman | Unmasking the Face: A Guide to Recognizing Emotions from Facial Clues[END_REF][START_REF] Russell | Is There Universal Recognition of Emotion from Facial Expression? A Review of the Cross-Cultural Studies Psych[END_REF] although VC are however capable of expressing subtle differences in facial expressions [START_REF] De Melo | Expression of emotions using wrinkles; blushing; sweating and tears[END_REF].

Despite the general acceptance of the notion that emotion is a dynamic process, few emotion theories specify mechanisms that allow analyzing or modeling dynamic changes over time.

Furthermore, basic emotion theories have the disadvantage that they describe only a few emotions in detail and provide little description on how to consider more complex emotion and blends of multiple emotions. Blends of several emotions are observed in natural settings [START_REF] Scherer | Lost luggage: a field study of emotionantecedent appraisal[END_REF][START_REF] Martin | Multimodal complex emotions: gesture expressivity and blended facial expressions[END_REF] and have been modeled in some VC [START_REF] Niewiadomski | Affect expression in ECAs: Application to politeness displays[END_REF].

According to cognitive theories, emotions result from a process of evaluation (also called appraisal) of the situation and its relation to the individual experiencing the emotion [START_REF] Scherer | The Component Process Model: architecture for a comprehensive computational model of emergent emotion A Blueprint for Affective Comp[END_REF]. Several appraisal models have been proposed in psychology [START_REF] Gross | Emotion generation and emotion regulation: one or two depends on your point of view[END_REF] and computational models have thus been defined and implemented [START_REF] Marsella | EMA: A process model of appraisal dynamics[END_REF]. Yet, few appraisal-based systems are used for real-time interaction, and little is known about how such systems should impact real-time interactive facial animation. Canned animations based on appraisal modeling have been presented to subjects who had to rate them outside any interaction context [START_REF] Paleari | Psychologically grounded avatars expressions[END_REF]. Such perception tests limit the exploration of cognitive theories of emotions and the associated dynamic models of emotions because these theories strongly rely on the appraisal of the current context.

In this paper, we present an interactive system inspired from the CPM model for the animation of a VC's facial expressions during a competitive game. This system is evaluated using a user study assessing how a VC that sequentially displays facial signs of appraisal was perceived during a real-time interactive game. We compared appraisal based animation to a VC displaying only categorical emotions or no emotion at all. Our general hypothesis is that the condition impacts participants' perception of the expressivity of the VC and of its mental states. We also expect an impact on participants' behavior during the game since facial expressions can be a powerful means of conveying information related to the playing strategy of the character.

The remainder of the paper is organized as follows. Section 2 summarizes related work in psychology of emotions and in interactive VC research. Section 3 presents the MARC (Multimodal Affective Reactive Character) platform that we extended to enable the dynamical display of sequential signs of appraisal by our VC. This platform enables the generation of sequential displays of facial signs of appraisals during an interactive application. Section 4 presents our participant study and details our hypotheses. Section 5 and 6 present and discuss the results. Section 7 concludes and explains our future research directions.

RELATED WORK 2.1 Emotions and Theories

Theories of emotion assume the existence of several emotional components, for example, cognitive processes, peripheral physiological responses, motivational changes, motor expression, and subjective feeling. Psychological theories of emotion differ in their assumptions on how these emotion components are integrated and, in particular, how qualitatively different emotional states are to be differentiated with respect to their patterning [START_REF] Scherer | [END_REF]. Several approaches to emotions have been proposed, such as categorical [START_REF] Ekman | Unmasking the Face: A Guide to Recognizing Emotions from Facial Clues[END_REF], dimensional [START_REF] Russell | Evidence for a three-factor theory of emotions[END_REF] and cognitive [START_REF] Lazarus | Emotions and Adaptation: Conceptual and Empirical relations Nebraska Symposium on Motivation[END_REF]. We consider hereafter two classes of theories that are relevant to our research: the categorical emotions theories and the cognitive theories of emotions. These two approaches are strongly related to the communicative function of emotions, and more specifically to the facial expressions of emotions. Some authors have made a distinction between emotional states (e.g. joyful, being proud, etc.) and other cognitive mental states that are not directly related to emotions (e.g., knowing, thinking, pretending) [START_REF] Hughes | Understanding mind and emotion: longitudinal associations with mental-state talk between young friends[END_REF]. Baron-Cohen has proposed a detailed list of 416 mental states including emotional states and non-emotional cognitive mental states. The MindReading database includes videos of acted facial expressions of these mental states [START_REF] Golan | The cambridge mindreading (CAM) face-voice battery : testing complex emotion recognition in adults with and without asperger syndrome : affective/emotional experiences of people on the autism spectrum[END_REF].

Categorical approach to emotions

According to the categorical approach to emotion, there is a set of basic emotions, such as joy, surprise, fear, anger, sadness, and disgust [START_REF] Ekman | Unmasking the Face: A Guide to Recognizing Emotions from Facial Clues[END_REF]. According to Ekman, several characteristics distinguish these basic emotions from one another as well as from other affective phenomena [START_REF] Ekman | Emotions Revealed. Understanding Faces and Feelings[END_REF]. These basic emotions are supposed to be triggered by specific conditions by response programs that might be universal. Each emotion is characterized by a specific circuit. A basic emotion is not seen as a single affective state, but rather as a family of related states. Different researchers [START_REF] Tomkins | Affect theory Approaches to Emotion[END_REF][START_REF] Izard | Human Emotions[END_REF][START_REF] Plutchik | Circumplex Models of Personality and Emotions The American Psychological Association[END_REF][START_REF] Ekman | Emotions Revealed. Understanding Faces and Feelings[END_REF] have considered different lists of fundamental emotions (for example, including interest and shame). This approach is highly centered on facial expressivity and proposes a list of "universal" expressions. It was extensively used in VC animation [START_REF] Pelachaud | Modelling Multimodal Expression of Emotion in a Virtual Agent[END_REF].

Appraisal theories of emotion

Appraisal theories are part of the cognitive approach to emotion. Emotions result from a process of evaluation of the situation and its relation to the individual [START_REF] Arnold | [END_REF][START_REF] Frijda | The Emotions[END_REF][START_REF] Scherer | The Component Process Model: architecture for a comprehensive computational model of emergent emotion A Blueprint for Affective Comp[END_REF][START_REF] Ortony | The Cognitive Structure of Emotions[END_REF]. Scherer has argued that emotions are generated through cycles of multi-level evaluations of events. Several different evaluations assess the significance and implications of a particular event for the survival or well-being of the organism. These evaluations are called appraisals. Scherer has proposed four main evaluation phases: 1) relevance, 2) implications, 3) coping potential, and 4) normal significance. Each phase is decomposed in several criteria, known as sequential evaluation checks (hereafter called checks). Scherer has defined several sets of checks but often focus on five to seven checks [START_REF] Scherer | On the sequential nature of appraisal processes: Indirect evidence from a recognition task[END_REF].

Checks may have multiple effects on the face, the body posture, the voice and the nervous system [START_REF] Scherer | Appraisal considered as a process of multilevel sequential checking in Appraisal processes in emotion: Theory, Methods, Research[END_REF]. The timing and order of these checks are crucial to a proper implementation of a computational model. For instance, a study has observed that the unpleasantness check is evaluated prior to the goal hindrance check [START_REF] Lanctot | The timing of appraisals Emotion[END_REF]. This study also provided muscles reaction delays for these checks (about 400ms for unpleasantness and 800ms for goal hindrance). Another study has suggested that the three first checks (expectedness, unpleasantness, and goal hindrance) occur in the brain within 250ms [START_REF] Grandjean | Unpacking the cognitive architecture of emotion processes[END_REF]. Higher level checks, such as coping potential and immorality, might induce longer delays, but little data is available in the literature about these delays.

Basic emotion vs. appraisal theories: what about facial expressions?

Basic emotion and the appraisal theories suggest different mechanisms underlying the generation of facial expressions. The basic emotion theory supposes the existence of a "prewritten program" for each discrete emotion. Tomkins suggested that the expressivity mechanism is a neuromotor program, predicting that following emotion elicitation, the prototypical pattern will be produced [START_REF] Tomkins | Affect theory Approaches to Emotion[END_REF]. Instead, the component process model based on appraisal theories considers that an emotion is an emergent process during which several elements of the expression appear and combine in time. These two different mechanisms result in very different facial expressive patterns. In the categorical approach, a prototypical facial expression pattern is then selected among a family of expressions and displayed. According to the component process model, the eliciting event is sequentially appraised according to a series of sequential evaluation checks, each producing a facial action. These facial actions combine in a dynamic fashion, producing a large variety of different patterns.

According to [START_REF] Smith | A componential approach to the meaning of facial expressions The psychology of facial expression[END_REF] each of these individual components contributing to a facial expression is inherently meaningful.

Basic emotion and appraisal theories differ according to the number and the prototypically of the facial expressions. A study compared categorical and appraisal-related facial expressivity [START_REF] Scherer | Multimodal expression of emotion: affect programs or componential appraisal patterns?[END_REF]. Twelve actors were asked to perform scenarios covering 14 emotions. No complete prototypical pattern was observed for basic emotions, contrary to the predictions that one would expect based on the categorical approach. Even the occurrence of partial patterns was relatively rare (1/3 of the portrayals). These observations can be interpreted as evidence against a strong affect program mechanism. Expression patterns show much more variability than one would expect on the basis of discrete emotion theory [START_REF] Scherer | The Component Process Model: architecture for a comprehensive computational model of emergent emotion A Blueprint for Affective Comp[END_REF].

Emotional Intelligence and the attribution of mental states to others

In order to understand how users perceive VC expressing emotions, we need to consider two important notions: emotional competence and emotional intelligence.

Emotional competence [START_REF] Scherer | Emotion and emotional competence: conceptual and theorical issues for modeling agents[END_REF] requires 1) to express appropriate emotions, which require adequate appraisals of internal goals states, coping potential, and the probable consequences of events, and 2) to differentiate emotions and to understand emotion blends, which implies a correct estimation of coping potential and accurate assessments of social expectations, norms, and moral standards.

Emotional intelligence is defined as "the ability to recognize and regulate emotions in ourselves and in others" [START_REF] Goleman | An EI-based theory of performance The Emotionally Intelligent Workplace[END_REF] . This capacity spans from basic cognitive processes to more complex combinations of cognition and emotion processes: 1) perceive, evaluate and express emotions (one's own and others' emotions), 2) use emotion during information processing, 3) differentiate and label different emotions, and understand emotion blends, and 4) organize one's own emotion for supporting social goals. Emotional intelligence would thus enable individuals to engage in interactions while controlling their own emotions and those of other individuals. Several questionnaires have been proposed to measure the specific skills of emotional intelligence [START_REF] Mayer | Measuring emotional intelligence with the MSCEIT V2[END_REF].

Virtual Facial expressions of emotions

Since the early 1970s, research in computer graphics has attempted to simulate the human face which is perceived as a powerful communication tool for human-computer interaction. Facial expression of emotion in virtual characters mostly focused on displaying basic emotions [START_REF] Balcı | XfaceEd: authoring tool for embodied conversational agents International Conference on Multimodal interfaces[END_REF]. Some systems feature the ability to blend several emotions on the whole face or using spatial facial region decomposition. Some systems also use dimensional models of emotions [START_REF] Hyniewska | Expression of affects in embodied conversational agents in A Blueprint for Affective Computing[END_REF] or sequenced expression models [START_REF] Niewiadomski | Modeling emotional expressions as sequences of behaviors in International conference on Intelligent Virtual Agents[END_REF].

A sequential facial animation system using Scherer's descriptions of facial signs of appraisals has also been implemented by [START_REF] Paleari | Psychologically grounded avatars expressions[END_REF]. The system displays temporary expressions of appraisals checks but was not interactive and did not provide animation context. A study [START_REF] Malatesta | Towards modelling embodied conversational agent character profiles using appraisal theory predictions in expression synthesis[END_REF] addressed dynamic issues comparing two modes (sequential vs. additive AU) to animate facial signs of appraisals. Subjects were asked which emotion they recognize in each of the canned animation. The additive mode showed recognition rates above the chance level, whereas the sequential mode gave recognition rates marginally above chance level.

REALTIME SIGNS OF APPRAISAL 3.1 The game application

Two-player turn-based games such as chess are relevant for affective computing research [START_REF] Leite | Towards and Empathic Chess Companion in Autonomous Agents and Multiagent Systems[END_REF]. We selected and implemented a game called Reversi (Figure 1). This competitive game is played by two players on an 8x8 grid board. This game is easy enough to learn, features a small set of possible events and hence sounds appropriate for conducting experimental studies about appraisals.

MARC

MARC is a framework composed of several models and tools for designing interactive expressive characters [START_REF] Courgeon | MARC: a Framework that Features Emotion Models for Facial Animation during Human-Computer Interaction[END_REF]. In order to investigate appraisal theories during interaction, we extended MARC with two modules (Figure 2): 1) the "Appraisal Application Module", which appraises the events that occur during the game, and 2) the "Sequential Checks Animation Module", which generates corresponding facial animation parameters.

The appraisal application module

This experimental setting is relevant for our research by enabling us to focus on a restricted set of emotional situations with different appraisal profiles. Three actions trigger emotional events in the system: 1) the participant plays, 2) the VC plays, and 3) the game is over. We adapted a subpart of the component process model [START_REF] Scherer | Appraisal considered as a process of multilevel sequential checking in Appraisal processes in emotion: Theory, Methods, Research[END_REF] that is relevant to these three emotional events. Our system thus deals with seven appraisal checks: expectedness, unpleasantness, goal hindrance, external causation, coping potential, immorality, and self-consistency. We chose these seven checks because they are relevant for the Reversi game. Moreover, several emotions have already been described according to those checks in psychological studies facilitating their implementation in a computational model [START_REF] Scherer | Appraisal considered as a process of multilevel sequential checking in Appraisal processes in emotion: Theory, Methods, Research[END_REF]. The interaction contexts that we consider are the game event history and a short term anticipation of the participant's next two potential actions. Anticipating the game covers the appraisal checks of expectedness and coping potential: for example, the system expects that the participant will move one of his pieces towards a place where it will reverse some pieces belonging to the system. We did not enable our system to have a larger prediction about the game so as to give to the player a chance to win.

For each event, the appraisal module uses a predefined decision tree to compute a value for each of the seven checks. To design these trees, we predefined groups of check values that match several situations that might occur.

The animation module

The animation module generates temporary facial expressions of checks and creates the resulting dynamic sequence of facial expressions. Temporary facial expressions of check were specified using FACS descriptions of appraisal effects [START_REF] Scherer | Appraisal considered as a process of multilevel sequential checking in Appraisal processes in emotion: Theory, Methods, Research[END_REF]. At the end of the sequential check animation, the animation module displays the final emotional state resulting from the appraisal sequence. We selected the following set of emotions: joy, fear, anger, sadness and pride. This set was selected because the literature has provided descriptions for their potential appraisal profile and the values of the checks [START_REF] Scherer | Appraisal considered as a process of multilevel sequential checking in Appraisal processes in emotion: Theory, Methods, Research[END_REF], and these emotions are often observed during a game.

The final facial expression for joy, fear, anger and sadness were defined using Ekman's description [START_REF] Ekman | Unmasking the Face: A Guide to Recognizing Emotions from Facial Clues[END_REF]. The design of this final facial expression of pride was inspired by the MindReading database [START_REF] Golan | The cambridge mindreading (CAM) face-voice battery : testing complex emotion recognition in adults with and without asperger syndrome : affective/emotional experiences of people on the autism spectrum[END_REF]: we selected the features of the facial expressions, (e.g. brows movements) appearing in at least half of the six videos illustrating pride.

Figure 3 (bottom line) provides an illustration of such a sequence of facial expressions of appraisals.

Prior perceptual validation of the facial animations of appraisal

Before proceeding to the actual experiment about the perception of facial expressions during the game interaction, we validated the perception of individual sequences of expressions of appraisals.

In a previous study, we observed that the facial expressions of basic emotions (including joy, fear, anger, and sadness that we used in this study) displayed by our VC were recognized by participants above the chance [START_REF] Courgeon | Impact of Expressive Wrinkles on Perception of a Virtual Character's Facial Expressions of Emotions[END_REF].

Sequences of facial expressions of appraisals were validated as follow. Animations were designed according to suggestions from the literature [START_REF] Scherer | Appraisal considered as a process of multilevel sequential checking in Appraisal processes in emotion: Theory, Methods, Research[END_REF]. Nine sequences of facial expressions that were possibly used during the Reversi game were tested. In total, 109 individuals participated in this study. There were 23 males and 86 females. The average age was 20.82 years. Each participant saw one animation. Each animation was seen and rated by an average of 12 participants. Participants had to fill the Geneva Appraisal Questionnaire, which aims at studying the relations between emotions and appraisal checks [START_REF] Scherer | Appraisal considered as a process of multilevel sequential checking in Appraisal processes in emotion: Theory, Methods, Research[END_REF]. We adapted this questionnaire to our setup (e.g., participants had to rate the emotions expressed by our VC instead of self-reporting their own emotions). We observed that the appraisal and categorical profile of the nine animations were recognized by participants above the chance level.

Study

We conducted a study to evaluate the impact of the facial expressions of the VC on participants' perception during a Reversi game. We compared 3 expressive conditions (Figure 3): 1) A neutral condition, i.e., the VC did not display any facial expression of emotion; participants in this group will be referred to as the "control group" 2) A categorical condition, i.e., the VC displayed an animation based on interpolation of prototypical facial expressions of categorical emotions; 3) An appraisal condition, i.e., the VC sequentially displayed facial expressions of appraisal checks reflecting an underlying sequential appraisal of the current situation. In the appraisal condition, the values of the checks External Causation, Immorality and Self consistency were not expressed using individual facial expressions. They were used instead in the final computation of the resulting emotion expressed at the end of the sequence. Animations in the categorical condition and the appraisal condition had the same duration.

Hypotheses

Regarding the question of how the condition influenced participants' perception, we had the following hypotheses in mind:

H1: The perceived emotional expressiveness of the VC increases with the number of facial expressions used in the condition

The VC displays expressions of emotion in the appraisal group and in the categorical groups. We expect that participants playing in these two conditions will report perceiving expressions of emotions.

H1A: Participants perceive less emotion in the VC's expressions in the control group than in the categorical and appraisal groups.

Perception of expressions of emotion: control group < (categorical group = appraisal group)

We expect that participants will also perceive the difference of dynamics between the animations used in the three groups. H1B: Participants perceive a higher dynamics of emotional expression when the number of facial expressions is higher.

Perception of the dynamics of emotional expression: control group < categorical group < appraisal group

H2: Participants' attribution of emotional states and other cognitive mental states to the VC depends on the condition

Because the VC displayed expressions of emotion in the appraisal group and in the categorical group, we expect that participants in these two groups will attribute internal emotional states to the VC.

H2A:

Participants attribute less emotional states to the VC in the control group than in the categorical and appraisal groups.

Attribution of internal emotional states: control group < (categorical group = appraisal group)

The appraisal condition features expressions of cognitive evaluations of the situation. Thus, we expect that participants will also attribute more non-emotional cognitive mental states (e.g., thinking) to the VC than in other conditions. H2B: Participants attribute more non-emotional cognitive mental states to the VC in the appraisal groups than in the control group and categorical group.

Attribution of non-emotional cognitive mental states: (control group = categorical condition) < appraisal condition

H3: Participants win more often and spend more time to play when the number of facial expressions is higher

We expect participants to win more often in the appraisal and categorical groups than in the control group because they can rely on more feedback to understand and predict the behavior of the VC.

H3A: Participants win more often when the number of facial expressions is higher.

Participant wins: appraisal condition > categorical condition > control group

Finally, we expect participants to spend more time to prepare and make their moves in the appraisal condition than in the categorical condition because they will have to interpret a higher number and variety of facial expressions.

H3B:

Participants spend more time to play when the number of facial expressions is higher.

Game duration: appraisal group > categorical group > control group

Method

Design and participants

The experiment used a between-participants design with the independent factor "expressive condition" as a single factor (control, categorical and appraisal).

Sixty participants took part in the study, all French native speakers. There were 17 females and 43 males. The average age was 26 years (SD 8.39). Participants had either a high school degree or a university degree. Participants were distributed randomly in three groups of twenty participants each.

Procedure

Participants were informed that they would play Reversi against a VC. They were left alone with the computer in a quiet room. The participants were video recorded to collect additional information about the interaction.

Participants played first. The board game was darkened when the participant made a move so as to direct participants' attention to the VC's facial expressions rather than the board at these emotionally relevant moments. The VC expressed the emotion resulting from the evaluation of the participant's move according to the condition. Then the VC played, and its face expressed the emotion reflecting the evaluation of new situation. The board game was displayed again so that the participant could play the next move.

Measures

Subjective measures

The questionnaire comprised two parts. Part I aims at analyzing participants' perception of the facial expressions displayed by the VC. Part II aims at studying the internal emotional states and nonemotional cognitive mental states that participants attributed to the VC. In each of these two parts, a list of claims was proposed. For each of these claims, participants had to report their level of agreement according to a 5-point Likert scale. The claims were inspired by questionnaires measuring emotional intelligence [START_REF] Mayer | Measuring emotional intelligence with the MSCEIT V2[END_REF].

The reliability of our questionnaire was checked using Cronbach's alpha. We computed Cronbach's alpha (CA) for the dimensions related to the perception of facial expression, the attribution of emotional states and the attribution of non-emotional cognitive mental states. The values were quite satisfactory according to the APA recommendations (between 0.70 and 0.94).

Part I: Participants' perception of the facial expressions displayed by the VC

The goal of this first section is to test our first hypothesis (H1) Perception of emotional expressions. 5 items (CA: 0.85); Perception of an absence of emotional expressions 5 items (CA: 0.94); Perception of emotional dynamics. 4 items (CA: 0.75);

Part II: Attribution of emotional states and non-emotional cognitive mental states by participants to the VC

The second part of the questionnaire concern the attribution of internal mental states by participants to the VC. It refers to our second hypothesis (H2): the attribution of emotional states and other cognitive mental states to the VC depends on the condition. This part of the questionnaire contains two sections:

Attribution of emotional states. 7 items (CA: 0.79); Attribution of non-emotional states. 7 items (CA: 0.70);

Performance measures

Objective measures were also used to test the third hypothesis (H3). The outcome of each game session was collected as a binary variable (Win/Lost). We recorded the timestamps of all moves by the agent and participants. This record allowed us to compute the time participants took to prepare and make all their moves.

Results

The results presented in this section are statistically significant (p<0.05). Results are explicitly referred as a "trend" if p is between 0.05 and 0.1. Collected data for subjective (user point of view) measures were analyzed using the t-test.

We applied the Kolmogorov-Smirnov test to show that the following variables succeed to satisfy normality assumptions: perception of emotional expressions (K-S d=,13955, p<,20), perception of an absence of emotional expression (K-S d=,10497, p> .20), perception of emotional dynamics of expressions (K-S d=,10783, p> .20), attribution of emotional states (K-S d=,08757, p> .20), and attribution of non-emotional cognitive mental states (K-S d=,12263, p> .20).

We performed an ANOVA with expressive conditions as an intersubject factor. Fisher's LSD was used for post-hoc pair-wise comparisons. All the analyses were performed with Statistica 9.

Subjective measures

H1: The perceived emotional expressiveness of the VC increases with the number of facial expressions used in the condition. H1A: Participants perceive less emotion in the VC's expressions in the control group than in the categorical and appraisal groups.

The reported perception of emotional expressions was higher in the appraisal group than in the control group (t(15) = -3.93; p < 0.001).

Participants in the appraisal condition also considered MARC to have expressed more emotions that the participants in the categorical group (t(18)=-2.05; p<0.05).

Participants in the categorical condition perceived more emotional expressions than participants in the control group (t(13) = -2.12; p < 0.05). The agent in the control group was rated as globally less expressive than the agent in the categorical group (t(13) = -3.88; p < 0.002).

These results confirm our hypothesis H1A and moreover distinguish the appraisal group from the categorical group. The agent in the appraisal group was perceived as expressing more emotions that the agent in the categorical and control groups (Figure 4).

H1B: Participants perceive a higher dynamics of emotional expression when the number of facial expressions is higher.

The perception of emotional dynamics was higher in the appraisal group than in the control group (t(15) = -2.06; p < 0.05).

Yet, the control group and the categorical group were equivalent in terms of perception of expression dynamics (t(13) = -0.83; p < 0.42 NS).

Finally, the comparison between the categorical group and the appraisal group revealed only a trend effect for the perception of dynamics of emotional expression (t(18)=-1.87; p<0.08). Figure 4 illustrates these results.

These results partly confirm our hypothesis H1B.

To summarize, we observed the following relations that partly confirm our hypothesis H1: Perception of expression of emotions: control group < categorical group < appraisal group Perception of the dynamics of emotional expression: (control group = categorical group) < appraisal group H2: Participants' attribution of emotional states and other cognitive mental states to the VC depends on the condition. H2A: Participants attribute less emotional states to the VC in the control group than in the categorical and appraisal groups Participants attributed a higher number of emotional states to MARC in the categorical and appraisal groups than participants in the control group (t(13) = -2.40; p < 0.03; t(15) = -4.06; p < 0.001) (see Figure 4) Furthermore, we did not observe any significant differences between the categorical and appraisal groups in terms of attribution of internal emotional states. Participants in these conditions assigned the same number of emotional states to MARC.

These results validate our hypothesis H2A. Subjects attributed a higher number of emotional states when the agent expressed emotions.

H2B: Participants attribute more non-emotional cognitive mental states to the VC in the appraisal group than in the control and categorical groups

The attribution of non-emotional cognitive mental states is higher in the appraisal group than in the control group (t(15) = -2.87 ; p < 0.01) (see Figure 4). There is no difference in the attribution of non-emotional cognitive mental states between the control group and the categorical group. Yet, participants in the categorical and appraisal groups assigned as many non-emotional cognitive mental states to MARC. This result does not completely validate our hypothesis H2B. Participants did not judge the agent in the appraisal group as having more non-emotional cognitive mental states than the agent in the categorical group.

To summarize, we observed the following relations:

Objective measures

H3: Participants win more often and spend more time to play when the number of facial expressions is higher

The outcome of the game was analyzed with chi-square (χ²) test.

We observed that the outcome of the game depended on the group (χ²(2) = 6.39, p < 0.04).

We applied the Kolmogorov-Smirnov test to show that the following variable succeed to satisfy normality assumptions: total duration of the game (K-S d=0.15770, p<0.20).

Participants in the control group lost the game more often than participants in the categorical group and participants in the appraisal group. It seems that interacting with a VC that expressed emotions improved the performance of participants. Participants perceived these expressions of emotions and might rely on them to be more efficient.

The time that participants took to plan and make a move was analyzed by ANOVA using two variables: 1) the group and 2) the emotion expressed by the VC before each move. We also used Fisher's LSD for post-hoc pair-wise comparisons. Our results reveal that the total duration of a participant's actions did not depend on the condition (F(2, 755) = 0.39; p = 0.68 NS). The mean duration of a game was 9 minutes 50 seconds.

However, participants in the appraisal group only displayed some differences in the way they played depending on the emotion expressed by the agent. This result suggests that user uses the expression of the agent as a reliable source of information. We observed a trend effect depending on the agent's emotional expression before a participant's move (F(2, 317) = 2.41; p = 0.09). Participants played slower after that the agent expressed sadness than when the VC remained neutral following the previous move by the participant. A significant result was also observed for the emotion expressed by the VC following its own move (F(2, 317) = 2.9265; p = 0.05). Participants played slower when the character expressed pride than when it expressed joy.

These results partly confirm our hypothesis H3. Players were more efficient and won more often when they were playing against an expressive VC and even more often when the agent displayed sequential signs of appraisal. Besides, we observed that the emotion expressed by the character had some impact on participants' moves in the appraisal condition.

CONCLUSION

This paper presented a study exploring how participants perceive facial expressions of appraisal and emotion displayed by a VC during an interactive game. Our experimental results suggest some benefits of displaying dynamical emotional expressions inspired by appraisal theories of emotion. When the VC displays sequential facial expressions of evaluation checks, participants attributed more non-emotional cognitive mental states than in the control group. This result is in line with [START_REF] Smith | A componential approach to the meaning of facial expressions The psychology of facial expression[END_REF], who argued that the facial expression of each check have a particular emotional meaning. Our study suggests that these expressions of checks convey meaning regarding the agent evaluation process. The facial expression of a check might express both a cognitive and an emotional component. Thus, displaying facial signs of appraisal is likely to increase the perception that participants have of the cognitive capacities of the VC. Furthermore, no difference was observed between the categorical and the control groups in terms of reported non-emotional cognitive mental states. None of them featured the display of the cognitive evaluation of the situation.

However, we did not observe any difference between the categorical and the appraisal groups in terms of attributed non emotional cognitive mental states. An explanation might be found in the [START_REF] Scherer | Facial expressions allow inference of both emotions and their components[END_REF] who observed that static pictures of facial expressions of basic emotions allow human subjects to infer both emotion categories and the corresponding evaluation checks. Cognitive state might have been inferred in the categorical condition.

The expression of emotion by the VC had an impact on participants' behavior during the game. Participants relied on the emotions expressed by the agent to guide their actions and thinking. Subjects facing a VC expressing emotions used these emotions in a way that influenced their playing strategy. As a result, they won more often when the agent expressed emotion.

We also observed that participants in the appraisal group clearly took these subtle clues into account in their strategy, and that it did influence their behavior. We observed differences in the time that participants took to prepare the next move depending on the appraisals sequence displayed previously by the VC. Participants took more time to prepare a move following an expression of pride by the VC. This effect was not observed in the categorical group.

Our results suggest a difference between the instantaneous unconscious perception of signs of appraisal by participants (which impacts the way they play in the appraisal group) and the post-hoc report of perceived non-emotional cognitive mental states (no difference between the categorical and the appraisal groups). This difference points to the well-known complexity of measuring the perception of emotions and its impact on users.

FUTURES DIRECTION

The present study can be extended in several directions. The appraisals dynamics was hard set in our animation engine. However, [START_REF] Scherer | Appraisal considered as a process of multilevel sequential checking in Appraisal processes in emotion: Theory, Methods, Research[END_REF] suggests that the dynamics is driven by the appraisal process, and durations of facial expression vary. Our system could take these possible variations into account. Using more complex dynamics in facial feature animation could also be explored, both in categorical and appraisal condition. It might lead to more realistic expressivity and animations.

The interaction context of our game application was intentionally restricted to some events occurring during the game to better control our experiment. We only considered seven checks of the component process model. This study can be extended to include other checks and other events. Using a more complete interactive context such as [START_REF] Buche | MASCARET : A pedagogical multi-agent system for virtual environment for training[END_REF] might lead to a set of more complex emotions and possibly more realistic behaviors displayed one or several VC. Similarly, modern componential theories conceptualize appraisal as a recursive process; it is a constant effort for the individual to refine appraisal results and bring them into line with reality [START_REF] Scherer | Emotion and emotional competence: conceptual and theorical issues for modeling agents[END_REF]. The result is a constant change of the qualitative nature and intensity of the resulting emotion. Implementing such a reappraisal process in our VC might also contribute to giving the perception of a more "emotionally intelligent" agent.

In the current setup, participants provided input only by indicating where to play using the touch-screen. Yet, dealing with participants' affective states in real-time is a key to create a real affective interaction loop and to enable a more sophisticated affective strategy in the VC.

Figure 1 .

 1 Figure 1. Participants played Reversi against a VC. A touch screen was used to interact with the Reversi board.

Figure 2 .

 2 Figure 2. The MARC Framework adapted to Reversi.

Figure 3 .

 3 Figure 3. Frames of the VC's expressions: control condition, categorical condition (sadness), appraisal condition (sequence leading to sadness with the following values of appraisal checks: unexpected, unpleasant, high goal hindrance, no coping potential).

Figure 4 .

 4 Figure 4. Summary of our experimental results

ACKNOWLEDGMENTS

Part of the work described in this paper was funded by the Agence Nationale de la Recherche (ANR): project MOCA (ANR-12-CORD-019) and by the Cap Digital Cluster.


Ioannis Ignatiadis
email: ioannis.ignatiadis@brgm.fr

Stéphanie Betelu

Romain Rodrigues

Frédéric Garnier

Stéfan Colombano

Clément Zornig

MECHANISMS OF NATURAL REDUCTIVE BIODECHLORINATION (RDC) OF CHLORINATED SOLVENTS IN AN OLD POLLUTED SITE

A thirty years old polluted site (Néry-Saintines, Oise, France) is selected for the development and in situ implementation of a chemical process for the reductive dechlorination (RDC) of chlorinated solvents (CS) in groundwater. Before this implementation, the pollution was investigated through the underground water analyses: i) during 15 years (2000)(2001)(2002)(2003)(2004)(2005)(2006)(2007)(2008)(2009)(2010)(2011)(2012)(2013)(2014) from several tens of piezometers distributed in a large area of more than 1 km², and ii) during 6 months (July-December, 2014) locally, from 12 piezometers sampled at minus to depths (-10 and -20 m) and located in the pilot implementation zone of 50 m x 50 m, or 2500 m² (0.0025 km²). The objective of the study is to improve understanding on the mechanisms and kinetics of natural bioremediation occurred in the groundwater of this so old polluted site.

The pollution in the sandy aquifer (Cuisian period) stands today as a majority of CSs and their metabolites. The nature and the relative abundances of these compounds are investigated and their spatiotemporal evolutions are charted. Some other parameters or species were measured and considered (temperature, pH, redox potential, conductivity, contents in chloride, bicarbonate, dissolved iron, sulfate, phosphate, sulfide, ..). Chloride ion is the principal produced component (evolution from 20 mg/L in a near not impacted zone to up to 350 mg/L, fig. 1), as well as bicarbonate (150 to up to 650 mg/L). Chloride ion, is the result of reductive biodechlorination of (presence in w/w percentage): Tetrachloroethylene or PCE (0.3-1.0%), Trichloroethylene, TCE (25-45%), trans-1,2-DiChloroEthylène (DCE) (0.3-0.4 %), cis,1,2-DCE (0.5-15.0 %) and 1,1-DCE (40-50%), Vinyl Chloride (VC) (0.7-1.0%), 1,1-DiChloroEthane (0.8-1.3%), DC-Methane (0.2-0.4%), TCMethane (3.5-6.0), TetraCMethane (0.3-0.4%). The nature and the relative abundances of the components show the mechanism and the limiting steps of the RDC. The bicarbonate is resulted from CO 2 dissolution after its production by the total biodegradation of organics. The higher the chloride content, the higher the conductivity, the higher the bicarbonate content and the lower the redox potential. This means that the reductive biodechlorination and the anaerobic biodegradation occur concurrently in the same zones. These investigations once again confirm the mechanism of RDC (fig. 1) as proposed in the literature by [START_REF] Morrison | Environmental Forensics: Contaminant Specific Guide, Chapter 12: Chlorinated Solvents[END_REF], for natural RDC and also give and clear indication on its kinetics.

Fig. 1 .

 1 Fig. 1. Chloride spatiotemporal content evolution at some piezometers and mechanism of the RDC of PCE.

Acknowledgements: This study is accomplished within the framework of DECHLORED, a project financed by ADEME, the French Agency for the Environment and Energy Resources (Eco-Industries 2011 program).