[EM] Sprucing up MMPO and other methods

[Forest Simmons]

> From: Gervase Lam <gervase.lam at group.force9.co.uk>
> Subject: Re: [EM] MMPO, Majority, Condorcet failures
>
>> Date: Mon, 20 Dec 2004 21:59:38 +1030
>> From: Chris Benham
>> Subject: [EM] MMPO, Majority, Condorcet failures
>
>> To me the price MMPO  (MinMax Pairwise Opposition) pays for strategy
>> benefits you describe is just far too high,
>> failing as it does (Mutual) Majority and  Clone-Winner.  (Also very
>> unattractive to me is that it  combines meeting
>> Later-no-harm with failing Later-no-help, and thus having a
>> zero-information  random-fill incentive.)

When an otherwise good method fails Clone Independence and/or the 
Condorcet Criterion, perhaps it can be rescued by the following general 
"spruce up:"

1.  Eliminate covered candidates until each remaining candidate has a 
short (length one or two) beat path to each of the other remaining 
candidates.

2.  Collapse all proper "beat clone sets."

3.  Apply the rescue worthy method, say MMPO, to the resulting set of 
ballots.

4.  If the winner in step 3 is one of the original candidates, then we are 
done.

5.  Otherwise, the winner is one of the collapsed clone sets. In this case 
we (recursively) use this "spruce up" on the clone set to find a winner.

A few details:

In step one form a matrix M whose (i,j) element is one if candidate i 
beats candidate j pairwise (as well as in the case if i=j), but is zero 
otherwise.  Then form the matrix A=M^2.

The (k,n) element of A will be zero if and only if there is no short 
beatpath from candidate k to candidate n, which means that candidate k is 
not among the uncovered candidates. Accordingly, we eliminate row k and 
column k from the matrix M. After taking care of all of the rows of A that 
have zero entries in this manner, we repeat the procedure with the new 
matrix M', and new matrix A', etc. until each remaining candidate has a 
short beatpath to each of the other remaining candidates, if there is more 
than one candidate left.

For step two, remember that a set C is a proper beat clone subset of a set 
S of candidates iff (the cardinality #C is strictly between one and #S 
and) if X is any candidate in S-C, then either X beats every member of 
C, or else X is beaten by every member of C.

In general some of the proper beat clone sets may themselves contain 
proper beat clone subsets.  So the containment relation gives rise to a 
nested family of beat clone sets, for which the Hasse diagram is a tree.

The leaves of the tree are individual candidates. Each of the other nodes 
represents an irreducible decomposition of its branch nodes into beat 
clone sets.

Now, how do we "collapse" a beat clone set?  We start with the nodes one 
level above the leaves, the first level of "proper" beat clone sets.

Suppose that C is one such set.  We go to the ballots and replace the 
members of C with a generic candidate "C."

How do we do this?  If the ballots are CR style, then on each ballot we 
give "C" a rating which is the average of the ratings of the members of C
on that ballot.  If the ballots are ordinal style, then we give "C" a rank 
that is the average (alternatively, median) of the ranks of the members of 
C on that ballot.

[If the "average ranking" alternative is used, the pairwise matrix can be 
adjusted directly, without going back to the individual ballots.]

Having collapsed the lowest level proper beat clone sets, these collapsed 
elements become the new leaves on the trimmed tree, so the procedure can 
be repeated until all of the proper beat clone sets are collapsed, which 
sets the stage for step three in the above "spruce up."

Remark. We use "beat clone sets" because they are more robust than clone 
sets defined by clustering on the ballots.  For example, if A, B, and C 
are members of a beat clone set they can be separated by other candidates 
on a significant number of ballots (e.g. ADBECFGH) without destroying the 
beat clone relationship.  In other words, a beat clone set doesn't have to 
be a beat clone set relative to each individual ballot. In this example, 
the collapse of {A,B,C} on the ballot ADBECFGH would result in the ballot 
D"C"EFGH.

Remark 2.  If we "spruce up" random ballot, the result is the same as 
using random ballot to choose among the uncovered set, i.e. the clone 
collapsing step doesn't change any winning probabilities.

Conjecture.  "Spruced Up Copeland (with random ballot completion)" is 
identical with random ballot among the uncovered set. I haven't been able 
to construct a counterexample.  In other words, every time I complete 
steps one and two in the spruce up process, if there is no Condorcet 
Winner, I end up with a tournament (typically among collapsed clone sets) 
in which each clone set beats the same number of clone sets, i.e. a 
Copeland tie.

In particular, it always happens that the number of clone sets in the 
tournament is odd, almost always one or three.  The case of five is 
always isomorphic to  A beats B and C, B beats C and D, C beats D and E, D 
beats E and A, and E beats A and B, which has a highly unlikely degree of 
symmetry for a public election.

It has been kind of fun exploring the possibilities of this "spruce up" 
process.  I hope that some of you will play with it, and report your 
findings, especially if you find something at odds with what I have led 
you to believe in the above message.

Happy Holidays,

Forest