Applying graph “adjustment” algorithms to Elo rating system

Question

I'm trying to address what I perceive to be a potential shortcoming in the Elo Rating System (predominantly used by the international Chess community to rate + rank players). I have a two-player game in mind (not Chess) that is played all over the world, and I'd like to start rating/ranking its players using Elo, but and am toying with the idea of adding what I might consider to be an "enhancement" to basic Elo.

So with Elo your performance rating is relative and is directly influenced by the people you've previously beaten or lost to, and what their respective performance ratings were at the time you played them.

The problem is, the game I am interested in applying Elo to is largely played in isolated "pockets" all over the world, with very little (if ever, any) crossover between these pockets. Meaning there might be a "pocket" of, say, 5,000 players in Australia that only ever play each other. And there might also be an equally-isolated group of players in, say, Greenland that also only ever play one another. Only extremely rarely would an Australian play a Greenlander.

So what I'm wondering here is that since Elo is relative to the players you've won/lost to, that you might end up with, say, the champion (ranked 1st) Australian with an Elo rating of, say, 1845. And the leading Greenlander might have an Elo of, say, 1820. So on paper they look like they are pretty much equals.

Except let's pretend that they're not -- not even close! Let's say the quality of play in Australia is far superior to the average quality of play in Greenland. And if the leading Australian + Greenlander ever played each other, the Australian would mop the floor with the Greenlander (BTW I'm American; nothing for/against Australia or Greenland here! Just using these as arbitrary examples!). In this case, it might be that if this Greenland champion were to move to Australia and start consistently playing against Australians, his Elo rating might eventually settle to, say, 1330.

Here's the fundamental problem I'm seeing with Elo:

• The Greenland champion has an Elo rating of 1845, and the 2nd ranked Greenlander has a rating of 1805
• The Greenland champion will almost always beat the 2nd place player every time (8 out of 10 times, etc.)
• But now, the Greenland champion spends a summer in Australia and consistently loses, driving his Elo rating down to 1330
• The 2nd ranked Greenlander still has a rating of 1805 even though he is inferior to a player who is now rated at 1330, all because he stayed home in the safety of Greenland

Basic/current Elo does not account for the existence of these "isolated pockets" of players and doesn't allow for the auto-correction of them on the rare occasions when "cross-pollination"/cross-over does occur (that is: when a member of one pocket plays a member of another pocket). Current Elo is hinged upon the notion that eventually all players will play each other (across all groups/pockets) and will trend towards their true score. But in my game (and I'm sure many others), this is simply not true. Most players will spend their entire lives only ever playing the same group of opponents, and I'd like to find a way to augment Elo or apply an additional adjustment algorithm to Elo that truly keeps everyone's rating true to their current ability.

Essentially I'm wondering if there's a way for ratings to "ripple throughout a pocket/isolated group" anytime this cross-pollination does occur.

I guess in my mind I was thinking about a graph algorithm that represents the play history of the entire game. Each node in the graph represents a unique player. Every edge on the graph represents a distinct game (hence the same two nodes can have multiple edges between them if the same 2 players have played each other multiple times). Then, every time a new game is played, some type of adjustment ripples out over the entire graph. So in my example above, after the Greenland champion loses his first match to the first Australian, his rating goes down...but so does the rating for every other player in the isolated "Greenland pocket", etc. So as the Greenland champion's rating converges at 1330 (the more Australians he plays) all the other Greenlander's ratings go down at the same/appropriate rate as well.

Are there any known/obvious solutions to this type of problem?

Answer 1

Good insight. There are other ranking algorithms that don't have this problem. The Bradley-Terry-Luce model is probably the easiest to understand. It is based on a principled statistical model for the likelihood that A will beat B, in terms of the difference between their ratings. It then applies maximum-likelihood statistical inference methods to infer the ratings of each player. This takes care of the issue you mentioned and ensures cross-pollination will occur.

So why do people use Elo instead of Bradley-Terry-Luce? Well, Elo is simpler. It can be implemented by hand, by looking up in a table to see how many Elo points you have gained or lost, based solely on the results of a single match. In comparison, statistical inference in the Bradley-Terry-Luce model requires a non-trivial inference algorithm that works on all the data, and so can only be done with the aid of a computer.

See also, e.g., https://stats.stackexchange.com/q/30976/2921, https://stats.stackexchange.com/q/6379/2921, https://stats.stackexchange.com/questions/tagged/rating, and https://stats.stackexchange.com/questions/tagged/ranking for more on our sister site, Statistics.SE.

Answer 2

For a graph-theoretic solution, it sounds like you want an algorithm like PageRank: https://en.wikipedia.org/wiki/PageRank

or the Hubs and Authorities algorithm (HITS): https://en.wikipedia.org/wiki/HITS_algorithm

These algorithms score nodes (individuals) based on the scores of the nodes that it beat and who beat it.

Your problem here will probably want to weigh the edges in some way to reflect the timestamp of each edge. The most recent results should count more than older edges.