Search for a Tie-breaker

LiquidFeedback until Core version 3.0.0 (in its default settings) could only select those initiatives as winner that gained the first Schulze rank. Due to the so-called “chaos theorems” and as explained in the previous article [Chaos], LiquidFeedback's behavior needed to be refined though. Therefore, since LiquidFeedback Core version 3.0.1, initiatives may also win if they gain the second, third, etc. Schulze rank.

As also explained in the previous article [Chaos], ties between those candidates that gain the second, third, etc. Schulze rank may not only arise in corner cases. As a consequence, the approach to solve ties simply by letting that initiative win which was created first (see [PLF, p.101]) must be considered unfair, because initiatives that were created earlier gain an advantage not only in corner cases.

Starting with LiquidFeedback Core 3.0.2, a new mechanism for breaking ties is implemented that considers the order of creation of initiatives only in corner cases. A full description of the algorithm is available in [Schulze, chapter 5, Tie-Breaking]. LiquidFeedback, however, uses a slightly modified version: the “Tie-Breaking Ranking of the Candidates” (TBRC), which is part of Markus Schulze's algorithm, is performed using the initiative creation time instead of picking random ballots. (Picking random ballots electronically would not be verifiable by the voters.)

A short introduction to the algorithm is given below.

Tie-breaking by forbidding shared links

The Schulze method measures the weakest link in the strongest path from one candidate to another candidate. This weakest link determines the strength of the defeat of one candidate over the other. It may happen that the strongest path from candidate A to candidate B shares the same weakest link with the strongest path from candidate B to candidate A. While this seems paradoxical at first, it is indeed possible. Markus Schulze gives an example in [Schulze, p.18]. See Figure 1 through 3.

12 voters prefer A to B to C to D, 6 voters prefer A to D to B to C, 9 voters prefer B to C to D to A, 15 voters prefer C to D to A to B, 21 voters prefer D to B to A to C. A beats B in direct comparison with 33 against 30 votes, A beats C in direct comparison with 39 against 24 votes, B beats C in direct comparison with 48 against 15 votes, C beats D in direct comparison with 36 against 27 votes, D beats A in direct comparison with 45 against 18 votes, D beats B in direct comparison with 42 against 21 votes.

Figure 1: Example given in [Schulze, Example 3] where the Schulze method does not resolve completely: D wins, but A and B are tied in regard of the second rank

The strongest path from A to B is from A to C to D to B, where the link from C to D is weakest: A beats C in direct comparison with 39 against 24 votes, C beats D in direct comparison with 36 against 27 votes, D beats B in direct comparison with 42 against 21 votes.

Figure 2: Strongest beat-path from A to B (A beats C, C beats D, D beats B) has a defeat strength of 36, because C's defeat over D is weakest

The strongest path from B to A is from B to C to D to A, where the link from C to D is weakest: B beats C in direct comparison with 48 against 15 votes, C beats D in direct comparison with 36 against 27 votes, D beats A in direct comparison with 45 against 18 votes,

Figure 3: Strongest beat-path from B to A (B beats C, C beats D, D beats A) also has a defeat strength of 36, because C's defeat over D is weakest

Unless a tie-breaker is used, the Schulze method considers the two candidates A and B to be tied, even if no vote count is equal to another vote count: all numbers are distinct and a single voter preferring A to B or vice versa added to the list of counted ballots wouldn't even change the situation.

Markus Schulze suggests[Schulze, p.58] that for breaking this tie (and only for breaking this tie), the shared weakest link (here: the link from C to D) shall be declared “forbidden” and the strongest paths from A to B and from B to A should be recalculated, ignoring those paths that contain the forbidden link. In the example above, candidate A would be declared winner over B, because A beats B directly with 33 votes, while there is no beat-path from B to A if the link from C to D is forbidden (B beats C, but C doesn't beat A and the link between C and D is forbidden).

A beats B in direct comparison with 33 against 30 votes, A beats C in direct comparison with 39 against 24 votes, B beats C in direct comparison with 48 against 15 votes, the link from C to D is declared forbidden, D beats A in direct comparison with 45 against 18 votes, D beats B in direct comparison with 42 against 21 votes.

Figure 4: Forbidding the shared link

Possible improvements

Unfortunately, Markus Schulze's algorithm requires to create a “tie-breaking ranking of all candidates” (TBRC)[Schulze, p.62] before the algorithm[Schulze, p.58-61] is applied. This tie-breaking ranking of all candidates must be performed regardless of if it has an impact on the result. In the example given in Figure 1, the TBRC has no effect on the winner, but in general it appears difficult to determine whether the TBRC (i.e. the creation order of initiatives in case of LiquidFeedback) has been used to create a unique ranking, or if the final ranking is independent of the TBRC.

Future versions of LiquidFeedback might use an improved algorithm that allows to gather information about whether the creation order of initiatives had an impact on the actual result. Additionally, it might also be better to use directly the creation order of the tied candidates to solve the tie in those cases. Until further mathematical research on this issue is available, LiquidFeedback, however, will default to Markus Schulze's approach as defined in [Schulze, p.58].