A semantic space for modeling children's semantic memory

A preliminary model based on a child corpus

In contrast to many LSA semantic spaces in the literature which are based on domain -specific corpora, we chose to build a general child corpus intended to model children's semantic memory [START_REF] Denhière | Psychologie cognitive et compréhension de texte: Une démarche théorique et expérimentale[END_REF]) and to offer a layer of basic semantic associations on top of which computational models of children cognitive processes can be designed and simulated (Lemaire, Denhière, Bellissens & Jhean -Larose, to appear).

Develop m e n t al data

We possess little direct information on the nature and the properties of the semantic memory of the children from 7 to 11 year-old (Howe & Courage, 2003;Murphy, McKone & Slee, 2003;Towse, Hitch & Hutton, 2002;De Marie & Ferron, 2003;Cycowicz, 2000). However we can refer to studies relating to the vocabulary acquisition for this period of cognitive development to build an approximation of children's semantic memory and to work out a corpus correspo n ding roughly to oral and written linguistic materials that a 7-11 year -old child is exposed to [START_REF] Lambert | NOVLEX: Une base de données lexicales pour les élèves du primaire[END_REF][START_REF] Lété | MANULEX: A grade -level lexical database from french elementary -school readers[END_REF].

From a theoretical point of view, the question: "How children learn the meaning of words?" has received different kinds of answers. [START_REF] Bloom | How Children learn the meanings of words[END_REF] argued that the mind does not have a module for language acquisition, that the processes of association and imitation are not sufficient to explain word learning that requires rich mental capacities: conceptual, social, and linguistic, that interact in complicated ways. As [START_REF] Gillette | Human simulations of vocabulary learning[END_REF] pointed out, "lexical and syntactic knowledge in the child, far from developing as separate components of an acquisition procedure, interact with each other and with the observed world in a complex, mutually supportive, series of bootstrap ping operations" (p. 171). In connectionist modeling of language acquisition (see [START_REF] Elman | An alternative view of the mental lexicon[END_REF][START_REF] Shultz | Computational developmental psychology[END_REF], [START_REF] Li | Early lexical development in a self-organizing neural network[END_REF] developed DevLex, a self-organizing neural network model of the development of the lexicon, designed to combine the dynamic learning properties of connectionist networks with the scalability of represental models such HAL [START_REF] Burgess | Modelling parsing constrainsts with high dimensional context space[END_REF] or LSA [START_REF] Landauer | A solution to Plato's problem: the Latent Semantic Anlysis Theory of the Acquisition, Induction and Representation of Knowledge[END_REF].

Finally, as [START_REF] Louwerse | How children learn the meaning of words and how LSA does it (too)[END_REF] emphasized, children likely do not learn the meaning of words through learning words, but through different forms of discourse and by understanding their relation in context. In consequence, these authors assume that "LSA is how all language processing works and that LSA can be considered a model of how children learn the meaning of words" (p. 302).

From these points of view, whatever the complexity of the processes implicated in language acquisition, it should be possible to reproduce different states of meaning acquisition by estimating two things: the mean normative vocabulary of children and the written data children are exposed to.

Then it should be possible to construct corpora trained in a model which take into account complex interaction of usage contexts.

One has estimated the quantitative aspects of vocabulary development. [START_REF] Landauer | A solution to Plato's problem: the Latent Semantic Anlysis Theory of the Acquisition, Induction and Representation of Knowledge[END_REF] wrote that "it has been estimated that the average fifth grade child spends about 15 minutes per day reading in school and another 15 out of school reading books, magazines, mail and comic books [START_REF] Anderson | Growth in reading and how children spend their thime outside of school[END_REF][START_REF] Taylor | Time spent reading and reading growth[END_REF]). If we assume 30 minutes per day total for 150 school days and 15 minutes per day for the rest of the year, we get an average of 21 minutes per day. At an average reading speed of 165 words per minute, which may be an overestimate of natural, casual rates, and a nominal paragraph length of 70 words, they read about 2,5 paragraph per minute, and about 50 per day." [START_REF] Ehrlich | Le développeme nt des connaissances lexicales à l'école primaire[END_REF], estimated the mean vocabulary of 2.538 French children in 4 scholar grades (from 2 nd through 5 th ) and from 4 social and economic classes (senior executives, medium ranking executives, employees and workers) by using a judgement task of lexical knowledge (scaled in five levels, from "never heard" to "I know that word very well and I use it frequently") and a definition task ("tell all the senses of that word"). The verbal materials was made of 13.500 root words (63 % substantives, 17% verbs and 20% adjectives and adverbs) assumed to be representative to a general adult vocabulary (First year's college students).

Then, the 13.500 root words were judged by 150 adults on a five levels scale and the 2.700 better known and more frequently used words were taken to make part of the experimental materials submitted to children, to test the extent of their vocabulary as a function of age and social and economic classes. The results showed that the number of totally unknown root words decreased of about 4.000 from 2 nd through 5 th grade, the number of very well known root words increased of only 900 and the number of medium known root words increased of approximativelly 3.000. According to the authors, the frequently used vocabulary does not vary so much over primary school grades, but children are learning a lot of new words that, for a major part, they are unlikely to use [START_REF] Ehrlich | Le développeme nt des connaissances lexicales à l'école primaire[END_REF]. The meaning knowledge level of substantives and verbs were equivalent whatever the age of the children, and were higher than knowledge level of adjectives and adverbs. Finally, the mean vocabulary was larger for favored classes (i.e., a mean difference of 600 words between the two extreme classes) and these differences kept the same over the 4 scholar grades. Moreover, after the results from the definition task, the vocabulary of the children was enriched by approximativelly 1.000 root words each school grade, the increase from 2 nd though 5 th grade was about 3.000 [START_REF] Ehrlich | Le développeme nt des connaissances lexicales à l'école primaire[END_REF].

More recently, [START_REF] Biemiller | Estimating root word vocabulary growth in normative and advantaged populations: Evidence for a common sequence of vocabulary acquisition[END_REF][START_REF] Biemiller | Vocabulary: Needed if more children are to read well[END_REF], [START_REF] Biemiller | Estimating root word vocabulary growth in normative and advantaged populations: Evidence for a common sequence of vocabulary acquisition[END_REF]), Biemiller & Slonim (2001) presented results that confirmed most of the pionner results of [START_REF] Ehrlich | Le développeme nt des connaissances lexicales à l'école primaire[END_REF]. In short, Biemiller & Slonim (2001), referring to the Dale and O'Rourke's Living Word Vocabulary (1981), estimated that in the 2 nd grade the mean normative vocabulary was 5.200 root words, increasing to approximately 8.400 root words by 5 th grade. This reflects acquiring about 2.2 words per day from ages 1 through 8 (end of grade two) and 2.4 words per day during ages 9 through 12. In other words, an average child learns between 800 and 900 root words a year, a figure that is close to the one obtained by [START_REF] Anglin | Vocabulary development: A morphological analysis[END_REF].

There is evidence that the vocabulary is acquired in largely the same order by most children. [START_REF] Biemiller | Estimating root word vocabulary growth in normative and advantaged populations: Evidence for a common sequence of vocabulary acquisition[END_REF] have found that when vocabulary data are ordered by children's vocabulary levels rather than their grade level, they can clearly identify ranges of words known well (above 75%), words being acquired (known between 25% and 74%) and words little known .

At any given point in vocabulary acquisition, a child is likely to be learning root words from about 2.000 to 3.000 words in a sequence of 13.000 to 15.000 words. This makes the construction of a "vocabulary curriculum" plausible. Unfortunately, although these findings imply the existence of a well-defined sequence of word acquisition, a complete sequential listing of the 13,000-15,000 root words expected at the level of twelfth grade cannot now be furnished (for more details, see [START_REF] Biemiller | Vocabulary: Needed if more children are to read well[END_REF][START_REF] Biemiller | Size and sequence in vocabulary development: Implications for choosing words for primary grade vocabulary instruction[END_REF].

Our corpus

Various kinds of written data children are exposed to have to be represented in our corpus. We gathered texts for a total of 3.2 million words. We could have gathered many more texts but we are concerned with cognitive plausibility. Our goal was to build a semantic space which reproduces as close as possible the verbal performa nces of a 7 to 11 year-old child. Moreover, we are not only concerned with mimicking the representation of the semantic memory, but also its development, from raw written data to the semantic representation of words. Therefore, the type and size of the input are importan t factors.

Children are exposed to various kinds of written data: storybooks, schoolbooks, encyclopedias, etc. It is very hard to estimate the proportion of each source to the total exposure to print. Actually, the main problem is that children have been exposed to language long before they can read: they learn the meaning of some words through exposure to speech, not to mention the perceptual input. This is a well-known limitation of LSA [START_REF] Glenberg | Symbol grounding and meaning: a comparison of high-dimensional and embodied theories of meaning[END_REF] but it is less of a problem with adult corpora. Indeed, the proportion of words learned from reading is much higher for adults than for children. Therefore, we need to take this problem into account in the design of child corpora by trying to mimic this kind of input. We could have used spoken language intended for children, but these kinds of data are less formal than written language and thus harder to process. We ended up with gathering children's productions, a kind of language which is closer to basic spoken language than stories or textbooks. In addition, we decreased the significance of textbooks and the encyclopedia, because these sources of information affect the children's knowledge base after they have learned to read.

Altogether, the child corpus consists of stories and folk tales written for children (~1.6 million words), children's own written productions (~800,000 words), reading textbooks (~400,000 words) and a children's encyclopedia (~400,000 words).

The size of the corpus is another important factor. It is very hard to estimate how many words we process every day. It is not easy to estimate this number from the literature since, as we mentioned earlier, most studies are based either on just root words or on the number of words children know and not those they were exposed to. Then, according to [START_REF] Landauer | A solution to Plato's problem: the Latent Semantic Anlysis Theory of the Acquisition, Induction and Representation of Knowledge[END_REF] estimate, we consider a relevant corpus size to be tens of million words for adults, and several million words for children around 10 years of age. The size of the corpus we are presenting in this paper is 3.2 million words. After processing this corpus by LSA, we compared it with human data.

Comparison of semantic similarities with human data

In order to validate the specific child semantic space Textenfants , we used four more and more constraining tests: association norms, semantic judgmen ts, a vocabulary test and memory tasks. First, we investigated whether our semantic space could account for word associations produced by children who were provided with words varying in familiarity. Therefore, the first test compares the performances of Textenfants on French verbal association norms recently published by [START_REF] De La Haye | Normes d'association verbale chez des enfants de 9, 10 et 11 ans et des adultes[END_REF]. Second, we compared the performances of Textenfants with grades 2 and 5 children's judgmen ts of semantic similarity between couples of words extracted from stories. Third, we tested whether our semantic space is able to represent definitions. LSA is often criticized for its ability to account for syntagmatic associations but not paradigmatic ones [START_REF] French | Four Problems with Extracting Human Semantics from Large Text Corpora[END_REF]. Like [START_REF] Landauer | Introduction to Latent Semantic Analysis[END_REF] did with the TOEFL test, we compared LSA scores to perfor mances of four groups of children. The task consisted in choosing the correct definition from a set of four definitions (correct, close, distant and unrelated). We believe that this test is more constraining than the first one because definitions could be either words, phrases or sentences but no dictionary was part of this corpus. Fourth, we used the semantic space to assess the children's performances of recall and summarization. We revisited results of nine prior experiments and compared the number of propositions recalled to the cosine measure between the source text and the text produced by each participant. To the extent that these are correlated Textenfants can be used to assess verbal protocols without resorting to the tedious propositional analysis.

Associations nor ms

The first experiment is based on verbal association norms published by [START_REF] De La Haye | Normes d'association verbale chez des enfants de 9, 10 et 11 ans et des adultes[END_REF]. Because of previous results are based on children from grades 2 to 5, our interest here concerns the 9 year-old norms. Two-hundred stimulus printed words (144 nouns, 28 verbs and 28 adjectives) were provided to 100 9-years -old children. For each word, participants had to write down the first word that came to their mind. The result is a list of words, ranked by frequency. For instance, given the word eau (water ), results are the following:

• boire (drink ): 22%

• mer (sea ): 8%

• piscine (swim ming pool): 7% ...

• vin (wine ): 1%

• froid (cold ): 1%

• poisson (fish ): 1% This means that 22% of the 9-year old children provided the word boire (drink ) when given the word eau (water ). This value can be used as a measure of the strength of the association between the two words. These association values were compared with the LSA cosine between word vectors: we selected the three highest -ranked words as well as the three lowest -ranked (vin, froid, poisson in the previous example). We then measured the cosines between the stimulus and the highest -ranked, the 2 nd highest, the 3 rd -highest, and the mean cosine between the stimulus word and the three lowest -ranked. Results are presented in Table 1. Student t-tests show that all differences are significant (p < .05). This means that our semantic space is not only able to distinguish between the strong and weak associates, but can also discriminate the first -ranked from the secondranked and the latter from the third -ranked.

The correlation with human data is also significant (r(1184)=.39, p<.001).

Actually, two factors might have decreased this value. First, although we tried to mimic what a child has been exposed to, we could not control the frequencies with which each word occurred in the corpus. Therefore, some words might have occurred with a low frequency, leading to an inaccurate semantic representation. When the previous comparison was performe d on the 20% of words with lower LSA weights (those words for which LSA has the most knowledge), the correlation was much higher (r(234) =.57, p<.001).

The second factor is the agreement among participants: when most children

provide the same answer to a stimulus word, there is high agreement, which means that both words are very strongly associated. However, there are cases when there is almost no agreement: for instance, the first three answers to the word bruit (noise ) are crier (to shout ) (9%), entendre (to hear ) (7%) and silence (silence ) (6%). It is not surprising that the model correspon ds better to the children's data in case of a high agreement, since this denotes a strong association that should be reflected in the corpus. In order to select answers whose agreement was higher, we measured their entropy. When we selected 20% of the items with the lowest entropy, the correlation increased: r(234)=.

48, p<.001.

We also compared these results with the several adult semantic spaces, a literature corpus and four French newspaper corpora. Results are presented in Table 2. In spite of much larger sizes, all adult semantic spaces correlate worse than the children's semantic space with the data of the participants in the study. Statistical tests show that all differences between the children model and the other semantic spaces are significant (p<.03). All these results show that the degree of association between words defined by the cosine measure within the semantic space seems to correspon d quite well to children's judgments of association.

Semantic judg m e n ts

A second test consisted in comparing TextEnfants with two groups of forty five children's (Grade 3 vs grade 5) results in a semantic distance judgmen t task (Denhière & Bourguet, in preparation). We asked participants to judge on a five points scale the semantic similarity between two words extracted from a story used in the Diagnos™ tests [START_REF] Baudet | Le diagnostic du fonctionne me nt cognitif dans la compréhension de textes[END_REF]. For each of the 7 stories selected, all the possible noun -noun couples were constructed ("giant -woman", "forest -woman", "house -woman" and so on) and had to be judged. For each couple, we obtained an average similarity value for each grade that we compared with LSA cosines for the two words of the couples.

Judgments were significatively correlated between the two groups of children (ranged from .80 to .95 as function of stories) and correlations between LSA cosines and children's judgements were all but one ("Giant" story) significant (see table 3). In conclusion, the degree of association between words (test 1) and the semantic distance between concepts (test 2), defined by the cosine measure within the semantic space TextEnfants fit quite well to children's productions and judgments.

Vocabula r y test

The third experiment is based on a vocabulary test composed of 120 questions (Denhière, Thomas, Bourguet & Legros, 1999). Each question is composed of a word and four definitions: the correct one, a close definition, a distant definition and an unrelated definition. For instance, given the word pente (slope ), translations of the four definitions are:

• tilted surface which goes up or down (correct);

• rising road (close);

• vertical face of a rock or a mountain (distant) ;

• small piece of ground (unrelated).

Participants were asked to select what they thought was the correct definition.

This task was performe d by four groups of 30 children from 2 nd , 3 rd , 4 th and 5 th -grades. These data were compared with the cosines between a given word and each of the four definitions. Altogether, 116 questions were used because the semantic space did not contain four rarely occurring words. We also investigated a possible effect of corpus lemmatization. French uses more word forms than English. This fact could reduce the power of LSA because there might be less opportunity to encounter relevant contexts.

Replacing all words by their lemma could therefore improve the representation of word meaning: instead of having N 1 paragraphs with word P 1 , N 2 paragraphs with word P 2 ,... N p paragraphs with word P n , we could have N 1 +N 2 +...+N p paragraphs with word P, which could be better from a statistical point of view. All forms of a verb are therefore represented by its infinitive, all forms of a noun by its nominative singular, and so forth. We used the Brill tagger on French files developed by the CNRS-ATILF laboratory at Nancy, France, as well as the Namer lemmatizer. However, results were worse than before when all words were lemmatized. Verb lemmatization also resulted in no improvment . Hence, lemmatization proved to be of no help in the present case.

Then, we modified the lemmatizer in order to lemmatize only verbs and found better results, almost exactly corresponding to the 2 nd -grade data. This can be due to the fact that verb lemmatization groups together forms that have the same meaning. However, the different forms of a noun do not have exactly the same meaning. For instance, flower and flowers are not argument s of the same predicates. In our semantic space, the cosine between rose and flower is .51 whereas the cosine between rose and flowers is only .14. Flower and flowers do not occur in the exact same contexts. Another example can be given from the neighbors of bike and bikes . First three neighbors of bike are handlebar , brakes and pedals whereas first three neighbors of bikes are motorbikes , trucks and cars . Bike and bikes do not occur either in the same contexts. Therefore, representing them by the same form probably confuses LSA.

Memor y tasks

The last experiment is based on recall or summary tasks [START_REF] Thomas | Diagnostic du fonctionne ment cognitif, évaluation dynamique et remédiation[END_REF]. Three groups of children (mean age of 8,3 years) and six groups of adolescents (between 16 and 18 years old) were asked to read a text and write out as much as they could recall, immediately after reading or after a fixed delay of one week. For three of these groups, participants were asked to write a summary. We used seven texts. We tested the ability of the semantic representations to estimate the amount of knowledge recalled. This amount is classically estimated by means of a propositional analysis: first, the text as can be used to assess text comprehension more quickly than propositional analysis, which is a very tedious task.

Corpus stratification for develop me ntal studies

The corpus presented so far contains the kind of texts a child is exposed to, but it does not reproduce the order in which texts are processed over a child's life. Actually, it would be very valuable to have a corpus in which paragrap hs are sorted according to the age they are intended for, which would make it possible to obtain a corpus for virtually any age. Comparing the model of semantic memory (or any processing model based on it) with data from children would be much more precise. In addition, it would then be possible to simulate the development of semantic memory.

We proceeded in two steps: first, we gathered more texts that were intended for a specific age and second, we sorted every paragraph of each category according to a readability measure.

Gathering texts for specific age

We defined four age levels: 4 to 7 years, 7 to 11 years, 11 to 18 years and adults (over 18 years). The goal was to build a well-rounded semantic space that includes lexical, encyclopedic and factual information. Lexical information is given by dictionaries. Encyclopedic information is provided by schoolbooks and encyclopedia. Factual information is obtained from stories and novels. For each age level, we therefore collected French texts in each of the following categories: children's written productions, dictionary, encyclopedia, textbooks and stories or novels. Each level is included in the next one. Level 1 is therefore composed of productions from 4 to 7 year-old children, a dictionary and an encyclopedia for 4 to 7 year-old children, 1 st grade reading textbooks and stories for 4 to 7 year-old children. Level 2 is composed of all the texts of level 1 plus productions from 7 to 11 year-old children, a dictionary and an encyclopedia for 7 to 11 year-old children, reading texts and stories for 7 to 11 year-old children, etc. For adults, the daily newspaper Le Monde was used in place of textbooks.

Sorting paragr a p h s according to a reada bility measu re

In order to be more precise, all paragraphs of a given level were sorted according to the age they best correspond to. We relied on a readability measure defined by [START_REF] Mesnager | Lisibilité des livres pour enfants: un nouvel outil?[END_REF][START_REF] Mesnager | Pour une étude de la difficulté des textes: la lisibilité revisitée[END_REF], which has been carefully standar dized. This measure is based on the percentage of difficult words and the mean length of sentences. Difficult words are those that are not part of a list of 32,000 French common words. The formula is the following:

readability = 3/4

percentage of difficult words + 1/4 mean sentence length

This measure is very rough, but we used it merely as a tool for sorting all paragrap hs within each level. Thus we computed the readability measure for every paragraph of each category. This work is very preliminary. As a rough test, we found that for each information source, the mean measure for level N was higher than the mean measure for level N-1, which is satisfactory.

Applications of the model of semantic memory

In this section, we present two applications of this model of semantic memory. The first one consists in comparing the relationships between co-occurrence frequency and LSA similarities. The second one aims at linking this model of semantic memory to a model of comprehension based on the construction -integration model designed by Kintsch (1988[START_REF] Kintsch | Comprehension: a paradigm for cognition[END_REF].

Studying the develop m e n t of semantic similarities

The semantic similarity of two words (or, stated differently, their associative strength) is classically reduced to their frequency of co-occurrence in language: the more frequently two words appear together, the higher their similarity. This shortcut is used as a quick way of estimating word similarity, for example, in order to control the material of an experiment, but it also has an explanatory purpose: people tend to judge two words as similar because they were exposed to them simultaneously. Undoubtedly, the frequency of co-occurrence is correlated with human judgments of similarity [START_REF] Spence | Lexical co-occurrence and association strength[END_REF]). However, several researchers have questioned this simple relation [START_REF] Bellissens | Word order or environme nt sharing: a comparison of two semantic memory models[END_REF][START_REF] Burgess | Explorations in context space: word, sentences, discourse[END_REF]. The goal of this simulation is to use our semantic space to study the relation between co-occurrence and similarity.

An ideal method to study the relation between co-occurrence and similarity would consist in collecting all of the texts subjects have been exposed to and comparing their judgments of similarity with the cooccurrence parameters of these texts, a task that is obviously impossible. One could think of a more controlled experiment, by asking participants to complete similarity tests before and after text exposure. The problem is that the mental construction of similarities through reading is a long-term cognitive process, which would probably not be apparent over a short period.

It is also possible to count co-occurrences in representative corpora, but that would give only a global indication a posteriori. Thus, we would learn nothing about the direct effect of a given first or second -order co-occurrence on semantic similarity. It is useful to know precisely the effect of direct and highorder co-occurrences during word acquisition. Assume a person X who has been exposed to a huge set of texts since learning to read. Let S be the judgmen t of similarity of X between words W1 and W2. The questions we are interested in are:

• what is the effect on S of X reading a passage containing W1 but not

W2?

• what is the effect on S of X reading a passage containing W1 and W2?

• what is the effect on S of X reading a passage containing neither W1 nor W2, but words co-occurring with W1 and W2 (second -order cooccurrence)?

• what is the effect on S of X reading a passage containing neither W1 nor W2, but third -order co-occurring words?

Our simulation follows the evolution of the semantic similarities of 28 pairs of words over a large number of paragraphs, according to the occurrence values. We started with a corpus size of 2,000 paragraphs. We added one paragrap h, ran LSA on this 2001 -paragraph corpus and, for each pair, computed the gain (positive or negative) of semantic similarity due to the new paragrap h and checked whether there were occurrences, direct cooccurrences or high-order co-occurrences of the two words in the new paragrap h. We then added another paragraph, ran LSA on the 2002 -paragrap h corpus, etc. Each new paragraph was simply the following one in the original corpus. More precisely, for each pair X-Y, we put each new paragraph into one of the following categories:

• occurrence of X but not Y;

• occurrence of Y but not X;

• direct co-occurrence of X and Y;

• second -order co-occurrence of X and Y, defined as the presence of at least three words which co-occur at least once with both X and Y in the current corpus;

• third -or-more -order co-occurrence, which forms the remainder (no occurrence of X or Y, no direct co-occurrence, no second -order cooccurrence). This category represents three -or-more co-occurrences because paragraphs whose words are completely neutral with X and Y (that is they are not linked to them by a high -order co-occurrence relation) do not modify the X-Y semantic similarity.

We stopped the computation at the 13,637th paragraph. 11,637 paragraph s were thus traced. This experiment took three weeks of computation on a 2

GHz computer with 1.5 Gb RAM. As an example, Figure 2 describes the evolution of similarity for the two words acheter (buy ) and magasin (shop ).

This similarity is -.07 at paragraph 2,000 and increases to .51 at paragrap h 13,637. The curve is quite irregular: there are some sudden increases and decreases. Our next goal was to identify the reasons for these variations. For each pair of words, we partialed out the gains of similarity among the different categories. For instance, if the similarity between X and Y was .134

for the 5,000 -paragraph corpus and .157 for the 5,001 -paragraph corpus, we attributed the .023 gain in similarity to one of the five previous categories. We then summed up all gains for each category. Since the sum of the 11,637 gains in similarity is exactly the difference between the last similarity and the first one, we ended up with a distribution of the total gain in similarity among all categories. For instance, for the pair acheter(buy)-magasin(shop) , the .58 (.51 -(-.07)) total gain in similarity is partialed out in the following way:

• -.10 due to occurrences of only acheter(buy) ;

• -.19 due to occurrences of only magasin(shop) ;

• .73 due to the co-occurrences;

• .11 due to second -order co-occurrences;

• .03 due to third -or-more -order co-occurrences. This means that the paragraphs containing only acheter(buy) contributed all together to a decrease in similarity of .10. This is probably due to the fact that these occurrences occur in a context which is different to the magasin(shop) context. In the same way, occurrences of magasin(shop) led to a decrease in the overall similarity. Co-occurrences tend to increase the similarity, which is expected, and high-order co-occurrences contribute also to an increase.

We performed the same measuremen t for all 28 pairs of words. These pairs were selected from the 200 items of the association task presented earlier and their first -ranked associated word, as provided by children. We kept only words that appeared at least once in the first 2,000 paragraphs in order to have the same number of semantic similarities for all pairs. Average results are the following:

• -.15 due to occurrences of the first word;

• -.19 due to occurrences of the second word;

• .34 due to the co-occurrences;

• .05 due to second -order co-occurrences;

• .09 due to third -or-more -order co-occurrences.

First of all, we found pairs of words that never co-occur (e.g. farine(flour)gâteau(cake) ) even though their semantic similarity increases. Another result is that, except in a few cases, the gain in similarity due to a co-occurrence is higher than the total gain in similarity. This result occurs because of a decrease due to occurrences of only one of the two words (-.15 and .-19). In addition, high -order co-occurrences play a small but significant role: they tend to increase the similarity (.14 in total).

Modeling text compr eh en sion on the basis of the seman tic memo r y model

In a second application, we use our semantic memory model as a componen t of a fully automatic model of text comprehension, based on the constructionintegration (CI) model [START_REF] Kintsch | Comprehension: a paradigm for cognition[END_REF], a predication mechanis m [START_REF] Kintsch | Predication[END_REF][START_REF] Lemaire | Contextual effects on metaphor comprehension: experiment and simulation[END_REF] and a model of the episodic buffer. This model is implemented in a Perl program that takes as input a text divided into propositions (Lemaire et al, to appear). Figure 3 shows the general architecture. Let us explain the flow of information which is an operational approximation of the CI model. Each proposition is considered in turn. First, the LSA semantic space (also called semantic memory) is used to provide terms that are semantically similar to the propositions and their components, thus simulating the process by which we automatically activate word associates in memory while reading. A fixed number of associates is provided for the predicate, but also for each of the arguments. For instance, given the proposition carry(truck, food) correspon ding to the sentence The truck is carrying bikes , our semantic space provides the terms transport , kilometers and travel for the proposition, the terms car , garage and vehicle for the argument truck and the terms motorbikes , trucks and cars for the argumen t bikes . Associates for the argument s are simply the terms whose cosine with the arguments in the semantic space is higher. Associates for the predicate require a bit more calculation since only those that are close enough (beyond a given threshold) to at least one of the arguments are kept. This algorithm comes from Kintsch's predication model [START_REF] Kintsch | Predication[END_REF]. In our example, the three associates transport , kilometers and travel were kept because they are similar enough to the truck or bikes . Not all associates are relevant within the context, but this is not a problem because the next phase will rule out those that are not related to the current topic. Actually, all the terms in working memory (none for the first sentence) are added to the current proposition and all its associates. As we will explain later, relevant propositions coming from episodic memory can also be added.

All

these terms and propositions are processed by the construction / i ntegration phase of Kintsch's model. The LSA semantic space is used once more to compute the similarity weights of links between all pairs of terms or propositions. For instance, the weight of truck /bikes is .67, the weight of carry(truck, bikes)/travel is .16, etc. Next, a specific spreading activation mechanism is used to give activation values to terms according to the weight of their connection with other terms. Those that are the most strongly linked to other terms will receive high activation values. For instance, the term garage in the previous example is weakly linked to all other terms or propositions. Therefore, this term will be given a low association value and will be droppe d out.

The most highly activated items are stored in working memory. Three strategies are available:

• either a fixed number of items is selected, following Baddeley's model (2000); or

• a maximum sum of activation is defined, which is distributed among the items [START_REF] Just | A capacity theory of comprehension: Individual differences in working memory[END_REF]; or

• only those items whose activation values are above a given threshold are selected.

Selected elements will be added later to the next proposition and its associates. They are also stored in episodic memory. This memory is the list of all terms or propositions already encountered, either because they were part of text propositions, or because they were provided by semantic memory as associates. Terms or propositions are attached to an activation value in episodic memory. This value is initially their activation value in working memory, but a decay function lowers this value over time. This activation value is increased each time a new occurrence of a term or proposition is stored in episodic memory. Both values are then combined according to functions we will not explain here. What is important is that elements in episodic memory can be recalled by the construction phase in case they are similar enough to the current proposition. The semantic space is then used once more to compute similarities and to decide whether elements in episodic memory are recalled or not. This last process simulates the fact that there was a digression in the text, leading to the fact that the previous propositions were droppe d out from working memory. When the digression ends, these propositions will be recalled from episodic memory because they will be similarities between all pairs of words are computed. After the integration step, working memory is:

meow(cat) (1.00)

grow(gardener,roses) (.967)

cat (.795)

meow (.776)

All terms related to the first sentence (border , garden , ...) were removed from working memory, because the second sentence is not related to the first one.

However, the entire proposition is still there.

The third proposition is throw(man,flower) . Flowers , bouquet , roses and violets are back to working memory, because they are close to the argument flower .

Terms that are neighbors of throw but also close to man or flower are: To sum up, the LSA semantic space is used three times: first, to provide associates to the current proposition and its arguments; second, to compute the weights of links in the construction phase and third, to compute similarities between the current proposition and the episodic memory items for their possible reactivation in working memory.

The main parameters of that model are:

• the minimal and maximal weight thresholds for terms, in order to only consider terms for which LSA has enough knowledge;

• the number of associates provided by the LSA semantic space;

• the similarity threshold for the predication algorithm;

• the strategy for selecting items in working memory after the integration step;

• the decay and updating functions of episodic memory.

This program can be used with any semantic space, but, when combined with the semantic space described in this paper, it should be very useful for the study of children text comprehension.

Conclusion

In this paper, we presented a semantic space that is designed to represent children's semantic memory. It is based on a multi-source corpus composed of stories and tales, children's productions, reading textbooks and a children's encyclopedia. Our goal is to build a general semantic space as opposed to domain -specific ones. Results of the four tests we performe d (comparison with association norms, semantic judgments, vocabulary test, recall and summary tasks) are promising (Denhière & Lemaire, 2004). The next step is to simulate the development of this semantic memory in order to reproduce develop mental changes in performa nce on these tests among children aged 4 to 7 years to adolescence. One of the goals would be to reproduce the effect of prior knowledge on text comprehension [START_REF] Caillies | The intermediate effect: interaction between prior knowledge and text structure[END_REF][START_REF] Caillies | The effect of prior knowledge on understa nding from text: evidence from primed recognition[END_REF].

The semantic space we constructed was linked to a comprehension model derived from the construction -integration model [START_REF] Kintsch | Comprehension: a paradigm for cognition[END_REF]. Like the CI model, our model uses semantic memory to activate the closest neighbors of the current concept or proposition, to select the most relevant elements and to keep the most activated in working memory. In addition, several models of short -term memory are implemented and an episodic buffer is used to store ongoing information and provide relevant prior items to working memory.

Our current work consists in adding a long-term working memory [START_REF] Ericsson | Long-term working memory[END_REF] and a generalization process based on memory traces from the episodic buffer (Bellissens & Denhière, 2004;[START_REF] Denhière | Psychologie cognitive et compréhension de texte: Une démarche théorique et expérimentale[END_REF]).

  Guy Denhière, CNRS (UMR 6146) & University of Aix-Marseille1, France Benoît Lemaire, Leibniz -IMAG (CNRS UMR 5522), University of Grenoble, France Cédrick Bellissens, University of Paris VIII, France Sandra Jhean -Larose, IUFM Paris & University of Paris VIII, France

Figure 1

 1 Figure 1 displays the average percentage of correct, close, distant and

Figure 1 .

 1 Figure 1. Percentage of answers for children and model data.

Figure 2 .

 2 Figure 2. Similarity between acheter (buy) and magasin(shop) according to the number of paragraphs.

Figure 3 .

 3 Figure 3. Architecture of the model of text comprehension.

  comm a n d , send , Jack . Man is too frequent for providing good neighbors; therefore the program did not consider it. Neighbors of flower are: petals , pollen , tulip . LSA similarities between all pairs of words are computed. After the integration step, working memory is: flower (1.00) flowers (.979) petals (.978) grow(gardener,roses) (.975) roses (.974) violets (.932) bouquet (.929) throw(man,flower) (.917) tulip (.843) pollen (.832)

Table 1 : Mean cosine between stimulus word and various associates for 9-years -old children

 1

	Words	Mean cosine with stimulus word
	Highest -ranked words	.26
	2 nd highest -ranked words	.23
	3 rd highest -ranked words	.19
	3 lowest -ranked words	.11

Table 2 : Correlations between participant child data and different kinds of semantic spaces

 2

	Semantic space Size (in million words)	Correlation	with	children
			data
	Children	3.2		.39
	Literature	14.1		.34
	Le Monde 1993	19.3		.31
	Le Monde 1995	20.6		.26
	Le Monde 1997	24.7		.26
	Le Monde 1999	24.2		.24

Table 3 : Correlations between LSA cosine s and children's semantic similarity judgments.

 3

		Grade 3	Grade 5	Couples (N)
	Giant	0,22	0,21	66
	Donkey	0,24*	0,22*	105
	Truck	0,28*	0,25*	66
	Chamois	0,34*	0,40**	55
	Clowns	0,48**	0,50**	56
	Lion	0,55**	0,63**	66
	Bear cub	0,55**	0,58**	91
	Mean	0,37**	0,37**

(* p <.05; ** p <.01).

Ackno wledge m e nt s

We would like to thank Eileen and Walter Kintsch and an anonymou s reviewer for their comments on a previous version of this paper.

well as each participant production are coded as propositions. Then, the number of text propositions that occur in the production is calculated. This measure is a good estimate of the information recalled from the text. Using our semantic memory model, this amount of recall is given by the cosine between the vector representing the text and the vector representing the participant production.

Table 4 displays all correlations between these two measures. They are all significant (< .05) and range from .45 to .92, which means that the LSA cosine applied to our children's semantic space provides a good estimate of the text information recalled, whatever the memory task, recall or summary, and the delay. In an experiment with adults, [START_REF] Foltz | Latent Semantic Analysis for text -based research[END_REF] has shown that LSA measures can be used to predict comprehension. Besides validating our model of semantic memory, this experiment shows that an appropriate semantic space similar again to the current propositions. However, if the digression lasts too long, the decay function will have greatly lowered the activation values of the first propositions and they will not be recalled any more.

Here is an English translation of a simulation we performed with the children Terms that are not related to the context (like radish ) were removed.

The second proposition is meow(cat) . Since the second sentence is not related to the first one, no terms appear to be gathered from episodic memory. Terms that are neighbors of meow but also close to cat are: meows , , purr . Neighbors of cat are meow , meows , miaow . They are added to working memory. LSA


Pierre Lescanne

(Mechanical) Reasoning on Infinite Extensive Games LIP report RR2008-16

come   L'archive ouverte pluridisciplinaire

is an annotation that limits its use. For instance, an object f of type A → B, written f : A → B represents a function and can only be applied to an object of type A to produce an object of type B. In our development we will write, for instance, a : Agent to say that a is an Agent and s : Inf Strategy to say that s is an infinite strategy. In what follows, a node (written iNode) in a infinite strategy is something that takes an agent, a choice, a finite strategy and an infinite strategy and produces an infinite strategy has a type, in more precise words it has the type, iNode : Agent → Choice → F inStrategy → Inf Strategy → Inf Strategy.

The Curry-Howard correspondence says also that types are propositions and insists essentially on the computational content of proofs and establishes the bases of the so-called constructive logic. Indeed since a proof works as a computation, an object can be taken into consideration only if it can be constructed and an existential proof is accepted if it allows constructing the object it claims the existence of. For instance, in an infinite extensive game we assert that there exists a utility for an agent a that can be associated with an infinite strategy, but this works if we prove it exists, i.e., provide a way to construct this utility, since assuming the existence without the construction is not enough.

The following formal development in Coq has been built in this framework and checked on a computer and is attached to proof scripts available on the web site of the author 2 . In this article we try to describe and comment the content of the scripts without entering in their full technicality, but the reader is anyway strongly encouraged to have a look at the scripts to convince himself of the materiality of the proofs and moreover, if he has access to a Coq implementation, he should try to run them on a computer.

Natural deduction

The proof systems we describe is based on natural deduction, which is one of the main system to formalize logic. Natural deduction has been formalized by Gerhard Gentzen [START_REF] Gentzen | Untersuchungen über das logische Schließen[END_REF] in 1935 (see also [START_REF] Prawitz | Natural Deduction: A Proof Theoretical Study[END_REF][START_REF] Van Dalen | Logic and Structure[END_REF]). Its adjective "natural" comes form the fact that its creators considered that it is just the natural way to formalize logic. It is based on the fact that to conduct a proof, one works under hypotheses and one tries to draw a conclusion. One considers that a theorem has been proved when all the hypotheses have been discharged.

The basic concept of natural deduction is this of sequent. A sequent is a pair of a context Γ and a proposition ϕ, which is written Γ ⊢ ϕ and which means that ϕ is a logical consequence of the set of hypotheses Γ. A context is a set of propositions and when we write Γ, ϕ we mean that the sequent Γ is enriched by the proposition ϕ, in other terms this is a notation for the union of sets of propositions. In this calculus there is one axiom and several rules. The axiom is and the elimination rule:

Γ ⊢ a : A Γ ⊢ ∀x : A, P (x) Γ ⊢ P (a)
Through the Curry-Howard correspondence, natural deduction is strongly connected to type theory and computation.

COQ

In this paper we are not describing all the details of the proof assistant Coq and the book [START_REF] Bertot | Interactive Theorem Proving and Program Development Coq'Art: The Calculus of Inductive Constructions[END_REF] is excellent source of information. Basically in Coq, proofs are mathematical objects in natural deduction and are considered as first class citizen that can be printed, be exchanged as objects between people, and overall be checked by a proof checker (a specific software) that examines it in full detail. As building proofs is a tedious process, the software Coq offers tools to build them. Basically a Coq development is made of several not fully separated phases: the user defines data structures (in our case: games and strategies), then he defines predicates, relations and functions on those structures (in our case: conversion, utilities and equilibria) and finally he proves theorems about those structures and predicates (in our case: a theorem that says that subgame perfect equilibria are Nash equilibria). Typically a script presents a set of sections in which a subdevelopment is presented, this section may invoke other sections; it is a sequence of declaration of variables, axioms, or hypothesis, followed by definitions and theorems with their proofs. To check that a script is correct, it is highly recommended to run it on a Coq implementation.

Induction, Coinduction, and Fixed point

Induction is a tool to reason over infinite sets of objects, provided those objects are finitely based. On the opposite, coinduction [START_REF] Bertot | Coinduction in Coq. Open archives[END_REF] has been designed to reason on infinite objects, like games with infinite paths. However infinite objects may have parts that are finite like finite paths in infinite games and induction can also be used on infinite objects, specifically on their finite subparts. In particular, if the paths are finite, one can compute the utility. Moreover in infinite games we can define finite relations, called convertibility. Therefore finite concepts are interleaved with infinite ones.

Beside games, we can define other finite or infinite objects, further we consider the following inductive (finite) objects: 1) finite games, 2) finite strategies (or strategy profiles), 3) the predicate eventually right that says when applied to a path of a game that the path in question goes eventually to the right, 4) the two convertibility congruences among strategies, namely among finite strategies, but also among infinitely strategy (we indeed claim this latter congruence can be described finitely provided we restrict it to appropriate strategies). 5) Nash equilibrium on finite games, 6) backward induction predicate and 7) Nash equilibrium on infinite games are also finite inductive concepts.

In this paper the archetype of a coinductive object is an infinite game. Obviously the associated concept of infinite strategy is coinductive. The function i2u that associates a utility with a strategy is also coinductive since the infinite strategies are. The predicate SGPE which tells whether an infinite strategy is a subgame perfect equilibrium is a coinductive object since the strategy is. In what follows we will define predicates that say that a property is "always" satisfied along a path, those properties on infinite objects are coinductively defined.

Roughly speaking inductive definitions are like equations and correspond to define the concept as least fixed points and the properties of this concept are derived of this minimality. On another hand, coinductive definitions correspond to greatest fixed points and the properties of this concept are derived from the maximality. Handling infinite objects (actual infinity vs potential infinity) is tricky and the Coq user does not escape this rule. Notice that Coq offers tools to verify along a proof that the one one builds will be accepted by the checker.

In this paper, we analyze games in extensive form. Informally such games are presented as trees. Each node of the tree is a situation in the game where a player has to take a decision. For reason of simplicity, following Vestergaard [START_REF] Vestergaard | A constructive approcah to sequential Nash equilibria[END_REF], we studied binary games where the players have only two choices. This seems a reasonable design decision, since we can reduce a choice among n to a binary choice between the n th and the set {1, ..., n -1} followed by the binary choice between the (n -1) th and the set {1, ..., n -2} etc... We do not loose any generality in term of modeling, and in term of abstraction this is the same as n choices at each node. A reader interested by an implementation based on more than two choices, i.e., on polyadic trees, is advised to consult Stéphane Le Roux PhD [START_REF] Le | Abstraction and Formalization in Game Theory[END_REF]. By considering binary games, we hope to be more didactic.

First we will consider finite binary games. Those games are somewhat connected with games with finite horizon, but in addition to offer choices to a finite depth, they are also finitely branching. Such a game is either a leaf, that is a game which ends and attributes the utilities, or a node where an agent has to take a decision. This leads typically to an inductive description. Like a natural is either 0 or the successor of a natural, or a binary tree is either a leaf with a content or a node made of two binary subtrees, a finite game is either a leaf with a function that associates a utility to each agent or a node with an agent and two subgames, namely a left subgame and a right subgame. With a finite game, we associate strategies. A strategy has the same structure as the game it is associated with, except that to each (internal) node we give a direction left or right, which corresponds to the choice made by the agent in this particular situation. In other words, a strategy is either a leaf associated with a utility, exactly like for games, or a node with an agent, a choice (left or right), and two substrategies.

The main goal of the study presented in this paper is infinite games, more specifically we describe deductions and formal reasoning on those games. Again for reason of simplicity, we study infinite games that looks like "centipedes", in other words binary games with a unique infinite path. The basic concept of those games is a node made of three components: an agent, a left subgames which is itself an infinite subgame, and a right subgame which is a finite subgame. This means that we "recycle" the formal development made for finite subgames for the right branch. Since the game is infinite its formalization relies no more on induction, but on coinduction. Like for finite binary games, the attached concept of strategy relies on a node with four components: an agent, a choice (left or right), an infinite left substrategy, and a finite right strategy.

Equilibria on finite Games

As an introduction to the Coq development, let us study equilibria on finite games.

Agent and Utility

First we set two basic concepts namely Agent and Utility. In Coq, this is done by the following declaration:

Variable Agent : Set. Variable Utility: Set.

In addition we set a preference as a binary relation on Utility and we make this preference a preorder, which we write =< , Utility fun is the type of the utility functions, in other words the type of the objects belonging to Agent → Utility.

Finite Games

A finite binary game, which we call a FinGame, in Coq, is built by induction, this means that this is either a leaf or this is a game with two subgames that are themselves binary games, we encapsulate these three items under the label gNode. In Coq, such a data structure will be written:

Inductive FinGame : Set := -gLeaf : Utility fun → FinGame -gNode : Agent → FinGame → FinGame → FinGame.
where Inductive is the key word to introduce any inductive definition. FinGame is a data structure, but elsewhere the same Inductive keyword will be used to define a predicate. An inductive definition creates a deduction rule that allows us to reason by induction, namely in the case of FinGame, the term FinGame ind is created by Coq: ∀ P : FinGame → Prop, (∀ u : Utility fun, P (gLeaf u)) → (∀ (a : Agent ) (f0 :FinGame), P f0 → ∀ f1 : FinGame, P f1 → P (gNode a f0 f1 ) ) → ∀ f1 : FinGame, P f1

It can be written as the rule ∀u : Utility fun, P(gLeaf u)

[∀f0 : FinGame, P f0 ∧ ∀f1 : FinGame, P f1] → ∀a : Agent, P (gNode a f0 f1)

∀f : FinGame, P f in other words, to prove that some properties holds for all the finite binary games, one has to prove it to hold for leaves and to prove that if it holds for two games then it holds for the game obtained by pairing those two games under the "control" of an agent.

Finite Strategies

As we said, a finite strategy3 has a structure which is very similar to a finite game, the only difference is that we add a "choice" at each node.

Inductive FinStrategy : Set := -sLeaf : Utility fun → FinStrategy -sNode : Agent → Choice → FinStrategy → FinStrategy → FinStrategy.

With a strategy we provide a function that associates with every strategy a utility function. The Coq keyword to define such a function is Fixpoint. A syntactic construction called match allows using a pattern matching mechanism. This reads as if the strategy s is a leaf, i.e., sLeaf uf (where uf is a utility function), then one returns uf, otherwise one returns the utility function associated with the left substrategy, if the choice is left, or the right substrategy if the choice is right.

Now we define on finite strategies a relation, which we call a-convertibility, and which we write s<<-a->>s'.

Labeled with a, it is associated with the agent a and says that Two leaves associated with the same utility function are a-convertible, Two sNodes, (sNode a c s1 s2 ) and (sNode a c' s1' s2' ), associated with the same agent a are aconvertible if s1 <<-a->>s1' and s2 <<-a->>s2'. Notice that c and c' do not have to be the same, Two sNodes, (sNode a' c s1 s2 ) and (sNode a' c s1' s2' ), associated with another agent a' are a-convertible if s1 <<-a->>s1' and s2 <<-a->>s2'. Notice that in this case c has to be the same.

We prove in Coq (a first interesting exercise) that the a-convertibility is an equivalence relation i.e., it is reflexive, symmetric and transitive. We are now equipped to define the predicate Nash equilibrium on finite strategy (in Coq the predicate FinNashEq on FinStrategy):

Inductive FinNashEq: FinStrategy → Prop := -NE : ∀ (s:FinStrategy), (∀ (a:Agent ) (s' :FinStrategy), s<<-a->>s' → (f2u s' a =< f2u s a)) → FinNashEq s.

It says that s is a Nash equilibrium if for all strategy s' that is a-convertible to s, f2u s' a =< f2u s a, in other words, the utility for a computed for s' is less than the utility for a computed for s. This is nothing more than the traditional definition of Nash equilibrium for extensive game, written in the formalism of Coq.

Beside the predicate Nash equilibrium, we define the predicate BI which says whether the strategy s can be obtained by the so-called backward induction. In Coq, it is written: In other words, BI holds for leaves, if BI holds for sl and sr and f2u sl a =< f2u sr a then BI holds for sNode a left sl sr (BINode left principle), the BINode right principle is symmetric, it says, that if BI holds for sl and for sr and f2u sr a =< f2u sl a then is BI holds for sNode a right sl sr. This is the formalization of backward induction for finite horizon games as described in textbooks [START_REF] Osborne | A Course in Game Theory[END_REF][START_REF] Osborne | An Introduction to Game Theory[END_REF][START_REF] Gintis | Game Theory Evolving: A Problem-Centered Introduction to Modeling Strategic Interaction[END_REF].

Then we are able to prove in Coq the theorem:

Theorem BI is FinNashEq : ∀ s, BI s → FinNashEq s.

The theorem relies on the following fact: the inductive definition of BI is a somewhat equational definition that says that BI is the least fixed point of that equation. Therefore if we can prove that if FinNashEq is another fixed point, this other fixed point is implied by BI and we are set. This can be done by three lemmas.

• FinNashEq satisfies the statement given by BILeaf :

Lemma FinNashEq Leaf : ∀ (uf :Utility fun), FinNashEq (sLeaf uf ).

• FinNashEq satisfies the statement given by BINode left :

Lemma FinNashEq fixpt left : ∀ (a:Agent ) (s1 s2 : FinStrategy), FinNashEq s1 → FinNashEq s2 → (f2u s2 a =< f2u s1 a) → FinNashEq (sNode a left s1 s2 ).

• FinNashEq satisfies the statement given by BINode right : Lemma FinNashEq fixpt right : ∀ (a:Agent ) (s1 s2 : FinStrategy), FinNashEq s1 → FinNashEq s2 → (f2u s1 a =< f2u s2 a) → FinNashEq (sNode a right s1 s2 ).

Then we conclude than FinNashEq satisfies the same equation as BI. Since BI is the least fixed point, BI s implies FinNashEq s.

Coinduction

Coinduction is the partner of induction, but whereas the induction defines objects or predicates as the least fixed point of some equations and therefore specifies finite objects and presents them from basic objects, coinduction defines infinite objects or infinite and finite objects as greatest fixed point of some equation. If one has in mind to define infinite objects only, there is no need to specify basic objects (i.e., objects meant to be the basis on which to define finite object). The typical infinite object is

CoInductive InfGame : Set := -igNode : Agent → InfGame → FinGame → InfGame.
In other words, an infinite binary game is made of an agent, an infinite binary subgame, and a finite binary subgame. On the same model as for finite binary games, we define infinite strategies the same way, i.e., as a coinductive:

CoInductive InfStrategy : Set := -iNode : Agent → Choice → InfStrategy → FinStrategy → InfStrategy.
7 Equilibria on Infinite Games

Decomposing Infinite Games

Since the strategies are infinite we can define total functions iAgent (which gives the agent at the root of the game), SubGameLeft (the infinite game on the left) and SubGameRight (the finite game on the right) with the lemma:

Lemma InfGame Decomposition: ∀ (g:InfGame), igNode (iAgent g) (SubGameLeft g) (SubGameRight g) = g.
that says that a game can be uniquely decomposed into an agent, a left subgame and a right subgame.

Generalizing the notion of horizon

In classical extensive game theory, the concept of backward induction relies on this of finite horizon, our experience in mechanizing the proof has shown us that finite horizon is not exactly the right notion, we prefer the notion of limited horizon, which means that the horizon of the agents is not bounded by a number, but that however it cannot go to infinity. In the frame of binary games, this means that we forbid paths that go always to the left, we want to consider the paths that eventually go to the right so that one can compute the utility of each agent. Since the games are now infinite, a total function that associates, by computation, a utility to a strategy can no more be defined, one can only define a relation between a strategy and a utility. If the path of the choice goes always to the left (on the backbone) the utility cannot be defined, but if the path goes "eventually to the right", the utility of a strategy makes sense. We therefore define a predicate EvtRight which says whether the path of the given strategy goes eventually to the right. The basic case for this predicate is that it holds for the game iNode a right sl sr. The induction case says that if EvtRight sl then EvtRight (iNode a left sl sr ). The predicate EvtRight is typical of an inductive predicate. We get two lemmas which show the existence and the uniqueness of a utility for a strategy that goes eventually to the right, therefore in that case, the association of the utility to the strategy is functional. Since most of the time we want this functional association, we require the predicate "eventually right" to hold.

Lemma Existence i2u: ∀ (a:Agent ) (s:InfStrategy), EvtRight s → ∃ u:Utility, i2u a u s.

Lemma Uniqueness i2u: ∀ (a:Agent ) (u v :Utility) (s:InfStrategy), EvtRight s → i2u a u s → i2u a v s → u=v.

Going eventually to the right is not enough. In some cases, when dealing with subgames, more specifically with subgame perfect equilibria, one wants to be able to compute utilities in subgames. Therefore one wants to be sure that even further in subgames one will go eventually to the right. Hence we define another predicate that ensures that we will always go eventually to the right. This predicate AlwEvtRight reminds us the same kind of predicate defined in the frame of temporal logic (see [START_REF] Bertot | Interactive Theorem Proving and Program Development Coq'Art: The Calculus of Inductive Constructions[END_REF] chap. 13 and [5]). Since AlwEvtRight has to traverse the whole infinite game, it has to be coinductive. It says that AlwEvtRight (iNode a c sl sr ) holds, if AlwEvtRight sl and EvtRight sr hold, in other words, a strategy goes always eventually to the right if its left substrategy goes always eventually to the right and if its right substrategy (which is finite) goes eventually to the right.

Convertibility of infinite strategies

The definition of the convertibility s < --a -->s' of two strategies s and s' is inductive. Its base case is the reflexivity of the convertibility. In other words, s < --a -->s' if: s = s', or if s1 < --a -->s1' and s2 <<-a->>s2' and s is iNode a c s1 s2 and s' is iNode a c' s1' s2' (c may be different, but a has to be the same), or if s1 < --a -->s1' and s2 <<-a->>s2' and s is iNode a' c s1 s2 and s' is iNode a' c s1' s2' (different agents, but same c).

Equilibria

To define Nash Equilibria on infinite games, one must be able to compare utilities. For that, one must be able to compute those utilities. Hence one restricts to strategies that go eventually to the right.

Inductive InfNashEq: InfStrategy → Prop := -INE : ∀ (s: InfStrategy), EvtRight s → (∀ (a:Agent ) (s' :InfStrategy) (u u' : Utility), EvtRight s' → s' < --a -->s → (i2u a u' s' ) → (i2u a u s) → (u' =< u)) → InfNashEq s.
On infinite strategies one defines a predicate Subgame Perfect Equilibrium. Because one has to be able to compute utilities on subgames, the Subgame Perfect Equilibrium predicate, written SGPE, is defined on strategies which go always eventually to the right. Notice that Subgame Perfect Equilibria are defined on a smaller class of strategies than Nash Equilibria, but also that the definition of SGPE is coinductive, since its definition requires to traverse the whole infinite subgame. One can show that InfNashEq is a fixed point of this definition. To prove the lemma SGPE s → InfNashEq s, one needs to perform a proof by induction, this cannot be an induction on the definition SGPE which is coinductive. To enable a proof by induction, we impose an additional requirement, namely that somewhere in the game a maximal utility is reached for all agents. We give a statement of this requirement through the following predicate EvtMaxU : It has two parts.

The game fulfills the maximal utility requirement for every agent,

The left subgame does.

Then we can set and prove the main theorem:

Theorem SGPE is InfNashEq : ∀ s:InfStrategy, EvtMaxU s → SGPE s → InfNashEq s.

If every agent reaches a maximal utility somewhere in the game, then a subgame perfect equilibrium is a Nash equilibrium. [START_REF] Girard | of Cambridge Tracts in Theoret Computer Science[END_REF] The "Illogic of Conflict Escalation" revisited Now we may want to apply those general results on a specific infinite subgame. Consider the following game proposed by Shubik [START_REF] Shubik | The dollar auction game: A paradox in noncooperative behavior and escalation[END_REF]. Recall its principle. Two agents Alice and Bob compete in an auction for an object of a value, say 2 , in this statement. The two agents bid 2 , one after the other. If one agent gives up, the highest bidder gets the object, but the second bidder pays also for his bid. As Shubik noted this game may never cease.

Let us take as the utility ordering, the order ≥ on the nat (the natural numbers or non negative integers), in other words, if u and v are two utilities, u and v are of type nat and u =< v means u ≥ v, i.e., the larger the bid, the smaller the utility.

Strategy Never give up

Let us consider the function enlarge left left n on strategies, that takes a strategy and returns another one and that can be described by the following picture, where the thick arrows give the choice at each node.

Alice Bob 2n+1,2n 2n+1,2n+2

We define the strategy never give up (in short ngu) as the strategy where the agents always keep bidding. It requires to define first a strategy that starts with the value n as the solution of ngu n = enlarge left left (ngu (S n)).

ngu n is an infinite strategy and we can prove that for n, (ngu n) is not a Nash equilibrium. In this proof, reasoning has a flavor of temporal logic.

Strategy Always give up

Here we consider the function enlarge right right n on strategies.

Alice Bob 2n+1,2n 2n+1,2n+2

Again agu n is an infinite strategy and we can prove the lemma:

Lemma SGPEAGU : ∀ (n:nat ), SGPE Ag12 nat ge (agu n).

which says that that this strategy is a Subgame Perfect Equilibrium.

Conclusion

The experiment presented in this paper is in a very stage. Its goal is to make clear that, in games, especially in infinite games, the reasoning can be mechanized despite it is not obvious; it evidences with no surprise some subtlety. To mimic it, humans elaborate rather complex deductions. One of the main statement we can make is that true classical logic is never used. More specifically, we noticed no use of the excluded middle or proofs by double negations. We hope this experiment opens a discussion and shows how far humans are from the somewhat ideal mechanized reasoning. We wish to pursue this research by trying other modelings and concepts and going further in the proofs, for instance finding other conditions for SGPE s → InfNashEq s and deeper results on the example of "Illogic Conflict of Escalation".

Fixpoint

  f2u (s:FinStrategy) : Utility fun := match s with -(sLeaf uf ) ⇒ uf -(sNode a left sl sr ) ⇒ (f2u sl ) -(sNode a right sl sr ) ⇒ (f2u sr ) end.

Inductive

  BI : FinStrategy → Prop := -BILeaf : ∀ uf :Utility fun, BI (sLeaf uf ) -BINode left : ∀ (a:Agent ) (sl sr : FinStrategy), BI sl → BI sr → (f2u sr a =< f2u sl a) → BI (sNode a left sl sr ) -BINode right : ∀ (a:Agent ) (sl sr : FinStrategy), BI sl → BI sr → (f2u sl a =< f2u sr a) → BI (sNode a right sl sr ).

CoInductive

  SGPE : InfStrategy → Prop := -SGPEnode left : ∀ (a:Agent )(u:Utility) (sl : InfStrategy) (sr : FinStrategy), AlwEvtRight sl → SGPE sl → BI sr → i2u a u sl → (f2u sr a =< u) → SGPE (iNode a left sl sr ) -SGPEnode right : ∀ (a:Agent ) (u:Utility) (sl : InfStrategy) (sr : FinStrategy), AlwEvtRight sl → SGPE sl → BI sr → i2u a u sl → (u =< f2u sr a) → SGPE (iNode a right sl sr ).

Inductive

  EvtMaxU : InfStrategy → Prop := -EUM basis: ∀ (s:InfStrategy), (∀ (a:Agent )(u u' :Utility)(s' :InfStrategy), s< --a -->s' → i2u a u' s' → i2u a u s → (u' =< u)) → EvtMaxU s -EUM gen: ∀ (a:Agent )(c:Choice)(sl :InfStrategy)(sr :FinStrategy), EvtMaxU sl → EvtMaxU (iNode a c sl sr ).

Γ ⊢ ϕ if ϕ ∈ ΓThere are two kinds of rules for each connector, namely introduction rule and elimination rule. For instance, for the implication →, the introduction rule isΓ, ϕ ⊢ ψ Γ ⊢ ϕ → ψ whereas the elimination rule is Γ ⊢ ϕ → ψ Γ ⊢ ϕ Γ ⊢ ψalso known as the modus ponens. We are now giving only the rule for the universal quantifier, the introduction rule Γ, x : A ⊢ P (x) Γ ⊢ ∀x : A, P (x)2 http://perso.ens-lyon.fr/pierre.lescanne/COQ/INFGAMES/

Actually we should probably say a strategy profile, but, for convenience and conciseness, we call this data structure just a strategy.