Elias Egho

Chedy Raïssi

Dino Ienco

Nicolas Jay

Amedeo Napoli

Pascal Poncelet

Catherine Quantin

Maguelonne Teisseire

Healthcare Trajectory Mining by Combining Multidimensional Component and Itemsets

Keywords: Sequential Patterns, Multi-dimensional Sequential Patterns, Data Mining

Sequential pattern mining is aimed at extracting correlations among temporal data. Many different methods were proposed to either enumerate sequences of set valued data (i.e., itemsets) or sequences containing multidimensional items. However, in real-world scenarios, data sequences are described as events of both multidimensional items and set valued information. These rich heterogeneous descriptions cannot be exploited by traditional approaches. For example, in healthcare domain, hospitalizations are defined as sequences of multi-dimensional attributes (e.g. Hospital or Diagnosis) associated with two sets, set of medical procedures (e.g. { Radiography, Appendectomy }) and set of medical drugs (e.g. { Aspirin, Paracetamol }) . In this paper we propose a new approach called MMISP (Mining Multidimensional Itemset Sequential Patterns) to extract patterns from a complex sequences including both dimensional items and itemsets. The novelties of the proposal lies in: (i) the way in which the data can be efficiently compressed; (ii) the ability to reuse and adopt sequential pattern mining algorithms and (iii) the extraction of new kind of patterns. We introduce as a case-study, experimented on real data aggregated from a regional healthcare system and we point out the usefulness of the extracted patterns. Additional experiments on synthetic data highlights the efficiency and scalability of our approach.

Introduction

Data warehouses are constituting a large source of data that can be used to extract information for expert analysis and decision makers [START_REF] Cohen | Online expansion of largescale data warehouses[END_REF]. In temporal data warehouses, every bit of information is associated with a timeline describing a total order over events. This total ordering introduces complexity in the extraction process. Many efficient approaches were developed to mine these patterns (i.e., sequential patterns) like PrefixSpan [START_REF] Pei | Prefixspan: Mining sequential patterns by prefixprojected growth[END_REF], SPADE [START_REF] Zaki | Spade: An efficient algorithm for mining frequent sequences[END_REF], ClosSpan [START_REF] Yan | Clospan: Mining closed sequential patterns in large datasets[END_REF],...etc. However, all these techniques and algorithms, without any exception, focus solely on sequences of set valued data (i.e., itemsets) and do not pay attention to realworld data that is described over multiple dimensions. To overcome this problem, Pinto et al. [START_REF] Pinto | Multi-dimensional sequential pattern mining[END_REF] introduced the notion of multi-dimensionality in sequences and proposed an efficient algorithm. Later works, like Zhang et al. [START_REF] Zhang | Approxmgmsp: A scalable method of mining approximate multidimensional sequential patterns on distributed system[END_REF] or Yu et al. [START_REF] Yu | Mining sequential patterns from multidimensional sequence data[END_REF] extended the initial Pinto's approach for different scenarios and use-cases. While in set valued approaches the events are represented by itemsets, in multidimensional temporal databases the events are defined over a fixed schema where all attributes appear in the extracted patterns. Furthermore, and this is particularly true in the data warehouse environment, background knowledge is usually available and can be represented as a hierarchy over the values of the attributes. Taking advantage of this observation, Plantevit et al. introduced M 3 SP [START_REF] Plantevit | Mining multidimensional and multilevel sequential patterns[END_REF], an efficient algorithm that is able to incorporate different dimensions and their taxonomies in the sequential pattern mining process. The benefit of this approach is to extract patterns with the most appropriate level of granularity. Still, this ideal representation of data is uncommon in real-world applications where heterogeneity is usually elevated to a foundational concept. In this study, we focus on extracting knowledge from medical data warehouse representing information about patients in different hospitals. The successive hospitalizations of a patient can be expressed as a sequence of multidimensional attributes associated with a set of medical procedures and a set of medical drugs. Our goal is to be able to extract patterns that express patients stays along with combinations of procedures over time. This type of pattern is very useful to healthcare professionals to better understand the global behavior of patients over time. Unfortunately this kind of complex data cannot be mined by any traditional sequential pattern approach. In this paper, we propose a new method to extract patterns from sequences which include multidimensional items and itemsets at the same time. In addition, the proposed approach incorporates background knowledge in the form of hierarchies over attributes. The remainder of this paper is organized as follows, Section 2 describes the existing work in the classical and multidimensional sequential patterns. Section 3 introduces the problem statement as well as a running example. The method for extracting multidimensional itemset frequent patterns is described in Section 4. Section 5 presents experimental results from both quantitative and qualitative point of views and Section 6 concludes the paper.

Related Work

Let I be a finite set of items. An itemset X is a non-empty subset of

I. A sequence S over I is an ordered list X 1 • • • X n , where X i (1 ≤ i ≤ n, n ∈ N) is an itemset. A sequence T = Y 1 • • • Y m is a subsequence of S = X 1 . . . X n , denoted by T S, if there exist indices 1 ≤ i 1 < i 2 < • • • < i m ≤ n such that Y j ⊆ X ij
for all j = 1 . . . m and m ≤ n. S is said to be a supersequence of T . Let S DB = {S 1 , S 2 . . . S n } be a database of sequences. The support of a sequence s in D is the proportion of sequences of D containing s. Given a minsup threshold, the problem of frequent sequential pattern mining consists in finding the set FS of sequences whose support is not less than minsup. Following the first work of Agrawal and Srikant [START_REF] Agrawal | Mining sequential patterns[END_REF] and the Apriori algorithm, many studies have contributed to the efficient mining of sequential patterns. The main algorithms are PrefixSpan [START_REF] Pei | Prefixspan: Mining sequential patterns by prefixprojected growth[END_REF], SPADE [START_REF] Zaki | Spade: An efficient algorithm for mining frequent sequences[END_REF], SPAM [START_REF] Ayres | Sequential pattern mining using a bitmap representation[END_REF], PSP [START_REF] Masseglia | The psp approach for mining sequential patterns[END_REF], DISC [START_REF] Chiu | An efficient algorithm for mining frequent sequences by a new strategy without support counting[END_REF], PAID [START_REF] Yang | Paid: Mining sequential patterns by passed item deduction in large databases[END_REF], FAST [START_REF] Salvemini | Fast sequence mining based on sparse id-lists[END_REF]. All of these algorithms aim to discover sequential patterns from a set of sequences of itemsets.

Usually, the information in a sequence is based on several dimensions. Pinto et al [START_REF] Pinto | Multi-dimensional sequential pattern mining[END_REF] propose the first work by including for mining multidimensional sequential patterns, by including dimensions in the first or the last itemset of the sequence. But this works only for dimensions that remain constant over time, such as gender of the patient. Among other proposals addressed in this area, Yu et al [START_REF] Yu | Mining sequential patterns from multidimensional sequence data[END_REF] consider multidimensional sequential pattern mining in the web domain.

Here, dimensions are pages, sessions and days. They present two algorithms: AprioriMD and PrefixMDSpan.

in real world applications, each dimension can be represented at different levels of granularity, by using a taxonomy. The interest lies in the capacity of extracting more or less general/specific sequential patterns and overcome problems of excessive granularity and low support. Although Srikant and Agrawal [START_REF] Srikant | Mining sequential patterns: Generalizations and performance improvements[END_REF] combined the use of hierarchy of values in the extraction of association rules and sequential patterns, their approach is not scalable in a multidimensional context. Han et al [START_REF] Han | Mining multiple-level association rules in large databases[END_REF] proposed a method for mining multiple level association rules in large databases. But their approach could not extract patterns containing items from different levels in the taxonomy. Appice et al [START_REF] Appice | Mining and Filtering Multilevel Spatial Association Rules with ARES[END_REF] proposed SPADA, an algorithm for discovering multi-level spatial association rules. Plantevit et al [START_REF] Plantevit | Mining multidimensional and multilevel sequential patterns[END_REF] proposed M 3 SP , an algorithm taking both multilevel and multidimensional aspects into account. M 3 SP is able to find sequential patterns with the most appropriate level of granularity. Egho et al [START_REF] Egho | A FCA-based analysis of sequential care trajectories[END_REF] proposed an extension for M 3 SP for extracting both general and specific sequences, they iteratively applied M 3 SP , decreasing threshold by one objects at each step. Their proposition allows the extraction of more interesting sequences than using a single minsup threshold.

Problem Statement

In this section we list some preliminary definitions needed to formalize the problem. First of all, we introduce a motivating example from a real data set related to the PMSI (Program of medical information systems). This French nationwide information system describes hospital activities from both economical and medical points of view. In this system, each hospitalization is related to the recording of administrative, demographical and medical data. Let S DB be a database of multidimensional itemsets data sequences. Figure 1 illustrates such a database.

Fig. 2. Hospital and diagnoses taxonomies

By taking into account the multidimensional items and the sets of items, we define an event as follows.

Definition 2. (Event) An event e = (d 1 , ..., d n , itemset n+1 , ..., itemset n+m ) is a vector of n multidimensional items and m sets of items where

d i ∈ D i , i = 1, • • • , n.
Given two events e = (d 1 , ..., d n , itemset n+1 , ..., itemset n+m ) and e = (d 1 , ..., d n , itemset n+1 , ..., itemset n+m ), e is more general than e , denoted by e ≤ e e, if and only if:

-∀ i ; 1 i n ; d i ∈ down(d i ). -∀ j ; 1 j m ; itemset n+j ⊆ itemset n+j . Example 2. e = (U H P aris , C 1 , {p 1 , p 2 , p 3 }, {drug 2 , drug 3 , drug 4 }) is an event, where:
-U H P aris , C 1 are two multidimensional items representing the two dimensions (hospital and diagnosis). -{p 1 , p 2 , p 3 }, {drug 2 , drug 3 , drug 4 } are two sets of items representing the medical procedures and the medical drugs.

The event e = (U H, T disease , {p 1 , p 2 }, {drug 2 , drug 3 }) is more general than e , e ≤ e e, because of:

-U H P aris ∈ down(U H) and C 1 ∈ down(T disease ).

-{p 1 , p 2 } ⊆ {p 1 , p 2 , p 3 } and {drug 3 , drug 4 } ⊆ {drug 2 , drug 3 , drug 4 }.

A multidimensional itemsets data sequence is composed of events.

Definition 3. (Multidimensional Itemsets Sequence) A multidimensional itemsets sequence s =< e 1 , e 2 , ..., e l > is an ordered list of events e i . Given two multidimensional itemsets sequences s =< e 1 , e 2 , ..., e l > and s =< e 1 , e 2 , ..., e l >, s is more general than s , denoted by s ≤ s s , if there exist indices 1 ≤ i 1 < i 2 < ... < i l ≤ l such that e j ≤ e e ij for all j = 1 . . . l and l l .

Example 3. The multidimensional itemsets sequence s = (U

H P aris , C 1 , {p 1 , p 2 }, {drug 1 , drug 2 , drug 3 }), (GH Lyon , R 1 , {p 2 }, {drug 2 , drug 4 }
) is a sequence of two events. It expresses the fact that a patient was admitted to the University Hospital of Paris U H P aris for a lung cancer C 1 , underwent procedures p 1 and p 2 and was treated with {drug 1 , drug 2 , drug 3 }, then he went to the General Hospital of Lyon GH Lyon for pneumonitis R 1 where he underwent procedure p 2 and received {drug 2 , drug 4 } .

The sequence s = (U H P aris , Cancer, Example 4. In Table 1, the multidimensional itemsets sequence s = (U

{p 1 }, {drug 1 , drug 2 }) is more gen- eral than s, s ≤ s s , because (U H P aris , C 1 , {p 1 , p 2 }, {drug 1 , drug 2 , drug 3 }) ≤ e (U H P aris , Cancer, {p 1 }, {drug 1 , drug 2 }).
H P aris , C 1 , {p 1 , p 2 }, {drug 1 , drug 2 }), (U H P aris , C 1 , {p 1 }, {drug 2 }), (GH Lyon , R 1 , {p 2 } , {drug 2
}) represents the trajectory for the patient P 1 .

Let supp(s) be the number of sequences that includes s in S DB . Furthermore σ be a minimum support threshold specified by the end-user. Definition 5. (Most Specific Frequent Multidimensional Itemsets Sequence) Let s be multidimensional itemsets sequence, we say that s is the most specific frequent multidimensional itemsets sequence in S DB , if and only if: supp(s) ≥ σ and s ∈ S DB , where supp(s) = supp(s ) and s ≤ s s .

The problem of mining multidimensional itemsets sequences is to extract the set of all most specific frequent multidimensional itemsets sequence in S DB such as supp(s) ≥ σ. By using the dimensions we can extract general or specific patterns and overcome problems of excessive granularities and low supports.

Example 5. Let σ = 0.75 (i.e. a sequence is frequent if it appears at least three times in S DB ). The sequence

s 1 = (U H P aris , C 1 , {p 1 , p 2 }, {drug 1 , drug 2 }), (GH Lyon , R 1 , {p 2 }, {drug 2 }) is frequent. s 2 = (U H, Cancer, {p 1 , p 2 } , {drug 1 , drug 2 }), (GH, Respiratory, {p 2 }, {drug 2 }) is also frequent. Nevertheless, s 2 is not kept since it is too general compared to s 1 .
In this section, we present the MMISP (Mining Multidimensional Itemsets Sequential Patterns) algorithm for extracting multidimensional itemsets sequential patterns with different levels of granularity over each dimension. MMISP follows a bottom-up approach by first focusing on extracting frequent multidimensional items that can exist at different level of granularity, then it considers the itemsets part of the events and compute the support of every item is S DB for each itemset. After these two steps, frequent multidimensional items and frequent itemsets are combined to generate events. In the final step, the frequent events are mapped to a new representation and a standard sequential mining algorithm is applied to enumerate multidimensional itemsets sequential patterns.

In the next subections, we provide the details of each step of our work and discuss the different challenges.

Generating frequent multidimensional items

MMISP starts by processing the n multidimensional items of the events in the sequences. Basically it considers three types of dimensions: a temporal dimension D t , a set of analysis dimension D A and a set of reference dimension D R . MMISP splits S DB into blocks according to dimension D R . Then, MMISP sorts each block according to the temporal dimension D t . This is a classic way of partitioning the database and was introduced in [START_REF] Plantevit | Mining multidimensional and multilevel sequential patterns[END_REF]. The tuples of n multidimensional items appearing in an event are defined w.r.t. analysis dimensions D A . The support of n multidimensional items is computed according to dimension of D R . It is the ratio of the number of blocks supporting the n multidimensional items over the total number of blocks. To simplify our works we will represent the n multidimensional items of the event as follows: The first steps in MMISP is generation all the frequent multidimensional components. This generation is given by the product of all partially ordered sets of the dimensions. The result of this product is a semilattice which has a top element (T 1 , ..., T m ) and each node in this semilattice is a multidimensional component. Extracting only the frequent multidimensional components can be done by choosing minsup and building the iceberg semi-lattice. The iceberg semilattice is a semi-lattice where its elements have a support greater than minsup. Figure 4 shows iceberg semi-lattice generated by the product of the two partially ordered sets (hospital and diagnosis) in Figure 2 Handling the product of several partial order sets is a cumbersome process. The result of a product is exponential in the number of partial order sets and the cardinality of each set. So, we present a simple and efficient algorithm to generate all frequent multidimensional components.

Following the previous partitioning, algorithm generates all the frequent multidimensional components as follows: firstly, we generate the most general multidimensional component, that is (T 1 , ..., T n ). In our running example, we have two dimensions (hospital and disease), so the most general multidimensional component is (T hospital , T disease ). Then, the algorithm generates all multidimensional components of the form (T 1 , ...T i-1 , d i , T i+1 , ..., T n ) where d i ∈ down(T i ). We take only the frequent multidimensional component which has support greater than σ. In the running example and for σ = 75% (3 blocks from 4), there are four new frequent multidimensional components: (U H, T disease ), (GH, T disease ), (T hospital , Respiratory) and (T hospital , Cancer).

The recursive generation of the new multidimensional components continues by using each previously generated frequent multidimensional component (a). This is done with an indexing method that identifies an integer z which is the position of the last dimension in a and is not top T . For example if a=(U H, T Disease ), z is equal to one, which is the first dimension (hospital) because the value for the hospital dimension (UH) and the second dimension (disease) has the value T disease .

For each dimension d k in a, where k ∈ [z, m], we replace d k with each of its specialization from the set down(d k ). For example, if a=(U H, T Disease ), we have z =1 and we can generate four new mdc s : {(U H P aris , T Disease ), (U H N ancy , T Disease ), (U H, Respiratory), (U H, Cancer)}. The first and the second multidimensional components are generated by replacing U H by down(U H) = {U H P aris , U H N ancy }, the third and the forth multidimensional components are generated by replacing T Disease by down(T Disease ) = {Respiratory, Cancer}.

At each step, we select only the frequent multidimensional components. For our previously example with σ = 75%, {(U H P aris , T Disease ), (U H, Cancer)} are the new frequent multidimensional components generated by (U H, T Disease ).

Finally, from all frequent multidimensional components generated, we select only the most specific multidimensional component. Table 1. The most specific frequent multidimensional components Example 8. Figure 5 illustrates the generation of all frequent multidimensional components on the running example with σ = 3 4 . The most specific components are (U H P aris ,C 1 ) and (GH Lyon ,R 1 ).

Generating Frequent Itemsets

In this step, MMISP focuses on m itemsets part of the events, (d 1 , ..., d n , itemset n+1 , ..., itemset n+m ). We will study separately each itemset in this part. Basically,

Frequent multidimensional Component

The most specific frequent multidimensional Component Support Fig. 5. Frequent multidimensional components generation this step aims at extracting the set of all items that are frequent in a sequence of length 1. Recall that, in level-wise approaches, either itemset-extension or sequence-extension can be considered. For example, if we have a sequence s 1 = {1, 2, 3} , then s 2 = {1, 2, 3}{4} is an extended sequence of s 1 and s 3 = {1, 2, 3, 4} is an itemset-extended sequence of s 1 . In our context we only consider itemset-extension. This task can be easily done by adapting any standard sequential pattern algorithm to extract only the sequence of length 1. Frequent medical drugs candidates Fig. 6. The frequent itemset generated Example 9. Figure 6 shows the sequences of medical procedures and medical drugs for patients, and also the frequent medical procedures and medical drugs candidates for σ = 3 4 .

Generating Frequent Events

Generating frequent events is achieved by combining frequent multidimensional components with frequent itemsets. This task has be done by building a prefix tree such that the first level in this tree is composed of the frequent multidimensional components and from the second level to leafs, each level is composed the frequent itemset candidates for each itemset part in the vector of itemsets. More precisely, each branch in the tree represents an event. Then a scan is performed over the database to prune irrelevant events from the tree. For example, Figure 7 illustrates the tree before and after pruning infrequent events for σ = 3 4 .

(UH Paris , C 1 )

(GH Lyon , R 1 ) Support T {p 1 } {p 2 } {p 1, p 2 } {drug 1 } {drug 2 } {drug 1, drug 2 } {drug 1 } {drug 2 } {drug 1, drug 2 } {drug 1 } {drug 2 } {drug 1, drug 2 } {p 1 } {p 2 } {p 1, p 2 } {drug 1 } {drug 2 } {drug 1, drug 2 } {drug 1 } {drug 2 } {drug 1, drug 2 } {drug 1 } {drug 2 } {drug 1, drug 2 } 3 3 3 3 4 3 3 3 3 0 0 0 0 3 0 0 0 0
Combination tree before pruning

(UH Paris , C 1 ) (GH Lyon , R 1 )
T

{p 1 } {p 2 } {p 1, p 2 } {drug 1 } {drug 2 } {drug 1, drug 2 } {drug 1 } {drug 2 } {drug 1, drug 2 } {drug 1 } {drug 2 } {drug 1, drug 2 } {p 2 } {drug 2 } 3 3 3 3 4 3 3 3 3 3
event Combination tree after pruning Fig. 7. An example of the tree for generating frequent events before and after the pruning

Extracting frequent multidimensional itemsets pattern

Frequent sequences can then be mined by using any standard sequential pattern mining algorithm. As these algorithms require that the dataset to be mined is composed of pairs in the form (id, seq), where id is a sequence identifier and seq is a sequence of itemsets, we transform the initial dataset as follows:

-Each branch in the prefix tree after pruning is assigned a unique id which will be used during the mining operation. This is illustrated in Table 2 . -Each block (patient) is assigned a unique id of the form P i .

-Every block b is transformed into a pair (P i , S(p i )), where S(P i ) is built according to the date and the content of the blocks. The final result is reported in Table 3.

A standard sequence mining algorithm can be applied on the transformed database.

Then, the extraction of frequent sequences can be carried out. With σ = 0.75, the pattern {e 9 }{e 10 } is frequent. This sequence corresponds to (U H P aris , C

Experiments

We conduct experiments on both real and synthetic datasets. The algorithm is implemented in Java and the experiments are carried out on a MacBook Pro with a 2.5GHz Intel Core i5, 4GB of RAM Memory running OS X 10.6.8. The extraction of sequential patterns is based on the public implementation of CloSpan algorithm [START_REF] Yan | Clospan: Mining closed sequential patterns in large datasets[END_REF]. We use the implementation supplied by the IlliMine6 toolkit.

In order to assess the effectiveness of our approach, we run several experiments on the PMSI dataset. This database includes the following informations for each stay: patient id and gender, hospital id, principal diagnosis and date of the stay, a set of associated diagnosis and a set of medical procedures. Our dataset contains 486 patients suffering from lung cancer and living in the East of France. The average length of data sequences is 27. The data is encoded using controlled vocabularies. In particular, diagnoses are encoded with the International Classification of Diseases (ICD10) 7 . This classification is used as an input taxonomy for MMISP. The ICD10 can be seen as a tree with two levels. As illustrated in Figure 8, 3-characters codes such as C34 (Lung cancer) have specializations: C340 is cancer of the main bronchus, C341 is cancer of upper lobe etc. Figure 9 shows an example of care trajectories described over two dimensions (diagnosis, hospital ID) coupled with two sets of medical procedures and associ- The experiments extract multidimensional sequential patterns for describing and analyzing patient trajectories. For this experiment the support value is set to 15 (i.e. σ = 0.03). MMISP generates 156 different frequent trajectories. Figure 10 shows some results of the experiment. Pattern 2 can be interpreted as follows: 40% of patients had a hospitalization in the University Hospital of Dijon (750712184) for any diagnosis (ALL), where they underwent a chest radiography (coded as ZBQK002) and an Electrocardiography (coded as DEQP003), with supplementary billing (coded as YYYY030); they had a malignant tumor of the lung as associated diagnosis. Then, the same patients had another stay for acute respiratory failure (J960), and they underwent tests with supplementary billing (coded as YYYY030). This second stay could occur in any hospital (ALL) and had the same associated diagnosis(C349). In the second experiment, we study the scalability of the approach. We consider the number of extracted patterns and the running time with respect to two different parameters, the number of dimensions and the average length of itemsets in the event. The first batch of synthetic data generated contains 10000 sequences defined over (2, 3, 4 and 5) analysis dimensions. Each sequence contains 30 events and each event is described, in average, by 15 items in the itemset. Each dimension is defined over 5 levels of granularity between elements of each Another experiment is aimed at comparing the performance of MMISP with M 3 SP on a synthetic dataset. In comparison we consider both the number of extracted patterns and the running time. The synthetic data generated contains 10000 sequences defined over two dimensions with one itemsets described by 5 items. Figure 13 reports the results according to different values of support threshold for both M 3 SP and MMISP. MMISP is able to extract less patterns than M 3 SP while from the point of view of time execution the two approaches show comparable performances. The reduced size of the MMISP results is related to its ability in extracting a multidimensional itemsets sequential patterns.

Conclusion

In this paper, we propose a new approach to mine multidimensional itemset sequential patterns. Our approach is based on multidimensional items and the set of items. We provide formal definitions and propose a new algorithm MMISP to mine this new kind of pattern. We conduct experiments on both real and synthetic datasets. The method was applied on real-world data where the problem was to mine healthcare patients trajectories and gave potential interesting patterns for healthcare specialists.

Definition 4 .

 4 (Patient Trajectory) A patient trajectory is defined as a multidimensional itemsets sequence.

Fig. 3 . 6 .

 36 Fig. 3. Block partition of the database according to DR={Patient}

Definition 6 .

 6 (multidimensional component) Given a dimension (D, ), a multidimensional component over D, denoted (mdc, mdc ), is a tuple (d 1 , ..., d n ) where d i ∈ D, i = 1, • • • , n. For two given multidimensional components mdc = (d 1 , ..., d n ) and mdc = (d 1 , ..., d n ), mdc mdc mdc denotes that mdc is more general than mdc , if for every i = 1, ..., n, d i ∈ down(d i ). Example 7. Let (U H P aris , Lung Cancer) and (U H, Cancer) be two multidimensional components. (U H P aris , Lung Cancer) mdc (UH, Cancer) because U H P aris ∈ down(U H) and Lung Cancer ∈down( Cancer).

Fig. 4 .

 4 Fig. 4. Iceberg semilattice generated by the product of the two partially ordered sets (hospital and diagnosis) in Figure 2 with minsup= 3 4 patient

Definition 7 .

 7 (Most specific multidimensional component) Let a be multidimensional component, we can say that, a is the most specific multidimensional component, if and only if a multidimensional component, where supp(a) = supp(a ) and a mdc a. Frequent multidimensional component (U H P aris ,C1) (GH Lyon ,R1)

Fig. 10 .

 10 Fig. 10. Some healthcare patients trajectories obtained by MMISP

Fig. 11 .Fig. 12 .

 1112 Fig. 11. Running Time (left) and Number of extracted pattern (right) obtained by MMISP with varying in the number of dimension

Fig. 13 .

 13 Fig. 13. Running Time (left) and Number of extracted pattern (right) obtained by MMISP and M 3 SP over the synthetic dataset

  H P aris , C 1 , {p 1 , p 2 }, {drug 1 , drug 2 }), (U H P aris , C 1 , {p 1 }, {drug 2 }), (GH Lyon , R 1 , {p 2 }, {drug 2 }) P 2 (U H P aris , C 1 , {p 1 }, {drug 2 }), (U H P aris , C 1 , {p 1 , p 2 }, {drug 1 , drug 2 }), (GH Lyon , R 1 , {p 2 }, {drug 2 }) P 3 (U H P aris , C 1 , {p 1 , p 2 }, {drug 1 , drug 2 , drug 3 }), (GH Lyon , R 1 , {p 2 }, {drug 2 , drug 4 }) P 4 (U H P aris , C 1 , {p 2 }, {drug 1 , drug 2 }), (U H P aris , R 2 , {p 3 }, {drug 2 }), (GH Lyon , R 2 , {p 2 }, {drug 3 }) D hospital = {T hospital , U H, GH, U H P aris , U H N ancy , GH P aris , GH Lyon } and U H P aris ∈ down(U H) as U H P aris is a direct descendant of U H.

	Patients					Trajectories
	P 1	(U Fig. 1. An example of a database of patient trajectories
	Definition 1. (Dimensions and specialization down(d)) A dimension (D, ) is
	a partially ordered set where D is the set of all items of dimension. For a given
	d ∈ D, down(d) (resp. up(d)) denotes the set of all specializations {x ∈ D|x d}
	(resp. generalizations {x ∈ D|d x}) of d.
	Example 1. Figure 2 shows two dimensions (hospital and diagnosis). For hospi-
	tal dimension, University Hospital (UH) General Hospital (GH) T hospital	Respiratory	T disease	Cancer
	UH Paris	UH Nancy	GH Paris	GH Lyon	Pneumoni;s (R 1 )	Asthma (R 2 )	Lung Cancer (C 1 )	Breast Cancer (C 2 )
		Hospitals				Diseases

  with minsup= 3 4 patients.

				(T hospital, T disease )
	(UH , T disease )	(T hospital ,Cancer)	(GH , T disease )	(T hospital ,Respiratory)
	(UH Paris, T disease )	(UH , Cancer)	(T hospital ,C 1 )	(GH Lyon, T disease )	(GH , Respiratory)	(T hospital ,R 1 )
	(UH Paris, Cancer)	(UH , C 1 )	(GH Lyon, Respiratory)	(GH , R 1 )
		(UH Paris, C 1 )			(GH Lyon, R 1 )

Table 2 .

 2 Identification each branch (Event) in T

	id	Sequence data
	P1 {e1, e2, e3, e4, e5, e6, e7, e8, e9}{e2}{e10}
	P2 {e2}{e1, e2, e3, e4, e5, e6, e7, e8, e9}{e10}
	P3	{e1, e2, e3, e4, e5, e6, e7, e8, e9}{e10}
	P4	{e5}

Table 3 .

 3 Transformed database {p 1 , p 2 }, {drug 1 , drug 2 }), (GH Lyon , R 1 , {p 2 }, {drug2}) by using the identification in Table2.

http://illimine.cs.uiuc.edu/

http://apps.who.int/classifications/apps/icd/icd10online/


Carine Heitz
email: carine.heitz@irstea.fr

Géraldine Flinois
email: geraldine.flinois@hotmail.fr

Sandrine Glatron
email: sandrine.glatron@live-cnrs.unistra.fr

Protection against muddy floods: perception for local actors in Alsace (France) of a protection measure (fascines)

Keywords: Risk mitigation, Perception, Surveys, Natural disasters

For several years, an increase of muddy floods frequency (and associated damages) is noticed in the Alsacian region (NE of France). In 2008, the regional authority ("Conseil Général") with the collaboration of the Chamber of Agriculture decided to set up, directly on farmlands, micro-structures called "fascines" (faggots of brushwood). These little protection systems allow to decrease the muddy floods velocity and to capture the sediments that are transported decreasing by this way the vulnerability in risk prone areas located downstream the catchment. These protections present two advantages: they are very easy and cheap to set up. In the region, we can list 400 fascines, step up in 21 municipalities exposed to the muddy floods risk.

This study focuses on farmers' perception of these fascines in order to understand their potential acceptability of this kind of mitigation measure and to highly the main issues linked to the democratization of these protective measures in the whole risk prone areas. The methodology used is a questionnaires (N=37) held among farmers in 5 municipalities exposed to muddy floods risk. The main results show that the fascines are perceived as a restrictive tool: the most of the farmers mentioned that their maintenance is more important than for other mitigation measures such as hedges, non-inversion tillage, grass strips,.... also proposed in the questionnaire. Moreover the "real" efficiency of the fascines against the muddy floods propagation is questioned by the farmers as well as their integration in the landscape. Among others, these results allow to highly the main restraints in the development of such mitigation measures and have been directly used by the Chamber of Agriculture in order to improve their information campaigns among the farmers to improve the use of the fascines in risk mitigation polices and risk prone areas planning.

INTRODUCTION

The Alsatian region is frequently concerned by runoff and soil erosion processes [START_REF] References | Étude des états de surface du sol et de leur dynamique pour différentes pratiques de travail du sol[END_REF], Le Bissonnais et al., 2002a): between 1982and 2005, 225 municipalities were concerned at least once (Auzet et al., 2005a[START_REF] Heitz | Etude de la perception du risque de catastrophes naturelles relatif aux coulées de boue par les acteurs de communes périurbaines. Approche méthodologique et analyse d'enquêtes[END_REF]. Due to the high number of associated damages, their management becomes a priority for public authorities in charge of the environmental issues, the farmers, the scientists, … For instance, in the Bas-Rhin department, the muddy floods risk management is conducted in partnership with public authorities and the Chamber of Agriculture. Among all the measures of protection, we can distinguish two kinds of measures, intervening at different levels of costs and scales:

1. the collective measures which are set up on the public area. Their setting up requires important investments. We can quote the setting up of dams, the road networks and urban areas plannings; 2. the individual measures, which concern the private domain and which require less investments. They include measures such as individual measures of protection, measures setting-up in the fields (fascines, grass straps, …).

We focus your study on these second types of measures and more precisely on the fascines. These measures of protection are directly set up in the fields, the agreement of the farmers is then required. It is important to inform them about the consequences of soil erosion and runoff, and especially to inform them about the usefulness of protective measures to decrease the vulnerability of the municipalities located downstream the catchment. Our question is by now: What kinds of perceptions have the farmers of the fascines, a few years after their setting-up? Our study follows two main objectives: 1. To identify the farmers' needs and the limits in the setting-up of fascines 2. To supply knowledge favoring the future setting-up of such measures.

To answer to these objectives, we conduct questionnaires among the farmers located in five municipalities frequently concerned by muddy floods.

MUDDY FLOODS: PROCESSES AND EXISTING MEASURES OF PROTECTION

The risk of muddy floods results from the conjunction of diverse factors. [START_REF] Boardman | Soil erosion science: Reflections on the limitations of current approaches[END_REF] consider this phenomenon as a "complex system" integrating a variety of physical and human aspects.

Physical processes and definition of the muddy floods

The muddy floods correspond to fluid flows with suspended loads (Auzet et al., 2005b). The superficial horizons of the soils are removed (under the effect of rains and/or of runoff) using gullies ploughed in the fields [START_REF] Auzet | L'érosion des sols par l'eau dans les régions de grande culture : aspects agronomiques[END_REF][START_REF] Le Bissonnais | L'érosion hydrique des sols en France[END_REF]. This definition shows that the muddy floods result from the conjunction of runoff and soil erosion processes. In Alsace, the presence of silty soils increases the risk of soil erosion (and muddy floods): silty material presents a very fine texture and confers it a weak structural stability. Moreover, in Alsace during springtime, soils are not covered by the crops (maize) and heavy rainfalls are registred (90-100 mm for the periods of May-June were registered in the south of Alsace -Van Dijk et al., 2005). Soil sealing is also formed by the drops' impacts and it will stop the water infiltration and favour the runoff processes [START_REF] Kinnell | Raindrop-impact-induced erosion processes and prediction: A review[END_REF].

Protective measures to decrease runoff and soil erosion

In the upstream catchment, the damages concern mainly the farmers. In the downstream catchment, they concern the inhabitants and the infrastructures (with damages on public equipment, roads, etc.). The measures of protection are various (Le Bissonnais et al., 2002a[START_REF] Auzet | L'érosion des sols par l'eau dans les régions de grande culture : aspects aménagements[END_REF][START_REF] Evrard | Muddy floods in the Belgian loess belt: Problems and solutions[END_REF] and can concern:

-the agronomic practices (reduced tillage practices, different cover crops, banks, grass strips, hedges, fascines, etc) -the hydraulics measures (dams, ponds) -financial support to change farmers' behaviors and agricultural practices.

METHODOLOGY OF THE QUESTIONNAIRES

The creation of a questionnaire requires following a precise methodology allowing us to answer to the questions: "What? Who? Where? When? How?" [START_REF] Cauvin | Propositions pour une approche de la cognition spatiale intra-urbaine[END_REF][START_REF] De Singly | L'enquête et ses méthodes[END_REF]. The precise methodology of this survey is available in Flinois (2011).

Definition of the main issues related to protective measures to create the questionnaire

The questionnaire was created after interviews with farmers and risk managers, allowing us to identify the main issues linked to muddy floods risk and their management. These issues concern mainly:

the setting up of fascines; -their cost; -their integration in the landscape; -their care and maintenance; -their efficiency against muddy floods; -their place among other protective measures.

The studied areas

We sample our population of farmers in five municipalities (Bas-Rhin department): Hohatzenheim, Brumath, Ettendorf, Eckwersheim and Lampertheim. All of the farmers have in common to have been damaged by muddy floods and to have set up fascines to protect the inhabitants and infrastructures located downstream the catchment. These five municipalities were also chosen because physical data, economic analyses and modelisations are available: comparisons and cross analyses can then be done.

The methodology used for the sampling plan and for the questionnaire administration

As the fascines are set up directly in the fields, we decide to sample all the farmers of the five municipalities (if they have set up fascines or not). By this way, we can identify the main issues taken into account by the farmers, when they accept to implement fascines, or when they refuse. We decide to be exhaustive: that means that we seek all the farmers of our municipalities (41 farmers).

We first contact them by phone: this phone-call allows us to explain our study and if they agree to participate to it, to decide an appointment for the questionnaire administration (face to face questionnaire). This method allows us to reduce the unwillingness to participate (5 refusals on 41 farmers). We met the farmers between April and May 2011 and 32 farmers have accepted to answer to our questionnaire.

RESULTS

All the farmers use conventional agricultural practices (ploughing):

-75 % use conventional practices, -21,9 % associate ploughing and reduce tillage, -3,1 % are involved in organic farming. 72% of the farmers are cereals farmers and 28 % have a breeding farm. Furthermore, on our five municipalities, the farms are relatively small with an average size lower than 40 ha.

How farmers assess them their level of threat?

All the farmers feel exposed to muddy floods risk. For cause, they were damaged at least once by muddy floods (fig 1). The main consequences were the loss of plants (quoted by 75 % of the farmers), additional work after the muddy flood and the loss of fertile soil (quoted by 34 % of the farmers) as well as the formation of gullies (for 31 % of them). To value the perceived level of exposure to muddy floods risks of the farmers, we asked them to mark a line on an scale limited by the signs " -" and " + ". This scale is a 10 centimetres axis and the signs " -" and " + " correspond to the "values" 0 and 10. By measuring the position of the line, it is possible to assess their perception of their exposure to muddy floods risks. The results highlight that the farmers located in Ettendorf feel to be highly exposed to muddy floods. They mark their level of exposure around 6.3/10 (Fig 2). It is not really surprising: the municipality was already concerned 5 times by this kind of disaster

It is interesting to compare this result with the other municipalities, in which the farmers feel less exposed while some of the municipalities are also frequently concerned (for instance, Eckwersheim -5 times). Other municipalities are even more frequently affected: Lampertheim and Brumath damaged respectively 6 and 7 times by muddy floods. In these two municipalities the farmers assess their level of exposure at 3.8/10 and 4.5/10 (mean).

The farmers of Hohatzenheim (two muddy floods events) seem to highly estimate their level of exposure at the risk, compared with the results observed in the other municipalities (mean perceived exposure = 5.3/10). These various results on the farmers' perceived level of exposure to muddy floods risk express the subjectivity of the perception of risk. The number of events seems not to be the single factor for explaining the level of perception.

Main factors that improve the setting up of fascines

For farmers, fascines are considered as "solutions of emergency". The inhabitants put the pressure on them: they are accused to be responsible of the formation of muddy floods. The farmers want to react quickly and setting up fascines seems to be an adequate solution. Fascines are visible and their efficiency is quasi immediate. According to the farmers, fascines seem to reassure the inhabitants. We ask the farmers to explain us what kind of feelings the inhabitants have towards the fascines. The results show that:

-34,4 % of the farmers highlight the fact that fascines are visible: "…That shows that the farmers made something, that they get involved", "… They see that the fascines will protect them". -31.3 % of the farmers think that the inhabitants trust the efficiency of thes protective measures and feel reassured by their installation: "… They are satisfied", "They feel protected". -31.3 % of them think that the inhabitants remain sceptical: "It is efficient but it is expensive", "They wonder about the functioning and the maintenance of the fascines". -3.1 % of the farmers think that the inhabitants have a negative feeling: "The Greens of the village said that it is not a good thing", "It is just an illusion".

These results show that the farmers identify positive aspects of the fascines: they are easy and fast to set up and the inhabitants see that the farmers undertake actions to protect them. It is possible that farmers agreed to settle fascines in their fields for these reasons.

CONCLUSIONS

The questionnaires allowed us to determine factors taken into account by the farmers in their willingness to set up fascines in their fields. Before anything else, the survey reveals that the great majority of them adopted this measure in an emergency context, following the catastrophic muddy floods of May, 2008. The fascines appeared as a fast solution to set up and whose effects were immediate. The negative aspects mainly concern the cost, the integration in the landscape and the maintenance of the fascines. A part of the farmers think that the fascines are temporary measures and they seem to be more willing to adopt more sustainable actions such as reduced tillage practices.

Another point highlighted by the survey is the lack of information concerning the care and maintenance of the fascines. In the Bas-Rhin, nobody is in charge of the care and maintenance of the fascines. In other French department (for instance, Nord-Pas-de-Calais), public authorities and Chamber of agriculture establish a convention with the farmers. They define together the responsibility of each stakeholder in the setting up and the maintenance of the fascines. It could be useful to allow the sustainability of this protective measure to specify this issue in the Bas-Rhin department.

Fig 1 .

 1 Fig 1. "How many times have you been affected by muddy floods?" (N=32)

Fig 2 .

 2 Fig 2. Perceived level of exposure in the 5 municipalities (mean)


Ilaria Brunetti
email: ilaria.brunetti@inria.fr

Eitan Altman
email: eitan.altman@inria.fr

Revisiting Evolutionary Game Theory *

Evolutionary game theory is a relatively young mathematical theory that aims to formalize in mathematical terms evolution models in biology. In recent years this paradigm has penetrated more and more into other areas such as the linguistics, economics and engineering. The current theory of evolutionary game makes an implicit assumption that the evolution is driven by selfishness of individuals who interact with each others. In mathematical terms this can be stated as "an individual equals a player in a game model". This assumption turns out to be quite restrictive in modeling evolution in biology. It is now more and more accepted among biologist that the evolution is driven by the selfish interests of large groups of individuals; a group may correspond for example to a whole beehive or to an ants' nest.

In this paper we propose an alternative paradigm for modeling evolution where a player does not necessarily represent an interacting individual but a whole class of such individuals.

I. INTRODUCTION

Evolutionary game theory (EGT) started as a theory that intended to explain and predict quantitative and qualitative aspects of evolution in biology by using the powerful tools of game theory [START_REF] Weibull | Evolutionary Game Theory[END_REF]. It focused on pairwise interactions, assuming selfishness of individuals who interact. Strategies are interpreted as inheritable traits and payoff as Darwinian fitness. Standard EGT has some modeling weaknesses since it identifies each individual which interacts with an individual as a selfish player.

We found several examples that put this model in question:

• in some species like bees or ants, the one who interacts is not the one who reproduces. This implies that the Darwinian fitness is related to the entire swarm and not to a single bee. • In many species, we find altruistic behaviors, which may hurt the individual adopting it, favoring instead the group he belongs to. Altruistic behaviors are typical of parents toward their children: they may incubate them, feed them or protect them from predators at a high cost for themselves. Another example can be found in flock of birds: when a bird sees a predator it gives an "alarm call" to warn the rest of the flock, attracting the predator's attention to itself. Also the stringing behavior of bees is an altruistic one: it serves to protect the hive, but it's lethal for the bees which strives.

• In engineering applications: in wireless communication, power control games have frequently been studied in the framework of standard EGT. Papers that consider these games always assume that each mobile can control selfishly its power. In practice however the protocols for power control are not determined by the users of the terminal but by the equipment constructors; with us argues that the real competition is among a final number of equipment constructors. In this paper we present a new model for evolutionary games, in which the concept of the player as a single individual is substituted by that of a player as a whole group of individuals. Even if we still consider pairwise interactions among individuals, our perspective is completely different: we suppose that individuals are simple actors of the game and that the utility to be maximized is the one of their group.

We analyze one of the most studied examples in evolutionary games, that of the Hawk and the Dove, which is a model for determining the degree of aggressiveness in the population. For this particular game we compute the symmetric Nash equilibrium and we show that the fact of teaming together makes individuals less aggressive at equilibrium.

The structure of the paper is as follows. In the next section we provide an overview and related literature. In section III we present the mathematical model of both the classical evolutionary game theory as well as our new definitions of group evolutionary game theory. We formulate games between several populations, both the case of infinite as well as finite populations are considered. We consider also the case in which the number of players is not known to the decision makers. In Section IV we present the Hawk and Dove game in GEG context.

II. OVERVIEW OF RELATED APPROACHES

Evolutionary game theory was introduced by John Meynard Smith [START_REF] Smith | Game theory and the evolution of fighting[END_REF], [START_REF] Smith | Evolution and the theory of Games[END_REF] to explain evolutionary processes in nature related to competition over resources. It is restricted to models of pairwise interactions between individuals. It assumes that an individual behaves as if it were a player, or a decision maker which maximizes its utility. The utility is taken to be the fitness of the individual; it is thus directly related to the reproduction rate of the individual. It is a function of both features (or behavior) of the individual as well as the distribution of features (or behavior types) among the whole population. Thus natural selection can be modeled as a game in which behaviors or features are actions, and the players are individuals.

When the number of players is very large, it is often well approximated by an infinite number of non-atomic players. This approach to model a large number of users have already been used in road traffic Engineering, where, however, an individual is not involved in pairwise interactions but in interactions with infinitely many individuals who share common roads. Such games are often called "population games". The equilibrium notion known as Wardrop equilibrium to those games was introduced already in 1952 [START_REF] Wardrop | Some theoretical aspects of road traffic research communication networks[END_REF]. We naturally find this equilibrium concept also in telecommunication networks when the number of decision makers is very large [START_REF] Altman | Equilibrium, games, and pricing in transportation and telecommunications networks[END_REF].

Much more recently, researchers in both road traffic [START_REF] Haurie | On the relationship between nash-cournot and wardrop equilibria[END_REF] as well as in telecommunication networks [START_REF] Orda | Competitive routing in multi-user communication networks[END_REF] have identified situations in which a whole group of cars can be associated with a single decision maker. A particular attention was given to situations in which the number of such groups is finite, and each group contains a strictly positive fraction of the whole population. These are often called splittable atomic games. In road traffic, such a group may correspond to a transportation company. In telecommunication networks it may correspond to an Internet Service Provider that may control how its traffic will be routed in the network. The equilibrium concept for these games, that of Nash equilibrium, is different than the Wardrop equilibrium, but under suitable condition the former converges to the latter as the number of groups grows to infinity (see [START_REF] Haurie | On the relationship between nash-cournot and wardrop equilibria[END_REF]).

We argue in this paper that the competition between groups should also be considered in the context of evolutionary games as it models many biological phenomena better than the standard evolutionary game paradigm. We shall show in an example how the Nash equilibrium obtained may indeed differ from that in which each individual is a player.

III. MODEL AND NEW CONCEPTS A. Classical Evolutionary Games

Evolutionary game theory is based on a setting with the following main features:

1) There is a large population of individuals, so large that it can be represented as a "fluid of individuals". 2) These individuals interact with each other through a large number of pairwise interactions. 3) There is a finite set A of actions. An individual choosing an action a facing another individual who chooses action b receives a payoff u(a, b). 4) If an individual chooses an action a in a random way using a probability p (whose entries are p(a), a ∈ A) and every other player chooses an action b according to a probability q (whose entries are q(b)) then the expected payoff for the individual is

u(p, q) = p T uq.
where u is the matrix whose a, b entry is u(a, b).

5) Each individual is a decision maker and he

chooses an action so as to maximize his own expected fitness. p is a Nash equilibrium if u(p, p) ≥ u(q, p) for all possible q. In this paper we replace point [START_REF] Orda | Competitive routing in multi-user communication networks[END_REF] above by distinguishing among actors, that is the individuals who chooses the action, and players, that is the groups of individuals whose utility is maximized. The rules that determine the actions of individuals are chosen so as to maximize the utility of their group. Note that in biological models this utility will represent the Darwinian's fitness of the group, and the decision process is done by darwinian selection, related to the whole group. We shall consider in this paper a finite number of competing groups and we will hence use the Nash equilibrium as solution concept.

B. Our new model: infinite population of individuals with a finite number of players

We consider an infinite population of individuals, divided into N groups; for simplicity of presentation we will consider symmetric groups of the same size. We can also think at a population composed of an higher number of groups, but in which each one of them only interacts with N neighbors.

As in standard evolutionary games, we focus on pairwise interactions, where each actor has a finite set of available actions: A = {a 1 , a 2 . . . a M }. We suppose that all individuals in the same group use the same strategy, so that the probability of choosing an action only depends on the group the individual belongs to. Given an actor j in group N i , the probability of choosing an action a k ∈ A is:

P(a i,j = a k ) = P(a i = a k ) = p i k ∀i = 1, . . . , N k = 1 . . . M
We associate to each group i the vector of probabilities pi :

pi = (p i1 , p i2 , . . . , p i M ) (1)
where M l=1 p i l = 1 ∀i = 1, . . . , N . As the population is infinite,we can assume that the probability of an interaction among two individuals of the same group equals the probability of an interaction among actors of different groups.

Since an individual is equally likely to interact with an individual of any one of the of the N groups (including its own one), the expected utility of a group (player) i is:

U i (p i , p-i ) = 1 N U pi, pi + 1 N N j=1,j =i U pi, pj (2)
where U pi pj (U pi pi ) is the immediate reward of an individual playing pi against an opponent playing pj (p i ).

Since we model a finite set of players, the natural solution concept is the Nash equilibrium.

C. The case of a finite population of individuals

As in our models a player represents a group of individuals, it's important to study the impact of the size of groups on the equilibrium. We thus consider now a finite population divided into N groups of size K.

Since the population is finite, given an actor in group N i and his opponent in N j , i, j ∈ {1, . . . , N }, the probability that they belong to the same group is:

P(i = j) = K -1 (K -1) + (N -1)K = K -1 N K -1
whereas the probability of belonging to two different groups is:

P(i = j) = 1 - K -1 N K -1 = K(N -1) N K -1
The expected utility of a player i is:

U i (p i , p-i ) = K -1 N K -1 U pi pi + + K N K -1 N j=1,j =i U pi pj (3)

D. The case of a random number of groups

In order to represent all those situations in which the number of groups a player interacts with is not known, we define a third model in which N is random. More generally we want to consider the case in which the total number of groups is fixed, but each group i interacts with a random number N i of players. We suppose that the population is finite and that the size of each group is K.

For each i = 1 . . . N we suppose that N i follows a geometric distribution:

P(N i = n) = (1 -q) n-1 q .
We assume that all the players but a fixed i use the same strategy, so that ∀j = i p j = p.

The average utility for the player i is:

U(p i , p) = ∞ n=1 q(1 -q) n-1 × × K -1 nK -1 U pi pi + K(n -1) nK -1 U pi pj (4)

IV. HAWK AND DOVE GAME IN GEGT

A. Hawk and Dove game in standard EGT

The Hawk and Dove game has been first introduced by Maynard Smith and Price in The Logic of Animal Conflict to describe animal behavior [START_REF] Smith | The logic of animal conflict[END_REF]; the model has been one of the most studied problems in EGT, and it has been applied to many different contexts. This basic model allows to study the evolution of aggressiveness within a population.

It was used not only in biology but also in Engineering in order to study the impact of selfishness on the choice of protocols for both congestion control, access control and power control [START_REF] Tembine | Evolutionary games in wireless networks[END_REF].

Hawk and Dove game represent a competition between two individuals for a resource. Each individual dispose of two possible strategies: he can choose to be a "hawk" and fight or he can choose to be a "dove" and peacefully back down. When two hawks meet, there will always be a fight, where the winner receive the benefit and the loser is injured. Doves are never aggressive, and so they are never involved in a fight. There is no cost to be a dove, only the possibility of receiving no payoff.

In order to illustrate our GEGT model, we suppose that any pairwise interaction is an Hawk and Dove game.

The set of available actions for each actor is A = {H, D}, where H corresponds to playing aggressively and D not aggressively. We associate to each group the probability

p i = P(a i = H) ∀i = 1, . . . , N
We define the following payoff matrix for the Hawk and Dove game:

H D H -δ + 1 2 1 D 0 1 2 (5)
where δ > 1 2 This allows us to compute the symmetric Nash equilibrium for our model, for the three cases we have presented in the previous sections.

B. Infinite population of individuals

In the case of an infinite population, we can rewrite the utility of a player i defined in (2) as:

U i (p i , p -i ) = 1 N U pi,pi + 1 N N j=1,j =i U pi,pj = 1 N [(-δ)p 2 i + 1 2 ]+ + 1 N N j=1,j =i [(-δp j + 1 2 )p i + 1 -p j 2 ]
We seek for the symmetric Nash equilibrium so we maximize the utility function :

∂U i (p i , p -i ) ∂p i = -2δ N p i + 1 N N j=1,j =i (-δp j + 1 2 ) = 2 N (-δ)p i + 1 N N j=1,j =i ( 1 2 -δp j )
We impose ∂Ui(pi,p-i) ∂pi = 0 :

p i = 1 2δN N j=1,j =i (-δp j + 1 2 )
By imposing p i = p j = p, we obtain the symmetric Nash equilibrium of the game:

p = N -1 N + 1 1 2δ (6)
It is interesting to study two extreme cases:

• N → ∞ When the number of groups is infinite we obtain: p = 1 2δ which is the value of the equilibrium of the corresponding standard evolutionary games. This is consistent with a similar result in [START_REF] Haurie | On the relationship between nash-cournot and wardrop equilibria[END_REF], that shows the convergence of Nash equilibrium to Wardrop equilibrium as the number of players goes to infinity.

• N = 2 When we have only two players formed by an infinity of actors,we obtain that p = 1 6δ which means that, as expected, two groups are less aggressive then two standard players. Figure 1 shows the equilibrium probability of being aggressive p as a function of the number of players N . We can observe that the equilibrium p is an increasing function in the number of groups. Note that when N increases, the probability of meeting a member of a different group increases: so we found that the level of aggressiveness is higher when the probability of interactions among individuals of different groups increases. Hence if an individual is aggressive it causes less damage to his group. This can explain the fact that the equilibrium probability of being aggressive increases in N .

As one may expect, we also observe that when the cost δ (involved in an encounter between two aggressive individuals) increases, the equilibrium probability p of being aggressive decreases.

C. Finite population of individuals

We now consider the second case, that of a finite population of individuals. When considering the payoff matrix (5), the utility defined in (3) becomes:

U i (p i , p -i ) = K -1 N K -1 (-δ)p 2 i + 1 2 + + K N K -1 N j=1,j =i (-δp j + 1 2 )p i + 1 -p j 2
As in the previous case, in order to maximize the utility we compute:

∂U i (p i , p -i ) ∂p i = = 2 K -1 N K -1 (-δ)p i + K N K -1 N j=1,j =i (-δp j + 1 2 ) = 2 K -1 N K -1 (-δ)p i + K N K -1 N j=1,j =i ( 1 2 -δp j )
and we impose ∂Ui(pi,p-i) ∂pi = 0. We obtain:

p i = K 2(K -1) N j=1,j =i (-p j + 1 2δ )
and by imposing the symmetry:

p = K(N -1) 2(K -1) ( 1 2δ -p)
We finally obtain the following Nash equilibrium:

p = K(N -1) K(1 + N ) -2 1 2δ (7)
In Figure 2 we plotted the value of the equilibrium p as a function of N for two different values of K and a fixed δ. As in the previous case, we can observe that p is an increasing function of N. In Figure [START_REF] Smith | The logic of animal conflict[END_REF] we plotted p as a function of the size of the groups. We can note that p rapidly decreases for small K; when K > 10, p stabilizes and it is very slowly decreasing. The explanation for this behavior is that when K is small, then the probability of meeting an individual of one's own group is quite sensitive to K, which is not the case when K is large.

D. Random number of groups

In the third case, that of a finite population divided into a random number of groups, the utility function (4) when considering the payoff matrix (5) becomes

U(p i , p) = q ((1 -2δp)p i + 1 -p) 2 ∞ n=1 (1 -q) n-1 + + q K -1 2 -2δp 2 i -(1 -2δp)p i + p × × ∞ n=1 (1 -q) n-1 nK -1 See derivation in Fig. VII in the Appendix VII. The sum ∞ n=1 (1-q) n-1 = ∞ n=0 (1-q) n is a geometric series which converges to 1 q . We define A ≡ ∞ n=1 (1 -q) n-1 1
nK-1 and we obtain:

U(p i , p) = ((1 -2δp)p i + 1 -p) 2 + + q K -1 2 -2δp 2 i -(1 -2δp)p i + p A
As we want to optimize the expected utility, we impose ∂U(pi,p) ∂pi = 0:

1 -2δp 2 + q K -1 2 (-4δp i -1 + 2δp)A = 0
By imposing p i = p, we have:

2δ(q(K -1)A + 1)p = 1 -q(K -1)A

And we find the symmetric Nash equilibrium:

p = 1 2δ 1 -q(K -1)A 1 + (q(K -1)A = 1 2δ 2 1 + (q(K -1)A -1 (8)
Figure 4 plots the equilibrium probability of being aggressive p as a function of q for three different values of K and a fixed δ. Taking into account that q = 1/E[N ], the form of the graph is indeed as can be expected from Figure 1 and Figure 2 in which the case of deterministic N was considered (note however that the two latter graphs is depicted as a function of N and not of 1/N ).

V. CONCLUDING SECTION AND DISCUSSION

This paper proposes a new alternative way to model evolutionary games in which fitness can be associated to a whole group rather than to an individual. Since fitness is defined in evolutionary games as related to the reproduction rate, the classical evolutionary game paradigm cannot model situations in which only one selected member of a Fig. 5. The value of p as a function of the size of groups K for three different values of q. Lower continuous line is obtained with q = 0.5, dotted line with q = 0.2, higher continuous line with q = 0.1 group is responsible for reproduction (beehives or nests of ants). We thus face a situation in which the decision maker (player) is not the individual involved in the interactions. The player can be identified with the group as a whole. We believe that our framework is useful also for other cases in which altruism is observed in nature between members of a family or of a larger group.

We considered here a finite number of players interacting with each other through pairwise interactions of their corresponding population. The equilibrium concept considered was naturally the Nash equilibrium which is a multistrategy such that no group can profit by deviating. In standard evolutionary games one often uses the notion of Evolutionary Stable Strategy (ESS) as a solution concept, which is stronger than a Nash equilibrium (it is robust against deviation of a whole small fraction of mutations). In our new GEG paradigm, Nash equilibrium implies robustness not just against a fraction of mutations in a group but against deviations of the whole group. Therefore, if we were to define an equilibrium in our model as a multistrategy robust against a small fraction of mutations, then it will not be a stronger equilibrium notion than the Nash equilibrium, as is the case in standard EG, but instead, any Nash equilibrium will also satisfy this definition of equilibrium.

Fig. 1 .

 1 Fig. 1. The value of p as a function of the number of groups N for two different values of δ. The continuous line (the upper curve) is obtained with δ = 0.8, the dotted line (lower curve) with δ = 1.2

Fig. 2 .Fig. 3 .

 23 Fig. 2. The value of p as a function of the number of groups N for two different values of K and δ = 0.8. Continuous line is obtained with K = 2, dotted line with K = 50

Fig. 4 .

 4 Fig. 4. The value of p as a function of q, for different values of K and δ = 0.8. Continuous line on the right is obtained with K = 5, dotted line with K = 25 and continuous left one with K = 50

Figure 5

 5 Figure 5 shows the equilibrium p as a function of K for three different values of N . The form of the graph is analogous to the one observed in Figure 3.

* The research was financed by the Congnas Eureopean project

VI. APPENDIX: EVALUATING A

We want to evaluate the sum

We define

where 0 < α < 1. From Fubini's theorem:

From the equality (9) we can also write:

where LerchP hi is the Lerch Zeta function defined as [START_REF] Luis M Navas | Asymptotic behavior of the lerh transcedent function[END_REF]:

We thus obtain that:

where q = r + 1.

We now rewrite f (α):

By considering q = -1 K , we get the following expression for f (α):

VII. APPENDIX: DERIVATION OF THE UTILITY FOR A RANDOM NUMBER OF PLAYERS

The derivation is provided in Figure VII.

(1 -q) n-1 nK -1

Fig. 6. Computing the expected utilities when the number of players is random