[EM] Re: "sprucing up"

[Forest Simmons]

The most amazing and directly useful result in the "sprucing up" message 
below is that (for public elections) the only case we have to worry about 
is a cycle of three.  If we can decide how to resolve cycles of three, the 
sprucing up process takes care of the rest.

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 <simmonfo at up.edu>
> Subject: [EM] Sprucing up MMPO and other methods
>
>> 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
>
>
> ------------------------------
>
> _______________________________________________
> Election-methods mailing list
> Election-methods at electorama.com
> http://lists.electorama.com/listinfo.cgi/election-methods-electorama.com
>
>
> End of Election-methods Digest, Vol 6, Issue 19
> ***********************************************
>