[EM] strategy-free Condorcet method after all!

[Juho]

One can thwart strategic voting in general by hiding the algorithm  
that makes the decision who wins. Instead of collecting perfect poll  
information (that voters are supposed to use accurately when they  
decide how to vote) one could upgrade the poll answers to actual  
ranked votes. The randomness / uncertainty could be introduced by  
determining the rules (in the case of a top level cycle) only after  
the votes have been collected (e.g. in using the randomization  
mechanism of the reverse Llull method).

If the method is Condorcet compliant voters may try to create a top  
level cycle if they don't like the expected Condorcet winner (that  
they guess based on some earlier polls etc.). Artificial cycles  
however typically include also candidates that are worse than the  
current winner and the candidate that one tries to promote. If one can  
not guess which one of the cycle members (or other candidates if that  
is allowed) will win then the benefits of strategic voting may easily  
be close to zero.

Polls are usually more sincere than actual votes. But actual votes may  
be one step more sincere if voting is heavily based on the polls but  
one's actual vote is independent of what one said in the polls.

The basic procedure was thus to collect ranked votes first and only  
after that decide the randomish procedure / algorithm input that is  
then used to decide which one of the "almost tied leading candidates"  
wins.

Juho



On Nov 14, 2009, at 2:32 PM, Jobst Heitzig wrote:

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