Etienne Papegnies

Vincent Labatut

Richard Dufour

Georges Linarès

Impact Of Content Features For Automatic Online Abuse Detection

Online communities have gained considerable importance in recent years due to the increasing number of people connected to the Internet. Moderating user content in online communities is mainly performed manually, and reducing the workload through automatic methods is of great financial interest for community maintainers. Often, the industry uses basic approaches such as bad words filtering and regular expression matching to assist the moderators. In this article, we consider the task of automatically determining if a message is abusive. This task is complex since messages are written in a non-standardized way, including spelling errors, abbreviations, community-specific codes... First, we evaluate the system that we propose using standard features of online messages. Then, we evaluate the impact of the addition of pre-processing strategies, as well as original specific features developed for the community of an online in-browser strategy game. We finally propose to analyze the usefulness of this wide range of features using feature selection. This work can lead to two possible applications: 1) automatically flag potentially abusive messages to draw the moderator's attention on a narrow subset of messages ; and 2) fully automate the moderation process by deciding whether a message is abusive without any human intervention.

Introduction

On the main achievements of the Internet is the freedom and anonymity it brought into the way we communicate. Online communities, which are freely accessible exchange spaces on the Internet, have enjoyed a surge of users as a result. They come in many shapes and forms but they all share a common aspect: they have to be maintained by some party. Some online communities have gained considerable socio-economical importance due to their huge user base. A correct behavior in these communities is usually required to comply with a given set of rules so that users may enjoy a hospitable and productive environment. However, freedom and anonymity often give rise to abusive behaviors. The definition of an abusive behavior is often dependent on community rules. Almost always though, users have to show respect to one another in the way they interact, so verbal abuse as well as the expression of racist, homophobic and otherwise discriminatory views constitutes abusive behaviors. As a result, moderation is the task of responding to abusive behaviors by sanctioning the users exceeding the rules. This moderation work is mainly done manually, which makes it very costly in terms of human and financial costs.

In this paper, we consider the problem of automatically determining if a message from a user is abusive or not. We first present our automatic abusive message classification system based on basic features. We then propose to enrich our system by considering original preprocessing approaches, as well as corpus selection and various new content features specific to the targeted community. We finally propose a qualitative study that helps to analyze the impact of each content feature on the automatic abusive message classification performance. Two types of messages are considered in this paper: one source akin to email and the other to discussions in a chatroom, both coming from a corpus of messages originating from the community of the French massively multiplayer on-line game SpaceOrigin.

This paper is organized as follows. In Section 2, we review the main works related to abuse detection and automatic moderation. In Section 3, we describe the features used to automatically detect abusive messages. In Section 4, we present our dataset as well as the experimental protocol, and discuss the results obtained. Finally, the main points of our work are summarized in Section 5, which also shows how it could be extended.

Related Work

A number of works have tackled the problem of detecting abusive messages in on-line communities. While most of them are evaluated on English datasets, the majority of the methods used are language-and community-independent, and can therefore be applied on messages from any online community, which makes them relevant to us. This review is focused around two axes: Preprocessing techniques and Features for abuse detection. Preprocessing consists in taking the raw message text and attempting to alleviate most of the problems introduced by the Internet medium, such as typos, abbreviations, use of smileys and so on. The feature extraction process consists in processing a series of indicators from the raw message text, that will reflect its class.

Preprocessing step

Preprocessing is usually a simple but important step when dealing with messages posted on-line. The Internet medium introduces specific difficulties: disregard of syntax and grammar rules, out-of-vocabulary words, heavy use of abbreviations, typos, presence of URLs... The Denoising and Deobfuscation tasks both consist in mapping an unknown word back into a dictionary of known words. In the first case, a word is out of the vocabulary for unintentional reasons such as typos, e.g. "I uess so" for "I guess so". In the second case, it is due to a more deliberate attempt to conceal the word, e.g. "F8ck3r" for "fucker". Globally, mapping the word back into the dictionary increases the performance of probabilistic learning methods, since these methods need the cleanest possible text to achieve their maximum performance.

In [START_REF] Sood | Using crowdsourcing to improve profanity detection[END_REF], the Levenshtein distance (a type of edit distance) is used in an attempt to match unknown words against words in a crowd-sourced list of manually annotated messages containing profanity. The Levenshtein distance [START_REF] Levenshtein | Binary codes capable of correcting deletions, insertions and reversals[END_REF] measures the number of insertions, deletions and replacements needed to convert a string into another (e.g. The Levenshtein distance between "@ss" and "ass" is 1). Computing the Levenshtein distance between two words of length n and m is computationally expensive: the runtime is O(nm), and for this specific task each word has to be matched against each word in the dictionary, which is huge. We base some of our features on the Levenshtein Distance.

Other works, such as [START_REF] Brill | An improved error model for noisy channel spelling correction[END_REF], proposed to improve on simple Levenshtein distance based denoising (for the purpose of spell checking) by considering the context of the string edition in a word (where the edited character is) and in a sentence (does the edit maps the word into a high n-gram probability?). However, this approach is based on the assumption that out-of-vocabulary words are mainly due to unintentional spelling mistakes and is therefore not applicable to deobfuscation.

In [START_REF] Lee | Spam deobfuscation using a hidden markov model[END_REF], the authors use a Hidden Markov Model customized with dictionary and context awareness for the purpose of deobfuscating spam messages. Those types of messages often include deliberately misspelled words in an attempt to bypass filters. Their model showed impressive results with the ability to correct both unintentional misspellings as well as deliberate obfuscation using weird characters or digits and could even map segmented words back into complete words. (ie: "ree movee" → "remove"). This preprocessing approach, while effective, is computationally intensive and complex to implement.

Preprocessing is an important step in an automated abuse detection framework, but it should be applied with caution. The goal of preprocessing is to increase the amount of relevant information in a message, but it can have the opposite effect. For example the tendency of a user to misspell words can be viewed as an important feature to describe the user, but blind preprocessing would hide that.

Text messaging classification

In this section we review existing classification approaches that consider the content of the messages to detect abusive messages, and then the context of the exchanged messages.

Content-based approaches. The work described in [START_REF] Spertus | Smokey: Automatic recognition of hostile messages[END_REF] was one of the first to automate the detection of hostility in messages. While hostility does not imply abuse, abuse often contains hostility. The paper defined a number of rules to identify certain characteristics of the messages, such as Imperative Statement, Profanity, Condescension, Insult, Politeness and Praise. A Decision Tree classifier was then used to categorize messages into Hostile and Non-hostile classes. The setup showed good results but was limited when dealing with sarcasm, noise or innuendo. This approach is interesting but highly tuned for the grammar rules, semantics and idioms of a specific language.

In [START_REF] Chen | Detecting offensive language in social media to protect adolescent online safety[END_REF], the authors note that the mere presence of an offensive word in a message is not a strong enough indication that the message itself is offensive, i.e. "You are stupid." is way more offensive than "This is stupid.". This is an important observation and the authors showed that the lack of context can be mitigated by looking at word n-grams instead of unigrams.

Another work [START_REF] Dinakar | Modeling the detection of textual cyberbullying[END_REF] used features computed from tf -idf weights, a list of words reflecting negative sentiment and widely used sentences containing verbal abuse to detect cyberbullying in comments associated with Youtube videos. Their model showed good results for instances of verbal abuse and profanity but was limited with regard to sarcasm and euphemism.

Finally, in [START_REF] Chavan | Machine learning approach for detection of cyberaggressive comments by peers on social media network[END_REF] the authors reviewed machine learning approaches for the classification of aggressive messages in On-line Social Networks, described a full pipeline for achieving classification of raw comments and introduced two new features: Pronoun Occurrence and Skip-Gram features. They allow for the detection of targeted phrases such as "He sucks" or "You can go die", and for the identification of long distance relationship between words, respectively.

Content-based text classification performs relatively well as a starting point. The computational cost to implement these approaches is usually reasonable. Nonetheless, these approaches have severe limitations. For instance, abuse can cross message boundaries, and therefore a message can be abusive only because of the presence of an earlier message. In other cases, messages can be abusive because they reference a shared history between two users. Therefore, studying the context of a message, its recipient, and its author might also be important.

Context-based approaches. To go beyond the limitations of content-based approaches, some authors proposed to take into account the context of messages, usually in addition to the textual content itself.

Some works explore the use of the content neighboring the targeted message. In [START_REF] Yin | Detection of harassment on web 2.0[END_REF], the authors used a supervised classifier working on n-gram features, sentence-level regular expression patterns and the features derived from the neighboring phrases of a given message to detect abuse on the Web. Their approach focused on detecting derivations in the context of a discussion around a given topic and their context features significantly improved the performance of their system. For this reason, we want to adopt a similar approach for our own method, but by focusing on derivations of users themselves from their usual patterns.

Other works have focused on modeling the users' behaviors by introducing higher-level features than the textual context. A comprehensive study of antisocial behavior in on-line discussion communities has been proposed in [START_REF] Cheng | Antisocial behavior in online discussion communities[END_REF]. Their exploratory work reinforced the weight of classic features used to classify messages such as misspellings and length of words, and provided insight into the devolution of users over time in a community, regarding both the quality of their contributions and their reactions towards other members of the community. This analysis is a good step towards modeling abusive behavior. One of the essential results of the analysis is that instances of antisocial messages tend to generate a bigger response from the community compared to benign messages. The number of respondents to a given message is a feature we use in this work.

A selection of contextual features aiming at detecting abuse in on-line game communities has also been investigated in [START_REF] Balci | Automatic analysis and identification of verbal aggression and abusive behaviors for online social games[END_REF]. These features form a model of the users of the game by including information such as their gender, number of friends, investment in the platform, avatars, and general rankings. The goal was to help human moderators dealing with abuse reports, and the approach yielded sufficiently good results to achieve this goal. The work was however limited in applicability because of the specifics of that given community, and of the raw amount of data needed to perform similar experiments in other games.

When quantifying controversy in social media [START_REF] Garimella | Quantifying controversy in social media[END_REF], the structure of the community network is exploited to identify topics that are likely to trigger strong disagreements between users. The approach relies on a network whose nodes are Twitter users and links represent communications between them. It is interesting, however hardly applicable to our case, since we cannot infer the exact network structure from our dataset unless we restrict the network to private conversations between two users.

Abusive Message Features

In this section, we describe the content-based features used in our automatic abusive message classification system. They can be broadly categorized as morphological, language, and context features. Some of them are quite generic, in the sense they are used for different classification tasks in the literature. The others were designed by us specifically for this experiment, and some are customized for the community where our dataset originates, but they can sometimes be generalized to other communities (we reflect on this in Section 5). The features we developed are denoted with a star (*) preceding their name and description.

Some features require the data to be preprocessed before being extracted, so we start with the description of our preprocessing approach first.

Preprocessing

We distinguish two preprocessing phases. In the basic phase, we first lower-case the raw text and tokenize it using spaces. Each token in the list is then stripped of punctuation before the message is reassembled.

In the advanced phase, the data undergo some additional preparation steps. First, we revert elision. Elision refers to the suppression of a final unstressed vowel immediately before another word beginning with a vowel. For the French language, we therefore replace instances of "j'", "t'" by their respective long forms "je ", "te ", so that, for instance, "j'arrive" becomes "je arrive". Second, we run a deobfuscation pass by mapping hexadecimal or binary encoded text in the message back to ASCII. This is highly specific to the considered online community, because users sometimes encode part of their messages in that way. Third, we convert each URL into a sequence of tokens. The first describes whether this URL is an internal link (to a server hosting the community) or an external one. The rest are words that could possibly be extracted from the name of the web page. For instance: http://edition.cnn.com/2017/01/31/politics/donaldtrump-immigration-white-house/index.html is mapped to: url external cnn com politics donald trump immigration white house index. Finally, we use the FrenchStemmer from the Natural Language Toolkit [START_REF] Bird | Nltk: the natural language toolkit[END_REF] to convert words into their stem.

Morphological Features

Message Length. This feature corresponds to the length of a message, expressed in number of characters, before any pre-processing. The intuition is that abusive messages are usually either kept short (e.g. "Go die."), or extremely long, which is symptomatic of a massive copy/paste.

We also consider the length expressed in terms of words. In conjunction with the character count, it can match certain overly emphasized messages (e.g.: "Shuuuuuuuuuuuuuuuuuuuuuuut uuuuuuuuuuuuuuuuuuuup!").

Character Classes. We split characters into 5 classes: Letters, Digits, Punctuation, Spaces and Others. We keep track of the number of characters in those classes and the ratio of those classes in the message. This is done on the raw message, before any preprocessing.

We selected these features based on several observations we made on the abusive messages. First, some of them have an unusual number of characters in the "Other" class, e.g.: "8==================D". Second, some use digits to obfuscate their meaning, in violation of the game rules. For instance, "01000111011011110010000001100100011010010110010100101110" and "476F20-6469652E" are obfuscated versions of the text "Go die.": the first one is coded in binary, and the second in hexadecimal.

Abusive users also commonly "yell" insults using capital letters, which is why we keep track of both the number of caps and the corresponding ratio of caps in the message.

Compression Ratio. This feature is defined as the ratio of the length of the compressed message to that of the original message, both expressed in characters. It is based on the observation that certain users tend to repeat exactly and many times the same text in their abusive messages. We use the Lempel-Ziv-Welch (LZW) compression algorithm [START_REF] Batista | Texture classification using the lempel-ziv-welch algorithm[END_REF], and the feature therefore directly relates to the number of copy/pastes made in the same message.

Unique Characters. By counting the number of distinct characters in the message, we can detect the use of binary or hexadecimal obfuscation, as well as the overuse of punctuation. For instance, for the message "010001110110111101110", this feature has only a value of 2. This value is also computed before any preprocessing.

Collapsed Characters. This feature is computed after the message is lowercased. When three or more identical consecutive characters are found in the message, they are collapsed down to two characters. For instance, "looooooool" would be collapsed to "lool". The feature is the difference between the length of the original message and that of the collapsed one. This preprocessing step has been widely used in the classification of Tweets, for instance in [START_REF] Roy | A lexicon based algorithm for noisy text normalization as pre processing for sentiment analysis[END_REF].

Language Features

Bag of Words. We transform the message into a Bag of Words (BoW). This is a sparse binary vector that has the same dimension as the known vocabulary of the corpus and where each component corresponds to one word. The component has value 1 if the word is present in the message and 0 if it is not. We use the output of a Naive Bayes classifier for a given BoW as an input feature into our larger system.

Word Length. This feature is a component of the Automated Readability Index (ARI) [START_REF] Senter | Automated readability index[END_REF]. It measures how proficient someone is at creating text documents. While abusive messages are sometimes surprisingly well written, this remains rare.

Unique Words. We consider the number of unique words in the message. The intuition is that messages with more words are likely to be more constructive in terms of their content. Moreover, we observed that people are generally straightforward when verbally abusing others, and rarely take the time to elaborate.

tf -idf Scores. Those features are the sums of the tf -idf scores of each individual word in the message. We use two distinct scores: the so-called non-abuse score is processed relatively to the non-abuse class (randomly chosen messages that have not been flagged as abusive), whereas the abuse score is processed over the abuse class.

If the considered word is unknown, in the sense it does not appear in the training set, we process an approximation of these scores. For this purpose, we first search for known words located within a given Levenshtein distance from the word of interest, and average their own scores.

Computing the full Levenshtein Distance between two words is computationally expensive. For this reason, solutions proposed in this paper never compute the full Levenshtein Distance between two words. Instead, a specialized treebased index data-structure with a search function that yields all words in the tree within a given maximum edit distance is used. We use 2 as the maximum edit distance. This is considerably faster because branches of the tree are pruned as soon as we reach a state where the maximum edit distance is exceeded. It is still the second most computationally intensive operation in our experiments.

Sentiment Scores. These features are numeric values derived from the number of words in the message that have a sentiment weight. It is based on the sentiment corpus presented in [START_REF] Chen | Building sentiment lexicons for all major languages[END_REF], which was automatically generated for the French language. We augmented it manually by selecting words from a large list of insults.

Bad Words. This feature corresponds to the number of words in the message that appear in a manually crafted list of bad words. The list of words was created from a list of insults in French and then augmented with common Internet shorthand and symbolism. (e.g: 'connard', 'fdp', 'stfu' but also '..-..', '8==D' etc)

When we cannot match the considered word to any of the bad words in our list, we try to perform a fuzzy match using the Levenshtein distance. This is supposed to allow us picking up some obfuscated bad words.

We also perform the same tests using the collapsed version of the message (as described for the Collapsed Characters feature).

Business Score*. We first mine messages for patterns specific to the community. In the targeted context of this particular online strategy game, we chose to focus on: names of buildings and military units, war vocabulary and other gamespecific jargon, sets of Coordinates, and report links. The latter refers to internal URLs generated by some actions, and pointing towards summaries that the players can share. For each pattern, we manually developed a regular expression and used it to find the number of non-overlapping occurrences of the pattern in the message. We then produced the Business Score by combining the individual scores obtained for each pattern. This is a measure of how the message relates to the focus of the community. By observing the corpus we noticed that abusive messages tend to be strictly personal attacks with no pretense of roleplay and no mention of game jargon.

User Behavior Features

Number of respondents. Given a fixed size window after a target message, this feature tracks how many distinct users replied to this message. This feature is likely to be relevant, because it has been shown that abusive comments tend to trigger big responses from the community.

Probability of n-gram emission (PNE)*. We investigate if the abusiveness of a user's message can be detected by considering the effect it has on the other users participating to the same conversation. To do this, we compare the writing behavior of the other users before and after the apparition of the targeted message. We model this behavior through a user-specific Markov chain, which we use to compute how likely some text is to have been generated by the considered user.

We first sort the messages in chronological order. For each participant other than the user who wrote the targeted message, we build a word n-gram Markov chain using all but the last W n-grams in the messages posted before the target message. The Markov chain is a convenient way to store the transition probabilities for all couples of n-grams in a participant's history. We compute two values: the average emission probabilities of the n-grams in the W -length window before and after the target message, as represented in Figure 1.

Let P i,i+1 be the emission probability of a transition between the i th and i + 1 th n-grams in the window of length W . Then we define the average emission probability S over the set of W n-grams as:

S = W -1 i=0 P i,i+1 W (1)
We note S B (u) and S A (u), respectively, the average probabilities processed before and after the targeted message, for the same user u. The final score S(u) for user u corresponds to their difference:

S(u) = S A (u) -S B (u) ( 2
)
This score is processed for every respondent to a message in a window of fixed length after the message. We then compute our feature by averaging this score over all the responding users.

Applicability Criterion for PNE*. The previous feature requires averaging scores, which makes sense only if the considered users have sufficient history: we define a limit of at least 300 bigrams. This feature reflects the fulfillment of this constraint.

Experiments

In this section, we describe the data used in our experiments (Subsection 4.1) as well as the experimental protocol (Subsection 4.2). We then evaluate the proposed system, including the various features and original preprocessing approaches (Subsection 4.3).

Dataset

We have access to a database of users' in-game interactions for the considered MMO. This user-generated content was manually verified, in the sense the game users had the ability to flag parts of the content as inappropriate (i.e. abusive). There are many types of reportable contents, but, in this paper, we focus on two of them: ingame-messages (iM) and chat messages (cM), collectively referred to as messages.

Ingame-messages (iM) are on-line messages with a clearly defined reach. They are the equivalent of e-mails and can be sent to specific users or groups of users. They can be edited a posteriori by moderators when an abuse case is reported. The reach of chat messages (cM) is loosely defined because it is limited to users currently active in a chatroom. However, there is no way to determine which user has actually seen a specific chat-message based on the available data. Users are fed recent scroll history for a chatroom upon joining, but it is not possible to reliably determine who has joined when from the chat logs. Chat-messages cannot be edited by moderators afterwards.

The database contains 474, 599 in-game messages and 3, 554, 744 chat-messages. We extract 779 abusive messages (0.02%), which constitute what we call the Positive Class (Class 1) of messages. These messages were first flagged by the game users using a built-in reporting tool, and then confirmed as being abuse cases by the game community moderators. Of these 779 abusive messages, 14% are ingame-messages, and the rest are chat-messages. We then extract non-abuse messages from the database, in order to constitute the so-called Negative Class (Class 0). They are chosen at random from a pool of messages written by users which have never been flagged by a confirmed abuse report. For each message, we also gather context data: a window of messages occurring before and after each message.

We run the experiments with different versions of the corpus: in-game messages only (iM ), chat-messages only (cM ) and messages of both types combined (iM+cM ). Sizes of each considered corpus configuration are reported in Table 1. These configurations are considered as "unbalanced" (U), since there are twice as many non-abusive messages as abusive messages. As a result, we also experiment with the use of "balanced" data (B), where the number of abusive messages is equals to the non-abusive ones.

Experimental Setup

Our experiment is designed as a multi-stage classifier pipeline, as described in Figure 2 (each box corresponds to a stage). The first stage (Raw Messages) consists in building the corpus. Messages from both the Abuse and Non-abuse classes are extracted from the database as explained in Subsection 4.1. The corpus is then split into a Train set containing 70% of the messages, and a Test set containing the remaining 30%. In the fourth stage (Feature Extraction), we extract the features described in Section 3 from the messages. As explained before, some of these are derived from the messages before any normalization or preprocessing, whereas some others require a specific preprocessing. We then use another classifier, a Support Vector Machine (SVM). We could directly feed the Bag Of Words to the SVM. However, given the size of the vocabulary in our experiments, this would lead to a dimensionality issue, with a number of features greatly exceeding the number of instances in the corpus. Therefore, we prefer to consider the decision from the Naive Bayes classifier (third stage) as an additional feature given to the SVM. We get a total of 67 distinct features, including the Naive Bayes decision, which are all gathered into an array.

The fifth stage (SVM Classifier ) is the final classification: the feature arrays from the Train set are fetched to an SVM classifier, and the resulting model is then used to generate class predictions for the Test set.

Results

We evaluate the performance of our proposed abusive message detection system in terms of the traditional Recall, Precision and F -Measure. Given the relatively low number of abusive samples of the targeted corpus, the whole dataset was split into 10 parts and every result given in this section is the average value over a 10-fold cross validation. In order to show the contribution of the features as well as pre-processing approach proposed, three system configurations are studied. The first is the baseline, which relies on the classic feature set and the basic preprocessing, as previously described. The two others are our contributions: on the one hand the full feature set with basic preprocessing, and on the other hand the full feature set with advanced preprocessing.

Table 2 presents the performance obtained by the proposed system for all the studied configurations, using unbalanced data. We can firstly see that, no matter the considered message type (iM only, cM only, or iM+cM), improvements in terms of Precision, Recall and F -measure are observed when completing the baseline system (classic features and basic preprocessing) with our new features. This gain is even more important when using our advanced preprocessing, with F -measure increases of 3.1 points (iM only), 3.3 points (cM only) and 3.2 points (iM+cM) compared to the baseline system. The same observations can be made for the results obtained on the balanced data, displayed in Table 3, but with smaller gains (3.3, 1.4 and 1.3 points, respectively). Table 3. Classification results (in %) of the automatic abusive message classification system, obtained by applying different feature sets and preprocessing configurations to the balanced data.

applying the Platt Scalling implementation of the Scikit-Learn Library [START_REF] Pedregosa | Scikit-learn: Machine learning in python[END_REF]). For a fully automatic system, requiring to be very precise on the decision to take (i.e. be sure that the message is abusive), a higher threshold should be used, with a loss in terms of number of detected abusive messages (i.e. lower Recall). On the contrary, for a software assisting a moderator, needing to recover as many abusive messages as possible, a lower threshold should be used, resulting in a higher recall (more abusive messages are retrieved) associated to a lower precision (more non-abusive messages be wrongly returned by the system). The plot shows a short plateau in the middle, which means it would be possible to increase the Recall without losing much Precision. However, estimating the exact optimal decision threshold will require more data. We now take a look at how the features are contributing to the result. We use a tree-based estimator from the Scikit-Learn library to estimate the importance of the features for our classification problem. This tool is stochastic, so the score measuring this importance can vary from one run to the other. Thus, we ran it 200 times to get stable results. The right plot in Figure 3 shows all of these runs as well as the average curve. It displays how the F -Measure evolves as the features are removed one by one, by increasing order of estimated importance. Our SVM classifier is trained and evaluated at each feature removal. Despite the stochastic nature of the process, the last removed (and therefore most important) feature is always the Naive Bayes decision: this makes sense, since it is already the output of a full-fledged classifier. This is confirmed by the tree-based estimator, which gives an importance score of 42.5%.

Each of the 200 runs shows a sharp drop at the end. We detected that this drop is due to the removal of any feature in the following group: Number of bad words in the collapsed comment, Average word length, PNE and Applicability criterion for PNE. We therefore conclude that these features are complementary, and result in a strong classifier when combined. According to the tree-based estimator, these four features have a combined importance score of 15.9%. So, our results show that a small group of 5 features account for 58.4% of the classifier performance. The rest of the features improve the performance only marginally. Other noteworthy features include the ratio of letters and other characters (5%), the ratio of capitalized letters (2.1%), and the positive and negative scores (4.23%). The Business Score feature, defined by us specifically for the targeted online community, has only an importance of 1.13%: it accounts for a small part of the classifier decision, but on the positive side it is fast to compute. This is not the case for the PNE feature: computing it is expensive both in terms of CPU time and memory since we need to build and store a complete model of multiple user speech patterns.

Conclusion

In this paper, we developed a system to classify abusive messages from an online community. It is developed on top of a first-stage Naive Bayes classifier and relies on multiple types of features: morphological, language-and contextbased features, that have proven their usefulness in previous research. We added several features that we derived directly from observations of our corpus, and developed a context-based feature that aims to capture abnormal reactions from users caused by an abusive message. Our goal here was to explore a large number of features to identify the most relevant one for the problem at hand.

Our results show that abusive messages have characteristics that can be caught by an automatic system, our proposed system achieving a Recall and a Precision of more than 76% on our dataset. While the performance of the system is not good enough yet to be deployed as fully automatic moderation tool, this can already help moderators focus on messages being identified as abusive, before a manual verification is made. However, because some features used in the system are specific to the community in which it is meant to operate, care must be taken when adapting the system to work on a different dataset. Our results also show that a small number of features, including both generic and problem-specific ones, account for most of the classifier decision.

We now plan to pursue our work in several ways. First, because preprocessing has been shown to have an important effect on overall performance, we will experiment with computationally more demanding preprocessing methods, such as the HMM-based preprocessor from [START_REF] Lee | Spam deobfuscation using a hidden markov model[END_REF], and evaluate their contribution to the classifier performance. Second, we want to derive variants of our PNE feature, and assess which one is the most appropriate in our situation. More generally, we plan to propose other context-based features, especially ones based on the network of user interactions.

Fig. 1 .

 1 Fig. 1. A sequence of messages broken down into n-grams. Each square represents an n-gram: red for the targeted message, blue for the surrounding messages written by other users.

Fig. 2 .

 2 Fig. 2. The full experimental setupIn the second stage (Bag of Words Features), messages are normalized, tokenized and converted into Bag Of Words. In the third stage (Naive Bayes Classifier ), the Bag Of Words representations of the Train messages are used to build a Naive Bayes classifier. This classifier is then used to generate predictions for the class of the Test messages.In the fourth stage (Feature Extraction), we extract the features described in Section 3 from the messages. As explained before, some of these are derived from the messages before any normalization or preprocessing, whereas some others require a specific preprocessing. We then use another classifier, a Support Vector Machine (SVM). We could directly feed the Bag Of Words to the SVM. However, given the size of the vocabulary in our experiments, this would lead to a dimensionality issue, with a number of features greatly exceeding the number of instances in the corpus. Therefore, we prefer to consider the decision from the Naive Bayes classifier (third stage) as an additional feature given to the SVM. We get a total of 67 distinct features, including the Naive Bayes decision, which are all gathered into an array.The fifth stage (SVM Classifier ) is the final classification: the feature arrays from the Train set are fetched to an SVM classifier, and the resulting model is then used to generate class predictions for the Test set.

Fig. 3 .

 3 Fig. 3. Left: Precision-Recall curve of the SVM classifier. Right: Evolution of the classifier performance when sequentially dropping all features but one.

Table 1 .

 1 Corpus sizes depending on the considered experimental setup (unbalanced data).

	Configuration	Abusive Messages	Non-Abusive Messages
	iM+cM	779	1558
	iM	111	222
	cM	668	1336

Let us now compare the results obtained for the different types of messages. When considering the unbalanced data (Table 2), iM and cM only lead to globally similar performances for all three considered measures. Combining them (iM+cM) does not bring any significant change. However, this is not the case for the balanced data (Table 3): the performance obtained for cM only is quite different, with a much higher Precision (+7.6 points on the advanced setup) and a lower Recall (-2.9 points). This pulls up the overall performance when using both message types (iM+cM), leading to a 76.5 F -Measure for the advanced setup, which is 4.4 points higher than with the unbalanced data.

Our experiments show that, even if acceptable results could be obtained with our abusive message detection system (best F -measure of more than 70%), performance is still not good enough to be directly used as a fully automatic system that replaces human moderation. Nonetheless, we think that this system could be useful to help moderators focus on messages considered as potentially abusive, instead of having to analyze all messages. This is illustrated by the left plot in Figure 3, which represents the Precision-Recall curve (traditionally obtained by varying the decision threshold on the SVM posterior probability obtained by


Stéphane Junca

Contractions to update Elo ratings for round-robin tournaments

Keywords: Pairwise comparisons, Elo, Markov chain, iterated random functions, contractivity. Mathematics Subject Classification. 60J20, 91D30

teaching and research institutions in France or abroad, or from public or private research centers.

Introduction

The Elo rating system is widely used for games and mainly today for online games. It can be used to rank any objects when a pairwise comparison is available [START_REF] Cattelan | Models for paired comparison data: a review with emphasis on dependent data[END_REF][START_REF] Langville | Who's # 1? The science of rating and ranking[END_REF]. Its simplicity and efficiency is a success of this ranking. In this paper, the Elo's system is mathematically studied under a very constraining assumption on the contractivity of the update. This contractivity is false for the original Elo's system but it is 'almost' true in practice. This point is discussed below in sections 3.3, 4.3. Moreover, the contractivity is an important tool to give some mathematical results, in particular for the fundamental linear model, in general to obtain the necessary stability conditions for the Elo's system. It is worth saying that Apard Elo first tried his rating system with the linear model [START_REF] Elo | The Rating of Chessplayers, Past and Present[END_REF][START_REF] Langville | Who's # 1? The science of rating and ranking[END_REF].

The Elo model The Elo rating system is first presented for 2 players. Let two players i and j with rating R n i and R n j at time n, S n ij ∈ [0, 1] the result of the match, Arpad Elo stated the following computations after each match to update the ratings,

R n+1 i = R n i + K(S n+1 ij -b(R n i -R n j )). (1.1)
Arpad Elo considered the case where the result of the match at time n + 1 is S n+1 ij = 0 or 1 and b(R n i -R n j ) is the expected score for two players as a function of the difference of the ratings at the previous time. The function b(.) has usually to take values in [0, 1]. If the difference of rating is important, the logical result, the win of the stronger player, has to affect slightly the ratings. Conversely, if the weaker player wins, then, the ratings has to be more modified.

There is another interpretation of the function b(.). If b(.) ≡ 0 in (1.1) then the rating diverges towards +∞. This is not interesting because we want to measure the strength of the player by a finite number. In some sense, the ratings are expected to converge if the strength of the players are constant. Thus, the function b(.) can be seen as a damp to stabilize the basic random walk model b(.) ≡ 0. As a stabilisator, b(.) can take values on R as it is done below. The function can also be seen as a bonus or malus function of the result of the outcome. But b(.) has some minimal constraint to sastifies. For instance, b(.) is increasing, at least non decreasing, db dx ≥ 0.

(1.2)

Arpad Elo was a physicist and stated that the natural following conservation law is fullfilled,

R n+1 i + R n+1 j = R n i + R n j . (1.3)
Since, for all i, j and n, the scores satisfy the symmetry,

S n+1 ij + S n+1 ji = 1, (1.4)
The function b(.) has to satifies the same symmetry for all x,

b(x) + b(-x) = 1, (1.5)
which means that b(0) = 1/2 and x → b(x) -1/2 is an odd function.

For the function b(.) Arpad Elo chose a centered distribution function of a normal law [START_REF] Elo | The Rating of Chessplayers, Past and Present[END_REF]. Now the logistic Elo is mainly used in practice. b(x) = 1 1 + 10 -x/400 .

(1.6)

It is motivated for 3 or more players to keep a transitivity relation beetwen the rating of players. If the player 1 is stronger than the player 2 and the player 2 is stronger than the palyer 3 then the player 1 is stronger than the palyer 3. A quantitive and more precise notion of transitivity leads to a logistic law [START_REF] Aldous | Elo ratings and the sports model: a neglected topic in applied probability?[END_REF][START_REF] Bradley | Rank analysis of incomplete block designs. I. The method of paired comparisons[END_REF][START_REF] Chetrite | The number of potential winners in Bradley-Terry model in random environment[END_REF][START_REF]Wikipedia: Elo rating system [Online[END_REF]. This important point is not more detailled here because other functions b(.) than the logistic function (1.6) are considered.

Other bonus-malus function b can be used. For instance a linear function and more generally a non decreasing function fullfilling the symmetry relation (1.5).

The K-factor has to be small in some sense. Not too big to not drastically change the rating and not too small to expect that if the rating of a player is not the good one then the process converges fastly enough to the new rating representing the real strength of the player. Jeff Sonas studied numerically the important question of the size of K [START_REF]Wikipedia: Elo rating system [Online[END_REF]. The size of K will appear below to be crucial to obtain convergence theorems.

Usually the rating is bigger than 1000 thus K 1000. In this way, if the rating are normalized to be of order O(1) replacing R n i by R n i /1000 in (1.1), the new factor is K/1000 becomes really small, and accordingly modifying the b(.) function.

Arpad Elo expected that the rating of each player represents well the strength of players after many games. Mathematically that means, in some sense, that the rating's converges to a law centered at the true value representing the skill of the player. In other words,

R n k is expected to converge in law towards R ∞ k for k = 1, 2, E(R ∞ k ) corresponds to the real strength of player k , and, b(E(R ∞ i ) -E(R ∞ j ))
is the probability that i beats j.

Notice that the model (1.1) is invariant under translation. If R n i satisfies (1.1) for all n, R n j the similar relation and 'r' be a constant then, R n i + r, R n j + r also satisfy the same relation (1.1). Thus, the pertinent information is the relative strength R n i -R n j . In all this paper only bounded independent (w.r.t. n) score S n ij are considered with the same law as S ij with S ij = 0 or 1 or with continuous values when the score can be more quantified than a win or a loss,

S ij ∈ [0, 1] or -M ≤ S ij ≤ M , sup i,j |S ij | ≤ M < +∞.
(

Keeping the same law means that the strength of the players is supposed to be constant. The independance of the score with respect to the time means that players are not affected by the previous score.

Elo assumption on the expected score: Assume that the strength of the players is constant, no learning effect as in [START_REF] Düring | Boltzmann and Fokker-Planck equations modelling the Elo rating system with learning effects[END_REF]. The score expectation of an encounter only depends on the difference of the theoritical ratings ρ i -ρ j [START_REF] Pierre-Emmanuel | Stéphane: A continuous model for ratings[END_REF] ,

E(S ij ) = b(ρ i -ρ j ), ∀n ∈ N (Elo Assumption) (1.8)
Indeed, the notion of theoritical rating or true strength is natural but generally unknonw. Furthermore, how one number can be describe the various skills of a chess player? However, to rank players only one number is needed. In the Elo's system it is implicitely expected that R n i is a random variable fluctuating around the 'real strength' for large n, so,

ρ i := lim n→+∞ E(R n i ).
(1.9)

The existence of the limit is already a mathematical problem and needs some stability of the Elo's system.

In this paper, the more general case where the score expectation only depends on the player without any notion of true rating is considered:

E(S ij ) = s ij (1.10)
Indeed, for a Bernoulli model, S ij = 0 or 1, p ij = P (S ij = 1), the matrix of scores reads,

s ij = p ij . (1.11)
It is not assumed that the mean scores s ij satisfy the Elo assumption (1.8). This is more realistic. It is well known that "circular" situations can occur, for instance:

Player number 1 is stronger than player 2, i.e. p 12 > 1/2.

Player number 2 is stronger than player 3, i.e. p 23 > 1/2.

Player number 3 is stronger than player 1, i.e. p 31 > 1/2.

More complex "cycles" can be studied with more players [START_REF] Krifa | On the convergence of the Elo rating system for a Bernoulli model and round-robin tournaments[END_REF]. Nevertheless, it is expected that the Elo rating system ranks the players after enough time. An important question is to try to identify the 'real strength' ρ i and to verify that the 'real strength' ranks well all the players.

Round-robin tournaments

The fairest tournament to rank N players is the round-robin tournament when all meet all. The following evaluation of the rating after each tournament is studied.

R n+1 i -R n i = K j (S n+1 ij -b(R n i -R n j )). (1.12)
The integer n means after n tournaments. On internet, the rating is usually updated after each match. A numerical study [?] seems to show that the result is similar for a large number of matches.

The important contractivity assumption is discussed in the section 4.3. It is not true (but 'almost' true) for the usual Elo model. It is mandatory for the linearized model.

The results obtained in the contractive setting are, condition on the size of K, convergence in law with exponential rate.

Elo ratings are bounded.

uniqueness of the invariant measure.

explicit study of the linear case:

-The Elo's system ranks well the players.

-The Elo assumption that the expected score depends on the difference of the rating is not true.

The paper is organized as follows. The convergence in law is expounded in Section 2. Section 3 deals with the linear case. The limit and the exponential rate of convergence is explicit. Some assumptions on the Elo's system are tested. Section 4 deals with the nonlinear case. The sections 3.3 and 4.3 present the main drawback of the contractivity assumption and discuss some advantages.

Convergence

The Elo vectorial Markov chain (1.12) for N players reads,

R n+1 = R n + K S n+1 -B(R n ) = G(R n ) + KS n+1 , (2.1)
with vectorial notations,

R n = (R n 1 , • • • , R n N ) T , 1 I = (1, • • • , 1) T ∈ R N , (2.2) r = (r 1 , • • • , r N ) T , B i j (r) = b(r i -r j ), (2.3)
B(r) = B(r) 1 I, (2.4)
G(r) = r -K B(r), (2.5)
S n+1 = S n+1 1 I, (2.6)
and the convention for all i

S n+1 ii = 1 2 , (2.7)
which corresponds to b(0) = 1/2 and allow us to extend the sum (1.12) also for j = i without changing the total sum. Under contrative assumptions (2.8) on the bonus-malus function the following convergence holds.

Theorem 2.1 (Bounds and exponential convergence in law)

If R 0 is the initial random vector which is bounded in L ∞ (Ω) and independent of the scores, (S n ) is a sequence of random independent matrixes with the same bounded law as S (1.7), and if the following contractance assumptions are fullfilled:

K (N -1) sup b < 1, 0 < inf b , (2.8)
then, with

γ = max(|1 -K N sup b |, |1 -K N inf b |) < 1, (2.9)
the Markov chain (R n ) n converges in law, with the exponential rate γ, to the law of the random variable

R ∞ + 1 N (R 0 • 1I) 1I
where R ∞ ⊥ 1I, R ∞ is independent of R 0 and its law µ ∞ is the vector valued measure supported on the hyperplane 1I ⊥ uniquely determined by:

µ ∞ = (Id -K B)#µ ∞ λ S , (2.10)
where # is the push-forward of a measure by an application, denotes the convolution of measures, and λ S is the S' law. The support of µ ∞ is bounded. Let the vector r ∞ uniquely defined by r ∞ ⊥ 1I and

r ∞ = G(r ∞ ) + E(S 1I) then R ∞ -r ∞ ∞ ≤ K 1 -γ (S -E(S)) 1I ∞ . (2.11)
This theorem can be seen in the framework of 'contractive iterated random functions' [START_REF] Diaconis | Iterated random functions[END_REF]. The point here is that the map Id -K B is not contractive on R N but on the hyperplane 1 I ⊥ .

Another point is the compact support of the limit law which is again a consequence of the contractivity (2.8) and it is not true for the used Elo model (1.6) where inf b = 0 [START_REF] Krifa | On the convergence of the Elo rating system for a Bernoulli model and round-robin tournaments[END_REF].

¨The convergence of the sequence (R n ) towards a random variable R ∞ is not expected [START_REF] Diaconis | Iterated random functions[END_REF]. Else, by (2.1), R ∞ has to satisfies: B(R ∞ ) = S. This is false (except the non interesting case when S is a constant).

Notice that, a priori, the limit depends on the factor K.

The linear case is first presented with more precise results. The limit in law is 'explicit', the optimal contractive assumption is provided, and the Elo assumptions (1.8) are studied. After, the convergence in law for the nonlinear case is given.

Linear recurrence

The linear case only means that the bonus-malus function is linear,

b(r) = 1 2 + L r. (3.1)
In practice, L is quite small, L = b (0) = ln(10)/1600 ∼ 10 -3 . For small r it corresponds to the expectation to win if the ratings difference is r. It is an approximation for |r| < 200. Conversely, for r too big, [r| > 1/L ∼ 1000, |b(r)| > 1 so it does not correspond to a probability. Indeed, it is a malus (resp. a bonus) to have a too big (resp. a too small) Elo. Thus, after the encounter, independently on the outcome, there is a loss (resp. win) of Elo points. It is a reason why the linear function b is not used. This discussion is continued in Section 3.3. Nevertheless, usually players have a rating difference ≤ 400 1000, so this linear model is a interesting to try to understand such typical situations. Moreover, Arpad Elo himself had started to study the linear Elo [START_REF] Elo | The Rating of Chessplayers, Past and Present[END_REF][START_REF] Langville | Who's # 1? The science of rating and ranking[END_REF]. Notice that the Elo ranks well the players in figures 1, 2, 3, 4.

The linear case is also an interesting simplest case to test or unvalid some usual assumptions on the Elo's system presented in the introduction.

This section is organized as follows. First, a general result on linear Markov chains is given [START_REF] Diaconis | Iterated random functions[END_REF][START_REF] Meyn | Markov Chains and Stochastic Stability[END_REF]. Second, the special case of the linear Elo rating is studied. Third, some asssumed behaviors of the Elo rating system are checked on the linear case.

Vectorial linear Markov chain

Consider a general vectorial linear iterative Markov chain [START_REF] Diaconis | Iterated random functions[END_REF],

R n+1 = A R n + S n+1 , (3.2)
where

R 0 is given, R n ∈ R N , A ∈ M n,n (
R), (S n ) a random independent vectorial sequence in R N with the same law as S, and R 0 is indepent of f this sequence. This is a well known subject [START_REF] Diaconis | Iterated random functions[END_REF]. The convergence result is recalled with a simple proof to be self-contained. A more general result can be found and proved in [START_REF] Diaconis | Iterated random functions[END_REF]. If the spectral radius of A satisfies (A) < 1, R 0 and S is a bounded random vector, R 0 , (S n ) are independent, then (R n ) convergences in law towards R ∞ with a geometric rate,

R n L -----→ n→+∞ R ∞ = +∞ n=0 A n S n , (3.3) R ∞ ≤ S 1 -|||A||| (3.4) sup n R n ≤ R 0 + S 1 -|||A||| , (3.5)
lim n→+∞ E(R n ) = E( R ∞ ) = (Id -A) -1 E(S), (3.6
)

|||Cov( R ∞ )||| ≤ 1 1 -|||A||| 2 |||Cov(S)|||, (3.7)
for a vector norm . on R N such that the induced matrix norm satisfies

|||A||| := sup R =0 AR R < 1.
The matrix Cov(X) is the covariance matrix of the random vector X,

Cov(X) = E([X -E(X)][X -E(X)] T ).
We cannot expect a convergence almost everywhere of the Markov chain. Indeed, if R n converges a.e. then S n also converges a.e. by (3.2). This convergence contradicts the independance of the sequence S n (except in the trivial case when S is almost surely constant).

Notice that the law of R n is uniformly compactly supported.

Proof : Equation (3.2) yields:

R n+1 = A n+1 R 0 + n j=0 A j S n+1-j
Since ρ(A) < 1 and R 0 is bounded , A n+1 R 0 converges with a geometric rate towards the vector 0. By the independance of the sequence (S n ) and R 0 , R n+1 has the same law as R n+1 :

R n+1 L = R n+1 = A n+1 R 0 + n j=0 A j S j .
R n converges uniformly towards R ∞ with a geometric rate . R n+1 and R n+1 have the same law, thus R n+1 = R n+1 ≤ R 0 + n j=0 |A| j S , and the uniform bounds (3.4), (3.5) follow.

The convergence in law and the previous uniform bound (3.5) imply the convergence of the esperance and the variance, so we can use (3.2) or the summation of the geometric series,

E Ä R ∞ ä = A E Ä R ∞ ä + E(S), Cov Ä R ∞ ä = A Cov Ä R ∞ ä A T + Cov(S), Cov( R ∞ ) = +∞ n=0 A n Cov(S) Ä A T ä n ,
which concludes the proof.

The limit is generally not a discrete law. Consider, this simple scalar example where S follows a symmetric Bernoulli law B(1/2) and:

R n+1 = 1 2 (R n + S n ), R 0 ≡ 0.
The limit law is simply the uniform law on [0, 1], U([0, 1]). An interesting discussion on the properties of the limit law in dimension 1 can be found in the review [START_REF] Diaconis | Iterated random functions[END_REF].

The linear Elo

Now the linear Elo model (3.1) is studied. This function satisfies (1.5), it is an increasing function and it fits well the usual bonus function (1.6) with L ≈ 0.001, but the function b(.) is not bounded.

A key role is played by the constant vector 1 I. It is related to the conservation of the total sum of Elo ratings. It is invariant by the matrix A involved in this linear Markov chain. Thus, the matrix A is not contractive on R 1 I. Hopefully it can be contractive on the hyperplane 1 I ⊥ .

The important Elo assumptions (1.8) are discussed on this simplest model by computing the 'real strengths' ρ i , i = 1, . . . , N , (1.9).

Let us start by some invariance properties also valid fo the nonlinear case (1.12). Invariance under translation: for any r ∈ R,

R n + r 1I
satifies recurrent system (1.12). That is to say we can translate all the ratings by the same contant r: R n i = R n i + r. Conservation of the total rating: for all n ∈ N ,

R n • 1I = R 0 • 1I, that is to say N i=1 R n i = N i=1 R 0 i .
Proof : The following proof does not use the linearity of b(.) and is still valid for a nonlinear b(.). The Elo update (1.1) in vectorial form (2.1) can be rewritten with the difference,

R n+1 -R n = K S n+1 -B 1 I. (3.8)
The matrix B only involves the differences of ratings, so R n satisfies the same relation and the invariance by translation follows.

The matrix S and B have the same symmetry from (1.4), (1.5).

S + S = U = B + B , (3.9)
with U ij = 1 for all i and j. That means that S -(1/2)U and B -(1/2)U are skew-symmetric.

Moreover U = 1 I 1 I , so the useful identities follow,

1 I S + S 1 I = 1 I U 1 I = ( 1 I 1 I) 2 = N 2 = 2 1 I S 1 I, (3.10) 1 I B + B 1 I = N 2 = 2 1 I B 1 I, ( 3
1 I R n+1 -R n = K 1 I S n+1 -B 1 I = K(N 2 -N 2 )/2 = 0,
and the conservation of 1 I R n follows.

Notice that only the symmetry of S and B are used, so the proof is valid for the nonlinear case. Proof : For all i, the following computations yield the announced result,

B ij (r) = 1/2 + L(r i -r j ) (B(r)) i = (B(r) 1 I) i = N/2 + N j=1 L(r i -r j ) = N/2 + L Ñ N r i - N j=1 r j é = (1/2)U + L N Id -U r 1 I i .
Lemma 3.2 On 1I ⊥ , the matrix B is the homothety L N Id.

(L N ) -1 B is the matrix of the orthogonal projection on 1 I ⊥ and Ker B = R 1 I.

Proof : The spectrum of U is {N, 0} and the multiplicity of 0 is N -1, since rank U = 1 and U 1 I = ( 1 I 1 I ) 1 I = N 1 I. In other words, N -1 U is simply the orthogonal projector on R 1 I. Thus U is diagonalizable with spectrum {0, N } and 0 has the multiplicity N -1. Then, B is also diagonalizable. The spectrum of B is {0, L N } and the multiplicity of L N is N -1. Thus B is the matrix of the linear map on R N such that the restriction on 1 I ⊥ is simply L N Id.

Now, the asymptotic behavior of R n is stated in the linear case.

Theorem 3.3 (Asymptotic law, expectation and covariance) Assume R 0 is a random bounded initial vector independent to the scores and

K L N < 2, (3.12)
then, R n converges in law with the geometric rate γ, |γ| < 1,

γ = 1 -K L N, (3.13)
R n L -----→ n→+∞ 1 N (R 0 • 1I) 1I + R ∞ , (3.14) 1I ⊥ R ∞ := K ∞ n=0 γ n S n , (3.15)
E(R ∞ i ) = 1 L N j =i s ij , (3.16
)

Cov(R ∞ ) = K 2 1 -γ 2 Cov(S).
(3.17)

Note that the asymptotic expectation does not depend on K. On the contrary the standard deviation depends on K.

A consequence of the contractive assumption (3.12) is a bound of the number of players for a round-robin tournament, for K = 20 used for amator chess players by the FIDE (international chess federation) N < 2/(K L) = 100, with K = 20 and L = 1/1000, and for professional players (chess masters) K = 10 so N < 200. In practice, the number of players for round robin-tournament is around 10 so the contractance of the update is assured.

If K L N = 1, then γ = 0 and the convergence is reached at N = 1, R ∞ = KS.
This is a discrete random vector if S is discrete. In general a not discrete variable is expected for γ = 0 [START_REF] Diaconis | Iterated random functions[END_REF].

Proof : The framework of linear Markov chain (3.2) is used with A = Id -K B and S n+1 is replaced by K S n+1 . Unfortunatelly, A 1 I = 1 I so, the spectral radius ρ(A) = 1 and Theorem 3.2 cannot be used directly. But, the restriction of A on 1 I ⊥ is simply (1 -K L N )Id 1 I ⊥ = γId 1 I ⊥ , and,

Id 1 I ⊥ -A 1 I ⊥ = (K L N )Id 1 I ⊥ , Lemma 3.2.
Thanks to the invariance by translation, Proposition 3.1, R n can be replaced by R n -1 N (R 0 • 1 I) 1 I. Now R n ⊥ 1 I for all n and the contractivity of A on 1 I ⊥ can be used. On 1 I ⊥ , the limit of the rating is performing thanks to Theorem 3.2. The induced euclidean norm can be used on 1

I ⊥ since |A 1 I ⊥ | 2 = |γ| < 1.

Individual Variance

The asymptotic variance of each rating depends on K and the number of players. It has the order K 2 N due to size N × N of the score matrice S and the bound of the independent coefficients (1.7),

V ar(S

i ) = j =i V ar(S ij ) ≤ (N -1)M 2 V ar(R ∞ i ) = K 2 1 -γ 2 V ar(S i ) ≤ K 2 N M 2 1 -γ 2 .
(3.18)

Moreover, the contractivity assumption K L N < 2 also yields to,

V ar(R ∞ i ) ≤ K 2M 2 L(1 -γ 2 )
.

Another way to bound the individual variance from Inequality (3.18) and finally eliminating K is,

V ar(R ∞ i ) ≤ K 2 N M 2 1 -γ 2 = K 2 N 2 L 2 N L 2 M 2 (1 -γ 2 ) = 1 N (1 -γ) 2 (1 -γ 2 ) 2M 2 L 2 , = 2 N 1 -γ 1 + γ Å M L ã 2 ≤ 2 N Å M L ã 2 .
That means that bigger is N , smaller is K and smaller is the variance. From Inequality (3.18), the variance can be seen of order K by eliminating N using the contractivity assumption,

N < 2/(K L), V ar(R ∞ i ) ≤ K 2 M 2 L(1 -γ 2 )
. Convergence towards the real strengths The Elo assumption (1.8) is first supposed. That reads for E(S ij ) (1.10),

s ij = b(ρ i -ρ j ) = L (ρ i -ρ j ) (3.19)
Notice that this assumption is very constraining. They are (N -1)N/2 unknowns for the quantities (s ij ) since they satify the symmetry (1.4). There are only N -1 independent parameters ρ i since ρ ⊥ 1 I or the model is invariant by translation. Therefore the nonlinear system (3.19), 1 ≤ i < j ≤ N to define ρ i (up to a translation) is quite overdeterminated, expect for the case N = 2. Nevertheless, in this case (3.19) and for the linear model the ratings converge towards the ρ i (up to a translation).

Proposition 3.2 (About Elo assumption) Assume ρ ⊥ 1I. If the matrix (s ij ) ij lives in the N -1 vetorial subspace of matrixes defined by (3.19), that is to say the Elo assumption (1.8) is true, then , the expectation of the limit rating law is the theoritical Elo rating, E(R ∞ i ) = ρ i for all i. Proof : The limit law is R ∞ given by Theorem 3.3. It suffices to apply the equality (3.16),

E(R ∞ i ) = 1 L N j =i s ij = 1 L N j =i L(ρ i -ρ j ) = 1 N N j=1 (ρ i -ρ j ) = ρ i - 1 N (ρ • 1 I) = ρ i .
Without the Elo assumption (1.8), the true skill is naturally given by the expected total score for a round-robin tournament.

s i := 1 N -1 j =i s ij .
(3.20)

These quantities rank the players. Indeed, under the contractive assumption (3.12) the limit rating is a biased estimation of s i . Therefore the mean ratings rank well the players.

Proposition 3.3 (Convergence towards the true skill)

Assume K L N < 2, then, the following convergence of the empirical rating holds

ρ i := lim n→+∞ E(R n i ) = 1 L Å 1 - 1 N ã s i + 1 N (E(R 0 ) • 1I). ( 3

.21)

Proof : This is again a corollary of Theorem 3.3. From (3.15), the following equality holds

ρ i = E(R ∞ i ) + (E(R 0 ) • 1 I)/N. Now,
as in the proof of Proposition (3.2) with equality (3.16), we have

L E(R ∞ i ) = 1 N j =i s ij = N -1 N s i
which concludes te proof.

Why is the linear Elo not used?

In this section, the score belongs to [0, 1] (M = 1) to discuss the probabilistic interpretation of the function b. Arpad Elo first assumed that the score is 0 or 1, [START_REF] Elo | The Rating of Chessplayers, Past and Present[END_REF]. In this case the score is a Bernoulli law and E(S n ij ) = p ij is the constant probability such that i beats j.

For the linear Elo, the function b is not confined in [0, 1]. Thus the interpretation as a probability to win is lost when b(∆r) > 1 where ∆r is the difference of the rating between the strongest and the weakest player. The critical value is approximately the prime number 347, Nevertheless, in this section, It is shown that the linear Elo is quite good for difference of ratings less than 347 Linear arguments are implictly used for the initialisation of the rating, and the Elo performance. A main other drawback is the loss of Elo points for a too strong winner. However, further reflections shows that such a loss occurs only marginally for two players. In fact, it is shown below that the interval

I A = Å - 1 2L , + 1 2L ã ≈] -347, 347[, (3.23)
is an attractive set for the difference of the ratings and almost a stable set. Thus such dramatic events as b(R n i -R n j ) is not a probability or the winner losses Elo points are not so important.

Linear approximation

The error between the linear and the logistic function b is computed for different values of ∆r, error = (1/2 + L∆r) -(1/(1 + 10 -∆r/400 ). ∆r 100 200 300 347 400 500 1000 error ≈ 0.004 0.03 0.08 0.12 0.17 0.27 0.94

The logistic function (1.6) is quite flat and the linear approximation is good enough for |r| < 300 with L = b (0) = ln(10)/1600 ≈ 0.0014.

Elo initialisation

Due to the slow convergence of the Elo it is important to have a good initial Elo for a new chess player. Before having an Elo, the new player plays ν games against rated players. Let R 1 , . . . , R ν the ratings of the rated player encountered, S i the score in {0, 1/2, 1}, R = (R 1 + . . . + R ν )/ν the mean rating and S = (S 1 + . . . + S ν )/ν the mean score, the initial Elo R 0 = R + b (-1) (S). In other words, the initialisation of the Elo R 0 is uniquely defined by the relation,

S = b(R 0 -R).
(3.24)

Implicitely, using means score and means rating, it is a linear way to compute the initial Elo after ν games. It coincides with the limit rating in the linear case if the new player always has the same result in an infinite serie of round-robin tournaments with the same players (3.21).

Elo performance

The Elo performance for a tournament is exactly computed as the Elo initialisation (3.24). Thus, again, it is a linear argument assuming implicitly that the bonus-malus function is linear.

Loss of points for the winner This becomes possible and it is a real drawback for the linear Elo. In the following computations the loss of Elo points is computed with K = 20 for the highest rating which is the strongest player and wins the match but loses Elo points. ∆r = 347 400 500 600 700 800 900 1000 loss ≈ 0 -1.5 -4 -7 -10 -13 -16 -19

For professional chess players (International Master) K = 10 and the loss is the half. In the next paragraph, it is explained a scenario where a such big loss cannot occur.

Bounded stable set Consider first the case of only two players i and j. Let

D n = R n i -R n j
the difference of rating. A stable interval is, with K = 20, Notice that the stability condition 2 K L < 1 for I S is stronger than the contractivity condition (3.12) which reads for two players (N = 2), K L < 1. The Elo is expressed with D n thanks to the mass conservation (1.3),

I S = Å - 1 2L -2K, + 1 2L + 2K ã ≈] -387, 387[, ( 3
R n i = m 0 + D n /2,
where the total mass is 2m 0 = R 0 i + R 0 j . Thus R n i belongs to translated interval m 0 + (1/2)I S for all n.

Moreover, when D n belongs to I s but outside I A , the dynamics is attractive to come back in I A . There is a particular case when D n is exactly at the boundary of I A , D n 0 = 1/(2L) and for n > n 0 the player i always wins then D n stays at the boundary. In fact, the dramatic loss of points for the winner only occurs when D n belongs to the set I S -I A .

Proof : By symmetries (D n ) satisfies the recurrence relation [START_REF] Krifa | On the convergence of the Elo rating system for a Bernoulli model and round-robin tournaments[END_REF],

D n+1 -D n = 2 K Ä S n+1 ij -b(D n ) ä
Assume that D n belongs to I A and D n is positive. The negative case can be handle in a similar way. There are two cases. If D n belongs to

I A then 0 < b(D n ) < 1 and D n+1 ≤ D n + 2K ≤ 1/(2L) + 2K, i.e. D n+1 ∈ I S . If 1/(2L) ≤ D n < 1/(2L) + 2K, that is D n belongs to I S but outside I A , then 1 ≤ b(D n ) < 1 + 2KL ≤ 2 and -4K = 2K(0 -2) < D n+1 -D n , then -1/(2L) -2K ≤ 1/(2L) -4K ≤ D n -4K < D n+1 ≤ D n . Thus D n+1 cannot go outside I S .
Finally, by induction, D n stays in I S for all n.

The extension for N players is now exposed.

Proposition 3.5 (N players) Let N m 0 = R 0 1 + . . . + R 0 N be the total mass,

J A = m 0 + Å - 1 2L , + 1 2L ã , J S = m 0 + Å - 1 2L -N K, + 1 2L + N K ã . The set J S is table under condition K L N < φ = (1 + √ 5)/2 ≈ 1.6.
Moreover, under the strong contractive assumption K L N < 1, there exists n 0 ≥ 0 such that, for all n ≥ n 0 and all i ∈ {1, . . . , N }, R n i ∈ J S . In fact, all R n i approach J A when n → +∞,

lim sup n→+∞ N max i=1 |R n i -m 0 | ≤ 1 2L . (3.26)
The mean mass m 0 has a central role due to the mass conservation. The contractive assumption used here is stronger than condition (3.12). This proposition suggests that it is more stable to update the Elo after each match instead of each round-robin tournament since I S is smaller than J S . See also [START_REF] Krifa | On the convergence of the Elo rating system for a Bernoulli model and round-robin tournaments[END_REF]. Proof : The recursion formula (1.12) is rewriten using the linearity of the function b. Incidentally, it gives another proof of the convergence in law for the linear case. For this purpose, introduce the notations, the total score

S n+1 i = S n+1 i1 + . . . + S n+1 iN N .
Notice that the sum is extented also for j = i. In this way, the mean score appears in the recursion formul. The mean score is quite fundamental since it is the constant m 0 due to the mass conservation. Furthermore, the term for j = i does not add someting since

S n+1 ii -b(0) = 1/2 -1/2 = 0. R n+1 i -R n i = K N j=1 Ä S n+1 ij -b(R n i -R n j ) ä .
Now, the mean quantities are used,

R n+1 i -R n i = N K Å S n+1 i - 1 2 -L(R n i -m 0 ) ã . (3.27)
This formula can again be written in two ways. The first way is

R n+1 i -R n i = N K Ä S n+1 i -b(R n i -m 0 ) ä . (3.28)
There is a simple interpretation of (3.28). It is like the player i plays against only one player having the mean rating, which is constant due to the mass conservation, and has the mean score

S n+1 i ∈ [0, 1]
. The constant K is replaced by N K reflecting that (N -1) matches are played (the match j = i does not exist). The second way is

R n+1 i -m 0 = γ(R n i -m 0 ) + N K Ä S n+1 i -1/2 ä , γ = 1 -K L N. (3.29)
The constant γ ∈] -1, 1[ under the contractive assumption K L N < 2. The formula (3.29) is powerful enough to prove again Theorem (3.3).

The stability of J S is first proven with formula (3.27) and assumption K L N < φ. So, assume that R n i ∈ J S . Two cases are considered,

R n i ∈ J A or R n i / ∈ J A When all the ratings R n i belong to J A then L|R n i -m 0 | < 1/2, and R n+1 i -R n i ≤ N K, i.e. R n+1 i ∈ J S . Now, consider that R n i does not belong to J A . For instance R n i > m 0 + 1/(2L), then L(R n i -m 0 ) > 1/2 and R n+1 i < R n i . Then R n+1 i decreases.
We have to check that it does not decreases too much and leaves J S . Indeed, it stays in J S thanks to the following computations,

R n+1 i ≥ R n i -N K|1/2 + L(R n i -m 0 )| ≥ R n i -N K|1/2 + 1/2 + KLN | > (m 0 + 1/(2L) + N K) -KN (1 + φ) = m 0 + 1/(2L) -φN K > m 0 -1/(2L) -N K,
since the last inequality is equivalent to (φ -1)KN ≤ 1/L, but KLN < φ and (φ -1)φ = 1, (φ 2 = φ + 1). . Now, the attractivity of J A (3.26) is proven under the stronger condition

K L N ≤ 1, so 0 ≤ γ < 1. Notice that |S n+1 i -1/2| ≤ 1/2 since 0 ≤ S n+1 i ≤ 1.
Thus, Formula (3.29) yields,

|R n+1 i -m 0 | ≤ γ|R n i -m 0 | + N K/2.
Such inequality allows to pass to the limit sup and yields,

lim sup |R n i -m 0 | ≤ 1 1 -γ N K/2 = N K 2KLN = 1 2L .
In this last line the fact that there is γ instead of |γ| is crucial to the last inequality, else a bigger interval appears. Thus, (3.26) is proved with 0 ≤ γ < 1. As a consequence, there exists n 0 such that all the rating R n 0 i belong to J S . Due to the stability of J S they stay in J S and continue to approach J A .

Nonlinear recurrence

For the nonlinear case, an elemtary proof of the convergence and the uniqueness of the equilibria is given. This is a case well known in probability [START_REF] Diaconis | Iterated random functions[END_REF]. The interesting case is the study of the Elo where the map is not contractive on the whole space due to the invariance by translation of the Elo. Nevertheless, it is shown that the Elo mapping is a contractor on the hyperplane 1 I ⊥ when the bonus-malus function b is a contractor and K is not too big. This is enought to apply a classic result on iterated contractive random mappings.

Contractor in L ∞

A more general result can be found in [START_REF] Diaconis | Iterated random functions[END_REF] using other norms and less restrictive assumption on the contractive mapping. For our purpose, the following result is now presented, self-contained and used for the contractive Elo right after.

Theorem 4.4 [Contraction mapping] Let (S n ) be a sequence of independent bounded random vector in R d with the same law S, G(.) a contractive map on R d with 0 ≤ γ < 1 be its Lipschitz constant, R 0 be a random bounded variable independent to (S n ) and the Markov chain R n defined as follow,

R n+1 = G(R n ) + S n+1 . (4.1)
Then the sequence (R n ) converges in law towards a bounded random vector R ∞ such that its law µ ∞ is the vector valued measure uniquely determined by,

µ ∞ = (G#µ ∞ ) λ S ,
where λ S is the measure of the S law. Furthermore, let r ∞ be the constant vector uniquely defined by

r ∞ = G(r ∞ ) + E(S) then, R ∞ (ω) -r ∞ L ∞ (Ω,R d ) ≤ 1 1 -γ S -E(S) ∞ . (4.2)
Notice that, we cannot expect the convergence of the sequence R n , else from the reccurence relation that means that S n converges. Since (S n ) is i.i.d, that means that S n is constant.

Remark 4.1 Altough, the limit expectation is unknown, (4.2) shows that the limit law is close to a fixed point, closer if all the d standard deviation (S i ) 1≤i≤d are small.

Proof : The idea is to prove the convergence of another sequence (W n ) such that W n has the same law as R n by reversing the time [START_REF] Diaconis | Iterated random functions[END_REF] as for the linear case.

V n+1 k+1 = G(V n k ) + S n+1-k , k ≤ n and V n 0 = R 0 .
Since (S n+1-k ) n≤N and (S n+1 ) n≤N have the same law, W n+1 = V n+1 n+1 has the same law as R n+1 . It remains to prove the convergence of the sequence (W n ). For k = n, n -1, • • • , 1, since the term S n+1-k is time reversed, the simplifications of the source term follows,

V n+1 k+1 -V n k = G(V n k ) -G(V n k-1 ), |V n+1 k+1 -V n k | ≤ γ|V n k -V n k-1 |, |W n+1 -W n | = |V n+1 n+1 -V n n | ≤ γ n |V n+1 1 -V n 0 | ≤ γ n |G(R 0 ) + S n -R 0 | ≤ γ n C, where the constant C ≤ R 0 ∞ + G(R 0 ) ∞ + S ∞ .
Thus (W n ) converges uniformly and (R n ) converges in law. Passing to the limit in the relation (4.1) gives the equation for the limit law (4.2).

The uniqueness is the consequence of the previous convergence and the contractance. The proof of the uniqueness is simpler than the proof of convergence. Assume there is two equilibria. Takes R 0 and R0 two random variables associated to these two equilibria. Let R n and Rn be the associated sequence at time n with the same sequence (S) in (4.1) but with different initial random variables R 0 and R0 . Thus R n and Rn have the same law has their initial data. Moreover, R n -Rn satisfies an homogenous recurrence relation,

R n+1 -Rn+1 = G(R n ) -G( Rn ) so |R n+1 -Rn+1 | ≤ γ|R n -Rn | and |R n -Rn | ≤ γ n |R 0 -R0 |.
By contractance and the uniform bound, R n -Rn → 0 uniformly. Thus the limit laws are equal.

It turns to get the L ∞ estimate (4.2). Summing up the inequality

|W n -W n-1 | ≤ γ n-1 |G(R 0 ) + S n -R 0 | yields the upper bound |W n -W 0 | ≤ |W n -W n-1 | + . . . + |W 1 -W 0 | ≤ |G(R 0 ) + S n -R 0 |/(1 -γ).
The limit is independent of the initial data R 0 due to the previous uniqueness result. With R 0 = r ∞ , since W 0 = R 0 , and taking advantage that r ∞ is a fixed point, the inequality becomes,

|W n -r ∞ | ≤ |G(r ∞ ) + E(S) -r ∞ + (S n -E(S)|/(1 -γ) = |S n -E(S)|/(1 -γ) ≤ S -E(S) ∞ /(1 -γ).
Passing to the limit the same bound is valid for R

∞ , |R ∞ -r ∞ | ≤ | S -E(S) ∞ /(1 -γ) which concludes the proof.

The nonlinear contractive Elo

To use the general theorem 4.4 on contractive map, we recall that the Markov chain associated to the Elo (1.12) can be rewritten in the vectorial form (2.1) as follows:

R n+1 = G(R n ) + K S n , G(r) = r -K B(r).
The contractive property of G(.) depends on the properties on B(.). So, the map B(.) is first studied. Notice that B(.) is not injective on R N since

B(R 1 I) ≡ 1 2 U, B(R 1 I) ≡ N 2 1 I, ( 4
(B(r) -B(r )) • (r -r ) ≥ (inf b ) 2 ( r -r 1 I ⊥ ) 2 , ∀r, r ∈ R N , (4.5)
where

r 1 I ⊥ 2 = N i=1 N j=1 (r i -r j ) 2 is an euclidean norm on 1I ⊥ .
The map B(.) is a gradient, Second, the coercive estimate (4.5) is performed on the scalar product s defined by,

B(r) = ∇ψ(r 1 , . . . , r N ), (4.6)
ψ(r) = 1 2 Ñ i j β(r i -r j ) -N N i=1 r i é , β (x)
s := (B(r) -B(r )) • (r -r ) = N i=1 N j=1 (b(r i -r j ) -b(r i -r j ))(r i -r i ).
Exchanging i and j and using the symmetry relation (1.5), another formula is obtained for s, as in [START_REF] Pierre-Emmanuel | Stéphane: A continuous model for ratings[END_REF],

s = N i=1 N j=1 (b(r j -r i ) -b(r j -r i ))(r j -r j ) = N i=1 N j=1 ((1 -b(r i -r j )) -(1 -b(r i -r j )))(r j -r j ) = - N i=1 N j=1 (b(r i -r j )) -b(r i -r j ))(r j -r j )
Adding the two expressions of s yields,

2 s = N i=1 N j=1 (b(r i -r j ) -b(r i -r j ))((r i -r i ) -(r j -r j ))
The monotonicity on b with δ = inf b > 0 yields to a lower bound for 2 s, (r i -r j )(r i -r j ).

(b(x) -b(y))(x -y) ≥ δ(x -y) 2 2 s = N i=1 N j=1 (b(r i -r j ) -b(r i -r j ))((r i -r j ) -(r i -r j )) ≥ N i=1 N j=1 δ(r i -r i -(r j -r j )) 2 = δ r -r 2
The bilinear form is non negative and vanishes on R 1 I. On 1 I ⊥ , for r = 0 1 I ⊥ , r 1 I ⊥ > 0 since the condition 0 = 1 I r = r i and r = 0 insures that there exist i and j such that r i = r j .

Fourth, B(.) is a gradient, Finally, the diffeomorphism property is a consequence of the monotonicity. Now, the contractivity is obtained under the assumption inf b > 0 (4.4). Notice that G(.) is not contractant on R d since G(t 1 I) = (t -K N/2) 1 I for all t ∈ R, (4.3). Indeed, the optimal Lipschitz constant of G(.) on R N is 1.

The contractivity condition (4.7) is similar as the linear case (3.12) (and exactly the same for N = 2).

Proof : The differential of G(.), DG is a symmetric matrix from (4.6), DG = Id -K∇ 2 ψ.

(4.8)

The symmetry of DB can be checked directly and the formula will be used later,

∂B i ∂r i = j b (r i -r j ), ∀i ∂B i ∂r j = -b (r i -r j ), ∀j = i.
The function b is even since x → b(x) -1/2 is an odd function.

Notice that DB 1 I = 0 from the previous formula or from the invariance of the hyperplane 1 I ⊥ under B(.) and also G(.). On 1 I ⊥ , DB correspond to a positive quadratic form (4.5). Now, the eigenvalues of DB and then DG has to be estimated. Let λ be an eigenvalue of DB with the associated eigenvector v ∈ 1 I ⊥ , v = 0. Let us assume v i = max j v j > 0, else change v by -v. Notice that there exists k = i such that v i > v k since v / ∈ R 1 I (not all components can be equal). Using (v i -v k ) > 0 and inf b > 0 yield, The associated eigenvalue of D G is 1 -K λ ∈]1 -2 K L(N -1), 1[. Therefore G(.) is contractant on 1 I ⊥ if 1 -2 K L(N -1) > -1 which concludes the proof.

λv i = j =i b (r i -r j )(v i -v j ) ≥ b (r i -r j )(v i -v k ) > 0,
We can now prove the convergence in law of the ratings (R n i ) when n goes towards +∞ under the contractive assumption (2.8), that is the Theorem 2.1. is explained that this case occurs when the difference of ratings are too large and that this case is marginal for two players due to confinement of the ratings near an attractive zone.

Indeed this drawback is already a drawback in the chess world. Players know that playing against lower rated player is dangerous, because they have to win. The loss is very costly. And professionnal chess players have asked for a smaller K-factor (K = 10) to risk less precious Elo points in such an encounter. This leads to another intersting problem, how take into to account different species of players with a different K-factor. In particular the conservation of total sum of the Elo ratings is lost. This is already a problem for the Glicko an extension of the Elo by Glickman [START_REF] Glickman | Paired comparison models with time-varying parameters[END_REF][START_REF] Glickman | Rating Competitors in Online Games[END_REF][START_REF] Glickman | Rating the chess rating system[END_REF][START_REF] Glickman | Dynamic paired comparison models with stochastic variances[END_REF]. Problems like this show that there are a lot of unanswered questions about Elo's system. On the other hand, the linear case and the nonlinear contractive one is a step towards better understanding the Elo's system.

Figure 1 :

 1 Figure 1: 4 players, number of tournaments on the horizontal axis, ratings on the vertical axis, true strength in red.

Theorem 3 . 2 (

 32 Limit bounded law, expectation, covariance)

Figure 2 :

 2 Figure 2: 4 players including two players with close strengths.

Proposition 3 . 1 (

 31 Invariances and the constant vector 1 I)

  .11) since 1 I S 1 I = 1 I S 1 I, 1 I B 1 I = 1 I B 1 I are scalar quantities. Thus, multiplying (3.8) on the left by 1 I yields,

Figure 3 :

 3 Figure 3: 4 players with close strengths. Notice that the strongest player loses points at the start because their initial ranking is too high.

Figure 4 :

 4 Figure 4: 10 players.

  ) < 1 < b(348) for the linearization of the logistic (1.6) at the origin. By symmetry, b becomes negative for too negative ∆r, b(-348) < 0 < b(-347).

. 25 )

 25 Proposition 3.4 (2 players) Assume the stability condition 2 K L < 1. If D 0 ∈ I A then D n belongs to I S for all n ∈ N.

. 3 ). 4 ) 4 . 6 (

 3446 from(3.9). However B(.) is a bijection on 1 I ⊥ under the assumption,inf x∈R b (x) > 0. (4Proposition Monotonicity of the vectorial map B(.) on 1I ⊥ ) If (4.4) is satisfied then, the map B(.) is a diffeomorphism from 1I ⊥ to 1I ⊥ , B( 1I ⊥ ) = 1I ⊥ . and the map B(.) is monotonic and coercive on 1I ⊥ ,

= x 0 b

 0 (y) dy.Proof : First, B(.) is constant on R 1 I (4.3) since b(0) = 1/2. It can be seen as the general symmetry relation (3.9) which yields B(t 1 I) = (N/2) 1 I for all t ∈ R as in(3.11) for the linear case.

  1 I ⊥ , which gives the coercive estimate (4.5) Third, r 1 I ⊥ is an eulcidean norm on 1 I ⊥ associated with the scalar product,

  r k -r j ) -β (r j -r k )) r k -r j ) + (b(r k -r j ) -1) é -N = 2 B k (r).

Proposition 4 . 7 (

 47 Contractive Elo on 1I ⊥ )If assumption (4.4) is fulfilled andK (N -1) sup b < 1, (4.7)then, G(.) is a contractive map on 1I ⊥ .

  thus λ > 0, which is also a consequence of (4.5). Now, more precise estimates are obtained on λ with L = sup b (4.10),DB ii = (e i , DB e i ) ≤ λ ≤ max i j |∂ j DB ij | , j =i b (r i -r j ) ≤ λ ≤ 2 max i j =i b (r i -r j ) (N -1) inf b ≤ λ ≤ 2L (N -1). (4.9)

Proof : To use the contractivity of G(.) on the hyperplane 1 I, thanks the invariance by translation, Proposition 3.1 valid in the nonlinear case, R n i is replaced by

without affecting the stochastic process. Now R0 ⊥ 1 I. Moreover, Rn ⊥ 1 I for all n due to the conservation of the total sum of ratings, Proposition 3.1. The conditions (2.8) allow to use Propositions 4.7 and Theorem 4.4 and to conclude the proof.

On the contractivity

The contractivity is an important tool to study of the convergence of the linearized model or general nonlinear models. But this assumption is not fulffilled for the Elo's system used in practice. First, it is explained why the usual Elo rating system is not contractive. Second some consequences are discusssed. In particular many comments valid for the linear case in Section (3.3) can be extended in the nonlinear case.

It first turns to present the non contractivity of the usual Elo model. The Elo model with the logistic function b(.) (1.6) is not contractive. Let us explain this point for two players i and j as in the introduction. The two equations (1.1) -one for i and one for j-to update the Elo can be rewritten as a single equation for the difference of the rating, using the symmetries of the scores and the bonus function b(.), [START_REF] Krifa | On the convergence of the Elo rating system for a Bernoulli model and round-robin tournaments[END_REF],

The question is the contractance or not of the function g(.). Therefore, the Lipschitz constant of g is max(|1 -2 K L|, 1) ≥ 1. The function g is never contractive. At least, the condition K L ≤ 1 is natural to avoid instability. However, on any compact set [-A, A] and assuming

So, if the ratings belongs in the same bounded set then g is contractive. The chess players genrally believe that the Elo is bounded. In practice, it is. But theorically, it is not [START_REF] Krifa | On the convergence of the Elo rating system for a Bernoulli model and round-robin tournaments[END_REF]. It can growth like ln n but with very small propabilities [START_REF] Krifa | On the convergence of the Elo rating system for a Bernoulli model and round-robin tournaments[END_REF]. Nevertheless, with a contractivity in average [START_REF] Diaconis | Iterated random functions[END_REF], it is possible to prove the convergence in law for two players [START_REF] Avdeev | Stationary distribution of the player rating in the Elo model with one adversary[END_REF][START_REF] Avdeev | Local contractibility of a process of player rating variation in the Elo model with one adversary[END_REF]. So understanding the contractivity conditions can be useful to deal with the non contractive case.

There is a worse consequence on the condition (4.4), the function is unbounded, lim ±∞ b(x) = ±∞. It is clear at +∞ and the other limit comes from the skewsymmetry of b, (1.5). Thus, the interpretation of b(ρ i -ρ j ) as the expected score is loss when b(ρ i -ρ j ) / ∈ [0, 1]. The main draw backs of this unboundeness is the possible loss of points for the winner. It is possible that a very strong player will win against a very weak one and lose Elo points. This point is discussed in section 3.3 for the linear Elo. It