Re: Voting system R&D (Re: 2017 update to the SPI voting algorithm for Board elections)

Hallo,

I recommend Schulze STV. This method is described mainly
in section 9 of this paper:

http://m-schulze.9mail.de/verylong.pdf

Source codes can be found here:

http://m-schulze.9mail.de/schulze3.zip

multi01g.cpp is multi-threading for g++.
multi01v.cpp is multi-threading for Microsoft Visual C++.
singl01g.cpp is single-threading for g++.
singl01v.cpp is single-threading for Microsoft Visual C++.

*********

When Schulze STV is used, then each voter gets a complete
list of all candidates and ranks these candidates in order
of preference. The individual voter may give the same
preference to more than one candidate and he may keep
candidates unranked.

*********

Schulze STV is an STV method, in so far as it satisfies
Dummett-Droop Proportionality: When strictly more than
x Droop Quotas of voters strictly prefer every candidate
of a set B of (at least x) candidates, then at least
x candidates of set B must be elected. (See section 9.3
of "verylong.pdf".)

*********

In single-winner elections, a "Condorcet winner" is a
candidate who wins every 2-way contest. The property of
being a Condorcet winner is very important because, when
some candidate X is a Condorcet winner, then candidate X
is also a Condorcet winner when some other candidate is
removed. So when some candidate X is a Condorcet winner,
we can declare this candidate the winner, knowing that
he doesn't owe his win to the presence of some other
candidate.

Schulze STV has the following property: Suppose M is the
number of seats. When some candidate X wins in every
(M+1)-candidate contest, then he is also a winner overall.
Again, the property of winning in every (M+1)-candidate
contest is important because, when some candidate X has
this property, then candidate X still has this property
when some other candidate is removed. (See section 9.4
of "verylong.pdf".)

*********

The analysis of Schulze STV is very short because most
of its properties follow directly from the fact that,
in the single-winner case, Schulze STV is identical to
the Schulze single-winner election method, which is
analyzed in sections 2--4 of "verylong.pdf". The Schulze
single-winner election method is currently used by SPI.

Markus Schulze

Purely as a FYI on Schulze method, it is implemented in the Liquid
Feedback system: http://liquidfeedback.org/

Liquid Feedback has been used for years in Central Europe, notably by
several chapters of the Pirate Party, but also some cooperatives, etc.

Note: LF itself is IMO not suitable for use by SPI - at least not
within the scope of the proposal now discussed.

Note: My intent here is to be purely informational. I'm not advocating
for or against the Schulze method compared to other STV methods.

henrik

On Sat, Mar 4, 2017 at 3:01 PM, Markus Schulze
<markus(dot)schulze(at)alumni(dot)tu-berlin(dot)de> wrote:
> Hallo,
>
> I recommend Schulze STV. This method is described mainly
> in section 9 of this paper:
>
> http://m-schulze.9mail.de/verylong.pdf
>
> Source codes can be found here:
>
> http://m-schulze.9mail.de/schulze3.zip
>
> multi01g.cpp is multi-threading for g++.
> multi01v.cpp is multi-threading for Microsoft Visual C++.
> singl01g.cpp is single-threading for g++.
> singl01v.cpp is single-threading for Microsoft Visual C++.
>
> *********
>
> When Schulze STV is used, then each voter gets a complete
> list of all candidates and ranks these candidates in order
> of preference. The individual voter may give the same
> preference to more than one candidate and he may keep
> candidates unranked.
>
> *********
>
> Schulze STV is an STV method, in so far as it satisfies
> Dummett-Droop Proportionality: When strictly more than
> x Droop Quotas of voters strictly prefer every candidate
> of a set B of (at least x) candidates, then at least
> x candidates of set B must be elected. (See section 9.3
> of "verylong.pdf".)
>
> *********
>
> In single-winner elections, a "Condorcet winner" is a
> candidate who wins every 2-way contest. The property of
> being a Condorcet winner is very important because, when
> some candidate X is a Condorcet winner, then candidate X
> is also a Condorcet winner when some other candidate is
> removed. So when some candidate X is a Condorcet winner,
> we can declare this candidate the winner, knowing that
> he doesn't owe his win to the presence of some other
> candidate.
>
> Schulze STV has the following property: Suppose M is the
> number of seats. When some candidate X wins in every
> (M+1)-candidate contest, then he is also a winner overall.
> Again, the property of winning in every (M+1)-candidate
> contest is important because, when some candidate X has
> this property, then candidate X still has this property
> when some other candidate is removed. (See section 9.4
> of "verylong.pdf".)
>
> *********
>
> The analysis of Schulze STV is very short because most
> of its properties follow directly from the fact that,
> in the single-winner case, Schulze STV is identical to
> the Schulze single-winner election method, which is
> analyzed in sections 2--4 of "verylong.pdf". The Schulze
> single-winner election method is currently used by SPI.
>
> Markus Schulze
>
>
> _______________________________________________
> Spi-general mailing list
> Spi-general(at)lists(dot)spi-inc(dot)org
> http://lists.spi-inc.org/listinfo/spi-general

--
henrik(dot)ingo(at)avoinelama(dot)fi
+358-40-5697354 skype: henrik.ingo irc: hingo
www.openlife.cc

My LinkedIn profile: http://fi.linkedin.com/pub/henrik-ingo/3/232/8a7

Henrik Ingo writes ("Re: Voting system R&D (Re: 2017 update to the SPI voting algorithm for Board elections)"):
> Purely as a FYI on Schulze method, it is implemented in the Liquid
> Feedback system: http://liquidfeedback.org/

Thanks. That's interesting. I wasn't aware of that. I think Liquid
Feedback is very exciting. It is an innovative system used by
politically oriented organisations who understand governance problems
well.

But I think in SPI we probably want to be more conservative.

In particular, Scottish STV (a traditional STV variant) has some
important advantages for us over Schultze STV:

* The specification of Scottish STV is expressed in readily
comprehensible prose, as opposed to mathematics.

* We already have multiple independent implementations of Scottish
STV. (Note that Markus has not provided the actual source code of
his implementation AFAIC T1])

* Scottish STV is considerably simpler. My reimplementation in Perl
is 432 lines. Markus's implementation of Schultze STV in C++ is
6000-7000 lines, depending on which variant we use.

* Traditional STV (including Scottish STV specifically) has a large
body of independent analysis - not just of the voting system from a
mathematical/technical level, but also of the sociopolitical
effects such as effects on voting patterns and on attitudes in the
polity.

My personal view is that a more Condorcet-ish proportional voting
system is a good thing, but that I would like to see more third-party
analysis. I do have the skills to follow Martin's paper myself, but
digging into this in detail is not a personal priority for me right
now.

In any case, the differences in outcome between Schultze STV and
Scottish STV are likely to be minor.

Thanks,
Ian.

[1] There is the file http://m-schulze.9mail.de/schulze3.zip whilch
contains (at least) four different variants, which have obviously been
generated from a single original source file. Neither that original
source file nor the machinery for substuting the variants is in the
zipfile.

On 4 March 2017 at 13:01, Markus Schulze
<markus(dot)schulze(at)alumni(dot)tu-berlin(dot)de> wrote:
> I recommend Schulze STV.

It is a very nice algorithm, which does about as well as any
polynomial-time algorithm could using rank ballots. It certainly
overcomes a lot of the practical pathologies in ScottishSTV or more
generally IRV-based STV systems.

I would agree that, assuming rank ballots, Schulze STV is the most
sensible choice.

If I were ranking them as fit-for-purpose in the current context, I'd rank

RRV > Schulze STV > ScottishSTV > Current System

If I wanted to be more informative, while using the entire dynamic
range, I'd say

RRV: 99
Schulze STV: 90
ScottishSTV: 50
Current System: 0

One issue with Schulze STV is that it is hard to explain to people who
are not mathematically sophisticated. That should not be a problem
here.

Cheers,

--Barak.

Ian, All:

So in all of this discussion, I've not heard anything which seems
terribly persuasive compared with just taking our existing system and
fixing the problem with unranked candidates (and maybe providing a
slightly better UI).

Yes, we could use a different system, but why?

The system we currently use has been good at choosing candidates who are
acceptable to most voting members over candidates who take highly
partisan positions. This is a *virtue*, not a drawback. If we'd had a
voting system which supported more partisanship, SPI probably would have
been destroyed ten years ago when we had folks actively trying to split
the membership.

If we have a problem with too many candidates needing to be Debian-ish,
then the answer is to add specific board seats elected in a way which
ensures a pool of candidates who don't care about Debian. Personally,
though, I think that would be more trouble than it's worth, and I work
on Fedora.

Overally, I disagree that there's any major issue with our voting
system, and this whole thing really looks to me like voting system geeks
looking for an excuse to tinker with "cool voting tech".

Let's just fix the unranked candidate problem, work on the UI a little,
and call it good enough.

On Mon, Mar 06, 2017 at 08:50:09PM -0800, Josh berkus wrote:
> So in all of this discussion, I've not heard anything which seems
> terribly persuasive compared with just taking our existing system and
> fixing the problem with unranked candidates

FWIW this is already fixed; the current system supports both the old
"unranked means no preference" and the preferred "unranked means lower
preference than all ranked" and defaults to the latter.

J.

--
"A true friend knows who you are...but likes you anyway."
This .sig brought to you by the letter C and the number 2
Product of the Republic of HuggieTag

Josh berkus writes ("Re: Voting system R&D (Re: 2017 update to the SPI voting algorithm for Board elections)"):
> So in all of this discussion, I've not heard anything which seems
> terribly persuasive compared with just taking our existing system and
> fixing the problem with unranked candidates (and maybe providing a
> slightly better UI).
>
> Yes, we could use a different system, but why?

The arguments were rehearsed extensively in July and August.

> The system we currently use has been good at choosing candidates who are
> acceptable to most voting members over candidates who take highly
> partisan positions. This is a *virtue*, not a drawback. If we'd had a
> voting system which supported more partisanship, SPI probably would have
> been destroyed ten years ago when we had folks actively trying to split
> the membership.

Proportional voting systems are _better_ at undermining partisanship
than winning-faction-takes-all ones.[1]

> If we have a problem with too many candidates needing to be Debian-ish,
> then the answer is to add specific board seats elected in a way which
> ensures a pool of candidates who don't care about Debian. Personally,
> though, I think that would be more trouble than it's worth, and I work
> on Fedora.

Proportional voting systems avoid the need for this kind of explicit
division, seats set aside, and so on. I don't SPI as a whole is at
all keen on such proposals. They are, perhaps, a necessary evil in
some very divided societies. SPI does not have those kind of
problems.

> Overally, I disagree that there's any major issue with our voting
> system, and this whole thing really looks to me like voting system geeks
> looking for an excuse to tinker with "cool voting tech".

The Single Transferable Vote is the opposite of "cool voting tech".

What we have right now is an experimental multi-winner Condorcet which
has been chosen almost by accident, and which has never been subjected
to any 3rd-party analysis, never been discussed in the literature, and
never adopted anywhere else. I want to move away from that to
something standard, well-regarded, and widely adopted.

I am trying to switch from "cool voting tech" to something boring.

(If I wanted excitement I would be looking at Schultze's system more
seriously.)

Ian.

[1] For example, if you want to read some sociology research
about Northern Ireland's adoption of STV, see

_The Single Transferable Vote and Ethnic Conflict:
The Evidence from Northern Ireland, 1982-2007_
Paul Mitchell, LSE, for _Designing Democrat Instutitions,
inaugural _Political Science and Political Economy_ conference,
LSE 13-14 May 2008
http://www.lse.ac.uk/government/research/resgroups/PSPE/pdf/2008conference_papers/Mitchell_STVpaper.pdf

or

_Nationalism and ethnic politics in Northern Ireland:
The Impact of PR-STV on European election campaigns"
Jonathan Githens-Mazer and Henry Jarret
Political Studies Association
64th Annual International Conference
Manchester 14-16 April 2014
https://www.psa.ac.uk/sites/default/files/conference/papers/2014/PSA%20NI%20elections%20paper.pdf

or you can do your own sociology research searches :-).

On 03/07/2017 10:13 AM, Ian Jackson wrote:
> Josh berkus writes ("Re: Voting system R&D (Re: 2017 update to the SPI voting algorithm for Board elections)"):
>> So in all of this discussion, I've not heard anything which seems
>> terribly persuasive compared with just taking our existing system and
>> fixing the problem with unranked candidates (and maybe providing a
>> slightly better UI).
>>
>> Yes, we could use a different system, but why?
>
> The arguments were rehearsed extensively in July and August.

I made this argument then, as well. Nothing I've seen has convinced me
that our existing system needs more than a few patches.

>> The system we currently use has been good at choosing candidates who are
>> acceptable to most voting members over candidates who take highly
>> partisan positions. This is a *virtue*, not a drawback. If we'd had a
>> voting system which supported more partisanship, SPI probably would have
>> been destroyed ten years ago when we had folks actively trying to split
>> the membership.
>
> Proportional voting systems are _better_ at undermining partisanship
> than winning-faction-takes-all ones.[1]

Concordet is not a winning-faction-take-all system. It is a "most
acceptable candidate" system. Which kinda makes this argument invalid.

>> Overally, I disagree that there's any major issue with our voting
>> system, and this whole thing really looks to me like voting system geeks
>> looking for an excuse to tinker with "cool voting tech".
>
> The Single Transferable Vote is the opposite of "cool voting tech".
>
> What we have right now is an experimental multi-winner Condorcet which
> has been chosen almost by accident, and which has never been subjected
> to any 3rd-party analysis, never been discussed in the literature, and
> never adopted anywhere else. I want to move away from that to
> something standard, well-regarded, and widely adopted.
>
> I am trying to switch from "cool voting tech" to something boring.

But STV is still a "single-winner" system. Any multi-winner
implementation of it we choose would *still* be experimental.

For that matter, STV isn't a proportional system, unless you're planning
to allocate "seats" by project? If so, that's a rather substantial
bylaws change, and needs to be spelled out.

In fact, looking over your posts to spi-general and spi-private, I can't
find one which does actually fully lay out what specific voting
mechanics you're proposing. I may have missed it because I was off
spi-private for a month or so; can you please link your paper explaining it?

--Josh Berkus

On 03/07/2017 10:29 AM, Josh berkus wrote:
> But STV is still a "single-winner" system. Any multi-winner
> implementation of it we choose would *still* be experimental

Aha, just found the multi-winner math for STV. Please ignore this part
of my arguments. The other parts still apply.

Josh berkus writes ("Re: Voting system R&D (Re: 2017 update to the SPI voting algorithm for Board elections)"):
> Concordet is not a winning-faction-take-all system. It is a "most
> acceptable candidate" system. Which kinda makes this argument invalid.

Condorcet is a single-winner voting system. SPI's homegrown
multi-Condorcet is a winning-faction-takes-all system.

Here is an example I posted in July, again:

Suppose there are 3 seats up for grabs, and red, pink, and blue board
candidates, 3 in each colour. If the electorate votes along colour
lines:

60 voters blue > pink > red
40 voters red > pink > blue

Then the outcome with SPI's multi-Condorcet is:

blue, blue, blue

That is precisely the winning faction taking all.
The outcome with STV is:

blue, red, blue

> > I am trying to switch from "cool voting tech" to something boring.
>
> But STV is still a "single-winner" system. Any multi-winner
> implementation of it we choose would *still* be experimental.

Seriously ?!

STV is not a single-winner system. STV is the popular multi-winner
extension to AV (the single-winner system "Alternative Vote", which is
known in the US as "IRV").

STV is far from experimental. Did you not spot that my draft
resolution refers to a UK Statutory Instrument (ie, government
legislation) from 2007 ?

> In fact, looking over your posts to spi-general and spi-private, I can't
> find one which does actually fully lay out what specific voting
> mechanics you're proposing. I may have missed it because I was off
> spi-private for a month or so; can you please link your paper explaining it?

Please see my draft resolution.

I will repost it in a moment (with the numbering fixed).

Ian.

--
Ian Jackson <ijackson(at)chiark(dot)greenend(dot)org(dot)uk> These opinions are my own.

If I emailed you from an address @fyvzl.net or @evade.org.uk, that is
a private address which bypasses my fierce spamfilter.

On Tue, 7 Mar 2017, Josh berkus wrote:

> On 03/07/2017 10:29 AM, Josh berkus wrote:
>> But STV is still a "single-winner" system. Any multi-winner
>> implementation of it we choose would *still* be experimental
>
> Aha, just found the multi-winner math for STV. Please ignore this part
> of my arguments. The other parts still apply.

Not sure how many people are aware of this but the Australian Senate
has been using multi-winner STV since 1948. The state of Tasmania has
been doing the same since 1907.

https://en.wikipedia.org/wiki/History_and_use_of_the_single_transferable_vote#Australia

There has been plenty of discussion in Australia about the pros and cons
of this system going back more than a century.

Cheers,

Rob