[EM] Fixing IRV

[Anthony Simmons]

>> From: Richard Moore <rmoore4 at home.com>
>> Subject: Re: [EM] Fixing IRV

Richard,

Everything you say is valid.  I don't know what I was
thinking.  Well, actually, I do.  I was reacting the way I
always do when people suggest that a problem is unsolvable
because of incompleteness.  Odd, given Gregory Chaitin's
discovery that "most" problems are unsolvable.

About defining an elimination method, doesn't that sound like
kind of a hopeless task?  It's pretty simple to define one in
terms of the definition, such as it is, that I mentioned
earlier.  One simply constructs a sequence of election
methods, En, En-1, ... E1 (please excuse the clumsy
subscripts).  The first has n candidates, the second has n-1,
etc., etc.  They all have the same number of ballots (same
meaning that you remove one candidate from ballots and close
up the holes to get the next in the sequence).  I don't have
a clue how that could be expressed in a form that would suit
your purposes.  And it suffers from the same difficulty in
actually working with it that you note below.  (Actually,
only the first and last elements in the sequence are needed
in order to define "elimination method".)

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