[EM] MinMax and Smith

[fsimmons at pcc.edu]

There may be an advantage to a Condorcet efficient method that doesn't always
elect from Smith: it may decrease the incentive to bury, since the purpose of
the burial strategy is to get a non-Smith member into the top cycle.

However that may be, we can easily and seamlessly enhance MinMax(AWP) to choose
from the uncovered set (hence from Smith) in a way that also satisfies
Independence from Non-Smith Alternatives:

1.  Let C1 be the MinMax(AWP) winner.  Elect C1 if it is uncovered, else ...

2.  Let C2 be the MinMax(AWP) winner among the alternatives that cover C1.  
Elect C2 if it is uncovered, else ...

3.  Let C3 be the MinMax(AWP) winner among the alternatives that cover C2.  
Elect C3 if it is uncovered, else ...

etc.

Proof of Independence from Non_Smith Alternatives:

Let  C_i  be the first member of the sequence  C1, C2, ...,W  which is in the
Smith set.  Then C_(i-1) is not in Smith, so the entire Smith set is a subset S
of the alternatives that cover C_(i-1).  Since C_i is the MinMax(AWP) winner of
S, and no defeat of a Smith candidate comes from outside Smith, C_i is also the
MinMax(AWP) winner over Smith.  In other words, from C_i onward, the non-Smith
alternatives are irrelevant.

It also turns out that this enhanced method satisfies Independence from Pareto
dominated Alternatives, Clone Independence, and Monotonicity.

In practice, W will almost always be found on the first or second step of the
enhancement.

The method is summable in two matrices M and A, where M(x,y) is the number of
ballots on which alternative x is ranked above alternative y, and A(x,y) is the
number of ballots on which x is ranked but y is not.

First form matrix M' by subtracting the transpose of M from M.  Then form A' by
replacing each positive entry of M' by the corresponding entry of A, while
zeroing out the rest of the entries.

The positive entries of A' represent the AWP defeat strengths.  The covering
relations can be recovered from A' as well.  So A' has sufficient information to
carry out the enhancement.

Forest