Page MenuHomePhabricator
Create Task
Maniphest T291821

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

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:

  1. 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).
  2. 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

SubjectRepoBranchLines +/-
Dont recalculate winners from scratch each roundmediawiki/extensions/SecurePollwmf/1.42.0-wmf.24+14 -3
Customize query in gerrit

Related Objects

Event Timeline

dom_walden created this task.Sep 27 2021, 10:35 AM
Restricted Application added a subscriber: Aklapper. · View Herald TranscriptSep 27 2021, 10:35 AM
dom_walden mentioned this in T290027: SecurePoll: Make sure tied candidates really are tied.Sep 27 2021, 10:35 AM
dom_walden updated the task description. (Show Details)
dom_walden updated the task description. (Show Details)Sep 27 2021, 10:50 AM
dom_walden updated the task description. (Show Details)Sep 29 2021, 11:57 AM
• Niharika moved this task from Untriaged to Triage/To be Estimated on the Anti-Harassment board.Oct 4 2021, 6:07 PM
• Niharika added subscribers: • TThoabala, STran, • Niharika.Oct 7 2021, 7:34 PM

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

phuedx moved this task from Triage/To be Estimated to Untriaged on the Anti-Harassment board.Oct 18 2021, 2:02 PM
phuedx moved this task from Untriaged to Triage/To be Estimated on the Anti-Harassment board.Oct 18 2021, 2:07 PM
• Niharika triaged this task as Medium priority.Oct 19 2021, 4:36 PM
ARamirez_WMF renamed this task from SecurePoll: Once a candidate is declared elected, make sure they remain elected to SecurePoll: Once a candidate is declared elected, make sure they remain elected [M].Oct 20 2021, 4:13 PM
ARamirez_WMF moved this task from Triage/To be Estimated to Cards ready for development on the Anti-Harassment board.
ARamirez_WMF renamed this task from SecurePoll: Once a candidate is declared elected, make sure they remain elected [M] to SecurePoll: Once a candidate is declared elected, make sure they remain elected [L].Oct 20 2021, 4:16 PM
ARamirez_WMF renamed this task from SecurePoll: Once a candidate is declared elected, make sure they remain elected [L] to SecurePoll: Once a candidate is declared elected, make sure they remain elected [M].Oct 20 2021, 4:27 PM
• Niharika moved this task from Cards ready for development to The Letter Song on the Anti-Harassment board.Oct 20 2021, 5:52 PM
• Niharika edited projects, added Anti-Harassment (The Letter Song); removed Anti-Harassment.
• Niharika edited projects, added Anti-Harassment; removed Anti-Harassment (The Letter Song).Nov 8 2021, 7:22 PM
jrbs raised the priority of this task from Medium to High.Sep 23 2022, 10:18 PM
jrbs moved this task from Backlog to Needs evaluation on the MediaWiki-extensions-SecurePoll board.
jrbs moved this task from Needs evaluation to Evaluated on the MediaWiki-extensions-SecurePoll board.
• Niharika moved this task from Untriaged to Triage/To be Estimated on the Anti-Harassment board.Dec 5 2022, 10:16 PM
jrbs subscribed.Jan 10 2023, 3:36 PM

Evaluation:

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

RamzyM-WMF subscribed.Sep 13 2023, 5:44 PM
Lhuyghe subscribed.Feb 19 2024, 1:04 PM
Driedmueller subscribed.EditedMar 4 2024, 10:28 AM

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?

jrbs moved this task from Evaluated to On deck on the MediaWiki-extensions-SecurePoll board.Mar 5 2024, 7:21 PM
dom_walden added a comment.Mar 7 2024, 4:48 PM
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.

dom_walden added a comment.Mar 8 2024, 8:44 AM

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.

T291821_getting_generateTestElection_to_work.patch403 BDownload

Driedmueller added a comment.Mar 11 2024, 9:20 AM

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?

dom_walden added a comment.Mar 11 2024, 1:58 PM
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).

Driedmueller added a comment.Mar 12 2024, 9:05 AM

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?

dom_walden added a comment.Mar 13 2024, 2:57 PM
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.

Driedmueller added a comment.EditedMar 20 2024, 1:34 PM

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.

dom_walden added a comment.Mar 21 2024, 2:31 PM
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 :).

Lhuyghe added a comment.Mar 22 2024, 7:48 AM

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.

gerritbot added a comment.Tue, Mar 26, 10:56 AM

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.Tue, Mar 26, 10:56 AM
Driedmueller added a comment.Tue, Mar 26, 11:03 AM
This comment was removed by Driedmueller.
jrbs mentioned this in T361077: Identify and implement a level of precision for STV elections.Wed, Mar 27, 1:17 AM
Content licensed under Creative Commons Attribution-ShareAlike (CC BY-SA) 4.0 unless otherwise noted; code licensed under GNU General Public License (GPL) 2.0 or later and other open source licenses. By using this site, you agree to the Terms of Use, Privacy Policy, and Code of Conduct. · Wikimedia Foundation · Privacy Policy · Code of Conduct · Terms of Use · Disclaimer · CC-BY-SA · GPL