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

[mediawiki/extensions/SecurePoll@master] Fix the elimination check in the STV algo

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

@STran helped me understand this better. We discussed in Slack about the possibility of adding BC and I am hesitant about us doing that at this point. We should go with whatever PHP's default is. If candidates 9, 10, 11 and 12 all achieved the same votes in a round according to PHP, we should eliminate them all. If 9 got more votes (by however much), we should not eliminate them.
We can probably not display this well in the UI but we can attempt to document this in all the necessary places and inform the election admins about this possibility.

In T289347#7298620, @gerritbot wrote:

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

[mediawiki/extensions/SecurePoll@master] Fix the elimination check in the STV algo

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

@STran Checking this out, I am seeing some weird behaviour.

This election (blt file) eliminates candidate 9 first, even though the resultsLog reports they have 205.00000000000304 votes compared to 205 for candidates 10, 11, 12.

Might this be due to the array_unique() function?

I have written a little patch for STVTallierTest which I think reproduces this bug, and includes a few other interesting cases. I hope you find it useful!

This was so useful. Thank you!!

I think I figured it out (thanks for the suggestion to investigate array_unique!):

• array_unique sees (float)205* as the same as (int)205 and therefore only passes through the first "205" it sees (actually 205.00000000000304)
• in the diff check abs( $ranked['total'] - $lowest ) < PHP_FLOAT_EPSILON, 9 fails because it's 205.00000000000304 - 205.00000000000304 = 0 while 10, 11, and 12 pass because it's 205.00000000000304 - 205 > epsilon

*actually 205.00000000000304

I had some trouble getting a ballot variant to distribute equally to 2 candidates to check if they would both be eliminated but I was able to "prove"** this by giving the one delayed vote to 10 and not running uasort (so that array_unique would see 9's (int)205 first.

**it did what I expected

Change 713963 merged by jenkins-bot:

[mediawiki/extensions/SecurePoll@master] Fix the elimination check in the STV algo

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

In T289347#7298747, @Niharika wrote:

@STran helped me understand this better. We discussed in Slack about the possibility of adding BC and I am hesitant about us doing that at this point. We should go with whatever PHP's default is. If candidates 9, 10, 11 and 12 all achieved the same votes in a round according to PHP, we should eliminate them all. If 9 got more votes (by however much), we should not eliminate them.
We can probably not display this well in the UI but we can attempt to document this in all the necessary places and inform the election admins about this possibility.

@Niharika Here is part of an answer which I hope is helpful.

I think there are 3 potential issues here. The first two refer to the issue of how we test for equality and are not necessarily related to whether or not we use bc. The third refers more generally to the issue of precision and might have a bearing on the decision to use bc.

Issue 1:

There seems to be an obvious bug here where a candidate with 205.00000000000304 votes is eliminated before a candidate with 205 votes.

This is obviously wrong. This should be fixed and I think Tran has identified the problem above.

Issue 2:

We are not treating the float 82.0 as equal to the int 82. In this case, the behaviour is unpredictable. Sometimes the float will be eliminated first, sometimes the int.

The above patch's solution to this is, when comparing $a and $b, to do: abs( $a - $b ) < PHP_FLOAT_EPSILON (PHP_FLOAT_EPSILON = 2.2204460492503E-16). I think this is quite a common solution when comparing floats.

Issue 3:

Why would some candidates have float 82.0 votes and other candidates int 82 votes?

The only time I have seen this is when a candidate has a very small (< 1) number of votes transferred to them. When this small number is added to the candidate's total votes there is some loss of precision, the small number is rounded to 0, and the total vote becomes float 82.0.

In this case, the candidate has arguably not had all their votes properly transferred to them. If someone were to audit the election and do their own calculations using arbitrary precision, they may get a number bigger than 82.0 and argue the candidate should not have been eliminated.

Unfortunately, the difference between what SecurePoll reports and what you might find when using arbitrary precision is not always less than PHP_FLOAT_EPSILON. Based on my own calculations, the biggest difference I have found so far is 7.275280E-14 (see here). I think it is a common issue with floating-point arithmetic that you cannot guarantee that errors will be within a certain bounds.

Moreover, even without doing your own calculations you might see some internal discrepancies in what SecurePoll reports. In the second example I gave in the description above, SecurePoll reports Candidate 9 "earned" ~5.15E-15 votes in round 3 but calculates their "total" votes as float 230.0 (see this output when dumping resultsLog).

I think this is because when we calculate "earned" votes we are often adding numbers of similar magnitude. When we are calculating "total" votes we are often adding numbers of different magnitudes. The latter is generally less precise than the former (although it can be unpredictable, for example, see here).

The biggest internal discrepancy I have seen between votes "earned" and "total" was ~1.35E-10 (see here).

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

[mediawiki/extensions/SecurePoll@master] Manually implement array_unique

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

Change 714416 merged by jenkins-bot:

[mediawiki/extensions/SecurePoll@master] Manually implement array_unique

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

The bugs in the description and T289347#7299771 are no longer reproducible.

Since this change QA has done various testing. See https://www.mediawiki.org/wiki/Anti-Harassment_Tools/SecurePoll_Improvements/Test_Results commit f06e679 and later.

There is more work to be done on eliminating tied candidates in T290027, and more testing will be done then.

Test Environment: Various, most recently https://vote.wikimedia.beta.wmflabs.org SecurePoll 3.0.0 (5374342) 06:11, 7 September 2021.