Selecting pairs of teams to play each round, with maximum exposure before repeats

Question

I'm writing a sports schedule generator. Given T teams (an even number), G games per round (a multiple of T/2), and R rounds I want to generate a schedule matching the criteria:

1. All teams play the same number of games in the round.
2. Team combinations are fully exhausted before they are repeated.

I have an algorithm that works most of the time, but not always. It is detailed at the end of this question. How can I fix (or replace) this algorithm to robustly work for all reasonable inputs?

This question is similar to Sorting pairs of teams with non-repeating | Round-robin tournament and Algorithm: Selecting pairs of teams from a set of games but has distinct requirements.

---

For example, assume there are T=4 teams. This gives us 6 possible games:

(T0,T1)  (T0,T2)  (T0,T3)  (T1,T2)  (T1,T3)  (T2,T3)

If there are G=4 games per round, then the first round must not be this set of games…

(T0,T1)  (T0,T2)  (T0,T3)  (T1,T2)

…because T0 gets to play 3 times, but T3 only gets to play once (a violation of requirement #1). Instead, the first round might look like this, where every team gets to play two games:

(T0,T1)  (T2,T3)  (T0,T2)  (T1,T3)

If that same set of games were repeated for the second round, then the two games (T1,T2) and (T0,T3) would never take place (a violation of requirement #2). So, we want to ensure that they are included in the second round before we pick up new games. A valid schedule for T=4, G=4, R=5 would be:

(T0,T1)  (T2,T3)  (T0,T2)  (T1,T3)
(T0,T3)  (T1,T2)  (T0,T1)  (T2,T3)
(T0,T2)  (T1,T3)  (T0,T3)  (T1,T2)
(T0,T1)  (T2,T3)  (T0,T2)  (T1,T3)
(T0,T3)  (T1,T2)  (T0,T1)  (T2,T3)

As seen, for large values of R it is acceptable for the set of games in a round to be repeated eventually.

---

The algorithm I have works like so:

• Calculate all unique pairwise combinations of teams (the possible games). Save this list as currentPool.
• Create an empty list, named otherPool.
• For each round, G times perform the following:
  • Find the game in currentPool with the lowest sum when adding together the number of times each team in the game has been seen in this round.
  • Add the game to the round.
  • Move the game from the currentPool to the otherPool.
    • If currentPool is empty, swap currentPool and otherPool.

For many reasonable values of T, G, and R this algorithm works. However, there are some combinations that fail. For example, with T=6, G=3, R=5, it generates this schedule:

(T0,T1)  (T2,T3)  (T4,T5)
(T0,T2)  (T1,T3)  (T0,T4)
(T0,T3)  (T1,T2)  (T0,T5)
(T1,T4)  (T2,T5)  (T3,T4)
(T1,T5)  (T2,T4)  (T3,T5)

The first round is correct, but in the second round T0 plays twice and T5 never gets to play. The problem is easy to spot—after picking (T0,T2) and (T1,T3) in round 2 the only game that is possible to satisfy requirement #1 would be (T4,T5), but that game was already used in the first round and per requirement #2 cannot be re-used until all 15 unique games are used up. The algorithm started down a dead-end and had no way to back track.

---

Finally, for completeness here is a JavaScript version of the algorithm described. Here's sample output of a successful run:

let schedule = singleFieldSchedule({
    teams            : 8,
    maxGamesPerRound : 12,
    rounds           : 8
})
console.log(schedule.map(round => round.map(game => `(T${game[0]},T${game[1]})`).join('  ')).join('\n') )

(T0,T1) (T2,T3) (T4,T5) (T6,T7) (T0,T2) (T1,T3) (T4,T6) (T5,T7) (T0,T3) (T1,T2) (T4,T7) (T5,T6)
(T0,T4) (T1,T5) (T2,T6) (T3,T7) (T0,T5) (T1,T4) (T2,T7) (T3,T6) (T0,T6) (T1,T7) (T2,T4) (T3,T5)
(T0,T7) (T1,T6) (T2,T5) (T3,T4) (T0,T1) (T2,T3) (T4,T5) (T6,T7) (T0,T2) (T1,T3) (T4,T6) (T5,T7)
(T0,T3) (T1,T2) (T4,T7) (T5,T6) (T0,T4) (T1,T5) (T2,T6) (T3,T7) (T0,T5) (T1,T4) (T2,T7) (T3,T6)
(T0,T6) (T1,T7) (T2,T4) (T3,T5) (T0,T7) (T1,T6) (T2,T5) (T3,T4) (T0,T1) (T2,T3) (T4,T5) (T6,T7)
(T0,T2) (T1,T3) (T4,T6) (T5,T7) (T0,T3) (T1,T2) (T4,T7) (T5,T6) (T0,T4) (T1,T5) (T2,T6) (T3,T7)
(T0,T5) (T1,T4) (T2,T7) (T3,T6) (T0,T6) (T1,T7) (T2,T4) (T3,T5) (T0,T7) (T1,T6) (T2,T5) (T3,T4)
(T0,T1) (T2,T3) (T4,T5) (T6,T7) (T0,T2) (T1,T3) (T4,T6) (T5,T7) (T0,T3) (T1,T2) (T4,T7) (T5,T6)

function singleFieldSchedule({teams=8, maxGamesPerRound=12, rounds=8}={}) {
    const uniquePairs = a => a.reduce((res,o1,i,a) => res.concat(a.slice(i+1).map(o2 => [o1,o2])), [])
    const teamNames = Array.from(Array(teams).keys())
    const fullExposure = uniquePairs(teamNames)
    const zeroTeamCounts = teamNames.map(n => [n,0])

    // Calculate how many games can be played by each team while keeping things fair
    const gamesPerTeam = Math.floor(maxGamesPerRound / teams * 2)
    const gamesPerRound = gamesPerTeam * teams/2    

    const schedule = []

    const pools = [fullExposure, []]
    let poolIndex = 0
    for (let r=0; r<rounds; ++r) {
        const round = []
        schedule.push(round)
        const gamesPerTeam = new Map(zeroTeamCounts)
        for (let g=0; g<gamesPerRound; ++g) {
            let pool = pools[poolIndex]
            if (!pool.length) pool = pools[poolIndex=((poolIndex+1)%2)]

            // Find the game whose teams have been seen the least
            let bestGameSum = Infinity
            let bestGameIndex
            for (i=0; i<pool.length; ++i) {
                const game = pool[i];
                // We square the times seen to favor a game where each team has been seen once
                // over a game where one team has been seen twice and the other team has never been seen
                const gameSum = gamesPerTeam.get(game[0])**2 + gamesPerTeam.get(game[1])**2
                if (gameSum < bestGameSum) {
                    bestGameSum = gameSum
                    bestGameIndex = i
                }
            }
            let bestGame = pool.splice(bestGameIndex, 1)[0]
            round.push(bestGame)
            gamesPerTeam.set(bestGame[0], gamesPerTeam.get(bestGame[0])+1);
            gamesPerTeam.set(bestGame[1], gamesPerTeam.get(bestGame[1])+1);

            // Put this game into the 'other' pool, to be used once this pool of games is used up
            pools[(poolIndex+1) % 2].push(bestGame)
        }

        // Check to see if any team got screwed this round
        const shortedTeams = teamNames.filter(t => gamesPerTeam.get(t)<gamesPerTeam)
        shortedTeams.forEach( t => {
            const ct = gamesPerTeam.get(t)
            console.warn(`Team ${t} only got to play ${ct}/${gamesPerTeam} games in round #${r}`)
        })
    }

    return schedule
}

Answer 1

In graph terms, the set of all games possible by all teams is a "complete graph", that is, a graph with one vertex per team with edges connecting every pair of teams.

            Complete graphs for T=6 and T=8

Finding pairs of games where all teams play exactly once is finding a "perfect matching" of the graph: finding edges that touch every vertex, with no vertex being touched by more than one edge.

            Example perfect matches for T=6 and T=8

Ensuring that all possible games are played—finding a set of "perfect matches" that uniquely select every edge—is a 1-factorization of the graph. Following are two different 1-factorizations of the T=6 and T=8 cases. The first of each was hand-created, while the second uses the round-robin algorithm described in the accepted answer.

Given the ability to generate any single 1-factorization for the graph, the problem is solved as following:

1. Create a 1-factorization of the complete graph representing the number of teams.
2. Calculate the number of times a single team plays per round N as 2*G/T.
3. For each round, select N perfect matches from the 1-factorization and use those edges as the games to play that round.
   • On subsequent rounds, use subsequent perfect matches, such that those not used in the first round will be used later.
   • Once all perfect matches have been used up, repeat the selection of perfect matches.

There is no requirement to calculate all 1-factorizations. Doing so would provide variety not experienced by players on the teams. For example, above the two 1-factorizations for T=6 show different perfect matches in the case where team A plays team F. However, while teams A and F are playing each other they are likely unaffected by whether team B is playing team D or team C.

---

A JavaScript version of this algorithm follows:

// Calculate a round-robin schedule using the 'circle' algorithm
// https://en.wikipedia.org/wiki/Round-robin_tournament#Scheduling_algorithm
function roundRobin(teams) {
    const loop = Array.from(Array(teams).keys())
    const rounds = []
    for (let i=0; i<(teams-1); ++i) {
        const round = []
        for (let j=0; j<teams/2; ++j) {
            round.push([loop[j], loop[teams-j-1]].sort())
        }
        loop.splice(1, 0, loop.pop()) // rotate the 'table'
        rounds.push(round)
    }
    return rounds
}

// Play multiple rounds of a round-robin tournament per a single 'round',
// while ensuring that every team plays the same number of games each round,
// and that every team plays every other team as soon as possible.
function multiGameRobin({teams=8, maxGamesPerRound=12, rounds=8}={}) {
    if (teams%2) console.error('number of teams must be even')
    const subrounds = roundRobin(teams)
    const gamesPerTeam = Math.floor(maxGamesPerRound / teams * 2)
    const schedule = []
    for (let r=0; r<rounds; ++r) {
        let round = []
        for (let i=0; i<gamesPerTeam; ++i) {
            round = round.concat(subrounds[(r*gamesPerTeam+i) % subrounds.length])
        }
        schedule[r] = round
    }

    return schedule
}

---

What may be interesting—though not a requirement from the original question—is to provide different combinations of perfect matches in subsequent rounds. For example, for T=6 there are 5 different perfect matches, which we might call PM1, PM2, PM3, PM4, and PM5. If in round 1 we use PM1, PM2, and PM3, in round 6 we might use PM1, PM3, and PM5 instead to provide even more variety, so that it is not a direct repeat of the games in round 1.

Answer 2

Lay out a standard round-robin schedule. Then merely take the pairings in order for the quantity of matches you want for each of your rounds.

"The standard schedule" pairs up the teams and rotates all but the first team for each round. For six teams, the schedule looks like this; pairings are adjacent vertically:

0 1 2
5 4 3

0 5 1
4 3 2

0 4 5
3 2 1

0 3 4
2 1 5

0 2 3
1 5 4

There it is: five rounds, each team playing each other team exactly once.

If you have an odd quantity of teams, then designate team 0 as the "bye".

If you need rounds of 6 matches, simply pick them in the order given above, left-to-right in each row:

0-5  1-4  2-3  0-4  5-3  1-2 
0-3  4-2  5-1  ... etc.

With 2N teams in the league, the lag between matches is N-1, N, or N+1 matches.

Answer 3

I don't have a theoretically perfect solution, but I have a polynomial time approach that should work better.

The heart of it is the Blossom Algorithm for maximal matchings. In each round, use that with edges representing as yet unplayed games. This will more more likely to find valid solutions of the simple cases that can fail with your current algorithm. In particular you have guaranteed that teams cannot play 2 games in a round, and as many unused games as possible get used.

But we can improve on this by noting that we can use a variation to find maximal weight matchings. If you make the weight of each edge be G^i where G is the number of games played and i is the number of rounds since a particular game was played last, then teams cannot play 2 games in a round, and we play with as many games as old possible.

This algorithm guarantees your first condition, and makes a good faith effort to do well by your second. But it does not guarantee the second. (However if you do have early repeats, they will be pretty well spread out.)

If you have a large number of rounds, you can play around with the weight condition to make sure that each one is used on average the right number of times.