[EM] Possibly making Sainte-Lague even more STV-like

[Kristofer Munsterhjelm]

I may get back to this in greater detail later, but some notes for now 
(yes, I'm writing late again):

On 09/03/2013 11:07 PM, Vidar Wahlberg wrote:
> On Mon, Sep 02, 2013 at 10:18:36AM +0200, Kristofer Munsterhjelm wrote:
>> Here's a short post (since I don't have as much time as I would
>> like) with an idea of how to make Sainte-Lague even more like STV. I
>> started thinking about it as part of my thinking that "perhaps
>> pairwise multiwinner methods will always be too complex"; and so I
>> tried to include some Condorcet compliance here as well.
>
> I hope I'm not misunderstanding you, but since you're mentioning
> "pairwise multiwinner methods" and parties I'll write a bit about an
> idea I've been playing with recently.

Pairwise multiwinner methods could be any method that fills a council 
using a pairwise setup, i.e. a generalization of a single-winner 
pairwise method. But there's a more specific pattern that turns up in 
many generalizations of pairwise single-winner methods, and I was 
referring to that pattern here.

In this particular generalization, you make a "virtual" single-winner 
election where each winner candidate is a particular assembly. For STV 
methods like CPO-STV or Schulze STV, each such winner is then a list of 
candidates, so there are n choose k of them. (These methods tend to be 
computationally expensive). For my "CPO version" of the "eliminate 
parties that don't have a chance" system, each winner is a list of 
parties that are part of the outcome (i.e. not eliminated), so there are 
2^(num parties) virtual candidates. My very complex nameless pairwise 
Sainte-Lague/Approval system also has n choose k winners and thus is 
utterly infeasible for a national count unless it can be mathematically 
reduced to something more like my CPO-SL.

In any case, these systems then define a pairwise function, call it 
f({A}, {B}), where A and B are virtual candidates, and the pairwise 
score of {A} against {B} is f({A}, {B}), while the pairwise score of {B} 
against {A} is f({B}, {A}). Note that this is the score prior to any 
thresholding (margins, wv, etc).

Then you just determine which virtual candidate wins and parse that back 
into an assembly. That assembly wins.

(A final note: Schulze STV bases its f({A}, {B}) on an inner function 
which one may call g({A}, {B}), that is only defined when the two sets 
differ by one candidate. f({A}, {B}) extrapolates this into every 
one-on-one by a strongest-path logic similar to that of the Schulze 
method itself.)

> I'm a fan of Condorcet methods, and notably Ranked Pairs. I wanted to
> try modifying RP in a way so it could be used for party-list elections,
> giving a result where the party most people agree on being the best
> party wins the most seats, rather than the party that have the most
> first preference votes. Party having the most first preference votes may
> of course also be the party that most people agree on being the best
> party.

[snip]

> Now the idea was that if some voters expressed a second preference, that
> should cause the second preference to win more seats, but not at the
> expense of the first priority, only at the expense of the other parties.
> So I made every vote for FRP have H as second preference, while leaving
> all other votes have no second preference. This gave me _almost_ the
> result I expected:
>     A: 46 seats
>    SV: 12 seats
>    RV:  2 seats
>    SP:  9 seats
>   KRF:  9 seats
>     V:  8 seats
>     H: 40 seats
>   FRP: 41 seats
> KYST:  1 seat
>    PP:  1 seat
>
> As expected, H won seats from the other parties, but to my surprise,
> FRP also won more seats, even though no votes ranked FRP higher than in
> the previous run, and it was the exact same amount of votes.
> I haven't dug deep down into the code yet to figure out why it benefited
> FRP to add H as second preference.

I think there are two problems here.

First, because of the sequential nature, this method must pass house 
monotonicity (as does ordinary Sainte-Laguë). That means that for any k, 
the outcome for k-1 seats is a subset of the outcome for k seats. But 
let's do a quick and dirty LCR example again:

48: L>C>R
42: R>C>L
10: C>R>L

where L is left-wing, C is center, and R is right-wing.

If you're electing just one seat, then C should win; anything else would 
be unfair to a majority. But if you're picking two, then if you give the 
first seat to C, giving the second to L will bias the assembly to L and 
giving the second to R will bias the assembly to R. So the right outcome 
for two seats would be {LR}. But {C} is not a subset of {LR}, so house 
monotonicity is not desirable. You might argue that {C1, C2} would fix 
the problem, but that would just push the problem itself into the 
three-seat case.

Second, a voter may gain undue power with additional preferences. Say a 
voter's preference is H > FRP. Then when a H seat is chosen, that will 
deweight his preference for H over AP (say), but it won't deweight his 
preference for FRP over AP. Thus some of his pairwise preferences get 
counted at full strength even though he got his first choice.

If you want to go down this sequential deweighting route, I think you 
should instead deweight the ballots themselves. So say H gets a seat. 
Then everybody who voted for H first should have his ballot deweighted, 
including later preferences (e.g. FRP > AP). That method isn't summable, 
but it's better[1]. You'd end up with something somewhat similar to 
Forest Simmons and Olli Salmi's "D'Hondt without lists", but with 
Sainte-Laguë instead of D'Hondt. See 
http://lists.electorama.com/pipermail/election-methods-electorama.com/2002-August/008561.html 
.

> For those especially interested, the code (still using the D language)
> is located here:
> https://github.com/canidae/voting/blob/master/slrp.d
> (Rough code, minimalistic RP, likely buggy, etc.)
>
>
> Any thoughts? And is it something like this you're talking about,
> Kristofer, or did I misunderstand you?

[1] Making a strongly summable setwise proportional method would make a 
lot of EM members pay attention, I think. I suspect it's impossible, but 
I only have a heuristic argument for it. By "strongly summable" I mean 
something that is summable with O(n^k) numbers of O(log(v)) digits each, 
n being the number of candidates and v the number of voters, for some 
constant k.