# [EM] condorcet loser elimination PR

Adam Tarr atarr at purdue.edu
Tue Jul 22 22:00:03 PDT 2003

```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

```

More information about the Election-Methods mailing list