From: Gervase Lam <[EMAIL PROTECTED]> 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 ---- Election-methods mailing list - see http://electorama.com/em for list info
