Re: Schulze STV bugs and updated results (was: Re: Preliminary Droop-fit proportionality results)
Toby Pereira via Election-Methods <[email protected]> Wed, 17 Jun 2026 23:20:27 +0000 (UTC)
| Newsgroups | gmane.politics.election-methods |
|---|---|
| Message-ID | <[email protected]> |
--===============1902131721127504205==
Content-Type: multipart/alternative;
boundary="----=_Part_4817614_1723800003.1781738427895"
------=_Part_4817614_1723800003.1781738427895
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Thanks to Kristofer for doing this extra work to sort out the error and ap=
ologies to Etjon for the result it caused!
Toby
On Wednesday, 17 June 2026 at 22:03:13 BST, Etjon Basha <etjonbasha@gma=
il.com> wrote: =20
=20
Boo!
On Thu, 18 June 2026, 12:28=E2=80=AFam Kristofer Munsterhjelm, <km-elmet@mu=
nsterhjelm.no> wrote:
On 2026-06-02 23:11, Toby Pereira wrote:
> I see yes, thanks. In that case, Schulze STV seems to do pretty=20
> terribly, not just a bit worse than other STV methods. And looking at=20
> your whole list, considerably worse than things like (Bloc) Borda! It's=
=20
> definitely not broken in your simulation?
I added some tests to Schulze STV and found an election where quadelect=20
would return the wrong outcome.
The bug appears to have been caused by undefined behavior in Schulze's=20
own code, where a line does something that has no clear order of=20
execution, and different compilers resolve the ambiguity differently. I=20
tested Schulze's prog01 compiled with a modern gcc and got the same bug.
After fixing the bug, I tested the example elections referenced in=20
"Implementing the Schulze STV Method"[1], table 2, and the Schulze STV=20
code used by my simulator now gives the correct outcome - i.e. the ones=20
listed in the paper - for all of them.
I then ran my multiwinner simulations and got much better results.=20
Sorry, Etjon :-)
Droop spatial proportionality:
Two seats, 10 candidates, 14400 elections:
Name=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Droop goodness-of-fit VSE
Meek/Warren=C2=A0 =C2=A0 0.7932
Harmonic (S-L) 0.9254
Schulze STV=C2=A0 =C2=A0 0.9997
Three seats:
Warren=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A00.8712
Meek=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A00.8713
Harmonic (S-L) 0.8925
Schulze STV=C2=A0 =C2=A0 0.9992
Four seats:
Harmonic (S-L) 0.8880
Warren=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A00.9184
Meek=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A00.9185
Schulze STV=C2=A0 =C2=A0 0.9954
Five seats:
Harmonic (S-L) 0.8809
Warren=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A00.9426
Meek=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A00.9428
Schulze STV=C2=A0 =C2=A0 0.9874
Six seats:
Harmonic (S-L) 0.8779
Meek=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A00.9598
Warren=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A00.9598
Schulze STV=C2=A0 =C2=A0 0.9758
Nine seats:
Harmonic (S-L) 0.9450
Schulze STV=C2=A0 =C2=A0 0.9497
Meek=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A00.9979
Warren=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A00.9980
The quantile fits for two out of ten are (288k elections):
Name=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Prop. quantile=C2=A0 =C2=A0 Go=
odness-of-fit VSE
Schulze STV=C2=A0 =C2=A0 0.3377=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 0.=
9961
Harmonic (S-L) 0.3498=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 0.9223
Meek/Warren=C2=A0 =C2=A0 0.3344=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 0.=
8090
and for the 2-of-4 CFC-Kemeny comparison (5760 elections):
Name=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Prop. quantile=C2=A0 =C2=A0 Go=
odness-of-fit VSE
Harmonic (S-L) 0.3317=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 0.9414
Meek/Warren=C2=A0 =C2=A0 0.3321=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 0.=
9602
Schulze STV=C2=A0 =C2=A0 0.3345=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 0.=
9989
CFC-Kemeny=C2=A0 =C2=A0 =C2=A00.2493=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 0.9998
as well as 2-of-5 (7200 elections):
Name=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Prop. quantile=C2=A0 =C2=A0 Go=
odness-of-fit VSE
Meek/Warren=C2=A0 =C2=A0 0.3346=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 0.=
9208
Harmonic (S-L) 0.3383=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 0.9294
CFC-Kemeny=C2=A0 =C2=A0 =C2=A00.2441=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 0.9967
Schulze STV=C2=A0 =C2=A0 0.3371=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 0.=
9967
So Schulze STV seems to be pretty good, but its margin over other=20
methods shrinks as seats/candidates ratio increases, to the point where=20
Meek and Warren beats it with nine seats.
Perhaps this has something to do with how Schulze STV's main calculation=20
is on sets that differ by one candidate, that it then uses widest path=20
to extrapolate; if there are more winners, such paths may have more=20
steps. But I don't know for sure.
I also found a few crash-inducing memory access bugs in Schulze's=20
implementation, but the code is difficult enough to understand that I'm=20
unsure how to fix them. I'll probably give more details in another post.
-km
[1]=20
https://sites.math.duke.edu/~bray/Courses/49s/Additional%20Reading/Schulze/=
Schulze3/schulze3.pdf
=20
------=_Part_4817614_1723800003.1781738427895
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<html><head></head><body><div class=3D"ydpe683d128yahoo-style-wrap" style=
=3D"font-family:Helvetica Neue, Helvetica, Arial, sans-serif;font-size:16px=
;"><div></div>
<div>Thanks to Kristofer for doing this extra work to sort out the =
error and apologies to Etjon for the result it caused!</div><div><br></div>=
<div>Toby</div><div><br></div>
=20
<div id=3D"ydpe683d128yahoo_quoted_1946867732" class=3D"ydpe683d128=
yahoo_quoted">
<div style=3D"font-family:'Helvetica Neue', Helvetica, Arial, s=
ans-serif;font-size:13px;color:#26282a;">
=20
<div>
On Wednesday, 17 June 2026 at 22:03:13 BST, Etjon B=
asha <[email protected]> wrote:
</div>
<div><br></div>
<div><br></div>
=20
=20
<div><div id=3D"ydpe683d128yiv6118367402"><div><div>Boo!</d=
iv><br clear=3D"none"><div id=3D"ydpe683d128yiv6118367402yqt68748" class=3D=
"ydpe683d128yiv6118367402yqt0092689017"><div class=3D"ydpe683d128yiv6118367=
402gmail_quote ydpe683d128yiv6118367402gmail_quote_container"><div dir=3D"l=
tr" class=3D"ydpe683d128yiv6118367402gmail_attr">On Thu, 18 June 2026, 12:2=
8=E2=80=AFam Kristofer Munsterhjelm, <<a shape=3D"rect" href=3D"mailto:k=
[email protected]" rel=3D"nofollow" target=3D"_blank">km-elmet@munste=
rhjelm.no</a>> wrote:<br clear=3D"none"></div><blockquote style=3D"margi=
n:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;" class=3D"ydpe683=
d128yiv6118367402gmail_quote">On 2026-06-02 23:11, Toby Pereira wrote:<br c=
lear=3D"none">
> I see yes, thanks. In that case, Schulze STV seems to do pretty <br cl=
ear=3D"none">
> terribly, not just a bit worse than other STV methods. And looking at =
<br clear=3D"none">
> your whole list, considerably worse than things like (Bloc) Borda! It'=
s <br clear=3D"none">
> definitely not broken in your simulation?<br clear=3D"none">
<br clear=3D"none">
I added some tests to Schulze STV and found an election where quadelect <br=
clear=3D"none">
would return the wrong outcome.<br clear=3D"none">
<br clear=3D"none">
The bug appears to have been caused by undefined behavior in Schulze's <br =
clear=3D"none">
own code, where a line does something that has no clear order of <br clear=
=3D"none">
execution, and different compilers resolve the ambiguity differently. I <br=
clear=3D"none">
tested Schulze's prog01 compiled with a modern gcc and got the same bug.<br=
clear=3D"none">
<br clear=3D"none">
After fixing the bug, I tested the example elections referenced in <br clea=
r=3D"none">
"Implementing the Schulze STV Method"[1], table 2, and the Schulze STV <br =
clear=3D"none">
code used by my simulator now gives the correct outcome - i.e. the ones <br=
clear=3D"none">
listed in the paper - for all of them.<br clear=3D"none">
<br clear=3D"none">
I then ran my multiwinner simulations and got much better results. <br clea=
r=3D"none">
Sorry, Etjon :-)<br clear=3D"none">
<br clear=3D"none">
Droop spatial proportionality:<br clear=3D"none">
<br clear=3D"none">
Two seats, 10 candidates, 14400 elections:<br clear=3D"none">
<br clear=3D"none">
Name Droop goodness-of-fit VSE<br c=
lear=3D"none">
Meek/Warren 0.7932<br clear=3D"none">
Harmonic (S-L) 0.9254<br clear=3D"none">
Schulze STV 0.9997<br clear=3D"none">
<br clear=3D"none">
Three seats:<br clear=3D"none">
<br clear=3D"none">
Warren 0.8712<br clear=3D"none">
Meek 0.8713<br clear=3D"none">
Harmonic (S-L) 0.8925<br clear=3D"none">
Schulze STV 0.9992<br clear=3D"none">
<br clear=3D"none">
Four seats:<br clear=3D"none">
<br clear=3D"none">
Harmonic (S-L) 0.8880<br clear=3D"none">
Warren 0.9184<br clear=3D"none">
Meek 0.9185<br clear=3D"none">
Schulze STV 0.9954<br clear=3D"none">
<br clear=3D"none">
Five seats:<br clear=3D"none">
<br clear=3D"none">
Harmonic (S-L) 0.8809<br clear=3D"none">
Warren 0.9426<br clear=3D"none">
Meek 0.9428<br clear=3D"none">
Schulze STV 0.9874<br clear=3D"none">
<br clear=3D"none">
Six seats:<br clear=3D"none">
<br clear=3D"none">
Harmonic (S-L) 0.8779<br clear=3D"none">
Meek 0.9598<br clear=3D"none">
Warren 0.9598<br clear=3D"none">
Schulze STV 0.9758<br clear=3D"none">
<br clear=3D"none">
Nine seats:<br clear=3D"none">
<br clear=3D"none">
Harmonic (S-L) 0.9450<br clear=3D"none">
Schulze STV 0.9497<br clear=3D"none">
Meek 0.9979<br clear=3D"none">
Warren 0.9980<br clear=3D"none">
<br clear=3D"none">
<br clear=3D"none">
The quantile fits for two out of ten are (288k elections):<br clear=3D"none=
">
<br clear=3D"none">
Name Prop. quantile Go=
odness-of-fit VSE<br clear=3D"none">
Schulze STV 0.3377 0.=
9961<br clear=3D"none">
Harmonic (S-L) 0.3498 0.9223<br cl=
ear=3D"none">
Meek/Warren 0.3344 0.=
8090<br clear=3D"none">
<br clear=3D"none">
and for the 2-of-4 CFC-Kemeny comparison (5760 elections):<br clear=3D"none=
">
<br clear=3D"none">
Name Prop. quantile Go=
odness-of-fit VSE<br clear=3D"none">
Harmonic (S-L) 0.3317 0.9414<br cl=
ear=3D"none">
Meek/Warren 0.3321 0.=
9602<br clear=3D"none">
Schulze STV 0.3345 0.=
9989<br clear=3D"none">
CFC-Kemeny 0.2493 &nbs=
p; 0.9998<br clear=3D"none">
<br clear=3D"none">
as well as 2-of-5 (7200 elections):<br clear=3D"none">
<br clear=3D"none">
Name Prop. quantile Go=
odness-of-fit VSE<br clear=3D"none">
Meek/Warren 0.3346 0.=
9208<br clear=3D"none">
Harmonic (S-L) 0.3383 0.9294<br cl=
ear=3D"none">
CFC-Kemeny 0.2441 &nbs=
p; 0.9967<br clear=3D"none">
Schulze STV 0.3371 0.=
9967<br clear=3D"none">
<br clear=3D"none">
So Schulze STV seems to be pretty good, but its margin over other <br clear=
=3D"none">
methods shrinks as seats/candidates ratio increases, to the point where <br=
clear=3D"none">
Meek and Warren beats it with nine seats.<br clear=3D"none">
<br clear=3D"none">
Perhaps this has something to do with how Schulze STV's main calculation <b=
r clear=3D"none">
is on sets that differ by one candidate, that it then uses widest path <br =
clear=3D"none">
to extrapolate; if there are more winners, such paths may have more <br cle=
ar=3D"none">
steps. But I don't know for sure.<br clear=3D"none">
<br clear=3D"none">
I also found a few crash-inducing memory access bugs in Schulze's <br clear=
=3D"none">
implementation, but the code is difficult enough to understand that I'm <br=
clear=3D"none">
unsure how to fix them. I'll probably give more details in another post.<br=
clear=3D"none">
<br clear=3D"none">
-km<br clear=3D"none">
<br clear=3D"none">
[1] <br clear=3D"none">
<a shape=3D"rect" href=3D"https://sites.math.duke.edu/~bray/Courses/49s/Add=
itional%20Reading/Schulze/Schulze3/schulze3.pdf" rel=3D"nofollow" target=3D=
"_blank">https://sites.math.duke.edu/~bray/Courses/49s/Additional%20Reading=
/Schulze/Schulze3/schulze3.pdf</a><br clear=3D"none">
</blockquote></div></div>
</div></div></div>
</div>
</div></div></body></html>
------=_Part_4817614_1723800003.1781738427895--
--===============1902131721127504205==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
----
Election-Methods mailing list - see https://electorama.com/em for list info
--===============1902131721127504205==--