[EM] Fixing IRV

[Forest Simmons]

Thanks to Blake for the comments on my previous fix.

The following example has dampened my enthusiasm for Roy's IRV fix based
on eliminating the candidate with the lowest median rank:

13 ABCXD
13 BCDXA
13 CDAXB
13 DABXC
16 XABCD
16 XBCDA
16 XCDAB
100

Note that X is both the Condorcet Winner and the candidate with the lowest
median rank.

Roy's fix doesn't quite satisfy the Condorcet Criterion after all.

But Roy's idea inspired the following fix of the fix:

At each stage of the runoff eliminate the candidate whose median pairwise
support is smallest.

This method does satisfy the Condorcet Criterion and can be computed from
the pairwise matrix, so it is superior to the method that inspired it on
both counts.

Here's another nice property:

In a three way contest it will always give the same result as Ranked
Pairs. [Check me on this.]

This latter property is the reason I prefer it over what Blake calls
pairwise elimination. 

Now here's a proof of the most important of these three properties.
 
Condorcet Criterion Satisfaction Proof:

We just need to show that when there is a Condorcet Winner, then that CW
is not eliminated by the method.

Let's call the CW just C for short.

All of C's wins are by more than fifty percent of the ballots, so at each
stage of the runoff C's median support is more than fifty percent. 

Let's call the (remaining) candidate with least median support L for
short.

Suppose that L = C .

This would mean that all of the (remaining) candidates have median support
of more than fifty percent. 

That would mean that all of the candidates had at least as many victories
as defeats (among remaining candidates).

And since C has strictly more victories than defeats, this would mean that
the total number of victories exceeded the total number of defeats.

This cannot be so, since victories and defeats come in pairs.

We were lead to this impossibility by assuming that L and C were the same
candidate. Therefore they are not.

Eliminating L does not eliminate C.

QED

Forest


On Fri, 10 Aug 2001, Blake Cretney wrote:

> On Fri, 10 Aug 2001 13:46:08 -0700 (PDT)
> Forest Simmons <fsimmons at pcc.edu> wrote:
> 
> > Here's another way to fix IRV:
> > 
> > At each stage of the runoff eliminate the candidate with the
> greatest
> > pairwise defeat.
> 
> I call this pairwise-elimination on my web site.  It is clone
> independent, and meets the Smith criterion (which implies the
> Condorcet criterion).  However it is non-monotonic, and fails reversal
> symmetry.
> 
> > This method is very close to minmax, but not quite the same.
> 
> Minmax is monotonic at the expense of clone independence and Smith. 
> It isn't reverse symmetric either.  Both methods pass the Condorcet
> criterion.  They can be expected to be quite different when there is
> no Condorcet winner.
> 
> Another method would be to eliminate the candidate with the fewest
> first preferences among the non-eliminated candidate (like IRV) until
> one candidate is the Condorcet winner.  This has similar properties to
> pairwise-elimination.
> 
> Also, the method Roy Johnson mentions,
> > Method: Compute the sum of each row. Eliminate the row and column
> > corresponding to the lowest sum, repeat with remaining figures.
> 
> is Nanson's method.  It passes Smith, but fails clone independence,
> monotonicity, and reversal symmetry.
> 
> ---
> Blake Cretney
> 
> See my Election Method Resource page at
> http://www.fortunecity.com/meltingpot/harrow/124
> 
>