[EM] RaMON, a method in honour of Ramon Llull

[Jobst Heitzig]

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