Date:
17/8, 10:30pm-12:20pm
Description
Ranking mechanisms play an important part in games. For example, player ranking is a significant component of matchmaking as well as tournaments. Similarly, AI competitions require some for of ranking for different algorithms. Given a performance measure like a score that induces a total order, finding a ranking is straightforward in single-player games. However, in multi-player games, considering pairwise comparisons makes this problem more difficult. Moreover, if the goal is to measure performance over multiple smaller games, the performance measure becomes multi-objective, thus adding an additional layer of difficulty. Ranking methods (and the related voting systems) have been a subject of research in game theory and algorithm benchmarking. Among other concepts, social choice theory was developed to provide a theoretical foundation for the analysis of ranking methods. Despite this existing framework, the theoretical properties of ranking and matchmaking algorithms in games and related literature are rarely investigated in depth. We propose this tutorial to introduce CIG researchers to more ranking systems inspired by game theory as well as their strengths and weaknesses for potential application in games as well as to facilitate discussions in that domain.
Outline
In the tutorial, we will thus present theorems and paradoxes in the realm of social choice theory and mechanism design along with their potential applications in games. We will present voting systems such as the Borda-count and the Condorcet method along with important taxonomies, such the distinction between preferential and non-preferential voting systems. Additionally, we will present the criteria used to characterise ranking methods in social choice theory and demonstrate their applicability to ranking in games. The criteria describe properties that a voting method should fulfill, such as the majority criterion, i.e. the candidate preferred by more than 50% of voters should win. We will also include important results such as Arrow’s theorem about the impossibility of fulfilling all of the criteria at once.
Format
We will start the session with illustrative examples of shortcomings of different ranking methods. In these examples, we want to involve the audience members by having them participate in the ranking. We will then provide relevant game-theoretic background and state-of-the-art methods from related fields. We will show the different outcomes of ranking methods when applied to various games and competitions. We conclude the tutorial with a discussion of the desirability of different game theoretic properties of ranking methods in the context of games.
List of presenters
Boris Naujoks: Boris is a professor for Applied Mathematics at TH Köln – Cologne University of Applied Sciences (THK). He joint THK directly after he received his PhD from Dortmund Technical University in 2011. During his time in Dortmund, Boris worked as a research assistant in different projects and
gained industrial experience working for different SMEs. Meanwhile, he enjoys the combination of teaching mathematics as well as computer science and exploring EC and CI techniques at the Campus Gummersbach of THK. He focuses on multiobjective (evolutionary) optimization, in particular hypervolume based algorithms, and the (industrial) applicability of the explored methods.
Vanessa Volz: Vanessa is a research assistant at TU Dortmund, Germany, with focus in computational intelligence. She holds B.Sc. degrees in Information Systems and in Computer Science from WWU Münster, Germany. She received an M.Sc. with distinction in Advanced Computing: Machine Learning, Data Mining and High Performance Computing from University of Bristol, UK in 2014 after completing a BigData internship at Brown University, RI, USA. Her current research focus is on employing surrogate-assisted evolutionary algorithms to obtain balance and robustness in systems with interacting human and artificial agents, especially in the context of games.
