WSDC Pairing as a Minimum Cost Perfect Matching

[tienne-B]

Andrew Chen
October 2024

Introduction

The Procedures for Power-Pairing at the World Schools Debating Championships provides a number of considerations for pairing teams at WSDC. The considerations are:

• Power-pairing (3.3-3.4)
• Pull-ups to be taken from the bracket immediately below where possible (3.5), teams not be pulled up more than once where possible (3.6), pullups to have weakest draw strength by opponents’ rank where possible (3.7)
• Brackets to be folded (3.8)
• A hard constraint against history (3.9)
• Overall side balance, which becomes a hard constraint beyond 5-3 (3.10)
• Prepared and impromptu side balance, which becomes a hard constraint beyond 3-1 (3.11)

The considerations often conflict, and the document does not prescribe a procedure for resolving such conflicts. Nonetheless, there has been consensus at recent WSDCs on how to do so:

1. Determine pullups, choosing the team in the bracket immediately below that has the weakest draw strength by opponents’ rank, has not been pulled up already (unless all teams in the bracket have been), and would not make pairing the bracket they are pulled up into impossible due to history (or hard side constraints - practically, a non-occurrence).
2. Fold brackets, making minimal adjustments for history and hard side constraints only.
3. For each matchup, allocate sides to optimise overall and then prepared/impromptu side balance.

Software/Tabbycat does not support this, in large part due to unusual situations that can arise with small probability (e.g. after 7 rounds, the one team on 7 having debated all teams on 6, requiring a pullup from the 5 bracket). Consequently, this has been carried out manually, requiring some effort and technical competence/understanding.

Software being able to generate WSDC-complaint draws is desirable, for convenience and to avoid human error. I present an algorithm for doing so as a minimum cost perfect matching problem.

The minimum cost perfect matching problem is, given a graph $G=(V,E)$ in which each edge has a weight, to find the perfect matching (a collection of edges such that each vertex is incident to exactly one edge) that minimises the total cost of the edges in the matching. We make generating a draw a minimum cost perfect matching problem as follows:

• Each team is a vertex.
• Each edge has a cost as described below.

The minimum cost perfect matching problem is solved with ‘efficient’ algorithms, e.g. Blossom algorithm (which runs in polynomial time). Interestingly, Tabbycat already offers minimum cost perfect matching via Blossom algorithm to solve conflicts within brackets for APDA.

Edge Costs

In the following,

• $M$ is the number of rounds (at WSDC, 8)
• $N$ is the number of teams
• $Inf$ is a large number, $M^4 N^8)$ is satisfactory.
• $A$ and $B$ represent 2 general vertices

History (Hard)

• Cost: $Inf$ if $A$ and $B$ have met before (history)

Power Pairing

• Cost: $|TeamPoints_A - TeamPoints_B|$
• Multiplier: $M^3 N^7$
• Range: $(0, M) \times M^3 N^7$ for one edge, $(0, \frac{MN}{2}) \times M^3 N^7$ for all $\frac{N}{2}$ edges
• Min. increment: $M^3 N^7$

Pullups

Pull up from teams who have had been pulled up the fewest times so far:

• Cost: $nPullups_A + nPullups_B$
• Multiplier: $1.25 M^2 N^6$
• Range: $(0, M)*1.25 M^2 N^6$ for one edge, $(0, \frac{MN}{2}) \times 1.25 M^2 N^6$ for all $\frac{N}{2}$ edges
• Min increment: $1.25 M^2 N^6$

Weakest draw strength by opponent rank:

• Cost: if A has been pulled up, -sum(OpponentRanks_A) + analogously for B
• Multiplier: $2.5MN^4$
• Effect: pulls up eligible team with weakest draw strength by opponent rank
• Range: $(-MN, 0) \times 2.5MN^4$ for one edge, $(-0.5MN^2, 0) \times 2.5MN^4$ for all $\frac{N}{2}$ edges
• Min. increment: 2.5mn^4

Fold

• Cost: $-(rank_A - rank_B)^2$
• Multiplier: $5MN$
• Effect: folds
• Comment: has the desired effect because the sum of squared differences is maximised by pairing off highest-lowest greedily. Constrained to doing so within brackets by above. Is neutral on whether to one-up-one-down above or below when there is history (though "remembers" pullups).
• Range: $(-N^2, 0) \times 5MN$ for one edge, $(-0.5N^3, 0) \times 5MN$ for all n/2 edges.
• Min. increment: $5MN$

Side Balance

Calculate cost for both possible allocations ($Prop_A, Opp_B$ and $Opp_A, Prop_B$), take the smaller of the two, which becomes the side allocation.

Overall side balance (hard)

• Cost: $Inf$ if $A$ or $B$ exceeds max no. prop/opp (WSDC: 5)
• Effect: enforces hard overall side balance constraint (WSDC: max 5), but not pre-emptively.

Overall side balance (soft)

• Cost: $(nProp_A - nOpp_A) \times (1 if A on Prop; -1 if A on Opp)$ + analogously for B.
• Multiplier: 1.5
• Effect: overall side balance
• Comment: Multiplier of 1.5 is not fixed. It provides a mild, but not total, preference for overall side balance over prepared/impromptu side balance.
• Range: $(-M, M) \times 1.5$ for each team, $(-MN, MN) \times 1.5$ for all teams
• Min. increment: 1.5

Impromptu side balance (hard)

• Cost: for impromptu rounds only, $Inf$ if $A$ or $B$ exceeds max no. prop/opp
• Effect: enforces hard impromptu side balance constraint (WSDC: max 3), but not pre-emptively.

Impromptu side balance (soft)

• Cost: for impromptu rounds only, $(nPrepProp_A - nPrepOpp_A) \times (1 if A on Prop; -1 if A on Opp)$ + analogously for B.
• Multiplier: 1
• Effect: impromptu side balance
• Range: $(-M, M)$ for each team, $(-MN, MN)$ for all teams
• Min. increment: 1

Prepared side balance (hard)

• Analogously to above
• Comment: constraint cannot be violated under current WDSC pairing rules owing to R1 and R2 being prepared and pre-drawn with teams taking opposite sides.

Prepared side balance (soft)

• Analogously to above

Random Number

• Cost: $x_{AB}$, where $x_{AB}$ is a random number between 0 and 1.
• Multiplier: $\frac{2}{n}$
• Effect: If there are multiple matchings that are otherwise equal cost (very unlikely), choose one of them at random.
• Range: $(0, \frac{2}{n})$ for one edge, $(0, 1)$ for all \frac{n}{2} edges.
• Min increment: 0

The cost of edge AB is the sum of all costs (in blue) above, each multiplied by their multiplier.

[teymour-aldridge]

I guess this would require a separate draw generator class for WSDC?

[tienne-B]

@teymour-aldridge I haven't completely planned this out yet, but I'm hoping that it won't be needed. We already have a Blossom algorithm-based draw generator for random and power-paired rounds, and should only need to adapt/add the constraint calculations that we don't currently have, such as the hard side constraint or draw strength by rank.

[tienne-B]

I think the plan for this can be split into a few discrete tasks:

• Create pullup resolution method on average opponent ranking #2445
• Create penalty preference in Draw Rules for:
  • Preferring teams within a bracket
  • Preferring pulling up teams by the ordering in the "Odd bracket resolution method"
  • Preferring to pull up teams that meet the pullup restriction
• Implement these penalties within the power-pairing (and some for random) draw generators
• Rather than run Blossom on each bracket, run on the entire draw

Side balance would still need some thought, and for how to not create edges for Inf weights.