Swiss tournament - pairing algorithm

Question

I am working on a Swiss Tournament system in Python and I'm trying to figure out an optimal pairing algorithm.
My biggest problem is that every algorithm I came with produced error in few sequences, where the last pair to be picked have already played each other, ruling the pairing is invalid.

The Swiss system I'm working on is simple: even players, everyone plays at each round and pairing is done based on the winning proximity (so strong players play against strong players, and weak against weak).
No Bye, only win/lose (no draw), opponents cannot play each other twice.

The current algorithm I did works as follow:

1. Produce a players list by ranking order (most wins to least wins)
2. Pick player, starting from player with most wins
3. Match him with the closest ranked player. If they already played, match him with the next one, until a match is found
4. Pop the pair out of the list and back to 1

For example:
Ranking after 2 rounds:

1. P1: [P2 win, P3 win] 2 wins
2. P5: [P6 win, P2 win] 2 wins
3. P3: [P4 win, P1 lost] 1 win, 1 loss
4. P4: [P6 win, P3 lost] 1 win, 1 loss
5. P2: [P1 lost, P5 lost] 2 losses
6. P6: [P5 lost, P4 lost] 2 losses

First pick would be P1 and the first match is P5. Taking (P1,P5) out of the list.

1. P3: [P4 win, P1 lost] 1 win, 1 loss
2. P4: [P6 win, P3 lost] 1 win, 1 loss
3. P2: [P1 lost, P5 lost] 2 losses
4. P6: [P5 lost, P4 lost] 2 losses

First pick would be P3, already played P4, so the match would be P2. Taking (P3,P2) out of the list.
In this sequence I finish with a pair that played against each other and the pairing is invalid:

1. P4: [P6 win, P3 lost] 1 win, 1 loss
2. P6: [P5 lost, P4 lost] 2 losses

---

Question: Is there any algorithm that guarantees an optimal pairing module while making sure I do not get 'stuck' at the end with two players who played each other?

Answer 1

Maybe I could help you with that. In chess we have different Swiss pairing algorithms but they all work with a strong-weak pairing (there can be surprises).

The basic principle of the Dutch one (the most used) is that, once you have assigned your pairing numbers, you apply the algorithm for each score bracket.

The algorithm works roughly as follows:

In the first score bracket, pick (about) half the players and place them in a sub-group and place the other players in an other sub-group. If the players are compatible, then pair them together. If they are not compatible, try swapping players in the second sub-group. If no pairings are compatible, exchange players between subgroups. If there were an odd number of players in the bracket, one will float down.

In the next score bracket: If there are floaters, pair them first. Then, do the same thing as previously with residual group.

Some more rules are added to be sure that there IS at least one pairing possible.

For example : if no exchanges are able to make a good enough pairing, backtrack to the previous score bracket and break the pairing to make floaters.

This is a really rough explanation of the Dutch pairing system, but that was my go at your question.

Answer 2

A brute force algorithm would be guaranteed to find an optimal pairing module, if there is one:

1. Define penalty function for a pairing (probably the difference of wins of the paired players)
2. Based on this, define a penalty function for pairing modules (maybe the sum of squares of the respective penalty values of the pairings in the module)
3. Enumerate all valid modules (note that there might be none)
4. For each valid module, compute the module penalty value according to (2.)
5. Sort by this value and choose the (one of) module(s) with the smallest penalty value. (The minimum might be shared by several.)

For a small number of players, this might even result in feasible runtimes. For a larger number, you'd want to look into optimizations and shortcuts.

Answer 3

I had the same question some time ago and ended up building a solution using a minimum weight maximum matching algorithm in python. There's even a nice library for this! https://healthyalgorithms.com/2009/03/23/aco-in-python-minimum-weight-perfect-matchings-aka-matching-algorithms-and-reproductive-health-part-4/

I wrote out my thought process in a blog post and made sure to link to the resources I used while building it. Hopefully this is helpful: https://www.leaguevine.com/blog/18/swiss-tournament-scheduling-leaguevines-new-algorithm/

Answer 4

I had the same problem and solved it in the following way.

1. I have separated the ranking in the middle into two groups

2. For each group: a. Create a matrix with the players, in row and column b. Assign a high cost (eg: 10000) for forbidden pairs (eg: already played, dummy player in case of odd number of players) c. Assign a "performance" value for all other pairs, for example based on the number of points earnt and lost d. Find all the possible matches, only in the half part of the matrix since it is a mirror. Sum the "performance value" of this solution e. Skip pairs with cost > 10000 f. Sort the list of solutions, take the lowest sum entry

3. If there is no solution, then re-do the same algorithm without splitting the players.

There is always an optimal solution only if the number of turns is kept controled. For example, for 20 players, the optimal number of rounds is 5, more may be dangerous (no any solution is found).

I have implemented this algorithm in C++ and tested in the field for a real tournament, it works great. You can find it on Github in the Tanca repository, in the file named "Tournament.cpp".

I have also written an article on my blog (in french, sorry).