1
$\begingroup$

I am writing on software that has to create matches between teams of bridge players. Each round a new series of matches is calculated. The algorithm has to meet these two criteria:

  • Each round every teams must meet a team against which it has not played before.
  • The teams that play against each other should have as close a total score as possible.

This method is known as "Swiss teams". Can someone point me in the right direction?

Read some more about the Swiss-tournament system

$\endgroup$
1
  • $\begingroup$ I am not sure if this is a suitable question for cstheory, it seems more appropriate for Stack Overflow. Please see the FAQ to understand the scope of cstheory. $\endgroup$ – Kaveh Dec 4 '11 at 23:25
2
$\begingroup$

Specifically this looks like the Stable Roommate Problem (SRP). Alternate the order of preference based on position in a list sorted by distance from the total score. I.E., imagine a list with the following scores:

1, 3, 18, 19, 20, 21.

Then the preference list would be:

1: 3, 18, 19, 20, 21
3: 1, 18, 19, 20, 21
18: 19, 20, 21, 3, 1
19: 18, 20, 21, 3, 1
20: 19, 21, 18, 3, 1
21: 20, 19, 18, 3, 1

For more accuracy use the Stable Roommate With Ties (SRT) algorithm.

The way Swiss Teams differs from SRP is that not everyone will be listed. That is, if the teams with scores 20 and 18 have played each other already then neither list each other as preferences. It's possible that SRP will still give the correct result but it remains to be verified.

$\endgroup$
2
  • $\begingroup$ Yes, I think this indeed is a stable roommate problem. However, the team with a total score of 18 would have a preference list of: 19,20,21,3,1. Or am I mistaken? $\endgroup$ – Dabblernl Jan 7 '11 at 9:31
  • $\begingroup$ I've modified the initial ordering to be based on distance instead of rank distance. $\endgroup$ – Jonathan Jan 9 '11 at 6:41
1
$\begingroup$

Maybe I’m totally wrong (the Wikipedia article suggests it), but to me this seems like a rather simple graph problem. The parties are the vertices in a graph, an edge’s weight is the difference in total score between the parties corresponding to the adjacent vertices. You start with a complete graph $G$ and search for a perfect (if the number of parties is even) minimum matching $M,$ then remove all edges in $M$ from $G,$ and search for another perfect minimum matching. Repeat these last two steps as often as necessary. Maybe the Wikipedia article on matchings helps.

$\endgroup$
1
  • $\begingroup$ Thank you, I will try to study this. It is entirely baffling to me at the moment, having no knowledge of maths beyond what was taught me at high school ;-) $\endgroup$ – Dabblernl Jan 7 '11 at 9:41

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.