[EM] non-deterministic methods for better strategy proofness

[Dave Ketchum]

I get dizzy on his one but, if a majority of voters prefer B, why do they 
not simply vote B, and quit talking about strategy?

Dave Ketchum

On Sun, 13 Jun 2004 15:38:36 +0200 Jobst Heitzig wrote:

> Markus mentioned Pattanaiks work on strategy-proofness, and I read the
> book in the meantime. This and the fact that the Random Dictator Method
> is completely strategy-proof got me thinking about introducing a certain
> randomness into Condorcet methods. This is what I came up with. The
> essential point is that can avoid the most serious strategical threats
> when we only choose deterministically when there is a Condorcet winner,
> but choose randomly from a small set of good options when there is no
> Condorcet winner. I suggest at least three methods of this kind which
> however are only to be considered a starting point for a discussion.
> 
> 
> I. Proofness against strategies to elect some option with *certainty*
> ----------------------------------------------------------------------
> 
> Assume that we have a method which fulfils the Condorcet Criterion, that
> is, elects the Condorcet winner whenever the *expressed* preferences
> show one, or that, more generally, we have a method under which each
> absolute majority (= group of more than half of the voters) can make any
> option of their choice the certain winner by voting strategically.
> 	With such a method, the risk of strategic distortion mostly comes from
> absolute majorities forcing some winner of their choice. But there is
> not such a large risk that some *minority* coalition might try to
> manipulate the result because they will always face a counter-threat by
> the remaining absolute majority who could react by forcing an option
> unwanted by the minority. Hence I will focus on the risk of an absolute
> majority having incentive to vote strategically.
> 	
> Assume further a sincere situation where for each option A there is
> another option B which is preferred to A by an absolute majority. Let us
> call this a "risky situation". (This is for example the case when the
> number of voters is odd, all individual preference relations are linear
> orderings (that is, "complete" and without "ties"), and there is no
> sincere Condorcet winner.)
> 	Now when the method elects any option A with certainty in this
> situation, there will always be an absolute majority preferring B over
> A, and this majority can make B the certain winner by voting
> differently. In other words, when the method chooses almost always
> deterministically, such sincere situations almost never have an
> equilibrium and will lead to strategic behaviour with unpredictable
> outcomes.
> 
> However, when the method does not choose deterministically in such a
> situation but *probabilistically*, that is, with a certain amount of
> randomness, it can remove most incentives to force any deterministic
> outcome by voting strategically:
> 	In each "risky situation", let the method compute some (small) set S of
> options such that for every option B there is an option A in S which is
> preferred to B by an absolute majority. Then let the method choose an
> element of S at random, with all elements A in S having some positive
> probability P(A)>0.
> 	With such a method, it is far less probable that some absolute majority
> build a coalition to force the election of some option B with certainty
> by voting strategically. This is because whatever B the coalition agrees
> upon, some members of the coalition take the risk of getting a *worse*
> outcome than before since there is some option A which is preferred to B
> by an absolute majority (and hence by at least one member of any
> absolute majority) and which is elected with a positive probability in
> the current situation.
> 	Since such a method sometimes uses a non-deterministic probability
> distribution P, we have to consider also threats by absolute majority
> coalitions which produce a different *non-deterministic* distribution Q.
> But still for every option B with Q(B)>0 there is some option A which is
> preferred to B by some member of the coalition and which is elected with
> a positive probability in the current situation, hence still some
> members of the coalition must take the risk of getting a worse outcome.
> 
> I will describe some methods of the kind sketched here later.
> 
> 
> II. Proofness against *risky* strategies
> -----------------------------------------
> 
> What if an absolute majority coalition decides to vote strategically
> despite some risk to get a worse outcome? This could occurr when each
> member of the coalition finds that the new distribution Q achieved by
> voting strategically is in some sense better than the old distribution
> P. But what could "better" mean here?
> 	
> As a first version, we could assume that a voter prefers Q to P when the
> probability that A is preferred to B is at least as large as the
> probability that B is preferred to A, when A is drawn from P and B is
> drawn from Q. In symbols:
> 	sum { P(A)*Q(B) : A is preferred to B }	
> 	>= sum { P(A)*Q(B) : B is preferred to A }
> We could then search for methods which compute a distribution P such
> that no absolute majority can produce a distribution Q considered
> "better" by all its members. However, the following example shows that
> this is already to much asked for:
> 
> COUNTER-EXAMPLE. 9 voters, 4 options A,B,C,D. Sincere preferences:
> 	1 B>C>D>A
> 	1 C>D>B>A
> 	1 D>B>C>A
> 	2 B>A>C>D
> 	2 C>A>D>B
> 	2 D>A>B>C
> Note that A is a Condorcet loser and the cyclic permutation (BCD) is an
> isomorphism.
> Assume that P(A)=a, P(B)=b, P(C)=c, and P(D)=d.
> Incentives to vote strategically:
> (i) If b+c>d, c+d>b, and d+b>c, then under the above understanding of
> "better distribution", the last six voters have an incentive to elect A
> by voting A>BCD.
> (ii) If a>c+d or c>a+d, five voters have an incentive to elect B by
> voting B>ACD.
> (iii) Analogously, if a>d+b, d>a+b, a>b+c, or b>a+c, five voters would
> want to elect C or D, resp.
> 	Now when the method is required to be neutral in the sense that because
> of the isomorphism (BCD) it must put b=c=d, it must put b=c=d=0 in order
> to avoid the incentive (i). But then it has a=1 so that incentives of
> type (ii) and (iii) occurr.
> 	To avoid this problem and still ensure neutrality, one could choose a
> random ordering of all options *before* the votes are cast, and then use
> this ordering to define the distribution P without the necessity of
> b=c=d. For example, when B comes before C and D in the random ordering,
> the method could put a=c=d=1/5 and b=2/5 and thus leave no incentives!
> 	However, this requires giving the Condorcet loser A a positive
> probability, since whenever a=0 and not b=c=d, an incentive of type (ii)
> remains! At this point I personally think that one should rather allow
> some of these "risky" incentives to remain than to give a Condorcet
> loser a positive probability of being elected.
> 
> A different understanding of "better distribution" is somewhat more
> conservative: Let us assume that the voter only prefers Q to P when Q
> results from P by "raising" some weight from less to more preferred
> options. This can be elegantly formulated like this:
> 	Call a set S of options "up-closed" when for every option A in S and
> every option B weakly preferred to A, also B is in S. Now Q is at least
> as good as P if and only if Q(S)>=P(S) for every up-closed set S.
> 	It is easy to see that when Q is better than P in this sense, it is
> also better in the first sense discussed above, so we have here a more
> exclusive definition of "better distribution". Here's again an
> interesting example:
> 
> EXAMPLE. 9 voters, 6 options A...F. Sincere preferences:
> 	1 D>F>E>A>B>C
> 	1 E>D>F>B>C>A
> 	1 F>E>D>C>A>B
> 	2 A>D>B>F>C>E
> 	2 B>E>C>D>A>F
> 	2 C>F>A>E>B>D
> Note that the Smith set is {D,E,F} and the permutation (ABC)(DEF) (in
> cyclic notation) is an isomorphism.
> Assume that P(A)=a, ..., P(F)=f.
> With the strict interpretation of neutrality, we would have to make
> a=b=c and d=e=f. Trying a=b=c=0 in order to keep the outcome inside the
> Smith set, we face a threat by the last six voters who would prefer
> a=b=c=1/3 and d=e=f=0 and can produce it by switching to voting like this:
> 	2 A>B>C>D>F>E
> 	2 B>C>A>E>D>F
> 	2 C>A>B>F>E>D
> However, there is a counter-threat to this because the first three
> voters can then make A a condorcet winner and thus produce a=1 by voting
> A>BCDEF, which is considered worse than the orginal result by the last
> four voters.
> 	More generally, assume there is any voting situation where there is a
> *non-deterministic* threat by a coalition of less than three quarters of
> all voters. Then there is always some kind of weak counter-threat: The
> strategic ballots of the coalition *alone* either show a Condorcet
> winner or not. If they do, the rest of the voters can react by electing
> this option deterministically. If they do not, they will instead contain
> a cycle of defeats A>B>C>A with A>B supported by at most 2/3 of the
> coalition (equalling less than half of all voters!). In the latter
> situation, the rest of the voters can force a defeat A>B or B>A as they
> like and thus disturb the strategy of the coalition. This is exactly
> what happened in the above example.
> 
> 
> III. Some methods as a starting point for further discussion
> -------------------------------------------------------------
> 
> For simplicity, let us here only consider situations with an odd number
> of voters and with all sincere and expressed preferences being linear
> orderings (the classical simplifications of social choice theory).
> This allows us to utilize the findings of tournament theory, where all
> kinds of nice subsets of options are studied.
> 	I have argued above that we need to put positive probability on enough
> options to make sure every non-Condorcet winner is defeated by some
> option which has a positive probability of being elected. On the other
> hand, we want to keep the result as deterministic as possible and
> exclude "bad" option altogether, of course. So, as a starting point, let
> us use only options in the top-cycle (= Smith set = Schwartz set) since
> they suffice to defeat all other options.
> 
> 	
> 1. Distributions on the Top-Cycle
> 
> a) Uniform distribution.
> 	This is monotone since when A belongs to the top-cycle and is
> reinforced against some B, the top-cycle can only get smaller but still
> includes A.
> 	However, the uniform distribution is the least deterministic (= most
> random) distribution possible and it does not as naturally correspond to
> a "procedure" as the following two.
> 
> b) Markov distribution.
> 	See my previous posting on Markov chains. The classical Markov scores
> are also monotone and correspond in the limit to the following ideal
> procedure of "Random Order Winner Stays with Replacement (ROWSR)":
> Starting with a first intermediate winner picked uniformly at random,
> successively pick a new opion uniformly at random, compare it to the
> last intermediate winner and keep the one defeating the other as the new
> intermediate winner. Repeat for an infinite (or at least very long :-)
> time. The final intermediate winner is elected.
> 	Advantage: The most probable options defeat at least half of the other
> options.
> 
> c) Random Order Winner Stays (ROWS) distribution.
> 	This is still more simple than the previous one: Starting with a first
> intermediate winner picked uniformly at random, successively pick a new
> opion uniformly at random *from all options not yet picked*, compare it
> to the last intermediate winner and keep the one defeating the other as
> the new intermediate winner. When all options have been picked, the
> final intermediate winner is elected. Could also be named "Random Agenda
> distribution".
> 	This is also easily seen to be monotone.
> 
> Still, the top-cylce seems somewhat too large to do the job, and it is
> not component consistent (cloneproof). Also, a Pareto-dominated options
> can belong to the top-cycle but not to the Uncovered Set.
> 
> 
> 2. Distributions on subsets of the Uncovered Set
> 
> Laslier mentions a number of subsets of the Uncovered Set:
> 
> a) Uncovered Set.
> 	All options A with the property that for every B defeating A there is C
> with A>C>B.
> 	These options have the advantage that all majority complaints can be
> rebutted by *short* beatpaths. (Note that because the immune set is very
> often a singleton, we cannot hope to be able to rebut majority
> complaints by *strong* beatpaths, so short ones are the next best
> possibility in my opinion...).
> 	Since the covering relation is transitive, each option is defeated by
> an uncovered option. The uncovered set is component consistent.
> 	Unfortunately, I don't know how to define a distribution on the
> uncovered set in a monotone manner...
> 
> b) Banks Set.
> 	All options which are top in some maximal subchain of the graph of
> defeats.
> 	Each option A is defeated by a Banks option: choose B with B>A. If B is
> not Banks, there is C with C>A,B and so on, hence we end up with a Banks
> element Z with Z>A. The Banks set is also component consistent.
> 	A disadvantage is that a Banks element might only defeat 1/3 of all
> non-Banks elements.
> 	However, this is the smallest set for which I was able to find a
> monotone way to compute probabilities:
> 
> Random Order Acrobatic Chain Climbing (ROACC) distribution.
> -----------------------------------------------------------
> 	This is somewhat like ROWS: Starting with an empty chain, successively
> pick a new opion uniformly at random from all options not yet picked,
> and add it to the chain when it defeats *all* options already in the
> chain. When all options have been picked, the last option added is elected.
> 	At the moment, this is my favourite choice, but it does not take  into
> account the strength of the defeats. If someone comes up with a
> *monotone* way to compute Banks probabilities from *strengths* of
> defeats, please post it!!!
> 
> 
> c) Tournament Equilibrium Set (TEQ).
> 	Defined in a recursive manner: Put A>>B when A is in the TEQ of the set
> of all options defeating B. The TEQ is then the top-cycle of this
> relation >>.
> 	This is contained in the Banks set and might be too small for our
> purposes since I could not verify that every option is defeated by some
> TEQ option... But if it does, it could be a nice solution since there is
> also a natural probability distribution linked to the TEQ...
> 
> d) Bipartisan Distribution.
> 	The Bipartisan distribution is the unique distribution P such that for
> every other distribution Q, the following holds: The probability that A
> defeats B is smaller when A is chosen from Q and B from P than when both
> are chosen from P. The Bipartisan Set is the set of A with P(A)>0.
> 	This set is said to have lots of nice properties including component
> consistency, and each option A is defeated by some Bipartisan option
> (otherwise the distribution Q with Q(A)=1 would not fulfill the above
> condition!)
> 	Unfortunately, P is not monotone, but there are at least some monotone
> "scores" defined by means of P:
> 	s(A) := P(options defeating A) / P(options defeated by A)
> The problem with these scores is that some might be infinite...
> 
> 
> ----
> This is how far I got into this direction. I would like to ask you to
> think about these and better ways to specify probabilities!
> 
> Jobst

-- 
  davek at clarityconnect.com    people.clarityconnect.com/webpages3/davek
  Dave Ketchum   108 Halstead Ave, Owego, NY  13827-1708   607-687-5026
            Do to no one what you would not want done to you.
                  If you want peace, work for justice.