1-on-1 unorganized tournament scoring system

Question

Assume I want to run a game tournament with 1-on-1 games (think chess) that have (for simplicity) just win or lose as the outcome and I need a way to rank the players. Formally speaking, I want a function that takes a list of (player1, player2, who_won) triples and returns a ranking of players, e.g. by attributing each of them a number (list of (player, score)).

Because the tournament is going to be informal and unorganized, I cannot in any way influence who plays against whom when. The scoring system I am looking for should have these properties:

• The order of games should not matter.
• If two (or more) players keep playing against each other over and over, with the same winning probabilities, the scores should not change (or not change much, e.g. converge).

If necessary, new games can affect the scores of all people, and calculations might need a computer.

What scoring systems fulfil this?

Answer 1

Try this, it's a system called Whole-History Rating. From the abstract:

Whole-History Rating (WHR) is a new method to estimate the time-varying strengths of players involved in paired comparisons. Like many variations of the Elo rating system, the whole-history approach is based on the dynamic Bradley-Terry model. But, instead of using incremental approximations, WHR directly computes the exact maximum a posteriori over the whole rating history of all players. This additional accuracy comes at a higher computational cost than traditional methods, but computation is still fast enough to be easily applied in real time to large-scale game servers (a new game is added in less than 0.001 second). Experiments demonstrate that, in comparison to Elo, Glicko, TrueSkill, and decayed-history algorithms, WHR produces better predictions.

It's been used rather successfully by a game I play called Arimaa. For a tournament score, rather than a player skill rating, you will probably want to treat all games as being played simultaneously, as opposed to allowing the ratio to fluctuate over time.

If it's source code you're after, you may find this pure Ruby implementation helpful. It can support any two player game, as long as the outcome is a simple win/loss.

Answer 2

ELO

ELO is the simplest ranking system, but it does not that fulfill your requirements since order of games do matter. in ELO, Each player has a fitness rating that is updated after each game. Winning a player with higher rating than you largely increases your rating, winning a player with lower rating than you slightly increase your rating.

see Understanding the Elo Rating System