[EM] Sprucing up MMPO and other methods
Forest Simmons
simmonfo at up.edu
Tue Dec 21 16:09:14 PST 2004
> 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
More information about the Election-Methods
mailing list