[EM] There is always a Condorcet Winner! (among all lotteries of candidates :

[James Green-Armytage]

Dear Jobst,

	Yes, it does sound like an intriguing idea, although non-deterministic
methods have never been an area of expertise for me. 
	In its present state, the proposal is still a little bit too abstract for
me to grasp; as usual, it's easier for me to understand a tally method
once I am given an example of it in practice. So, could you please find
the Condorcet lottery for the following group of preferences, and show me
how you did it?

35: A>B>C>D
25: B>C>A>D
30: C>A>B>D
10: D>C>A>B

thanks!
James Green-Armytage
http://fc.antioch.edu/~jarmyta@antioch-college.edu/voting.htm
http://fc.antioch.edu/~james_green-armytage/voting.htm


>Dear folks!

>Reading again Laslier's book, I stumbled upon a method which proves to be
>very promising after close inspection. 
>It is based on the simple fact that when comparing lotteries of
>candidates instead of the candidates alone,
>there is always a "Condorcet Winner" among the lotteries!
>Accordingly, I will call the method "Condorcet Lottery" here:
>
>
>Def. CONDORCET LOTTERY
>----------------------
>A lottery p assigns to each candidate x a winning probability p(x) so
>that all these probabilities add up to 1.
>A lottery p is said to beat another lottery q if the probability that x
>beats y is at least 1/2 when x is drawn from p and y is drawn from q.
>Find a lottery which beats all other lotteries.
>Draw the winner from this "Condorcet" lottery.
>
>
>Notes:
>
>1.  There is always exactly one such Condorcet lottery p. 
>
>2.  The set W of all candidates x with positive winning probability p(x)
>has an odd number of members
>    and is usually much smaller than the set of all candidates (see also
>7.).
>
>3.  The probabilities are proportional to odd numbers, i.e. p(x)=n(x)/d
>with odd n(x) and d.
>    
>4.  W consists of exactly one candidate if and only if that one is a
>Condorcet Winner. 
>    Otherwise, all p(x) are at most 1/3.
>
>5.  W consists of exactly three candidates if and only if they build a
>majority cycle and each other candidate is beaten by a least two of them. 
>    In that case, each of the three gets probability 1/3.
>
>6.  If W consists of five candidates, their defeats are
>    (a) either of the form a>b>c>d>e>a>c>e>b>d>a (a regular pentagon) 
>    (b) or of the form a>b>c1/2/3>a,c1>c2>c3>c1 (a 3-cycle substituted as
>a clone-set into a 3-cycle).
>    In that case the probabilities are
>    (a) p(a)=p(b)=p(c)=p(d)=p(e)=1/5 (this is clear by neutrality) or
>    (b) p(a)=p(b)=1/3=3/9 and p(c1)=p(c2)=p(c3)=1/9.
>
>7.  W is a subset of Dutta's minimal covering set, which is a subset of
>the [iterated] uncovered set, which in turn is a subset of the Smith set.
>    In particular, 
>    (a) Each candidate outside W is beaten by at least one member of W.
>    (b) The winner is uncovered, i.e. has a beatpath of length at most 2
>to all other candidates.
>    (c) Pareto-dominated and strongly dominated candidates cannot win.
>
>8.  The method is clone consistent in the strong sense that when
>replacing a candidate x by a clone set C, 
>    (a) the probability of candidates outside C remains the same,
>    (b) the total probability of C equals that of x,
>    (c) the probability of a clone c in C is that of x times that of c
>when choosing from C only.
>
>9.  The method is extremely robust with respect to manipulation. The
>following manipulations don't change anything: 
>    (a) removing candidates from outside W (=strong superset property),
>    (b) changing individual preferences between elements outside W
>(=independence from the losers),
>    (c) reinforcing some x in W with respect to some y outside W.
>
>10. In particular, ISDA and IPDA are fulfilled (this follows from 7. and
>9.).
>
>11. W is monotonic, that is, reinforcing a member of W cannot turn it
>into a loser. 
>
>12. The probability ratios p(x)/p(y) are monotonic in the sense that 
>    reinforcing x with respect to y does not decrease p(x)/p(y).
>
>13. When there are at most five candidates, also p(x) is monotonic, that
>is, reinforcing x cannot decrease p(x).
>
>14. The winner can be expected to defeat at least half of the other
>candidates. 
>    More precisely, the expected Copeland score of the winner is at least
>(n-1)/2 under p, where n is the number of candidates.
>
>15. The method satisfies a form of "immunity from second place
>complaints":
>	When removing the winner, the new winner can be expected to be beaten by
>the original winner. 
>	More precisely: When removing a possible winner x and applying the
>method again, 
>    it is more probable that x beats the new winner than vice versa.
>
>16. The method discourages strategies by majorities in the following
>sense:
>    Whenever a majority M of the voters think about voting strategically
>in some way, 
>    they will find that with a probability of at least 1/2 some member of
>M 
>    would prefer the outcome of the sincere votes to the outcome of the
>strategic votes
>    (and will thus wish to not have voted strategically).
>    Although this criterion may seem very weak to most of you, it seems
>absolutely desirable to me.
>    I encourage all of you to search for any other method which fulfils
>it :-)
>
>17. The method could also be used to elect a small committee: 
>    W is the committee and p(x) is the weight of x's vote in committee
>decisions. 
>    These decisions would then be made using again some method which is
>based on pairwise comparisons of all options.
>    And because of 2. and 3., there will always exist simple majorities
>in all these pairwise comparisons when no commitee member is allowed to
>abstain,
>    hence the committee decisions will not need a tiebreaker.
>
>Most of this follows easily from Laslier: "Tournament Solutions and
>Majority Voting" 
>who cites 4 original articles by David Fisher and Jennifer Ryan which
>have been published in
>    Amer. Math. Monthly, Vol.99 (1992), pp.935-942
>    J. Graph Theory, Vol.19 (1995), pp.217-236
>    Linear Algebra and its Applications, Vol.217 (1995), pp.87-100
>    Discr. Appl. Math., Vol.56 (1995), pp.87-91
>
>
>Of course, there are also some weaknesses of Condorcet Lottery: 
>- It can be difficult to find p.
>- Although the method is monotonic in the sense of 11. and 12., 
>  the probability p(x) can still decrease when x is reinforced and there
>are more than 5 candidates.
>- The method uses only the defeats, not their strengths.
>  Although it would be easily possible to do so by changing the payoff
>function of the game, 
>  that would destroy most of the nice properties, in particular, 1.-3,
>5.-7., 10., 13.-17. would probably no longer hold...
>
>
>So, what do you think? Should we inspect this further?
>
>Yours, Jobst
>
>
>
>PS: Some mathematics
>By definition, p is the unique Nash equilibrium in mixed strategies of
>the "tournament game". 
>Its support W is also called the "bipartisan set" by Laslier.
>The tournament game is the symmetric zero-sum two-player game with the
>candidates as the pure strategies and payoff 1 for the defeating
>candidate)
>p can thus be found by using the Lemke-Howson or the
>Porter-Nudelman-Shoham algorithm, for example.
>Although this means that it may in bad cases be complicated to find p, 
>it is always easy to prove that the result is correct once it is found by
>just showing that it beats each of the n pure strategies.
>This can be done in O(n^2) time just as in case of Ranked Pairs or River.
>(By the way, is it possible to prove a Beatpath winner in O(n^2) time
>also?)
> 
>________________________________________________________________
>Verschicken Sie romantische, coole und witzige Bilder per SMS!
>Jetzt neu bei WEB.DE FreeMail: http://freemail.web.de/?mc=021193
>
>----
>Election-methods mailing list - see http://electorama.com/em for list info