Titre :

Skill Rating for Multiplayer Games Introducing Hypernode Graphs and their Spectral Theory

Auteur(s) :

Ricatte, Thomas [Auteur]
Machine Learning in Information Networks [MAGNET]
Gilleron, Remi [Auteur]
Machine Learning in Information Networks [MAGNET]
Tommasi, Marc [Auteur]
Machine Learning in Information Networks [MAGNET]

Titre de la revue :

Journal of Machine Learning Research

Pagination :

1 - 18

Éditeur :

Microtome Publishing

Date de publication :

2020

ISSN :

1532-4435

Mot(s)-clé(s) en anglais :

Hypergraphs
Graph Laplacians
Graph Kernels
Spectral Learning
Semi- supervised Learning
Multiplayer Games
Skill Rating Algorithms

Discipline(s) HAL :

Informatique [cs]/Intelligence artificielle [cs.AI]

Résumé en anglais : [en]

We consider the skill rating problem for multiplayer games, that is how to infer player skills from game outcomes in multiplayer games. We formulate the problem as a minimization problem arg min s s T ∆s where ∆ is a ...
Lire la suite >We consider the skill rating problem for multiplayer games, that is how to infer player skills from game outcomes in multiplayer games. We formulate the problem as a minimization problem arg min s s T ∆s where ∆ is a positive semidefinite matrix and s a real-valued function, of which some entries are the skill values to be inferred and other entries are constrained by the game outcomes. We leverage graph-based semi-supervised learning (SSL) algorithms for this problem. We apply our algorithms on several data sets of multiplayer games and obtain very promising results compared to Elo Duelling (see Elo, 1978) and TrueSkill (see Herbrich et al., 2006). As we leverage graph-based SSL algorithms and because games can be seen as relations between sets of players, we then generalize the approach. For this aim, we introduce a new finite model, called hypernode graph, defined to be a set of weighted binary relations between sets of nodes. We define Laplacians of hy-pernode graphs. Then, we show that the skill rating problem for multiplayer games can be formulated as arg min s s T ∆s where ∆ is the Laplacian of a hypernode graph constructed from a set of games. From a fundamental perspective, we show that hypernode graph Laplacians are symmetric positive semidefinite matrices with constant functions in their null space. We show that problems on hypernode graphs can not be solved with graph constructions and graph kernels. We relate hypernode graphs to signed graphs showing that positive relations between groups can lead to negative relations between individuals.Lire moins >

Langue :

Anglais

Vulgarisation :

Non

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL