[EM] Re: sprucing up

[Forest Simmons]

Dan,

Thanks for your interest.

"Sprucing Up" is still in a state of evolution.  Originally it meant 
restricting to the Uncovered Set, then collapsing any "beat clones" that 
might remain, then (recursively) applying the method being spruced up
to the collapsed clone sets until an actual candidate comes up winner.

Later we changed "Uncovered" to "Dutta" to take into account that the only 
candidates that would have a chance of winning with sophisticated rational 
voters with perfect information (and some other standard assumptions) 
would be members of the Dutta Set, the set of candidates that should 
receive positive probability in a kind of generalized rock, paper, 
scissors game with regard to the candidates.

[On the count of three we both announce a candidate.  If your candidate 
beats mine pairwise, then I give you a dollar.  Candidates that are 
dominated by better choices in this game are not strong enough to be taken 
seriously by sophisticated voters with perfect information.]

Beat clone sets are a slight generalization of what some folks have called 
"subcycles."

In Dutta Sets based on public elections there would probably never be any 
difference between a subcycle and a proper beat clone set.

A beat clone set Beta is a set of candidates such that every candidate not 
in Beta is either beaten by all members of Beta or by no members of Beta.

This "beat consistency" allows us to treat the beat clone set as though it 
were a single candidate in pairwise comparisons with other candidates and 
other beat clone sets.

Mentally we collapse the beat clone set to a point, i.e. we "mod it out" 
to use the language of algebra.  [Compare how multiples of twelve all get 
collapsed to zero in clock arithmetic.  Mathematicians call this 
"arithmetic mod twelve," an example of modular arithmetic.]

Of course each singleton set is a beat clone set, so the interesting ones 
are the proper beat clone sets ... those with more than one member, but 
fewer than the total number of candidates.

It is obvious that singleton sets are not cycles, so this is one 
difference between subcycles and beat clones.

Not even every proper beat clone set is a cycle:  If A beats both B and C, 
then {B,C} is a beat clone set (assuming that A, B, and C are the only 
candidates).  This kind of beat clone set is eliminated automatically in 
the first step of sprucing up since it would never do to pick B or C in 
the rock, paper, scissors game.  [The guy who picked A would always get a 
dollar from anybody who picked B or C.]

Since (in public elections) it is unlikely that any irreducible (incapable 
of further collapse) beat clone subset of a Dutta Set would have more than 
three members, after all of the proper beat clones are collapsed, the 
resulting cycle will consist of three members (unless there is a Condorcet 
Winner, in which case there will be no cycle at all: the Dutta Set will 
consist of only one candidate, the CW).

Therefore (in public elections), if the method being spruced up can handle 
a cycle of three, then the spruce up process takes care of the rest of the 
work (by presenting various cycles of three to the method as long as 
(collapsed) subcycles keep coming up winner).

So sprucing up allows us to concentrate on the three candidate cycle case. 
If we can get that case right, then sprucing up will take care of 
generalizing the method to more than three candidates in a clone free way 
which also satisfies the generalized Condorcet Criterion.

This is perhaps the main appeal of sprucing up ... a uniform way of 
extending methods from the three candidate case to the many candidate 
case, with the automatic incorporation of the Condorcet Criterion along 
with Clone Independence.

The current question is when does sprucing up preserve monotonicity?

It appears that some kind of randomness must be used to help pick among 
the members of the subcycles in order to preserve monotonicty.  In other 
words, if there is no Condorcet Winner, then some randomness of some kind 
must be used, or the spruced up version will not be monotonic.

It appears that Spruced Up Random Candidate is Monotonic (at least for 
public elections) since in that case it is the same as "Condorcet Lottery" 
which has been proven to be monotonic (if I remember correctly).

Go ahead and use these ideas.  However, because of the state of flux, some 
quotes from earlier postings will contain errors.  Therefore, if you quote 
me, either run it by me first, or do not attribute it to me. If you use 
your own wording, make it clear that it is your own understanding of an 
idea in flux.

My main interest now is in finding suitable probabilistic methods for 
eliminating all incentives for insincere rating of the candidates by 
sophisticated voters.

"Random Ballot" accomplishes that, so it is possible.  But random ballot 
gives positive probability  even to the candidate with 99 percent of last 
place votes, provided there is even one ballot on which he is ranked 
first.

This is generally unacceptable.

Spruced Up Random Candidate and Spruced Up Random Ballot are generally 
considered improvements on plain Random Ballot (since they are clone free 
Condorcet methods) but (unlike Random Ballot) they do suffer from some
incentives for insincerity on the ballots.

It appears that no Condorcet method can eliminate the incentive for 
insincere ballots, so I either have to abandom spruced up methods 
(which are all Condocet methods) or else add a pre-processing step up 
front, before restricting to the Dutta Set.

This preprocessing step might be something like converting over to some 
set or other of "lotteries" (which are probability distributions of the 
candidates) and then sprucing up the "election of lotteries," and then 
finally letting the winning lottery pick the candidate.

Obviously this process could be iterated.  The election of lotteries could 
be converted into an election of lotteries of lotteries, etc.

These artificial elections may have more complicated irreducible beat 
clone sets than the simple cycles of three that we are used to, thus 
defeating one of the main advantages of sprucing up: that we only have to 
know how to handle cycles of three.

Don't think about it too much if you are susceptible to headaches.

Forest


On Tue, 15 Feb 2005, Dan Keshet wrote:

> Hi Forest,
>
> As you may have heard, I have helped start the Electorama wiki at
> http://wiki.electorama.com  I have imported a lot of text from Wikipedia, and
> have been in the process of cleaning it to get rid of cruft.  It still has a
> long way to go, but I hope and anticipate that it will eventually become the
> canonical reference, so that neophytes like me don't have to go searching
> through EM archives that we don't understand.
>
> Toward that end, I have started a page on "sprucing
> up" ( http://wiki.electorama.com/wiki/Sprucing_up )  I have linked your
> original explanation, but I would like your permission to copy it onto the
> site and edit it.  To do so, you would need to release it under the GNU Free
> Documentation License ( http://www.gnu.org/copyleft/fdl.html ) or a more
> permissive license (such as the public domain).  Would you?
>
> I'd like to edit it, adding internal links so neophytes can understand it.
> For example, I don't, offhand, know what a "beat clone" is.
>
> Thank you for your time and consideration,
>
> Dan Keshet
>