2
$\begingroup$

I would like to create a schedule for a set of players to play a tournament. The players are divided into a number of teams, and each round consists of the matches between these teams.

The type of schedule I would like to make should conform to Balanced-Tournament Design. This means:

  • each team plays at each location
    • Sometimes, locations are not always equal. For example, the centre court at Wimbledon. A balanced tournament should let everyone play at every location a fair number of times.
  • each team plays every other team
    • A staple of most round robin tournaments
  • each team is "home" and "away" and equal number of times
    • In team sports, often there needs to be a home and away team. In baseball, for example, the home team gets to bat last in each inning. This can be an advantage, so a balanced tournament should let every team have this opportunity an equal number of times.

I've had a lot of success using Orthogonal Latin Squares and Factored Balanced Tournament Design, and found a decent way to generate such tournaments.

However, I would like to now do something a little different:

  • Players are grouped (e.g. based on skill or position). A team needs one player of each group (e.g. one player of each position or skill level)
  • Each round, the teams and matches are recreated such that
    • The number of times two people play with each other is minimized
    • The number of times two people play against each other is minimized

This is similar to Individual-Pairs tournaments, but in my problem, the teams can have more than 2 players and the players are grouped such that each team requires a player from each group. By changing the teams each round, a single player from each group (e.g. position or skill level) can "win" the tournament by winning more games than any other player.

More formally, this could be described as follows (I am open to changing this notation should anyone have a better way to represent this):

  • There are p players, divided up into g groups, each consisting of t=p/g players.
  • Groups of players are labelled Gi={Pi1, Pi2, ... Pit} where
    • i is the number of the group (0<=i<=g)
    • All players in this group are the same position/skill level, so a team will have exactly one player from each group.
  • Players are labelled Pij where
    • i is the group the player belongs to (0<=i<=g)
    • j is the number of the player within group i (0<=j<=t)
  • The schedule will contain r=t-1 rounds
    • This will let everyone play against everyone else within their group.
  • Each round, t teams and m=t/2 matches must be created
  • Teams are labelled Tij={P1a, P2b, ... Pgc} where
    • i is the round this team is for (0<=i<=r)
    • j is the number of the team within round i(0<=j<=t)
    • Each team consists of exactly one player from each group
  • Matches are labelled Mij={Tia, Tib} where
    • i is the round this match is for (0<=i<=r)
    • j is the number of the match within round i (0<=j<=m)
  • Minimize the following
    • The number of times two players in the same group play together
      • a team can only have one player from each group, so this must be 0
    • The number of times two players in different groups play together
      • Through the course of the tournament, two players shouldn't be on the same team more than once
    • The number of times two players in the same group play against each other
      • Should be exactly 1 if r=t-1
    • The number of times two players in different groups play against each other
      • In my experience, this might have to be twice

Should this prove too complicated, I am more than willing to discuss the more specific case where:

  • each team consists of 4 players (g=4)
  • the number of teams is "low", between 5 and 12 (20 to 48 players)
  • the number of rounds does not need to be t-1.
    • If it is t-1, then a player could (and should) play against all the other players of the same group exactly once. This may not be possible to create, so I would accept a solutions where r is maximized such that a player never plays against another player in the same group more than once (i.e. some players in a group may never play against each other).

While methods dealing generic problem are great, I am most interested in these specific cases since those are what motivated me to look at this problem in more detail.

Thanks!

$\endgroup$
  • $\begingroup$ Earlier today I used an SMT solver to answer a question similar to this one: math.stackexchange.com/questions/452003/…. They're a handly tool for this sort of problem. $\endgroup$ – Daniel Franke Jul 27 '13 at 3:30
  • $\begingroup$ Is there such a solver available for Linux? $\endgroup$ – Trenin Jul 30 '13 at 18:09
  • $\begingroup$ Yes, several. Z3 (what I used in the linked question) has binaries for Linux despite being a Microsoft research project; minion and STP are a couple others that I know of. $\endgroup$ – Daniel Franke Jul 30 '13 at 18:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.