Fair tournament

[EternalFury]

I just found this forum and I feel like a starving prospector at the sight of a big gold nugget...

Here is a problem:

n players
k players per team

Each player must play “with” and “against” every other player at least  once and an equal number of times using a minimal number of matches.

An easy example:

Players = 1, 2, 3, 4 (n = 4) 2 players per team (k = 2) Matches: 1, 2 vs. 3, 4 1, 3 vs. 2, 4 1, 4 vs. 2, 3 After those 3 matches, all players played “with”  each other once and “against” each other twice.

As simple as it gets.

The goal is obviously to have a fair assessment of each player's skills.

The challenge that is causing me trouble:

Find an efficient method to generate the minimal number of matches for any n and k.

It sounded trivial at first… at first.

Reading around here, I see this is not trivial at all, particularly for any n and k.

If I were to fix k to 4 and needed a solution for 5, 6, 7, 8, 9, 10...16 players, what would your suggest?

[Ian Wakeling]

I think there are far fewer options for a fair tournament than you realise.  With k=2 the whist schedules do nicely for 4p players or 4p+1 players. The problems start with k>2.

It is easily shown that if players are to play "with" each other exactly n1 times, and "against" each other n2 times, that the following must hold:

n1*k = n2*(k-1)

So in your example above 1*2=2*1, but now with k=4 the simplest solution that might be possible is n1=3 and n2=4.

The schedule with 8 players does exist:

(8 4 5 7) vs (3 1 6 2)
(8 5 6 1) vs (4 2 7 3)
(8 6 7 2) vs (5 3 1 4)
(8 7 1 3) vs (6 4 2 5)
(8 1 2 4) vs (7 5 3 6)
(8 2 3 5) vs (1 6 4 7)
(8 3 4 6) vs (2 7 5 1)

It may well be possible to have a fair 15 round schedule for 16 players with two matches per round, but when there are between 9 and 15 players then things are likely to get messy with byes each round.  I would think there is no alternative other than writing an algorithm to try to examine a large number of potential schedules and choose one with optimal fairness, but note that even giving everyone the same number of games may be difficult.

[EternalFury]

I think there are far fewer options for a fair tournament than you realise.  With k=2 the whist schedules do nicely for 4p players or 4p+1 players. The problems start with k>2.

It is easily shown that if players are to play "with" each other exactly n1 times, and "against" each other n2 times, that the following must hold:

n1*k = n2*(k-1)

So in your example above 1*2=2*1, but now with k=4 the simplest solution that might be possible is n1=3 and n2=4.

The schedule with 8 players does exist:

(8 4 5 7) vs (3 1 6 2)
(8 5 6 1) vs (4 2 7 3)
(8 6 7 2) vs (5 3 1 4)
(8 7 1 3) vs (6 4 2 5)
(8 1 2 4) vs (7 5 3 6)
(8 2 3 5) vs (1 6 4 7)
(8 3 4 6) vs (2 7 5 1)

It may well be possible to have a fair 15 round schedule for 16 players with two matches per round, but when there are between 9 and 15 players then things are likely to get messy with byes each round.  I would think there is no alternative other than writing an algorithm to try to examine a large number of potential schedules and choose one with optimal fairness, but note that even giving everyone the same number of games may be difficult.

Hi Ian,

Thank you! You are amazing.

Yes, over the past few days, as I wrote several programs that appear to run a very very very long time without returning any results, I now realize that "there are far fewer options" than I thought.

I don't have a constructive method, so brute force is all that remains. But, even then, the computational power required is quite large.

If you know other equations bounding the combination space, it would help.

n1*k = n2*(k-1) is a good one.

Would there be any constraining r (the number of rounds required)?

Any other?

As far as r is concerned, when I am dealing with human players with limited availability and patience, I assume I cannot use more than 32 rounds.

Something tells me that a constructive approach to this problem would have the elegance of a very very rare wonder.

I'll keep you posted on my findings, but my hopes are not what they used to be when I started asking myself those questions.

I submitted the problem to several "serious" Mathematicians and they all gave me that look they give me when I bring them a problem that is both too trivial and too hard to solve.

[Ian Wakeling]

I am not aware of any literature for the k>2 scenario so that may be the cause of the look you received.  Certainly I can't find any mention in the books I have here. Rather than the number of rounds required, it may be better to consider the total number of matches required.  This is:

    n1*v*(v-1)
m = ----------
    2*k*(k-1)

where v is the number of players.  Clearly m must be a whole number to work.  If you investigate for k=4 & n1=3, then the only choices of v that work are 8,9,16,17, etc.. and like the whist designs, this corresponds to everyone, or everyone but one bye, playing in each round.  So constructions may exist for all these, I don't see that there is anything else even close to your limit of 32 rounds, apart from:

v=12, k=4, n1=6, n2=8, m=33

where each player would play in 22 of the 33 matches.

So the algorithmic solution will be the only option most of the time.  Certainly you shouldn't be thinking of trying to test all possible schedules as there will be far too many.  Some sort of iterative improvement approach might work.

[Ian Wakeling]

After some more searching I have found something useful in the literature. Have a look at this article on nested designs.  If you can make sense of this, then Table 36.5 items 9 and 37, which are described later on as 'pitch tournaments' will provide solutions for 9 and 16 players when k=4.

[EternalFury]

Ian,

I'm back.

Yes, the problem is very resistant to brute force approaches. I know that now! Yikes!

So, I must reduce it.

I am willing to reduce it as follows:

1) I will only care about cases where n is a multiple of k. From a practical standpoint, that probably means I am only interested in n = 8, 12, 16, 20, 24, 28, 32.

2) I will not have any constraints on n1 or n2.

3) I will not have any constraints on m (the number of matches required).

With these restrictions, can you think of a heuristic that would make the problem more computationally tractable?

I am not interested in inventorying all possible schedules, I really just need 1 schedule for each value of n. Obviously, if m could be as small as possible, it would make things simpler as well.

Any suggestions?

[Ian Wakeling]

There is still the combinatorial approach - there is the 8 player schedule above, and the 16 player schedule is in the reference I gave, you just need to develop the first round into 15 rounds, each time adding 1 to the previous round and reducing modulo 15 (take infinity+1 to be infinity).  There is every possibility that constructions exist for 24 players in 23 rounds, and 32 players in 31 rounds.  You may be reluctant to take this route, but I would be amazed if you could find the last two schedules using an algorithmic approach.

If I had to construct an algorithm I think I would use a two stage approach.  In practial terms, the participants will probably be more aware of the players who they play with, rather than the players they play against, so I would give priority to balancing the former aspect of the schedule.  Let's say there were going to be 15 matches of 4 against 4, then I would first decide on the makeup of 30 teams of 4, such that every player plays with every other as evenly as possible.  This corresponds to a partially balanced incomplete block design and there are approaches you could take to find this - for example, see table 2 in "Constructing some PBIBD(2)s by Tabu Search Algorithm", Luis B. Morales, 2002.  Then in the second stage I would try to pair up the 30 blocks to make the 15 matches, you would need an algorithm that forbids placing the same player on opposing teams and also tries to balance the frequency with which player pairs oppose.

Hope that might give you some ideas.

[EternalFury]

I have this resolution:

// v = 12, k = 4, L = 3

Resolution:

[[0, 1, 3, 7], [2, 4, 9, 10], [5, 6, 8, 11]], [[0, 1, 3, 11], [2, 6, 7, 9], [4, 5, 8, 10]],
[[0, 1, 4, 6], [2, 3, 5, 9], [7, 8, 10, 11]], [[0, 2, 6, 10], [1, 3, 8, 9], [4, 5, 7, 11]],
[[0, 2, 7, 8], [1, 5, 9, 10], [3, 4, 6, 11]], [[0, 2, 10, 11], [1, 5, 6, 8], [3, 4, 7, 9]],
[[0, 3, 5, 10], [1, 2, 4, 8], [6, 7, 9, 11]], [[0, 4, 5, 7], [1, 9, 10, 11], [2, 3, 6, 8]],
[[0, 4, 8, 9], [1, 6, 7, 10], [2, 3, 5, 11]], [[0, 5, 6, 9], [1, 2, 4, 11], [3, 7, 8, 10]],
[[0, 8, 9, 11], [1, 2, 5, 7], [3, 4, 6, 10]]

How do I make a schedule out of it?

[Ian Wakeling]

There are an odd number of blocks in your example, so one block can't be used in the final schedule, and as a consequence 4 players will be one game short. Nevertheless, it is relatively easy to pair up the resolution classes so that there is a pair of blocks that do not intersect (highlighted).  The two highlighted blocks in each pair of classes can form 1 match, the remaining pair of blocks in each class can form two other matches. Finally take any 2 blocks from the last class to form the 16th match.

The hard part will be constructing an algorithm to find as many of these partitions as possible, then pick the partition that gives the best opponent balance.  For each one make an opponent frequency matrix and pick the one with the lowest sum of squared frequencies.

0, 1, 3, 7      2, 4, 9, 10      5, 6, 8, 11
0, 1, 3, 11     2, 6, 7, 9       4, 5, 8, 10
            
0, 2, 7, 8      1, 5, 9, 10      3, 4, 6, 11
0, 8, 9, 11     1, 2, 5, 7       3, 4, 6, 10
            
0, 2, 6,  10    1, 3, 8, 9       4, 5, 7, 11
0, 2, 10, 11    1, 5, 6, 8       3, 4, 7, 9
            
0, 3, 5, 10     1, 2, 4, 8       6, 7, 9, 11
0, 5, 6, 9      1, 2, 4, 11      3, 7, 8, 10
            
            
0, 4, 8, 9      1, 6, 7, 10      2, 3, 5, 11
0, 1, 4, 6      2, 3, 5, 9       7, 8, 10, 11
            
0, 4, 5, 7      1, 9, 10, 11     2, 3, 6, 8