[EM] condorcet loser elimination PR

[Adam Tarr]

Rob Speer wrote:

>has anyone devised a method to compare entire slates of candidates
>that reaches a decision without, well, comparing every possible slate of
>candidates?

Not to my knowledge.  But I don't think anyone's put a serious effort into 
it.  I imagine that, like many potentially intractable problems, a 
reasonable approximate solution can be found.  For example: lets say you 
were using PAV or some PR Condorcet method to elect 8 winners out of (being 
pessimistic here) 80 candidates.  I imagine you could use some sort of 
genetic algorithm with multiple randomized starting points, to whittle the 
billions of potential slates down to a manageable few hundred thousands, 
which could be cranked through manually.  I'm sort of talking out my ass 
here, but you get the idea.

>An important criterion of an election method, to me, is that it runs in
>polynomial time in the number of candidates. So far, the only
>proportional methods I've seen that satisfy this are list PR, STV, and
>sequential PAV.

I guess you consider cumulative voting, et cetera, to be too crude to 
qualify as true PR methods.

If it's a choice of those three, I'd pick STV first.  I think I'd prefer a 
well-designed open-list PR to sequential PAV, although it's a near 
thing.  sequential PAV can run into the same pitfalls that David Gamble and 
others found in sequential Condorcet PR methods.

I just had an idea on a method to reduce PAV complexity.  You could start 
by guaranteeing proportionality among the parties, a-la list PR.  If 
someone approves across party lines in this stage, then their vote counts 
toward each party in the fraction of their approvals that are for 
candidates of that party.  So if I approve three Democrats and two 
Republicans, and nobody else, then I cast .6 Democratic and .4 Republican 
votes in the list PR portion of the election.

In the second stage, you actually use PAV to elect the 
representatives.  Since the number of reps from each party is fixed, the 
number of potential slates to consider is dramatically reduced.

I don't claim this method to be especially wonderful, but if reducing the 
complexity of PAV is your main goal, then this does the job.

-Adam