Round Robin Tournament Scheduling

coed social square

ryryguy · 7 · 4585

ryryguy

  • Newbie
  • *
    • Posts: 4
on: August 15, 2012, 01:27:36 PM
Hi, a friend has requested help doing a schedule for a "mix-up" volleyball tournament.  I'm a programmer and want to try to throw together a web page to generate the schedule.

It's basically a 4x4 "social square", but with the additional constraint that the teams must be co-ed. I've briefly scanned Richard's pages about this, but haven't had a chance to dig in seriously yet.  But it seems like his algorithm should work except for the co-ed constraint.  Has anyone got an algorithm that deals with that constraint, or got a hint?  (If someone has or can quickly generate the schedule for me, that would work too!  :D )

8 guys
8 gals
Teams of 4 coed 2 guys and 2 gals
2 courts at a time
Ten rounds (*edit*: in other words, 20 total games (10 rounds x 2 courts), with each player playing 10 times.)

edit: clarification of number of games.
« Last Edit: August 16, 2012, 02:01:24 AM by ryryguy »


ryryguy

  • Newbie
  • *
    • Posts: 4
Reply #1 on: August 15, 2012, 01:54:06 PM
Having had a moment to look a bit more at the social square notes, I see another difference.  For the volleyball tournament, the goal is to maximize the unique combinations of both teammates and opponents.  If I'm reading it right, the "pure" social square is just about unique combinations of teammates.  For the volleyball tournament, for a given player we want to see the same players on either side of the net as few times as possible.  It's probably not possible to get that perfectly balanced but as close as we can come.


Ian Wakeling

  • Forum Moderator
  • God Member
  • *****
    • Posts: 1141
Reply #2 on: August 16, 2012, 04:19:13 AM
You are right about the social square, these are not going to help you - but if you do need those then they can be generated with some combinatorial math, search for more info on design theory and affine planes.

The bad news is that I don't have any way of generating a schedule for your volleyball mix-up and it will be a real monster to design an algorithm for balancing it.  You would need to break it down as follows, there are:

56 possible same-sex pairs on the same team
64 possible opposite-sex pairs on the same team
56 possible same-sex pairs on opposing teams
64 possible opposite-sex pairs on opposing teams

Starting with a random schedule, count up the frequency of all the pairs above and then look for changes to the schedule which improve the pairwise balance as a whole.  So an iterative improvement approach may work, or alternatively it may be possible to optimize everything using a constraint programming approach. Either way it will likely take a lot of CPU.

Hope that helps.


ryryguy

  • Newbie
  • *
    • Posts: 4
Reply #3 on: August 16, 2012, 11:57:02 AM
Thanks Ian.  I hadn't thought of an iterative approach like you describe, that is interesting.

Maybe I'll be able to figure something out for next year - my friend should have asked me to help earlier than 3 days ahead of the tournament.   ;D  If I do come up with something I'll post it here.

Thanks again.


Richard A. DeVenezias

  • Forum Administrator
  • Full Member
  • *****
    • Posts: 45
Reply #4 on: August 16, 2012, 12:39:59 PM
This plan may work for you.  Females are even numbered and Males odd.

round      team1      team2      team3      team4

1      (16,2,3,5)      (10,15,6,9)      (4,11,13,14)      (7,1,8,12)
2      (16,12,13,15)      (5,10,1,4)      (14,6,3,7)      (2,11,8,9)
3      (16,4,5,7)      (12,2,15,1)      (6,13,8,11)      (9,3,10,14)
4      (16,7,11,14)      (8,10,15,5)      (9,1,12,6)      (3,4,13,2)
5      (16,14,5,9)      (15,2,3,6)      (1,8,10,11)      (4,13,7,12)
6      (16,3,7,10)      (4,6,11,1)      (5,12,14,15)      (8,2,9,13)
7      (16,9,2,7)      (10,12,13,1)      (11,3,14,8)      (5,6,15,4)
8      (16,5,9,12)      (6,8,13,3)      (7,14,1,2)      (10,4,11,15)
9      (16,11,4,9)      (12,14,15,3)      (13,5,2,6)      (1,10,7,8)
10      (16,13,6,11)      (14,1,2,5)      (15,7,4,8)      (3,12,9,10)

There are 78 pairs with repeats. 40 occur twice, 28 thrice and 10 four times.  17 pairs are repeats as opponents-only, 17 as teammates-only and 44 split between as mate and opponent.
6 pairs (out of 120 possible) never occur.

It was derived from the 16-player Whist schedule and popped out after running through some combinatoric and balancing transformations.
« Last Edit: August 16, 2012, 12:45:41 PM by admin »
The Administrator.


Ian Wakeling

  • Forum Moderator
  • God Member
  • *****
    • Posts: 1141
Reply #5 on: August 16, 2012, 01:18:05 PM
Richard,

Do you intend that team1 always plays team 2, and team 3 against team 4 in each round?

Ian.


ryryguy

  • Newbie
  • *
    • Posts: 4
Reply #6 on: August 16, 2012, 06:30:16 PM
Richard - thanks a lot!  I think we can use that.  Even if not as balanced as it could possibly be I think it's a lot better than what they've used in years past.  (This is an annual tournament.)

 :)