The sprucing up process only does two things: (1) it eliminates uncovered candidates, and (2) clone proofs the method. It is amazing to me that those two steps alone do everything except resolve cycles of three.
In other words, if two methods always resolve cycles of three in the same way, then their spruced up versions will be equivalent in public elections, no matter how many candidates there might be.
In particular, Spruced Up River, Spruced Up Ranked Pairs, Spruced Up Short Ranked Pairs, Spruced Up MinMax, Spruced Up SSD, Spruced Up PC, etc. are all equivalent as long as they all go with the same choice for measuring defeat strength (wv, margins, cardinal pairwise, approval, etc.).
Consequently, we can subsume all of these methods under the title of "Spruced Up Condorcet," which might come in handy at public proposal time.
Also Spruced Up Bucklin and Spruced Up Weighted Median Approval (Chris' version) are equivalent.
Spruced Up Black is equivalent to Spruced Up Borda.
How about Spruced Up IRV ?
I have heard that Craig (of Polytopes and Politicians) has a good three candidate method. If so, then its spruced up version should be a good public election method.
Let's go a little further. Let's suppose that we have a method that satisfies the following reverse cancellation property:
A ballot of the type ABC is cancelled by its reverse BCA, i.e. removing both of them has no effect on the winning probabilities.
If a method based on ordinal ballots satisfies this cancellation property and the Symmetric Completion Criterion (as well as anonimity, etc.). Then results of the spruced up version of the method are completely determined by how it resolves a three faction cycle of the type
x ABC y BCA z CAB
where max(y,z) < x < y+z .
If two election methods resolve all such cycles in the same way, and they both satisfy the Symmetric Completion Criterion, the Reverse Cancellation Property, etc. then their spruced up versions will give equivalent results, i.e. will assign identical winning probabilities to the respective candidates in all public elections, no matter how many candidates there may be.
[The "public election" assumption is that (1) there are no pairwise ties, and (2) there are no cycles with as much symmetry as the cycle C(i) beats both C(i+1 mod 5) and C(i+2 mod 5) for i in {0,1,2,3,4}.]
With little or no loss in generality we can assume that x+y+z=100%. This equation determines a triangle with corners at (100%,0,0), (0,100%,0), and (0,0,100%) in the first octant of a three dimensional coordinate system. The inequalities max(y,z) < x, and x < y+z narrow down to a subset R of this triangle. Each partition of R into three subsets (winning regions for A, B, and C, respectively) determines a (deterministic) method.
In other words, design of election methods (of this type) amounts to shading in subsets of a triangle. How about that for a "Geometry of Voting"? [This is more like what I was hoping for when I read Saari's book by that title.]
It should be instructive to compare how the (symmetric completion version of) the various methods mentioned above allocate the points of R to A, B, and C.
For methods failing either Symmetric Completion, Reverse Cancellation, or Determinism there are more degrees of freedom, so a two dimensional diagram is not adequate. Evidently, these extra degrees of freedom are necessary for the defense criteria satisfied by winning votes versions of Condorcet methods, for example.
I know that this exposition is somewhat abstract and lacking in nitty gritty details, hence open to misunderstanding. If I have piqued your interest, and you would like more complete explanations, just let me know, so I can ask someone with more patience (like Jobst) to provide some concrete examples, etc. if I don't have time to do it myself.
Cheers!
Forest
From: Forest Simmons <[EMAIL PROTECTED]> Subject: [EM] Sprucing up MMPO and other methods
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 [EMAIL PROTECTED] http://lists.electorama.com/listinfo.cgi/election-methods-electorama.com
End of Election-methods Digest, Vol 6, Issue 19 ***********************************************
---- Election-methods mailing list - see http://electorama.com/em for list info
