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/[EMAIL PROTECTED]/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 ---- Election-methods mailing list - see http://electorama.com/em for list info