[EM] Could a single specially-crafted new vote resolve all ties in a Shulze election?

[Kristofer Munsterhjelm]

Scott Ritchie wrote:

> Anyway, I'd like to prevent problems in the future, so:
> 1) Endorse an algorithm.  I've already decided on Shulze, since that's
> what Debian uses and they're our sister project.
> 2) Create a formal tie-breaking rule.  My intuition says that we can
> give Mark Shuttleworth (who already has special privileges) a second
> vote that he only uses in the case of a tie, add that vote to the box,
> and then rerun the election.
> 
> However, I'm not 100% sure that a regular vote cast in the CIVS sense
> will actually resolve ties cleanly.  So, I'm asking the list:
> 
> Suppose we have a tie among {A,B} for the marginal seat in an election.
>  Would a vote for A > B that expressed no other preferences always
> result in an identical overall ranking except with a resolved tie?
> 
> If the tie is larger (or number of marginal seats larger), could he
> similarly vote {A>B=C} or {A=B>C} to resolve them?
> 
> Could either vote affect the non-marginal seat order?  Shuffling the
> above winners, provided they all still win, isn't much of a problem,
> however shuffling the losers might be an issue since we use the list
> order for replacement candidates when someone steps down mid-term.

It might not resolve the actual tie itself, and it could produce further 
ties. The Schulze method uses a strongest path calculation, which means 
that (unless I'm mistaken) some contests can be changed without 
affecting the result.

This is analogous to the minmax method, which Schulze is based on, and 
which considers the worst defeat by any opponent, electing the candidate 
whose worst defeat is the least. If you have two candidates, call them A 
and B, and their worst defeat is against X and Y respectively, then no 
ballot that ranks both X and Y above (or below) both A and B will 
resolve the tie, because it alters both worst defeats by the same 
amount. For Schulze, it's a bit more complex, but the same reasoning holds.

My educated guess is that Schulze is considerably less likely to produce 
more ties in this case than it is likely to simply retain the ties that 
do exist, and it is more likely still to actually resolve the tie while 
not producing any more ties.

-

You could break the ties in a simple way by just using Mark's ballot 
directly. If there's a tie between A and B, then you check if Mark voted 
A above B or vice versa, and the candidate he voted highest wins. You 
can do the same thing with multiple candidates: if there's a tie between 
A, B, and C, and Mark's vote (over A, B, and C alone) is A>B>C, then A 
wins, B comes second, and C third.

If that still doesn't resolve the tie, pick a random ballot and break 
ties as shown above. Do so until the tie is broken or all the ballots 
have been exhausted. If there's still a tie, that means nobody voted A>B 
or B>A, so flip a coin. This is called the Random Voter Hierarchy 
tiebreaker.

Also, I may be wrong about the subtleties of Schulze. I don't *think* I 
am, but if you want to be sure, you might want to ask Markus Schulze 
himself (if he doesn't see our posts and replies to either of them).