[EM] Re: lotteries
Forest Simmons
simmonfo at up.edu
Wed Jan 5 15:15:21 PST 2005
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" <heitzig-j at web.de>
> Subject: [EM] There is always a Condorcet Winner! (among all lotteries
> of candidates :-)
> To: election-methods-electorama.com at electorama.com
> Message-ID: <818420780 at web.de>
> 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
> Election-methods at electorama.com
> http://lists.electorama.com/listinfo.cgi/election-methods-electorama.com
>
>
> End of Election-methods Digest, Vol 7, Issue 9
> **********************************************
>
More information about the Election-Methods
mailing list