Evaluation of Ranking & Matchmaking in Competition

Evaluation of Ranking & Matchmaking in Competition A Simulation and Humanist Approach Master Thesis David Bucher University of Fribourg January 2025 Abstract In recent years, there has been an increasing amount of complaints in the video game community regarding ranking and competition. Ranking systems can be evaluated with empirical study on game dataset. For sport and competition, there is a simple model suitable for simulation based research. Yet this approach is relatively absent from literature. The purpose of the thesis is double. First, I introduce the matchmaking overfitting hypothesis. I perform comparative studies between state-of-the-art rating systems, highlighting differences in behavior in challenging settings. In a second step, I present the experiment to a panel of experts in competition to measure how receptive they are to simulation. Keywords Competition, Ranking, Bradley-Terry model, Simulation, steady state, Elo, Glicko, TrueSkill, OpenSkill Prof. Edy Portmann, Soft and Cognitive Computing, Human-IST Institute, University of Fribourg, Responsible Dr. Maurizio Rigamonti, DIVA, Department of Informatics, University of Fribourg, Supervisor 1 2 Ce que l’on conçoit bien s’énonce clairement, et les mots pour le dire arrivent aisément. 1 Nicolas Boileau-Despréaux, L’art poétique (1674) 1 Whatever we conceive well, we express clearly, and words then flow with ease. Translation taken from https://skwi.fr/ 2015/07/08/what-you-understand-well-you-enunciate-clearly/ Contents 1 Introduction 5 1.1 Motivation.......................................... 6 1.2 The Problematic: Matchmaking Overfitting . . . . . . . . . . . . . . . . . . . . . . . . 7 1.3 Definitions.......................................... 9 2 Methodology 10 2.1 SimulationBasedResearch................................. 10 2.1.1 Modeling...................................... 11 2.1.2 Simulation ..................................... 11 2.1.3 Research ...................................... 12 2.2 Recommendation System Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.3 Simulation for Competition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.3.1 MMbench...................................... 14 2.4 State-of-the-art ....................................... 14 3 RSTT Package 16 3.1 Presentation......................................... 16 3.2 Implementation....................................... 16 3.2.1 LanguageChoice.................................. 16 3.2.2 Design ....................................... 17 3.3 Validation.......................................... 18 3.3.1 Reproducibility of Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.4 Usage ............................................ 20 3.4.1 Example ...................................... 20 3.4.2 Access ....................................... 21 3.4.3 Quality ....................................... 21 3.4.4 CodeReview.................................... 22 4 Experience 23 4.0.1 StartingPoint.................................... 23 4.0.2 The Direction, The Final Experimentation . . . . . . . . . . . . . . . . . . . . . 24 4.1 Baseline........................................... 24 4.2 Elo prediction and the single Elimination Bracket . . . . . . . . . . . . . . . . . . . . . 25 4.2.1 Formalapproach .................................. 25 4.2.2 Motivation&goals................................. 27 4.2.3 Protocol....................................... 28 4.2.4 Results ....................................... 28 4.3 TheSnakeformat...................................... 29 4.3.1 Motivation&goals................................. 29 4.3.2 Definition...................................... 29 3 CONTENTS 4 4.3.3 Properties...................................... 30 4.3.4 Convergenceproof................................. 31 4.3.5 ModelValidation.................................. 31 4.4 RandomSnakeExperiment................................. 34 4.4.1 Motivation&goals................................. 34 4.4.2 Protocol....................................... 34 4.4.3 Results ....................................... 34 4.5 Convergence in the Snake format . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.5.1 Motivation&goals................................. 36 4.5.2 Protocol....................................... 36 4.5.3 Results ....................................... 37 5 Survey 39 5.1 Goals&Design....................................... 39 5.2 ContentPresented...................................... 40 5.2.1 Questions...................................... 40 5.2.2 Protocol....................................... 41 5.3 Results............................................ 41 5.3.1 InitialForm..................................... 42 5.3.2 FinalForm ..................................... 43 5.3.3 EvolutionofOpinion................................ 46 5.4 Struggles .......................................... 46 5.5 Discussion.......................................... 48 6 Conclusion 50 7 Appendix 51 A Validation 52 A.1 RSTT version of the 2 player Elo convergence . . . . . . . . . . . . . . . . . . . . . . . 52 B Performance 53 B.1 RSSCProtocol ....................................... 53 B.2 ExecutionProfile ...................................... 54 C Experiences 55 C.1 Probability table for the Single Elimination Bracket . . . . . . . . . . . . . . . . . . . . 55 C.2 Elo and the Single Elimination Bracket . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 1 Introduction In this thesis, I propose to combine Simulation Based Research and Human Centered Approach. In simulation, one deals with a model. It is pure computation with little regard, not only for humans, but also for the "Real World". In Human Centered Design, people are at the center of the methodology. It focuses on a user in an interactive system and his needs to increase customer satisfaction. Often, it includes community participatory research. These methods seem opposed to each other. I argue that their differences are exactly what makes them valuable together. The motivation is to understand why simulation is a neglected approach in the fields despite well known models. This marriage turned out to be a powerful and meaningful one. The work presented in this thesis takes its roots in complaints formulated against ranking and matchmaking algorithms by the gaming community on social networks. To address certain issues, I propose the matchmaking overfitting hypothesis. Simply put, can a ranking learn a bias introduced by a matchmaking algorithm? The key point is the interdependency between both notions. A Ranking infers the level of players based on game data. A matchmaking system generates and evaluates potential games to be played using a ranking. There is a loop: a ranking is used to generates games, which in turn are used to train a ranking. Overfitting in that context means that a ranking makes great predictions on the games it suggest itself as quality games. However, it could perform poorly on other potential matchups. This would not appear in a dataset. It is a snake eating its own tail. This hypothesis is suited for simulation based research. First of all, in the context of competition in sports, there are well-known models for simulation. The domain uses and validates simulation. But more importantly, to study the bias of a dataset, one needs to control the entire data generation process. Simulation does this, a model controls everything happening in a run. When one knows in advance the bias in the data, it is relatively simple to measure if a ranking learned the bias. Alternatively, we can produce many different datasets by changing hyper-parameters and conduct comparative studies to evaluate ranking design and their resilience to the phenomenon. After conducting experiments, I present a few selected one to a panel of expert in competition. The goal is to evaluate how receptive they are to simulation research. Do they understand the model? Does it fit their intuition and experience? What do they think of the design and the metrics used? To some extent, this is also related to the potential that simulation can have regarding the transmission of knowledge - its usage as an educational tool. Can scientists exchange and share their work with a targeted community 5 CHAPTER 1. INTRODUCTION 6 using simulated examples? This question addresses the thesis motivation - community complaints. In Chapter 2, I provide an overview of the methodologies. What is simulation based research? How is it performed for competition? I place it within the context of recommendation system and from the perspective of Human Centered research. In Chapter 3, I present the tools used, the technical details of the research, and its implementation. You will find there the potential for future research and some limitation. Someone looking to challenge and critique my work should probably start here. In Chapter 4, you will find the details about experimentation. I focus mostly on the ideas and goals of the experimental design. Results should be reproducible with any tools, and should not be code dependent. A clear, yet simple, protocol is provided in that regard. It contains all the necessary modeling considerations and the run specifications for anyone looking to replicate the experiments. The chapter also covers my own analysis, interpretation, and conclusions of each experiments in dedicated subsections. In Chapter 5, I discuss the interaction with experts in the field, from the survey design to its conclusion. This might come as a surprise: to split the two methodologies into separate chapters in a thesis where the topic is about combining them, seems incoherent. There are multiple reasons for it. First, it represents the work. The studies were conducted and designed separately, the second following the first. The reader could be interested in, or referring to one independently. But more importantly, the benefit of including design research - involving participants with simulation research - is independent of the underlying actual simulation research questions and experiments. It does not matter what I was interested in or the content of my research. What matters is the nature of the Human - Simulation interaction, and how does the two benefit from each other. But before all of this, I strongly recommend to read section 1.1, which present the context of my research, and section 1.3 where the terminology about ranking and competition is introduced. 1.1 Motivation I love games and sports, and I do watch a lot of events. I love competition and did measure myself against other contestants in several titles. I even earned a bit of money from it as player, coach, analyst and commentator. In competition, rankings are everywhere. They are a great tool to compare athletes against each other, which is exactly the nature of competition. I am and have been ranked in many different games. In 2023, I have seen many complaints over the internet about ranking and seeding in video game competitions. One of the frequent conversations surrounding League of Legend 1 matchmaking is the Loser Queue Theory. Some players believe that Riot matches losing player together with a presumed intention to make them lose even more. Doing this manipulates the ranking, leading to hard-stuck 2 and boosted 3 players. I do not believe in this theory nor even understand what it is supposed to explain. But I can accept that people have a horrible experience in a game due to a bad competitive ecosystem. It is hard to formulate exactly a problem in a technical field. To me, the Loser Queue Theory does not describe a malicious algorithm, it expresses an unpleasant human experience. In a Reddit post 4 , user renecotyfanboy, a French PhD student in astrophysics (as he presents himself), tries to disprove the theory. Two days later, a Twitter thread 5 from @AnalyseStatLOL performed additional study and provide nuances to the results. The works are reasonably well documented, especially for social media posts. My issues are regarding the dataset and a debatable hypothesis. They use games from the master tier level, the 1% highest ranked players 6 . It’s not a bad dataset, but why not use a more representative one? Whatever conclusion you draw from it is limited to a minority of gamers. Also, they 1A popular esport title of the MOBA genre 2A player whom ranking is significantly underrated 3A player who’s ranking is significantly overrated 4www.reddit.com/r/leagueoflegends/comments/15k2nw4/existence_of_loser_queue_a_ statistical_analysis/ 5https://x.com/AnalyseStatLOL/status/1688738885944119296 6rank distribution can be seen at https://www.leagueofgraphs.com/rankings/rank-distribution CHAPTER 1. INTRODUCTION 7 use the Elo algorithm to process the data and rank the players. It is an arbitrary choice. At the time, there was no documentation of which method Riot 7 8 used to rank their customers. But today we know it is TrueSkill2 910 . Interesting work, but not conclusive in my eyes. It does highlight that the community is not happy about the state of the game and tries itself to find answers to questions and problematics. On May 25th 2023, NER0cs posted on HLTV a blog 11 criticizing the usage of seeding in the biggest Counter-strike event of the year, the Major. He points out that the rank correlation between the seeding and the final standing was below 0 in several top events. He recommends changing the seeding procedure. I was chocked and still am chocked. My interpretation of a negative rank correlation between seeding and final standing is the following one: The ranking used for initial seeds was not of good quality. It fails to make accurate predictions. The athletes involved in the tournament were able to perform independently of their initial seeds. It was an unbiased competition. My conclusion is that the ranking performs poorly, not the seeds. My recommendation would be to improve the ranking design. I want to add a serious concern I have. Personally, I consider Changing the seeding procedure to get desired results match fixing! The document ’CETS - 215’ by the Council of Europe12 stipulates: "[...] sport, based on fair and equal competition, is unpredictable in nature and requires unethical practices and behaviour in sport to be forcefully and effectively countered [...]" These posts not only showed practical issues, but raised a more profound question. How does one perform study on ranking? What should be measured? Which data matters, and which methodology to use? I expected to find answers to those questions in scientific papers. But no. Turns out, different systems are evaluated with different metrics and different methodologies. Some use datasets and evaluate game score prediction. Other uses mathematical definition and theorem proof. Others perform simulations and verify expected behavior. Diversity in methods is great. It is an asset to tackle problems from multiple perspectives and increase the meaning of the object under study. But I see a segregation: Elo with mathematical and simulation supports versus TrueSkill and OpenSkill with empirical support. In the following section, I explain more precisely a hypothesis of mine. It is an idea that emerged exploring the state-of-the-art. Convergence - a word frequently used to describe ranking’s behavior - seems to be abusively interpreted in certain contexts. 1.2 The Problematic: Matchmaking Overfitting In data driven research, fine-tuning a model to avoid overor under-fitting is crucial. This is relatively absent from literature about rankings in competition. As you may have realized, I look for over, not underfitting. Why so? Overfitting risk increases with an increasing number of parameters in a model. People complain more about TrueSkill than Elo, the first uses more value to rate players. The uniqueness of a stationary distribution is a property that the Elo system can exhibit depending on the matchmaking. Simply put, the game generation procedure can impact the resulting ranking, its convergence. For some reason, matchmaking matters when ranking players. It is possible to rank players with fewer parameters than the amount there is in the criticized systems. Research tends to not track rigorously overfitting. 7Many assumes it is an Elo rating system in LoL, but official sources explicitly state that the system used is kept secret 8https://support-leagueoflegends.Riotgames.com/hc/en-us/articles/ 4405781372051-MMR-Rank-and-LP 9https://www.sportskeeda.com/esports/league-legends-season-14-new-mmr-trueskill-2-systems-explained# 10My guess would be that at the time of the reddit post, they used TrueSkill 11https://www.hltv.org/news/36097/valves-swiss-system-under-the-microscope 12https://rm.coe.int/16801cdd7e CHAPTER 1. INTRODUCTION 8 Thus, the matchmaking overfitting hypothesis. CHAPTER 2. METHODOLOGY 15 studying the uniqueness of a stationary distribution in the Elo on a skilled based matchmaking case. Simulation methods to study ranking in sports are summarized by D. Aldous in [ 1 ] and illustrated for simple Elo convergence by A. Krifa in [16]. In [ 6 ] and [ 7 ] A. Dehpanah explores validation metrics for rating systems in different game modes. In simulation based research, we can compare a ranking learning with a ground truth ranking using the Kendall rank correlation [15]. 3 RSTT Package 3.1 Presentation RSTT stands for Ranking Simulation Testing Tool, and is exactly that: A tool to test ranking through simulation. It was originally developed to ease the coding of simple experiments of my own. But as experiments became bigger and more complex, so did the package. The goal of RSTT is to enable research about competition integrity. A special focus was put on the study of steady state of ranking regarding different formats of competition and player behavior. It offers close to complete control over all parameters behind the generation of a synthetic game dataset. With the package, a lot of the workload in simulation based research is shifted from the coding of a simulation to the analysis of the data. This was achieved by identifying needed components of a competition simulation and handling all their interactions at the highest level of abstraction. In turn, coding a simulation is reduced to specifying the parameters (the component) and ordering events (the protocol); the run itself is performed by the package. This thesis is not about the development of the package 1 ; however, the research conducted relies heavily on it. This chapter provides all the information necessary to understand the work and build a critical opinion on it. The following sections describe implementation choices, concepts in place, the validation process of the package, and how it can be used. 3.2 Implementation 3.2.1 Language Choice The package is implemented in Python. The language choice was motivated by the target audience: people who analyze data - data scientists, mathematicians, etc. This means that one can generate a synthetic dataset and analyze it in one single place, like a Jupyter notebook, for example. On the downside of this choice is the performance resulting from an interpreted language (see section 3.4.4). 1 The implementation was also not part of the thesis, neither in scope nor time. During the master thesis, limited modifications were done to the package. 16 CHAPTER 3. RSTT PACKAGE 17 Another reason is the object of interest: Rankings. There are publicly available Python implementations of TrueSkill2and OpenSkill3. 3.2.2 Design The package, and any simulation based on it, relies on the following notion (also defined in section 1.3). Figure 3.1 shows UML class diagrams. • Ranking is a Composition over Inheritance class that stores "standing", "datamodel", "inferer" and an "observer". The class responsibility is to maintain the correct ordering of players in the standing and offer a convenient user interface. • Datamodel A variant of default dictionary where keys are Player and values are Rating. It accepts functions of the key as default values. A datamodel also provides an ordinal() method to convert a rating into a float value. • Standing A list-dictionary hybrid container. It stores a triplet (rank, item, value). Ranks are integer from 0 to n, items are Player and values are float used to sort the standing. In a ranking class, the values in the standing match the datamodel.ordinal() returned values. • Backend A statistical inference tool to compute ratings from game data. It is defined as an interface that provides a rate() function. • Handler A game preand post-processing component. It is defined as an interface that provides an handle_observations() function. •Scheduler An automated Game generation protocol. •Game models an encounter of Player with an outcome - a Score. • Player are the common elements Ranking/Scheduler/Game share. Player plays Game and gets rated by Ranking. A Player has a level() methods that returns values to compute game outcomes. • Solver is the core of a simulation. It is the component that assign a Score to a Game. Usually by looking at the Player models, like their respective levels. Any simulation in RSTT is a composition of at least ’Game’, ’Solver’ and ’Player’. The research I performed used also ’Competition’ class to generate games and ’Ranking’ to rate Player. The package is meant to enable research and not to constrain the simulation design by its features’ limitations. This means users have a relative flexibility to play with their own component that fits in the tool. This was achieved by implementing the notions at a high level of abstraction. In most cases it is sufficient to inherit from an existing class and override a few methods to enrich the behavior of the simulation. Another design feature is type restriction, which Python does not support by default. This is important in the case of developers who integrate their own component into the framework. It ensures that functionalities are used on the correct data structure and that the components interact the way they were designed to. The entire package uses typing 4 for function annotations, and typeguard 5 for runtime type-checking. The package defines ’Protocol’ 6 and uses Duck-Typing to give more freedom than inheritance would. 2https://trueskill.org 3https://openskill.me/en/stable/installation.html 4https://docs.python.org/3/library/typing.html 5https://peps.python.org/pep-0647/ 6interface in other object-oriented programming languages CHAPTER 3. RSTT PACKAGE 18 Figure 3.1: Class diagram of the RSTT package. Core concepts of the simulation are Player, Game and solver. They interact with each other by the means of the Game.play(), Solver.solve() and Player.level() methods. Competition and Ranking reflect the systems under study. 3.3 Validation I am confident in my results and their scientific relevance. The base model is simple to implement. I have performed unit testing 7 . Before any experimentation, I run model validation. When I run multiple times the same experiment, I get consistent results. I can use my tool to verify claims made in publication. I can reproduce results from others with a few line of code using the RSTT framework. 3.3.1 Reproducibility of Results I illustrate here that with the RSTT package it is possible to run experiments and reproduce published simulations and results. A. Krifa shows in [ 16 ] a simple Elo convergence simulation. The example is relevant to the thesis because: (1) It studies long-term convergence. (2) It manipulates initial seeding. Figure 3.2 shows the original diagram, the caption is a copy-paste of the setting specification in the paper. Figure 3.3 shows the RSTT version. 7https://docs.python.org/3/library/unittest.html CHAPTER 3. RSTT PACKAGE 19 Figure 3.2: This graph shows the Elo evolution over 1000 games of two players A and B, A has a p=b(ρ1ρ2) chance of winning against B. ρ is meant to be the ’true’ (theoretical) force of a player; b(ρ1ρ2) is what we will name the ’natural’ probability of A winning against B. Here we have ρ1 = 1500, ρ2 = 700 and the players start with 1000 and 1200 Elo respectively. Source: [16], page 10. 0 200 400 600 800 1000 i-th game 0 500 1000 1500 2000 elo RSTT Elo Simulation Figure 3.3: RSTT simulation using the same setting as in Figure 3.2. We observe similar results with different code implementations. The run is stochastic, and no seed was specified to the random generator in the RSTT version. The simulation tool did not need fine-tuning of hyperparameters. The code is available in appendix A.1. CHAPTER 3. RSTT PACKAGE 20 3.4 Usage 3.4.1 Example For simple simulation, one usually needs a population of players, a scheduler to generate games, and a solver to decide the outcome of encounters. To make it interesting, a ranking can be updated and compared to the ground truth implied by the model. Figure 3.4 illustrates a basic usage of the rstt package, with no parameters’ specification. The population is generated using a Gaussian distribution. It is possible to fine-tune the mean and variance of the player’s level. It is possible to fine-tune the hyperparameters of the Elo ranking. Figure 3.4: We can recognize behind the variable the related notion of Player (population), Scheduler (tournament), Solver (LogSolver()) and rankings (elo, truth). We do not see the notion of Game. The game mode is one-versus-one. The mode is the consequences of the scheduler choice (Single Elimination Bracket) and the registration of Player (rather than team of Player). Additional material to the thesis include tutorial notebooks of the package. They focus on the user interface of the classes and the different model implementation. It can be useful to understand experimental code. I implemented myself an Elo 8 and Glicko 9 Backend. TrueSkill and OpenSkill have official Python distribution, Figure 3.5 shows how to integrate OpenSkill in the RSTT framework by inheritance from the Ranking class. It is not necessary to write predict and quality methods. That depends on what you want to measure and if you prefer to interact with the ranking rather than the ranking.backend (openskill.models instance). Testing Python implemented ranking system is straight forward. If there is no Python distribution, one option is to write an observer (in the code: handler) that dumps formatted game data in a file (for example .csv or .json) and reads updated ratings from another one. Additionally, a dummy backend needs to launch an external process (running the actual system), and its rate() methods should signal the process to read the game date file and write back the updated ratings. 8Implementation follows the wikipedia description. https://en.wikipedia.org/wiki/Elo_rating_system 9 The implementation rigorously follows Dr. Mark E. Glickmann specification. It was also tested with the author’s computation example CHAPTER 3. RSTT PACKAGE 21 Figure 3.5: RSTT integration example with the OpenSkill library; openskill.models provide multiple technique to rate players based on game outcome. The experiment in chapter 4 uses this code with the parameter: model=openskill.models.PlackettLuce() 3.4.2 Access The package is available upon request from the author 10 . Note that TrueSkill 11 usage requires a license. The package has auto generated documentation using numPy 12 style docstring and sphinx 13 . The code comments issues, feature enhancement, performances bottlenecks and some unresolved bugs. The code comments includes literature and web references to implemented models. I did perform unit testing to ensure code specifications. I did work on performances benchmark and optimization. 3.4.3 Quality To ensure minimal standards of code quality, I followed software development principles such as Liskov Substitution,Dependency Inversion or design patterns such as Decorator and Delegation. Adhering to these good practices enabled me to write robust code that allowed me to proceed smoothly with my simulations. In fact, most of the error was due to inappropriate usage of the package rather than a bug within RSTT itself. As an example, the "Must be a new event" error in the package ensures dataset integrity. Player instances track automatically games they play and events they participated in. Events must have a name to identify them, and, for example, it is not possible to participate twice in the World Cup 1998. It is impossible to execute accidentally14 the following code portion twice. # parameter year =1998 # schedule an event event =SingleEliminationBracket(name=f'World Cup - {year}', seeding=ranking, solver=solver) # enroll competitors 10send an email to: davidbucherde[email protected] 11https://github.com/sublee/trueskill/blob/master/LICENSE 12https://numpydoc.readthedocs.io/en/latest/format.html 13https://www.sphinx-doc.org/en/master/index.html 14by copy-paste or running a second time the same cell in a notebook CHAPTER 3. RSTT PACKAGE 22 event.registration(ranking.players()) # play the tournament event.run() # update the ranking based on game results ranking.update(games=event.games()) An error is raised the second time cup.run() is executed, before the ranking.update() is called 15 . The variable year needs to be updated before to avoid errors (or directly the ’name’ parameter at event instantiation). It is possible to update twice the ranking based on the same event games. You can call ranking.update(...) as many times as you want. But it needs to be explicitly written so without rerunning the event. The package does not allow an event to have multiple outcomes simultaneously. I have lost hours of computations and large datasets due to this feature. Rightfully so, because what I was doing made no sense. In a stochastic environment, if we play multiple times the same event 16 we can observe different results. The diversity of results can be interesting and is possible to study with the package. However, it needs to be explicit in the code by using the Player.reset()17 method in between event reruns. 3.4.4 Code Review I used pyinstrument 18 to identify bottlenecks in edge-case scenarios. I compared different ranking designs (as an abstract component of RSTT. I am not talking about Elo versus Glicko here) and sorting protocol. All of this is irrelevant to the thesis. The package performs probably faster than what we can expect from an interpreted simulation tool, but significantly slower than what we hope. The package is bigger than the code needed for the experimentation. To review the thesis, it is not necessarily needed to review the entire package. Most of the features are not used. As a code profiler, pyinstrument tracks the call of each code section. This helps to identify which function is actually executed. To have a deeper understanding of the simulation presented in chapter 4, you can take a look into the code analysis I performed (c.f. appendix B.2). It gives a decent glimpse of what happens under the hood. It follows the package calls in the rssc protocol, a code segment present in all my simulations. 15This can otherwise lead to ill-tuned ranking 16With identical initial state, i.e. same seeding, same player strength etc. 17method that clears a player’s history. 18https://pyinstrument.readthedocs.io/en/latest/ 4 Experience In this chapter, I present some of the most interesting experiences I have designed in my journey. 4.0.1 describes the first step I took in simulation. 4.0.2 presents a practical experiment to achieve, a sort of direction to keep the work coherent. In 4.3 I introduce a simple matchmaking model I propose. I claim it is an interesting and relevant object of research. In 4.2, 4.4 and 4.5 I detail three experiments of particular interest. I have presented all three to a panel of experts in competition to collect opinions and measure if it is of interest also from their perspective. 4.0.1 Starting Point The very first system I studied was ranking in a two player base, one-versus-one game environment. It is the simplest case I could imagine. In this system a ranking is a function that maps an arbitrary string of results (for example: wwlwwlllw... where ’w’ stands for ’win’ and ’l’ stands for ’lose’) to a pair of ratings (rating_1, rating_2). The string is the input, and the ratings’ pair, the output of the algorithm. This setting is borderline simulation. There is no player model, no distribution of skills, no matchmaking, no solver. Really just a function with input and output. There are however two parameters, the length of the input (how many characters) and the ratio between the ’w’ and the ’l’1. The metrics that I found the most interesting in this setting is to measure the distribution of a distance(rating_1, rating_2) when the length of the string and the ratio w/l are kept constant. The question behind this design is: what happens to a ranking system when I change the order of the game presented? I went as far as developing an interactive user interface solely for this experimentation. In regard to my hypothesis Matchmaking overfitting, there is no matchmaking. There is not a component that takes a player base and matches them together with the intention of playing a game. But there is a notion of history - the ordering of games, which is something that matchmaking does impact. How much are the ratings impacted by the last few games versus the wl-strings in its entire form? 1Unrelated but interesting to point out that during my Bachelor thesis I worked on similar data - I called them ’wl-string’ 23 CHAPTER 4. EXPERIENCE 24 4.0.2 The Direction, The Final Experimentation Ultimately, behind the matchmaking overfitting hypothesis, stand practical problems I try to identify and solve. In a tweet, RiotPhroxzon addresses the losers queue issues. He explicitly states that they (at Riot) do not match on purpose underperforming players together to make them lose more games (in the video game League of Legend). His tweet states: Sure there are games where your teammates play poorly, that’s just the nature of a 5v5 game. In the long run, you’re the only common factor and the only one responsible for your rating is you. If you took an "unwinnable" game and replayed it with any Challenger in your spot, it would probably result in a win.2 Although it is a reasonable statement in itself, the behavior of a ranking is something to be assessed. Are you indeed the only one responsible for your rating? If you took an "unwinnable" game and replayed it with any Challenger 3 in your spot is a simulation protocol. The fact those games would result in wins is not debatable in itself, but the question is, if those games were wins, would it result in rating improvement? However, the simulation model is quite complex. 5 versus 5 is harder to simulate than one-versus-one. The author introduces the notion of a player with time-varying strength, and more precisely, learning and improving from game experience and losses. All of this is possible. But one needs a clear understanding of each component individually, before combining them. At the time of writing the thesis, I consider myself halfway from the start to this goal. I have explored a lot of the one-versus-one case regarding many different ranking design and matchmaking approaches. I have also tested players and metrics regarding time-varying levels. Furthermore, I have started the validation process of solver involving multiple players in two separate teams within a game. 4.1 Baseline The Bradley-Terry model implies a Consensus Ranking based on the strength value of the players. I have mentioned that Elo has a unique stationary distribution. This means that the ranking state over a long time is independent of the initial condition. It should ’always’ reach a state similar to the consensus ranking. In figure 4.1 we can see the convergence of the Elo system under three different conditions. It is an RSTT simulation using the following parameters: • Player 64 players of constant skill draw from a Gaussian distribution X∼ N(µ= 1500, σ2= 500) . •game mode one-versus-one. • Solver The LogSolver() with a default base = 10 and logistic constant lc = 400 . It computes win probability4 IP(A beats B) = 1 base −(A.level() −B.level()) lc •Ranking The Elo rating system with K= 20,lc = 400 and default rating 1500. •Scheduler It is a comparative run where the scheduler is the varying parameter. •interaction RSSC loop described below. depth=160. 2https://x.com/RiotPhroxzon/status/1756511358571643286 3a rank corresponding to a few hundred best players among millions in a given region 4https://wismuth.com/elo/calculator.html CHAPTER 4. EXPERIENCE 31 4.3.4 Convergence proof The proof is harder to read and understand than it actually is. In fact, it is a pretty simple observation. Some of the issues come from my formalism choices, but some come from the terminology in the field of competition. Indeed, when speaking, one would refer to a better or stronger player, and low or high seeds. The best player, is the number 1, and the highest seeds is the 1. As a value (indices in the proof), 1 is small, the smallest of all. This leads to confusing usage of inequalities. Following the proof may require some mental gymnastics, that would not occur in the oral form. This section is here for the sake of completeness. If equations are not your cup of tea, you can refer to the validation section 4.3.5 where I demonstrate in simulation the convergence properties. Theorem 1. Let us consider a population of n ordered players Player1, ...Playern such that Playeri always wins against Playerj if and only if i < j . We consider the snake format as described in section 4.3.2, and play n edition. Seedk i represent the Player at seed i in the k-th edition. Placek j represent the player that finished at the j-th place in the k-th edition as proposed in 4.3.3 (A). claim: For any arbitrary initial seeding S:= {Seed1 1, ..., Seed1 n} , and the seeding procedure Seedi j= Placei−1 j , we have the final standing F:= {Placen 1, ..., P lacen n} , where Playeri=Placen i∀i=i, ..., n In other words, the players sort themselves out, by skills/strength/levels. Proof. By induction on k. Hypothesis:Playerj=Placek j∀j≤k. Base Case: For k = 1, after the first edition Player1=Place1 1 This is indeed true, Player1 is by definition the best player and wins against anyone else, i.e. independently of his initial seed. Precisely, if Player1 has Seed1 m , then he wins every games against Seed1 m+1, Seed1 m−1, ..., Seed1 1 . He thus finishes first place, i.e. Place1 1in the final standing. Induction Step: Playerk+1 wins against any p∈ {Playeri∥k+ 1 ≤i}={Seedk+1 i}\{Playeri∥i≤k+ 1}= {Seedk+1 i∥k+ 1 ≤i}=⇒P layerk+1 is W innern−k−1. Playerk+1 loses against any p∈ {Playerj∥j≤k+1}={P lacek j∥j≤k+1}={Seedk+1j∥j < k+ 1}=⇒Playerk+1 loses against Seedk+1 k i.e. Playerk+1 =Placek+1 k+1 4.3.5 Model Validation I illustrate the following Snake properties: (B) Skilled Based Scheduler, (E) Deterministic Convergence, and (F) Probabilistic Convergence. I show that the Snake competition is a skilled based Scheduler in which players are naturally14 sorted by strength. The claims (C) and (D) are important to understand the motivation and idea behind the scheduler design. However, I cannot provide a good illustration of it. This would require a meaningful metric. There is not one because, well, the matchmaking overfitting is a hypothesis proposed by this thesis. Expected Score and Win probability are problematic because they are defined for competition, not matchmaking. Also, many ranking, including TrueSkill update ratings continuously, one after the other, there is no notion 14without the help of an external ranking CHAPTER 4. EXPERIENCE 32 of game batches, which is necessary for these two metrics. They require knowledge measuring the bias of a dataset. It is a potential (challenging) future work. This is not an issue for simulation run. The general assumption is that matchmaking does not introduce bias in a game dataset. Whether the Snake format introduces one or not is irrelevant regarding the run itself nor the generated data. It is relevant when interpreting results. Independently of what is observed, no conclusion can be made regarding a learned bias 15 as this would assume the existence of such bias! But observations could provide evidence that there is or not a bias. 0 20 40 60 80 100 120 Number of 'self-seeded' Competition Edition 0.05 0.15 0.25 0.35 0.45 0.55 0.65 0.75 0.85 0.95 1.05 Consensus Ranking Correlation Deterministic Run, claim (E) Stochastic Run, claim (F) Snake Convergence Figure 4.5: The graph shows Kendalltau rank correlation between the final placement of a snake edition and the consensus ranking. The k-th edition (on the x-axis) was seeded with the final placement of the (k-1)-th edition. In orange, a simulation run using the probabilistic LogSolver solver, in blue the deterministic BetterWin solver. Runs are performed with n=64 players of constant levelsBetterWin. We can see that indeed, after n editions (64) the correlation is at 1, the final standing is the consensus ranking. In the probabilistic case, we can observe a similar converged state, noisy due to the unpredictable nature of a balanced game. A 0.95 rank correlation is a value close to what is observed for any other scheduler (c.f. Figure 4.1 ). The figure 4.5 illustrates the convergence of the Snake final standing in the rssc protocol. The behavior observed is not different from the one of a ranking algorithm such as the Elo in a round-robin environment. The claim that the format sorts itself the player based on their strength is correct, in the context of deterministic and stochastic simulation. The players are sorted accordingly to the consensus ranking without external intervention. Figure 4.6 shows the game quality produced in Snake competition as perceived by common competitive ranking algorithms. In the case of TrueSkill and PlackettLuce, the quality was measured using the 15alternatively: not learned bias CHAPTER 4. EXPERIENCE 33 built-in quality() method. For Elo and Glicko, I implemented the quality_1vs1() method from https: //github.com/sublee/glicko/blob/master/glicko.py The question that I address with this graph is not if the Snake Scheduler is a skilled based competition 16 . What we are interested in here is whether ranking algorithms and the format have a similar notion of balanced matching/pairing. We can see that in the case of Elo and Glicko, each game is of quality approximately 1.0, this means that both opponents have about 50% chance each to win the game. We have extremely balanced games. This is mostly true for PlackettLuce and TrueSkill, but we can note a few games of weaker quality (below 0.8). These two rankings rate players using a Gaussian (mu, sigma). The quality() method is not just a function of the difference in both ratings but also in the absolute value of sigma. Take a close look at the below equations. TrueSkill.quality([[(mu = 25, sigma = 8.333)],[(mu = 25, sigma = 8.333)]]) = 0.4619 (4.1) TrueSkill.quality([[(mu = 25, sigma = 0.789)],[(mu = 25, sigma = 0.789)]]) = 0.9825 (4.2) Both equations show the computation of a TrueSkill game quality between two players of identical ratings. In 4.3.5 it is the default rating 17 and in 4.3.5 it uses ratings with the default mu value, but a sigma 18 value close to what is observed at the end of the simulation in figure 4.6. As time passes, TrueSkill consider the scheduler’s games more and more balanced19. 0.0 0.2 0.4 0.6 0.8 1.0 Game Quality 0 1000 2000 3000 4000 5000 6000 7000 8000 Number of Games Elo Glicko TrueSkill PlackettLuce Snake as Skilled Based Matchmaking Figure 4.6: Game quality in the snake format as perceived by different rating systems. The snake format can be seen as a skilled based scheduler because most games are considered balanced by state-of-the-art rating systems. 16This is by design 17when the player is new and the system has not been update on any games 18A simple statistical analysis of the sigma distribution 19 the trueskill rating is said to represent the strength of a player as gaussian distributed value. This observation suggest me that the sigma behave as a confidence value CHAPTER 4. EXPERIENCE 34 4.4 Random Snake Experiment 4.4.1 Motivation & goals The goal is to understand what a ranking learns in a skilled based scheduler. Conceptually, I do not see what information there is in a perfectly balanced game. I say none. I say there is nothing to learn. If you toss a fair coin with friends, you do not draw any conclusions. Maybe after ten losses, you start to believe that the coin is biased, or your opponent is a cheater. But a head or tail says nothing. The idea in the random snake setup is to present, to a ranking, games that are assumed to be fair are indeed fair. Now if you paid attention in the previous section, the snake is a ranking, and it has some degree of correlation between the initial seeding and the final placement. The bias introduced is more subtle here. All possible matchups are perfectly balanced in a coin toss game. The scheduler will generate a fraction of the possible encounters, and the choice relies on the ranking. We study strictly the interaction of ranking and scheduler. The player model does not exist, any possible game is equivalent and any game outcome is equally likely. It is a conceptual setup. It makes no sense to organize a tournament of coin toss. Likewise, it makes no sense to speak about skilled base matchmaking for a game with no skill, and certainly no one would build a ranking from such a dataset. But I invite readers, to think about it. What do you believe a ranking means in this context? What metric would you track? I invite the readers to make a guess. How does your favorite ranking algorithm behave in this setting? 4.4.2 Protocol I perform a comparative study on Elo, Glicko, TrueSkill and Openskill (PlackttLuce). The metric of evaluation is rank correlation with a win rate based ranking 20 . The simulation parameters are the following ones: parameters: • players: 64 players • game type: one-versus-one • Scheduler: Snake • Solver: FlipCoin (player level does not matter, pure random results) For each ranking I perform an RSSC run of depth 500. At different time of the simulation t=0, 5, 10, 50, 100, 200, 500, for each player, I measure the total number of wins, the win rate in career, and the win rate over the last 50 played games. This serves as references to compute three different "ground truth" rankings. During the RSSC loop the state 21 of the ranking is stored after each update, i.e. after each Snake edition. 4.4.3 Results From a far distance, we can see in figure 4.7 that Elo and Glicko behave similarly, chaotic lines crossing each other multiple times. TrueSkill and PlackettLuce have more straight lines and fewer crossing. At any point of the simulation, Elo and Glicko have a high rank correlation with the current win rate of the players. The ranking does not converge, it continuously changes. As time passes, it reaches close to 0 rank correlation with its prior states. In a random game, ’skill’ means luck. 20 Choosing a good metric in this setting is a challenge. The win rate has the benefit that it is practically computable and that it is something that player and spectator of a competition do experience. 21the point of each player as computed with their respective ratings CHAPTER 4. EXPERIENCE 35 0 100 200 300 400 500 0.0 0.2 0.4 0.6 0.8 1.0 Algo 1 total win 0 100 200 300 400 500 0.0 0.2 0.4 0.6 0.8 1.0 win rate 0 100 200 300 400 500 0.2 0.0 0.2 0.4 0.6 0.8 1.0 win rate last 50 games 0 100 200 300 400 500 0.0 0.2 0.4 0.6 0.8 1.0 Algo 2 0 100 200 300 400 500 0.0 0.2 0.4 0.6 0.8 1.0 0 100 200 300 400 500 0.2 0.0 0.2 0.4 0.6 0.8 1.0 0 100 200 300 400 500 0.2 0.0 0.2 0.4 0.6 0.8 Algo 3 0 100 200 300 400 500 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0 100 200 300 400 500 0.0 0.2 0.4 0.6 0.8 0 100 200 300 400 500 0.0 0.2 0.4 0.6 0.8 Algo 4 0 100 200 300 400 500 0.0 0.2 0.4 0.6 0.8 0 100 200 300 400 500 0.0 0.2 0.4 0.6 0.8 time 0 time 5 time 10 time 50 time 100 time 200 time 500 Figure 4.7: Kendall tau rank correlation of state-of-the-art ranking algorithm with observed statistics in the random snake setup. The rows are Algo1=Elo, Algo2=Glicko, Algo3=TrueSkill, Algo4=PlackettLuce. Columns are ranking references computed on wins in the simulation. Colors represent the different moments where the references were computed. For example, the pink line in the top left diagram is the rank correlation of the Elo through time with the final number of wins. We can see that at the beginning of the simulation, the correlation is 0, obviously because little games have been played, and at the end, when all games were played, the correlation is 0.8. This can seem obvious, but compare it with what happens in TrueSkill or OpenSkill. CHAPTER 4. EXPERIENCE 36 Regarding TrueSkill and PlackettLuce, the rankings do not change over time. They converged to a state. Onward, the state barely evolves. In skilled based matchmaking and perfectly balanced game, the ranking state is not altered. In my eyes, both behaviors are reasonable. Exploring every possible ranking state because there is no ranking is acceptable. It means every state is equally ’true/likely’, fair enough. And for the second, like I said, in my mind there is no information in a skilled based matchmaking, so the ranking state should not change. This is perhaps the greatest contribution of my thesis: A conceptual test that shows qualitative (not quantitative) differences between well-known ranking techniques. Usually we can read comments like A converges faster than B,C does better prediction than D etc. Here we can answer the question: What do they do ? But there is one thing that bothers me a lot. The state OpenSkill and TrueSkill adopt is not one where players all have the same level. The state the TrueSkill and PlackettLuce adopt is the initial luck. There is no reason to converge initially; the matchmaking quality has not changed. The players’ levels did not evolve. After players have each participated in 500 games and more, they are still ranked the same way they were after approximately 10. Why bother playing? For sure, players realize that they play a bunch of random games, and that higher-ranked players are not better than them. For sure, they get frustrated about the rank difference. I would personally create a new account. Instead of playing 500 games, I would create 50 accounts and play 10 games on each. I would probably get lucky in some of these accounts and get a high rating. I would then play on that account with my ratings not changing much and just brag about my rank! And I would never speak about accounts where I got unlucky and had a low rating. Maybe I am too far in conclusions. But I think it can be interesting to explore the correlation in video games between the ranking behavior displayed in this experiment, and the number of smurfing accounts. Another interesting thing to do, is the work on metrics to track. For example, we can measure the elasticity of the system with the difference between the highest and the lowest rated player. We can measure the distribution of game quality over the entire domain, not just the one presented to the ranking. 4.5 Convergence in the Snake format 4.5.1 Motivation & goals A natural extension is to see how the ranking behavior in the random snake setup translates into a more realistic scenario. We consider a situation where the notion of ranking is meaningful, where players do have an actual in game level. One parameter is the state of ranking itself. One question is how rankings evolve from a "wrong" state to a more correct one. The worst-case scenario is when the best player has the lowest ratings and the weakest player the highest. That state can be obtained by letting a ranking converge to the consensus ranking and then applying a permutation on the players and reassigning corresponding ratings. This can challenge rankings learning in skilled based matchmaking because, when reversing the ranking, we do not change much the game balance in the snake format. 4.5.2 Protocol I perform a comparative study on Elo, Glicko, TrueSkill and PlackettLuce. I had one more ranking to the pool, the final standing of the snake competition - players sort them-selves out. The metric of evaluation is rank correlation with the consensus ranking. In the middle of the simulation rankings are applied a permutation where player at rank i= 0, ...., n −1 receive the rating of player at rank n−1−i . The ranking is reversed. The experiments is repeated for different population sizes. parameters: CHAPTER 4. EXPERIENCE 37 • players: 8, 16, 32, 64, 128, 256, 512 of constant level • game type: one-versus-one • Scheduler: Snake • Solver: LogSolver I perform an RSSC loop, and the duration of the simulation is depth=150 Snake tournament editions before the permutation and depth=150 afterward. The resulting games are stored in 7populations ·5rankings ·2 = 105datasets the smallest one contains 2100 games and the biggest 230’000. 4.5.3 Results 0 10 20 30 40 50 60 70 80 90100110120130140150 1.05 0.90 0.75 0.60 0.45 0.30 0.15 0.00 0.15 0.30 0.45 0.60 0.75 0.90 1.05 Snake Algo 1 0 10 20 30 40 50 60 70 80 90100110120130140150 1.05 0.90 0.75 0.60 0.45 0.30 0.15 0.00 0.15 0.30 0.45 0.60 0.75 0.90 1.05 Algo 2 0 10 20 30 40 50 60 70 80 90100110120130140150 1.05 0.90 0.75 0.60 0.45 0.30 0.15 0.00 0.15 0.30 0.45 0.60 0.75 0.90 1.05 Algo 3 0 10 20 30 40 50 60 70 80 90100110120130140150 1.05 0.90 0.75 0.60 0.45 0.30 0.15 0.00 0.15 0.30 0.45 0.60 0.75 0.90 1.05 Algo 4 0 10 20 30 40 50 60 70 80 90100110120130140150 1.05 0.90 0.75 0.60 0.45 0.30 0.15 0.00 0.15 0.30 0.45 0.60 0.75 0.90 1.05 PreviousRank 0 10 20 30 40 50 60 70 80 90100110120130140150 1.05 0.90 0.75 0.60 0.45 0.30 0.15 0.00 0.15 0.30 0.45 0.60 0.75 0.90 1.05 SingleEliminationBracket 0 10 20 30 40 50 60 70 80 90100110120130140150 1.05 0.90 0.75 0.60 0.45 0.30 0.15 0.00 0.15 0.30 0.45 0.60 0.75 0.90 1.05 0 10 20 30 40 50 60 70 80 90100110120130140150 1.05 0.90 0.75 0.60 0.45 0.30 0.15 0.00 0.15 0.30 0.45 0.60 0.75 0.90 1.05 0 10 20 30 40 50 60 70 80 90100110120130140150 1.05 0.90 0.75 0.60 0.45 0.30 0.15 0.00 0.15 0.30 0.45 0.60 0.75 0.90 1.05 0 10 20 30 40 50 60 70 80 90100110120130140150 1.05 0.90 0.75 0.60 0.45 0.30 0.15 0.00 0.15 0.30 0.45 0.60 0.75 0.90 1.05 0 10 20 30 40 50 60 70 80 90100110120130140150 1.05 0.90 0.75 0.60 0.45 0.30 0.15 0.00 0.15 0.30 0.45 0.60 0.75 0.90 1.05 DoubleEliminationBracket 0 10 20 30 40 50 60 70 80 90100110120130140150 1.05 0.90 0.75 0.60 0.45 0.30 0.15 0.00 0.15 0.30 0.45 0.60 0.75 0.90 1.05 0 10 20 30 40 50 60 70 80 90100110120130140150 1.05 0.90 0.75 0.60 0.45 0.30 0.15 0.00 0.15 0.30 0.45 0.60 0.75 0.90 1.05 0 10 20 30 40 50 60 70 80 90100110120130140150 1.05 0.90 0.75 0.60 0.45 0.30 0.15 0.00 0.15 0.30 0.45 0.60 0.75 0.90 1.05 0 10 20 30 40 50 60 70 80 90100110120130140150 1.05 0.90 0.75 0.60 0.45 0.30 0.15 0.00 0.15 0.30 0.45 0.60 0.75 0.90 1.05 8 players 8 players 16 players 16 players 32 players 32 players 64 players 64 players 128 players 128 players 256 players 256 players 512 players 512 players Figure 4.8: Kendall tau rank correlation (y-axis) of state-of-the-art rankings with the consensus ranking over time (x-axis, the number of tournament editions). The columns are Algo1=Elo, Algo2=Glicko, Algo3=TrueSkill, Algo4=PlackettLuce. The last column is the final placement ranking in the last completed tournament. Rows are Scheduler. I added Single Elimination and Double Elimination Brackets for comparison purposes. Colors represent the different population sizes. A continuous line indicates the "before" reversing the ranking. The dotted line indicates the behavior after the reversing the ranking. This is why dot starts usually with a rank correlation close to -1. CHAPTER 4. EXPERIENCE 38 As we can see in the figure 4.8. In the base case (continuous lines), the rankings converge fast to the consensus ranking. In the Snake format, they all reach a rank correlation around 0.9. Simply put, rankings do what they are supposed to do. They rate and order players based on their skills. In the Single Elimination Bracket, the correlation is lower, around 0.75-0.8. This should not come as a surprise. Section 4.2 shows how the bracket affects a dataset and the learning of the Elo. From this picture, we can see that the rank correlation of Glicko, TrueSkill and PlackettLuce is consistent with the Elo in the same setting. Where things get interesting is when we look at the dotted lines, the ’worst case scenario’ when rankings are reversed and intentional put at around -1.0 rank correlation. We can see that it takes significantly more time for TrueSkill and PlackettLuce to reach the consensus ranking. Elo and Glicko need less time, fewer games to capture the real level of the participants. To put into perspective the performances. Take a look at the dark blue dotted line; 8 players are sorted in reverse order, the better player is rated the worst. It takes TrueSkill more than 90 snake editions to sort them, this period consists of about 630 games. 630 games were played among 8 players, facing each other again and again. If you look at the "previous Rank" in the same context, the 8 players are sorted in less than 10 editions. This setting is without a ranking intervention, it is when we use the final placement as seeding for the next edition. Basically, players sort themselves out naturally faster than in a TrueSkill environment. This shows the hard-stuck and boosted players problematics as a strict consequence of the interaction between a ranking algorithm and a scheduler. 5 Survey The thesis motivation is based on community complaints. The goal is not just to find answers, but to find ones that can be heard by the community. An important step is to verify if the methodology used is something accepted and understood by people whose job is impacted by ranking and matchmaking systems. A survey was conducted in that regard. The topic of this chapter is the perception of experts on simulation based research. 5.1 Goals & Design The goal of the study is to measure to what extent simulation based methods can be used to perform research accepted by actors in competition. The survey involves a panel - 4 persons with expertise in different fields of professional competition (in a broad sense). It is performed in three steps. • Step 1: Prior Knowledge In a Google form, participants are asked general questions about who they are, what they know and what they believe in. There is no right or wrong answer. • Step 2: Simulation based experiments Models, Simulation and the experiences of chapter 4 are presented in a series of five videos. • Step 3: Learning and Feedback Finally, in a 2nd Google form, participants are asked questions about the content presented in step 2. Do they understand the model, the experiment? What do they think of certain choices made, like the metrics of interest? Do they accept the work as knowledge? did they learn something? All the material was produced in French. The content presented is technical, and the experiments abstract. It is hard to present it accurately to an audience with diverse education and knowledge. I relied on intuition to express concepts like Convergence and stationary distribution. This is easier to do in the mother tongue, French in my case. France is the 7th biggest video game market 1 both in revenue and player base. I do not believe the language choice is detrimental to the results’ relevance. 1https://newzoo.com/resources/rankings/top-10-countries-by-game-revenues 39 CHAPTER 5. SURVEY 40 5.2 Content Presented The work is introduced in five videos uploaded on YouTube 2 , each lasting for approximately 8 to 10 minutes. The videos are unlisted and can only be watched with a link. The first video introduces the basics of simulation based research in the context of competition. I present The Bradley-Terry Model and the consensus ranking. I mention that I believe it is a valid but not frequently used methodology of research in the field. I explained that I have developed my own tool, and showed the basic code usage (Figure 3.4). I do not go into the details of the simulation methodology. However, I insist that the goal is not to draw conclusions about the real world but about a system under study. In the 3rd video, I introduce the Kendall tau rank correlation, how to read the values, and give some examples. The video also presents the Snake format with its claimed properties. Each of the sections 4.2, 4.4, and 4.5 are presented in three dedicated videos. Viewers are informed about the model, the parameters, the synthetic dataset generated, and the metric of interest. I briefly motivate the experiment - what are we trying to see, which questions are we asking ? I then present the results in one picture. I give the necessary information to read the picture so that the participants can make their own interpretation. Participants are NOT informed about my hypothesis of matchmaking overfitting. They are not aware of the steps in a simulation based research. More precisely, they are not presented with the validation steps. They are left with their own intuition and how the Bradley-Terry model fits it. To understand the survey, it is important to realize that the 3 presented experiments 3 can only be performed in simulation. In the real world, the Consensus ranking is not known (I would say does not even exist). Nobody does skilled based matchmaking for Coin Toss, and certainly not a ranking from it. And comparing the model probability versus the observed one is tricky since you only have access to the observation and not the underlying distribution. The experiments show different ranking system behavior. It is not just about a quantitative distinction, but also qualitatively. Something personally, I have not seen in the literature on the subject. Human perspective becomes very interesting when results are not just about numbers. 5.2.1 Questions In this section, I focus on the general concepts behind the questions and their goals. I do not list every single one of them. The Forms and the results are available as additional material to the thesis for anyone interested in it. In the following text, they/them/their refer to participants. Who are you? It is asked where their expertise comes from. From which game genre (Tactical Shooters, MOBA, Board game, etc.), and what roles they endorsed (Player, coach, analyst, etc.) Some questions are about their knowledge of the state-of-the-art. Which algorithm they know, which concept they are familiar with. These questions are multiple choices. What do you believe? There is a set of questions that target directly intuition, values and beliefs about ranking. For example, I ask if they agree with the CETS-215 citation (cf. 1.1). I ask if they believe competition can be manipulated with a scheduler. Most are Yes/No/Maybe questions. The others have the following formulation: On a scale from x to y, how much do you agree with [...]. The questions I ask are based on my own intuitions, ideas and opinions. They are the notions I tried to challenge myself on when 2https://youtube.com/playlist?list=PLK9VMh_9P3x1WppFpKXJchYgs39hB5c9V&si= 6dbESWSrICOeWUkf 3Single Elimination Bracket versus the Elo,Random Snake and Snake Convergence CHAPTER 5. SURVEY 47 Figure 5.7: Answers to the questions: How important are each of the following features regarding a ranking quality. Blue=Superfluous, Red=Bonus, Yellow=Useful, Green=Important, Purple=Necessary. The features from left to right are: 1) Summarized past success, 2) Predict win probability of encounter, 3) Identify balanced matchups, 4) Identify unbalanced matchups, 5) Fast convergence, 6) Correct ordering based on player level. CHAPTER 5. SURVEY 48 was skeptical that it could be interesting to anyone, expect people with technical knowledge. I am however happy with the end product. The questions are interesting and relevant. The videos are of decent quality. The submitted answers on Google Forms do not track email addresses, they are anonymous. This limits results interpretation about individuals opinions. I personally know who said what (I can compare the initial and final opinion of a given participant) because I know when participants completed each step. This is not possible for anyone else reading the data. The data tracks the evolution of a panel opinion. Yes, I do have a few interesting insights that I cannot back up 8 . It does not affect much the conclusion of the survey. Finding participants was a nightmare. By design, it targeted experts in the field, people with solid experience of competition. I cannot remember how many people I contacted with no answer. Some politely declined. One particular explained to me that he receives such survey requests on a daily basis and cannot participate in all of them. I understand the refusal and lack of answer. But it makes it hard. Really hard. There were options to open the survey. To be more flexible with the targeted participants. Ask anyone with an interest in competition. I did not make this choice. I have a panel of 4 experts. I am interested about opinions of people that ranking and matchmaking impact directly and professionally. The hypothesis is novel. It is abstract, and the survey material relies on intuition. It is a step-by-step process. Now that I have conducted this survey, I would be excited to redo such work with a broader audience, with no experience restriction. I plan in the future to upload public video on the internet about simulation in more realistic situations, and I think I would like to attach polls to collect opinions and feedback. 5.5 Discussion I want to discuss some points that may not be obvious at first glance. The panel was consistent in his answers. I presented experiments in triplets (methods, ranking feature, metric). For example, in the first video, I show an empirical analysis of a dataset evaluating win probability prediction using the "Expected versus Observed" technique. In the 3rd video, I present a simulation based study evaluating the ordering of the player with Kendall tau rank correlation. In the formulary, the participants are asked in separate questions their opinion about (A) study methodology, (B) ranking features and (C) metric used. They have simulation and empirical study both in high regard, they give the same amount of interest to the win prediction as they do to correct ordering. Finally, they consider Kendall tau rank correlation with the consensus ranking equally important for a ranking quality as the Expected versus Observed win rate. The panel did not express opinion about unsupported claims, such as the bias in a snake edition, and whether it is a skilled base matchmaking or not. They answered ’maybe’. It is a very healthy attitude. The panel was not confused by the technicality of the work, by the wordings, or by the experimental setup. They did not see me as an authority and did not believe in everything I said. They kept a critical mind. The panel sample is small, but they provided very good insight. Players seem to have strong natural ability in modeling. They spontaneously propose features to add and even present a scenario where it is relevant. They are interested and formulate their concerns, doubts and questions in terms of study to perform. They are comparing and are ready to choose their favorite ranking designed based on simulation. It is awesome. The only participant that had a negative opinion on simulation based research (and consider the model used not suited for ranking study) mentioned his experience in game design. There is only one game designer on the panel. The others have mostly experience as player, coach, analyst and manager. This is interesting. If game designers and competitors do not agree on how to validate ranking, do not have the same perception of what a ranking is, and do not consider the same model valid, then it is not surprising 8In the thesis, I only provide result that are readable from the data. I do not share what I cannot back up. CHAPTER 5. SURVEY 49 that there are community complaints about ranking and matchmaking quality. There is a disagreement on what the tool is supposed to do. There is a disagreement about what competition consists of. It does indicate that, maybe, technical work on ranking should try to define more clearly what they mean by a ranking. What it does. Personally, the methodology used in many papers about the Elo ranking fits my intuition based on my personal experience in competition. Methods used to present TrueSkill or OpenSkill do not. I care about the uniqueness of a stationary distribution. The methodological differences, and the underlying concept of ranking, inspired most of the design I present in this study. Elo in Chess does not seem to raise many critics. One learning from my side is the importance of performing such survey in an interactive fashion. When writing the formulary, I paid attention to not formulate question that orients results interpretation. I did not want my own conclusions (and bias) to influence theirs. For example, I asked in step 1 and step 3 Do you believe ranking can encourage smurfing by design?. In the final Form I did not ask In the random snake videos, do you think one of the rankings’ behavior encourages smurfing?, because this leans toward my personal interpretation. All the 4 participants already agreed that rankings can encourage smurfing by designed before watching the videos, nothing changed their minds after. I cannot support my conclusions with their opinions because I did not ask the right question. Regarding potential future work. I am interested in redoing this exact survey with more participants, not necessary experts. I wonder how the model fits their perception. The material needs to be reworked a bit. I am also very interested in involving experts in the research itself. I wonder in which steps (2.1.3) they can contribute the most. From problem identification to model development and scenario specification, for validation or metrics choices, I have reasons to believe they can contribute at pretty much every step of a simulation based research. The who, when, and how can be a complex research in itself. 6 Conclusion In this thesis, I show that simple models to simulate competition fit the intuition of experts. They do understand and accept concepts such as consensus ranking and the Bradley-Terry model. They understood and learned from abstract experiments. Likewise, They are capable to propose model’s extensions and formulate their concerns in terms of scenarios to investigate. Relevance of simulation based research is as high as other methods. More importantly, the survey shows that they are not tricked into believing unsupported claims. The work highlight the potential to integrate experts at different stage of research in the collaborative fashion. I propose the matchmaking overfitting hypothesis and provide several examples to identify and define its meaning. In the process, I was able to build a dataset for which a perfectly tuned ranking fails to generalize outside the matchmaking domain. I proposed a conceptual challenge - the random snake - in which state-of-the-art rankings display two different behaviors. I show that this difference translates to differences in convergences when manipulating the initial state. More importantly, I show the hard-stuck and boosted phenomena as the consequence of a rating system in skilled based competition. Furthermore, my works suggest multiple research priorities. What are good metrics to track in simulation based research? What are the most important components of a realistic model? What does a ranking learn in a dataset? What are the edge cases a rating system should reasonably be able to address? But above all, my work shows the importance of correctly describing the convergence of rating systems and whether it is possible to show a unique stationary distribution. The speed of convergence is less important than the resulting state itself. Below, a list of my contributions: • The RSSC protocol to study the interplay between a scheduler and a rating system • The Snake scheduler and its properties to study skilled based matchmaking • The bias of Single Elimination Bracket, expected scores do not correlate with athletes’ levels. • The Random Snake as a conceptual test for rating system. The bias of The Single Elimination bracket is likely to have a direct, immediate impact, as The FIFA ranking for football and the Riot Power Ranking put more weight on the final than the first round games. 50 7 Appendix 51 A Validation A.1 RSTT version of the 2 player Elo convergence Figure A.1: RSTT implementation 52 B Performance B.1 RSSC Protocol Figure B.1: Code snippet illustrating the ’rssc’ loop. The ’for-loop’ executes two high level functionality of the rstt package. Cup.run() generates and plays games. Ranking.update() trigger ranking internal mechanisms that results in a change of it states. This code is a core component of every simulation I perform and present in this thesis. 53 APPENDIX B. PERFORMANCE 54 B.2 Execution Profile Figure B.2: Output of the command ’pyinstrument -r html rssc.py’. You can note the limited dependencies. It uses the python built-in sort() function. Typeguard is called for typechking. Names is used to generate random name for the Player instances. All other calls are from within the package. C Experiences C.1 Probability table for the Single Elimination Bracket The below table show win probabilitis of 8 players population (player A, B, C, D, E, F, G, H). A player facing himself has 0.5 chance of wining the game (because he faces someone of identical level). It is a convention - the value is never used in the simulation. The table reads as a matrix M8×8 where the value Mi,j reads as the probability that ’i wins against j’. It satisfies IP(i wins against j) + IP(j wins against i)=1 so that there is always one of the player wining the encounter. It also enforce transitiveness. A B C D E F G H A0.5 0.55 0.6 0.65 0.7 0.75 0.8 0.85 B0.45 0.5 0.55 0.6 0.65 0.7 0.75 0.8 C0.4 0.45 0.5 0.55 0.6 0.65 0.7 0.75 D0.35 0.4 0.45 0.5 0.55 0.6 0.65 0.7 E0.3 0.35 0.4 0.45 0.5 0.55 0.6 0.65 F0.25 0.3 0.35 0.4 0.45 0.5 0.55 0.6 G0.2 0.25 0.3 0.35 0.4 0.45 0.5 0.55 H0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 55 APPENDIX C. EXPERIENCES 56