# SecurePoll: Make sure tied candidates really are tiedClosed, ResolvedPublicBUG REPORTActions

Assigned To
 STran
Authored By
 dom_walden Aug 30 2021, 6:39 PM2021-08-30 18:39:53 (UTC+0)
Referenced Files
 F34626584: image.png Aug 31 2021, 10:59 AM2021-08-31 10:59:37 (UTC+0)
 F34626624: image.png Aug 31 2021, 10:59 AM2021-08-31 10:59:37 (UTC+0)
Subscribers

# Description

##### What is the problem?

Because we eliminate all tied candidates at once, we should make pretty certain they really are tied before eliminating them all.

Before eliminating tied candidates we should check that either:

1. None of the tied candidates have a chance of winning, or
2. There are no more votes to transfer

In case 1, we can treat the candidates as tied. Even if one tied candidate could in theory overtake another tied candidate, they still would not win.

We already do case 1 to some extent now, but we do it differently than OpenSTV. See below.

In case 2, we know none of the tied candidates can overtake any of the others, so we are sure they are equal.

##### Decisions
1. How do we calculate when tied candidates have no chance of winning?

OpenSTV does number of votes * number of tied candidates + surplus. So 2 tied candidates with 50 votes would need to be more than 100 + surplus behind the second lowest candidate to be eliminated (ref).

SecurePoll does number of votes + surplus. So 2 tied candidates with 50 votes would need to be more than 50 + surplus behind the second lowest candidate to be eliminated.

I guess the logic behind OpenSTV's calculation is whether it would be possible for one of the tied candidates to win if the rest of the tied candidates were eliminated.

In our case, I guess we are checking whether it would be possible for all the tied candidates to win simultaneously. But, this assumes that all the tied candidates really are tied, and we only know they are tied when we get to case 2.

1. How do we decide when there are no more votes to transfer?

OpenSTV does it when the current round's surplus equals last rounds surplus, i.e. no change in surplus between 2 rounds (ref).

I think this becomes important when all the remaining hopeful candidates are tied. There is no second lowest vote to catch up to, so we just need to make sure that the remaining tied candidates really are tied (i.e. there are no more votes to transfer).

Currently, in the case where all remaining candidates are tied, I believe SecurePoll eliminates them all immediately.

##### Steps to reproduce problem

Example elections:

### Event Timeline

Restricted Application added a subscriber: Aklapper. Aug 30 2021, 6:39 PM

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

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.

@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) {
}```

@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:

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.