Re: Schulze STV bugs and updated results (was: Re: Preliminary Droop-fit proportionality results)
Etjon Basha via Election-Methods <[email protected]> Thu, 18 Jun 2026 07:03:00 +1000
| Newsgroups | gmane.politics.election-methods |
|---|---|
| Message-ID | <CA+EJN6QGhbMvnozHvtC8FAGX-FEAR=EDb984fmQgyVAMaOkfEQ@mail.gmail.com> |
--===============8142492111689202429== Content-Type: multipart/alternative; boundary="0000000000002f085706547963d7" --0000000000002f085706547963d7 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Boo! On Thu, 18 June 2026, 12:28=E2=80=AFam Kristofer Munsterhjelm, < [email protected]> wrote: > On 2026-06-02 23:11, Toby Pereira wrote: > > I see yes, thanks. In that case, Schulze STV seems to do pretty > > terribly, not just a bit worse than other STV methods. And looking at > > your whole list, considerably worse than things like (Bloc) Borda! It's > > definitely not broken in your simulation? > > I added some tests to Schulze STV and found an election where quadelect > would return the wrong outcome. > > The bug appears to have been caused by undefined behavior in Schulze's > own code, where a line does something that has no clear order of > execution, and different compilers resolve the ambiguity differently. I > 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 > "Implementing the Schulze STV Method"[1], table 2, and the Schulze STV > code used by my simulator now gives the correct outcome - i.e. the ones > listed in the paper - for all of them. > > I then ran my multiwinner simulations and got much better results. > Sorry, Etjon :-) > > Droop spatial proportionality: > > Two seats, 10 candidates, 14400 elections: > > Name Droop goodness-of-fit VSE > Meek/Warren 0.7932 > Harmonic (S-L) 0.9254 > Schulze STV 0.9997 > > Three seats: > > Warren 0.8712 > Meek 0.8713 > Harmonic (S-L) 0.8925 > Schulze STV 0.9992 > > Four seats: > > Harmonic (S-L) 0.8880 > Warren 0.9184 > Meek 0.9185 > Schulze STV 0.9954 > > Five seats: > > Harmonic (S-L) 0.8809 > Warren 0.9426 > Meek 0.9428 > Schulze STV 0.9874 > > Six seats: > > Harmonic (S-L) 0.8779 > Meek 0.9598 > Warren 0.9598 > Schulze STV 0.9758 > > Nine seats: > > Harmonic (S-L) 0.9450 > Schulze STV 0.9497 > Meek 0.9979 > Warren 0.9980 > > > The quantile fits for two out of ten are (288k elections): > > Name Prop. quantile Goodness-of-fit VSE > Schulze STV 0.3377 0.9961 > Harmonic (S-L) 0.3498 0.9223 > Meek/Warren 0.3344 0.8090 > > and for the 2-of-4 CFC-Kemeny comparison (5760 elections): > > Name Prop. quantile Goodness-of-fit VSE > Harmonic (S-L) 0.3317 0.9414 > Meek/Warren 0.3321 0.9602 > Schulze STV 0.3345 0.9989 > CFC-Kemeny 0.2493 0.9998 > > as well as 2-of-5 (7200 elections): > > Name Prop. quantile Goodness-of-fit VSE > Meek/Warren 0.3346 0.9208 > Harmonic (S-L) 0.3383 0.9294 > CFC-Kemeny 0.2441 0.9967 > Schulze STV 0.3371 0.9967 > > So Schulze STV seems to be pretty good, but its margin over other > methods shrinks as seats/candidates ratio increases, to the point where > Meek and Warren beats it with nine seats. > > Perhaps this has something to do with how Schulze STV's main calculation > is on sets that differ by one candidate, that it then uses widest path > to extrapolate; if there are more winners, such paths may have more > steps. But I don't know for sure. > > I also found a few crash-inducing memory access bugs in Schulze's > implementation, but the code is difficult enough to understand that I'm > unsure how to fix them. I'll probably give more details in another post. > > -km > > [1] > > https://sites.math.duke.edu/~bray/Courses/49s/Additional%20Reading/Schulz= e/Schulze3/schulze3.pdf > --0000000000002f085706547963d7 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable <div dir=3D"auto">Boo!</div><br><div class=3D"gmail_quote gmail_quote_conta= iner"><div dir=3D"ltr" class=3D"gmail_attr">On Thu, 18 June 2026, 12:28=E2= =80=AFam Kristofer Munsterhjelm, <<a href=3D"mailto:km-elmet@munsterhjel= m.no">[email protected]</a>> wrote:<br></div><blockquote class=3D= "gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding= -left:1ex">On 2026-06-02 23:11, Toby Pereira wrote:<br> > I see yes, thanks. In that case, Schulze STV seems to do pretty <br> > terribly, not just a bit worse than other STV methods. And looking at = <br> > your whole list, considerably worse than things like (Bloc) Borda! It&= #39;s <br> > definitely not broken in your simulation?<br> <br> I added some tests to Schulze STV and found an election where quadelect <br= > would return the wrong outcome.<br> <br> The bug appears to have been caused by undefined behavior in Schulze's = <br> own code, where a line does something that has no clear order of <br> execution, and different compilers resolve the ambiguity differently. I <br= > tested Schulze's prog01 compiled with a modern gcc and got the same bug= .<br> <br> After fixing the bug, I tested the example elections referenced in <br> "Implementing the Schulze STV Method"[1], table 2, and the Schulz= e STV <br> code used by my simulator now gives the correct outcome - i.e. the ones <br= > listed in the paper - for all of them.<br> <br> I then ran my multiwinner simulations and got much better results. <br> Sorry, Etjon :-)<br> <br> Droop spatial proportionality:<br> <br> Two seats, 10 candidates, 14400 elections:<br> <br> Name=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Droop goodness-of-fit VSE<br> Meek/Warren=C2=A0 =C2=A0 0.7932<br> Harmonic (S-L) 0.9254<br> Schulze STV=C2=A0 =C2=A0 0.9997<br> <br> Three seats:<br> <br> Warren=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A00.8712<br> Meek=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A00.8713<br> Harmonic (S-L) 0.8925<br> Schulze STV=C2=A0 =C2=A0 0.9992<br> <br> Four seats:<br> <br> Harmonic (S-L) 0.8880<br> Warren=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A00.9184<br> Meek=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A00.9185<br> Schulze STV=C2=A0 =C2=A0 0.9954<br> <br> Five seats:<br> <br> Harmonic (S-L) 0.8809<br> Warren=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A00.9426<br> Meek=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A00.9428<br> Schulze STV=C2=A0 =C2=A0 0.9874<br> <br> Six seats:<br> <br> Harmonic (S-L) 0.8779<br> Meek=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A00.9598<br> Warren=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A00.9598<br> Schulze STV=C2=A0 =C2=A0 0.9758<br> <br> Nine seats:<br> <br> Harmonic (S-L) 0.9450<br> Schulze STV=C2=A0 =C2=A0 0.9497<br> Meek=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A00.9979<br> Warren=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A00.9980<br> <br> <br> The quantile fits for two out of ten are (288k elections):<br> <br> Name=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Prop. quantile=C2=A0 =C2=A0 Go= odness-of-fit VSE<br> Schulze STV=C2=A0 =C2=A0 0.3377=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 0.= 9961<br> Harmonic (S-L) 0.3498=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 0.9223<br> Meek/Warren=C2=A0 =C2=A0 0.3344=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 0.= 8090<br> <br> and for the 2-of-4 CFC-Kemeny comparison (5760 elections):<br> <br> Name=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Prop. quantile=C2=A0 =C2=A0 Go= odness-of-fit VSE<br> Harmonic (S-L) 0.3317=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 0.9414<br> Meek/Warren=C2=A0 =C2=A0 0.3321=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 0.= 9602<br> Schulze STV=C2=A0 =C2=A0 0.3345=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 0.= 9989<br> CFC-Kemeny=C2=A0 =C2=A0 =C2=A00.2493=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 0.9998<br> <br> as well as 2-of-5 (7200 elections):<br> <br> Name=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Prop. quantile=C2=A0 =C2=A0 Go= odness-of-fit VSE<br> Meek/Warren=C2=A0 =C2=A0 0.3346=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 0.= 9208<br> Harmonic (S-L) 0.3383=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 0.9294<br> CFC-Kemeny=C2=A0 =C2=A0 =C2=A00.2441=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 0.9967<br> Schulze STV=C2=A0 =C2=A0 0.3371=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 0.= 9967<br> <br> So Schulze STV seems to be pretty good, but its margin over other <br> methods shrinks as seats/candidates ratio increases, to the point where <br= > Meek and Warren beats it with nine seats.<br> <br> Perhaps this has something to do with how Schulze STV's main calculatio= n <br> is on sets that differ by one candidate, that it then uses widest path <br> to extrapolate; if there are more winners, such paths may have more <br> steps. But I don't know for sure.<br> <br> I also found a few crash-inducing memory access bugs in Schulze's <br> implementation, but the code is difficult enough to understand that I'm= <br> unsure how to fix them. I'll probably give more details in another post= .<br> <br> -km<br> <br> [1] <br> <a href=3D"https://sites.math.duke.edu/~bray/Courses/49s/Additional%20Readi= ng/Schulze/Schulze3/schulze3.pdf" rel=3D"noreferrer noreferrer" target=3D"_= blank">https://sites.math.duke.edu/~bray/Courses/49s/Additional%20Reading/S= chulze/Schulze3/schulze3.pdf</a><br> </blockquote></div> --0000000000002f085706547963d7-- --===============8142492111689202429== 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 --===============8142492111689202429==--