[EM] (4) APR: Steve's 4th dialogue with Kristofer

[Kristofer Munsterhjelm]

Sorry that I haven't been able to reply before this. Hopefully it didn't 
cause too much of a problem!

By the way, my mail client says your posts are in the Windows-1254 
format. Are you writing on a Turkish computer? If not, something might 
be strange with your setup.

Your message source also states Content-Type: text/plain; 
charset="windows-1254".

On 07/17/2015 09:54 PM, steve bosworth wrote:
>
> Re: (4) APR: Steve's 4^th dialogue with Kristofer
>
>
>  > From: election-methods-request at lists.electorama.com
>  > Subject: Election-Methods Digest, Vol 133, Issue 2
>  > To: election-methods at lists.electorama.com
>  > Date: Thu, 2 Jul 2015 12:01:24 -0700
> …....................................................
>
>
>  > 1. Thresholded weighted multiwinner elections
>  > (Kristofer Munsterhjelm)
>  >
> 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
>
>  >Steve's questions will follow each element of what Kristofer wrote:
>
>  > 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.
>
> 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 effective 'strategic voting'?

As a side note: the Duggan-Schwartz theorem implies that every 
deterministic ranked voting method is sometimes vulnerable to strategic 
voting, even if it's a multiwinner method rather than a single-winner 
one. So every method is in some sense flawed; we just have to find good 
ones. Since APR's method is a ranked multiwinner method and thus covered 
by D-S, it can't be invulnerable to strategic voting. The question is 
whether it's good enough.

As for the cloning attack, I specifically found it while analyzing APR's 
voting method. So it's meant to work against APR's voting method 
(semimajoritarian IRV). It is not quite as strong as I originally 
thought, but would still lead to party list in an equilibrium. See below.

> This practical invulnerability would seem to arise from the facts
> that  APR's election
> of reps to a large national assembly would allow all citizen to rank
> as few or as many of all the thousands of candidates in the country.
> Accordingly, for example, the portion of all the perceived clones
> would be elected who were discover to be, for example, among the 435
> most popular candidates in the USA. Each elected candidate would
> simply have a weighted vote in the assembly equal to the number of
> votes that each had received directly or indirectly from citizens.

As I may have mentioned, we can abstract the two-stage voting method as 
follows:

First you run a first stage which determines who the winners are. No 
weighting is done at this stage.

Second, you assign each voter to the winner that he prefers the most of 
the winners. E.g. if the winner set is {ABC} and a voter voted D>C>B>A, 
then he is assigned to C.

Each winner gets a weight proportional to the number of voters assigned 
to him.

(End of abstraction)

In APR, to elect k winners, the first stage is IRV until you have 
eliminated all but k candidates. (E.g. to elect three winners, you 
eliminate and redistribute first preferences until only three candidates 
are left, and they are the winners).

The way I read you, you're saying that because the second stage is fair, 
then the method as a whole is fair. That is, "each elected candidate 
would simply have a weighted vote in the assembly equal to the number of 
votes that each had received directly or indirectly from citizens", and 
you also implicitly bring that up when you talk about wasted votes and 
how APR doesn't waste votes.

But there's another way by which the method can be unfair. That is by 
affecting the first stage. Say in a three-winner election example that a 
lot of voters would be happy if E were elected, but the use of strategy 
pushes E off the winning set entirely. E.g. voters who prefer A to E 
strategize so that the winning set goes from {BCE} to {ABC}.

Now, the E-voters will contribute to the candidate they favor among A, 
B, and C, but that doesn't make the fact that they preferred E go away. 
Their vote isn't wasted *among A, B, and C*, but it's diminished by (or 
degraded by) that they didn't get E.

In very simple terms: the first stage is "Determine what choices you get 
to choose from", and the second stage is "Choose from the choices 
given". The model is that the voters will choose, from those choices, 
the choice they prefer, and that might work, but it can't make winners 
out of non-winnerss. It needs the choices passed on from the first stage 
to be good to begin with.

Thus, my cloning and strategy observations are directly focused on the 
first stage. My "degraded voters" concept is also based on this 
observation. I could construct observations for the second stage, but 
that would currently only distract from the more serious ones in the 
first stage.

> At the same time, how could any citizen or group of citizens be able
> to have enough reliable knowledge about how enough other citizens
> will rank candidates in order to be confident enough of having a
> 'strategy' that would have the effect of producing anything other
> than an honest result? In any case, what rational motive would any
> citizen or group of citizens have in ranking other than their favored
> candidates when their honest voting would instead guarantee that each
> of their votes will only strengthen the elected reps they favor more
> than the other reps?>

The incentive I have in mind is to push close competitors or minor 
candidates off the winning set. If a candidate belonging to party A is 
ranked second by a voter and the party can push off that voter's first 
preference by cloning, then A wins. If a candidate belonging to party A 
is ranked third by a voter and the party can push off the first two 
candidates by cloning, then A wins, and so on.

A side effect of this is that it pushes the outcome towards one where 
all candidates that have less than a Droop quota's worth of support are 
excluded, because parties have nothing to lose by cloning to begin with. 
As a result, the party that can pull off the most well-planned vote 
allocation gains an advantage, all other things equal.

(IRV has other incentives for voters to not vote their favorites first, 
but that's not part of the cloning problem, so I won't deal with them 
here. Suffice to say that IRV, like most methods, fails the favorite 
betrayal criterion.)

But first, coordination.

It's true that for the cloning attack to work, the supporters of the 
party have to distribute evenly among the candidates that are part of 
the party or conspiracy. However, due to the way that IRV works, if the 
coordination fails, the party executing the attack loses nothing 
compared to what would have happened if they did not clone to begin 
with. Here's an example somewhat different from my last:

52: X > Y > Z > W
25: Y > W > Z > X
10: Z > W > X > Y
  5: W > Y > X > Z

Three candidates to elect. W gets eliminated, the winning set becomes 
{X, Y, Z}, and the weights are:

X: 52/92 = 56.5%
Y: 30/92 = 32.6%
Z: 10/92 = 10.9%

Now suppose that X would like to capture Z's weight. Since X has more 
than two Droop quotas' worth of votes, it can do so by cloning:

26: X1 > X2 > Y > Z > W
26: X2 > X1 > Y > Z > W
25: Y > W > Z > X1 > X2
10: Z > W > X1 > X2 > Y
  5: W > Y > X2 > X1 > Z

Now, first W and then Z is eliminated and the winning set becomes {X1, 
X2, Y} with weights

X1: 36/92 = 39.1%
X2: 26/92 = 28.3%
Y: 30/92 = 32.6%

So the X party increased its share of the pie from 56.5% to 67.4% and 
from a simple majority to a two thirds majority by cloning. Note how the 
first stage weakens the second - the Z-voters' first preferences are no 
longer counted, instead only their third preferences are.

But what would have happened if the coordination went badly? Then you 
would have got something like this:

50: X1 > X2 > Y > Z > W
  2: X2 > X1 > Y > Z > W
25: Y > W > Z > X1 > X2
10: Z > W > X1 > X2 > Y
  5: W > Y > X2 > X1 > Z

The elimination order is X2 first, then W, and the winning set is {X, Y, 
Z}. The second stage goes as above: no harm befalls X for having cloned.

That still leaves the question of how a party would coordinate their 
voters. Note that the voters aligned with X don't need to know how the 
non-X voters are voting.

How do they coordinate? In SNTV (as was used in Taiwan until 10 years 
ago or so) the need for coordination was even greater, since fielding 
too many clones could cost a party all of its seats. A similar need for 
coordination has shown itself in Hare party list in Hong Kong. So we can 
look at those to get some idea of how parties can coordinate. In Taiwan, 
the strategies differed as the parties tried to find out what worked 
best, but what they ended up doing in the end was:

- To find out how much support it has, Party X polls the electorate.
- Say it has three Droop quotas' worth. It thus fields three canidates.
- It then posts a newspaper ad saying "If your birthday is on the 1st to 
10th of the month, vote for X1. If your birthday is on the 10th to the 
20th of the month, vote for X2. Otherwise, vote for X3."

This gives a more or less even distribution (as there are about as many 
months with 31 days as 30) and lets the voters coordinate the strategy. 
See also https://en.wikipedia.org/wiki/Vote_allocation .

In APR, the situation is a little different. It never hurts to run more 
clones as long as the voters spread their votes evenly among them. If 
there are three seats or winner set positions, the party might field 
three candidates, or field five if there are five seats. Say there are 
three seats. Party X would proceed like this:

- It fields three ccandidates.
- It then posts a newspaper ad saying "If your birthday is on the 1st to 
10th of the month, vote X1 > X2 > X3. If your birthday is on the 10th to 
the 20th, vote X2 > X3 > X1. Otherwise, vote X3 > X1 > X2."

Again, the attack is on the first stage rather than the second stage. If 
the set of winners passed from the first stage to the second is already 
compromised, then the second stage can't compensate even if the second 
stage would happen to be quite fair.

>  > It might turn out that the only way of
>  > making weighted voting work is through either varying the number of
>  > winners (like in party list) [...]
>
>  Is not this what APR does, or have I misunderstood you here?.

Not quite, because the seats in party list aren't just for weighting 
parties, but also for permitting more parties to be represented.

Here I'm going to simplify the example above so everybody bullet votes, 
just to make the point obvious.

Say the voters vote for parties like this:

52: X
25: Y
10: Z
  5: W

and say we have three seats. Webster produces the following allocation:
X: 2, Y: 1

That's the same outcome as if X had cloned in APR above. There are two 
distinct winners: X and Y.

Now suppose that X tries to clone:

26: X1
26: X2
25: Y
10: Z
5: W

Webster produces the following allocation:
X1: 1, X2: 1, Y: 1

so the cloning has no effect. There are now three distinct winners (X1, 
X2, and Y). The method adjusts the number of distinct winners who are 
permitted onto the council, and that is what renders the cloning attack 
above ineffective here. (This is a major reason why Webster is a better 
party list method than SNTV.)

In contrast, APR has a fixed number of winners. If there are three 
seats, it needs to fill them all up, hence it elects {X, Y, Z} in the 
first case and {X1, X2, Y} in the second.

We have that APR's method goes from one set of winners to another set of 
winners after cloning. So either one of those sets (or both) were wrong 
to begin with, or the problem isn't a problem. In other words, the 
responses I can see to this is:

A. The cloning attack is a problem and should be fixed, and {X, Y, Z} is 
the correct outcome; three-seat APR should afford to be more diverse 
than three-seat party list.

B. The cloning attack is a problem and should be fixed, and {X, Y} is 
the correct outcome; the method should behave more like party list does. 
Z has too little support to be represented anyway.

C. The cloning attack is not a problem since unweighted STV exhibits the 
same thing.

The fix depends on which of these conclusions seem more right.

> > [...] or by an unconventional (nondeterministic) voting system or
> > the Asset version of this.
>
>  Is not this what APR does, or have I misunderstood you here?>

No; APR is not nondeterministic (randomized). Nor does it always go to 
an Asset stage.

In the part you quoted, I was thinking about ways of making APR work if 
you came to conclusion A. In particular, the asset version I mentioned 
would be based on something like: give all the candidates initial 
weights according to some election method, stick those candidates in a 
room and let them move their weights around, and let them out again once 
95% by initial weight agree on the distribution (and only as many 
winners as you'd like have nonzero weight, etc). That approach, which is 
a little like forming a government, would have a 5% implicit threshold 
and would also favor the status quo. It might be possible to do better 
and not favor any group, but finding a better method would require 
research along Heitzig's lines.

> > First, why the cloning attack is possible: when we use (call them semi-
> > majoritarian[1]) methods like IRV or Plurality,if candidates
> > represent parties who can clone as many as they want, then I think the
> > strategic equilibrium gives each party a number of seats equal to their
> > number of Droop quotas. If we instead use an unweighted multiwinner
> > method (STV,
> > Schulze STV, etc), then the Droop proportionality criterion gives each
> > party at least their Droop quotas' worth in seats without strategy.
> >
> > Simply, when the number of winners is fixed, the semi-majoritarian
> > methods have an implicit threshold of a Droop quota, and the unweighted
> > multiwinner methods have an explicit threshold of the same.
>
>
> I understand that, above and below, you are exploring the logic of
> these theoretical possibilities but why would we actually want to use
> such needlessly less proportional and much more complicated methods than
> those offered by APR for electing the legislative assembly of a large
> nation?

How are they less proportional? Can you give an example where one of the 
mentioned methods is less proportional than weighted IRV if the second 
stage is the same?

> Correct me if I am mistaken, but perhaps your next post (also copied
> below) provides part of your answer to this question. It seems to worry
> that APR might elect a so-called 'unpalatable set' of reps for the
> assembly. If this is part of your answer, do you still accept that APR
> would always have the best chance of electing an assembly that would be
> entirely palatable to its voting citizens. This is because each citizen
> could rationally see that she has a rep in the assembly who most likely
> will both qualitatively and mathematically (proportionately) represent
> her views?

No, I don't, because the first stage is suspect. I can go into detail 
when we're done with the cloning.

> Is your definition of 'unpalatable' something other than simply 'what
> you happen subjectively to dislike?

It's closer to "what the voters would happen to dislike, were they aware 
of the alternatives". (When the voters in Burlington showed their 
dislike of IRV by repealing it, that wasn't because Warren Smith 
subjectively disliked IRV.)

But this is only distantly related to the cloning problem, so perhaps we 
should talk about the cloning first and then get to this afterwards? 
That way, we won't spread too thin :-)