[EM] Fixing IRV
Richard Moore
rmoore4 at home.com
Sun Aug 12 12:06:16 PDT 2001
Anthony Simmons wrote:
> Fortunately for everyone who is eager to get started matching
> them up, election methods have to be compared only with
> others that have the same number of ballots. N is an
> arbitrary variable, and the proof says that for any N, the
> result is true. This amounts to having a separate proof for
> each N, and for each proof, the number of possible
> comparisons is finite.
>
> "In principle" just means that the actual act of comparing
> sets only has a finite number of steps, and implies that it
> may not be practical.
Anthony,
Even if we limit ourselves to a finite number of cases, we
still don't have a way to apply this to Markus' question,
which was "How do you want to check whether a given
elimination method can also be defined as a method that
doesn't "eliminate alternatives prior to selecting a
winner"?" For when we speak of "elimination" we are
classifying methods according to their algorithms, not by
their output. So for a given method, you can generate all
possible input/output pairs (given a finite limit on the size).
You also wrote "Therefore, it is possible (yes, "at least in
principle") to prove that a given election method is or is
not equivalent to a non-elimination method." This assumes we
are given both methods and want to compare them. But we were
presented with a different problem, which is that if we are
given one method that uses elimination, how do we either
find an equivalent non-elimination method or else prove that
one doesn't exist? To answer Markus' question using the
large finite sets approach, you then have to turn to the
question of "What algorithms could have generated these
outputs for these inputs?", and then answer the question,
"Are any of these algorithms non-elimination algorithms?"
I imagine you could generate an algorithm of arbitrary
complexity for a finite set of inputs and outputs. So don't
we still have an infinite number of equivalent algorithms to
examine?
What we are looking for is a definition of "elimination"
that will allow us to cleanly split the set of all possible
methods into elimination methods and non-elimination
methods. I agree with Markus that this isn't an easy thing
to define, but should we conclude that no useful definition
exists? (By "useful" I mean that you could build theorems
around the definition.)
Richard
More information about the Election-Methods
mailing list