An Analysis of Skill-Based Matchmaking and the Elo Rating System in Video Games
Many online video games utilize matching algorithms to decide which players are teamed with and against one another. Whether it is a sports game or a multi-player shooter, game developers rely on these algorithms to make each game as fair as possible for the user. Fair matches incentive players to keep returning as it provides greater satisfaction for users and limits the feeling of being cheated someone may have when they are matched against people with skill levels far superior to their own. In the gaming world this is known as “skill-based matchmaking” or SBMM for short where players are matched by perceived skill generated by an algorithm.
Thore Graepel and Ralf Herbrich introduce the foundation of many computer matchmaking algorithms as Professor Árpád Élő who created the Elo rating system which has been used by the World Chess Federation in determining the matchings of two chess players. The Elo rating system assigns players a level of skill based on the number of matches they play and the outcomes of those matches. Using these skill ratings the system can assign probabilities to who will win and payoffs for the outcomes. For instance, a player with a higher skill rating will have a higher predicted probability of winning and a lower payoff for doing so. In general, the more matches a player has the more accurate the Elo rating system becomes as there is more data for the ranking system to include in its calculations. While many video games match more than just two players, the principles of the Elo rating system still apply. For the Xbox 360, Microsoft utilized a version of this called Trueskill which can be applied to team-based games where there are multiple players to a team and/or more than two parties involved.
In general, skill-based matchmaking attempts to make the probability either side wins in a match as close to even (in two party games 50/50) as possible. The most basic principles of skill-based matchmaking and the Elo rating system can be looked at as a matching markets problem which we learned about in lecture. Here we would randomly divide the player base in to two groups of players (buyers and sellers) who have skill ratings (prices and values) and we have to match them such that they are disparity minimizing (minimizes rating difference). In the image attached below we can see an example network where we have 6 players who are matched in a way that minimizes the disparity between their skill ratings. By minimizing the disparity, skill-based matchmaking is attempting to make matches “fairer” (as close to 50/50 as possible) and thus increase player retention.
An example skill-based matchmaking network
The example described above is applicable in settings where we have 1 versus 1 player matches. It can be expanded to fit as many players as one wants to track which can be beneficial to the players as the more skill ratings there are to match the smaller and smaller the disparity can get. An interesting form of matching described in the article is one used to match players to two teams. It goes like this, you match the highest skill rating player to one team and the second highest to the other. After this you match each subsequently highest ranked player to the team with the lower total skill rating. While we haven’t covered something like this in class one could potentially illustrate this in a dynamic network where the total ranking for each team is updated after each round and the next matching is decided accordingly.
https://www.herbrich.me/papers/Game-Developer-Feature-Article-Graepel-Herbrich.pdf