[EM] strategy-free Condorcet method after all!

[Jobst Heitzig]

Dear folks,

it seems there is a stragegy-free Condorcet method after all -- say
good-bye to burying, strategic truncation and their relatives!

More precisely, I believe that at least in case of complete information
(all voters knowing some details about the true preferences of all other
voters) and when all voters will follow dominating strategies, then the
following astonishingly simple method will always make unanimous sincere
voting the unique dominating strategy, and it will always elect a true
beats-all winner (=Condorcet winner):


Method: Reverse Llull
=====================

1. Sort the options into some arbitrary ordering X1,...,Xn (e.g.
alphabetically or randomly), publish this ordering, and put i=n.

2. If already i=1, then X1 is the winner. Otherwise, ask all voters
whether they prefer Xi or the option they expect to be the winner of
applying this method to the remaining options X1,...,X(i-1).

3. If more voters prefer Xi, Xi is the winner. Otherwise, decrease i by
1 and repeat steps 2 and 3.


Why should this be strategy-free?

If n=2, the question in step 2 is whether X1 or X2 is preferred and the
method is traditional majority choice in which sincere voting is known
to be the dominant strategy in case of 2 options.

For n>2, we prove strategy-freeness inductively, assuming it has been
proved for n-1 options already: Since we assume that each voter follows
dominant strategies and knows enough about the other voter's
preferences, and since each voters knows that sincere voting is the
unique dominant strategy for all cases of at most n-1 options, she will
know in step 2 which option Xj would win if the method was applied to
X1,...,X(i-1), and she will also know that her vote at this step does
not influence which option Xj is but only whether Xi or Xj will win.
That is, in step 2 all voters face a simple majority choice between two
known options Xi and Xj, so again voting sincerely in this step is the
unique dominant strategy. By induction, the whole method is strategy-free.


The method is in some sense the reverse of Llull's famous earliest known
"Condorcet' method from the 13th century (cited recently on this list):
In the classical Llull method, voters would first make a majority
decision between X1 and X2, then a majority choice between the winner of
the first choice and X3, and so on working thru the whole list of
options, always keeping the last winner and comparing it with the next
option in the list. The overall winner is the winner of the last comparison.

So, the only difference between classical Llull and Reverse Llull is the
order in which these pairwise comparisons are done. If we assume all
voters vote sincerely in classical Llull, both method would be
equivalent. But with strategic voters, the difference is important: In
classical Llull, a voter's voting behaviour in one step can influence
the results of the later steps (because it can influence which candidate
"stays in the ring"), whereas in Reverse Llull it cannot.


In practice, the method can be sped-up by using approval-style ballots
on which each voter marks after step 1 every option Xi which she prefers
to the expected winner of the subset X1,...,X(i-1).

As for additional properties, Reverse Llull is Pareto-efficient,
Smith-efficient (i.e. elects a member of the Smith set), and monotonic,
but not clone-proof.

I wonder if we can also find a clone-proof version of this... Any ideas?


Yours, Jobst