Hi folks!
Here's another simple method which is designed to fulfill uncoveredness, clone-proofness, and a certain degree of monotonicity. I tried to keep it as simple as possible in the following sense: Its application only requires us to draw some ballots and check some pairwise defeats, but it does not involve any computations or complicated notions such as cycles or beatpaths or covering or lotteries or whatever. The idea is to first define a sequence of "nominees" by drawing ballots, then finding a sequence of "intermediate winners" by constructing maximal orderings from these nominees, such that each intermediate winner beats its predecessor, and finally stopping as soon as some nominee occurs a second time. I call it the RaMON method in honour of Ramon Llull who proposed to elect the "Condorcet" winner 500 years before the Marquis de Condorcet. Also the idea to use pairwise comparisons between a sequence of nominees goes back to Llull. The method comes in four variants, depending on how much information on individual preference strength the ballots contain: RaMON-T, RaMON-A, RaMON-C, and RaMON-R, which are defined like this: Def.: Randomized Maximal Ordering by Nomination (RaMON) --------------------------------------------------------- 1. Determine all pairwise defeats. 2. Find a sequence of "nominees" N1,N2,... like this: Each nominee is determined in the same way: For RaMON-T: Draw a random ballot and take its top element. This is the nominee. (If there is a tie at the top, use further ballots to reduce to one candidate) Or, for RaMON-A (requires approval cutoffs): Draw a random ballot and give each approved candidate a point. Repeat until one candidate has more points than all others. This is the nominee. Or, for RaMON-C (requires approval cutoffs): Draw a random ballot and give each disapproved candidate a point unless that would leave no candidates with zero points. Repeat until all but one candidate have points. That one is the nominee. Or, for RaMON-R (requires cardinal ratings, say 0..100): Draw a random ballot and give each approved candidate its rating as points. Repeat until one candidate has a lead of 100 points or more. This is the nominee. 3. Find a first "intermediate winner" W1 like this: Starting with an empty set of candidates, look at the nominees N1,N2,... (in this order) and add each nominee to the set when (s)he defeats all those already in the set. As soon as no further candidate defeats the whole set, the last one who was added to the set is the first intermediate winner W1. 4. Extend this to a sequence of intermediate winners W1,W2,... like this: W(i+1) is found exactly like W1, that is, by looking at N1,N2,..., but with the difference that we start not with an empty set but with a set containing only Wi. 5. As soon as some intermediate winner Wj equals an earlier intermediate winner Wi, the one before the second occurrence, that is, W(j-1), is declared the final winner. Note: In praxis, the sequence of nominees need only be determined as far as it is needed by 3. and 4., that is, after the first nominee, the successive nominees are determined only "on demand". An example of RaMON-T: ---------------------- Ballots: 2x A>B>C>D 2x B>C>D>A 2x D>A>B>C 1x C>A>B>D 1. Defeats: A>B>C>D>A>C,B>D. 2. Nominees = tops of randomly drawn ballots, for example: C,B,D,D,A,B,C,B,A,D,A,C,B,D,C,A,A,D,B,D,B,B,C,A,... 3. To find the first intermediate winner, we start with an empty set, add C, add B, skip D since D<B, add A since A>B, then stop since no candidate beats C,B, and A. Hence the first intermediate winner is W1=A. 4. To find the second intermediate winner, we start over with A, consider again C, now skip C and B since C<A and B<A, but add D since D>A, and stop again since no candidate beats both A and D. Hence W2=D. Similarly, we get a third set consisting of D and B, hence W3=B. Then, the fourth set consists of B and A, hence W4=A. But this has occurred before (W4=A=W1), hence the winner is W3=B. It is no coincidence that the winner equals the first nominee that is in the Banks set: This is always the case when the Banks set consists of three candidates (in this case A,B,D). From this fact we can already see a certain degree of monotonicity: When there are at most four candidates, the possible winners are the Banks candidates, and the winning probability of a Banks candidate is the proportion of direct support for her or a beat clone of her. More precisely, when the defeats are A>B>C>D>A>C,B>D as above, and the direct support is nA,nB,nC,nD, then the Banks elements are A,B,D, and C is a beat clone of B, hence A wins with probability nA/n, B wins with probability (nB+nC)/n, and D wins with probability nD/n. In the above example, A,B,D win with probability 2/7, 3/7, and 2/7, respectively. Further properties of RaMON: ---------------------------- The method is clone-proof in a semi-strong sense: Cloning does not change the winning probabilities of the other candidates, and the clone set has the same winning probability as the cloned candidate had, but the winning probabilities inside the clone set might be distributed differently than when only the clone set would be considered. But note that this clone-proofness relies on the fact that in 3. and 4. always the same sequence of nominees is used, always starting with N1! Although I have no hope that the method will fulfil monotonicity in general, I expect it to be monotonic in most public election situations, especially when the Banks set is small. This is the most interesting question about RaMON at the moment I guess! Note that by construction each set constructed in 3. or 4. is a maximal subchain of the graph of all defeats, hence each intermediate winner (and thus also the final winner) is a Banks element (and thus, in particular, uncovered and in the Smith set). More precisely, this is at least the fact when all candidates in the Smith set have a chance of being nominates. However, I could not yet establish whether all Banks elements get a positive winning probability as it was the case with ROACC. If not, the question will arise whether in situations without a CW still all candidates are defeated by at least one possible winner. Jobst ---- Election-methods mailing list - see http://electorama.com/em for list info
