@STran @TThoabala I would like your input on this ticket. Do you think we should be prioritizing this ticket?

Evaluation:

Seems important and only of medium difficulty. Proposed solution #1 seems feasible

Hello!

I tried to reproduce the bug, but was not successful yet.
I checked out the state of the STVTallier algorithm from Aug 19, 2021 (https://gerrit.wikimedia.org/r/c/mediawiki/extensions/SecurePoll/+/712409) to make sure the bug has not been fixed meanwhile.
I tried it with the two given ballot files (20_6_5000_1301235635.blt, 20_7_5000_425367464.blt).
For this i used the cli commands to reproduce the case:

php generateTestElection.php --ballots=/app/wikimedia/20_7_5000_425367464.blt --admins=WikiSysop --election=stv  --name=TestTally
php tally.php --name=TestTally

The result seems fine for me. All declared winners got carried over to later rounds.
Is there may be another (and more simple) example ballot, with which the bug could be reproduced?

In T291821#9595294, @Driedmueller wrote:

Hello!

I tried to reproduce the bug, but was not successful yet.
I checked out the state of the STVTallier algorithm from Aug 19, 2021 (https://gerrit.wikimedia.org/r/c/mediawiki/extensions/SecurePoll/+/712409) to make sure the bug has not been fixed meanwhile.

Have you tried checking out the commit dcbad8c? The bug was introduced sometime during September 2021 (see T290027#7376288).

Elections with the test data listed in the description are on our beta securepoll test environment (https://vote.wikimedia.beta.wmflabs.org/wiki/Special:SecurePoll/tally/1886, https://vote.wikimedia.beta.wmflabs.org/wiki/Special:SecurePoll/tally/2126). I clicked "Create tally" on both of those, but it is still currently in a pending state. Beta is not always reliable so it could be unrelated. Do you have access? I could potentially get you access if you need it.

I am trying to see if I can reproduce this locally as well, but so far I am just getting errors trying to generate an election (either with commit dcbad8c or the latest version). I will keep trying tomorrow.

Tallying via the CLI on our beta environment, I am getting the same exception I was getting in T290027#7376288:

$ mwscript extensions/SecurePoll/cli/tally.php --wiki=votewiki --name=20_7_5000_425367464
/usr/local/bin/mwscript: line 27: 32355 Segmentation fault      sudo -u "$MEDIAWIKI_WEB_USER" $PHP "$MEDIAWIKI_DEPLOYMENT_DIR_DIR_USE/multiversion/MWScript.php" "$@"

$ mwscript extensions/SecurePoll/cli/tally.php --wiki=votewiki --name=20_6_5000_1301235635
/usr/local/bin/mwscript: line 27: 32363 Segmentation fault      sudo -u "$MEDIAWIKI_WEB_USER" $PHP "$MEDIAWIKI_DEPLOYMENT_DIR_DIR_USE/multiversion/MWScript.php" "$@"

I was able to get the generateTestElection.php working on the latest version of SecurePoll (commit ba9476b58d2db73744221aa2449072d4346870b3). When I tally an election with either of the two test ballots in the description, it starts to eat all my RAM and I cancel it after about 20 seconds.

Note, to get generateTestElection.php working locally I needed to apply the below patch and run it twice, the second time with --reset.

I tried again with dcbad8c and ba9476b58d2d (with patch given) and get the same results.

Both sample ballots consists of 5000 votes. I also run into Segmentation fault (core dumped), but curiously the removing of one vote in the ballots (and then having 4.999 votes) prevents this issue. I simply assume that the one vote has no influence on the result. But there is some different problem underlying here. Also with ballot 20_6_5000_1301235635.blt i get sometimes Seat count mismatch. Ballot options: 6 Election options: 7 on generateTestElection.

Do you have access? I could potentially get you access if you need it.

I dont have access and it would be great to get it, thanks!

I was able to get the generateTestElection.php working on the latest version of SecurePoll

Could you reproduce the "elected candidates get eliminated in later" rounds issue with the given ballots?

In T291821#9619132, @Driedmueller wrote:

I tried again with dcbad8c and ba9476b58d2d (with patch given) and get the same results.

Do you mean you were able to reproduce the bug?

Both sample ballots consists of 5000 votes. I also run into Segmentation fault (core dumped), but curiously the removing of one vote in the ballots (and then having 4.999 votes) prevents this issue. I simply assume that the one vote has no influence on the result.

As far as I remember, those ballots were designed to create close elections in order to test SecurePoll's floating-point comparisons. I think a single vote could make a difference. It does not surprise me that removing one vote means you can no longer reproduce the bug.

But there is some different problem underlying here. Also with ballot 20_6_5000_1301235635.blt i get sometimes Seat count mismatch. Ballot options: 6 Election options: 7 on generateTestElection.

Hmm. Is that a bug when generating the election or in the tallying?

Do you have access? I could potentially get you access if you need it.

I dont have access and it would be great to get it, thanks!

I have sent @jrbs instructions for getting you ssh access. In the meantime, I have created you an account on https://vote.wikimedia.beta.wmflabs.org. @jrbs has the credentials.

I was able to get the generateTestElection.php working on the latest version of SecurePoll

Could you reproduce the "elected candidates get eliminated in later" rounds issue with the given ballots?

I don't think I ever saw a bug where candidates who were counted as elected in one round were eliminated in a later round. The behaviour I saw after inserting var_dump's in the code was candidates being elected in one round and then in the next no longer being elected (but not eliminated. Sorry, I cannot remember the name of the state).

Do you mean you were able to reproduce the bug?

No sorry, i meant the election looks good and i could not reproduce it. But, as you stated, i was missing one vote and this could make the difference.
So next step for me would be to reproduce it with all 5000 votes, if thats technically possible from my side.
Alternatively, it would be great, if there is may be another and more simple example ballot, with which the bug could be reproduced?

Hmm. Is that a bug when generating the election or in the tallying?

On generating with generateTestelection.php. I tried again, but i cant reproduce it safely, i think it does not play a (big) role here.

I have sent @jrbs instructions for getting you ssh access. In the meantime, I have created you an account on https://vote.wikimedia.beta.wmflabs.org. @jrbs has the credentials.

Great, thanks! I get in touch with him.

I don't think I ever saw a bug where candidates who were counted as elected in one round were eliminated in a later round. The behaviour I saw after inserting var_dump's in the code was candidates being elected in one round and then in the next no longer being elected (but not eliminated. Sorry, I cannot remember the name of the state).

Ah ok! Im not yet that into the functionality, so i just assumed not elected is the same as eliminated. Then the question would be, if you were able to reproduce the bug with the given ballots? And if yes, is this also true for the latest version of SecurePoll extension?

In T291821#9622678, @Driedmueller wrote:

Alternatively, it would be great, if there is may be another and more simple example ballot, with which the bug could be reproduced?

I tried yesterday and a bit today but could not. I think it will be hard to reproduce it with fewer votes because the more votes the higher the number of decimal places in the calculations that SecurePoll has to do (at least from my experience).

I don't think I ever saw a bug where candidates who were counted as elected in one round were eliminated in a later round. The behaviour I saw after inserting var_dump's in the code was candidates being elected in one round and then in the next no longer being elected (but not eliminated. Sorry, I cannot remember the name of the state).

Ah ok! Im not yet that into the functionality, so i just assumed not elected is the same as eliminated. Then the question would be, if you were able to reproduce the bug with the given ballots? And if yes, is this also true for the latest version of SecurePoll extension?

Reading the code again, I think the terminology it uses is "hopeful" candidates.

Yes, I have been able to reproduce the bug with those two ballots from the description in the latest version of SecurePoll (3.0.0 (d0dd97e) 07:28, 11 March 2024).

The tally.php script does not complete and uses up all my RAM.

I added var_export's to includes/Talliers/STVTallier.php to print out $this->resultsLog each round. After a few rounds, the $this->resultsLog['rounds'][<round num>]['surplus'] alternates between 0 and 1.7053025658242404E-13. In the former case, $this->declareWinners returns no winners. In the latter case, it returns two winners.

It needs to get to a point where it can eliminate a candidate and reallocate votes, and one condition which triggers this is if the surplus stays the same between rounds. However, this never happens.

Im able now to reproduce the issue with both ballots and could debug the process.
The algorithm and calculations thats going on there is rather complex, so that we can not provide a solution involving mathematical magic, but we suggest to implement the first solution, like OpenSTV: persist the winners from round to round.

I would also present and discuss a thing i also noticed, when i tried to reproduce the alternating surplusses between 0 and 1.7053025658242404E-13.
The reason for this behaviour lies in the incapability of PHP to do correct arithmetic operations on floating numbers.
A famous example of this is in PHP: 0.1 + 0.2 = 0.300000000000004.
If you are interested in this odd behaviour, i googled this explanation:

PHP’s float is an IEEE 754–1985 double under the hood, which is a binary floating-point number, and is therefore not capable of representing certain numbers, such as 0.2. This is because the value is usually stored as an integer multiplied by 2 to the power of an exponent: a * 2^b = c, where a and b are integers. When there are no integer solutions for a and b, the resulting number will be an approximation.

Ultimately this leads to wrong calculations that, in my understanding, gets worse the more places after the comma.
I added a rounding function with a precision value to the algorithm and applied it on every occurrence i thought it would be meaningful.
I did test runs with both ballots and different precisions:
The first number is the round. The others the candidates. In case of the thousands round, its only the last rounds, before my memory was full.

20_7_5000_425367464.blt

without rounding
27501 924,925,926,928,929
27502 924,926,927,929
27503 924,925,926,928,929
27504 924,926,927,929
27505 924,925,926,928,929
27506 924,926,927,929

precision = 100 
27497 924,925,926,928,929
27498 924,926,927,929
27499 924,925,926,928,929
27500 924,926,927,929
27501 924,925,926,928,929
27502 924,926,927,929

precision = 15
2 924,925,926,927,928,929
3 924,925,926,927,928,929
4 924,925,926,927,928,929
5 924,925,926,927,928,929
6 924,925,926,927,928,929
7 924,925,926,927,928,929
8 924,925,926,927,928,929
9 924,925,926,927,928,929
10 924,925,926,927,928,929
11 924,925,926,927,928,929
12 924,925,926,927,928,929
13 924,925,926,927,928,929
14 924,925,926,927,928,929
15 924,925,926,927,928,929
16 924,925,926,927,928,929
17 924,925,926,927,928,929
18 924,925,926,927,928,929
19 924,925,926,927,928,929
20 924,925,926,927,928,929
21 924,925,926,927,928,929
22 924,925,926,927,928,929
23 924,925,926,927,928,929
24 924,925,926,927,928,929
25 924,925,926,927,928,929
26 924,925,926,927,928,929
27 924,925,926,927,928,929
28 924,925,926,927,928,929
29 924,925,926,927,928,929
30 924,925,926,927,928,929
31 924,925,926,927,928,929
32 924,925,926,927,928,929
33 924,925,926,927,928,929
34 924,925,926,927,928,929
35 924,925,926,927,928,929
36 924,925,926,927,928,929
37 924,925,926,927,928,929
38 924,925,926,927,928,929
39 924,926,927,928,929
40 924,926,927,928,929
41 924,925,926,927,928,929
42 924,925,926,927,928,929
43 924,925,926,927,928,929
44 924,925,926,927,928,929
45 924,925,926,927,928,929
46 924,925,926,927,928,929
47 924,925,926,927,928,929
48 924,925,926,927,928,929
49 924,925,926,927,928,929
50 924,925,926,927,928,929
51 924,925,926,927,928,929
52 924,925,926,927,928,929
53 924,925,926,927,928,929
54 924,925,926,927,928,929
55 924,925,926,927,928,929
56 924,925,926,927,928,929
57 924,925,926,927,928,929
58 924,925,926,927,928,929
59 924,925,926,927,928,929
60 924,925,926,927,928,929
61 924,925,926,927,928,929
62 924,925,926,927,928,929
63 924,925,926,927,928,929
64 924,925,926,927,928,929
65 924,925,926,927,928,929
66 924,925,926,927,928,929
67 924,925,926,927,928,929
68 924,925,926,927,928,929
69 924,925,926,927,928,929
70 924,925,926,927,928,929
71 924,925,926,927,928,929
72 924,925,926,927,928,929
73 924,925,926,927,928,929
74 924,925,926,927,928,929
75 924,925,926,927,928,929
76 924,925,926,927,928,929
77 924,925,926,927,928,929
78 924,925,926,927,928,929
79 924,925,926,927,928,929
80 924,925,926,927,928,929
81 924,925,926,927,928,929
82 924,925,926,927,928,929
83 925,926,927,928,929
84 925,926,927,928,929
85 924,925,926,927,928,929
86 924,925,926,927,928,929,943

precision = 10
2 924,925,926,927,928,929
3 924,925,926,927,928,929
4 924,925,926,927,928,929
5 924,925,926,927,928,929
6 924,925,926,927,928,929
7 924,925,926,927,928,929
8 924,925,926,927,928,929
9 924,925,926,927,928,929
10 924,925,926,927,928,929
11 924,925,926,927,928,929
12 924,925,926,927,928,929
13 924,925,926,927,928,929
14 924,925,926,927,928,929
15 924,925,926,927,928,929
16 924,925,926,927,928,929
17 924,925,926,927,928,929
18 924,925,926,927,928,929
19 924,925,926,927,928,929
20 924,925,926,927,928,929
21 924,925,926,927,928,929
22 924,925,926,927,928,929
23 924,925,926,927,928,929
24 924,925,927,928,929
25 924,926,928,929
26 924,926,928,929
27 924,925,926,927,928,929
28 924,925,926,927,928,929
29 924,925,926,927,928,929
30 924,925,926,927,928,929
31 924,925,926,927,928,929
32 924,925,926,927,928,929
33 924,925,926,927,928,929
34 924,925,926,927,928,929
35 924,925,926,927,928,929
36 924,925,926,927,928,929
37 924,925,926,927,928,929
38 924,925,926,927,928,929
39 924,925,926,927,928,929
40 924,925,926,927,928,929
41 924,925,926,927,928,929
42 924,925,926,927,928,929
43 924,925,926,927,928,929
44 924,925,926,927,928,929
45 924,925,926,927,928,929
46 924,925,926,927,928,929
47 924,925,926,927,928,929
48 924,925,926,927,928,929
49 924,925,926,927,928,929
50 924,925,926,927,928,929
51 924,925,926,927,928,929
52 924,925,926,927,928,929
53 924,925,926,927,928,929
54 924,925,928,929
55 924,925,927,929
56 924,925,927,929
57 924,925,926,927,928,929
58 924,925,926,927,928,929,943

precision = 6 (Display precision)
2 924,925,926,927,928,929
3 924,925,926,927,928,929
4 924,925,926,927,928,929
5 924,925,926,927,928,929
6 924,925,926,927,928,929
7 924,925,926,927,928,929
8 924,925,926,927,928,929
9 924,925,926,927,928,929
10 924,925,926,927,928,929
11 924,925,926,927,928,929
12 924,925,926,927,928,929
13 924,926,927,928,929
14 924,926,927,928,929
15 924,925,926,927,928,929
16 924,925,926,927,928,929
17 924,925,926,927,928,929
18 924,925,926,927,928,929
19 924,925,926,927,928,929
20 924,925,926,927,928,929
21 924,925,926,927,928,929
22 924,925,926,927,928,929
23 924,925,926,927,928,929
24 924,925,926,927,928,929
25 924,925,926,927,928,929
26 924,925,926,927,928,929
27 924,925,926,927,928,929
28 924,925,926,927,928,929
29 924,925,926,927,928,929
30 924,925,926,928,929
31 925,926,927
32 925,926,927
33 924,925,926,927,928,929
34 924,925,926,927,928,929,943

precision = 5
2 924,925,926,927,928,929
3 924,925,926,927,928,929
4 924,925,926,927,928,929
5 924,925,926,927,928,929
6 924,925,926,927,928,929
7 924,925,926,927,928,929
8 924,925,926,927,928,929
9 924,925,926,927,928,929
10 924,925,926,927,928,929
11 924,926,927,928,929
12 924,926,927,928,929
13 924,925,926,927,928,929
14 924,925,926,927,928,929
15 924,925,926,927,928,929
16 924,925,926,927,928,929
17 924,925,926,927,928,929
18 924,925,926,927,928,929
19 924,925,926,927,928,929
20 924,925,926,927,928,929
21 924,925,926,927,928,929
22 924,925,926,927,928,929
23 924,925,926,927,928,929
24 924,925,926,927,928,929
25 926,927
26 924,925,927,928,929
27 924,925,927,928,929
28 924,925,926,927,928,929
29 924,925,926,927,928,929,943

precision = 2
2 924,925,926,927,928,929
3 924,925,926,927,928,929
4 924,925,926,927,928,929
5 924,925,926,927,928,929
6 924,925,926,927,928,929
7 924,925,926,927,928,929
8 924,925,926,927,928,929
9 924,925,926,927,928,929
10 924,925,926,927,928,929,943

20_7_5000_425367464.blt

without rounding
27501 924,925,926,928,929
27502 924,926,927,929
27503 924,925,926,928,929
27504 924,926,927,929
27505 924,925,926,928,929
27506 924,926,927,929

precision = 100
27497 924,925,926,928,929
27498 924,926,927,929
27499 924,925,926,928,929
27500 924,926,927,929
27501 924,925,926,928,929
27502 924,926,927,929

precision = 15 succeeds
2 924,925,926,927,928,929
3 924,925,926,927,928,929
4 924,925,926,927,928,929
5 924,925,926,927,928,929
6 924,925,926,927,928,929
7 924,925,926,927,928,929
8 924,925,926,927,928,929
9 924,925,926,927,928,929
10 924,925,926,927,928,929
11 924,925,926,927,928,929
12 924,925,926,927,928,929
13 924,925,926,927,928,929
14 924,925,926,927,928,929
15 924,925,926,927,928,929
16 924,925,926,927,928,929
17 924,925,926,927,928,929
18 924,925,926,927,928,929
19 924,925,926,927,928,929
20 924,925,926,927,928,929
21 924,925,926,927,928,929
22 924,925,926,927,928,929
23 924,925,926,927,928,929
24 924,925,926,927,928,929
25 924,925,926,927,928,929
26 924,925,926,927,928,929
27 924,925,926,927,928,929
28 924,925,926,927,928,929
29 924,925,926,927,928,929
30 924,925,926,927,928,929
31 924,925,926,927,928,929
32 924,925,926,927,928,929
33 924,925,926,927,928,929
34 924,925,926,927,928,929
35 924,925,926,927,928,929
36 924,925,926,927,928,929
37 924,925,926,927,928,929
38 924,925,926,927,928,929
39 924,926,927,928,929
40 924,926,927,928,929
41 924,925,926,927,928,929
42 924,925,926,927,928,929
43 924,925,926,927,928,929
44 924,925,926,927,928,929
45 924,925,926,927,928,929
46 924,925,926,927,928,929
47 924,925,926,927,928,929
48 924,925,926,927,928,929
49 924,925,926,927,928,929
50 924,925,926,927,928,929
51 924,925,926,927,928,929
52 924,925,926,927,928,929
53 924,925,926,927,928,929
54 924,925,926,927,928,929
55 924,925,926,927,928,929
56 924,925,926,927,928,929
57 924,925,926,927,928,929
58 924,925,926,927,928,929
59 924,925,926,927,928,929
60 924,925,926,927,928,929
61 924,925,926,927,928,929
62 924,925,926,927,928,929
63 924,925,926,927,928,929
64 924,925,926,927,928,929
65 924,925,926,927,928,929
66 924,925,926,927,928,929
67 924,925,926,927,928,929
68 924,925,926,927,928,929
69 924,925,926,927,928,929
70 924,925,926,927,928,929
71 924,925,926,927,928,929
72 924,925,926,927,928,929
73 924,925,926,927,928,929
74 924,925,926,927,928,929
75 924,925,926,927,928,929
76 924,925,926,927,928,929
77 924,925,926,927,928,929
78 924,925,926,927,928,929
79 924,925,926,927,928,929
80 924,925,926,927,928,929
81 924,925,926,927,928,929
82 924,925,926,927,928,929
83 925,926,927,928,929
84 925,926,927,928,929
85 924,925,926,927,928,929
86 924,925,926,927,928,929,943

precision = 10 succeeds
2 924,925,926,927,928,929
3 924,925,926,927,928,929
4 924,925,926,927,928,929
5 924,925,926,927,928,929
6 924,925,926,927,928,929
7 924,925,926,927,928,929
8 924,925,926,927,928,929
9 924,925,926,927,928,929
10 924,925,926,927,928,929
11 924,925,926,927,928,929
12 924,925,926,927,928,929
13 924,925,926,927,928,929
14 924,925,926,927,928,929
15 924,925,926,927,928,929
16 924,925,926,927,928,929
17 924,925,926,927,928,929
18 924,925,926,927,928,929
19 924,925,926,927,928,929
20 924,925,926,927,928,929
21 924,925,926,927,928,929
22 924,925,926,927,928,929
23 924,925,926,927,928,929
24 924,925,927,928,929
25 924,926,928,929
26 924,926,928,929
27 924,925,926,927,928,929
28 924,925,926,927,928,929
29 924,925,926,927,928,929
30 924,925,926,927,928,929
31 924,925,926,927,928,929
32 924,925,926,927,928,929
33 924,925,926,927,928,929
34 924,925,926,927,928,929
35 924,925,926,927,928,929
36 924,925,926,927,928,929
37 924,925,926,927,928,929
38 924,925,926,927,928,929
39 924,925,926,927,928,929
40 924,925,926,927,928,929
41 924,925,926,927,928,929
42 924,925,926,927,928,929
43 924,925,926,927,928,929
44 924,925,926,927,928,929
45 924,925,926,927,928,929
46 924,925,926,927,928,929
47 924,925,926,927,928,929
48 924,925,926,927,928,929
49 924,925,926,927,928,929
50 924,925,926,927,928,929
51 924,925,926,927,928,929
52 924,925,926,927,928,929
53 924,925,926,927,928,929
54 924,925,928,929
55 924,925,927,929
56 924,925,927,929
57 924,925,926,927,928,929
58 924,925,926,927,928,929,943

precision = 6 (Display precision)
2 924,925,926,927,928,929
3 924,925,926,927,928,929
4 924,925,926,927,928,929
5 924,925,926,927,928,929
6 924,925,926,927,928,929
7 924,925,926,927,928,929
8 924,925,926,927,928,929
9 924,925,926,927,928,929
10 924,925,926,927,928,929
11 924,925,926,927,928,929
12 924,925,926,927,928,929
13 924,926,927,928,929
14 924,926,927,928,929
15 924,925,926,927,928,929
16 924,925,926,927,928,929
17 924,925,926,927,928,929
18 924,925,926,927,928,929
19 924,925,926,927,928,929
20 924,925,926,927,928,929
21 924,925,926,927,928,929
22 924,925,926,927,928,929
23 924,925,926,927,928,929
24 924,925,926,927,928,929
25 924,925,926,927,928,929
26 924,925,926,927,928,929
27 924,925,926,927,928,929
28 924,925,926,927,928,929
29 924,925,926,927,928,929
30 924,925,926,928,929
31 925,926,927
32 925,926,927
33 924,925,926,927,928,929
34 924,925,926,927,928,929,943

precision = 5
2 924,925,926,927,928,929
3 924,925,926,927,928,929
4 924,925,926,927,928,929
5 924,925,926,927,928,929
6 924,925,926,927,928,929
7 924,925,926,927,928,929
8 924,925,926,927,928,929
9 924,925,926,927,928,929
10 924,925,926,927,928,929
11 924,926,927,928,929
12 924,926,927,928,929
13 924,925,926,927,928,929
14 924,925,926,927,928,929
15 924,925,926,927,928,929
16 924,925,926,927,928,929
17 924,925,926,927,928,929
18 924,925,926,927,928,929
19 924,925,926,927,928,929
20 924,925,926,927,928,929
21 924,925,926,927,928,929
22 924,925,926,927,928,929
23 924,925,926,927,928,929
24 924,925,926,927,928,929
25 926,927
26 924,925,927,928,929
27 924,925,927,928,929
28 924,925,926,927,928,929
29 924,925,926,927,928,929,943

precision = 2
2 924,925,926,927,928,929
3 924,925,926,927,928,929
4 924,925,926,927,928,929
5 924,925,926,927,928,929
6 924,925,926,927,928,929
7 924,925,926,927,928,929
8 924,925,926,927,928,929
9 924,925,926,927,928,929
10 924,925,926,927,928,929,943

20_6_5000_1301235635.blt

without rounding
27513 902,903
27514 
27515 902,903
27516 
27517 902,903
27518 

precision = 100
27515 902,903
27516 
27517 902,903
27518 
27519 902,903
27520 

precision = 15
2 903
3 903
4 
5 
6 902,903
7 902,903
8 902,903
9 902,903
10 902,903
11 902,903
12 902,903
13 902,903
14 902,903
15 902,903
16 902,903
17 902,903
18 902,903
19 902,903
20 902,903
21 902,903
22 902,903
23 902,903
24 902,903
25 902,903
26 902,903
27 902,903
28 902,903
29 902,903
30 902,903
31 902,903
32 902,903
33 902,903
34 902,903
35 902,903,904,905

precision = 10
2 903
3 903
4 903
5 902,903
6 902,903
7 902,903
8 902,903
9 902,903
10 902,903
11 902,903
12 902,903
13 902,903
14 902,903
15 902,903
16 902,903
17 902,903
18 902,903
19 902,903
20 902,903
21 902,903
22 902,903
23 902
24 903
25 903
26 902,903,904,905

precision = 6 (Display precision)
2 903
3 903
4 903
5 902,903
6 902,903
7 902,903
8 902,903
9 902,903
10 902,903
11 902,903
12 902,903
13 902,903
14 902,903
15 902,903
16 
17 
18 902,903,904,905

precision = 5
2 903
3 902
4 902
5 902,903
6 902,903
7 902,903
8 902,903
9 902,903
10 902,903
11 902,903
12 902,903
13 902,903
14 902,903
15 903
16 903
17 902,903,904,905

precision = 2
2 903
3 903
4 902,903
5 902,903
6 902,903
7 902,903
8 902,903
9 902
10 903
11 903

As you can see, adding precision to the floating numbers does not solve the issues of the elected winners getting to the next round, but it prevents the memory issue and does improve the performance a lot. Im not sure however if the results are still valid. The end result seems to stay the same though (except precision = 2).
OpenSTV does not have this problem because python can actually calculate correctly with floating numbers.
I am curious to hear your thoughts on this.

In T291821#9645629, @Driedmueller wrote:

I would also present and discuss a thing i also noticed, when i tried to reproduce the alternating surplusses between 0 and 1.7053025658242404E-13.
The reason for this behaviour lies in the incapability of PHP to do correct arithmetic operations on floating numbers.
A famous example of this is in PHP: 0.1 + 0.2 = 0.300000000000004.

I thought most/all programming languages had this problem. I tried this on python 3.9:

>>> 0.1 + 0.2
0.30000000000000004

We did look into implementing the PHP BC library for arbitrary precision arithmetic. But apparently it wasn't successful T289185.

I had thought that OpenSTV used fixed-point arithmetic instead, which I have read in some places might be better for this sort of thing. But, when I re-read the code, I cannot find evidence for this. Moreover, I am not a numerical analyst :).

Update after yesterday's meeting with @jrbs:

@Driedmueller will implement it by storing the winners between the rounds.

The precision topic needs a new ticket, which will be created by @jrbs.

Change #1014053 had a related patch set uploaded (by Driedmueller; author: Driedmueller):

[mediawiki/extensions/SecurePoll@wmf/1.42.0-wmf.24] Dont recalculate winners from scratch each round

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

Hi there, @TAdeleye_WMF asked if I could provide code review support on this, which I'm happy to do whenever there is a patch against the master branch. However, I don't have a clear way to reproduce the issue against master. Could @dom_walden or @Driedmueller offer me (a person with mediawiki experience, but no subject matter expertise for SVT polls) a concise way to reproduce the "declare winners" issue locally? I updated STVTallierTest_drw.php to the point where unit_test_stv.sh, but it eventually dies out (I'm assuming due to memory issues). Maybe an updated/smaller test file? The patch looks good on a read through, but wouldn't be comfortable giving a +2 just based on that. It looks like there are some good findings here from live testing, but most of the discussion about that seems to be dealing with the rounding error.

In T291821#9649754, @dom_walden wrote:

In T291821#9645629, @Driedmueller wrote:

I would also present and discuss a thing i also noticed, when i tried to reproduce the alternating surplusses between 0 and 1.7053025658242404E-13.
The reason for this behaviour lies in the incapability of PHP to do correct arithmetic operations on floating numbers.
A famous example of this is in PHP: 0.1 + 0.2 = 0.300000000000004.

I thought most/all programming languages had this problem. I tried this on python 3.9:

>>> 0.1 + 0.2
0.30000000000000004

We did look into implementing the PHP BC library for arbitrary precision arithmetic. But apparently it wasn't successful T289185.

I had thought that OpenSTV used fixed-point arithmetic instead, which I have read in some places might be better for this sort of thing. But, when I re-read the code, I cannot find evidence for this. Moreover, I am not a numerical analyst :).

You are right, Python and every other programming language has this problem. That was a wrong assumption from my side.
I also just stepped over: https://www.mediawiki.org/wiki/Anti-Harassment_Tools/SecurePoll_Improvements/Test_Results/Precision,
where the precision errors have also been investigated.
I think, a fixed precision could still improve the performance, without changing the outcome. But i cant prove it.

In T291821#9745815, @jsn.sherman wrote:

Hi there, @TAdeleye_WMF asked if I could provide code review support on this, which I'm happy to do whenever there is a patch against the master branch. However, I don't have a clear way to reproduce the issue against master. Could @dom_walden or @Driedmueller offer me (a person with mediawiki experience, but no subject matter expertise for SVT polls) a concise way to reproduce the "declare winners" issue locally? I updated STVTallierTest_drw.php to the point where unit_test_stv.sh, but it eventually dies out (I'm assuming due to memory issues). Maybe an updated/smaller test file? The patch looks good on a read through, but wouldn't be comfortable giving a +2 just based on that. It looks like there are some good findings here from live testing, but most of the discussion about that seems to be dealing with the rounding error.

Hi! Thanks for having a look!
Im also unable to really reproduce the problem, at least when it comes to detecting an meaningful impact on the outcome of the vote.
When tallying the two given example ballot files, without precision, it will produce an error.
So i tested it with an precision of 15 (16 e.g., also produces the error).

The first https://github.com/dominic998/SecurePoll-Test-Data/blob/main/test_data/20_6_5000_1301235635.blt and the second https://github.com/dominic998/SecurePoll-Test-Data/blob/main/test_data/20_7_5000_425367464.blt producing the same result, regardless if the winners are saved between rounds.

20_6_5000_1301235635.blt
Without saving winners:
Round 1: 1010
Round 2: 1010
Round 3: 
Round 4: 
Round 5: 1009,1010
Round 6: 1009,1010
Round 7: 1009,1010
Round 8: 1009,1010
Round 9: 1009,1010
Round 10: 1009,1010
Round 11: 1009,1010
Round 12: 1009,1010
Round 13: 1009,1010
Round 14: 1009,1010
Round 15: 1009,1010
Round 16: 1009,1010
Round 17: 1009,1010
Round 18: 1009,1010
Round 19: 1009,1010
Round 20: 1009,1010
Round 21: 1009,1010
Round 22: 1009,1010
Round 23: 1009,1010
Round 24: 1009,1010
Round 25: 1009,1010
Round 26: 1009,1010
Round 27: 1009,1010
Round 28: 1009,1010
Round 29: 1009,1010
Round 30: 1009,1010
Round 31: 1009,1010
Round 32: 1009,1010
Round 33: 1009,1010
Round 34: 1009,1010,1011,1012
With saving Winners: 
Round 1: 1010
Round 2: 1010
Round 3: 1010
Round 4: 1010
Round 5: 1010,1009
Round 6: 1010,1009
Round 7: 1010,1009
Round 8: 1010,1009
Round 9: 1010,1009
Round 10: 1010,1009
Round 11: 1010,1009
Round 12: 1010,1009
Round 13: 1010,1009
Round 14: 1010,1009
Round 15: 1010,1009
Round 16: 1010,1009
Round 17: 1010,1009
Round 18: 1010,1009
Round 19: 1010,1009
Round 20: 1010,1009
Round 21: 1010,1009
Round 22: 1010,1009
Round 23: 1010,1009
Round 24: 1010,1009
Round 25: 1010,1009
Round 26: 1010,1009
Round 27: 1010,1009
Round 28: 1010,1009
Round 29: 1010,1009
Round 30: 1010,1009
Round 31: 1010,1009
Round 32: 1010,1009
Round 33: 1010,1009
Round 34: 1010,1009,1011,1012

20_7_5000_425367464.blt
Without saving winners:
Round 1: 987,988,989,990,991,992
Round 2: 987,988,989,990,991,992
Round 3: 987,988,989,990,991,992
Round 4: 987,988,989,990,991,992
Round 5: 987,988,989,990,991,992
Round 6: 987,988,989,990,991,992
Round 7: 987,988,989,990,991,992
Round 8: 987,988,989,990,991,992
Round 9: 987,988,989,990,991,992
Round 10: 987,988,989,990,991,992
Round 11: 987,988,989,990,991,992
Round 12: 987,988,989,990,991,992
Round 13: 987,988,989,990,991,992
Round 14: 987,988,989,990,991,992
Round 15: 987,988,989,990,991,992
Round 16: 987,988,989,990,991,992
Round 17: 987,988,989,990,991,992
Round 18: 987,988,989,990,991,992
Round 19: 987,988,989,990,991,992
Round 20: 987,988,989,990,991,992
Round 21: 987,988,989,990,991,992
Round 22: 987,988,989,990,991,992
Round 23: 987,988,989,990,991,992
Round 24: 987,988,989,990,991,992
Round 25: 987,988,989,990,991,992
Round 26: 987,988,989,990,991,992
Round 27: 987,988,989,990,991,992
Round 28: 987,988,989,990,991,992
Round 29: 987,988,989,990,991,992
Round 30: 987,988,989,990,991,992
Round 31: 987,988,989,990,991,992
Round 32: 987,988,989,990,991,992
Round 33: 987,988,989,990,991,992
Round 34: 987,988,989,990,991,992
Round 35: 987,988,989,990,991,992
Round 36: 987,988,989,990,991,992
Round 37: 987,988,989,990,991,992
Round 38: 987,989,990,991,992
Round 39: 987,989,990,991,992
Round 40: 987,988,989,990,991,992
Round 41: 987,988,989,990,991,992
Round 42: 987,988,989,990,991,992
Round 43: 987,988,989,990,991,992
Round 44: 987,988,989,990,991,992
Round 45: 987,988,989,990,991,992
Round 46: 987,988,989,990,991,992
Round 47: 987,988,989,990,991,992
Round 48: 987,988,989,990,991,992
Round 49: 987,988,989,990,991,992
Round 50: 987,988,989,990,991,992
Round 51: 987,988,989,990,991,992
Round 52: 987,988,989,990,991,992
Round 53: 987,988,989,990,991,992
Round 54: 987,988,989,990,991,992
Round 55: 987,988,989,990,991,992
Round 56: 987,988,989,990,991,992
Round 57: 987,988,989,990,991,992
Round 58: 987,988,989,990,991,992
Round 59: 987,988,989,990,991,992
Round 60: 987,988,989,990,991,992
Round 61: 987,988,989,990,991,992
Round 62: 987,988,989,990,991,992
Round 63: 987,988,989,990,991,992
Round 64: 987,988,989,990,991,992
Round 65: 987,988,989,990,991,992
Round 66: 987,988,989,990,991,992
Round 67: 987,988,989,990,991,992
Round 68: 987,988,989,990,991,992
Round 69: 987,988,989,990,991,992
Round 70: 987,988,989,990,991,992
Round 71: 987,988,989,990,991,992
Round 72: 987,988,989,990,991,992
Round 73: 987,988,989,990,991,992
Round 74: 987,988,989,990,991,992
Round 75: 987,988,989,990,991,992
Round 76: 987,988,989,990,991,992
Round 77: 987,988,989,990,991,992
Round 78: 987,988,989,990,991,992
Round 79: 987,988,989,990,991,992
Round 80: 987,988,989,990,991,992
Round 81: 987,988,989,990,991,992
Round 82: 988,989,990,991,992
Round 83: 988,989,990,991,992
Round 84: 987,988,989,990,991,992
Round 85: 987,988,989,990,991,992,1006
With saving winners:
Round 1: 987,988,989,990,991,992
Round 2: 987,988,989,990,991,992
Round 3: 987,988,989,990,991,992
Round 4: 987,988,989,990,991,992
Round 5: 987,988,989,990,991,992
Round 6: 987,988,989,990,991,992
Round 7: 987,988,989,990,991,992
Round 8: 987,988,989,990,991,992
Round 9: 987,988,989,990,991,992
Round 10: 987,988,989,990,991,992
Round 11: 987,988,989,990,991,992
Round 12: 987,988,989,990,991,992
Round 13: 987,988,989,990,991,992
Round 14: 987,988,989,990,991,992
Round 15: 987,988,989,990,991,992
Round 16: 987,988,989,990,991,992
Round 17: 987,988,989,990,991,992
Round 18: 987,988,989,990,991,992
Round 19: 987,988,989,990,991,992
Round 20: 987,988,989,990,991,992
Round 21: 987,988,989,990,991,992
Round 22: 987,988,989,990,991,992
Round 23: 987,988,989,990,991,992
Round 24: 987,988,989,990,991,992
Round 25: 987,988,989,990,991,992
Round 26: 987,988,989,990,991,992
Round 27: 987,988,989,990,991,992
Round 28: 987,988,989,990,991,992
Round 29: 987,988,989,990,991,992
Round 30: 987,988,989,990,991,992
Round 31: 987,988,989,990,991,992
Round 32: 987,988,989,990,991,992
Round 33: 987,988,989,990,991,992
Round 34: 987,988,989,990,991,992
Round 35: 987,988,989,990,991,992
Round 36: 987,988,989,990,991,992
Round 37: 987,988,989,990,991,992
Round 38: 987,988,989,990,991,992
Round 39: 987,988,989,990,991,992
Round 40: 987,988,989,990,991,992
Round 41: 987,988,989,990,991,992
Round 42: 987,988,989,990,991,992
Round 43: 987,988,989,990,991,992
Round 44: 987,988,989,990,991,992
Round 45: 987,988,989,990,991,992
Round 46: 987,988,989,990,991,992
Round 47: 987,988,989,990,991,992
Round 48: 987,988,989,990,991,992
Round 49: 987,988,989,990,991,992
Round 50: 987,988,989,990,991,992
Round 51: 987,988,989,990,991,992
Round 52: 987,988,989,990,991,992
Round 53: 987,988,989,990,991,992
Round 54: 987,988,989,990,991,992
Round 55: 987,988,989,990,991,992
Round 56: 987,988,989,990,991,992
Round 57: 987,988,989,990,991,992
Round 58: 987,988,989,990,991,992
Round 59: 987,988,989,990,991,992
Round 60: 987,988,989,990,991,992
Round 61: 987,988,989,990,991,992
Round 62: 987,988,989,990,991,992
Round 63: 987,988,989,990,991,992
Round 64: 987,988,989,990,991,992
Round 65: 987,988,989,990,991,992
Round 66: 987,988,989,990,991,992
Round 67: 987,988,989,990,991,992
Round 68: 987,988,989,990,991,992
Round 69: 987,988,989,990,991,992
Round 70: 987,988,989,990,991,992
Round 71: 987,988,989,990,991,992
Round 72: 987,988,989,990,991,992
Round 73: 987,988,989,990,991,992
Round 74: 987,988,989,990,991,992
Round 75: 987,988,989,990,991,992
Round 76: 987,988,989,990,991,992
Round 77: 987,988,989,990,991,992
Round 78: 987,988,989,990,991,992
Round 79: 987,988,989,990,991,992
Round 80: 987,988,989,990,991,992
Round 81: 987,988,989,990,991,992
Round 82: 987,988,989,990,991,992
Round 83: 987,988,989,990,991,992
Round 84: 987,988,989,990,991,992
Round 85: 987,988,989,990,991,992,1006

So saving winners between rounds with those two examples does not affect the outcome of the votes. At least when tallying with a precision.

In T291821#9752189, @Driedmueller wrote:

In T291821#9745815, @jsn.sherman wrote:

Hi there, @TAdeleye_WMF asked if I could provide code review support on this, which I'm happy to do whenever there is a patch against the master branch. However, I don't have a clear way to reproduce the issue against master. Could @dom_walden or @Driedmueller offer me (a person with mediawiki experience, but no subject matter expertise for SVT polls) a concise way to reproduce the "declare winners" issue locally? I updated STVTallierTest_drw.php to the point where unit_test_stv.sh, but it eventually dies out (I'm assuming due to memory issues). Maybe an updated/smaller test file? The patch looks good on a read through, but wouldn't be comfortable giving a +2 just based on that. It looks like there are some good findings here from live testing, but most of the discussion about that seems to be dealing with the rounding error.

Hi! Thanks for having a look!
Im also unable to really reproduce the problem, at least when it comes to detecting an meaningful impact on the outcome of the vote.
When tallying the two given example ballot files, without precision, it will produce an error.
So i tested it with an precision of 15 (16 e.g., also produces the error).

The first https://github.com/dominic998/SecurePoll-Test-Data/blob/main/test_data/20_6_5000_1301235635.blt and the second https://github.com/dominic998/SecurePoll-Test-Data/blob/main/test_data/20_7_5000_425367464.blt producing the same result, regardless if the winners are saved between rounds.

20_6_5000_1301235635.blt
Without saving winners:
Round 1: 1010
Round 2: 1010
Round 3: 
Round 4: 
Round 5: 1009,1010
Round 6: 1009,1010
Round 7: 1009,1010
Round 8: 1009,1010
Round 9: 1009,1010
Round 10: 1009,1010
Round 11: 1009,1010
Round 12: 1009,1010
Round 13: 1009,1010
Round 14: 1009,1010
Round 15: 1009,1010
Round 16: 1009,1010
Round 17: 1009,1010
Round 18: 1009,1010
Round 19: 1009,1010
Round 20: 1009,1010
Round 21: 1009,1010
Round 22: 1009,1010
Round 23: 1009,1010
Round 24: 1009,1010
Round 25: 1009,1010
Round 26: 1009,1010
Round 27: 1009,1010
Round 28: 1009,1010
Round 29: 1009,1010
Round 30: 1009,1010
Round 31: 1009,1010
Round 32: 1009,1010
Round 33: 1009,1010
Round 34: 1009,1010,1011,1012
With saving Winners: 
Round 1: 1010
Round 2: 1010
Round 3: 1010
Round 4: 1010
Round 5: 1010,1009
Round 6: 1010,1009
Round 7: 1010,1009
Round 8: 1010,1009
Round 9: 1010,1009
Round 10: 1010,1009
Round 11: 1010,1009
Round 12: 1010,1009
Round 13: 1010,1009
Round 14: 1010,1009
Round 15: 1010,1009
Round 16: 1010,1009
Round 17: 1010,1009
Round 18: 1010,1009
Round 19: 1010,1009
Round 20: 1010,1009
Round 21: 1010,1009
Round 22: 1010,1009
Round 23: 1010,1009
Round 24: 1010,1009
Round 25: 1010,1009
Round 26: 1010,1009
Round 27: 1010,1009
Round 28: 1010,1009
Round 29: 1010,1009
Round 30: 1010,1009
Round 31: 1010,1009
Round 32: 1010,1009
Round 33: 1010,1009
Round 34: 1010,1009,1011,1012

20_7_5000_425367464.blt
Without saving winners:
Round 1: 987,988,989,990,991,992
Round 2: 987,988,989,990,991,992
Round 3: 987,988,989,990,991,992
Round 4: 987,988,989,990,991,992
Round 5: 987,988,989,990,991,992
Round 6: 987,988,989,990,991,992
Round 7: 987,988,989,990,991,992
Round 8: 987,988,989,990,991,992
Round 9: 987,988,989,990,991,992
Round 10: 987,988,989,990,991,992
Round 11: 987,988,989,990,991,992
Round 12: 987,988,989,990,991,992
Round 13: 987,988,989,990,991,992
Round 14: 987,988,989,990,991,992
Round 15: 987,988,989,990,991,992
Round 16: 987,988,989,990,991,992
Round 17: 987,988,989,990,991,992
Round 18: 987,988,989,990,991,992
Round 19: 987,988,989,990,991,992
Round 20: 987,988,989,990,991,992
Round 21: 987,988,989,990,991,992
Round 22: 987,988,989,990,991,992
Round 23: 987,988,989,990,991,992
Round 24: 987,988,989,990,991,992
Round 25: 987,988,989,990,991,992
Round 26: 987,988,989,990,991,992
Round 27: 987,988,989,990,991,992
Round 28: 987,988,989,990,991,992
Round 29: 987,988,989,990,991,992
Round 30: 987,988,989,990,991,992
Round 31: 987,988,989,990,991,992
Round 32: 987,988,989,990,991,992
Round 33: 987,988,989,990,991,992
Round 34: 987,988,989,990,991,992
Round 35: 987,988,989,990,991,992
Round 36: 987,988,989,990,991,992
Round 37: 987,988,989,990,991,992
Round 38: 987,989,990,991,992
Round 39: 987,989,990,991,992
Round 40: 987,988,989,990,991,992
Round 41: 987,988,989,990,991,992
Round 42: 987,988,989,990,991,992
Round 43: 987,988,989,990,991,992
Round 44: 987,988,989,990,991,992
Round 45: 987,988,989,990,991,992
Round 46: 987,988,989,990,991,992
Round 47: 987,988,989,990,991,992
Round 48: 987,988,989,990,991,992
Round 49: 987,988,989,990,991,992
Round 50: 987,988,989,990,991,992
Round 51: 987,988,989,990,991,992
Round 52: 987,988,989,990,991,992
Round 53: 987,988,989,990,991,992
Round 54: 987,988,989,990,991,992
Round 55: 987,988,989,990,991,992
Round 56: 987,988,989,990,991,992
Round 57: 987,988,989,990,991,992
Round 58: 987,988,989,990,991,992
Round 59: 987,988,989,990,991,992
Round 60: 987,988,989,990,991,992
Round 61: 987,988,989,990,991,992
Round 62: 987,988,989,990,991,992
Round 63: 987,988,989,990,991,992
Round 64: 987,988,989,990,991,992
Round 65: 987,988,989,990,991,992
Round 66: 987,988,989,990,991,992
Round 67: 987,988,989,990,991,992
Round 68: 987,988,989,990,991,992
Round 69: 987,988,989,990,991,992
Round 70: 987,988,989,990,991,992
Round 71: 987,988,989,990,991,992
Round 72: 987,988,989,990,991,992
Round 73: 987,988,989,990,991,992
Round 74: 987,988,989,990,991,992
Round 75: 987,988,989,990,991,992
Round 76: 987,988,989,990,991,992
Round 77: 987,988,989,990,991,992
Round 78: 987,988,989,990,991,992
Round 79: 987,988,989,990,991,992
Round 80: 987,988,989,990,991,992
Round 81: 987,988,989,990,991,992
Round 82: 988,989,990,991,992
Round 83: 988,989,990,991,992
Round 84: 987,988,989,990,991,992
Round 85: 987,988,989,990,991,992,1006
With saving winners:
Round 1: 987,988,989,990,991,992
Round 2: 987,988,989,990,991,992
Round 3: 987,988,989,990,991,992
Round 4: 987,988,989,990,991,992
Round 5: 987,988,989,990,991,992
Round 6: 987,988,989,990,991,992
Round 7: 987,988,989,990,991,992
Round 8: 987,988,989,990,991,992
Round 9: 987,988,989,990,991,992
Round 10: 987,988,989,990,991,992
Round 11: 987,988,989,990,991,992
Round 12: 987,988,989,990,991,992
Round 13: 987,988,989,990,991,992
Round 14: 987,988,989,990,991,992
Round 15: 987,988,989,990,991,992
Round 16: 987,988,989,990,991,992
Round 17: 987,988,989,990,991,992
Round 18: 987,988,989,990,991,992
Round 19: 987,988,989,990,991,992
Round 20: 987,988,989,990,991,992
Round 21: 987,988,989,990,991,992
Round 22: 987,988,989,990,991,992
Round 23: 987,988,989,990,991,992
Round 24: 987,988,989,990,991,992
Round 25: 987,988,989,990,991,992
Round 26: 987,988,989,990,991,992
Round 27: 987,988,989,990,991,992
Round 28: 987,988,989,990,991,992
Round 29: 987,988,989,990,991,992
Round 30: 987,988,989,990,991,992
Round 31: 987,988,989,990,991,992
Round 32: 987,988,989,990,991,992
Round 33: 987,988,989,990,991,992
Round 34: 987,988,989,990,991,992
Round 35: 987,988,989,990,991,992
Round 36: 987,988,989,990,991,992
Round 37: 987,988,989,990,991,992
Round 38: 987,988,989,990,991,992
Round 39: 987,988,989,990,991,992
Round 40: 987,988,989,990,991,992
Round 41: 987,988,989,990,991,992
Round 42: 987,988,989,990,991,992
Round 43: 987,988,989,990,991,992
Round 44: 987,988,989,990,991,992
Round 45: 987,988,989,990,991,992
Round 46: 987,988,989,990,991,992
Round 47: 987,988,989,990,991,992
Round 48: 987,988,989,990,991,992
Round 49: 987,988,989,990,991,992
Round 50: 987,988,989,990,991,992
Round 51: 987,988,989,990,991,992
Round 52: 987,988,989,990,991,992
Round 53: 987,988,989,990,991,992
Round 54: 987,988,989,990,991,992
Round 55: 987,988,989,990,991,992
Round 56: 987,988,989,990,991,992
Round 57: 987,988,989,990,991,992
Round 58: 987,988,989,990,991,992
Round 59: 987,988,989,990,991,992
Round 60: 987,988,989,990,991,992
Round 61: 987,988,989,990,991,992
Round 62: 987,988,989,990,991,992
Round 63: 987,988,989,990,991,992
Round 64: 987,988,989,990,991,992
Round 65: 987,988,989,990,991,992
Round 66: 987,988,989,990,991,992
Round 67: 987,988,989,990,991,992
Round 68: 987,988,989,990,991,992
Round 69: 987,988,989,990,991,992
Round 70: 987,988,989,990,991,992
Round 71: 987,988,989,990,991,992
Round 72: 987,988,989,990,991,992
Round 73: 987,988,989,990,991,992
Round 74: 987,988,989,990,991,992
Round 75: 987,988,989,990,991,992
Round 76: 987,988,989,990,991,992
Round 77: 987,988,989,990,991,992
Round 78: 987,988,989,990,991,992
Round 79: 987,988,989,990,991,992
Round 80: 987,988,989,990,991,992
Round 81: 987,988,989,990,991,992
Round 82: 987,988,989,990,991,992
Round 83: 987,988,989,990,991,992
Round 84: 987,988,989,990,991,992
Round 85: 987,988,989,990,991,992,1006

So saving winners between rounds with those two examples does not affect the outcome of the votes. At least when tallying with a precision.

If I'm understanding the problem correctly, it's that a winner in an early round should show up in all subsequent rounds (and not go down in rank), but is occasionally dropped. Is that correct? If so, it looks to me like saving the winner is in fact fixing the issue? If I'm misunderstanding the problem, maybe someone could share a correct result for one or both of these files, even if it's fabricated, to help me understand the issue?

In T291821#9768759, @jsn.sherman wrote:

If I'm understanding the problem correctly, it's that a winner in an early round should show up in all subsequent rounds (and not go down in rank), but is occasionally dropped. Is that correct? If so, it looks to me like saving the winner is in fact fixing the issue? If I'm misunderstanding the problem, maybe someone could share a correct result for one or both of these files, even if it's fabricated, to help me understand the issue?

While developing the STV algorithm, we used OpenSTV as a reference program. It might be hard install on more modern operating systems, but this Dockerfile might help.

I realise I saved the OpenSTV results from the two files in the description. The very last line shows you the finally elected candidates:

• For 20_6_5000_1301235635.blt, see P16848 (your output may vary as tied candidates are selected at random by OpenSTV)
• For 20_7_5000_425367464.blt, see https://www.mediawiki.org/wiki/Anti-Harassment_Tools/SecurePoll_Improvements/Test_Results/20_7_5000_425367464/expected

In T291821#9745815, @jsn.sherman wrote:

Hi there, @TAdeleye_WMF asked if I could provide code review support on this, which I'm happy to do whenever there is a patch against the master branch. However, I don't have a clear way to reproduce the issue against master. Could @dom_walden or @Driedmueller offer me (a person with mediawiki experience, but no subject matter expertise for SVT polls) a concise way to reproduce the "declare winners" issue locally? I updated STVTallierTest_drw.php to the point where unit_test_stv.sh, but it eventually dies out (I'm assuming due to memory issues). Maybe an updated/smaller test file?...

The tally running indefinitely or running out of memory is a symptom of this bug, because a few candidates go from being elected in one round to being not elected in the next round to being elected in the next round and so on. It never gets enough elected candidates and so never finishes.

I didn't find a circumstance where such an election finishes and there are candidates who had been considered elected in an intermediate round but are not elected in the end. That is not to say it couldn't possibly happen.

Sadly, I couldn't reproduce this problem with a smaller file. You need enough votes for precision to be a problem.

@dom_walden thank you for the clarification! This makes me wonder: could switching from decimal to scientific notation be a 3rd solution if the formatting issues can be worked out?

Bringing in to TSP's sprint since we've been asked to look at it. (Thanks @TAdeleye_WMF for raising this.)

Change #1037491 had a related patch set uploaded (by Driedmueller; author: Driedmueller):

[mediawiki/extensions/SecurePoll@master] Dont recalculate winners from scratch each round Declared winners are stored between rounds

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

Change #1014053 abandoned by Driedmueller:

[mediawiki/extensions/SecurePoll@wmf/1.42.0-wmf.24] Dont recalculate winners from scratch each round

Reason:

Wrong target branch

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

Following a team conversation, it sounds like TSP shouldn't be tagged on this, but Moderator Tools just have a question for TSP about it. @TAdeleye_WMF will book a meeting to get that question answered.

I updated the existing phpunit test for tallying.
I added a comparison between the new declaredWinners array and elected winners end result array to the existing test. They have to be equal. This tests the added functionality.
However, there is no test case which could reproduce that an election outcome has been wrong without storing declared winners between rounds and would now be correct.
Im not able to create such a test case.
This bug seems to occur only on elections with thousands of votes.