[EM] Markus' request

[Forest Simmons]

Markus asked me to define the Dutta Set, the Condorcet Lottery method, and 
clarify whether or not this lottery method is monotonic.

I think the best I can do is to include a copy of Jobst's posting of 5 Jan 
2005, which answers all of these questions to one degree or another.

In particular, the monotonic nature of the method is described in 
properties 11 and 12 below.

From: "Jobst Heitzig" <heitzig-j at web.de>
Subject: [EM] There is always a Condorcet Winner! (among all lotteries
 	of	candidates :-)

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?)