[EM] Re: questions about sprucing up

[Forest Simmons]

> From: Kevin Venzke <stepjak at yahoo.fr>
> 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 <simmonfo at up.edu> 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