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
---- Election-methods mailing list - see http://electorama.com/em for list info
