Further notes and examples.

Case 1

Can be seen in round 12.

SecurePoll

• Lowest candidate = 82 votes
• Second lowest = 83 votes
• Surplus = ~0.9

So candidates 9, 10, 11 and 12 are eliminated.

OpenSTV

• Lowest candidate = 82 votes
• Second lowest = 83 votes
• Surplus = 0.002348

First candidate eliminated in round 49, because there was no change in surplus between rounds 48 and 47.

Case 2

Can be seen in round 13.

SecurePoll

• Lowest candidate = 83
• Second lowest candidate = none
• Surplus = ~263

Candidates 13-20 eliminated.

OpenSTV

• Lowest candidate = 83.000970
• Second lowest candidate = 83.001164
• Surplus = 0.002395

Candidate 13 eliminated in round 240, because there was no change in surplus between rounds 238 and 239.

I tested this against an updated definition of surplus (using number of votes * number of tied candidates + surplus) and we still see 9-12 eliminated at the same time https://gerrit.wikimedia.org/r/c/mediawiki/extensions/SecurePoll/+/715711/4

First candidate eliminated in round 49, because there was no change in surplus between rounds 48 and 47.

This means no shortcutting right?

I tested against a few other variations (eliminating 1 at a time, not counting other tied votes as potential votes for transfer, when surplus can be considered none) and the closest I got to replicating the results seen in OopenSTV was if I didn't shortcut and used Hill's definition of "round end" (surplus < .0001) https://gerrit.wikimedia.org/r/c/mediawiki/extensions/SecurePoll/+/715711/5

In T290027#7321300, @STran wrote:

I tested this against an updated definition of surplus (using number of votes * number of tied candidates + surplus) and we still see 9-12 eliminated at the same time https://gerrit.wikimedia.org/r/c/mediawiki/extensions/SecurePoll/+/715711/4

So I guess it is reaching abs( $surplus - $prevSurplus ) < PHP_FLOAT_EPSILON )? If so, this is correct behaviour in my opinion. We know none of the potentially tied candidates are going to receive more votes so we can treat them as actually tied.

I think your above patch is good. It brings us closer to OpenSTV. The only difference is that at the point at which OpenSTV eliminates one tied candidate at random we eliminate them all. And this is a difference we said we wanted.

It is good that the quota is more-or-less the same between SecurePoll round 140 and OpenSTV round 48 (when the first elimination happens). I don't know why the rounds numbers are so different, but it might not matter.

First candidate eliminated in round 49, because there was no change in surplus between rounds 48 and 47.

This means no shortcutting right?

Not in that round. For a shortcut to happen the next lowest candidate would need to have over ~330 votes (82 * 4 plus surplus) which would never happen in that election.

Per discussion in eng meeting, we're going with PS4 to match w/OpenSTV's implementation.

Change 715711 had a related patch set uploaded (by STran; author: STran):

[mediawiki/extensions/SecurePoll@master] Redefine surplus to accomodate tied candidates

https://gerrit.wikimedia.org/r/715711

Change 715711 merged by jenkins-bot:

[mediawiki/extensions/SecurePoll@master] Redefine surplus to accomodate tied candidates

https://gerrit.wikimedia.org/r/715711

@STran I am not able to tally correctly this election (https://github.com/dominic998/SecurePoll-Test-Data/blob/main/test_data/20_6_5000_1301235635.blt, https://vote.wikimedia.beta.wmflabs.org/wiki/Special:SecurePoll/tally/2126).

On beta, when I try to tally via the CLI, I get:

/usr/local/bin/mwscript: line 26: 25394 Segmentation fault      sudo -u "$MEDIAWIKI_WEB_USER" $PHP "$MEDIAWIKI_DEPLOYMENT_DIR_DIR_USE/multiversion/MWScript.php" "$@"

On my local docker, after ~5 seconds it exits without any output. I don't see any obvious errors in the logs.

That election does tally correctly with commit 87874b017e19b2f9175e57df9b7e330dc7223a5a.

In T290027#7376288, @dom_walden wrote:

@STran I am not able to tally correctly this election (https://github.com/dominic998/SecurePoll-Test-Data/blob/main/test_data/20_6_5000_1301235635.blt, https://vote.wikimedia.beta.wmflabs.org/wiki/Special:SecurePoll/tally/2126).

On beta, when I try to tally via the CLI, I get:

/usr/local/bin/mwscript: line 26: 25394 Segmentation fault      sudo -u "$MEDIAWIKI_WEB_USER" $PHP "$MEDIAWIKI_DEPLOYMENT_DIR_DIR_USE/multiversion/MWScript.php" "$@"

On my local docker, after ~5 seconds it exits without any output. I don't see any obvious errors in the logs.

That election does tally correctly with commit 87874b017e19b2f9175e57df9b7e330dc7223a5a.

When tallying this election, if I dump the $this->resultsLog each round the surplus is alternating between 0 and 1.7053025658242E-13, and so is never the same between two successive rounds.

I think this is explained by the fact that, if I dump the output of declareWinners() each round it alternates between:

array(2) {
  [0]=>
  int(865)
  [1]=>
  int(866)
}

and

array(0) {
}

In T290027#7379765, @dom_walden wrote:

In T290027#7376288, @dom_walden wrote:

@STran I am not able to tally correctly this election (https://github.com/dominic998/SecurePoll-Test-Data/blob/main/test_data/20_6_5000_1301235635.blt, https://vote.wikimedia.beta.wmflabs.org/wiki/Special:SecurePoll/tally/2126).

On beta, when I try to tally via the CLI, I get:

/usr/local/bin/mwscript: line 26: 25394 Segmentation fault      sudo -u "$MEDIAWIKI_WEB_USER" $PHP "$MEDIAWIKI_DEPLOYMENT_DIR_DIR_USE/multiversion/MWScript.php" "$@"

On my local docker, after ~5 seconds it exits without any output. I don't see any obvious errors in the logs.

That election does tally correctly with commit 87874b017e19b2f9175e57df9b7e330dc7223a5a.

When tallying this election, if I dump the $this->resultsLog each round the surplus is alternating between 0 and 1.7053025658242E-13, and so is never the same between two successive rounds.

I think this is explained by the fact that, if I dump the output of declareWinners() each round it alternates between:

array(2) {
  [0]=>
  int(865)
  [1]=>
  int(866)
}

and

array(0) {
}

Raised T291821.

I retested a number of elections (from here) which I thought might be problematic (including the one from the description).

There are a couple of test elections where we've improved our results (i.e. they now match OpenSTV), including:

• https://www.mediawiki.org/wiki/Anti-Harassment_Tools/SecurePoll_Improvements/Test_Results/20_9_5000_468090402
• https://www.mediawiki.org/wiki/Anti-Harassment_Tools/SecurePoll_Improvements/Test_Results/12_9_4928_1803187550
• https://www.mediawiki.org/wiki/Anti-Harassment_Tools/SecurePoll_Improvements/Test_Results/20_9_496_604810680
• https://www.mediawiki.org/wiki/Anti-Harassment_Tools/SecurePoll_Improvements/Test_Results/20_9_488_1934769146

In the other elections, our results have not changed but we are running an appropriate number of rounds to make sure that there are no more votes to transfer before eliminating tied candidates.

The only bug I found (which was pre-existing but was revealed by this change) was T291821.

Test environment https://vote.wikimedia.beta.wmflabs.org various versions, latest: SecurePoll 3.0.0 (624ef32) 00:10, 28 September 2021.