[EM] proof that ER-IRV(fractional) meets WDSC?

[James Green-Armytage]

Mike wrote:
>
>As for ERIRV(fractional), I wasn't going to bring this up, but now I'm
>not 
>sure of my claim that ERIRV(fractional) meets WDSC. About a year ago I
>found 
>a demonstration that it does. I made that claim in postings. But I
>haven't 
>succeeded in demonstrating it more recently. Maybe I made an error in my 
>earlier demonstration that ERIRV(fractionial) meets WDSC. I now have
>neither 
>a proof that ERIRV(fractional) meets WDSC, nor an example in which it
>fails 
>WDSC. Anyone else is welcome to post either.

	I haven't written many proofs at this point, so this is very rough and
messy and probably uses uncouth notation. I think that it works logically,
though... I welcome any serious feedback the proof, i.e. whether or not it
is correct, and how I might improve it. I will try to post an improved
version later on if I get enough feedback.
	It seems highly possible that this proof is longer than it needs to be. 
	(It might have been easier if I assumed that the majority voters would
rank Z as tied for last place, but I didn't want to make that restriction
if it wasn't necessary, which it doesn't seem to be. Apparently a majority
ranking A in first or tied for first, and Z anywhere below A, is
sufficient to assure that Z cannot win...)

Definition of WDSC:
If a majority prefers one particular candidate to another, then they
should have a way of voting that will ensure that the other cannot win,
without any member of that majority reversing a preference for one
candidate over another.

Definition of ER-IRV(fractional):
1. Ranked ballots, with equal rankings allowed.
2. Do a ballot count for each candidate as follows: Add 1 to the vote
total of a candidate for each ballot which ranks them alone in first
place. Add 1/n to the vote total of a candidate for each ballot on which
they are in an n-candidate tie for first place. (By first place, I mean
the highest ranking given to a non-eliminated candidate.)
3. Eliminate the candidate with the lowest vote total.
4. Repeat steps 2 and 3 until only one candidate remains.

___________________________________
Proof that ER-IRV(fractional) satisfies WDSC:
___________________________________

1. Assume that there are two pools of votes, a majority pool and a
minority pool. The majority pool contains m votes, and the minority pool
contains n votes. m>n. 
The number of votes is v. All votes are in one pool or the other; that is,
m+n=v.
2. Assume that all votes in the majority pool rank A strictly in first
place or tied for first place, and that all votes in the majority pool
rank Z below A.

Goal: Show that Z cannot win...

Case 1: All votes in the minority pool list Z as the strict favorite.
3. A's top choice vote total is always greater than or equal to all other
candidates with the possible exception of Z. 
4. If any votes in the majority pool rank A strictly in first place, no
other candidate (except possibly Z) can have a greater top choice vote
total than A in any round, and if the last round is between A and Z, A
will win.
5. If all votes in the majority pool list one or more other candidates Bi
as being tied with A in first place, then A may be randomly eliminated
before one of these candidates, but if so, at least one Bi will make it to
the last round, and if Z makes it to the last round as well, a Bi will
defeat Z.

Case 2: Some votes in the minority pool list a candidate Bi above Z.
6. The number of Bi>Z votes in the minority pool is r.
7. The number of strict A>Bi votes in the majority pool is s. 
8. If r>s, it is possible for Bi to have more top choice votes than A at
some stage before Z is eliminated, so A can be eliminated before Bi while
Z is still in the race. However, Bi will beat Z if they both make it to
the last round, because m-s+r > m > v/2.
9. If r=s, A and Bi have the same number of top choice votes as long as Z
is not eliminated, so A can be eliminated randomly in favor of Bi.
However, Bi will beat Z if they both make it to the last round, because
m-s+r = m > v/2
10. If r<s, Bi cannot have more top choice votes than A as long as Z is
not eliminated, so Bi must be eliminated before A, unless Z is eliminated
first.
11. These statements hold for any number of Bi candidates.

Case 3: Some votes in the minority pool list a candidate Bi as being tied
with Z
12. Treat any ...>Z=Bi>... vote as 1/2 of a ...>Z>Bi>... vote and 1/2 of a
...>Bi>Z>... vote. In ER-IRV(fractional), this kind of symmetric
completion cannot alter the result. Given symmetric completion, case 3
reduces to case 2.

Conclusion:
13. Any candidate Bi such that A can be eliminated before Bi while Z is
still in the race will be capable of defeating Z if they both make it to
the last round.
14. Thus, if A is eliminated, then at least one candidate capable of
beating Z will remain in the race, and no candidates (other than Z) that
are incapable of beating Z will remain in the race.


James Green-Armytage