6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I'm not sure how relevant it is to the question, but the 40-point rating difference between your hypothetical top-two Greenlanders in no way corresponds to the top guy winning 80% of the games: it would actually be something like 56%. $\endgroup$ – David Richerby Nov 28 '17 at 15:06
  • $\begingroup$ Thanks for the clarification @DavidRicherby :-) ... but that isn't really the main point of the question. The point is: the 1st place Greelander is categorically "better" than the 2nd place Greenlander, and so when the 1st place Greenlander's rating gets driven down to 1330 after spending a summer playing against the superior Australians, the 2nd place Greenlander's rating of 1805 really should be going down as well. As well as the entire graph/network of all the other Greenlanders, etc. $\endgroup$ – smeeb Nov 28 '17 at 15:09
  • $\begingroup$ The Greenlanders' ratings will go down, and quickly. They keep losing to this 1330 guy! $\endgroup$ – David Richerby Nov 28 '17 at 15:12
  • $\begingroup$ I'm assuming that the Greenland champion goes back to playing chess in Greenland after his trip to Australia. When he does that, he'll still beat all the people he used to beat before, and their ratings will sink like stones. The problem with the system you're proposing is that it can't cope with people's strength changing over time. Suppose you and I are strong players but I get old and senile. I start losing a lot of games and my rating falls. By your proposal, your rating falls, too, because we played in the past and now my rating is falling. That can't be fair to you: your rating should... $\endgroup$ – David Richerby Nov 28 '17 at 15:26
  • $\begingroup$ Thanks @DavidRicherby (+1) that makes a good point...however their ratings would only go down once the Greenlandic (?) champion returns home from his summer trip to Australia and resumes playing his fellow countrymen. And so for the entire summer they'll all have inflated ratings that aren't actually accurate to their true ability. If someone were to do a worldwide ranking mid-summer, they'd see all these seemingly-fantastic Greenlanders with inflated ratings... $\endgroup$ – smeeb Nov 28 '17 at 15:27
1
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.