Francesca Fossati

Stefano Moretti
email: stefano.moretti@lamsade.dauphine.fr.

Stefano Secci

A Mood Value for Fair Resource Allocations

In networking and computing, resource allocation is typically addressed using classical sharing protocols as, for instance, the proportional division rule, the max-min fair allocation, or other solutions inspired by cooperative game theory. In this paper, we argue that, under awareness about the available resource and other users' demands, in a cooperative setting such classical resource allocation approaches, as well as associated notions of fairness, show important limitations. We identify in the individual satisfaction rate the key aspect of the challenge of defining a new notion of fairness and, consequently, a resource allocation algorithm more appropriate for the cooperative context. We generalize the concept of user satisfaction considering the set of admissible solutions for bankruptcy games. We adapt the Jain's fairness index to include the new user satisfaction rate. Accordingly, we propose a new allocation rule we call 'Mood Value'. For each user it equalizes our novel game-theoretic definition of user satisfaction with respect to a distribution of the resource. We test the mood value and the new fairness index through extensive simulations showing how they better support the fairness analysis.

I. INTRODUCTION

In communication networks and computing systems, resource allocation (in some contexts also referred to as resource scheduling, pooling, or sharing) is a phase, in a network protocol or system management stack, when a group of individual users or clients have to receive a portion of the resource in order to operate a service. Resource allocation becomes a challenging problem when the available resource is limited and not enough to fully satisfy users' demand. In such situations, resource allocation algorithms need to ensure a form of fairness. Such situations emerge in a variety of contexts, such as wireless access [START_REF] Saad | Coalitional games for distributed collaborative spectrum sensing in cognitive radio networks[END_REF], [START_REF] Ghimire | Revisiting scheduling in heterogeneous networks when the backhaul is limited[END_REF], competitive routing [START_REF] Orda | Competitive routing in multiuser communication networks[END_REF], transport control [START_REF] Sy. Yun | Distributed Proportional Fair Load Balancing in Heterogenous Systems[END_REF].

The common methodology adopted in the literature is to, on the one hand, determine allocation rules such that they satisfy desirable properties [START_REF] Thomson | Axiomatic and game-theoretic analysis of bankruptcy and taxation problems: an update[END_REF], and, on the other hand, analyse the fairness of a given allocation through indices, the most commonly used being the Jain's index [START_REF] Jain | A quantitative measure of fairness and discrimination for resource allocation in shared computer system[END_REF]. Allocation rules and indices of fairness are commonly justified by some fairness criteria. For instance, among two equivalent users demanding the same amount of resource, it makes sense not to discriminate and to give to each of them the same portion of the resource. In some cases, it can be desirable to guarantee at least a minimum amount of the resource so that the maximum number of users can be served.

In the networking literature, the resource allocation problem is historically solved as a single-decision maker problem in which users are possibly not aware of the other users' demands and of the total amount of available resource. It follows that the Fig. 1: A critical resource allocation situation example most natural and intuitive way to quantify the user satisfaction is through the proportion of the demand that is satisfied by an allocation. Large literature exists indeed in the networking area on proportional resource allocations for many practical situations, from wireless networks to transport connection management [START_REF] Ghimire | Revisiting scheduling in heterogeneous networks when the backhaul is limited[END_REF], [START_REF] Orda | Competitive routing in multiuser communication networks[END_REF], [START_REF] Sy. Yun | Distributed Proportional Fair Load Balancing in Heterogenous Systems[END_REF].

In this paper, we are particularly interested instead in cooperative networking contexts such that users can be aware of other users' demands and the available amount. As such, rational users shall compute their satisfaction also based on the presence of other users. In fact, such networking contexts with demand and resource availability awareness are making surface in wired and wireless network environments with an increasing level of programmability, i.e., using softwaredefined radio and network platforms that expose novel (northbound) interfaces to users to disseminate information and pilot network resource allocations. Our main idea is defining a new notion of user satisfaction for such interactive resource allocation situations with demand and resource awareness.

Let us briefly clarify our motivation with the following allocation example. A user i asks a quantity of resource that is bigger than the resource itself (as B in Fig. 1). Classical fairness indices [START_REF] Jain | A quantitative measure of fairness and discrimination for resource allocation in shared computer system[END_REF], [START_REF] Ab | On the measurement of inequality[END_REF], [START_REF] Mo | Fair end-to-end window-based congestion control[END_REF] tend to qualify the user satisfaction as maximum when i obtains exactly what it asks. In the case where i asks more than the available amount, it cannot reach the maximum satisfaction due to the fact that its demand exceeds the available resource. Instead, in demand and resource awareness conditions, it would be more reasonable that its satisfaction is maximum when it obtains all the available resource. Furthermore, if all the other users together ask a quantity of good inferior to the resource, a minimum portion of it, equal to the difference between the resource and the sum of the demands of all the others, is guaranteed to i. Under a dual reasoning, it also appears more acceptable that the minimum satisfaction of a user is reached when it receives the minimum portion of the available resource, instead of when it receives zero. If users are in complete information context the classical approach can lead to not reasonable outcomes.

In this perspective, in order to better describe the user satisfaction as a function of the available resource, and to capture the interactions due to the networking context (e.g., networked users may be aware of respective demands, may ally in the formulation of their demands, etc), we propose to model the resource allocation problem as a coalitional game. Accordingly, we define a new satisfaction rate for users, able to adapt to various configurations of the demands. Furthermore, we define a new resource allocation rule, called the 'Mood Value', based on the idea that the most fair allocation is the one that equalizes the satisfaction of each player. Indeed, regardless of the level of satisfaction, each player is not discriminated if its satisfaction is the same than the one of all the others. Choosing this allocation, users, who have the chance to recover informations about the other users and the available resource, have the feeling to receive a fair portion of the resource. We also provide an interpretation of this approach positioning it with respect to classical traffic theory [START_REF] Fp | Rate control for communication networks: shadow prices, proportional fairness and stability[END_REF]. The paper is organized as follows. Section II presents the state of the art on the topic. In Section III a new satisfaction rate is proposed. In Section IV the mood value and a new fairness index are described. In Section V we provide an interpretation of the mood value with a traffic theory methodology, i.e. as result of the maximization of an appropriate utility function. Section VI presents some numerical examples. Finally, Section VII concludes the paper.

II. BACKGROUND

A resource allocation problem can be characterized by a pair (c, E), in which c is the vector of demands (claims) from n users (claimants) and E is the resource (estate) that should be shared between them. The set of users is N = {1, ..., n}. The resource allocation is a challenging problem when E is not enough to satisfy all the demands ( n i=1 c i ≥ E). An allocation x ∈ R n is a solution vector that satisfies three basic properties:

• Non-negativity: each user should receive at least zero.

• Demands boundedness: each user cannot receive more than its demand. • Efficiency: the sum of all allocations should be E. An allocation rule is a function that associates a unique allocation vector x to each (c, E).

A. Classical resource allocation rules

Many resource allocation rules are proposed in the literature and each of them is characterized by a set of properties that justify the use of the given rule in order to find a solution of the allocation problem [START_REF] Thomson | Axiomatic and game-theoretic analysis of bankruptcy and taxation problems: an update[END_REF]. In computer networks, the most well-known rules are: the proportional rule and the weighted proportional rule [START_REF] Fp | Rate control for communication networks: shadow prices, proportional fairness and stability[END_REF], the max-min fair allocation (MMF) [START_REF] Dp | Data networks[END_REF], [START_REF] Ogryczak | Fair optimization and networks: A survey[END_REF], and the α-fair allocation [START_REF] Mo | Fair end-to-end window-based congestion control[END_REF]. Each of these allocation rules, result of an optimization problem and/or an iterative algorithm, follows a fairness criterion.

The weighted proportional allocation rule is based on the idea that a logarithmic utility function captures well the individual evaluation of the worth of the resource [START_REF] Fp | Rate control for communication networks: shadow prices, proportional fairness and stability[END_REF]. One way to compute it is via the maximization of n i=1 w i log x i subject to demand boundness and efficiency constraints. When w i is equal to 1 the resulting allocation is called simply proportional and when w i is equal to c i we obtain the allocation that actually produces allocations proportional to the demands; hence in the following, we refer to the latter rule as 'proportional' instead of the previous (not weighted) one.

The idea behind the max-min fairness (MMF) allocation is to maximize firstly the minimum allocation; secondly, the second lowest allocation, and so on [START_REF] Dp | Data networks[END_REF], [START_REF] Ogryczak | Fair optimization and networks: A survey[END_REF]. This solution coincides with the only feasible allocation such that, if the allocation of some users is increased, the allocation of some other users with smaller or equal amount is decreased.

More generally, it is possible to obtain a family of allocation rules maximizing a parametric utility function. The α-fair utility function is defined as [START_REF] Mo | Fair end-to-end window-based congestion control[END_REF]. If α → 1 the solution of the optimization problem coincides with the weighted proportional allocation with w i equal to 1, if α = 2 with the minimum delay potential allocation, that is the allocation obtained minimizing the total potential delay n i=1

n i=1 x (1-α) i 1-α
( 1 xi ) [START_REF] Massoulié | Bandwidth sharing: objectives and algorithms[END_REF], and if α → ∞ with the max-min fair allocation.

B. Game theoretical allocation rules

Recently game theory has been applied to communication systems in order to model network interactions. For example, in [START_REF] Rj | A game-theoretic look at the Gaussian multiaccess channel[END_REF] a cooperative game model is proposed to select a fair allocation of the transmission rate in multiple access channels and in [START_REF] Mathur | Coalitions in cooperative wireless networks[END_REF] the authors studied, using coalitional game theory, the cooperation between rational users in wireless networks.

Moreover, it is possible to analyze the allocation problem as a Transferable Utility (TU) game [START_REF] Mc | Bankruptcy-based radio resource management for multimedia mobile networks[END_REF], [START_REF] Hoteit | A nucleolus-based approach for resource allocation in OFDMA wireless mesh networks[END_REF], [START_REF] Hoteit | On fair network cache allocation to content providers[END_REF], which is defined as a pair (N, v), where N = {1, . . . , n} denotes the set of players and v : 2 N → R is the characteristic function, (by convention, v(∅) = 0). Bankruptcy games [START_REF] Thomson | Axiomatic and game-theoretic analysis of bankruptcy and taxation problems: an update[END_REF], in particular, deal with situations where the number of claimed resource exceeds that available. A Bankruptcy game is a TUgame (N, v) in which the value of the coalition is given by

v(S) = max{E - i∈N \S c i , 0} (1)
where E ≥ 0 represents the estate to be divided and c ∈ R N + is a vector of claims satisfying the condition i∈N c i > E [START_REF] Owen | Game Theory[END_REF], [START_REF] Rj. Aumann | Game theoretic analysis of a bankruptcy problem from the Talmud[END_REF]. The bankruptcy game is superadditive, that is:

v(S ∪ T ) ≥ v(S) + v(T ), ∀S, T ⊆ N |S ∩ T = ∅ (2)
it is also supermodular (or, equivalently, convex), that is:

v(S ∪ T ) + v(S ∩ T ) ≥ v(S) + v(T ) ∀S, T ⊆ N (3)
A classical set-value solution for a TU-game is the core C(v), which is is defined as the set of allocation vectors x ∈ R N for which no coalition has an incentive to leave the grand coalition N , i.e.:

C(v) = {x ∈ R N : i∈N x i = v(N ), i∈S x i ≥ v(S) ∀S ⊂ N }. (4)
A one-point solution (or simply a solution) for a class C N of coalitional games is a function ψ : C N → R N that assigns a payoff vector ψ(v) ∈ R N to every coalitional game in the class. A well-known solution for TU-games is the Shapley value [START_REF] Ls | A value for n-person games[END_REF] φ(v) of a game (N, v), defined as the weighted mean of the players' marginal contributions over all possible coalitions and computed as follows:

φ i (v) = S⊆N :i∈S w i (S)(v(S) -v(S \ {i})), (5)
with w i (S) = (s-1)!(n-s)! n!

where s denotes the cardinality of S ⊆ N . Another well studied solution for TU-games is the nucleolus, based on the idea of minimizing the maximum discontent [START_REF] Schmeidler | The nucleolus of a characteristic function game[END_REF]. Given a TU-game (N, v) and an allocation x ∈ R N , let e(S, x) = v(S) -i∈S x i be the excess of coalition S over the allocation x, and let ≤ L be the lexicographic order on R. Given an imputation x, θ(x) is the vector that arranges in decreasing order the excess of the 2 n -1 non-empty coalitions over the imputation x. The nucleolus ν(v) is defined as the imputation x (i.e., i∈N x i = v(N ) and x i ≥ v({i}) for each i ∈ N ) such that θ(x) ≤ L θ(y) for all y imputations of the game v.

Given a bankruptcy game, many other solutions can be proposed [START_REF] Thomson | Axiomatic and game-theoretic analysis of bankruptcy and taxation problems: an update[END_REF]. As already introduced in the previous section, the proportional allocation assigns to player i an allocation

equal to E • c i / n i=1 c i .
For example, it is worth mentioning the Constrained Equal Loss (CEL) allocation that divides equally the difference between the sum of the demands and E, under the constraint that no player receives a negative amount.

C. Fairness indices

The evaluation of the fairness of the allocations, used as an important system performance metric especially in networking, can be useful to discriminate among allocation rules and to evaluate the level of 'justice' in the repartition of the resources. Jain [START_REF] Jain | A quantitative measure of fairness and discrimination for resource allocation in shared computer system[END_REF] introduces a formula aimed at providing a quantitative measure of the fairness of a resource sharing allocation.

Definition 1 (Jain's index). Given an allocation problem (c, E) and an allocation x, the Jain's fairness index is:

J = n i=1 x i c i 2 n n i=1 x i c i 2 (6)
The Jain's index is bounded between 1 n and 1 [START_REF] Jain | A quantitative measure of fairness and discrimination for resource allocation in shared computer system[END_REF]. The maximum fairness is measured when all the users obtain the same fraction of demand and the minimum fairness is measured when it exists only one user that receives all the resource. The Jain's index has the following good properties:

• Population size independence: applicable to any user set, finite or infinite. • Scale and metric independence: not affected by the scale.

• Boundedness: can be expressed as a percentage.

• Continuity: able to capture any change in the allocation. The index considers the proportion of demand and it gives the maximum fairness to the allocation for which all the users receive the same proportion of the demand, regardless of the type of allocation problem, it suggests to allocate the resources in a proportional way even when this allocation is not the most suitable to solve the problem. Another well-know index of fairness is the Atkinson's index [START_REF] Ab | On the measurement of inequality[END_REF]; contrary to the Jain's index, it measures the degree of inequality of a given allocation, taking value equal to 0 when the system is 100% fair in the MMF sense, and 1 when it is totally unfair. I along with the Jain's index and 1-Atkinson's index in order to have a measure of fairness. 1).

The axiomatic theory of fairness proposed in [START_REF] Lan | An axiomatic theory of fairness in network resource allocation[END_REF] shows that it exists an unique family of fairness measures, which includes the Jain's and the Atkinson's indices, satisfying a set of reasonable axioms. In the rest of the paper, we consider only the Jain's index because it is the one classically used in networking applications. MMF-driven inequality indices find their most appropriate use in socio-economical contexts, because they are linked to the concept of welfare of an income distribution. Furthermore the Jain's index is based on the idea of summarizing the information about the users' satisfaction, which is close to our methodology of redefining users' satisfaction under demand and resource awareness, as discussed in the following section.

III. FROM DEMAND FRACTION SATISFACTION TO GAME THEORETICAL SATISFACTION

In this section, we propose a game-theoretic approach to evaluate the satisfaction of a user for an allocation.

A. User satisfaction rate

A crucial issue in resource allocation is to jointly:

• find the best solution in terms of a certain goal;

• evaluate its fairness by referring to a fairness index. With this purpose, it is important to evaluate the individual satisfaction rates and to summarize the information given by each of them with a global fairness index.

A natural way to quantify the satisfaction of a user, as proposed by Jain, is through the proportion of the demand that is satisfied by an allocation [START_REF] Jain | A quantitative measure of fairness and discrimination for resource allocation in shared computer system[END_REF].

Definition 2 (Demand Fraction Satisfaction rate). Given the user i with demand c i and an allocation x i , the Demand Fraction Satisfaction (DFS) rate of i is:

DF S i = x i c i . (7)
This rate takes value between 0 and 1 since it represents the percentage of the demand that is satisfied.

Unavoidably, this way to quantify the user satisfaction makes the weighted proportional allocation the fairest one since it allocates proportionally to the demand. There are, however, situations in which the common sense does not suggest to allocate in a proportional way; e.g., if there is a big gap between the demands, in order to protect the 'weaker' users and guarantee them a minimum portion of the estate, the MMF allocation can be preferable. Furthermore, as mentioned in the introduction, the presence of other users should rationally be considered not to distort the satisfaction of each user, in case of awareness about other users' demand and the available demands.

For these reasons, we aim at defining an alternative satisfaction rate such that it satisfies the following two properties we name demand relativeness and relative null satisfaction:

• Demand relativeness: a user is fully satisfied when it receives its maximal right, based on the available resource; • Relative null satisfaction: a user has null satisfaction when it receives exactly its minimal right, based on other users' demands and the available resource. The minimal right for a player is the difference between the available amount and the sum of the demands of the other users (i.e., taking a worst case assumption that the others get the totality of their demand), and the maximal right is equal to the maximum available resource, i.e., c i if c i < E, or it is equal to E otherwise. Remembering the definition of the characteristic function of a bankruptcy game we have that:

• the minimal right for player i is v(i)

• the maximal right for player i is v(N ) -v(N \ i) Thus we introduce the 'player satisfaction (PS) rate', which satisfies the above two properties by considering the value of the bankruptcy game associated to the allocation problem.

Definition 3 (Player Satisfaction Rate). Given a bankruptcy game such that n i=1 c i > E and an allocation x i , the Player Satisfaction (PS) rate for i is:

P S i = x i -min i max i -min i , (8)
where: [START_REF] Saad | Coalitional games for distributed collaborative spectrum sensing in cognitive radio networks[END_REF] if the allocation belongs to the core (see Proposition 1). Moreover it 'corrects' DF S i since it replaces the interval of possible values [0, c i ] for x i with the interval [min i , max i ]. Consequently, if for the DFS rate the maximum satisfaction for i is measured when it gets c i and the minimum when it gets 0, with PS, i is measured to be totally satisfied when it gets max i and totally unsatisfied when it gets min i . In both cases the PS rate shows that player 2 is less satisfied than what expected with the DFS rate. This is due to the fact that the game guarantees player 2 to get at least 5.

min i = v(i), max i = v(N )-v(N \i). If n i=1 c i = E the player satisfaction rate is P S i = 1, ∀i ∈ N . P S i ∈ [0,
The following propositions show some interesting properties of the PS rate.

Proposition 1. If the allocation x belongs to the core of the bankruptcy game, P S i ∈ [0, 1] ∀i ∈ N .

Proof. If a solution x belongs to a core it holds:

x i ≥ v(i) and x i ≤ v(N ) -v(N \ i). Thus v(i) and v(N ) -v(N \ i)
are the minimum and the maximum value that an allocation in the core can take. If

x i = v(i) = min i then P S i = 0, if x i = v(N ) -v(N \ i) = max i then P S i = 1.
Proposition 2. It is possible to summarize the bankruptcy regimes of the P S rate in four possible cases as in Table II.

c i < E c i ≥ E PS case PS case v(i) = 0 x i c i GM x i E GG v(i) = 0 x i -v(i) c i -v(i) MM x i -v(i) E-v(i)

MG

TABLE II: Value of PS in the four possible cases.

Proof. Let us treat each possible cases of Table II:

• Case GM: v(i) = 0, c i < E
Using the definition of bankruptcy game, it holds:

v(N ) -v(N \ i) = E -max{0, E -c i } = E -E + c i . It follows P S i = x i /c i . • Case GG: v(i) = 0, c i ≥ E
Using the definition of bankruptcy game, it holds:

v(N ) -v(N \ i) = E -max{0, E -c i } = E. It follows P S i = x i /E • Case MM: v(i) = 0, c i < E As in case MG, v(N )-v(N \i) = E -max{0, E -c i } = c i . It follows P S i = (x i -v(i))/(c i -v(i)). • Case MG: v(i) = 0, c i ≥ E As in case GG , v(N )-v(N \i) = E -max{0, E -c i } = E. It follows P S i = (x i -v(i))/(E -v(i)).
Case terminology: the PS rate differentiates 4 possible cases we name GM, GG, MM, MG. If a player asks less than E we call it moderate player (M) while if it asks more than E it is a greedy player (G). In similar way, if the sum of the demand of a group of n -1 players exceeds E, that means v(i) = 0, the group is a group of greedy players (G) otherwise if v(i) = 0 we have a group of moderate players (M).

Proposition 2 highlights that, not only there is a relation between the DFS rate and the PS rate, the satisfaction of a user should be modified when it is considered as a player inside a cooperative game. In particular, we can notice that for case GM the PS rate coincides with the DFS one, i.e., P S i = DF S i ; for case GG, the user satisfaction measured with the PS rate is higher than when it is measured with the DFS rate, i.e., P S i ≥ DF S i ; in the MG case, we have instead that DF S i ≥ P S i . We can also notice that the denominator of the PS rate is always different from zero. In cases GM and GG this is obviously true, in case MM the denominator is zero when n i=1 c i = E but in this case we set P S i = 1 and in case MG the denominator is zero when j∈N,j =i c j = 0 that is impossible. Furthermore, from Proposition 2 it follows that if an allocation, i.e. a solution of an allocation problem that satisfies efficiency, non-negativity and demand boundedness, is an imputation, then P S i ∈ [0, 1] for all the users. This holds due to the fact that for an allocation, in each of the 4 cases presented above, it is always verified that v(N ) -v(N \ i) is an upper bound for x i .

B. Game-theoretical interpretation

To support and justify the use of the new satisfaction rate, we show an interesting game-theoretic interpretation.

Gately [START_REF] Gately | Sharing the gains from regional cooperation: A game theoretic application to planning investment in electric power[END_REF] introduced the concept of propensity to disrupt in order to eliminate the less fair imputation inside of the core. The idea was to investigate the gain of the player from the cooperation or, instead, its propensity to leave the cooperation, and to eliminate the imputation for which the propensity to leave the coalition for some players is excessively high. The formal definition of the propensity to disrupt is given in [START_REF] Sc | The propensity to disrupt and the disruption nucleolus of a characteristic function game[END_REF]. Definition 4 (Propensity to disrupt). For any allocation vector x, the propensity to disrupt d(x, S) of a coalition S ∈ N (S = ∅, N ) is the ratio of the loss incurred by the complementary coalition N \ S to the loss incurred by the coalition S itself if the payoff vector is abandoned. In formula,

d(x, S) = x(N \ S) -v(N \ S) x(S) -v(S) . (9)
An equivalent definition of d(x, S) is :

d(x, S) = x(S) -v(S) x(S) -v(S) -1 (10)
where: x(S) = v(N ) -v(N \ S) [START_REF] Gately | Sharing the gains from regional cooperation: A game theoretic application to planning investment in electric power[END_REF].

The propensity to disrupt of a coalition S quantifies its desire to leave the coalition. When x(S) = v(S) the propensity to disrupt of S is infinite and the desire of S to leave the coalition is maximum; when x(S) > v(S) but x(S) -v(S) is small, the value of d(x, S) is very high and again S does not like the agreement; when x(S) = v(N ) -v(N \ S) the propensity to disrupt is zero and S has the propensity not to destroy the coalition; when x(S) > v(N ) -v(N \ S) the index is negative and there is an hyper-enthusiasm for such an agreement.

It holds an interesting relationship between the propensity to disrupt and the player satisfaction rate. Proposition 3. The relationship between the player satisfaction rate and the propensity to disrupt is:

P S i = 1 d(x, i) + 1 . ( 11
)
Proof. Using the alternative definition of d(x, i) we have

d(x, i) = v(N ) -v(N \ i) -v(i) x i -v(i) -1 (12) but v(N )-v(N \i)-v(i) xi-v(i)
is equal to 1 P Si so d(x, i) = 1 P Si -1. It is worth noting that if d(x, i) goes to infinity, then P S i goes to 0 and if d(x, i) = 0 then P S i = 1. This gives another interpretation of the PS rate. The higher the satisfaction is, the bigger the enthusiasm of i, for being in the coalition, is. On the contrary, the closer to zero the user satisfaction is, the higher the propensity of user i to leave the coalition is.

IV. THE MOOD VALUE AND THE PLAYER FAIRNESS INDEX

In this section, we define a new resource allocation rule we call the Mood Value. The fairness idea behind this rule is the same of the one behind the Jain's index. A repartition of a resource is fair when all the users have the same satisfaction. Furthermore, we propose a novel fairness index as a modification of the Jain's index.

A. The Mood Value

Using the defined PS rate, we can define the mood value.

Definition 5 (Mood Value). Given an allocation problem characterized by (c, E), the allocation x such that P S i = P S j ∀i, j ∈ N is called mood value.

Due to the relation between the propensity to disrupt and the player satisfaction, the fairest solution corresponds to the one in which every player has the same propensity to leave the coalition. Equalizing the propensity to disrupt of the users, this allocation equalizes the mood of each player. In particular, given a game, it exists a unique mood such that the satisfaction of each user is the same. The closer to zero the mood is, the more unsatisfied user i is; the closer to one the mood is, the more enthusiast the user i is.

m = E -min max -min (13)
where min

= n i=1 v(i) = n i=1 min(i) and max = n i=1 [E - v(N \ i)] = n i=1 max(i).
And the mood value is given by:

x m i = v(i) + m(max(i) -min(i)). ( 14
)
Proof. Let P S i = m ∀i ∈ N . It follows:

x i = m(E -v(N \ i)) + (1 -m)v(i).
Due to the efficiency property it holds:

n i=1 m(E -v(N \ i)) + (1 -m)v(i) = E.
Thus [START_REF] Rj | A game-theoretic look at the Gaussian multiaccess channel[END_REF]. Since x i is the mood value iff P S i = m ∀i ∈ N :

x i -v(i) E -v(N \ i) -v(i) = m ( 15
)
∀i ∈ N and ( 14) remains proved.

From [START_REF] Rj | A game-theoretic look at the Gaussian multiaccess channel[END_REF] we can notice that the mood depends only on the game setting, thus, given a bankruptcy game, we can know a priori the value of the mood that produces a fair allocation. Knowing m, on can easily calculate the mood value x m i .

The formula [START_REF] Mathur | Coalitions in cooperative wireless networks[END_REF] shows that each user receives the minimum possible allocation v(i) plus a portion m of the quantity max i -min i . The nearer to 1 is the mood m, the greater is the happiness of each user, and the closer to the maximum the allocation is. In fact, when m is equal to 1, the player receives exactly E -v(N \ i), that is the maximum portion of resource that it can get, being inside a bankruptcy game.

The mood value owns some interesting properties. It is an allocation thus it satisfies non-negativity, demand boundedness and efficiency property; it is stable, that means it belongs to the core of the game (prop. 5) and it guarantees more than minimal right to each player (x m i > v(i)). Furthermore it satisfies the following property: if v(i) = v(j) and v(N \i) = v(N \j) then x m i = x m j . This implies the equal treatments of equals (c i = c j ⇒ x m i = x m j ) and equal treatment of greedy claimants (given a bankruptcy game, let G be the set of greedy players, i.e. such that

c i > E: if |G| ≥ 2 then x m i = x m j ∀i, j ∈ G)
. This last property guarantees that even if a user has a cheating behavior its demand is bounded by the available amount of resource E. Furthermore the mood value is a strategy-proof allocation because a user has no advantages in splitting his demand.

Proposition 5. The mood value belongs to the core of (N, v).

Proof. We should prove that x m S ≥ v(S), ∀S ⊆ N . If v(S) = 0 the condition holds due to the fact that x m i < 0, ∀i ∈ N . Now consider the case v(S) > 0. Suppose that x m S < v(S) = E -i∈N \S c i . For the efficiency property it holds E = x m S + x m N \S , implying x m N \S > i∈N \S c i , which yields a contradiction with the fact that, according to the mood value solution, each user receives at most its demand.

Mood Value Computation Complexity: Differently from the other allocation solutions inspired by game theory, in order to calculate this new allocation, only the value of 2n coalitions, i.e., the ones formed by the single players and the ones containing n -1 players, is needed. The time complexity of mood value computation is dominated by the complexity of computing v(i) that is O(n). In dynamic situations, i.e. when the value of each of the n coalitions has to be updated at each slot of time, the complexity is therefore O(n 2 ), but it can be reduced to O(n) where v(i) pre-computation is possible. This makes the mood value the best allocation rule in terms of time complexity together with the proportional allocation: the Shapley value has a time complexity of O(n!), while iterative algorithms for the computation of MMF and CEL allocations have a O(n 2 log n) time complexity; the Nucleolus computation is a NP-hard problem.

In terms of spatial complexity, the mood value, proportional, MMF and CEL allocations can be considered as equivalent and in the order of O(n). Instead, the Shapley value and the Nucleolus computations have a spatial complexity of O(2 n ).

B. The Player Fairness Index

Considering the observed good properties that make the Jain's index a strong fairness index, we propose its modification replacing the DFS rate of the Jain's index with the PS rate. The resulting new fairness index we propose takes value 1 when all the users have the same satisfaction, i.e., when the allocation is the mood value. Definition 6 (Players fairness index). Given a problem (c, E) and an allocation x, the players fairness index is:

J p = n i=1 P S i 2 n n i=1 P S i 2 (16)
Proposition 6. The players fairness index takes value in [ 1 n , 1] when the allocation belongs to the core.

Proof. From Proposition 1 follows that P S i belongs to [0, 1] and that n i=1 P S i is always not negative. The maximum fairness is measured when all the users have the same PS rate, i.e.:

n i=1 P S i 2 = nP S i 2 ⇒ n n i=1 P S i 2 = nn P S i 2 .
Thus J p = 1. The minimum fairness is measured when ∃!k s.t. P S k = 0 and P S j = 0 ∀j = k. In this case:

n i=1 P Si 2 = P S k 2 ⇒ n n i=1 P Si 2 = n P S k 2 ⇒ Jp = 1 n
For core allocations, J p takes value in the same interval of J making possible a comparison between the two indices. Furthermore, this index maintains all the good properties of the Jain's index: the population size independence, the scale and metric independence, the boundedness and the continuity.

V. INTERPRETATION WITH RESPECT TO TRAFFIC THEORY

In the already cited seminal works about the definition of proportional and weighted proportional allocations in network communications, network optimization models are defined using as goal the maximization of an utility function. A typical application is the bandwidth sharing between elastic applications [START_REF] Fp | Rate control for communication networks: shadow prices, proportional fairness and stability[END_REF], i.e., protocols able to adapt the transmission rate upon detection of packet loss. In this context we show how it is possible to revisit the mood value as a value resulting of the sum of the minimum allocation and the result of a weighted proportional allocation formulation where the weights are not the original demands, but new demands re-scaled accordingly to the maximum possible allocation knowing the available resource, and the minimum allocation under the awareness of other user's demands and the available resource. More precisely, the mood value can be computed as the result of the following 4-step algorithm.

Step 1: We assign to each user the minimal right v(i).

Step 2: We set the new value of the estate E = E -min = E -n i=1 v(i) and the new demands c i = max i -min i .

Step 3: We solve the following optimization problem maximize

x n i=1 c i log x i subject to x i ≤ c i , i = 1, . . . , n x i ≥ 0, i = 1, . . . , n n i=1 x i = E (17)
Step 4: The mood value coincides with the sum of the minimal right and the allocation given by step 3:

x m i = v(i) + x i . Proof.
We should prove that the result of the optimization problem is x i = mc i . The lagrangian of the problem is

L(x, µ, λ) = n i=1 c i log x i -µ T (C -Ax) -λ(E - n i=1 x i )
where the vector µ and λ are the lagrangian multipliers (or shadow prices), C is the vector of the demands [c 1 , ...c n ] and A is the identity matrix of dimension n. Then, ∂L ∂yi = Step 4: x m i = [1.5, 7.5, 1]. The algorithm shows that the mood value firstly assign the minimal right (step 1) and secondly, considering the new allocation problem resulting after the first assignment (step 2), it allocates in a proportional way the resources (step 3). The proportion of resource to allocated is the mood.

c i yi -µ i -λ.
We provides two ways to compute the mood value: ( 14) and the 4-step algorithm of Section V. It is clear that the computation of the mood value throught the formula ( 14) is less complex than the one using the 4 steps algorithm.

VI. NUMERICAL EXAMPLES

We tested the mood value and the new fairness index in a few significant configurations comparing them with the classical allocations and the Jain's index.

We considered two demands distributions: (i) a uniform distribution, and (ii) a Weibull distribution. The former can be considered as a baseline, while the latter a maybe more realistic one. Taking inspiration from cellular (OFDMA) resource allocation studies we emulated an indoor scenario of femtocells using the WINNER II channel model [START_REF] Yj | IST-4-027756 WINNER II D1. 1.2 V1. 2 WINNER II Channel Models[END_REF]: generating in a uniform way 10000 users around the cell station between 3 and 100 m, we associate resource blocks (RBs) to each of them with a transmit power between 1 and 100 dB; the resulting RB distribution is well fit by a Weibull distribution. We now consider a range for demand generation between 0 and 100 units and we generate from (i) a uniform distribution between 0 and 100 and (ii) from a Weibull distribution f

(x) = ( a b )( x b ) (a-1) e -( x b ) a
for x > 0 with scale parameter a = 40 and shape parameter b = 1.4.

It is worth noting that the Weibull distribution is quite close to the Pareto distribution (both are exponential ones), its and discrete variations (e.g., Zipf's one), for example used in innetwork content caching resource allocation [START_REF] Hoteit | On fair network cache allocation to content providers[END_REF] .

We run different instances with a ratio of E (available resource) ranging from 5% to 95% of the global demand. We first simulate 300 bankruptcy games with 3 and 5 users. Fig. 2 show the users configuration as a function of the available resource. With 3 users (Fig. 2a,c), for low value of E almost all are greedy players (GG case) due to the fact that the resource is small; increasing E the number of moderate players (GM) increases but also some users in configuration MG appear. In fact, increasing E some greedy players become moderate while the others remain greedy ones; some of them are greedy inside a group of greedy users (GG), while some others greedy inside a group of moderate ones (MG). When the available resource is higher than half of the global demand, greedy players GG disappear and the number of moderate players increases. In particular, users MM appear and they become the majority when the resource is large. With 5 users (Fig. 2b,d), we find a similar trend than with 3 users in the number of moderate players that increases when increasing E. However, MG users are few; in fact, it holds that it can exist at most one MG user in a game and, due to the higher number of users in the system, it is very unlikely that there exists only a player MG in the system such that the sum of the demands of the other n -1 players exceeds E. Thus, with a number of users higher than 5, one can practically reduce the number of user cases from 4 to 3. For this reason, in order to capture all the possible scenarios, we choose a low number of user for the first round of simulations. We consider the six allocations discussed before: Proportional, Shapley, Nucleolus, Mood Value, MMF and CEL. We calculate the Jain's fairness index and the players fairness index and we plot, for each ratio of E and each index, the mean value in between the first and third quantile lines. The Jain's index is depicted with the red color and square points while the players fairness index with the blue one and round points. Due to space limit, we do not show the case of 3 users with uniform demand distribution because similar to the 3-user one with the weibull distribution.

In the 3-user scenario (Fig. 4) it is possible to notice differences between the result obtained by the classical Jain's index and our new players fairness (PF) index. It is worth recalling that the Jain's index has value 1 when the allocation is proportional while the PF index is 1 when the allocation is the mood value. We can notice that the PF index considers the MMF allocation as a fair one when the available resource is small (high congestion), i.e., when there are many greedy users. In fact the MMF allocation and the mood value, are close: in such cases, both have the property of treating equally the greedy claimant, giving them the same portion of resource, independently of their demands. Instead, when E increases, the MMF one is not fair any longer because it satisfies more the two users with less claim while it gives the minimal right to the one with bigger claim; in fact, in such cases the mood value becomes closer to the Proportional allocation, to the Shapley value and to the Nucleolus. The similarity between the Proportional allocation and the mood value is due to the fact that the correct way to measure the satisfaction of moderate players is through the DFS rate and increasing E the number of moderate players increases. It follows that the allocation equalizing the DFS rates, i.e., the Proportional one, is close to the one equalizing the PS rates of user, i.e., the Mood Value. With 5 users (Fig. 3 and Fig. 5), we can notice that, due to the fact that the group MG is little, when E reach the 40% of the global demand the Proportional is equal to the Mood value and it shows a PF index equal to 1. Furthermore the MMF allocation show again a high (PF) fairness when the resource is little (5%), i.e., when there are many greedy players.

With a second round of simulations we want to see how the Demand Fraction (DFS) and Player (PS) Satisfaction rates are distributed with an increasing number of users. Results are shown in Figure 6 as box-plots (minimum, quantiles and maximum, without outliers), for two regimes (high congestion of a 5% E/demand ratio, and low congestion of a 95% ratio). We can notice that the value of the satisfaction is low when the resource is small (Fig. . 6a,b,c) while it is higher when the congestion is low (Fig. 6d,e,f). With 4 users, in terms of user satisfaction rate, the mood value is close to the MMF allocation when the congestion is high, and to the proportional allocation when the congestion is low. As the number of players grows, the absolute difference between allocation in terms of distribution of the satisfaction decrease. In both the congestion situations (E equal to 5% and 95% of the demand) the Shapley value is the closest allocation to the mood value in terms of PS rate.

Summarizing, the simulations show that the Mood Value is able to nicely weight the nature (greedy or moderate) of users and of user groups. In particular it is close to the MMF allocation when the resource is scarce and to the proportional allocation when the resource is close to the global demand. Furthermore, it is worth noticing that with respect to classical game-theoretical allocation rules (Shapley Value, Nucleolus), the results show that the Mood Value shows a similar good behavior in terms of fairness, with the key advantage of having

VII. CONCLUSION

We proposed a game-theoretical approach to analyze and solve resource allocation problems, going beyond classical approaches that do not explore the setting where users can be aware of other users' demand and the available resource.

In particular, we proposed a new way of quantifying the user satisfaction and a new fairness index as enhancement of the Jain's index, describing and comparing their mathematical properties in detail. Accordingly to these new concepts, we propose a new resource allocation rule that meets the goal of providing the fairest resource allocation, we called the 'Mood Value', which we position with respect to game theory metrics as well the common theory of fair allocation in networks. Finally, we test our ideas via numerical simulations of representative demand distributions, showing at which extent the mood value can approach and differ from max-min-fairness, weighted proportional, constrained-equal loss, Shapley Value and Nucleolus allocations.

Example 1 .

 1 Let (c, E) be the situation of Fig. 1 with c = (3, 13, 2) and E = 10. The discussed allocation rules provide values in Table

Example 2 .

 2 Consider (c, E) of Example 1 (see Fig.1) and the corresponding bankruptcy game model. It holds: Proportional allocation: DF S 2 = 0.555 and P S 2 = 0.444 MMF allocation: DF S 2 = 0.3846 and P S 2 = 0.

Proposition 4 .

 4 Let (c, E) characterize an allocation problem. It exists a unique mood m such that P S i = m ∀i ∈ N ; it is:

1 m

 1 The optimum is given by y i = c i µi+λ when µ ≥ 0, Ay ≤ C, n i=1 y i = E and µ T (C -Ay) = 0. This coincides with the case in which µ T = 0 and λ = 0. In fact, we have E . It follows that λ = 1 E n i=1 c i is greater or equal to 1 and y i = c i λ is less or equal to c i , that is an admissible solution. We can now notice that λ = 1 E n i=1 c i = max-min E-min = . It follows y i = mc i . Example 3. Let (c, E) be the allocation problem of Fig. 1. Following the algorithm we have: Step 1: v(i) = [0, 5, 0]. Step 2: E = 5, c i = [3, 5, 2]. Step 3: x = [1.5, 2.5, 1]

Fig. 2 :

 2 Fig. 2: User cases distribution

Fig. 3 :Fig. 4 :Fig. 3 ,

 343 Fig. 3: Fairness as a function of E/demand (5 users, uniform)

Fig. 5 :

 5 Fig. 5: Fairness as a function of E/demand (5 users, weibull)

Fig. 6 :

 6 Fig. 6: Users satisfaction rates -E over global demand = 5% and 95% -uniform demand distribution a much lower computation time complexity.

TABLE I :

 I

Allocation rules: comparison (E = 10, cf. Fig.

ACKNOWLEDGMENT

This work was partially funded by the FED4PMR 'investissement d'avenir' project. The authors would like to thank Sahar Hoteit for her suggestions, and Deep Medhi and Catherine Rosenberg for their useful feedback.


Kei-Léo Brousmiche
email: kei-leo.brousmiche@lip6.fr

Jean-Daniel Kant
email: jean-daniel.kant@lip6.fr

Nicolas Sabouret
email: nicolas.sabouret@limsi.fr

François Prenot-Guinard
email: francois.prenot-guinard@airbus.com

Stéphane Fournier
email: stephane.fournier@airbus.com

From Field Data to Attitude Formation

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The new conflicts that arouse during the two last decades have brought a deep shift in military strategies [START_REF] Smith | The utility of force: the art of war in the modern world[END_REF]: most of the stabilization operations conducted by western forces involves opponents who blend themselves into the "human environment" to turn the population in their favor. In order to counter them, one should not only rely on tactical actions against them but also on non-kinetic actions such as reconstruction or specific communication actions that aim at altering the "hearts and minds" of the population. In this context, understanding the impact of actions performed by the intervention Force on the population's attitude is a major issue.

The concept of attitude derives from social psychology and could be defined as "a mental and neural state of readiness organized through experience" [START_REF] Allport | [END_REF]. Multi agent simulation of attitude dynamics seems a promising approach to study such complex social phenomenon since it is funded on individuals micro modeling and their interactions to analyze emergent macro trends [START_REF] Drogoul | Multi-agent simulation as a tool for modeling societies: Application to social differentiation in ant colonies[END_REF]. While multiple agentbased models have been proposed to study attitude and opinion (i.e. expressed attitude) dynamics [START_REF] Deffuant | Mixing beliefs among interacting agents[END_REF][START_REF] Urbig | Drifting to more extreme but balanced attitudes: Multidimensional attitudes and selective exposure[END_REF][START_REF] Brousmiche | The role of emotions on communication and attitude dynamics: an agent-based approach[END_REF], the major difficulty relies in validation: can a given model correctly reflect the attitude dynamics of a population in a conflict zone?

Opinion polls can provide target values. However, collecting field data to feed the simulation model and assessing the validity of its outcome (based on the expected values) can prove to be very difficult.

As part of our research, we have been given an access to polls results about opinions of the population toward the different present Forces (foreign Force and Taliban) in an area of Afghanistan where French forces conducted stabilization operations. These results have been collected by Altai Consulting for the French Ministry of Defense4 . Our analysis of these data has brought light to attitude dynamics that go against classical approaches in social simulation. First, most models compute the attitude as the aggregation of the impact of each feature, seen as independent criteria or events [START_REF] Urbig | Drifting to more extreme but balanced attitudes: Multidimensional attitudes and selective exposure[END_REF][START_REF] Deffuant | Mixing beliefs among interacting agents[END_REF]. However, people do not evaluate each action (such as food provision, military patrol, bombing attack, etc.) independently but towards what similar actions represents in general in terms of direct and indirect consequences for the population. It corresponds to Kahneman's memory-based, retrospective approach of evaluation [START_REF] Daniel Kahneman | Experienced utility and objective happiness: A moment-based approach[END_REF]. Second, we noticed that population's attitude toward the UN army could decrease when it fails to accomplish its securing mission. For instance, in case of a bombing attack, victims will not only blame insurgents who are directly responsible but also the Security Force which have "failed" to prevent such an event. It corresponds in this case to the concept of "role-responsibility" in the sense of Hart [START_REF] Lionel | Punishment and responsibility: Essays in the philosophy of law[END_REF]. More generally, people tend to attribute the responsibility of an action to other people, groups or situational factors in addition to the direct responsible [START_REF] Kelley | The processes of causal attribution[END_REF][START_REF] Jones | The attribution of attitudes[END_REF].

In this paper, we propose a multi-agent simulation model based on field data that will help to better comprehend attitude dynamics in conflict zones where the population is confronted to antagonists Forces. The next section presents the related works in social simulation of attitude dynamics to situate our work. Section 3 presents our datasets on the events and opinion polls in Afghanistan. Section 4 describes our model of agent and attitude dynamics. Finally, section 5 shows experimental results through a model calibration based on field data and attitude dynamics analysis.

Related works

Several researches have already proposed computational models of attitudes, from simple binary approaches [START_REF] Nowak | From private attitude to public opinion: A dynamic theory of social impact[END_REF] to more complex ones (e.g. [START_REF] Kottonau | Simulating political attitudes and voting behavior[END_REF]). However, as was pointed out by [START_REF] Castellano | Statistical physics of social dynamics[END_REF], most of these models' focuses are limited to the interactions between individuals: they do not consider the construction mechanism of the attitude itself at a cognitive level. On this matter, Urbig and Malitz [START_REF] Urbig | Drifting to more extreme but balanced attitudes: Multidimensional attitudes and selective exposure[END_REF] proposed to represent attitudes as the sum of the evaluations of the object's features that can be seen as beliefs on the object, so as to take into account the cognitive aspect. While this model constitutes an interesting view on attitude formation, it has two limits with respect to our objectives.

First, the attitudes' values are not connected to the beliefs of each agent constituting their personal history. Indeed, their attitude revision mechanism is based on the bounded confidence model (e.g. [START_REF] Deffuant | Mixing beliefs among interacting agents[END_REF]): when two individuals have attitude values close to each other, agents converge their attitudes. However, it could be possible to combine this with Fazio's model of attitude [START_REF] Russell | Attitudes as object-evaluation associations of varying strength[END_REF]. This model connects the attitude to its forming beliefs as a set of memory associations. Each of these evaluations is weighted by an accessibility value determining the evaluation's degree of reminiscence. By essence, this model maintains a balance between the cognitive representation of the object and its corresponding attitude.

Second, the attitude model of Urbig and Malitz does not embody an emotional component, while social psychologists have defined the attitude as embodying rational and affective components [START_REF] Rosenberg | Cognitive, affective, and behavioral components of attitudes. Attitude organization and change: An analysis of consistency among attitude components[END_REF][START_REF] Russell | Attitudes as object-evaluation associations of varying strength[END_REF]. This is the reason why Brousmiche and al. [START_REF] Brousmiche | The role of emotions on communication and attitude dynamics: an agent-based approach[END_REF] attempted to combine Fazio's model with the Simplicity Theory proposed by Dessalles [START_REF] Dimulescu | Understanding narrative interest: Some evidence on the role of unexpectedness[END_REF]. However, their model does not consider (1) the aggregation of beliefs into a personal history as proposed by Fazio and (2) the notion of role responsibility impacting attitudes toward other actors than perpetrators of an action.

In this paper, we will take the model presented in [START_REF] Brousmiche | The role of emotions on communication and attitude dynamics: an agent-based approach[END_REF] as a starting point and extend it in order to take into account these two concepts by adding a mechanism of co-responsibility and modifying the aggregation method of the attitude computation.

Field data

Scenario In the course of the NATO intervention in Afghanistan to stabilize the country, the French Forces were tasked to maintain security in the regions of Kapisa and Surobi between 2008 and 2012. It is in this context that members of CIAE 5 were sent in the area from October 2010 to September 2012. As part of a more comprehensive maneuver, their actions were meant to complement conventional security operations by positively influencing the population and its key individuals through communication, reconstruction and humanitarian actions. Through a set of six interviews with all the successive officers in charge (3 colonels and 3 commanders) from the Joint Command for Human Terrain Actions, we managed to rebuild the sequence of the events that took place during their tenures, originating both from the NATO and from the Taliban insurgents. This sequence takes the shape of a scenario (see figure 1).

Each action is characterized by a reach, a frequency and a payoff: how many people were directly affected by the action, how many times per week if it is frequent, how each individual is impacted. These values were defined based on subjective assessments of domain's subject matter experts (including members of CIAE). For instance, we defined the action "patrol" as being triggered by the Blue Force, affecting the population with a positive impact of 30 and a reach of 20 people, repeated 3 times per week in average. Similarly, "IED" (Improvised Explosive Devices) are done by Red Forces and affect one individual with a payoff of -100. The number of victims of each attack were defined according to open source records (e.g. [START_REF] Ema | Ensemble vers l'autonomie[END_REF]).

We can observe that both Forces have a constant background activity toward the population composed of non-kinetic actions. However, the Red Force activity is heavily decreased during winter which corresponds to the second period on the scenario. One reason is that local Taliban leaders leave the region to avoid the arid climate. Also, the surveillance systems, including drones, are more effective in the absence of foliage, making it more difficult for insurgents to place discretely the IEDs. On the Blue Force side, the activity decreases constantly due to the political decision taken after the big human losses on the first period. Indeed, the French government began to adopt a "retreat" strategy after the suicide attack of Joybar (July 13th 2011) which caused considerable human casualties among the Blue Forces.

Opinion polls In order to follow the progress of population's sentiments and to link them to foreign Forces activities, the French Ministry of Defense financed opinion polls in Afghan regions where the French forces were operating. Those surveys were conducted by Afghan contractors between February 2011 and September 2012 with an interval of approximately 6 months issuing into four measure points P1, P2, P3 and P4 of the opinion of the population of Kapisa Polls dates P1 P2 P3 P4 "The Blue Force contributes to security" 40 32 24 19 "The Red Force is the principal vector of insecurity" 27 60 27 37 Fig. 2: % of the population favorable with two questions at different dates toward (1) the Blue Force and (2) the Red Force on the period corresponding to our scenario.

Opinions toward Red Force in the context of security decrease in summer periods. This could be explained by their high activity level as exposed in the previous section. As for the Blue Force, the global opinion value keeps decreasing along with their decreasing activities. In overall, the opinion dynamics showed by these polls results are consistent with the scenario previously established.

Model

General approach

Our model is based on the following principle: a simulation corresponds to the execution of actions (e.g. food distribution, construction of a bridge, bombing attack etc.) by actors (e.g. UN Force, terrorists or others) on a population. Individuals communicate about these actions with the others and form an attitude toward the actors.

In our model, we consider a set of actors A and a set of individuals Ind. Actors represent Forces that act in the simulation and for which we want to analyze the attitudes evolution. Each of them corresponds to a computational automaton executing its actions list specified by the above scenario. Each individual i ∈ Ind is represented by a computational agent and is characterized by its belief base recording facts he is aware of and his connections to other individuals. For each i ∈ Ind and actor ∈ A, we denote att(i, actor) ∈ R the attitude of the individual i toward the actor actor.

Beliefs about actions will be the core element in our model: attitudes and communications will be based on these beliefs. We note a(i) the belief of individual i about an action a. Each a(i) is a tuple: name(a), actor(a), coResp(a), bnf (a), payof f (a), date(a) with:

name the unique name of the action (e.g. "patrol", "suicide attack") actor ∈ A the actor who performed the action (Blue or Red Force) -coResp ∈ A the co-responsible actor of the action, if any (e.g. Blue Force will be co-responsible of "suicide attacks" performed by Red Force) bnf ∈ Ind ∪ A the beneficiary of the action, i.e. the individual or actor which undergoes the action payof f ∈ R the impact value of the action, negative when the action is harmful (e.g. attack) and positive when it is beneficial (e.g. food provision). date ∈ N the occurrence date of the action.

Attitudes are computed as the aggregation of evaluation of similar actions seized by the individual in his past. Two actions are similar if and only if they have the same name and actor. For instance, two distinct patrols done by the Blue Force in the same area are considered as similar. We call general action the meta action that includes similar actions. We denote ga(i, a) the general action corresponding to the action a according to the individual i and ga(i) the list of all general actions that i knows.

Actions can be perceived via direct perception (the agent is beneficiary of the action), actor's communication toward the population (the agent receives a message from the actors) or intra-population communication (the agent receives a message from another individual).

Attitude computation

When an agent receives a new information about an action a, it adds it to its belief base (if the action is not already present) and, possibly, communicates about it. Moreover, the agent revises its attitude toward the actor of the action. Our model of attitude construction is based on the model proposed by Fazio [START_REF] Russell | Attitudes as object-evaluation associations of varying strength[END_REF] (see section 2). In short, Fazio proposes to compute the attitude as the average of beliefs' evaluations (i.e. how much this fact is beneficial) weighted by their accessibilities (i.e. how accessible is the information in the subject's mind).

First we compute the interest of an information to estimate its accessibility and its narrative interest (whether or not to communicate the action to other agents). Second, we evaluate the action based on its payoff. Third, we compute the impact of co-responsibility, if required. Finally, we aggregate these evaluations, weighted by their accessibilities, to compute the attitude.

Interest of an action In order to determine what to base their attitude on and

what to communicate to other individuals, agents estimate a model of interest of the actions in their belief base. Following [START_REF] Brousmiche | The role of emotions on communication and attitude dynamics: an agent-based approach[END_REF], our model of interest is based on the Simplicity Theory of Dessalles [START_REF] Dimulescu | Understanding narrative interest: Some evidence on the role of unexpectedness[END_REF] which proposes to define the narrative interest N I of an information according to the emotion E and the surprise level S it causes to the individual using the following formula: N I(a) = 2 αE(a)+(1-α)S(a) where E corresponds to the personal emotional response intensity of the individual when faced to an information and the surprise level S translates the sentiment of unexpectedness felt by the individual. The parameter α ∈ [0, 1] balances these two parts.

The emotional intensity E corresponds to the emotional amplitude experienced by the individual when exposed to an event and follows a logarithmic law in conformity with Weber-Fechner's law of the stimuli. In our case, the stimuli corresponds to actions' payoff. A parameter of personal sensibility ξ ∈ [0, 1] modulates the response intensity.

The surprise S experienced by an individual when exposed to an event derives from a level of raw unexpectedness (e.g. "It is surprising that a Taliban saves a citizen"). This level is reduced by a personal reference of unexpectedness based on a personal experience (e.g. "But I have once been saved by a Taliban before").

While N I(a) corresponds to the narrative interest used as a communication heuristic, we also compute the information's interest corresponding to the accessibility of the information:

interest(a) = log(N I(a)) = αE(a) + (1 -α)S(a)
Action evaluation Fishbein and Ajzen [START_REF] Ajzen | The influence of attitudes on behavior[END_REF] advance that the evaluation of an action is weighted by the attitude toward its beneficiary. For instance, a beneficial action for my enemy is harmful for me. Therefore, we define the evaluation of an action belief as:

evaluation(a) = payof f (a) × att(i, bnf (a))
Co-responsibility In our case study, the Blue Force endorses the role of security guardian, thus they are co-responsible of all actions compromising the security of the population including Talibans' attacks from population's perspective. Thus, we introduce a co-responsibility mechanism that enables individual to attribute a fraction ρ ∈ [0, 1], parameter of the simulation, of an action payoff to the co-responsible. This mechanism occurs when an individual faces an action a in which (1) there is a co-responsible actor, (2) its impact is negative (i.e. there is no co-responsibility for beneficial actions) and (3) its evaluation is negative. In that specific case, the individual adds a belief a with actor(a) = coResp(a) and evaluation(a ) = ρ × evaluation(a).

Aggregation Let gaList(i, actor) be the list containing all the general actions performed by the actor in the belief base of agent i. The attitude att(i, actor) of the individual i toward the actor is given at each time of the simulation by:

att(i, actor) = ga(i)∈gaList(i,actor)   a(i)∈ga(i,a) evaluation(a) × interest(a, i)) |ga(i, a)|  

Experiments

In this section, we present the experimental results of our model. We aim to reproduce the results of opinion polls collected on the field using the established scenario of events that took place in Kapisa between September 2011 and September 2013. Since the polls did not asked directly the opinion toward the Red Force but "whether they represent a threat" (see section 3), we decided to take the opposite of these results as the target attitude values.

Simulation settings and initialization

We input the action sequence presented in the scenario of both Red and Blue Forces into the simulation scheduler; one tick corresponds to one day: the simulation covers the period between the first and last opinion polls in 554 ticks. The two agents corresponding to each Force will then operate their actions according to the scenario. The artificial population representing the inhabitants of Kapisa is composed of 150 agents connected by an interaction network based on a small-world topology [START_REF] Milgram | The small world problem[END_REF] with a degree of 4 (i.e. each individual has 4 neighbors in average).

Before running the actual simulation, we initialize the population with a personal history for each individual and an attitude corresponding to the value given by P1. Indeed, one of our model originality resides in the fact that the attitude depends on the agent's cognitive state characterized by its beliefs and accessibility values. Thus, we must give individuals an initialization belief with a certain reach and payoff for both attitudes toward Red and Blue Forces. These beliefs represent the interactions with Forces preceding to the simulation span. Another subtle point in our model is that individuals are surprised when they witness a totally new action, resulting in an overestimation of the action's impact. In order to habituate them to certain regular actions (such as patrols, preaches, radio broadcasts etc.) we need to run an initialization scenario before the actual one in which the population is confronted to these actions, until we reach a stable point (approximately 200 ticks).

Calibration method Once the simulation is properly initialized, we calibrate the model parameters using each opinion polls results as objectives. We have four points to calibrate per Force, thus totaling 8 points of calibration. The model parameters are shared among all individuals of the population:

α the weight of emotional sensibility toward the surprise factor ξ the level of sensibility to a stimuli (i.e. payoff) ρ the co-responsibility factor of Blue Forces for harmful Red actions We also have to determine the parameters of initialization actions to attain the first point P1: one positive and one negative action per Force. To do so, we fix their payoff values (negative for the harmful action and positive for the other) and calibrate their reaches.

We define our fitness function as the sum of differences' squares between each point of the opinion poll results and its corresponding percentage of favorable individuals in the simulation. We choose to minimize this fitness using the evolutionary algorithm CMA-ES that is one of the most powerful calibration method to solve this kind of problem [START_REF] Hansen | Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES)[END_REF]. Once the fitness stops progressing over 500 iterations, we interrupt the calibration process and save the parameters. Each calibration iteration is based on the average output on over 20 simulations replica since the model is stochastic.

Calibration results

The figure 3 shows the results of our model once its parameters have been calibrated. Plain curves represent the objectives to reach that are based on the collected opinion polls results (see section 3) ; dashed curves correspond to the simulation results, with α = 0.70, ξ = 0.08 and ρ = 0.15 (as obtained by the calibration).

We can observe that the attitude dynamics tendencies are well reproduced. The average difference between results and objective points is 13.25% with a maximum of 19% for the last point. This gap between survey and simulation results could be explained by several factors in addition to the model itself: field data are generally inaccurate and capture only a limited part of reality. Fig. 3: Simulation results compared to opinion polls First, the established scenario is based on subjective assessments of some Blue Force officers and do not capture all the military events that took place on the terrain. Adding to this, the parameters of action's models (i.e. payoffs, frequency and reach) have been assessed based on qualitative appraisal of subject matter experts since there is no scientific method to assess them.

Second, the sampling of the opinion survey could not be maintained through the survey process, due to the dynamics of the conflict : certain villages could not be accessed constantly over time due to their dangerousness. Moreover, as it was pointed earlier, the questionnaire did not directly ask the opinion toward Red Force which might increase the gap between our model outputs and the polls results.

Finally, our field data is limited to the context of military events. Even if our study concerns attitudes toward Forces in the military/security context, other events might also have influenced these attitudes such as economic or daily activities.

In view of these limitations, the reproduction of the general tendencies of attitude dynamics between each polls seems encouraging. Besides, these results have been obtained by calibrating only 3 model parameters.

Attitude Dynamics Agent based simulation enables not only to reproduce aggregated data but also to analyze micro behaviors. Figures 4 and5 below show the dynamics of population's attitudes means values between two polls along with their corresponding scenario.

The decreasing general tendency of the attitude toward the Red Force between P1 and P2 in figure 4 is due to the constant pressure activity that affects negatively the population. We can observe repercussions of each occurrence of action on the attitude dynamics. For instance, in figure 4 we can clearly see Fig. 4: Attitude mean toward Red Force between P1 and P2 Fig. 5: Attitude mean toward Blue Force between P3 and P4 attitude decreasing toward Red Force at each IED (Improvised Explosive Device, gray blocs in the figure) and also that the first occurrence has the greatest impact since the population is surprised. Besides, we can notice that the impact of a suicide attack is much greater than other actions (mid-July 2011 and June 2013).

In figure 5, we can see that attitudes toward the Blue Force are also impacted by each of its actions. Moreover, we can notice that the curve greatly decreases when the suicide attack perpetuated by Reds occurs. This phenomenon is enabled by the mechanism of co-responsibility (see 4.2), the Blue Force is also responsible of these attacks, in a moderate way. Similarly, the attitude toward Blue Force decreases constantly since the background communication actions and patrols are not enough to counter their co-responsibility toward the pressure activity for Reds.

Role of co-responsibility

To show the impact of the co-responsibility mechanism, we have performed a new simulation with ρ = 0 (i.e. no co-responsibility). Since the initial values of attitudes toward Blue Force depend on ρ during the initialization scenario, we had to re-calibrate the model parameters. Figure 6 shows the resulting attitude dynamics. As it was predictable, the attitude toward the Blue Force constantly increases as their only potentially negative actions (kinetic actions against the Red Force) are easily countered by communication toward the population or reconstruction actions. This is what was expected by the stakeholders when they decided to engage in Afghanistan.

The tendency of attitude toward Red Force remains the same since the coresponsibility only affects the Blue. We can notice that the simulated attitudes toward Reds is closer to opinion polls than in the first calibration. This is due to the fact that the red scenario is more simple (less action diversity).

Conclusion

We have collected information on the opinion dynamics and the events during the involvement of French army in Afghan war. These information were analyzed and processed with the support of subject matter experts. Based on these field observations, we proposed a simulation model of attitude dynamics. This model embodies both cognitive and affective components in the formation of attitude and the diffusion of beliefs. While it was designed in the context of military operations, it can be applied to civilian use: the actors can represent any kind of active social object such as political parties, institutions, companies or brands.

We also introduced a new concept of co-responsibility that reflects attitude behavior perceptible in conflict terrain. These components were aggregated through a new method that better understands the concept of attitude proposed by Fazio. We conducted a model calibration based on the collected data that showed encouraging results.

In future works, we intend to conduct deeper analysis of the field data to adapt the model and implement the simulation of different social groups that are present in this area. Moreover, we would like to implement a memory mechanism to let the agents "forget" some beliefs over time. This would be enabled for instance using the Peak-End mechanism of Kahneman [START_REF] Daniel Kahneman | Experienced utility and objective happiness: A moment-based approach[END_REF]. Furthermore, we would like to add a behavioral component to enable population agents to express their attitudes through actions selection.

Fig. 1 :

 1 Fig. 1: Scenario of Blue and Red Forces actions. The time points P1, • • • , P4 correspond to the dates of the opinion polls presented in the next section.

Fig. 6 :

 6 Fig. 6: Impact of co-responsibility

www.altaiconsulting.com

Joint Command for Human Terrain Actions: in charge of civil-military actions (e.g. reconstruction) and community outreach actions (i.e. attitude influence operations)