Single RR, 5-10 Competitors, ONE Venue Efficiency?

[Ben_J]

I run Martial Arts Tournaments. We are slowly growing larger, more professional, so I'm wondering if there's a better way build a Round-Robin Pool Schedule.

Each Pool of Competitors has one ring, so the matches for the Round-Robin are sequential. Getting everyone to fight each other is easy. Is there any algorithm which efficiently equalizes (or close to) the number of matches BETWEEN a given competitor's fights?

The idea is to have no fighter need to take a break from fighting for too long, nor be required to jump into his/her next fight after too short a time off.

I have been able to build (by hand) a Five-Person Pool (which we've used for a while - example below):
1   1v4
2   3v5
3   2v4
4   1v3
5   2v5
6   3v4
7   1v5
8   2v3
9   4v5
10 1v2
This meets most of the normal high-points of RR design; the last few matches are likely to be the most important results / most exciting matches to watch, etc. In every match, one competitor had 2 matches off, the other had 1 match off. Usually, the higher-seeded competitor had more rest (notable exception - 3v4 match #6).

What I'm interested in is determining if there is any algorithmic way to build a similar schedule for 6, 7, 8, or even 9 or10 competitors?

The primary goal is to have, as much as possible, the 'matches between' for each competitor to be +/-1 all the way through the schedule. Like for Seven (7) Competitors, is there a schedule where each fighter gets a minimum of 2 fights break between his/her matches?

I've tried playing with it by-hand, and it's just hellish.

[Ian Wakeling]

The more competitors there are, the easier it should be to meet your requirements as the average wait time gets longer.  For example with 10 competitors there are 45 fights, and any one competitor takes part in 9 fights, or 1 fight out of 5.  In your schedule above the numbers are double - 4 fights out of 10.

I think the algorithm you are looking for may be to unravel the cyclic round-robins.  If you follow the 'schedules' link near the top of this page then enter 6 items, then you can unravel the cyclic schedule (reading from right to left) to obtain:

3 4
2 5
1 6
2 3
4 6
1 5
2 6
3 5
1 4
5 6
2 4
1 3
4 5
3 6
1 2

This can then be tweaked to your exact requirements.  For example if you swapped all the 4s and 6s around then the last three fights would be between closely seeded competitors.   The same approach should work for any even number of competitors.   For 7 and 9 competitors, start with the cyclic schedules for 8 and 10 competitors respectively, then delete 'Match 1' before applying the same unravelling process and finally subtract one from all the competitor numbers.

[wbport]

Try this round robin generator chosing Min. Moves.  With 9 fights per round, each competitor will be in there once in from 8-10 round each: rrpair.php.

[Ben_J]

That's pretty much what I've been doing. It worked fine for 6-Competitors, but if you look at, for example the 8-Player schedule, it's a large jump to take the 3v4 match down towards the end of the event; this also has immediate knock-on effects on the rest of the schedule, etc...

That gets even worse for the method described for odd number of players, since then even the (without the #1 player) 2v3 match is buried upstream...

In other words, that's back to doing it all by hand as I have been. That's pretty specifically why I'm looking for an algorithmic solution, if one exists.

I'm attaching a screenshot of the Excel spreadsheet I've been using; I can move the matches around and it will count the number of fights between, the 'time-off' for each fighter before his next fight. I hand-mark (in yellow), the places where I feel like it's either too short or too long a wait, and I'd like to make it better. But because each time I move a fight, it has an effect on the time between someone else's matches, what's in the pic here is as close as I've been able to get to acceptable.

Right now, the 5-Person pool is, I think, as good as it can be. The 6-Person pool is OK, and the 7-Person is pretty good. But when I get to 8, 9, or 10 people, I just feel like there *should* be a better way. I just can't find anything that speaks to this kind of problem when googling...

[Ben_J]

Try this round robin generator chosing Min. Moves.  With 9 fights per round, each competitor will be in there once in from 8-10 round each: rrpair.php.

Excellent, thank you I will try that.

[Ben_J]

Try this round robin generator chosing Min. Moves.  With 9 fights per round, each competitor will be in there once in from 8-10 round each: rrpair.php.

After playing with this for a bit - it still has the same basic problem; because this algorithm (as well as the one hosted locally to this board) take each Round as a discrete event, separate from the other rounds, the order, either within the round or which round gets done in which order, does not matter to the overall solution, other than a couple of limited constraints such as placing the high-"value" matches near the end.

If I'm understanding the 'Min-Moves' constraint in the Chess RR solver, the constraint works for 1/2 the field at a time, but since it does not also constrain the other 1/2, for my purposes, it still allows what become, for my needs, conflicts - so again I think I'm back to square one...

[Ben_J]

So, for example - I don't know why I didn't find this before in my searching, but this paper is exactly what I'm trying to figure out:
http://cs.stanford.edu/~warut/roundrobin.pdf

That said, having just read it quickly, it does not have a 'solver', per se, it simply proves that a few things are possible in terms of the things I'm trying to figure out.

[Ian Wakeling]

I don't think I explained clearly enough, as there is no need to move matches around.   If you take a full round-robin schedule, apply any permutation to the competitor numbers, then you will still have a full round-robin schedule.   In the image I show the 8 player cyclic schedule in the top half, then below that I have applied the following permutation to the numbers :

Leave competitors 1, 2 & 3 unchanged.  Transform
4 to 5
5 to 7
6 to 8
7 to 6
8 to 4

the overall effect of these changes is to make the last round 4 fights between closely seeded competitors.   I would be interested to know how this measures up if you unravel it as I have suggested above and then paste in to your spreadsheet.   My gut feel is that your manual approach has given a close to optimal solution for 8 competitors, so I am not hopeful on improving on it.  But perhaps the same approach applied to 10 competitors will offer an improvement.

[Ian Wakeling]

Thanks for posting the link - I will take a look at the paper.

Ian

[Ben_J]

You're right - I didn't get your gist the first time. My mistake.

Proof-of-concept with 8-players yields the following:
20 matches where one player has a 2-match break,
13 matches where one player has a 3-match break,
18 matches where one player has a 4-match break,
1 matches where one player has a 5-match break

as compared to my by-hand solution in which:
17 matches where one player has a 2-match break,
21 matches where one player has a 3-match break,
13 matches where one player has a 4-match break,
1 matches where one player has a 5-match break

Beyond that, the solutions are surprisingly similar, structurally, in terms of the 'flow' of who fights who when; suggesting that I was mentally on the right track to begin with.

I'll move forward to work this solution for 10-person pool, and see what comes up.

Thank you again.

[Ben_J]

.....aaaand of course now I'm going back through it - I'm finding mistakes in my work...

most of this by-hand stuff I was working on more than a year ago...

All the more reason to have been looking for algorithms and proper solvers for the problem - fewer mistakes that way.

The solution for 10-players worked perfectly by the way. I am not sure that simply removing matches as suggested to get the odd-player solutions works as well - still testing that now...

[Ian Wakeling]

This is exactly the point of the paper by Warut Suksompong that you have linked to above, we need the construction from Theorem 4.1 to handle an odd number (n) of competitors, then you can guarantee a rest time of (n-3)/2 games.   Figures 4 and 5 in the paper give the schedules for n=5 and n=7 respectively, if I have understood correctly then this is the schedule for n=9 (perhaps you can check it with your spreadsheet):

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

It is intended that these are unravelled from left to right and from top to bottom, but I think if you took these in reverse order it would give you a workable schedule with the 'close' fights at the end.