Variants on market matchings: Chess tournament pairings and the stable roommates problem
Eija Kujansuu from the University of Tampere in Tampere, Finland proposes an alternative pairing method for chess tournaments. Although at first glance, generating tournament matchups may appears as simple as pairing individuals of similar ability, the problem is actually more complicated due to further constraints imposed upon the matchups by the Fédération Internationale des Échecs (FIDE). FIDE rules state that whenever possible, players must alternate piece colors between matches (e.g. if player A played black last match, it is preferable for him to play white in the next). Furthermore, FIDE formalizes the concept of “equal ability” through the creation of score groups. Each player’s score is the number of points they’ve accrued in the tournament thus far (1 for a win, 0.5 for a tie, and 0 for a loss), and her score group is the group of players in the tournament with the same score as her. FIDE rules state that whenever possible, players should play a new opponent within their score group. Since it is often impossible to honor all of the guidelines, FIDE places pairing preference on the highest ranked player. A manual pairing of all the players in the tournament using these rules is called the Swiss system. As Kujansuu points out, not only does the Swiss system often result in unfavorable matchups for lower and middle ranked players (who are either forced to play the same color twice in a row or are moved outside of their score group), oftentimes it is true that both players in a matchup are in an unfavorable situation! Kujansuu seeks to fix some of these problems using an alternative pairing system based on the stable roommates problem, which is discussed in further detail in the next paragraph. At a high level, the method works by constructing a preference list for each player in the tournament. The preference list contains the names of players that the player in question would be well-suited to play next. Preference is based on color history compatibility (e.g. A and B are color history compatible if A should play white next match and B black) and score difference. Once the preference lists have been formulated, the problem of chess tournament pairings has been reduced to a canonical instance of the stable roommates problem, and industry-standard algorithms can be used to find the best tournament pairing.
The stable roommates problem (SRP) is a variant of the matching market model discussed in class. Both problems involve dividing people into pairs in the best possible way. The key difference is that unlike a matching market, the SRP does not make a distinction between a group of “buyers” and a group of “sellers”. Instead, everyone belongs to one large group. This means that the definition of optimal is slightly different. In the context of the SRP, a set of pairings from the candidate pool is considered “stable” if there is no pair where both partners prefer a candidate in another pairing over the candidate in their pairing. A short example: suppose (A, B) and (C, D) are paired, and C and D were each other’s top choice. However, A would have preferred to have been paired with C. As long as B is perfectly content, the matching is still stable. But, if B also would have preferred someone else over A, the matching is not stable. Another important difference between the SRP and matching markets is that a solution is not guaranteed to exist for every configuration of the SRP. Efficient (polynomial-time) algorithms exist for the SRP, and these have been used to solve a myriad of situations where people within the same pool must be paired optimally. Kidney exchange and chess tournaments are some examples of applications of the SRP.