[EM] (6) APR: Steve's 6th dialogue with Kristofer & Others

[Kristofer Munsterhjelm]

This reply might be rough, and definitely is long in the coming, due to
that I had to deal with a lot of real world matters while working on the
post. I hope it is not too rough, though.

On 10/22/2015 01:01 AM, steve bosworth wrote:
> 
> (6) APR: Steve's 6th dialogue with Kristofer & Others
> 
>  
> 
> 
>> From: election-methods-request at lists.electorama.com
>> Subject: Election-Methods Digest, Vol 136, Issue 19
>> To: election-methods at lists.electorama.com
>> Date: Mon, 19 Oct 2015 12:02:10 -0700
>> 
>> 1. Re: (5) APR: Steve's 5th dialogue with Kristofer & Others
>> (Kristofer Munsterhjelm)
>> 
>> ----------------------------------------------------------------------
>> 
>> Date: Mon, 19 Oct 2015 00:22:46 +0200
>> From: Kristofer Munsterhjelm <km_elmet at t-online.de>
>> To: steve bosworth <stevebosworth at hotmail.com>,
>> "election-methods at lists.electorama.com"
>> Subject: Re: [EM] (5) APR: Steve's 5th dialogue with Kristofer &
>> Others
>> Message-ID: <56241BB6.6070603 at t-online.de>
>> Content-Type: text/plain; charset=windows-1254; format=flowed
>> 
>> On 10/01/2015 11:08 PM, steve bosworth wrote:
>> 
>> >> > Re: (4) APR: Steve's 4th dialogue with Kristofer
>> >> >
>> >> > Date: Wed, 01 Jul 2015 22:14:11 +0200
>> >> > > From: Kristofer Munsterhjelm <km_elmet at t-online.de>
>> >> > > To: Election Methods Mailing List <election-methods at electorama.com>
>> >> > > Subject: [EM] Thresholded weighted multiwinner elections
>> >> > > Message-ID: <55944A13.7060800 at t-online.de>
>> >> > > Content-Type: text/plain; charset=utf-8; format=flowed
>> >> >
> 
> 
> [….]
> 
> 
>> > S: Steve's questions will follow each element of what Kristofer wrote:
>> >> >
>> >>K: I think I see why the cloning attack is possible in two-stage weighted
>> >> > > voting. If I'm right, then it is possible to make voting methods that
>> >> > > produce results that fit weighted voting better -- at least when the
>> >> > > voters are honest. However, I'm not sure if it is possible at all if
>> >> > > enough voters are strategic.
>> >> >
>>S: Am I mistaken in believing that, in practice, APR's 'weighted
>> multiwinner elections' would not be vulnerable to the threats either of
>> effective 'cloning' or of other kinds of 'strategic voting'?
>> 
> K: Yes. I mean the very opposite.
>> 
> K:> Firstly, no method is entirely invulnerable to strategic voting; that
>> was my point when mentioning Duggan-Schwarz. All you can do is find more 
>> resilient methods, or balance resilience against other desirable 
>> properties (like how good results you get under honesty).
>> 
>> Second, the cloning attack I mentioned specifically targets APR's 
>> IRV-based election mechanism. What I tried to show is that APR is 
>> vulnerable to cloning. Unlike STV's similar vulnerability, the IRV based 
>> method used in ARV [i.e. APR] has a vulnerability that favors well-organized
>> participants, and so would give an advantage to parties that can organize.
> 
> 
>  
> 
> 
> S: Given these and your later words, it seems that either you are not
> understand exactly how my APR is counted or I am not understanding the
> terms you are using.  Thus, in order for me fruitfully to address your
> argument, please explicitly define, explain or comment on the following
> words, phrases, and dialogues copied from all that is repeated after the
> +++++++++++ line: 
> 
> 
> 1)      the exact differences you have in mind between IRV, STV, and APR;

To try to be simple:

IRV is a method where you repeatedly eliminate Plurality losers until
only one candidate remains. IRV-until-k repeatedly eliminates Plurality
losers until only k candidates remain.

STV is similar to IRV, except that it also distributes surplus votes. If
a candidate has more than a Droop quota's worth of first preferences, he
is automatically elected and the surplus (the number of voters he had
past a Droop quota) is distributed to the next preferences of the voters
who contributed to his election.

The part of APR I'm focusing on is the "eliminate until k remain and
then give them the weights according to the number of first place votes
they got" part. That is equivalent to IRV-until-k followed with giving
each candidate weight according to the number of first place votes they
get on a ballot set where everybody except those k have been eliminated.

> 2)      vote allocation (is this simply ranking?);

Vote allocation is the SNTV strategy I have been mentioning. It may more
generally be called vote management: i.e. the coordination, by a party,
of how its supporters vote, for the purpose of gaining some benefit. See
https://en.wikipedia.org/wiki/Vote_allocation.

> 3)      Droop quota (Strictly speaking, APR has no use for the Droop
> quota.  APR may elect some candidates who have received fewer votes than
> this quota.  This will occur as a result of some candidates being
> elected with more votes than this quota and therefore receiving more
> ‘weighted votes’ in the assembly.);

My whole point is that a party that has more than k Droop quotas' worth
of support can get k of its candidates elected by cloning. If every
party does this, then candidates with less than a Droop quota's worth of
support are pushed off because there isn't any room left.

A Droop quota in voter terms is v/(s+1) votes, where v is the number of
voters and s is the number of seats. In fractional terms, it's 1/(s+1),
e.g. 1/2 = 50% for a single-winner election, 1/3 = 33% for a two-winner
election and so on.

Droop quotas might be relevant even though the method does not
explicitly mention them. Consider single-winner Plurality phrased like
"count the votes, and whoever has the most votes wins". Then the
equivalent Droop quota (1/2 = 50%, a majority) is important in that any
candidate who gets more than this is automatically elected. Yet the
definition of Plurality does not explicitly mention majorities, let
alone Droop quotas.

> 4)      spread the votes evenly (Does this mean giving all the party
> voters’ 1^st preferences to the most favored candidate while they give
> the same number to 2^nd or lower preference clones?  In any case, I do
> not yet see how this strategy would give this party more ‘weighted
> votes’ in the assembly, or could ‘push off’ any opposing candidates.);

For clarification, when I use single letters like X, Y, Z, I usually
mean candidates. When I use letters followed by numbers (e.g. X1, X2), I
usually mean clones of the same candidate (X). You can also consider
that to be clones provided by the same party, in which case X would be
the party.

Now, suppose the party is P and it fields four candidates: P1, P2, P3,
and P4.
Suppose it has the support of 100 voters. Then "evenly spreading" would
instruct the voters to vote in a way so that 25% of the voters vote for
any given clone in the first place, 25% of the voters vote for any given
clone in second, 25% of the voters vote for any given clone in third,
and 25% vote for any given clone in fourth. A simple way of doing this
is as follows:

25: P1 > P2 > P3 > P4
25: P2 > P3 > P4 > P1
25: P3 > P4 > P1 > P2
25: P4 > P1 > P2 > P3

I.e. they vote around a circle with each rotation in equal numbers.

By using dice or cards, it is possible to perform an even more
sophisticated allocation[1] so that after say, P1 is eliminated, 33% of
the ballots vote for the one of the three remaining clones in first, and
the same for second and third place. However, I don't want to confuse
the issue.

> 5)      k of n candidates (k is the total number the party’s most
> favored candidates while n is the total number of candidates the party
> is running.  However, I see that k seems to have a different meaning
> nearer the end of your post.);

k usually is a number corresponding to a part of the whole, and n is a
number corresponding to the whole. For instance, the binomial choose
operator is usually written as "n choose k", which gives how many ways
one can pick k items from a group of n.

In the proof sketch, k is the number of candidates from a party who won,
and n is the number of candidates that party fielded.

In the term "IRV-until-k", k is the number of winners and n is the
number of candidates in total.

> 6)      n-k candidates (means the total number of candidates less
> favored by the party.  If so, I do not understand how ‘IRV eliminates
> more than n-k in one go);

Correspondingly, n-k is the number of candidates who did not win, either
from the party (in the proof sketch) or generally.

> 7)      What ‘threshold’?  I do not see APR as having any ‘threshhold’. 
> APR simply continues to eliminate the candidate that currently has the
> fewest votes until only the pre-established number of candidates remain
> to be elected to each electoral association.

I mean the Asset voting threshold. Say that any candidate who achieves
more than 10% of the vote will have to distribute his weight according
to a predeclared order. Then that 10% is the threshold. (It may be 20%,
15%, the argument still stands.)

> 8)      ‘the first stage weakens the second’ (I think you are referring
> more simply to APR’s 4-stage count explained in Endnote 4.)

No, I mean the two-stage reformulation of the weighted voting process.
The first stage determines who the winners are. The second stage
determines their weights. "The first stage weakens the second" is just
the observation that a candidate that has been pushed off by IRV can't
ever get a nonzero weight, so however fair the idea of giving weights to
winners is, it doesn't help if you get pushed off the winner list entirely.

> Also, please clarify the following questions.  These question have also
> been copied from also remains below the ++++++++++ line:
> 
> S: I do not yet understand why you think an analysis of Single
> Non-Transferable Voting (SNTV) is relevant to STV or APR. 

That is because both SNTV and IRV-until-k is an adaptation of a
single-winner method to a multiwinner system; and because IRV is close
enough to Plurality that some of the weaknesses in the latter makes it
possible to do an attack in the former.

In some ways, performing vote management in IRV-until-k is less risky
than doing it in SNTV. If a party overestimates its support in SNTV, it
can risk losing all of its seats; however, in IRV-until-k, the excess
clones will simply be eliminated and then the count proceeds as if the
party didn't field those clones to begin with.

>>K: It doesn't seem to invalidate the proof sketch.
> 
> S:  Again, I appreciate that your ‘proof sketch’ (especially if I fully
> understood it) may have shown how a strategizing party will lose nothing
> in trying (except time, the money for some of the deposits for some of
> its eliminated candidates, perhaps confusing its voters, etc.).  What I
> do not yet understand is how, in practice, they will acquire the for
> knowledge needed to get any more benefits than this.

What I said above holds the key. The idea is that if a party evenly
spreads its votes, then it doesn't matter if they field too many clones.
Those clones will then simply be eliminated and then the count proceeds
as if they didn't field too many clones.

The voters who execute an even spreading strategy intend mainly to
distribute their own voters irrespective of what the other voters are
doing. That's why they don't need much information about how the other
voters are voting: all they intend to do is to push off other candidates
by making more than one candidate get elected at a lower weight where
only one used to be elected at a higher weight. (See below.)

The whole appeal of IRV, as I understand it, is that it reduces the
problem of electing a winner from a pool of 10 candidates to the problem
of electing a winner out of 9 candidates, and so on down to the problem
of electing a winner out of 2 candidates, at which point you can just
use majority rule. For IRV-until-k, it reduces the problem of electing
say, 3 winners out of 10 candidates to the problem of electing 3 winners
out of 9, then 3 out of 8, then ... down until 3 out of 3.

However, this very same elimination mechanic makes it risk-free to field
lots of clones, because the very worst thing that can happen is that
some clones get eliminated, and then you're reduced to a similar
situation as if you hadn't fielded those clones to begin with.

So we've established the risk-free nature of cloning (apart from time,
deposits, etc). How can a party benefit? Suppose that there are two
situations. Let's disregard what I've called the threshold for now: I
want to be as simple as possible so that the explanation won't be
confusing. That is, let's disregard the clause that says that candidates
who get too much weight must redistribute it.

So, there are two situations. In the first, the party fields one
candidate and he gets 20% of the weight, is elected, and represents that
party with 20% weight.

In the second, the party fields two candidates and (because of even
spreading), each candidate gets at least 10% of the weight and they're
both elected. If the attack fails, the remaining candidate gets 20% so
there's no risk. Assume it succeeds.

Now, cloning seems to have given the party no benefit. However, if there
are only 10 people in the assembly, then what happens is also that one
of the other candidates were pushed off to make room for the party's
second candidate.

We know that the sum of the two winners' weights will still be at least
20% because the party has 20% support. But if there were some voters who
first voted for the candidate who was pushed off, then for the party
that cloned, then those voters' votes will go to the party that cloned
since the candidate who was pushed off is no longer around to receive
any weight. So by cloning and pushing off, the party may receive more
than 20% support in total.

It doesn't need to know how others vote to do so. If it misjudged, then
one of its clones is eliminated and it gets another shot with the
remaining clones. So the whole point of even spreading is that the party
maximizes the chances of any given clone winning, to the extent it can
among its own supporters. Any further help provided by other voters is
just a bonus.

Why is even spreading the best choice? Well, suppose a party P has two
clones: P1 and P2. If the supporters of P vote only for P1 first, then
P2 will be eliminated right away. If the supporters of P vote only for
P2 first, then P1 will be eliminated right away. The more the voters
shift votes from P1 to P2, the better a chance P2 has to survive...
until its survival comes at the cost of P1. And that breakeven point
happens when P1 has the same number of first preferences, among P's
supporters, as P2 has.

In short, the party clones to maximize the number of different people
they can get into the assembly. They like getting lots of people with
low weight into the assembly more than getting a few people with high
weight in. Why? Because getting lots of their own reps in displaces reps
not in the party from the assembly, and the subsidiary votes of voters
who vote for the reps who were pushed off may then go to the party instead.

E.g. if the Republican party can give all of its candidates greater
support than the greatest support of independent libertarian candidates,
and all libertarians vote Republican before they vote Democratic, then
the Republican party can displace the libertarian candidates and add the
libertarian voters' weight to their own.

>> For default votes: either they are the ballots themselves, in which
>> case there's no problem, or they're optional different lists, in which case 
>> voters for X could just not use them.
> 
> S:  No. ‘Default votes’ are passed onto winning candidates by the 1^st
> choice candidate of the voter who has not ranked any winning candidates.

I see. That shouldn't be a problem, since if the party pushes off
representatives not aligned with them, the voter can only choose between
winners, i.e. can't make any of the reps who were pushed off get back on.

>> For extra Asset reallocations: they don't come into play when
>> cloning is
>> used because no single member amasses enough weight to go past the 
>> threshold.
> 
> S:  By saying this, you seem to have forgotten that APR does not use
> thresholds.  Instead, APR requires very popular elected candidate to
> retain only up to 10% of all the ‘weighted votes’ in the assembly.  Any
> votes received above this 10% limit must be non-returnably passed on by
> the relevant MP to other MPs she trusts.

Here I use threshold in the general sense: a barrier above which the
rules change[2]. In this particular case, the change is that the
candidate must pass on the excess.

>> I think my cloning example in that email is relevant. I showed an
>> instance where APR would first choose {X, Y, Z} as the winners to 
>> distribute weight among. Then X clones and the outcome switches to {X1, 
>> X2, Y}: Z is pushed off. Since the method moved from thinking Z should 
>> be included into thinking Z should not, it was mistaken in at least one 
>> of these cases. Which is it? Should candidates with less than a Droop 
>> quota (Z in this case) always be retained, or should they be excluded 
>> beforehand so that cloning has no effect?
> 
> 
>  
> 
> 
> S:  I do not yet understand these claims.  In APR, only the very popular
> elected candidate (i.e. any with more than 10% of the weighted votes in
> the assembly) would be allowed to ‘distribute weight’ to their less
> popular colleagues.  Also, it would help me if you could express the
> same argument without relying on abstract mathematical symbols like X,
> X1, X2.  In any case, do these 3 symbols represent 3 different parties;
> 3 different candidates; or one most preferred candidate, a 1st choice
> clone candidate, and a 2nd choice clone candidate?

Alright, I'll try to rephrase it in the Republican-Libertarian example
above. It will be grossly simplified, of course: in reality there would
be more seats and more factions, but still.

52: Repub1 > Democrat1 > Libertarian > Moderate
25: Democrat1 > Moderate > Libertarian > Repub1
10: Libertarian > Moderate > Repub1 > Democrat1
 5: Moderate > Democrat1 > Repub1 > Libertarian

These are all candidates. The Republican party has one candidate:
Repub1. Similarly, the Democratic party has one candidate: Democrat1.
The Libertarian and Moderate candidates are either the sole candidates
fielded by respectively Libertarian and some Moderate party, or
independents that hold respectively libertarian and moderate views.

In this pre-cloning election, the moderate is eliminated and one from
each group is elected: a Republican, a Democrat, and a Libertarian. The
Democratic winner also gets the weights from the moderate voters.

But now the Republicans clone. All the unaffiliated voters vote the
clones in the same order (perhaps Republican 1 is the more genuine one):

26: Repub1 > Repub2 > Democrat1 > Libertarian > Moderate
26: Repub2 > Repub1 > Democrat1 > Libertarian > Moderate
25: Democrat1 > Moderate > Libertarian > Repub1 > Repub2
10: Libertarian > Moderate > Repub1 > Repub2 > Democrat1
5: Moderate > Democrat1 > Repub1 > Repub2 > Libertarian

As before, the moderate is pushed off. But now the second Republican
displaces the Libertarian and the winners are

Republican #1, Republican #2, Democrat #1.

By cloning, the Republicans in effect acquired the libertarian voters'
weight. The libertarians find their weight going to their third choice
instead of their first simply because the cloning worked. Note again
that the Republican party did not have to know that everybody would
judge Republican 1 as more genuine than #2: even spreading worked just fine.

Does that help?

My question is, since the method changed its mind from electing a
Republican and Libertarian (and Democrat) to electing two Republicans
(and a Democrat) through no change of the voters' actual preferences,
when did it make the right call? Did it when it elected the Libertarian,
or when it elected two Republicans? It can't be both.

There is a third alternative: that the method should give less popular
candidates seats whenever there's room to do so, but that if there isn't
any room, then there isn't any, and that's no fault of the method
itself. But that alternative isn't unproblematic, either.

I don't know if the voting numbers are realistic, but again, I'm only
out to show why cloning gives a benefit when it does. You could probably
construct voter profiles, something like:

- The 52 Republican voters are mainstream Republicans and thus don't
want anything to do with the libertarians,

- The 25 Democrats are cosmopolitan moderates who abhor the Religious
Right and would rather have a libertarian if it came to that,

- The 10 libertarians don't like the mainstream parties much at all,

- And the 5 moderates find the Democratic candidate more appealing than
the Republicans.

But that's not in itself all that relevant for the situation.

>> More generally, I'd like to know how you define proportionality. Do
>> you
>> have a method-independent criterion as to what it means for an outcome 
>> to be proportional, and if so, what is it? Such a definition could help 
>> answer the question above, and it would also explain how you would 
>> conclude that my method sketches of an even earlier post were 
>> necessarily less proportional than APR's IRV.
> 
> S:  For me, complete proportional representation would be mathematically
> achieved when every citizen vote counts for one in the assembly (no
> votes wasted), the percentage of each different MP’s vote in the
> assembly is equal to the percentage of voting citizens who had voted for
> that MP.  Qualitatively, representation would be as complete as possible
> if the electoral system allows each citizen to rank any of all the
> candidates which she sees as being able to represent a scale of value
> similar to her own.  I see the associational element of APR as
> structurally maximizing the chances that each citizen will be able to
> see the largest number of such candidates that are available in her
> society, i.e. APR seems to maximize the chances that each citizen’s vote
> will be added to the weighted vote of the person in the society who has
> become an MP and who most accurately and reliably will represent her
> hopes and fears in the assembly.

I've moved my reply to this to the vote-wasting thread since that seems
to be a more appropriate place for it.


-

[1] Obviously, such an approach would be a lot more suitable to mail
ballots or internet voting than physical ones, but I don't want to give
the impression that voters need to make use of clever randomization
procedures for the cloning procedure to work at all. Since cloning never
hurts, the closer the voters can get to a complete even spread, the
better, and simple rotation (as I have detailed it) will work a lot of
the time.

[2] E.g. CED definition 5: "a level or point at which something would
happen, would cease to happen, or would take effect, become true, etc".