5

I am an organizer for a board game tournament. All of our players have an internal Trueskill rating we calculate to assist us with matching opponents for each round of the tournament. For each round, we can pair any player up with any other player as we wish. For each hypothetical pairing, Trueskill can provide us with a "Match Quality" score between 0.0 and 1.0, the higher the better.

Here is a grid of hypothetical Trueskill match quality scores. Note it is symmetrical along the diagonal:

           Player1  Player2  Player3  Player4
=====================================================
Player1 |    -----    0.821    0.234    0.555
Player2 |    0.821    -----    0.833    0.642
Player3 |    0.234    0.833    -----    0.743
Player4 |    0.555    0.642    0.743    -----

When we select who is paired with whom in a given round, what is the best way to maximize the total match quality score of those pairings? Obviously with a small number of players you can just iterate through all possible combinations, adding the match quality scores and select the set of pairings with the highest total value. However the number of players in our tournament makes this problematic. For 70 players, we're talking 70-factorial combinations.

What I'm doing now is basically a greedy algorithm--select the best overall pairing, remove those two players from further consideration, select the remaining overall best pairing, remove those players, etc., until all players are paired up with someone. It works quite well, but the nerd is me is wondering if there isn't a better method that will result in even more optimal overall pairing.

TorgoGuy
  • 151
  • 4
  • 2
    What is to prevent your algorithm--or indeed any algorithm--from producing identical pairings for every round? – whuber Dec 28 '12 at 05:11
  • If you have a rating for each individual, then you could match the top pair, the next pair, etc. This will not be far from optimal. – Henry Dec 28 '12 at 09:05
  • As a game-player myself, I'm wondering why you are rejecting the common formats for tournaments of either Swiss system or round robin. If you want to maximize match quality for the whole tournament, round robin after dividing the 70 players into groups probably is close to optimal. The number of groups would be based on number of rounds. – Peter Flom Dec 28 '12 at 11:47
  • @whuber--We artificially adjust the match quality score of previous pairings down to 0 to avoid rematches. – TorgoGuy Dec 28 '12 at 14:04
  • @Henry--that's about what we currently do. – TorgoGuy Dec 28 '12 at 14:09
  • @Peter Flom--We actually don't reject common formats. I simplified our situation for the question. We start with accelerated Swiss pairings. When someone has lost enough games to drop out of playoff contention, our goal for that subset of players switches from the Swiss goal (making sure top players make it to the end) to a goal of the most competitive matches possible, because it is more fun for the players to have competitive matches. Previously we used Danish pairings, but the with match quality score available, we thought it would be an ideal way to accomplish the "competitive match" goal. – TorgoGuy Dec 28 '12 at 14:11
  • In attempting to answer my own question, I've come across the "Hungarian Algorithm" which may work in a modified fashion. I'm not sure yet if even in the intended application the Hungarian algorithm guarantees an optimal result. http://en.wikipedia.org/wiki/Hungarian_algorithm – TorgoGuy Dec 28 '12 at 14:19
  • Is the "total match-quality score" just some (perhaps weighted) sum of the individual pairing scores or something more complicated? In single-elimination bracket tournaments, a relatively simple dynamic-programming solution exists to find the optimal way to fill out the projected winners for a full bracket to maximize a linear score based on choosing winners correctly. (Think NCAA bracket pools.) But, that's with the bracket already fixed. A similar idea might work, though. – cardinal Dec 28 '12 at 14:32
  • @cardinal By "total match-quality score" I meant the unweighted sum of all of the match quality scores for the selected pairings. The question relates to selecting pairings for one round of the tournament. The next round's pairings will be selected after that round is complete and will be based on the newly calculated Trueskill values (and corresponding match quality values for possible pairings) which includes their performance in the previous round. So we aren't setting up pairings for all rounds up-front. It's kinda-sorta like tournaments that reseed after each round. – TorgoGuy Dec 28 '12 at 17:11

1 Answers1

0

I haven't found an algorithm that guarantees the highest-total-value for pairings selections, but I have found one that guarantees the lowest-total-value, so we can modify the original matrix to accommodate that algorithm. Basically, we just have to subtract all of the match quality scores from 1.0 and assign a value of 2.0 along the diagonal (to ensure a player never gets paired with themself). When we do that, we get something like this:

           Player1  Player2  Player3  Player4
=====================================================
Player1 |    2.000    0.179    0.766    0.445
Player2 |    0.179    2.000    0.167    0.358
Player3 |    0.766    0.167    2.000    0.257
Player4 |    0.445    0.358    0.257    2.000

As mentioned, our goal now is to select pairings with the LOWEST overall score, not the highest and that problem can be solved using the Hungarian Algorithm. That algorithm guarantees finding an optimal set of lowest value pairings and because we subtracted the match quality score from 1.0, gives us the pairings with the highest summed match quality scores, which was the original question.

Note: When considering if we're done at each step of the algorithm, we have to ignore the duplicate symmetrical values, so that complicates applying the algorithm a bit.

TorgoGuy
  • 151
  • 4