Open-ended tournament pairing algorithm

Question

I'm developing a tournament model for a virtual city commerce game (Urbien.com) and would love to get some algorithm suggestions. Here's the scenario and current "basic" implementation:

Scenario

• Entries are paired up duel-style, like on the original Facemash or Pixoto.com.
• The "player" is a judge, who gets a stream of dueling pairs and must choose a winner for each pair.
• Tournaments never end, people can submit new entries at any time and winners of the day/week/month/millenium are chosen based on the data at that date.

Problems to be solved

• Rating algorithm - how to rate tournament entries and how to adjust their ratings after each match?
• Pairing algorithm - how to choose the next pair to feed the player?

Current solution

• Rating algorithm - the Elo rating system currently used in chess and other tournaments.
• Pairing algorithm - our current algorithm recognizes two imperatives:
  1. Give more duels to entries that have had less duels so far
  2. Match people with similar ratings with higher probability

Given:
N = total number of entries in the tournament
D = total number of duels played in the tournament so far by all players
Dx = how many duels player x has had so far

To choose players x and y to duel, we first choose player x with probability:

p(x) = (1 - (Dx / D)) / N

Then choose player y the following way: Sort the players by rating Let the probability of choosing player j at index jIdx in the sorted list be: p(j) = ... 0, if (j == x) n*r^abs(jIdx - xIdx) otherwise

where 0 < r < 1 is a coefficient to be chosen, and n is a normalization factor.

Basically the probabilities in either direction from x form a geometic series, normalized so they sum to 1.

Concerns

• Maximize informational value of a duel - pairing the lowest rated entry against the highest rated entry is very unlikely to give you any useful information.
• Speed - we don't want to do massive amounts of calculations just to choose one pair. One alternative is to use something like the Swiss pairing system and pair up all entries at once, instead of choosing new duels one at a time. This has the drawback (?) that all entries submitted in a given timeframe will experience roughly the same amount of duels, which may or may not be desirable.
• Equilibrium - Pixoto's ImageDuel algorithm detects when entries are unlikely to further improve their rating and gives them less duels from then on. The benefits of such detection are debatable. On the one hand, you can save on computation if you "pause" half the entries. On the other hand, entries with established ratings may be the perfect matches for new entries, to establish the newbies' ratings.
• Number of entries - if there are just a few entries, say 10, perhaps a simpler algorithm should be used.
• Wins/Losses - how does the player's win/loss ratio affect the next pairing, if at all?
• Storage - what to store about each entry and about the tournament itself? Currently stored: Tournament Entry: # duels so far, # wins, # losses, rating Tournament: # duels so far, # entries

Answer 1

instead of throwing in ELO and ad-hoc probability formulae, you could use a standard approach based on the maximum likelihood method.

The maximum likelihood method is a method for parameter estimation and it works like this (example). Every contestant (player) is assigned a parameter s[i] (1 <= i <= N where N is total number of contestants) that measures the strength or skill of that player. You pick a formula that maps the strengths of two players into a probability that the first player wins. For example,

P(i, j) = 1/(1 + exp(s[j] - s[i]))

which is the logistic curve (see http://en.wikipedia.org/wiki/Sigmoid_function). When you have then a table that shows the actual results between the users, you use global optimization (e.g. gradient descent) to find those strength parameters s[1] .. s[N] that maximize the probability of the actually observed match result. E.g. if you have three contestants and have observed two results:

• Player 1 won over Player 2
• Player 2 won over Player 3

then you find parameters s[1], s[2], s[3] that maximize the value of the product

 P(1, 2) * P(2, 3)

Incidentally, it can be easier to maximize

 log P(1, 2) + log P(2, 3)

Note that if you use something like the logistics curve, it is only the difference of the strength parameters that matters so you need to anchor the values somewhere, e.g. choose arbitrarily

 s[1] = 0

In order to have more recent matches "weigh" more, you can adjust the importance of the match results based on their age. If t measures the time since a match took place (in some time units), you can maximize the value of the sum (using the example)

 e^-t log P(1, 2) + e^-t' log P(2, 3)

where t and t' are the ages of the matches 1-2 and 2-3, so that those games that occurred more recently weigh more.

The interesting thing in this approach is that when the strength parameters have values, the P(...) formula can be used immediately to calculate the win/lose probability for any future match. To pair contestants, you can pair those where the P(...) value is close to 0.5, and then prefer those contestants whose time-adjusted number of matches (sum of e^-t1 + e^-t2 + ...) for match ages t1, t2, ... is low. The best thing would be to calculate the total impact of a win or loss between two players globally and then prefer those matches that have the largest expected impact on the ratings, but that could require lots of calculations.

You don't need to run the maximum likelihood estimation / global optimization algorithm all the time; you can run it e.g. once a day as a batch run and use the results for the next day for matching people together. The time-adjusted match masses can be updated real time anyway.

On algorithm side, you can sort the players after the maximum likelihood run base on their s parameter, so it's very easy to find equal-strength players quickly.