Scheduling: balanced home/away round-robin tournament algorithm

Question

I am trying to achieve a round-robin algorithm for sports scheduling that also guarantees a fair or balanced home/away rotation.

I based my algorithm on the round-robin scheduling algorithm:

def round_robin(teams, rounds):
    # bye
    if len(teams) % 2:
        teams.append(None)

    schedule = []
    for turn in range(rounds):
        pairings = []
        for i in range(len(teams) / 2):
            pairings.append((teams[i], teams[len(teams) - i - 1]))
        teams.insert(1, teams.pop())
        schedule.append(pairings)

    return schedule

However, this algorithm does not address H/A balance. I am trying to satisfy these two objectives:

• H/A rotation: each team should play a home game and an away game every other round, i.e. in a tournament with 5 rounds, a given team should have the following rotation: H-A-H-A-H.

• Number of H/A games: the number of home games and away games should be the same (or offset by one if the total is odd) number, so a tournament with 10 games per team should have 5 home games and 5 away games for each team.

The previous algorithm does not satisfy any of these objectives:

• It does not alternate H/A games. For example, the first team only has home games, and the other teams get home games until they are rotated to the end of the list and then only away games (and the opposite: away games until reaching the beginning, then get home games only). See what I mean below (1).

• It does guarantee a balanced number of H/A games but only if the number of rounds is a multiple of the number of games (or number of games minus one), otherwise we get a number of home or away games too many (the difference between the actual number of games and the next multiple).

(1)

[(1, 8), (2, 7), (3, 6), (4, 5)]
[(1, 7), (8, 6), (2, 5), (3, 4)]
[(1, 6), (7, 5), (8, 4), (2, 3)]
[(1, 5), (6, 4), (7, 3), (8, 2)]
[(1, 4), (5, 3), (6, 2), (7, 8)]
[(1, 3), (4, 2), (5, 8), (6, 7)]
[(1, 2), (3, 8), (4, 7), (5, 6)]

I made several straight forward modifications to get a closer approach to a balanced rotation:

def round_robin(teams, rounds):
    # bye
    if len(teams) % 2:
        teams.append(None)

    schedule = []
    for turn in range(rounds):
        pairings = []
        for i in range(len(teams) / 2):
            pairing = (teams[i], teams[len(teams) - i - 1])
            # alternate first team
            if i == 0 and turn % 2:
                pairing = pairing[::-1]
            # alternate based on the team's previous round appearance
            if schedule and None not in pairing:
                previous_round = list(sum(schedule[-1], ()))
                for team in pairing:
                    if team in previous_round and pairing[previous_round.index(team) % 2] == team:
                        pairing = pairing[::-1]
            pairings.append(pairing)
        teams.insert(1, teams.pop())
        schedule.append(pairings)

    return schedule

But of course this is not a smart algorithm. It helps, but it does not fully satisfy any of both objectives.

I have been trying to find an algorithm that addresses this issue, but I have not been able to find one, quite a surprise because tournament scheduling is a common problem.

I have thoght of using constraint programming to use this problem, but I am not entirely sure this would be the ultimate solution, maybe it is a bit of an overkill and another most classical approach is better. Also, formulating the problem as a constraint programming problem (or CSP) can turn out to be quite a challenge, at least for me.

Any kind of help, suggestion, insight will be most welcome.

Answer 1

I don't think it's possible to strictly satisfy this requirement in a round-robin system:

H/A rotation: each team should play a home game and an away game every other round, i.e. in a tournament with 5 rounds, a given team should have the following rotation: H-A-H-A-H.

Let's say you have a round-robin system where every team takes part in one match each round and every team has a perfectly alternating home-away-schedule. Let A and B be teams that both play at home in the first round. Then they'll be playing at home every odd round and playing away every even round. There will never be a round where A plays at home and B plays away or vice versa. Consequently, if A and B do not share the home location, then A and B will never face each other. The system is flawed.

I think assigning the team location (Home or Away) to the rows of the standard round robin algorithm and alternating them should work reasonably well.

So, for round one (and for each odd round) you would have home teams in the first row and away teams in the second row:

Round 1. (1 plays 14, 2 plays 13, ... )
1  2  3  4  5  6  7 (Home)
14 13 12 11 10 9  8 (Away)

For round two (and for each even round) you would have away teams in the first row and home teams in the second row:

Round 2. (1 plays 13, 14 plays 12, ... )
1  14 2  3  4  5  6 (Away)
13 12 11 10 9  8  7 (Home)

Alternating home and away could be implemented by taking the first algorithm and changing this line

pairings.append((teams[i], teams[len(teams) - i - 1]))

into something like this

if turn % 2:
    home = teams[i]
    away = teams[len(teams) - i - 1])
else:
    home = teams[len(teams) - i - 1])
    away = teams[i]
pairings.append((home, away))

Answer 2

I ended up going with something like this. Deff could use some cleanup and de-duplication.

import collections
teams = [1, 2, 3, 4, 5, 6, 7, 8, 9]
rounds = 8
schedule = []

teams.insert(0, None)
d = collections.deque(teams)
dl = list(collections.deque(d))
pl = list(zip(dl[::2], dl[1::2]))
schedule.append(pl)

for turn in range(rounds):
    d.rotate(1)
    # Swap bye week back to top
    d[1] = d[0]
    d[0] = None
    dl = list(collections.deque(d))
    pl = list(zip(dl[::2], dl[1::2]))

    schedule.append(pl)

print(schedule)

Output seems sane:

[(None, 1), (2, 3), (4, 5), (6, 7), (8, 9)], 
[(None, 9), (1, 2), (3, 4), (5, 6), (7, 8)], 
[(None, 8), (9, 1), (2, 3), (4, 5), (6, 7)], 
[(None, 7), (8, 9), (1, 2), (3, 4), (5, 6)], 
[(None, 6), (7, 8), (9, 1), (2, 3), (4, 5)], 
[(None, 5), (6, 7), (8, 9), (1, 2), (3, 4)], 
[(None, 4), (5, 6), (7, 8), (9, 1), (2, 3)], 
[(None, 3), (4, 5), (6, 7), (8, 9), (1, 2)], 
[(None, 2), (3, 4), (5, 6), (7, 8), (9, 1)],