Cihan Aksoy
email: caksoy@uekae.tubitak.gov.tr

Vincent Labatut

Chantal Cherifi

Jean-François Santucci

MATAWS: A Multimodal Approach for Automatic WS Semantic Annotation

Keywords: Web Service, Semantic Web, Semantic Annotation, Ontology, WSDL, OWL-S

Many recent works aim at developing methods and tools for the processing of semantic Web services. In order to be properly tested, these tools must be applied to an appropriate benchmark, taking the form of a collection of semantic WS descriptions. However, all of the existing publicly available collections are limited by their size or their realism (use of randomly generated or resampled descriptions). Larger and realistic syntactic (WSDL) collections exist, but their semantic annotation requires a certain level of automation, due to the number of operations to be processed. In this article, we propose a fully automatic method to semantically annotate such large WS collections. Our approach is multimodal, in the sense it takes advantage of the latent semantics present not only in the parameter names, but also in the type names and structures. Concept-to-word association is performed by using Sigma, a mapping of WordNet to the SUMO ontology. After having described in details our annotation method, we apply it to the larger collection of real-world syntactic WS descriptions we could find, and assess its efficiency.

Introduction

The semantic Web encompasses technologies which can make possible the generation of the kind of intelligent documents imagined ten years ago [START_REF] Berners-Lee | The Semantic Web[END_REF]. It proposes to associate semantic metadata taking the form of concepts with Web resources. The goal is to give a formal representation of the meaning of these resources, in order to allow their automatic processing. The process of defining such associations is known as semantic annotation (or annotation for short), and generally relies on libraries of concepts collectively described and structured under the form of ontologies. The result is Web documents with machine interpretable mark-up that provide the source material for software agents to operate. The annotation of Web resources is obviously fundamental to the building of the semantic Web.

According to Nagarajan and Uren et al., in order to properly treat documents, annotating systems must follow a generic process [START_REF] Nagarajan | Semantic Annotations in Web Services[END_REF] and meet seven different requirements [START_REF] Uren | Semantic Annotation for Knowledge Management: Requirements and a Survey of the State of the Art[END_REF]. The annotation process is composed of three primary steps that are the identification of the entity to be annotated, its possible disambiguation and its association to a concept. The requirements are as follow. The first one is to use standard formats (R1). Indeed, they provide a bridging mechanism that allows the access to heterogeneous resources and collaborating users and organizations to share annotations. The second one is to provide a single point of entry interface (R2), so that the environment in which users annotate documents is integrated with the one in which they create, read, share and edit them. The third one is to support multiple ontologies and to cope with changes made to ontologies (R3). This last point ensures consistency between ontologies and annotations with respect to ontology changes. The fourth and the fifth requirements are related to the document to be annotated. An annotating system must support heterogeneous input formats (R4), and be able to manage the annotation consistency when the document evolves (R5). The sixth requirement is about the annotation storage (R6), for which two models are proposed: the annotations can be stored separately from the original document or as an integral part of the document. Seventh, and finally, as manual semantic annotation leads to a knowledge acquisition bottleneck, the last requirement deals with the automation of the annotating process (R7). Automated annotation provides the scalability needed to annotate existing documents on the Web, and reduces the burden of annotating new documents.

Besides static Web content such as textual or multimedia documents, semantic annotation also concerns dynamic content, and more particularly Web Services (WS). WS are non-static in nature; they allow carrying out some task with effects on the Web or the real-world, such as the purchase of a product. The semantic Web should enable users and agents to discover, use, compose, and monitor them automatically. As Web resources, classic WS descriptions such as WSDL files can be semantically enhanced using the annotation principle we previously described, i.e. by the association of various ontological concepts. However, due to the particular structure of WS descriptions, these associations must comply with very specific constraints, which are different from those encountered for other kinds of Web resources such as Web pages. [START_REF] Nagarajan | Semantic Annotations in Web Services[END_REF]. Indeed, the semantics associated with WS need to be formulated in a way that makes them useful to the application of WS. Sheth presents four types of semantics for the complete life cycle of a Web process: data, functional, nonfunctional and execution [START_REF] Sheth | Semantic Web Process Lifecycle: Role of Semantics in Annotation, Discovery, Composition and Orchestration[END_REF]. Data semantics is related to the formal definition of data input and output messages. Functional semantics is related to the formal definition of WS capabilities. Non-functional semantics is related to the formal definition of constraints like QoS. Execution semantics is related to the formal definition of execution flows at the level of a process or within a WS. Semantically annotating a WS implies describing the exact semantics of the WS data and functionality elements, which are crucial for the use of the WS, as well as its non-functional and execution elements.

Efforts for WS annotation include WS semantic languages as well as tools to annotate legacy WSDL files. The most prominent semantic languages are OWL-S [START_REF] Martin | Owl-S: Semantic Markup for Web Services[END_REF], WSMO [START_REF] De Bruijn | Web Service Modeling Ontology[END_REF], WSDL-S [START_REF] Akkiraju | Web Service Semantics -Wsdl-S[END_REF] and SAWSDL [START_REF] Farrell | Semantic Annotations for Wsdl and Xml Schema[END_REF]. While OWL-S and WSMO define their own rich semantic models for WS, WSDL-S and SAWSDL work in a bottom-up fashion by preserving the information already present in WSDL. Those description languages are used in many research projects focusing on various semantic-related applications like automatic discovery and composition. In order to test these applications, one needs a benchmark, i.e. a large collection of annotated WS [START_REF] Küster | Opossum -an Online Portal to Collect and Share Sws Descriptions[END_REF]. Such collections exist, but are limited in terms of size, realism, and representativity. These limitations are due to the fact the annotation process is generally performed manually, and is therefore costly. The use of an appropriate annotation tool can help decrease this cost, especially if it is automated. However, because of the specific structure of this kind of document, automatically annotating a WS description is much different, from the natural language processing perspective, than annotating other Web documents such as plain text. It consequently requires to perform a particular form of text mining, leading to dedicated tools such as ASSAM [START_REF] Hess | Assam: A Tool for Semi-Automatically Annotating Semantic Web Services[END_REF] or MWSAF [START_REF] Patil | Meteor-S Web Service Annotation Framework[END_REF]. But those tools also have their own limitations, the main one being they are only partially automated and require human intervention, which is a problem when annotating a large collection of WS descriptions.

In this paper we present the first version of MATAWS (Multimodal Automatic Tool for the Annotation of WS), a new semantic WS annotator, whose purpose is to solve some of these limitations. MATAWS was designed with the objective of batch annotating a large collection of syntactic descriptions and generating a benchmark usable to test semantic-related approaches. It focuses on data semantics (i.e. the annotation of input and output parameters) contained in WSDL files, and currently generates OWL-S files (other output formats will shortly be included). Our main contributions are: 1) a full automation of the annotation process and 2) the use of a multimodal approach. We consider not only the parameter names, but also the names present in the XSD types used in the WSDL descriptions: type names, and names of the fields defined in complex types.

The rest of this paper is organized as follows. Section 2 presents both existing ways of retrieving a collection of semantic WS descriptions: recover a publicly available collection and annotate a syntactic collection using one of the existing annotation tools. In section 3, we introduce MATAWS and describe our multimodal approach. In section 4 we apply MATAWS to the annotation of a publicly available collection of syntactic WS descriptions. Finally, in section 5 we discuss the limitations of our tool and explain how we plan to solve them.

Solutions to Access an Annotated Collection

When looking for a collection of semantic WS descriptions, one can consider two possibilities: either using a predefined collection, or creating his own one. In this section, we first review the main existing collections and their properties. The creation of a collection can be performed either by using a random model to generate artificial descriptions, or by semantically annotating a collection of real-world syntactical descriptions. The usual goal when looking for a semantic collection is to test WS-related tools on realistic data. To our opinion, the WS collections properties are not known well enough to allow the definition of a realistic generative model, which is why we favor the second solution. For this reason, in the second part of this section, we also review the main tools allowing to annotate WS descriptions.

Collections of Semantic Descriptions

The main publicly available collections of semantic WS are those provided by the ASSAM WSDL Annotator project, SemWebCentral and OPOSSum. Their major features are gathered in Table 1.

The ASSAM WSDL Annotator project (Automated Semantic Service Annotation with Machine learning) [START_REF] Hess | Assam (Automated Semantic Service Annotation with Machine Learning) Wsdl Annotator[END_REF] includes two collections of WS descriptions named Full Dataset and Dataset2. Full Dataset is a collection of categorized WSDL files, which contains 816 WSDL files describing real-world WS. Dataset2 is a collection of OWL-S files, obtained by annotating a subset of the WSDL files using the ASSAM Annotator (cf. section 2.2). 164 descriptions were fully labeled, assigning ontology references to the WS itself, its operations and their inputs and outputs. SemWebCentral [START_REF]Semwebcentral.Org[END_REF] is a community whose purpose is to gather efforts from people working in the semantic Web area. Three semantic collections are available: OWLS-TC (OWL-S Test Collection), SAWSDL-TC (SAWSDL Test Collection) and SWS-TC (Semantic WS Test Collection). OWLS-TC3 is the third version of this test collection. It provides 1007 semantic descriptions written in OWL-S from seven different domains. Part of the descriptions were retrieved from public IBM UDDI registries, and semi-automatically transformed from WSDL to OWL-S. SAWSDL-TC originates in the OWLS-TC collection. It was subsequently resampled to increase its size, and converted to SAWSDL. The collection provides 894 semantic WS descriptions. The descriptions are distributed over the same seven thematic domains than OWLS-TC. SWS-TC is a collection of 241 OWL-S descriptions. There is not much information about this collection.

OPOSSum (Online POrtal for Semantic Services) [START_REF] Küster | Opossum Online Portal for Semantic Services[END_REF] is a joint community initiative for developing a large collection of real-world WS with semantic descriptions. Its aim is to create a suitable test bed for semantically enabled WS technologies. OPOSSum gathered the three semantic collections of SemWebCentral, plus the Jena Geography Dataset collection, explicitly collected within OPOSSum. The collection contains 201 real-world WS descriptions retrieved from public. All the described WS belong to the domains of geography and geocoding. Unfortunately, for now, no semantic descriptions are available for the services of the Jena Geography Dataset, which is why this collection is absent from Table 1.

These collections have been widely used in semantic WS-related works [START_REF] Skoutas | Efficient Semantic Web Service Discovery in Centralized and P2p Environments[END_REF][START_REF] Ma | Web Services Discovery Based on Latent Semantic Approach[END_REF]. As shown in Table 1, they all focus on the annotation of the data elements, which corresponds to our objective. However, one can notice some limitations. SWS-TC description is insufficient, it is not even clear if the WS descriptions are real-world. Dataset2 contains only real-world WS descriptions but it is very small, which can raise questions about its representativity. On the contrary, OWLS-TC3 and SAWSDL-TC contain a substantial number of descriptions. Nevertheless, these have been partially resampled in an undocumented way, which raises important questions concerning their realism.

Annotation Tools

From our point of view, WS annotation is considered as a one-time task, aiming at annotating legacy WS, which are described only syntactically. Newly created or modified WS should be (re)annotated manually by their authors, which is much preferable in terms of quality than any automatic processing. For this reason, and due to the specific nature of WS annotation, we are not concerned by all the 7 requirements stated by Uren et al. [START_REF] Uren | Semantic Annotation for Knowledge Management: Requirements and a Survey of the State of the Art[END_REF] for general annotation tools. It is of course necessary to use standard formats for input and output (R1). A polyvalent environment is not necessary, since we do not want to modify existing descriptions or create any new ones (R2). The support of multiple or changing ontologies is relevant (R3), but it is not the most important point, so we chose to ignore it in this first work. The input format is constrained to WSDL (R4), since it is the de facto standard for syntactical WS description. As stated before, we do not plan to maintain annotations if WS are modified (R5). The model of annotation storage (R6) is constrained by the output format: separate form for OWL-S and integrated for WSDL-S and SAWSDL. Finally, the level of automation is of great interest to us, given our context (R7). Only a few publicly available tools exist to semantically annotate WS descriptions. Table 2 presents the main ones and summarizes their properties. They all take a set of WSDL files as input (R1 and R4), but differ on several properties such as their level of automation (R7) and the language used to output the semantic descriptions (R1). The tools are described in details in the rest of this subsection.

Radiant is an open source tool created at the Georgia University [START_REF] Gomadam | Radiant: A Tool for Semantic Annotation of Web Services[END_REF]. It takes the form of an Eclipse plug-in and can output both SAWSDL and WSDL-S files. It provides a GUI which presents the elements constituting the WS description and allows to select the concepts one wants to associate to parameters or operations, by browsing in the selected ontologies. This interface makes the annotation process easier, but the annotation is nevertheless fully manual.

ASSAM is an open source Java program developed at the University College Dublin [START_REF] Hess | Assam (Automated Semantic Service Annotation with Machine Learning) Wsdl Annotator[END_REF], able to output OWL-S files. It provides assistance during the annotation process. First, the user starts manually annotating parameters and/or operations using an existing ontology. Meanwhile, ASSAM identifies the most appropriate concepts using machine learning methods. After enough information has been provided, the software is able to propose a few selected and supposedly relevant concepts when the user annotates a new WS.

MWSAF is another open source Java tool created at the Georgia University [START_REF] Patil | Meteor-S Web Service Annotation Framework[END_REF]. It outputs WSDL-S files, and like ASSAM it has a machine learning capability allowing it to assist the user during the annotation process. It is able to annotate not only parameters and operations, but also non-functional elements.

WSMO Studio is an Eclipse plug-in initially designed to edit semantic WS based on the WSMO model. An extension allows annotating WS parameters and operations, and outputting the result under the form of SAWSDL files [START_REF] Dimitrov | Wsmo Studio -a Semantic Web Services Modelling Environment for Wsmo[END_REF]. However, the tool does not provide any assistance to the user and the process is fully manual. Besides these annotation tools, several softwares allow to convert WSDL files to OWL-S files, but without performing any semantic annotation: they only apply a syntactic transformation and present the information contained in the original WSDL file under a form compatible with the OWL-S recommendation. WSDL2OWLS is an open source Java application created at the Carnegie Mellon University [START_REF] Srinivasan | Wsdl2owl-S[END_REF]. OWL-S Editor is a plug-in for Protégé (itself an ontology development environment) created at SRI [START_REF] Elenius | Owl-S Editor[END_REF]. Another software performing the same task is also called OWL-S Editor, but was developed at Malta University [START_REF] Scicluna | Visual Modelling of Owl-S Services[END_REF].

From this review, we can conclude the existing annotation tools present various limitations relatively to our goals. First, from a practical perspective, some of these tools are old and not supported anymore, which can cause installation and/or use problems. For instance, Radiant and ASAM are not compatible anymore with the current versions of some of the Eclipse plug-ins, libraries or API they rely on; meanwhile MWSAF installs and runs fine, but generates files without any of the annotations defined by the user. More importantly, these tools require important human intervention: Radiant and WSMO Studio are fully manual, whereas ASSAM and MWSAF only assist the user, after a compulsory learning phase. This justifies the development of our own tool, which we present in the next section.

Proposed Annotation Method

The absence of an existing solution fulfilling our needs compelled us to develop our own tool to semantically annotate WS descriptions. The main differences with the other annotation tools are the exploitation of several sources of information and the automation of the annotation process. In this section, we first describe the general architecture of our tool, which is made up of several independent components. We then focus separately on the components of interest, explaining their design and functioning.

General Architecture

MATAWS takes a collection of WSDL files as input and generates a collection of OWL-S files as output. Fig. 1 gives an insight of its modular structure, which includes five different components. Among these components, two are using external APIs (Associator and Output Component), whereas the three remaining ones were developed by us in Java. The Input and Output components are not of great interest with regards to the topic of this article, which is why we describe them shortly here. The other components are described in details in the following subsections. The Input Component is in charge for extracting the set of all operation parameters defined in the considered collection of WSDL files. We designed a parser able (among other things) to retrieve the parameter names, type names and type structures (in the case of complex types) [START_REF] Cherifi | Ws-Next, a Web Services Network Extractor Toolkit[END_REF]. The Output Component is used after the annotation process to generate a collection of OWL-S files corresponding to annotated versions of the input WSDL files. For this purpose, we selected the Java OWL-S API, which provides a programmatic read/write access to OWL-S service descriptions [START_REF] Martin | Owl-S: Semantic Markup for Web Services[END_REF]. Note we plan to add support for WSDL-S and SAWSDL by using other appropriate APIs.

The three remaining components correspond to the core of the annotation process. After the input component has parsed the WSDL files, it fetches parameters information to the Preprocessor. This one originally focuses on the parameter names, decomposing, normalizing and cleaning them so that they can be treated by the Associator. This component is based on the inference engine Sigma [START_REF] Pease | Sigma Knowledge Engineering Environment[END_REF] is to associate an ontological concept to a word. If Sigma is successful and manages to return a concept, this one is associated to the considered parameter. After all the parameters of a WS have been annotated, the Output Component is used to generate an OWL-S file with both the information contained in the original WSDL file and the selected concepts. However, for various reason explained later, it is not always possible for Sigma to find a suitable concept for every parameter. In this case, the Type Explorer accesses some properties related to the parameter data type, to obtain what we call subparameters. These are then fetched to the Preprocessor and the core processing starts again. In case of repeated annotation failure, this process can be repeated recursively until success or lack of subparameters.

Preprocessor

In order to work properly and propose a suitable concept, the Associator needs to process clear and normalized words. However, the names defined in real-world WS certainly do not meet this criterion. First, the meaning of an operation, parameter or type can hardly be described using a single word. For this reason, most names are made up of several concatenated words, separated either by alternating upper and lower cases or by using special characters such as dots, underscores, hyphens, etc. Second, sometimes the result is too long and abbreviations are used instead of the complete words. Finally, an analysis of any collection quickly shows different additional characters such as digits or seemingly useless separators can also appear. Of course, there is no way to define an exhaustive list of the various forms a name can take in a WS description, but WS programmers actually follow only a few conventions, which allows performing very efficient preprocessing by applying a set of simple transformations to break a name into usable words. We distinguish three steps during name preprocessing: decomposition, normalization and filtering. The decomposition consists in taking advantage of the different types of concatenations we identified to break a name into several parts. It also involves some cleaning, in the sense all characters which are not letters are removed and diacritical marks are deleted. Table 3 shows some examples involving case alternation, and digit and underscore used as separators.

The normalization role is first to provide the Associator a clean version of the word, typographically speaking, by setting each word to lower case. Moreover, the normalization handles abbreviations, by replacing them with the corresponding fulllength words. Table 3 gives an example of the name no being replaced by the word number. However, this last task is very context-dependent, because some strings are both full words and common abbreviations. For instance, no could simply mean the opposite of "yes", used to negate the following concatenated word, e.g. no_limit.

For this reason, human intervention can be necessary to set up this preprocessing, and adapt it to the considered collection. We chose to allow the user to define a list of common abbreviations.

Finally, we added a filtering step to deal with stop-words, i.e. words with no particular semantic information relatively to their context. For instance, the string parameter commonly appears in parameter names, without bringing any significant information, since the syntax of the WSDL file already allows to know if a certain name points out at a parameter. For this reason, it can be considered as noise and ignored. Even more than before, the nature of the stop-words is closely linked to the domain of application, and requires human intervention to adapt the list of stop-words we defined.

Let us consider as an example the preprocessing of the name ASessionId_02. First it will be broken down to the words A, Session and Id while the numeric end of the name (02) will be ignored. The normalization step will transform them in a, session (lowercase) and identity (replacing an abbreviation). Finally, the filter will remove the article a, because it is a stop-word. Eventually, for this name ASessionId_02, the Preprocessor will output the two words session and identity.

Associator

As mentioned before, we use an existing tool called Sigma to associate a concept to a word. It is written in Java and allows to create, test, modify and infer ontologies [START_REF] Pease | Sigma Knowledge Engineering Environment[END_REF].

It is provided with the Suggested Upper Merged Ontology (SUMO), which (unlike its name suggests) contains also mid-level and domain ontologies [START_REF] Niles | Towards a Standard Upper Ontology[END_REF]. SUMO is free, covers a wide range of fields, and it has been mapped to the whole WordNet lexicon [START_REF] Pease | Linking Lexicons and Ontologies: Mapping Wordnet to the Suggested Upper Merged Ontology[END_REF]. It was initially defined using the SUO-KIF language [START_REF]IEEE: Suo-Kif (Standard Upper Ontology Knowledge Interchange Format[END_REF], and it is currently being converted in OWL [START_REF] Mcguinness | Owl Web Ontology Language[END_REF]. Although its main purpose is to work on ontologies, Sigma also offers a programmatic access to this mapping under the form of a method taking an English word as input and outputting a SUMO concept. Table 4 gives a few examples of such associations. The names we processed are most of the time not plain English words, which justifies our preprocessing.

Type Explorer

Although our focus is primarily on parameter names, we described the two previous components in general terms, because they can be applied to any kind of names. Indeed, different difficulties can arise, making it impossible to associate a concept to a parameter name. First, the Preprocessor might fail to break the name down to relevant words, hence fetching the Associator strings it cannot map to appropriate concepts. Second, the Preprocessor might filter all the words resulting from the name decomposition, meaning it will not be able to provide the Associator any word to process. This can be the case, for instance, when a name is composed of a single stopword or several concatenated ones (e.g.: SomeParameter_08). Third, even if at least one correct English word can be fetched to the Associator, it is possible this one simply does not find any associated concept. All three cases, or any combination of these three cases, result in the fact no concept could be associated to the considered parameter. To overcome this problem, we propose a multimodal approach taking advantage of latent semantics contained in the data type information available through WSDL files. First, in real-world WS, a large proportion of types have a user-defined name, whose meaning can be considered as complementary to the parameter name. Additionally, many of these custom types are complex in the XSD sense, i.e. they can be compared to the structured data types used in programming languages. A parameter whose type is complex is made up of several subparameters, which can recursively be composed themselves of other subparameters, if they have a complex type too. Therefore, by taking advantage of the data types, one can access the semantic information implicitly contained in the type names and subparameter names and types. Fig. 2. Excerpt from a real-world WSDL file: parameter with a complex XSD type. Fig. 2 gives an example of a complex type extracted from a real-world WSDL file. A parameter named category has a complex type called categoryDetail, defined as a sequence of two strings: a singer and a composer. If we suppose the word <message name="GetCategories"> <part name="category" type="categoryDetail" /> </message> ... <complexType name="categoryDetail"> <sequence> <element name="singer" type="xsd:string" /> <element name="composer" type="xsd:string" /> </sequence> </complexType> ... ... category is a stop-word, the Associator will not be able to provide any concept for this parameter. However, considering the words singer and composer gives access to additional information usable by the Associator.

The principle of our Type Explorer component is as follows. It is activated when the processing of the parameter name could not be used to successfully identify any concept. We start with the type name: if it is custom, we process it exactly like the parameter name, going through the preprocessing and association steps. In case of failure to associate any concept, we go further and consider the type structure. If it is complex, we access the first level of subparameters. For now, we only consider XSD sequences, because these are the most widespread, however the same approach can be extended to the other kinds of XSD types. We first focus on the subparameter names, and if the association is inconclusive, on their type names. In case of failure, the process recursively goes on by analyzing the structure of the subparameter types to access the second level of subparameters. The recursion stops when there is no more level to process (permanent failure) or as soon as concept can be associated (success).

Application to Real-World Descriptions

To assess its performance, we applied MATAWS to a collection of syntactic WS descriptions. We wanted to use a large collection of real-world descriptions, in order to avoid specific cases and to get consistent results. Given these criteria, the best collection we could found is the Full Dataset collection from the ASSAM project [START_REF] Hess | Assam (Automated Semantic Service Annotation with Machine Learning) Wsdl Annotator[END_REF], previously mentioned in our review of WS descriptions collections (section 2.1). It contains 7877 operation distributed over 816 real-world WS descriptions. In this section, we present the results we obtained on this collection. First we adopt a quantitative point of view and distinguish parameters only in terms of annotated or non-annotated. Second, we analyze the results qualitatively and discuss the relevance of the concept associated to the parameters.

Quantitative Aspect

We first focus on the proportion of parameters from the Full Dataset collection which could be automatically annotated by MATAWS. In this section, we consider a parameter to be successfully annotated if our tool was able to associate it to at least one concept. Table 5 displays several values, corresponding to the progressive use of the different components described in section 3. Each row represents the performance obtained when using simultaneously the specified functionality and those mentioned in the previous rows.

The first line corresponds to the direct application of the Associator, with no significant preprocessing. The only transformation consists in setting parameter names to lowercase, which is compulsory to apply Sigma. Under these conditions, MATAWS can propose a concept for 39.63% of the parameters. This means close to 40% of the parameters names are single words, which can be retrieved directly in WordNet. The rest needs more preprocessing to be successfully annotated.

The second row corresponds to the introduction of the decomposition step. The small improvement in the success rate (around +2%) allows us to think compound names do not contain directly recognizable words. By adding the normalization step, the improvement is extremely large (almost +48%). Further analysis shows this is only marginally caused by the replacement of abbreviations by full words. Among the remaining 10%, one can found specific parameter forms we plan to introduce in our preprocessing, and word variations such as plural forms, also easily integrable in our approach. A strong decrease (-21%) can be observed when introducing the filtering step. This means that, among the associated words, many correspond to stop-words, or concatenations of stop-words. In this case, the Annotator might be able to retrieve a concept, but this one is useless in this context (e.g. parameter). The introduction of the Type Explorer allows improving slightly our success rate (+3%), but its effect is not as strong as we expected. This can be justified by the fact most parameters with a custom type where annotated using only their names. Moreover, the type structure is difficult to exploit in this collection, because some types defined as complex surprisingly do not actually have any content (i.e. no subparameters at all).

Qualitative Aspect

The quantitative analysis reflects the fact a large proportion of parameters could be associated to a concept. The question is now to know if these associations, which were automatically retrieved, are relevant relatively to the context. For this matter, we isolated all the words detected in the whole set of parameters, thanks to our Preprocessor and Type Explorer. Table 6 shows the first most frequent words with their associated concept. Overall, most of the annotated words are associated to relevant concepts, leading to an approximate success rate of 83%. Words like computer, month, numeric, password, customer are perfectly recognized, but this is not the case of several widespread words such as name, user, address or value.

Irrelevant concepts are due to the fact some words have several meanings and can therefore be associated to several concepts. Such ambiguity can be raised directly when the considered word has most probably a unique meaning in the context of WS. For instance, when the word user is submitted to Sigma, it outputs three concepts, including the one expected in this case, i.e. "someone employing something". However, the top result corresponds to "someone who does drugs", which explains the associated concept (DiseaseOrSyndrome). Similarly, the appropriate concept for name is among the concepts returned by Sigma, but the top result correspond to its meaning in the expression "in the name of the law", hence the concept (HoldsRight). The quality of the annotation could be improved for such common words by simply selecting a priori the appropriate concepts, like we defined lists of stop-words and abbreviations. The selection of an accurate concept can also be context dependent, which makes it impossible or difficult to perform it a priori. For instance, the word value corresponds to many concepts equally likely to appear in a WS description: quantity, monetary value, time duration, etc. Regarding this problem, the quality of the automatic annotation can be improved by deriving concepts from several words, when they are available. For instance, if the parameter name is value01 and its type is myCurrencyType, then we have enough information to infer the most relevant concept. This can be done, for example, by taking advantage of the WordNet textual definitions.

Conclusion

In this article, we presented our tool MATAWS, which implements a new method to semantically annotate WS descriptions. It focuses on WS parameters, i.e. on the Data semantics [START_REF] Sheth | Semantic Web Process Lifecycle: Role of Semantics in Annotation, Discovery, Composition and Orchestration[END_REF], and implements most of the requirements defined by Uren et al. [START_REF] Uren | Semantic Annotation for Knowledge Management: Requirements and a Survey of the State of the Art[END_REF] and relevant to our context: it processes WSDL files and produces OWL-S files (R1 & R4), and is fully automated (R7). This automation level is enforced through the use of both an ontological mapping of the WordNet lexicon, and a multimodal approach consisting in using not only parameter names, but also data type names and structures to identify appropriate ontological concepts. When compared to existing annotation tools such as ASSAM [START_REF] Hess | Assam (Automated Semantic Service Annotation with Machine Learning) Wsdl Annotator[END_REF] and MWSAF [START_REF] Patil | Meteor-S Web Service Annotation Framework[END_REF], it is important to notice that MATAWS is much less flexible, because it does not include any machine learning abilities. This is due to the fact our goal is different: we want to batch annotate a large collection of WS descriptions without any human intervention, whereas the cited works aim at helping human users to annotate individual WS descriptions. Moreover, we tested MATAWS on a large collection of syntactic real-world WS descriptions, and despite its simplicity, it obtained very promising results, with 72% of the parameters annotated.

The version presented in this article constitutes a first step in the development of our tool. Although some parameters could not be associated with relevant concepts, it is clear that we reduced the manual labor required for the annotation of WS. However, for now this reduction is not important enough to spare human intervention, which is needed at least to control the result of the annotation process. To get around this limitation, we plan to improve our tool on several points. First, in order to lower the proportion of parameters we failed to annotate, we can use other sources of latent semantics present in the WSDL descriptions: natural language descriptions and names of messages and operations. Second, the association step can be improved in two ways. We can complete the Associator by including more tools able to map a lexicon to an ontology, such as DBPedia [28]. This would complete and enhance the results already obtained through Sigma. Also, by taking advantage of our multimodal approach, we can retrieve all the words related to a given parameter through its data type, in order to compare them with concept definitions expressed in natural language (as found in a dictionary).

Fig. 1 .

 1 Fig. 1. Architecture of MATAWS.

Table 1 .

 1 Collections of semantic WS descriptions: main features.

	Name	Dataset2	OWLS-TC3	SAWSDL-TC	SWS-TC
	Source	ASSAM project SemWeb Central	SemWeb Central	SemWeb Central
	Type	Real-world	Real-world	Real-world	N/A
		descriptions	descriptions,	descriptions,
			partially resampled	partially resampled
	Language OWL-S	OWL-S	SAWSDL	OWL-S
	Annotated	Data,	Data	Data	Data
	Type	Functional
	Size	164	1007	894	241
	Particular	Processed using	Single interface,	Single interface,	N/A
	features	Assam	one operation per	one operation per
		annotator	service	service

Table 2 .

 2 WS Semantic annotation tools and their properties.

	Name	Output Format	Annotated Type	Automation	Last Update
	Radiant	SAWSDL,	Data, Functional	Fully manual May 2007
		WSDL-S
	ASSAM	OWL-S	Data, Functional	Assisted	May 2005
	MWSAF	WSDL-S	Data, Functional,	Assisted	July 2004
			Non-Functional
	WSMO Studio SAWSDL	Data, Functional	Fully manual Sept. 2007

  , whose role

	Input Component	Parameters	Preprocessor	Words	Associator	Annotations	Component Output
	Syntactic Descriptions	Subparameters		Data Types	Semantic Descriptions
			Type Explorer
	WSDL Collection					OWL-S Collection

Table 3 .

 3 Preprocessing examples.

	Transformation	Original Name	Extracted Words
	Decomposition	WhiteMovesNext	White, Moves, Next
	Decomposition	Number3Format	Number, Format
	Decomposition	AUsername	Username
	Decomposition	User_name	User, name
	Normalization	no	number
	Normalization	Password	password
	Filtering	Parameter	-
	Filtering	Body	-

Table 4 .

 4 Concept association examples.

	Word	SUMO Concept associated by Sigma
	buffalo HoofedMammal
	school	EducationalProcess
	talk	Communication

Table 5 .

 5 Success rates obtained by using the different functionalities of MATAWS.

	Added Modification Proportion of Annotated Parameters
	No preprocessing	39,63%
	Decomposition	41,94%
	Normalization	90,01%
	Filtering	69,06%
	Type Explorer	72,04%

Table 6 .

 6 List of the most frequent words, with their associated concept. Bold rows represent semantically irrelevant concepts.

	Word	Occurrences Associated Concept
	identity	1255	TraitAttribute
	key	548	Key
	name	470	HoldsRight
	user	424	DiseaseOrSyndrome
	code	295	Procedure
	number	294	Object
	address	258	SubjectiveAssessmentAttribute
	date	203	DateFruit
	city	168	City
	amount	135	ConstantQuantity
	administrator 128	Position
	message	115	Text
	value	106	ColorAttribute
	password	98	LinguisticExpression
	pass	70	ContestAttribute
	customer	52	Customer
	company	51	Corporation
	phone	41	Device
	electronic	35	ElectricDevice
	computer	33	Computer
	mailing	33	Transfer
	month	32	Month
	numeric	32	Number

Acknowledgments. The authors would like to thank Koray Mançuhan, who participated in the development of MATAWS.


Tadeusz P Latkowski
email: tplatk@mimuw.edu.pl

Cooperation in Two-Person Evolutionary Games with Complex Personality Profiles

Keywords: numbers Population Dynamics, Prisoner's Dilemma, Mixed Equilibria

We propose a theory of evolution of social systems which generalizes the standard proportional fitness rule of the evolutionary game theory. The formalism is applied to describe the dynamics of two-person one-shot population games. In particular it predicts the non-zero level of cooperation in the long run for the Prisoner's Dilemma games, the increase of the fraction of cooperators for general classes of the Snow -Drift game, and stable nonzero cooperation level for coordination games.

I. INTRODUCTION

Game theory has been proved to be an effective tools of modeling different types of interactions in various scientific disciplines, e.g. in biology, social sciences and economics, cf. e.g. [START_REF] Vega-Redondo | Economics and the theory of games[END_REF], [START_REF] Nowak | Evolutionary Dynamics: Exploring the Equations of Life[END_REF], [START_REF] Szabo | Evolutionary games on graphs[END_REF], [START_REF] Mcelreath | Mathematical Models of Social Evolution: A Guide for the Perplexed[END_REF], [START_REF] Gintis | The Bounds of Reason. Game Theory and the Unification of the Behavioral Sciences[END_REF] and references therein. The usual assumptions of the perfect rationality lead to results which contradict many real and laboratory experimental situations. The standard game theory as a language of modeling the social interactions adopts too strong assumptions concerning individual behaviors, its motivations and regulatory mechanisms. We propose a theory of evolution of social systems which generalizes the standard proportional fitness rule of the evolutionary game theory. The biological fitness of a behavior, strategy, measured by the payoff from interactions, is replaced by more general function, the attractiveness of the behavior. The attractiveness of the strategy is assumed to depend not only on its payoff, but also on its actual popularity (fraction) in the population. The parameters of the attractiveness function describe different psychological characters of the agents. We formulate the evolution equation for the two-persons symmetric games with two strategies and find the equilibria and determine their stabilities for the considered mean field type population models. For such games we prove the existence of a polymorphic stable equilibrium. We determine sufficient conditions for which the equilibrium is unique. We also discuss the generic games with three mixed equilibria, two of them stable. Their existence is important in particular for the temporal evolution -the mixed equilibrium time asymptotic state depends for such games not only on the personality profiles of the actors and the payoff matrix of the game, but also on the initial composition (i.e. the fractions of the agents who play each available strategy) of the population. For the games with unique mixed equilibrium we study the dependence of the equilibrium composition of the strategies on the personality profiles of the actors. The PD game is one of the most popular and important games in social sciences, studied as a paradigm for the evolution of cooperation. In the models of continuous systems of actors playing at each instant of time the one-stage PD, e.g. in the mean field type equations of the replicator dynamics, the only asymptotic equilibrium state is defection. There are various 'solutions' of the dilemma, aimed at maintaining cooperation in the systems of agents in the long run. One can add spatial structure in the model, consider repeated interactions, learning through the introduction of the aspiration levels etc. Our model provides another solution of the dilemma, allowing -for general psychological profiles -for the persistence of cooperation in the long run. The theory is applied to fairly general two-person games, including the Snow-Drift game and the coordination games.

II. MODEL

We consider the evolutionary scenario: infinite homogeneous population of individuals. The players interact through a random pairwise matching, playing at each instant of time a 2-person symmetric game with two behavioral types (strategies) C and D, with the payoff matrix C D C R S D T P abbreviated in the following by [R, S, T, P ], where R, S, T, P are arbitrary positive numbers. In general C and D denote any two strategies. The most important applications will cover the social dilemmas, in particular the Prisoner's Dilemma game (PD), and for the Snow Drift game (SD), for which C stands for cooperation, D for defection, R for reward, S for sucker, T for temptation, and P for punishment. Another applications refer to the coordination games, for which we keep the same notation, cf. next section. We denote: p i = p i (t), i = 1, 2: the fraction of the strategy i (popularity, propensity of i) in the population at time t, ν 1 = Rp 1 + Sp 2 , ν 2 = T p 1 + P p 2 : the mean payoffs of the strategy respectively C and D in the population, u i (t): the attractiveness of the strategy i at time t. The attractiveness of the strategy i in the population reflects the fact that more attractive strategies ought to have an evolutionary advantage in the considered social systems. The attractiveness of the strategy i will be assumed to be an increasing and concave function of its mean payoff ν i and the popularity p i in the population. The concavity reflects the fact that when the attractiveness reaches a higher level, the changes are slower. It is also expected that the attractiveness of the strategy becomes zero if its mean payoff or its popularity in the population is zero. In our model we choose for the attractiveness of the strategy i the Cobb-Douglas utility function, cf. [START_REF] Cobb | A Theory of Production[END_REF], [START_REF] Platkowski | Operant Response Theory of Social Interactions[END_REF]:

u i (t) = p 1-α i ν 1-β i , i = 1, 2, (1) with
(α, β) ∈ [0, 1] × [0, 1].
The formula [START_REF] Aviles | Cooperation and non-linear dynamics: An ecological perspective on the evolution of sociality[END_REF] states that the attractiveness of a strategy depends not only on the payoff of the strategy, but also on its actual popularity in the population. The parameters α, β determine the responsiveness of the function u i to changes of the actual values of the current popularity and of the mean payoff of the action i. They define diverse personality profiles of the individuals. Exploiting Weber's intuitions, cf. Weber (1968), we defined the ideal types of the personality profiles for the limiting values of the parameters α, β, and characterized their basic properties, cf. [START_REF] Platkowski | Operant Response Theory of Social Interactions[END_REF]: HE (Homo Economicus): α = 1, β = 0. It means that HE assesses attractiveness of the action exclusively through its effectiveness (u i = ν i ). HE is interested exclusively in the future prospects, In the Weber's typology this sort of actor's motivation is called Zweckrationalitat (future-oriented instrumental rationality). HS (Homo Sociologicus): α = 0, β = 1. The HS assesses attractiveness of the action only through its popularity, the past effect for him/her (u i = p i ). HS is insensitive to the payoffs of the game. HT (Homo Transcendentalis): α = β = 1. It is an ideal type, for which every action has the same attractiveness (u i = 1). It describes a personality not interested in the effectiveness of a behavior or in its propensity, but rather by some other values. Thus, HT is the ideal type insensitive to the payoffs and the popularities of the strategies. This type of actor's orientation is called Wertrationalitat in Weberian terms. HA (Homo Afectualis): α = β = 0. The attractiveness function takes the form u i = ν i p i The corresponding evolution equations reduce to the standard replicator equations, as will be shown below.

All the other values of the parameters α, β describe intermediate, mixed personality profiles. We show below that the relevant combination of these parameters, defined through the sensitivity parameter s = 1-β α plays a crucial role in determining the temporal evolution of the considered populations. At the end of this section we discuss the sensitivities of the ideal personality profiles defined above. The notion of attractiveness generalizes the notion of fitness in the classical evolutionary game theory, in which a linear relation between payoff and fitness is usually assumed, mainly for its mathematical advantages. In general the relation [START_REF] Aviles | Cooperation and non-linear dynamics: An ecological perspective on the evolution of sociality[END_REF] gives nonlinear dependence of the attractiveness on the payoffs. We note that e.g. the exponential dependence of the fitness on payoffs has been considered in [START_REF] Traulsen | Analytical Results for Individual and Group Selection of Any Intensity[END_REF]; [START_REF] Aviles | Cooperation and non-linear dynamics: An ecological perspective on the evolution of sociality[END_REF]. The reader is also referred to [START_REF] Henrich | Why People Punish Defectors. Wak Conformist Transmission can Stabilize Costly Enforcement of Norms in Cooperative Dilemmas[END_REF] for another approach in which the ideas of imitating the successful, and copying the majority (the conformist transmission), are put together to stabilize the cooperation in populations of individuals. Many social and biological interactions are based on imitation processes, where individuals are more likely to adopt more successful and more popular strategies. We assume that the change of the distribution of the strategies in the system occurs through the process of imitation of the more attractive strategies. Let K be the number of available strategies (in this paper K = 2). Let N i (t) denotes the number of individuals playing the action i, N = N 1 + N 2 + ...N K -the fixed size of the system, p i = N i /N -the propensity of the behavior i for i = 1, 2, ..., K.

Assuming that the i-strategists review their strategy according to the Poisson process with the arrival rate r i we model the corresponding stochastic processes as a deterministic flow. The balance conservation equations read, cf. [START_REF] Weibull | Evolutionary Game Theory[END_REF], Section 4.4:

ṗi (t) = j =i [p j r j p i j -p i r i p j i ], i = 1, ...K, (2)
where p i j is the probability that the agent playing the j strategy will switch to the i strategy. We assume that p i j is proportional to the attractiveness u i of the strategy i:

p i j = cu i , (3)
c being the same for all strategies: the strategies with higher attractivenesses have larger probability to be imitated.

Assuming that the arrival rates r j are state and strategy independent constants, we obtain, after a straightforward calculation and time rescaling

ṗi (t) = u( u i u -p i ), u:= K j=1 u j , i = 1, 2, ..., K. (4)
The evolution equations ( 4) state that the change of p i is governed by its relation to the reference function -the normalized attractiveness ũi := ui u , and that the fraction p i of the strategy i increases if ũi is bigger than the actual fraction of the strategy i in the population, and decreases if it is smaller. We study the time evolution and the fixed points (equilibria) of the dynamical system (4) for K = 2 strategies. With the normalization condition p 1 + p 2 = 1 eq. ( 4) reduces to the evolution equation

ṗ1 = (1 -p 1 ) 1-α p 1-α 1 [ν 1-β 1 (1 -p 1 ) α -ν 1-β 2 p α 1 ], (5)
with

ν 1 = (R -S)p 1 + S, ν 2 = (T -P )p 1 + P.
We note that for each personality profile (α, β) ∈ [0, 1] × [0, 1] there exist two pure equilibria of (4):

p 1 = 0 and p 1 = 1 [for α = 1 we put u i (p i = 0) = 0, i = 1, 2].
All the other equilibria of eq. ( 4) will be called Mixed Equilibria, and denoted ME. Thus, each ME corresponds to a fixed point of eq. ( 5). We find a simple transformation

z = p 1 1 -p 1 , p 1 ∈ (0, 1). (6)
which allows to study important mathematical properties of ME in our model. In Appendix A (cf. Proposition 1) we show that the stationary solutions of (5) in the interval (0, 1), as well as their stability properties are the same as those of the equation

ż = W (z) ≡ Rz + S T z + P s -z, z ∈ (0, ∞), (7)
where we introduced the sensitivity to reinforcements parameter s:

s = 1 -β α , α = 0. (8)
Formula ( 8) implies that the existence and the asymptotic properties of the solutions of eq. ( 4) depend on the combination of the parameters α, β, which characterize the personality profile of the players, rather than separately on each of them. The sensitivity parameter s plays an important role in the matching law in the operant response theory of the mathematical psychology, cf. Hernstein (1997), [START_REF] Seth | Evolving Behavioral Choice: An Investigation into Herrnsteins Matching Law[END_REF], [START_REF] Platkowski | Operant Response Theory of Social Interactions[END_REF], and references cited therein. To see the connection we derive from (4) the equilibrium condition (for K = 2):

u 1 p 1 = u 2 p 2 , (9)
which, after substituting (1) and ( 8) is equivalent to the matching law of the mathematical psychology:

p 2 p 1 = ν 2 ν 1 s . ( 10
)
The parameter s is a measure of the degree to which, in equilibrium, the response ratio changes when the reinforcement ratio is modified.

In particular, the weberian ideal type Homo Transcendentalis: α = β = 1, for which s = 0, describes the personalities insensitive to reinforcements. The ideal type Homo Economicus: α = 1, β = 0 corresponds to the sensitivity s = 1.

Note that in the Cobb-Douglas utility function (1) the case α + β = 1 is referred to as the constant return to scale in the mathematical economics. This case corresponds also to the third ideal type, Homo Sociologicus: α = 0, β = 1, for which every state vector (p 1 , p 2 ) is an equilibrium, as can be seen from ( 5). Finally the "opposite" to Homo Transcendentalis ideal type, Homo Afectualis, α = β = 0, corresponds to infinite sensitivity. In this case the evolution equations ( 4) are identical to the replicator equations in the evolutionary game theory. To see it note that for α = 0 eqs. ( 4) can be rewritten in the form ṗi = p i j=1,...K

p j [ν 1-β i -ν 1-β j ], i = 1, ...K. (11)
In particular for β = 0 we obtain the usual replicator equations for the two-person symmetric games with K strategies. For K = 2 strategies we obtain from eqs. [START_REF] Pacheco | Evolutionary dynamics of collective action in N-person stag hunt dilemmas[END_REF] the modified replicator dynamics

ṗ1 = p 1 (1 -p 1 )[ν 1-β 1 -ν 1-β 2 ]. (12)
In the next section we discuss the existence, uniqueness and stability properties of the equilibrium states of our model. Results are proved for general payoff matrices of the two-person symmetric games, including the most popular two-person social dilemmas: the Prisoner's Dilemma and the Snow -Drift games as well as the general Coordination games.

III. EQUILIBRIA

A. General results

Let p * ∈ (0, 1) denotes a Mixed Equilibrium (ME), i.e. a fixed point of eq. ( 5). Thus, p * is the fraction of the individuals who play the first (C) strategy in equilibrium. When discussing the social dilemmas, with C denoting the first, cooperation strategy, the value p * will be called the (asymptotic) cooperation level in the population.

The inverse transformation z * := p * 1-p * , cf. ( 6) allows to identify ME with the zeros z * of the function W (z) in ( 7): W (z * ) = 0. We study ME and their stability under the dynamics (5), or equivalently [START_REF] Henrich | Why People Punish Defectors. Wak Conformist Transmission can Stabilize Costly Enforcement of Norms in Cooperative Dilemmas[END_REF]. In particular, for social dilemmas described by the relevant two -person games with cooperation and defection as two available strategies (e.g. for the PD or the SD game) the stable ME describe the states for which the partial cooperation is an asymptotic outcome of the considered social systems. We prove the following theorem on the existence, uniqueness and stability of ME for the considered two-person symmetric games:

Theorem 1

For the payoff matrix [R, S, T, P] with positive entries: I. For each 0 ≤ s < ∞ there exists at least one ME -the fixed point of the evolution equation [START_REF] Hauert | Spatial structure often inhibits the evolution of cooperation in the snowdrift game[END_REF].

II. Denote B := (1 -s) P T + (1 + s) S R , Δ := B 2 -4 SP RT . If 1.
Δ ≤ 0, or 2. B ≥ 0, or 3. ST ≥ RP , then ME is unique. III. For each 0 ≤ s < ∞ there exist at most three ME. IV. There exist three ME iff Δ > 0, B < 0, and U (z 1 )U (z 2 ) < 0, where z 1,2 := [-B ∓ √ Δ]/2, and U (z) := lnz + s ln T z+P Rz+S , z > 0. V. If ME is unique then it is globally stable in (0, 1) under the dynamics [START_REF] Hauert | Spatial structure often inhibits the evolution of cooperation in the snowdrift game[END_REF]. If there are three ME, then the smallest and the largest ME are stable, the middle one is unstable. Proof: I. Taking logarithm of eq. W (z) = 0, cf. [START_REF] Henrich | Why People Punish Defectors. Wak Conformist Transmission can Stabilize Costly Enforcement of Norms in Cooperative Dilemmas[END_REF], we obtain 1-1 correspondence between the zeros of the function U (z) defined in Theorem 1, and the ME -the solutions of [START_REF] Henrich | Why People Punish Defectors. Wak Conformist Transmission can Stabilize Costly Enforcement of Norms in Cooperative Dilemmas[END_REF]. The proof follows by noting that for positive entries of the payoff matrix [R, S, T, P ] we have lim z→0 U (z) = -∞, lim z→+∞ U (z) = +∞. P. II-IV are proved by studying the extrema of U (z) (details are given in Appendix A). P. V follows from the observation that in eq. ( 5) for all α ∈ (0, 1], β ∈ [0, 1] we have ṗ1 > 0 for p 1 > 0 small enough, and ṗ1 < 0 for 1p 1 small enough (whereas the expression in the square brackets in ( 5) is positive for p 1 small enough, and negative for 1p 1 small enough). The statement I implies that the dependence of the utility function (attractiveness) of a strategy on the propensity of the strategy results in the existence of at least one ME for all symmetric two-person games with positive payoffs, including all types of the social dilemmas for such games. In particular this "solves the dilemma" of the Prisoner's Dilemma game in the considered populations. An application of the sufficient conditions II is given in Example 3, Appendix B. In particular, p. II.2 implies that for s ≤ 1 the ME is unique. P. V states its global stability. Note that for s ≤ 1 the cooperation level does not depend on the initial distribution of the strategies in the population. On the other hand, if the sufficient conditions of p.IV are satisfied, then there are two (locally) stable fixed points of eq. ( 5), and the cooperation level does depend on the initial state of the population. P. II.3 provides the sufficient condition for the uniqueness of ME for all s ≥ 0. It states that the the ME is unique if the product of payoffs from playing different strategies is bigger than that from playing the same strategies, e.g. for the class of the anti-coordination games considered below. P. V implies that if the ME is unique, then the pure equilibria, which correspond to the fixed points p 1 = 0 and p 1 = 1 of eq. ( 4) are unstable, the polymorphic asymptotic state of the population is the only stable one. This implies for example that in such cases the monomorphic equilibria (all defectors or all cooperators) are unstable for the social dilemmas games. Examples and applications of Theorem 1 to the two-person social dilemmas will be discussed in the next subsections. For completeness, in Appendix B we provide analogous existence theorems for the payoff matrices which admit zero entries.

B. Equilibria for PD Games

The PD game is a two-person symmetric game with the payoff matrix the entries of which are denoted [R, S, T, P ], T > R > P > S,

where R(Reward), and S(Sucker) are the payoffs for C=Cooperation when the opponent plays respectively C, and D, whereas T (Temptation), and P (Punishment) are the payoffs for D=Defection when the opponent plays respectively C, and D. First we discuss the dependence of the cooperation level p * on the payoffs and on the sensitivity parameter s for such PD games, for which Theorem 1 guarantees the uniqueness of ME. As expected, p * increases for increasing R and decreasing T, P , cf. Fig. 1 for different PD payoff matrices. Moreover, p * → 0 when s → +∞, in agreement with the previously discussed fact that our dynamics approaches the modified replicator dynamics (12) in this limit. In general the uniqueness of the ME does not hold for all types of the PD games [START_REF] Platkowski | Operant Response Theory of Social Interactions[END_REF]. We found some particular types of PD (i.e. rather 'narrow' intervals of the entries of the general PD matrix), for which there exist three ME. To this end we performed calculations for all integer entries of the payoff matrix ( 13) from the set {1, ....40}, checking the sufficient conditions for the existence of three ME formulated in Theorem 1, p. V for various sensitivities s. For example for the sensitivity s = 2 there are only five such integer valued matrices: [R, S, T, P ] = [33, 1, 36, 10], [32, 1, 33, 10], [37,[START_REF] Aviles | Cooperation and non-linear dynamics: An ecological perspective on the evolution of sociality[END_REF]38,[START_REF] Pacheco | Evolutionary dynamics of collective action in N-person stag hunt dilemmas[END_REF], [38,[START_REF] Aviles | Cooperation and non-linear dynamics: An ecological perspective on the evolution of sociality[END_REF]40,[START_REF] Pacheco | Evolutionary dynamics of collective action in N-person stag hunt dilemmas[END_REF], [37,[START_REF] Aviles | Cooperation and non-linear dynamics: An ecological perspective on the evolution of sociality[END_REF]39,[START_REF] Pacheco | Evolutionary dynamics of collective action in N-person stag hunt dilemmas[END_REF]. In Fig. 2 we show the cooperation levels as functions of the sensitivity s for the PD game [R, [START_REF] Aviles | Cooperation and non-linear dynamics: An ecological perspective on the evolution of sociality[END_REF]30,[START_REF] Hauert | Spatial structure often inhibits the evolution of cooperation in the snowdrift game[END_REF] for different values of the reward R. For clarity we plotted discretized values, the full plots are continuous. Note the existence of three ME for a "narrow" interval of sensitivities around s = 3 for R = 27, 29; one can easily checked that the sufficient conditions for their existence, formulated in p. IV, Theorem 1, are satisfied. FIG. 2: Cooperation levels vs. sensitivity for increasing reward R for the PD game [R, [START_REF] Aviles | Cooperation and non-linear dynamics: An ecological perspective on the evolution of sociality[END_REF]30,[START_REF] Hauert | Spatial structure often inhibits the evolution of cooperation in the snowdrift game[END_REF]. For R=6 and R=25 the ME is unique. For R=27 and R=29 there are three ME in the narrow interval of s around s = 3. For example for R=29 and the sensitivity s = 3.2 two stable ME correspond to the cooperation levels p * ≈ 0.25 and p * ≈ 0.02, whereas the unstable ME corresponds to p * ≈ 0.08.

C. Equilibria for Anti-coordination Games

We define the general Anti-coordination game with the payoff matrix [R, S, T, P ], T > R > 0, S > P ≥ 0.

(

) 14
The game has one mixed and two pure Nash equilibria, the mixed one stable under the replicator dynamics. We prove Lemma 1 For all sensitivities s ∈ [0, +∞) there exists an unique ME for the Anti-coordination game ( 14) -a global attractor of the dynamics [START_REF] Hauert | Spatial structure often inhibits the evolution of cooperation in the snowdrift game[END_REF].

Proof: Using the notation of Theorem 1 we calculate B = s(ST -RP )/RT + P/T + S/R.

For the payoff matrix ( 14) B > 0, therefore the uniqueness and the global attraction property of the ME follows respectively from p. II.2 and V of Theorem 1. Note that this result holds for P ≥ 0, i.e. in particular for the -important for applications in social sciences -the Snow-Drift (SD) game, cf. Sugden (1986), [START_REF] Hauert | Spatial structure often inhibits the evolution of cooperation in the snowdrift game[END_REF].

Let us consider the SD game with the payoff matrix in the (b)enefit -(c)ost formulation:

[b -c/2, b -c, b, 0], b > c > 0. ( 15
)
This game represents the social dilemma in which the strategy C -cooperation implies a benefit b to the cooperator and to the opponent (independently of the opponent's strategy), and in addition incurs the cost c if the opponent plays the strategy D (i.e. defects), or c/2 if (s)he cooperates. If both players defect, they receive 0.

In the mixed Nash equilibrium of the replicator dynamics the fraction of C -players is equal p N = 2(bc)/(2bc).

In Fig. 3 In Fig. 4 we plot the dependence of p * on the type of the game, for the sensitivities in the interval [0, 10], and different payoffs S. The payoff matrix is [3, S, 5, 1]. For 1 > S ≥ 0 it describes the PD games, for S = 1 the 'Weak' PD game, and for the payoff S > 1 the Anti-coordination games [START_REF] Platkowski | Cooperation in aspiration-based N-person prisoners dilemmas[END_REF]. For all three types of the games, for each sensitivity s > 0 the increase of the payoff S implies the increase of p * . Note that for S > 0 the ME is unique. For S = 0 there exists

D. Equilibria for Coordination Games

We consider the Coordination games defined by the payoff matrix:

[R, S, T, P ], R > T, P > S.

The Nash equlibrium p N = (P -S)/(R -T + P -S) is unstable under the replicator dynamics. For example the Stag Hunt game (with T ≥ P , and the first, C strategy corresponding to "Hunt Stag", the second, D -to "Hunt Hare") belongs to this class. In our dynamics, unlike the Anti-coordination games ( 14), the Coordination games can have two stable ME, as will be documented below. First we prove another uniqueness result. As already stated, p. II.2 of Theorem 1 implies that for all 2-person games the condition s ≤ 1 is sufficient for the uniqueness of the ME. For the Coordination games [START_REF] Souza | Evolution of cooperation under N-person snowdrift games[END_REF] we have a stronger uniqueness result: Lemma 2 For the Coordination game [START_REF] Souza | Evolution of cooperation under N-person snowdrift games[END_REF] with := ST RP < 1 the ME is unique for s ≤ 1+ 1-. Proof: The above inequality for s is equivalent to B > 0, i.e. to the sufficient condition II.1 of Theorem I for the uniqueness. Below we study the Coordination games with the payoff matrix [R, S, S, R], R = S, R > S > 0, [START_REF] Sugden | The Economics of Rights, Co-operation and Welfare[END_REF] By inspection of ( 7), written for [START_REF] Sugden | The Economics of Rights, Co-operation and Welfare[END_REF], we note that for all 0 ≤ s < ∞ there exists the ME z * = 1, i.e. p * = 1/2. The uniqueness depends on the payoff ratio f := R/S and on the sensitivity s. In Appendix B, Example 4 we formulate sufficient conditions for the existence of three ME for s = 2. Example 1 Fig. 5 shows the bifurcation of the stable equilibrium into three equilibria for two Coordination games. For the payoff matrix [2, 1, 1, 2] the equilibrium p * = 0.5 is globally stable and unique for s ≤ 3 (in notation of Lemma 2 = 0.5). The branching point s = 3 corresponds to z * = 1, which is the third order zero of the function W (z) in [START_REF] Henrich | Why People Punish Defectors. Wak Conformist Transmission can Stabilize Costly Enforcement of Norms in Cooperative Dilemmas[END_REF]. For s > 3 the emerging two branches correspond to stable ME: for s = 3 + δ, δ > 0 we calculate, from Theorem 1: Δ = 6δ + 0(δ 2 ) > 0, B = -2δ < 0, and U (z 1 )U (z 2 ) < 0, which guarantees the existence of three ME.

The second game, with the payoff matrix [2.01, 1, 1, 2], indicates the sensitivity of the branching point to small perturbations of the payoff R = 2. For s < 3.1 the ME is unique. For s ≈ 3.1 two new equilibria emerge, the middle one unstable, the lower stable, cf. the lower diagram of Fig. 5. For s → ∞ two stable ME tend, as expected, to the replicator dynamics values p * = 0, p * = 1, the third ME tends to the unstable Nash equilibrium, as expected for the replicator dynamics for this coordination game.

Example 2

For the Stag Hunt game with the payoff matrix [R, S, T, P ] = [3, 1, 2, 2] (and for all the games with R + S = T + P ), the value p * = 0.5, corresponding to z * = 1, is the cooperation level for all sensitivities s ≥ 0, since in this case W (z * = 1) = 0 ∀s ≥ 0. For s ≈ 3.8 there emerge two additional ME, cf. Fig. 6. For slightly larger s the bigger ME tends to p = 0.5, and merges with p = 0.5 for s = 4. For s > 4 the ME p * = 0.5 is unstable, the other two branches are stable. As in the previous example, for s → ∞ two stable ME tend to p * = 0, p * = 1, the third ME corresponds to the unstable Nash equilibrium with p * = 0.5.

IV. DISCUSSION

We presented a model of population with complex personality profiles, and its applications to symmetric two-persons games, in particular those representing most important social dilemmas. The results are proved for well mixed infinite populations with random pairwise matching. The mechanism of the strategy updating based on imitation of more successful and more popular strategies solved the dilemma of the PD game. We found stable equilibria of the considered dynamics, not present in the classical evolutionary game theory approach based on the replicator dynamics. In particular there exists a stable mixed equilibrium for the general PD game with arbitrary positive payoffs. Moreover, our theory reveals a 'subtle' structure of the asymptotic stationary solutions of the PD game under considered dynamics. In particular there are classes of the PD games with three stationary solutions, two of them locally stable for some intervals of the sensitivity parameter. The sensitivity parameter has a direct interpretation in the matching law of the operand-response theory. Similar structure can occur in the Coordination games, whereas for the Anti-coordination games (in particular for the SD game) the mixed equilibrium is unique and globally stable. The idea of combining together the bias towards imitating the strategies of the most payoff-successful agents and the strategies of the majority is not new, cf. e.g. [START_REF] Henrich | Why People Punish Defectors. Wak Conformist Transmission can Stabilize Costly Enforcement of Norms in Cooperative Dilemmas[END_REF] where it led to stabilization of the cooperation in populations. Multiple polymorphisms for the games with two strategies played in infinite populations have been found e.g. in the models of social dilemmas with synergy and discounting, cf. In the presented imitation model, in which the "sociological" aspect of the attractiveness of the strategies is taken into account through its dependence on the actual propensities of the strategies, the multiple polymorphisms can exist already in the two-person games. Further research will be focused on generalization for systems with more than two behavioral types, non-symmetric games, other attractiveness functions, and more general psychological types. Preliminary investigations indicate interesting dynamics in such more complicated situations. It will also be interesting to allow the actors to change their personalities during the interactions.

FIG. 1 :

 1 FIG. 1: Cooperation level vs. sensitivity for various PD games. The components of the vectors in the legend correspond to the entries of the payoff matrix [R, S, T, P ].

FIG. 3 :

 3 FIG.3: Cooperation level vs. cost c for the SD game with the normalized (b = 1) matrix [1c/2, 1c, 1, 0] for various sensitivities s. The 'Nash' curve corresponds to infinite sensitivity.

FIG. 4 :

 4 FIG. 4: Cooperation level vs. sensitivity for the payoff matrix [3, S, 5, 1] for different values of the sucker payoff S.

  0

  [START_REF] Hauert | Synergy and discounting of cooperation in social dilemmas[END_REF], in the aspiration-based models, cf. e.g. Palomino, Vega-Redondo (1999),[START_REF] Platkowski | Cooperation in aspiration-based N-person prisoners dilemmas[END_REF], in the Stag-Hunt N-person games, cf. Pacheco et al. (2009), in the N-person Snowdrift games, cf. Souza et al. (2009).

FIG. 6 :

 6 FIG. 6: Bifurcation of the unique ME into three ME for the Stag Hunt Game with the payoff matrix [3, 1, 2, 2].

  FIG. 5: Bifurcation of the unique ME into three ME for two Coordination Games with the payoff matrices [2, 1, 1, 2], and [2.01, 1, 1, 2]

									'[2,1,1,2]'
		1
		0.8					stable
	Cooperation level p*	0.4 0.6		stable			unstable
		0.2					stable
			2.6	2.8	3	3.2	3.4	3.6	3.8	4
						Sensitivity s
									'[2.01,1,1,2]'
		1
							stable
		0.8
	Cooperation level p*	0.4 0.6		stable			unstable
		0.2					stable
		0	2.6	2.8	3	3.2	3.4	3.6	3.8	4
						Sensitivity s

Acknowledgements. TP was supported by the Polish Government Grant no. N201 362536. The author is grateful to two anonymous referees for helpful comments.

V. APPENDIX A

Proposition 1 p * ∈ (0, 1) is the stationary solution of (5) iff z * = p * /(1p * ) is the stationary solution of of [START_REF] Henrich | Why People Punish Defectors. Wak Conformist Transmission can Stabilize Costly Enforcement of Norms in Cooperative Dilemmas[END_REF]; p * is stable (unstable) iff z * is stable (unstable).

Proof

The proof follows from the fact that omitting the positive multiplicative terms on the rhs of eq. ( 5) we do not change its equilibria and their stability. After substituting z = p 1 /(p 1 -1) eq. ( 5) takes the form ż = P (z)[(R(z) s )) αz α ], [START_REF] Szabo | Evolutionary games on graphs[END_REF] where R(z) = (Rz + S)/(T z + P ), and P (z) > 0 ∀z ∈ (0, ∞) is a well defined function. Eq. ( 18) has the same ME and their stability properties, as eq. ( 7).

Proof of Theorem 1, p. II-IV: II. We calculate U (z) = W 1 (z) P (z), where P (z) > 0 ∀z > 0, and

Thus, extrema of U are zeros of the polynomial W 1 . II.1 follows from the fact that: for all z > 0 and Δ < 0 W 1 (z) > 0 ; for Δ = 0 ∃!z * : W 1 (z * ) = 0, i.e. U (z * ) = 0: z * = -B/2, thus can not be an extremal point. II.2 follows from the following observations: for B = 0 W 1 > 0 ∀z ≥ 0, therefore U (z) > 0 ∀z ≥ 0, U is strictly monotonic; for B > 0: if Δ ≥ 0 then z 1 < 0 and z 2 < 0, where W 1 (z i ) = 0, i = 1, 2, therefore U (z) has no extrema for z > 0. if Δ < 0 then W 1 (z) > 0 ∀z ≥ 0.

II.3 follows by noting that ∀s ≥ 0 B > 0, and applying II.2.

III follows from the observation that the graph of U (z) has at most three common points with the z-axis.

IV: <=: For Δ > 0 both roots 0 < z 1 < z 2 of W 1 are positive. The condition U (z 1 )U (z 2 ) < 0 together with the limit values of U (z) imply U (z 1 ) > 0 and U (z 2 ) < 0. In consequence the graph of U (z) crosses the positive part of the zaxis three times. =>: The existence of three ME, i.e. that U crosses the z -axis three times, implies that U (z) must have two extrema, say at z1 > 0 and z2 > 0, i.e. W 1 (z 1 ) = W 1 (z 2 ) = 0. Thus, Δ > 0, and the relation z1 + z2 = -B > 0 implies B < 0. The condition that U (z) crosses the z-axis three times implies U (z 1 ) > 0 and U (z 2 ) < 0.

Remarks

The uniqueness condition II.3 can be given the following interpretation. Each 2-person symmetric game can be considered as the sum of two basic games: the pure Coordination game (CG) with the payoff matrix [R, 0, 0, P ], and pure Anti -coordination game (AG) with the payoff matrix [0, S, T, 0]. Then II.3 states that the ME is unique if the product of the positive payoffs in AG is bigger than that in CG. We note that ( 5) is invariant in [0, 1], that for α = β = 1 z * = 1 is the unique, globally stable ME. Two ME are also possible for particular cases in which the graph of U is tangent to the z axis. Such situations are "unstable" with respect to arbitrarily small perturbations of the relevant parameters of the model, and are not considered here.

VI. APPENDIX B

For convenience of the reader we formulate the existence theorem for the matrices with nonnegative entries. The proofs are similar to the proofs of the existence theorems considered above and will be omitted here.

For S = 0 and R, T, P > 0, e.g. for the PD matrix corresponding to the Axelrod's tournament, [START_REF] Axelrod | The evolution of cooperation[END_REF], the existence of ME is not guaranteed, cf. [START_REF] Platkowski | Operant Response Theory of Social Interactions[END_REF].

Theorem 2

For the payoff matrix [R, 0, T, P ], R > 0, T > 0, P > 0: For s < 1 there exists an unique ME, i.e. positive solution of eq. ( 7). For s > 1 the existence and uniqueness of ME depend on the function Proof. The Nash equilibrium is

the positive solution of eq. W (z) = 0, p * = z(c)/(z(c) + 1). The condition p * > p N is equivalent to c 2 -10c + 8 < 0, satisfied for 1 > c > 2/3. For s = 1 we checked numerically, for c > 2/3, the validity of the inequality

5 , i = 1, 2. Thus, for s ∈ [0, s 2 ], where s 2 ≈ 2.4 z * = 1 is the unique ME. For s > s 2 two new ME z 1 < z 2 emerge, as can be verified by checking the sufficient conditions IV of Theorem 1. For s = 2.5 z 2 = 1 is neutrally stable, z 1 is globally attractive (except z 2 ). For s > 2.5 z 2 bifurcates into two ME: the unstable z 2 = 1, and the stable z 3 > 1. For s → ∞ we recover two stable Nash equilibria p * = 0 and p * = 1, and the unstable one p * = 0.5.

Example 4

For the Coordination games [START_REF] Sugden | The Economics of Rights, Co-operation and Welfare[END_REF] with s = 2 and f = R S ≤ 1 + √ 2 the ME p * = 0.5 is unique. For f > 1 + √ 2 there are three ME: p * = 0.5, p * 1 < 0.5, p * 2 > 0.5. For f → ∞ p * 1 → 0, p * 2 → 1. Proof: For s = 2 the equilibrium condition W (z) = 0, cf. [START_REF] Henrich | Why People Punish Defectors. Wak Conformist Transmission can Stabilize Costly Enforcement of Norms in Cooperative Dilemmas[END_REF], takes the form

The result follows from the analysis of zeros of the binomial z 2 + (1 + 2ff 2 )z + 1.


Matthew D Johnston

Philip K Maini

S Jonathan Chapman

Carina M Edwards

Walter F Bodmer

On the proportion of cancer stem cells in a tumour

It is now generally accepted that cancers contain a sub-population, the cancer stem cells (CSCs), that initiate and drive a tumour's growth. At least until recently it has been widely assumed that only a small proportion of the cells in a tumour are CSCs. Here we use a mathematical model, supported by experimental evidence, to show that such an assumption is unwarranted. We show that CSCs may comprise any possible proportion of the tumour, and that the higher the proportion the more aggressive the tumour is likely to be.

Cancer stem cells are the cells that both initiate and propel a cancer through all its many phases of growth [START_REF] Reya | Stem cells, cancer, and cancer stem cells[END_REF][START_REF] Mcdonald | Mechanisms of disease: from stem cells to colorectal cancer[END_REF][START_REF] Polyak | Roots and stems: stem cells in cancer[END_REF] . They, in general, have the ability to differentiate into a variety of cell types according to the tissue of origin [START_REF] Mackenzie | Retention of stem cell patterns in malignant cell lines[END_REF][START_REF] Locke | Retention of intrinsic stem cell hierarchies in carcinoma-derived cell lines[END_REF][START_REF] Harper | Stem cell patterns in cell lines derived from head and neck squamous cell carcinoma[END_REF] . A cancer, therefore, to a greater or lesser extent recapitulates the organisation of the normal tissue from which it is derived, but in a deranged manner. Cancer therapy cannot be successful unless it eliminates the CSCs.

Thus, understanding the nature and evolution of stem cells in a cancer is crucially important for the development of effective therapies.

A variety of approaches, especially selecting for certain surface markers using monoclonal antibodies and Fluorescence Activated Cell Sorter (FACS) technology, have been applied to the identification of CSCs in a wide range of cancers and cancer derived cell lines (see, for example [START_REF] Al-Hajj | Prospective identification of tumorigenic breast cancer cells[END_REF][START_REF] Singh | Identification of human brain tumour initiating cells[END_REF][START_REF] O'brien | A human colon cancer cell capable of initiating tumour growth in immunodeficient mice[END_REF][START_REF] Ricci-Vitiani | Identification and expansion of human colon-cancerinitiating cells[END_REF][START_REF] Cho | Recent advances in cancer stem cells[END_REF][START_REF] Yeung | Cancer stem cells from colorectal cancer-derived cell lines[END_REF] ). In many cases it has, however, been assumed that CSCs necessarily constitute only a small minority of the cells in a cancer (see, for example [START_REF] O'brien | A human colon cancer cell capable of initiating tumour growth in immunodeficient mice[END_REF][START_REF] Ricci-Vitiani | Identification and expansion of human colon-cancerinitiating cells[END_REF][START_REF] Dalerba | Cancer stem cells: models and concepts[END_REF][START_REF] Dalerba | Phenotypic characterization of human colorectal cancer stem cells[END_REF][START_REF] Clarke | Neurobiology: at the root of brain cancer[END_REF] ). This assumption has largely been based on data suggesting that only a minority of the cancer cells xenografted from any given human cancer into immunodeficient mice can form a tumour. Modelling has also been used to support the idea that cancer stem cells are comparatively rare in a cancer [START_REF] Huntly | Summing up cancer stem cells[END_REF][START_REF] Michor | Dynamics of chronic myeloid leukaemia[END_REF] . However, more recent work on melanomas by Quintana et al. [START_REF] Quintana | Efficient tumour formation by single human melanoma cells[END_REF] has shown that, while earlier techniques could identify only one in 837,000 cells in a melanoma as being cancer stem cells, their newer assay suggested that as many as one in four cells from melanomas could form tumours in more stringently immuno-deprived mice and observed over a longer period of time (see also [START_REF] Baker | Cancer stem cells, becoming common[END_REF] ). Previous studies on mouse leukaemias have also shown that at least some malignancies may be maintained by more than 10% of the cells in a tumour [START_REF] Kelly | Tumor growth need not be driven by rare cancer stem cells[END_REF] .

Recently, Yeung et al. [START_REF] Yeung | Cancer stem cells from colorectal cancer-derived cell lines[END_REF] have shown that the proportion of cancer stem cells that can be identified in colorectal cancer derived cell lines can vary quite widely, from perhaps 20% to virtually all cells. Thus, evidence is accumulating that different individual cancers may contain widely differing proportions of CSCs, though the average proportion may differ between different types of tumours, such as breast and colorectal cancers, and melanomas.

It is not at all clear that CSCs are necessarily derived from tissue stem cells [START_REF] Polyak | Roots and stems: stem cells in cancer[END_REF][START_REF] Van Es | Notch/ γ -secretase inhibition turns proliferative cells in intestinal crypts and adenomas into goblet cells[END_REF] . In their original three compartment mathematical model, Tomlinson and Bodmer [START_REF] Tomlinson | Failure of programmed cell death and differentiation as causes of tumors: some simple mathematical models[END_REF] raised the possibility that cancers may be initiated from transit amplifying cells rather than the tissue stem cells. In their subsequent development of this model, incorporating feedback and using a continuous time model, Johnston et al. [START_REF] Johnston | Mathematical modeling of cell population dynamics in the colonic crypt and in colorectal cancer[END_REF][START_REF] Johnston | Examples of mathematical modeling: tales from the crypt[END_REF] suggested that, while both derivation from the tissue stem cell or from the transit amplifying cell may be possible, the ultimate derivation of the CSC is most likely to be traced back to progenitor or transit amplifying cells derived from the tissue stem cell, rather than from the tissue stem cell itself. The aim of this note is to show that very plausible models of a cancer, along the lines of our earlier work, can readily explain substantial variation in the proportion of CSCs versus differentiated cells in a cancer, depending on the balance between the rate of turnover of the CSCs and their rate of differentiation.

Colorectal crypt compartment model

Johnston et al. [START_REF] Johnston | Mathematical modeling of cell population dynamics in the colonic crypt and in colorectal cancer[END_REF][START_REF] Johnston | Examples of mathematical modeling: tales from the crypt[END_REF] introduced a three compartment continuous time mathematical model of cell turnover in the colorectal crypt that was based on the discrete model of Tomlinson and Bodmer [START_REF] Tomlinson | Failure of programmed cell death and differentiation as causes of tumors: some simple mathematical models[END_REF] . The cells in a healthy crypt are separated into populations of stem, transit-amplifying and fully-differentiated cells, denoted by 0 N , 1 N and 2 N , respectively. For simplicity we ignore the fact that there are three types of differentiated cells in the colorectal crypt. We assume that the stem (respectively transit) cells either die, differentiate or renew at rates 1 α , 2 α and 3 α (respectively 1 β , 2 β and 3 β ), and that the fully-differentiated cells eventually die and are shed into the lumen at a rate γ (see β , 3 β and γ are the rates at which these processes occur.

The dynamics of the three cell populations can then be described by a system of three coupled differential equations. The net growth rates of the stem ( 0 N ) and transit amplifying ( 1 N ) cells are, respectively,

2 1 3 α α α α - - = and 2 1 3 β β β β - - =
. The equilibrium situation in the normal crypt requires that α = 0, and that β < 0. The initiation and progression of a cancer are determined by genetically or epigenetically based changes in theα and β rates that disrupt the normal balance of the three types of cells and eventually lead to exponential unlimited growth, when either α or β or both exceed 0. Johnston et al. [START_REF] Johnston | Mathematical modeling of cell population dynamics in the colonic crypt and in colorectal cancer[END_REF][START_REF] Johnston | Examples of mathematical modeling: tales from the crypt[END_REF] showed that plausible models of cancer progression required the introduction of saturating feedback terms, which were introduced by replacing the differentiation rates 2 . These equilibria correspond to benign or adenomatous stages of tumour progression. Only when either α or β exceed their respective limits, will exponential growth representing the full development of a cancer occur. When α first exceeds its limit, the CSCs, which drive the exponential growth of the cancer, are derived from the normal tissue stem cells. However, if β first exceeds its limit then the CSCs are derived from the transit amplifying cells. Johnston et al. [START_REF] Johnston | Examples of mathematical modeling: tales from the crypt[END_REF] showed that if 0 0 = m , so that there is no saturation of the feedback for the stem cells representing, plausibly, greater feedback constraint on them than on the transit amplifying cells, CSCs will always be derived from the transit-amplifying cells. This may be, as we have already mentioned, the more usual situation.

Modelling the exponential growth phase

Johnston et al. [START_REF] Johnston | Mathematical modeling of cell population dynamics in the colonic crypt and in colorectal cancer[END_REF][START_REF] Johnston | Examples of mathematical modeling: tales from the crypt[END_REF] , as discussed above, showed that their model could lead to instability either through growth of the tissue stem cells ( 0 N ) driving proliferation, or through the semi-differentiated cells ( 1 N ) driving growth. We now consider both these cases in turn.

In order to obtain estimates of the proportion of CSCs in a tumour based on the above model, we have to consider the behaviour of the differential equations when 0 N , ( )

( ) ( ) ( ) (3) . d d (2) , d d (1)
, d d 1 1 1 2 2 2 0 0 0 2 1 1 1 1 0 0 0 0 N m k N t N N m k N m k t N N m k t N + + - ≈ + + - ≈ - ≈ β γ α β α
The parameters in these equations now represent the ultimate values reached at the final exponential growth phase of the cancer. These equations can be explicitly solved to obtain a general expression for the limiting ratios of If the CSCs are derived from a normal tissue stem cell, then ) (

2 1 0 0 N N N N + +
is the proportion of CSCs in the tumour. This proportion can be expressed in the form ) 1 ( 1 P + , where P is given by . 1

0 0 1 1 2 1 1 0 0 0 0 2 ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ + - + + + - - + = γ α β β α α m k m k m k m k m k P (4)
(see supplementary information). Thus, depending on the value of the various parameters, the proportion of CSCs could be either close to 1 (when P is very small) or near to 0 (when P is very large). In Figure 2 , where P is now given by

γ β β + - + = 1 1 1 1 2 m k m k P . (5)
(see supplementary information). When the maximum rate of differentiation of the CSCs (

1 1 2 m k + β
) is small, then P can be near zero and the proportion of CSCs near 1. On the other hand, when the CSCs can still differentiate well, and their maximum growth rate together with the rate of fully differentiated cell removal (β -k 1 /m 1 + γ) is small relative to this, P will be larger and so the proportion of CSCs smaller. This agrees well with the clinical expectation that the less the propensity of a tumour to differentiate, the more aggressive it is likely to be and the higher the proportion of CSCs it is likely to contain.

Discussion

While a number of models exist for the spatiotemporal dynamics of cells in crypts (see, for example, [START_REF] Van Leeuwen | An integrative computational model for intestinal tissue renewal[END_REF] and references therein) or, as in the present model, implicitly including spatial constraints in a temporal model (see, for example, 26 ,27 ) to our knowledge, there has been no previous attempt to use mathematical modelling to predict the proportion of CSCs in a tumour.

We have shown that, when our previously analysed model of cell turnover in the colorectal crypt is analysed at the exponential growth phase of a cancer, it is possible to explain almost any proportion of CSCs in a tumour under quite plausible assumptions. This is in marked contrast to the previously widely made assumption that CSCs necessarily constitute a small proportion of the cells in a cancer. Our result is supported by specific experimental evidence at least in melanomas [START_REF] Quintana | Efficient tumour formation by single human melanoma cells[END_REF] , lymphoid and myeloid malignancies [START_REF] Kelly | Tumor growth need not be driven by rare cancer stem cells[END_REF] , and colorectal cancer derived cell lines [START_REF] Yeung | Cancer stem cells from colorectal cancer-derived cell lines[END_REF] . It is, of course, entirely possible that the average proportion of CSCs in a cancer may vary from one tissue to another. In any case, according to our model, the proportion of CSCs depends on the balance between their rates of growth and differentiation, and this is just as would be expected from clinical and experimental data.

Fig. 1 Figure 1 .

 11 Fig.1).

k and 1 k

 1 represent the speed of response of the feedback, while the positive constants m 0 and m 1 represent feedback saturation.With this model, as first suggested by Tomlinson and Bodmer[START_REF] Tomlinson | Failure of programmed cell death and differentiation as causes of tumors: some simple mathematical models[END_REF] , there can be a series of new stable equilibria with increased numbers of stem cells or transit amplifying cells, so long as the net growth rates α and β do not exceed, respectively,

1 N and 2 N

 12 are very large. It can be shown that the three coupled differential equations describing the model with feedback saturation then approximate to;

3 α

 3 we illustrate some numerical examples which show how variations in the parameter P , or in any of its constituent components, such as , can allow the proportion of CSCs to vary substantially.

Figure 2 . 3 α

 23 Figure 2. Illustrations showing how the percentage of CSCs in a tumour, when derived from the tissue stem cell, can vary depending on the parameters: (i) as the parameter P varies according to (4); and (ii) as the stem cell renewal rate

1 1

Acknowledgements We acknowledge the support provided by the funders of the Integrative Biology project: the EPSRC (GR/S720231/01) and IBM. M.D.J. was supported by an EPSRC DTA graduate studentship (Award No. EP/P500397/1) and the Sarah and Nadine Pole Scholarship, which are gratefully acknowledged. W.F.B. was supported by a program grant from Cancer Research UK, and is grateful for helpful discussions with Trevor Yeung and Shaan Gandhi. P.K.M. was partially supported by a Royal Society Wolfson Research Merit Award.