[EM] non-deterministic methods for better strategy proofness

[Jobst Heitzig]

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