Maximum Weight Perfect Matching

Maximum Weight Perfect Matching is a graph algorithm used in pairing programs.

In graph theory, a graph is represented as a set of vertices (points), which may be connected by edges (lines).

Here, we only consider undirected edges. This means that we do not distinguish between an edge from A to B and an edge from B to A - they are the same edge.

A graph is complete if every pair of vertices is connected by an edge.

A matching is a set of edges in the graph which do not share any vertices.

A matching is perfect if it covers all vertices.

For a tournament event, we can construct a complete graph where the participants are represented as vertices, and the possible games between them as edges. Then if the number of participants is even, then a perfect matching on this graph is a pairing. Since every vertex is covered, every player has a game. And since no vertex is shared, no player is playing two games at the same time. (If the number of participants is odd, a BYE is added as an extra virtual player to make a perfect matching possible.)

If we give each edge (possible game) a weight, representing how desirable that game is, then a maximum weight perfect matching is a pairing where the sum of the desirabilities of all the games is maximized. Theoretically, this is a pairing that is better than any other pairing (or at least just as good).

There exist well-researched algorithms for finding maximum weight perfect matchings in a reasonable amount of time (i.e., without trying every possible pairing). So if a program can set reasonable weights for each potential game, it can then use such an algorithm to find a good pairing.

Setting weights for each game generally considers the following factors:

Previous pairing: If the players have already met, it is extremely undesirable to pair them again.
McMahon/Swiss score: If the players have different scores, the undesirability grows with the difference in points
In group placement: The desirability depends on our group pairing strategy (fold, slide, etc)
Color balance: A game is more desirable if both players can get a color they haven't played with much.
Same origin: Players from the same club/country may prefer playing people they don't meet every week (this is generally not use in the top of the tournament).

Exact calculation of the relative importance of the above is up to the writer of the pairing program, and is sometimes configurable.

Note that the maximum weight perfect matching algorithm can be applied on graphs that are not complete (e.g., when edges are removed from players who have already played with each other), assuming that a perfect matching exists. However, some pairing programs, such as the MacMahon pairing program, only operate on complete graphs. The difference is somewhat academic though, as we can construct a complete graph from an incomplete graph by adding edges with very low weights (e.g., negative infinity).

[edit]

Maximum Weight Perfect Matching

See also: