This looks like another way of doing Spruced Up Random Candidate.
In particular, properties 7 and 8 below correspond to the first two steps of the "Spruce Up" process. Because of this, Spruced Up Lottery has to be equivalent to Lottery. And then properties 5 and 6 finish the characterization of Spruced Up Random Candidate.
At minimum, they are equivalent for public elections.
I have always considered Spruced Up Random Ballot to be superior to Spruced Up Random Candidate. This question could be answered by comparing Lottery (equivalent to Spruced Up Random Ballot) with Random Ballot Dutta (equivalent to Spruced Up Random Ballot).
How well does Random Ballot Dutta compare with Lottery? I would think that it would satisfy all of the properties below but with slightly greater Social Utility.
By the way ... is there any difference between Banks, Dutta, and "iterated uncovered set" in the context of public elections?
Any spruced up non-deterministic method satisfies at least properties 2, 4, 7, and 8. (also property 6, concerning the size of W, but not necessarily the numerical values of the probabilities)
If the Porter-Nudelman-Shoham algorithm is not always efficient, then (equivalent) Spruced Up Random Candidate should be used, since the sprucing up process can be done efficiently.
Ted Stern gets the credit for finding an efficient sprucing up procedure by finding an existing clone collapsing algorithm in the literature.
I like this as well as any other ordinal ballot method that I have ever seen.
However, even though it is non-deterministic, and highly manipulation resistant, it is not totally manipulation free:
(following Bart's critique on non-determinism...)
Suppose that there are three factions with sincere preferences
x A>C>B y B>C>A z C>B>A ,
and that there is no statistically discernible difference in the values of x, y, and z.
Suppose further that for all members of the first faction the utility u of the sincere Condorcet Winner C is below mean, i.e. less than halfway from B to A: 0 < u < 50% < 100% .
Then this faction would be better off voting A>B>C which would give their favorite A a one third chance of winning, as long as the method (deterministic or not) satisfied neutrality, since statistically A would then have the same chance of winning as B or C.
Specifically their expected utility rises from u to (100%+u)/3, which is an improvement as long as u < 50%.
Of course, the C faction can easily guard against this ploy by truncating A. But the point is that they do have to employ some strategy or sustain significant risk of losing their rightful victory.
This shows that all neutral Condorcet methods (including Lottery) require strategical vigilence.
This result taken together with the Gibbard Satterwaithe (sp?) theorem shows that the only non-manipulable methods based on ordinal ballots are like Random Ballot, in that they are nondeterministic and they fail the Condorcet Criterion.
Which of the desireable criteria below is failed by Random Ballot Dutta?
I suspect that Random Ballot Dutta was not suggested because in tournament applications there may not be any ballots to fall back on, and Lottery requires only the pairwise win matrix, which may be all that is available in some applications.
I think Random Ballot Dutta would be easier to sell than Lottery in virtue of its relative simplicity. In particular the artifice of a tournament of lotteries brings in abstract baggage that would put off most citizens, no matter how elegant it might seem to the rest of us.
However, if Lottery is truly superior to Random Ballot Dutta, then I think we should offer it in the Spruced Up Random Candidate form, since that form doesn't require the introduction of a tournament of lotteries, but gives identical results in public elections.
Here is Lottery in the form of Spruced Up Random Ballot:
1. Cross out strategically dominated candidates (so that only Dutta candidates remain). This ensures the satisfaction of the Generalized Condorcet Criterion. [If we were doing Random Ballot Dutta, our final step would be to elect the highest reamining candidate on a randomly drawn ballot.]
2. Collapse all remaining proper beat clone sets. This makes the method beat clone free, which implies clone free. [Ted Stern has found an efficient way of doing this clone collapsing step.]
3. If the result is a single candidate, we're done. Otherwise it is a (collapsed) cyclical clone set. Pick a member of this cycle at random. If that member is a single candidate, we're done. Otherwise, it is a (collapsed) cyclical clone set. Continue in this manner until a candidate is chosen.
Good work, Jobst. It looks like somebody else has done most of the criteria compliance work for us on Spruced Up Random Candidate, which is where I went when trying to de-clone your ROACC method. In fact, Lottery, Spruced Up Random Candidate, Spruced Up Copeland, and Spruced Up ROACC are all equivalent, at least in public elections, if not always.
Forest
Date: Wed, 05 Jan 2005 18:16:42 +0100 From: "Jobst Heitzig" <[EMAIL PROTECTED]> Subject: [EM] There is always a Condorcet Winner! (among all lotteries of candidates :-) To: election-methods-electorama.com@electorama.com Message-ID: <[EMAIL PROTECTED]> Content-Type: text/plain; charset="iso-8859-1"
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 [EMAIL PROTECTED] http://lists.electorama.com/listinfo.cgi/election-methods-electorama.com
End of Election-methods Digest, Vol 7, Issue 9 **********************************************
---- Election-methods mailing list - see http://electorama.com/em for list info
