[EM] Fixing IRV

Anthony Simmons bbadonov at yahoo.com
Sat Aug 11 15:41:11 PDT 2001

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

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

>> It is not reasonable to ask for a way to check this in
>> general. As Godel showed, there are true statements in
>> mathematics for which no proof can be found. So we may have
>> to live with the possibility that there may be methods out
>> there for which we cannot determine (with the certainty of
>> mathematical proof) if there is an equivalent
>> non-elimination method. If so, the proposition that the
>> equivalent exists (or not) for such a method will remain a
>> conjecture. Maybe it's true that no such problematic methods
>> exist (meta-statement). Maybe someone can even prove (or
>> disprove) this meta-statement. Then again, maybe the
>> meta-statement is true but cannot be proven.

>> In other words, "don't go there".

>> Richard

The answer falls out of its own accord if I just
reformulate the problem in sufficiently rigorous

Let the number of voters be N, and the number of ways of
marking a ballot (valid ways plus one general way called
"invalid") be m.  Then there are N^m distinct ways that all
of the ballots can be marked.  (If you like, you could
include all registered voters in N, and include one more way
of marking the ballot, "unvoted".)

Each way of marking the ballots maps to an outcome, which is
a ranking of the candidates, allowing for whatever
peculiarities, such as ties, might be allowed.

Call this function, which maps sets of marked ballots to
outcomes, an "election method".  Each election method, being
a function, is just a set of ordered pairs; each pair
contains one set of ballots and the outcome they map to.

Each election method is a finite set (with N^m elements) of
ordered pairs.  Since every election method is a finite set,
there is an effective, if somewhat tedious, method of
comparing two of them to see if they are equivalent --
compare their members.  One of those "at least in principle"
things.  Since the number of election methods is also finite,
it is, again at least in principle, possible to compare a
given election method with all other election methods (or
with a subset of them) to see if they are equivalent.

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 does *not* mean there's a
feasible method.

Life is so easy with finite sets.

More information about the Election-Methods mailing list