Floating point arithmetic can result in different election results

[akazukin5151]

TLDR: the 1000th example of why floating point arithmetic is bad, in an excessively long post

Running the same election with starpy (Python) and Equal-Vote's star-core (Javascript) gives different results.

I am using these ballots from the star-core test cases, for STAR-PR:

https://github.com/Equal-Vote/star-core/blob/9a554932e4fc7ae9d6eb295fa1076437c812f5ce/src/Tests/pr.test.js#L105-L122

After spending an hour staring at two different debuggers simultaneously, I think the reason is because pandas in starpy somehow has different floating point behavior, causing a different candidate to be elected in the first round. This cascades throughout the end and we get a different election result overall.

Steps to reproduce

The ballot data is copied from star-core (JS) tests as linked above

# Paste in everything from https://github.com/Equal-Vote/starpy/blob/main/starpy/Allocated_Score.py here
b = [
    [0., 0., 3., 2., 3., 0., 2., 1.],
    [3., 2., 4., 4., 4., 3., 4., 2.],
    [3., 3., 2., 1., 2., 4., 3., 0.],
    [4., 3., 1., 2., 0., 4., 4., 2.],
    [4., 2., 1., 0., 2., 2., 1., 0.],
    [1., 0., 2., 1., 1., 1., 4., 2.],
    [3., 0., 3., 0., 2., 2., 0., 4.],
    [2., 0., 2., 4., 1., 3., 0., 2.],
    [1., 4., 0., 1., 1., 1., 2., 4.],
    [2., 3., 4., 2., 0., 2., 3., 3.],
    [0., 0., 3., 3., 0., 0., 2., 3.],
    [1., 2., 3., 4., 3., 3., 1., 4.],
    [2., 3., 0., 0., 2., 4., 4., 3.],
    [2., 1., 1., 1., 2., 1., 3., 0.],
    [1., 0., 4., 3., 1., 3., 0., 0.],
]

n_cands = 8
n_voters = 15
ballots = pd.DataFrame(b)
n_seats = 3
assert ballots.shape[1] >= n_seats
winners = Allocated_Score(5, n_seats, ballots)
print(winners)

The answer I get is [2, 6, 7]. This is 0-indexed so candidates 3, 7, and 8 are elected. This does not match the JS tests, where candidates 1, 3, and 7 are elected:

https://github.com/Equal-Vote/star-core/blob/9a554932e4fc7ae9d6eb295fa1076437c812f5ce/src/Tests/pr.test.js#L129

What is happening

Let's look at the normalized ballots. Each row is a voter and each column is a candidate. There are 15 voters and eight candidates for a 3 seat election:

      0    1    2    3    4    5    6    7
0   0.0  0.0  0.6  0.4  0.6  0.0  0.4  0.2
1   0.6  0.4  0.8  0.8  0.8  0.6  0.8  0.4
2   0.6  0.6  0.4  0.2  0.4  0.8  0.6  0.0
3   0.8  0.6  0.2  0.4  0.0  0.8  0.8  0.4
4   0.8  0.4  0.2  0.0  0.4  0.4  0.2  0.0
5   0.2  0.0  0.4  0.2  0.2  0.2  0.8  0.4
6   0.6  0.0  0.6  0.0  0.4  0.4  0.0  0.8
7   0.4  0.0  0.4  0.8  0.2  0.6  0.0  0.4
8   0.2  0.8  0.0  0.2  0.2  0.2  0.4  0.8
9   0.4  0.6  0.8  0.4  0.0  0.4  0.6  0.6
10  0.0  0.0  0.6  0.6  0.0  0.0  0.4  0.6
11  0.2  0.4  0.6  0.8  0.6  0.6  0.2  0.8
12  0.4  0.6  0.0  0.0  0.4  0.8  0.8  0.6
13  0.4  0.2  0.2  0.2  0.4  0.2  0.6  0.0
14  0.2  0.0  0.8  0.6  0.2  0.6  0.0  0.0

The first problem happens in column 2. We are summing to find the candidate with the highest score, so for column 2, we do this: 0.6+0.8+0.4+0.2+0.2+0.4+0.6+0.4+0.0+0.8+0.6+0.6+0.0+0.2+0.8.

starpy/starpy/Allocated_Score.py

Line 21 in 77e00d9

w = weighted_scores.sum().idxmax()

In JS, this is 6.599999999999999. In my Python debugger and script, it is also 6.599999999999999. However when pandas actually sums it up, it becomes 6.6.

Here's what my debugger session looks like:

> /home/me/star_pr.py(187)Allocated_Score()
-> w = weighted_scores.sum().idxmax()
(Pdb) weighted_scores.sum()
0    5.8
1    4.6
2    6.6
3    5.6
4    4.8
5    6.6
6    6.6
7    6.0
dtype: float64
(Pdb) weighted_scores.sum()[2]
6.6
(Pdb) type(weighted_scores.sum()[2])
<class 'numpy.float64'>
(Pdb) float(weighted_scores.sum()[2])
6.6
(Pdb) type(float(weighted_scores.sum()[2]))
<class 'float'>

Hence it is not an artifact of pandas/numpy rounding for printing.

Compare the sums with the sums in JS (emphasis mine):

[
    5.800000000000002,
    4.6,
    6.599999999999999,  // <--- #2
    5.6000000000000005,
    4.800000000000001,
    6.6,  // <--- #5
    6.6000000000000005,  // <--- #6
    5.999999999999999
]

(Setting a breakpoint here: https://github.com/Equal-Vote/star-core/blob/9a554932e4fc7ae9d6eb295fa1076437c812f5ce/src/StarResults.js#L442)

For comparison, normal Python sums column 5 to 6.6, and column 6 to 6.6000000000000005. So this is a problem with pandas/numpy

The consequences is that indices 2, 5, and 6 gets the same value of 6.6 in Python, but in JS they are all different. In JS, the highest score belongs to candidate 6, but since there is a tie in Python, it arbitrarily selects index 2.

Python elects index 2 then 6. JS elects index 6 then 2. But the error has cascaded too much for the final seat. The out of order election resulted in different re-weightings. See the debugging values:

Value	Candidate	JS	Python
split_point	7	0.8	3.0
spent_above	7	0	3.0
weight_on_split	7	4	2.0
split_point	3	0.6	0.6
spent_above	3	2.0	3.0
weight_on_split	3	4.0	4

Raw data (hopefully I transcribed it correctly)

js split_point for 7 is 0.8
python split_point for 3 is 0.6
js spent_above for 7 is 0

python spent_above for 3 is 3.0
js weight_on_split for 7 is 4

python weight_on_split for 3 is 4
python split_point for 7 is 0.6

js split_point for 3 is 0.6
python spent_above for 7 is 3.0

js spent_above for 3 is 2.0
python weight_on_split for 7 is 2.0

js weight_on_split for 3 is 4.0

The sum of scores at the end of the 2nd round is completely different, causing Python to elect candidate 8 and JS to elect candidate 1.

What can we do about this?

Some projects such as tallystick offers the ability to use exact representations for rational fractions, or fixed point decimals. (For example, Scottish Councils use 5 d.p. for STV)

I'm not engaged in the STAR project, but I think if the code is supposed to be a "gold standard" then it might be worth it to show that it is rigorous, production, and real world ready.

I know it's not easy to change something so fundamental, and I totally understand because I haven't bothered with more exact decimals in my own project too. But at least people can see this issue and evaluate this for their own needs. I might not need this issue to be fixed, but hopefully it will save time for someone else who does.

(I stumbled on to this issue, because I was going to use the JS tests to validate my own implementation. This has implications for #2 and #9 as the JS tests couldn't be simply copied to Python)

Misc

• Pandas 1.4.3 (the requirements.txt states pandas>=1.3.4)
• Numpy 1.24.2 (the requirements.txt states numpy>=1.21.4)
• Python 3.10.10
• 64-bit Linux

This issue is appropriate for this repo or the star-core repo, but I think this repo the most appropriate because only pandas shows this behavior

See also

• https://stackoverflow.com/questions/68536339/numpy-returns-unexpected-results-of-analytical-function/68537019#68537019
• https://stackoverflow.com/questions/59327454/why-does-python-round-this-sum
• https://stackoverflow.com/questions/30531925/tiny-numerical-difference-in-sum-of-squares-depending-on-numpy-procedure-call-us/30532839#30532839

[penyuan]

I really like how comprehensive your post is, @akazukin5151! Thank you! 👍🏼

I've used numpy before, but don't have the deep technical knowledge needed to fix the issue you described, hope others can chime in.

That said, I think a key, basic step we should take is to be upfront about this (possibly) rare issue in the documentation. Speaking of which, the README should probably be expanded into better documentation for this reference code. 😄

[akazukin5151]

I don't think it's fixable in numpy. I did some searches for "numpy exact decimal", "exact fraction", and "exact rational" with nothing relevant. Python does have a decimal and fraction types, but you lose the speed and terseness of numpy.

This is indeed a big change, so I agree that we should at least document it.

[penyuan]

Thanks, @akazukin5151 I think issues like this are particularly important for reference implementations like this repository.

Would you (and others) consider this to be a rare, but critical issue? Or might it happen quite often?

Yeah we probably can't directly fix this in numpy. But could there be a workaround for just this part using Python's internal functions? Would using Python itself (instead of an external library) make any difference?

[akazukin5151]

I think it is not rare but also not that critical. I have no evidence, but considering that you can observe floating point behavior with 0.1 + 0.2 = 0.30000000000000004, I think it is not rare. But averaging many situations together, it is "probably good enough". It depends on your use case. Actual governments using this will need all edge cases to be covered, but not everyone is a government. This example started because there was a tie, which should be rare in the real world. But all you need is a single tie and mistakes will cascade. Electing the wrong candidate does sound pretty serious to me, after all the point of investing in alternate electoral systems is better accuracy

My understanding of floating point arithmetic is that if you really need exact guarantees, you cannot rely on floating points [1]. So there's no point in using "a different float", it just makes different mistakes.

The decimal or fraction modules is in the Python standard library ("internal functions"/"using Python itself"), and they will fix it. But using plain Python floats instead of numpy floats won't make a difference.

Reading my post again, I think pandas/numpy is actually "more right" by using 6.6 instead of 6.599999999999999. But ultimately the ideal solution is to use fixed/infinite precision decimals in both Python and JS.

At least Python has it in the standard library, but JS would need an external library like decimal.js. On the other hand, the JS code is written with loops so I think it would mostly be a drop in replacement. The difficulty in fixing it in Python is because the code is written in a vectorized pandas style, which has to be rewritten to loops for the decimal type.

I'm surprised how much I've written. The code is not that long (simple implementation was one of the factors in choosing STAR after all), so it's possible to spend a week discussing it when it can be fixed in a few days. (I don't have time right now but I might consider later)

[1] https://softwareengineering.stackexchange.com/questions/382736/do-i-still-need-to-use-fixed-point-to-guarantee-computers-get-the-same-result-fo

[akazukin5151]

Voter satisfaction efficiency (VSE) appears to use floats as well, I wonder how much that affects results. Hopefully not significant enough!

[endolith]

First, floats are inherently imprecise and should not be used in applications where they need to be tested for equality, which is what ties are. The scores, number of candidates, number of winners, number of voters are all integers, so this algorithm is inherently based on rational numbers and should calculate using those ideally.

Second, the line:

        #Select winner
        w = weighted_scores.sum().idxmax()`

doesn't have any way to deal with ties. If there are multiple candidates with the same score at this point, it will always pick the first one in the list(?) Which could lead to a systemic bias if the candidates are arranged alphabetically. How should ties be handled?

If I print the results of each round, it looks like these are actually tied, even in the floating-point representation:

Weighted scores:
0    5.80000000000000159872
1    4.59999999999999964473
2    6.59999999999999964473 [tied]
3    5.59999999999999964473
4    4.80000000000000071054
5    6.59999999999999964473 [tied]
6    6.59999999999999964473 [tied]
7    5.99999999999999911182
dtype: object

Winner: 2

Weighted scores:
0    4.20000000000000017764
1    3.40000000000000079936
3    2.89999999999999991118
4    2.99999999999999955591
5    4.50000000000000000000
6    4.69999999999999928946 [highest, no ties]
7    3.79999999999999982236
dtype: object

Winner: 6

Weighted scores:
0    1.80000000000000004441
1    1.40000000000000013323
3    1.89999999999999991118
4    1.60000000000000008882
5    1.70000000000000017764
7    2.39999999999999991118 [highest, no ties]
dtype: object

Winner: 7
[2, 6, 7]

If I convert the code to use Python Fraction objects, the results are exact, but the tie still results in the same outcome:

Weighted scores 
0    29/5
1    23/5
2    33/5 [tied]
3    28/5
4    24/5
5    33/5 [tied]
6    33/5 [tied]
7       6
dtype: object

Winner: 2

Weighted scores 
0     21/5 = 4.20
1     17/5 = 3.40
3    29/10 = 2.90
4        3
5      9/2 = 4.50
6    47/10 = 4.70 [highest, no ties]
7     19/5 = 3.80
dtype: object

Winner: 6

Weighted scores 
0      9/5 = 1.80
1      7/5 = 1.40
3    19/10 = 1.90
4      8/5 = 1.60
5    17/10 = 1.70
7     12/5 = 2.40 [highest, no ties]
dtype: object

Winner: 7
[2, 6, 7]

But I think both issues need to be dealt with. Ties need to be handled somehow, and floats should not be used.

[endolith]

@akazukin5151

In JS, this is 6.599999999999999. In my Python debugger and script, it is also 6.599999999999999. However when pandas actually sums it up, it becomes 6.6.

Here's what my debugger session looks like:

> /home/me/star_pr.py(187)Allocated_Score()
-> w = weighted_scores.sum().idxmax()
(Pdb) weighted_scores.sum()
0    5.8
1    4.6
2    6.6
…

It's not really 6.6; it's actually 6.599999999999999644728632119950… They're just rounded for printing as a convenience (because floats are "close enough" data type). If you need to print it more precisely, though, you can add digits:

print("\nWeighted scores:\n", weighted_scores.sum().map('{:.20f}'.format))

[mikefranze]

If there are multiple candidates with the same score at this point, it will always pick the first one in the list(?) Which could lead to a systemic bias if the candidates are arranged alphabetically. How should ties be handled?

This hasn't been added to the python implementation yet, but how it's done in the JS version is we make a list of all candidates with the scores equal to the max score and pick randomly from that. Currently we don't have a better ties protocol for this method.

[mikefranze]

If I convert the code to use Python Fraction objects, the results are exact, but the tie still results in the same outcome:

Interesting, didn't know that existed. It looks like there's a Fraction library for JS too

[endolith]

If there are multiple candidates with the same score at this point, it will always pick the first one in the list(?) Which could lead to a systemic bias if the candidates are arranged alphabetically. How should ties be handled?

This hasn't been added to the python implementation yet, but how it's done in the JS version is we make a list of all candidates with the scores equal to the max score and pick randomly from that. Currently we don't have a better ties protocol for this method.

Ok. In my single winner implementation I have three options:

• return None in case of a tie at any stage
• always favor the lowest candidate id for deterministic reasons (but you can order the candidates randomly for fairness)
• break ties randomly (but may return different results when the same election is recounted)

I would suggest doing it the second way: Specify that the list of candidates be randomized before tabulating the election, and then favor the first one in the list in case of ties, so it's deterministic but fair?

[endolith]

Here I've got the version with Fraction objects: main...endolith:starpy:I_got_98.99999_problems

[tim-one]

Fraction objects are the way to go. Then, e.g., you could add the very valuable (for both internal documentation purposes and for catching logic errors) assertion that, at the start of a round the sum of the ballot weights is exactly equal to the quota times the number of winners remaining to be picked.

IMO it would be good to get away from numpy/Pandas here regardless. Their use greatly reduces the audience able to read the code, and buys approximately nothing worth getting: the code is not complex and the computational expense is minor, Simple pure-Python loops are more than up to the task of specifying the exact computation clearly.

[endolith]

Using Fraction objects removes the vectorization anyway.

Though the ballots are inherently a 2D object which pure Python doesn't really support, so removing numpy might actually make it less readable?

[larryhastings]

I agree with tim-one.

I used Fraction objects in my implementation:

https://github.com/larryhastings/starvote

It does slow things down a bit; I repurposed one of the bigger test elections I could download from https://star.vote/ to test Bloc STAR and Allocated Score, and there's a perceptible pause before it produces results. I don't think anybody would actually care about the performance impact, especially if you tell them "it's a little slower because it's 100% accurate".