Matchmaking Networks 🕸️¶
Introduction¶
Given a pool of players (nodes), pair them by skill level $X$ to ensure enjoyable games (links).
- Start from $N$ players with associated rating (color) $x$
- Pairs two players. Players with similar rating have higher probability to be paired.
- Repeat. Increase edge weight by one if the edge already exists.
Let’s focus on the player with highest rating (yellow node):
- Strong links with next strong players (green / blue nodes)
- Few links with low rated players (dark purple nodes)
- Links weights are not symmetric
Rating System¶
Many matchmaking algorithms rely on rating system to provide fair matches, i.e.
a scalar value quantifies the player’s strength relative to other players.
Matchmaking based on rating systems is employed in
Board Games: Chess, Go, Backgammon, ...
Video Games: League of Legends, Dota 2, CS:GO, ...
Sports: Tennis, Table Tennis, ...
I've studied the emerging matchmaking network on chess games dataset.
Elo - Definition¶
Proposed by Arpad Elo, it infers rating from wins, losses, and draws against other players.
Let $E_A$ be the expected result for player $A$ with rating $x_A$ (same for player $B$)
$$ \begin{cases} E_A \propto 10^{x_A / 400} \\ E_B \propto 10^{x_B / 400} \end{cases} \quad \textrm{such that} \quad E_A + E_B = 1 $$
If the game result is $S_A$, $x_A'$ is the updated rating of player A:
$$ x_A' = x_A + K \cdot (S_A - E_A) \quad \textrm{where} \quad S_A = \begin{cases} 1 &\textrm{if $A$ wins} \\ 0.5 &\textrm{if $A$ draws} \\ 0 &\textrm{if $A$ loses} \\ \end{cases} $$
$K$ is a fixed parameter, usually in the range $[10, 40]$.
Elo - Distribution¶
$$ E_A = \mathbb{P} (A \, \textrm{wins}) = {\left[1 + e^{-\frac{\ln{10}}{400} (x_A - x_B )} \right]}^{-1} \quad F_{\textrm{ Logistic}} (x \, | \, \mu, \, \beta ) = {\left[ 1 + e^{-\frac{(x - \mu )}{\beta}} \right]}^{-1} $$
$$ X_A - X_B \sim \textrm{Logistic} \left(x_A - x_B \, | \, \mu=0, \, \beta=\frac{400}{\ln{10}} \right) $$
Property
$$ \begin{cases} X_A \sim \textrm{Gumbel }(x_A \, | \mu_{X_A}, \, \beta)\\ X_B \sim \textrm{Gumbel }(x_B \, | \mu_{X_B}, \, \beta) \end{cases} \quad \Rightarrow \quad X_A - X_B \sim \textrm{Logistic} \left(x_A - x_B \, | \, \mu_{X_A} - \mu_{X_B}, \, \beta \right) $$
$$ \Longrightarrow X \sim \textrm{Gumbel}\left(x \, | \, \mu=\mu_{X}, \, \beta=\frac{400}{\ln{10}} \right) = \frac{1}{\beta} \exp{\left[\frac{x - \mu}{\beta} - \exp{\left(\frac{x - \mu}{\beta}\right)}\right]} $$
Matchmaking Network - Chess Games¶
- Dataset: games played on lichess.org between 2014 and 2016.
- Rating System: Glicko-2, an improvement over Elo.
- Matchmaking: pairs players with similar rating, $x \pm \Delta x$
Players distribution¶
Games distribution¶
Graph¶
Nodes
- represent a player
- property: $x$
- $N = 172,195$
Links
- represent games played between two players
- directed: player with white pieces is the source
- weight: number of games
- $L = 30,081,979$
- $x$-assortativity
- expected high positive value
- $0.7612 \pm 0.0001$
- Degree distribution
- Does not follow power-law
- Physical limit (games per month) & Structural limit (nodes with extreme $x$)
- Distances
- computed over 2000 sampled nodes: $\langle d \rangle = 2.90 $
- pseudo-diameter: $d_{\max} = 8$
Reduced Graph¶
Group players with same $x$-bin into single node.
Nodes
- represent a bin of size 50
- properties: $x$-bin, # players
- $N = 39$
Links
- represent games between bins of players
- directed: players with white pieces are the source
- weight: number of games
- self-loops: players of the same bin can play against each other
- $L = N^2 = 1521$
- weighted $x$-assortativity: $0.78 \pm 0.33$
Matchmaking Network - Simple Model¶
Recipe¶
- Start from fix set of $N$ nodes with rating $X \sim \mathcal{N}(\mu_{x}, \sigma_{x})$
- Select a random node $s$ as source
- Sample from distribution $ \propto \mathcal{N} (\mu_{x}, \sigma_{x}) \cdot \mathcal{N} (x_s, \alpha)$ a rating $x_t$
- Add the edge $s \rightarrow t$ where $t :=$ argmin $|x_v - x_{t}|$ (with $v \neq s$)
... and repeat 2. to 4.
$$ \mathcal{N} (\mu_t, \beta \,) = \mathcal{N} (\mu_{x}, \sigma_{x}) \cdot \mathcal{N} (x_s, \alpha) \quad \text{where} \quad \mu_{t} := \frac{\mu_x \alpha^2 + x_s \sigma^2_x}{\sigma^2_x + \alpha^2} \quad \beta := \sqrt{\frac{\sigma^2_x \alpha^2}{\sigma^2_x + \alpha^2}} $$
$$ \mathcal{N}_x \equiv \mathcal{N} (\mu_{x}, \sigma_{x}) \, \begin{cases} \mu_{x} = 1500 \\ \sigma_{x} = 250 \end{cases} \quad \mathcal{N}_s \equiv \mathcal{N} (x_s, \alpha) \, \begin{cases} x_s = 2300 \\ \alpha = 150 \end{cases} \quad \Longrightarrow \quad \mathcal{N}_t \begin{cases} \mu_t \approx 2088 \\ \beta \approx 129 \end{cases} $$
Example:$\quad N = 300 \quad L = 30,000 \quad \mathcal{N}(\mu_x = 1500, \sigma_x = 400) \quad \alpha = 200 $
- weighted $x$-assortativity: $0.86 \pm 0.04$
References¶
[1] Elo, Arpad E. (August 1967). "The Proposed USCF Rating System, Its Development, Theory, and Applications". Chess Life. XXII (8): 242–247. PDF
[2] Arthur, Berg. (September 2020). "Statistical Analysis of the Elo Rating System in Chess". LINK
[3] Lichess.org, "Lichess Database." Accessed June 10, 2024. LINK
[4] Barabási, Albert-László. (2016). "Network Science". Cambridge University Press. LINK
[5] Peixoto, Tiago P. (2014). "The graph-tool Python library". LINK
[6] P.A. Bromiley (November 2003), "Product and Convolution of Gaussian Distribution". Internal report. PDF