From: Kevin Venzke <[EMAIL PROTECTED]> Subject: Re: [EM] Re: "sprucing up"
Forest,
I certainly think this is an impressive, interesting idea, even if I don't have a lot of comments on it. But:
--- Forest Simmons <[EMAIL PROTECTED]> a écrit :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.).
I raise an eyebrow upon reading this,
[I wish I were that coordinated. It must be one of those genetic things.]
since if all you have done is eliminate clones, how can River, RP, and Schulze produce different winners when they haven't been "spruced up"? All of those methods are supposed to be clone-proof.
Before eliminating clones we eliminate all covered candidates. I suspect that this step by itself would take care of the extant examples that separate River, RP, and Schulze.
Also, there are clones, and then there are "beat clones." Every clone is a beat clone, but not vice versa. IRV is clone free, but not beat clone free, since whenever there is a CW, the remaining candidates form a beat clone set, and when that set is collapsed, the resulting two-alternative election is handled neatly by the CW.
Even RP is not beat clone free since it could quite possibly give the win to C in a tournament where A beats both B and C, both of which in turn beat D, who beats A. But C is the Condorcet Loser in the beat clone set {B,C}, so C could not possibly win in any spruced up method.
Moreover, in the spruce up process, C would not even survive to the collapsing-of-clone-sets step, because C is covered (by B).
Recall that B covers C iff B beats C, and B also beats every candidate that C beats. In this case C beats only D, and both C and D are beaten by B. So in the language of game theory, B "dominates" C.
In game theory, it is posited that a rational player with perfect information about the other players' preferences would never bet on a dominated alternative. So in the game of continuing-to-field versus withdrawing of candidates (before the election), rational supporters with perfect information would withdraw C from the election. If they lacked the authority to do that, they would simply focus their efforts on electing somebody else, without worrying about the consequences to C.
If every candidate were dominated by some other candidate, this would lead to a circular paradox, but this problem never arises, since there is always at least one uncovered candidate.
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 ?
Sprucing up Bucklin and IRV seem particularly interesting. But I doubt it is able to do anything helpful with the 49 A, 24 B, 27 C>B scenario.
[I curl a tongue upon reading this.]
For you to express doubt about this example, you must not have understood (due to my poor exposition) that the three candidate case occurs in spruced up methods only if there is no CW.
[The converse of this statement is also true in the case of public elections.]
In fact, according to step one of the sprucing up process, every spruced up method chooses from the uncovered set, which (in turn) is contained in the Smith set, so spruced up methods satisfy the Generalized Condorcet Criterion.
In this case C is the only uncovered candidate, so the other two candidates are eliminated in the first step. But even if we left out the first step, the sets {A,B} and {B,C} are both beat clone sets. It doesn't matter which of these sets is collapsed: if we collapse {A,B} then the resulting winner is C, one of the original candidates, so we are done.
If we collapse {B,C} then the winner (between A and the clone set) is the clone set, which is not one of the original candidates, so the spruce up rules say that we apply the method within the winning clone set {B,C}. Inside this set C wins. Since C is one of the original candidates, C is the winner.
As it did in this example, the ambiguity of the irreducible beat clone decomposition always turns out to be harmless (at least in the applications I have considered).
More to the point, eliminating covered candidates before collapsing beat clone sets entirely removes the ambiguity, so this difficulty never arises in the spruce up process.
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.
It's not so, though. I believe he immediately eliminates any candidate with fewer than 1/3 of the first preferences. He has diagrams to justify this, but unfortunately I can't understand them.
This seems like a reasonable rule in the case of three candidates without a CW, which is the only case the method would ever encounter if spruced up.
However, I'm leaning towards Spruced Up Bucklin, which resolves three candidate cycles MCA style, for which I have a certain fondness.
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.]
Yes, that would be extremely interesting.
It would be nice, in general, if key differences in the behavior of methods could be shown in diagrams. I don't know how to do such a thing, though.
I believe that Rob LeGrand has automated this. The trick is to project the above mentioned triangle into a two dimensional coordinate system:
First let R, G, and B be position vectors for the vertices of a nearly equilateral triangle, say R=[0,0], G=[100%,0], and B=[50%,87%]. Then (with a random number generator) you pick x and y less than 100% at random, calculate z as 100%-x-y, and use your method to find the winner for the election
x RGB y GBR z BRG
Finally color the point P=x*R+y*G+z*B with red, green, or blue, depending on whether the winner was R, G, or B.
Repeat the process until the shapes and boundaries of the colored regions manifest themselves.
Pay particular attention to the region where there is no majority winner, i.e. where max(x,y,z) < 50, which is the only area of concern for our spruced up methods.
This region is the interior of the triangle whose vertices are the midpoints of the sides of the triangle RGB. If the three triangles complementary to this center triangle get colored solid with the color of their respective main vertex R, G, or B, then the method satisfies the majority criterion (for this three faction case).
After going through this whole process with several election methods, try to develop some intuition for matching geometrical features with election method properties.
Once this intuition starts to develop, try using it to design a new method, and then test this method to see if it has the design properties that you were hoping for, etc.
Keep in mind, however, that the method must satisfy Symmetric Completion and Reverse Cancellation for the results to extend beyond this three faction case, and even then, the sprucing up process may or may not preserve properties like "mono subtract no later harm chicken flu," etc.
I hope that my answers didn't insult anybody's intelligence. After all, I do hope that they are read by neophytes as well as oldofights :')
Forest
---- Election-methods mailing list - see http://electorama.com/em for list info
