SecurePoll: Once a candidate is declared elected, make sure they remain elected [M]
Open, HighPublicBUG REPORT
Actions

Assigned To

Authored By

	dom_walden
	Sep 27 2021, 10:35 AM

Description

What is the problem?

There are circumstances in which a candidate can be declared elected in one round but not be considered elected in a later round.

The declareWinners() method calculates the winners from scratch each time. In one round, if we have calculated the keep factor for a previously elected candidate in such a way that they have fewer votes than the quota, they will not be considered elected.

I can see at least two possible solutions:

Don't recalculate winners from scratch each round. For example, have an array of winners which we append to. declareWinners() only looks at candidates who are not already in this array. I think this is something OpenSTV does (see here).
Do some mathematical magic to make sure elected candidates are always declared elected by declareWinners(). This might be harder. Also, according to 2.9 in meekm.pdf, calculation of the keep factor can put elected candidates votes below the quota.

See T290027#7379765 for an example of where this is happening, where it leads to infinite recursion/iteration.

blt files to reproduce problem

Environment

Wiki(s): SecurePoll 3.0.0 (dcbad8c) 06:35, 27 September 2021.

Details

Related Changes in Gerrit:

Subject	Repo	Branch	Lines +/-
Once a candidate is declared elected, make sure they remain elected	mediawiki/extensions/SecurePoll	master	+427 K -251 K
Don't recalculate winners from scratch each round	mediawiki/extensions/SecurePoll	master	+22 -3
Use fixed-point arithmetic for the STV algorithm	mediawiki/extensions/SecurePoll	master	+16 K -27 K
Dont recalculate winners from scratch each round	mediawiki/extensions/SecurePoll	wmf/1.42.0-wmf.24	+14 -3

Customize query in gerrit

Related Objects

Mentioned In: T397934: Final round is sometimes not shown in STV election results
T397932: Increase precision in HTML report to 10
T387759: STV tally result displaying an incorrect summary if not all spots are filled
T361077: Identify and implement a level of precision for STV elections
T290027: SecurePoll: Make sure tied candidates really are tied
Mentioned Here: T397932: Increase precision in HTML report to 10
T397934: Final round is sometimes not shown in STV election results
T361077: Identify and implement a level of precision for STV elections
P16848 20_6_5000_1301235635_expected
T289185: Use bc in STV algorithm
rESPOd0dd97e02055: Localisation updates from https://translatewiki.net.
rESPOba9476b58d2d: Localisation updates from https://translatewiki.net.
T290027: SecurePoll: Make sure tied candidates really are tied
rESPOdcbad8ceecf5: Localisation updates from https://translatewiki.net.

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes

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

gerritbot added a project: Patch-For-Review.Mar 26 2024, 10:56 AM

Driedmueller added a comment.Mar 26 2024, 11:03 AM

This comment was removed by Driedmueller.

jrbs mentioned this in T361077: Identify and implement a level of precision for STV elections.Mar 27 2024, 1:17 AM

jsn.sherman added a project: Moderator-Tools-Team (Kanban).Apr 25 2024, 4:04 PM

jsn.sherman moved this task from Ready to Reviewed (waiting for changes) on the Moderator-Tools-Team (Kanban) board.

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.

Samwalton9-WMF moved this task from Reviewed (waiting for changes) to Eng review on the Moderator-Tools-Team (Kanban) board.Apr 30 2024, 4:04 PM

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.

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.

TAdeleye_WMF edited projects, added Trust and Safety Product Team (PM); removed Anti-Harassment-Team.May 14 2024, 4:29 PM

TAdeleye_WMF moved this task from PM to Needs Triage on the Trust and Safety Product Team board.May 14 2024, 4:30 PM

TAdeleye_WMF edited projects, added Trust and Safety Product Team; removed Trust and Safety Product Team (PM).

@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.)

Tchanders moved this task from Priority Backlog to Ready on the Trust and Safety Product Sprint (Sprint Shekere (13th May - 24th May)) board.May 16 2024, 3:51 PM

Samwalton9-WMF removed a project: Moderator-Tools-Team (Kanban).May 16 2024, 4:16 PM

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

Dreamy_Jazz moved this task from Sprint Shekere (13th May - 24th May) to Sprint Melodica (Jun 3 - Jun 14) on the Trust and Safety Product Sprint board.Jun 3 2024, 10:12 AM

Dreamy_Jazz edited projects, added Trust and Safety Product Sprint (Sprint Melodica (Jun 3 - Jun 14)); removed Trust and Safety Product Sprint (Sprint Shekere (13th May - 24th May)).

Dreamy_Jazz moved this task from Priority Backlog to Needs Review on the Trust and Safety Product Sprint (Sprint Melodica (Jun 3 - Jun 14)) board.

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.

Samwalton9-WMF moved this task from Inbox to Triaged on the Moderator-Tools-Team board.Aug 22 2024, 2:01 PM

Amdrel subscribed.Jan 23 2025, 11:07 PM

Restricted Application added a project: Trust and Safety Product Team. · View Herald TranscriptJan 23 2025, 11:07 PM

Change #1114474 had a related patch set uploaded (by Amdrel; author: Amdrel):

[mediawiki/extensions/SecurePoll@master] Use fixed-point arithmetic for the STV algorithm

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

I found that the infinite loop issue goes away if I change the tallier to use fixed-point arithmetic instead of floats. I get the same winners as OpenSTV for 20_6_5000_1301235635.blt and 20_7_5000_425367464.blt, with the exception being the randomly chosen winners in the first ballot. The Gerrit patch I just uploaded changes the tallier to use bc functions with a scale of 9 to accomplish this. A couple of existing tests are broken with this patch since the number of rounds needed to complete the tally shrunk, but the winners and eliminated assertions are still passing.

I noticed that there's an existing ticket that calls for this, so I referenced both this ticket and the other one in the patch (https://phabricator.wikimedia.org/T289185). I did not have to incorporate the logic to remember declared winners to get these ballots working. Assuming that this approach of switching over to fixed-point arithmetic is sound, is that still a change we want to make as well?

imo if fixed point arithmetic solves it in all situations, that's even better. Reading through all the related tickets around this situation, it does sound like rounding errors tend to be the cause of our edge case woes. I'm not sure if this resolves this edge case:

Also, according to 2.9 in meekm.pdf, calculation of the keep factor can put elected candidates votes below the quota.

which also may be a precision situation but I think we try this out for now and if QA or live finds another situation where this problem persists, we can revisit. ~~Your patch also I think solves this ticket? T361077: Identify and implement a level of precision for STV elections~~

kostajh assigned this task to Amdrel.Jan 29 2025, 10:43 AM

kostajh added a project: Trust and Safety Product Sprint (Sprint Tuba (Jan 20 - Feb 7)).

kostajh moved this task from Ready for development to Actively working on the MediaWiki-extensions-SecurePoll board.

Change #1114474 merged by jenkins-bot:

[mediawiki/extensions/SecurePoll@master] Use fixed-point arithmetic for the STV algorithm

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

kostajh edited projects, added Trust and Safety Product Sprint (Sprint Hurdy-Gurdy (Feb 10 - Feb 28)); removed Trust and Safety Product Sprint (Sprint Tuba (Jan 20 - Feb 7)).Feb 10 2025, 10:01 AM

• mszabo moved this task from Priority Backlog to Needs QA on the Trust and Safety Product Sprint (Sprint Hurdy-Gurdy (Feb 10 - Feb 28)) board.Feb 10 2025, 12:50 PM

@Amdrel I have been comparing the results of SecurePoll with OpenSTV.

I made a fork of OpenSTV which implements the same strong tie-break method we implement.

In that repository is create_test_data.py which will generate a random .blt file and .json file which can be used in tests/phpunit/unit/fixtures.

I wrote a modified STVTallierTest.php to work with the generated .json files. It uses assertEqualsWithDelta to compare numbers, and I have to set the delta to 0.00001. Anything smaller will cause lots of failures. Is that OK? Considering we are using bc with a precision of 10, 0.00001 seems a big delta to me. I don't know what we should expect, though.

Do we need to change what we are adding to the droop quota from 0.000001 to 0.0000000001?

Samwalton9-WMF removed a project: Moderator-Tools-Team.Feb 18 2025, 10:22 PM

In T291821#10559872, @dom_walden wrote:

Do we need to change what we are adding to the droop quota from 0.000001 to 0.0000000001?

According to https://web.archive.org/web/20210225045400/https://prfound.org/resources/reference/reference-meek-rule/ (this link is mentioned in the tally page, rounds table section)

Adding to the droop quota should be 1/(10^9).

I believe this should solve the delta precision mentioned above, which should be 1/(10^6) from my understanding.

Dreamy_Jazz moved this task from Sprint Hurdy-Gurdy (Feb 10 - Feb 28) to Sprint Lemon Meringue (March 3 - 21) on the Trust and Safety Product Sprint board.Mar 3 2025, 3:45 PM

Dreamy_Jazz edited projects, added Trust and Safety Product Sprint (Sprint Lemon Meringue (March 3 - 21)); removed Trust and Safety Product Sprint (Sprint Hurdy-Gurdy (Feb 10 - Feb 28)).

Dreamy_Jazz moved this task from Priority Backlog to Needs QA on the Trust and Safety Product Sprint (Sprint Lemon Meringue (March 3 - 21)) board.

STran mentioned this in T387759: STV tally result displaying an incorrect summary if not all spots are filled.Mar 3 2025, 5:13 PM

Tchanders edited projects, added Trust and Safety Product Sprint (Sprint Chocolate Cake (March 24 - April 11)); removed Trust and Safety Product Sprint (Sprint Lemon Meringue (March 3 - 21)).Mar 24 2025, 2:21 PM

Tchanders moved this task from Priority Backlog to Needs QA on the Trust and Safety Product Sprint (Sprint Chocolate Cake (March 24 - April 11)) board.

In T291821#10584442, @Mimurawil wrote:

In T291821#10559872, @dom_walden wrote:

Do we need to change what we are adding to the droop quota from 0.000001 to 0.0000000001?

According to https://web.archive.org/web/20210225045400/https://prfound.org/resources/reference/reference-meek-rule/ (this link is mentioned in the tally page, rounds table section)

Adding to the droop quota should be 1/(10^9).

I believe this should solve the delta precision mentioned above, which should be 1/(10^6) from my understanding.

@Mimurawil Thanks. Will this change be made in this task or should I create another one?

In T291821#10692972, @dom_walden wrote:

@Mimurawil Thanks. Will this change be made in this task or should I create another one?

I think we can use this task. I'll make some changes and start testing tomorrow.

I'm logging some discoveries while testing my changes.

So, by increasing the decimal addition to the droop quota to 1/(10^9), I noticed the original bug in this ticket, where an elected candidate would be eliminated in a later round.

This can be observed when testing the fixture TiedEliminationMidElection.json, producing:

{
    "elected": [
        984,
        985,
        986,     <--- elected
        987,
        988
    ],
    "eliminated": [
        1002,
        1003,
        989,
        990,
        991,
        992,
        993,
        994,
        995,
        996,
        997,
        998,
        999,
        1000,
        1001,
        986     <--- eliminated
    ],
...

Another observed issue was that this scenario above only had 4 seats available, and the original fixture file was only mentioning 3 elected candidates (see below):

	{
		"elected": [
			984,
			985,
			986     <--- candidate 987 should be here as well
		],
		"eliminated": [
			1002,
			1003,
			989,
			990,
			991,
			992,
			993,
			994,
			995,
			996,
			997,
			998,
			999,
			1000,
			1001,
			987,
			988
		],
...

Most of the test fixtures broke because of new calculation (changed from 1/(10^6) to 1/(10^9) so only the round values were affected. The scenario above was an edge case where I believe the fixture had an incorrect result.

Also good to note that, in the fixture above, the candidate 988 was also elected after the initial change, this happened because both 987 and 988 were elected in the same round (another scenario we need to account for).

I believe I've found a fix for those bugs. I'm currently testing & re-adjusting the fixture files. I think I'll be able to create a patch as soon as I finish passing through all the fixtures.

Change #1136004 had a related patch set uploaded (by Mimurawil; author: Mimurawil):

[mediawiki/extensions/SecurePoll@master] Once a candidate is declared elected, make sure they remain elected

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

kostajh edited projects, added Trust and Safety Product Sprint (Sprint Cozonac (April 14 - May 2)); removed Trust and Safety Product Sprint (Sprint Chocolate Cake (March 24 - April 11)).Apr 14 2025, 2:52 PM

kostajh moved this task from Priority Backlog to Needs QA on the Trust and Safety Product Sprint (Sprint Cozonac (April 14 - May 2)) board.

• mszabo edited projects, added Trust and Safety Product Sprint (Sprint Key Lime Pie (May 5 - May 23)); removed Trust and Safety Product Sprint (Sprint Cozonac (April 14 - May 2)).May 3 2025, 11:43 PM

• mszabo moved this task from Priority Backlog to Needs QA on the Trust and Safety Product Sprint (Sprint Key Lime Pie (May 5 - May 23)) board.

Change #1136004 merged by jenkins-bot:

[mediawiki/extensions/SecurePoll@master] Once a candidate is declared elected, make sure they remain elected

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

ReleaseTaggerBot added a project: MW-1.44-notes (1.44.0-wmf.28; 2025-05-06).May 4 2025, 12:00 AM

Change #1037491 abandoned by Kosta Harlan:

[mediawiki/extensions/SecurePoll@master] Don't recalculate winners from scratch each round

Reason:

No longer needed

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

Maintenance_bot removed a project: Patch-For-Review.May 7 2025, 12:31 PM

@Amdrel I am comparing how the results look on the tally page on beta before and after, and am seeing some discrepancies.

For example, 5_3_2679 before:

Screen Shot 2025-05-21 at 09.39.51.png (868×710 px, 100 KB)

after:

Screen Shot 2025-05-21 at 09.40.02.png (541×690 px, 59 KB)

The quota and votes for candidates A and B don't exactly match. I think possibly just because we need to update the precision on the tally page to reflect above changes. @STran will know more.

Also notice how before we had a final round where Candidate A is explicitly elected. We no longer seem to do that and it might look as if they are being elected with ~509 votes when the quota is ~669.

Different numbers of rounds I hope is expected.

A few other examples:

4_2_104_839775172 before and after (archive)
4_2_104_388762016 before and after (archive)

I have seen a few cases where the candidates elected before and after this change are different. I think they are due to the changes in precision.

12_9_4996_1067098093: before, after (archive). Running the same election in OpenSTV will only elect candidate 9 when I set the precision to 15 or more.[1]
12_9_5000_179685718: before, after (archive). OpenSTV only elects candidate 10 if precision is 17 or greater.
12_9_5000_1830523430: before, after (archive). OpenSTV only elects candidate 9 if precision 17 or greater.

Notes

Using my fork of OpenSTV and running python2 openstv/runElection.py -t all -w strong -p <precision> MeekSTV <blt file>. Test data can be found here.

kostajh edited projects, added Trust and Safety Product Sprint (Sprint Carrot Cake (May 26 - June 13)); removed Trust and Safety Product Sprint (Sprint Key Lime Pie (May 5 - May 23)).May 25 2025, 6:53 PM

kostajh moved this task from Priority Backlog to Needs QA on the Trust and Safety Product Sprint (Sprint Carrot Cake (May 26 - June 13)) board.

The quota and votes for candidates A and B don't exactly match. I think possibly just because we need to update the precision on the tally page to reflect above changes. @STran will know more.

Also notice how before we had a final round where Candidate A is explicitly elected. We no longer seem to do that and it might look as if they are being elected with ~509 votes when the quota is ~669.

Good catch. That might just be a rendering bug but we should definitely be showing that last round.

I have seen a few cases where the candidates elected before and after this change are different. I think they are due to the changes in precision.

I cannot view the after results since I don't have an account on beta votewiki, though I can see the before results since they're on a user page. If I can see both then it will be easier for me to troubleshoot this.

In T291821#10888529, @Amdrel wrote:

I cannot view the after results since I don't have an account on beta votewiki, though I can see the before results since they're on a user page. If I can see both then it will be easier for me to troubleshoot this.

Sorry. I have edited my above comments to include links to the after results in a user page. Let me know if you want me to create you an account on beta votewiki.

Sorry. I have edited my above comments to include links to the after results in a user page.

Thank you for the new links! I'm going to debug these some more. Here's what I noticed so far:

12_9_4996_1067098093: It appears like candidate 9 gets elected arbitrarily even though 10, 11, and 12 have the same amount of votes. I don't see any vote transferring to 9 so I'll debug why the seat is being filled when it should not.
12_9_5000_179685718: I don't see anything obviously wrong with this one unlike the previous one. I'm going to see if tweaking the precision on our end leads to different results. I'm seeing some very small vote transfers for candidates 9 and 10 in the newer tally that aren't in the previous version. I'm wondering if those transfers did happen in the old implementation, but due to the minuscule numbers involved no change happened to the floating point numbers, thereby making them not render in the summary.
12_9_5000_1830523430: It looks like whatever if affecting 12_9_4996_1067098093 is affecting this result as well.

Let me know if you want me to create you an account on beta votewiki.

I would appreciate that, thank you!

After investigating 12_9_4996_1067098093 I believe the new result may actually be more correct. Candidate 9 does appear to have slightly more votes because there is single ballot with multiple candidates chosen 1 1 2 3 4 5 6 7 8 9 0 in the .blt file that includes candidate 9 in it. Candidate 9 has the same amount of single votes as 10 11 and 12 do. The votes from the referenced ballot get added to candidate 9 during round 2. I suspect what may have happened was the previous implementation using floating point numbers was unable to account for the extra low ranked vote. I would have to debug the old version to compare to be sure, but the fact that OpenSTV can reproduce this result with 15 points of precision may make sense if this is the case, though 10 points of precision should have been enough which seems odd to me.

As for why OpenSTV and our implementation behave differently with the same precision configured I am not sure yet. If I recall correctly OpenSTV uses fixed numbers as well, though it does it using integers rather than the Decimal type that Python provides, but it should be fine. Perhaps there's a quirk in the implementation due to something like an implicit type conversion happening, which can happen with integers in Python with certain operations? 10 points of precision should be just enough to tell 247.0000000000 and 247.0000000001 apart.

Regardless it is a bit confusing that it looks like a single candidate with the same amount of votes is chosen over others in the HTML view. Changing the HTML view to display 10 points of precision instead of 6 like it does now should make this more apparent.

kostajh edited projects, added Trust and Safety Product Sprint (Sprint Baklava (June 16 - July 4)); removed Trust and Safety Product Sprint (Sprint Carrot Cake (May 26 - June 13)).Jun 16 2025, 6:12 AM

kostajh moved this task from Priority Backlog to Needs QA on the Trust and Safety Product Sprint (Sprint Baklava (June 16 - July 4)) board.

It looks like all of the ballots have the same root cause.

dom_walden mentioned this in T397932: Increase precision in HTML report to 10.Jun 26 2025, 1:55 PM

dom_walden mentioned this in T397934: Final round is sometimes not shown in STV election results.Jun 26 2025, 2:06 PM

Further to the above discussion, I have raised two bugs for follow up work:

Therefore, I will move this into Done.

Niharika closed this task as Resolved.Jun 30 2025, 4:15 PM

Re-opening this, as the fix applied short-circuited the algorithm and filled seats whenever the number of available seats exceeded the number of remaining candidates, causing the ambiguity in T397934: Final round is sometimes not shown in STV election results. This was reverted and we should try to fix this so that the algorithm naturally elects candidates as they meet quota.

STran moved this task from Actively working to Ready for development on the MediaWiki-extensions-SecurePoll board.Jul 11 2025, 3:33 PM

STran removed a project: Trust and Safety Product Sprint (Sprint Baklava (June 16 - July 4)).

OKryva-WMF edited projects, added Product Safety and Integrity; removed Trust and Safety Product Team.Oct 24 2025, 3:22 PM

OKryva-WMF moved this task from Inbox to Triaged (backlog) on the Product Safety and Integrity board.

	F60339073: Screen Shot 2025-05-21 at 09.40.02.png
	May 21 2025, 8:48 AM

	F60339068: Screen Shot 2025-05-21 at 09.39.51.png
	May 21 2025, 8:48 AM

	F58506026: Screenshot 2025-02-26 at 10.26.52 AM.png
	Feb 26 2025, 6:36 PM

	F42461072: T291821_getting_generateTestElection_to_work.patch
	Mar 8 2024, 8:44 AM

SecurePoll: Once a candidate is declared elected, make sure they remain elected [M]Open, HighPublicBUG REPORTActions