[EM] Markov chain approaches

[Jobst Heitzig]

Here's some ideas for methods using the limit distribution of some
Markov chain to find the winner. The idea is to move through the set of
options, making "transitions" with certain probabilities which in some
way correspond to the preferences of the voters.

The reason why I post this is that some of the recent postings mention
equilibria in the context of strategic voting, and I have the feeling
that when the method itself uses some "dynamic process" to find the
winner, its strategic properties might be studied more easily and its
strategic equilibria might be found more easily. Has anybody thought in
that direction already?

Jobst


GENERALITIES

n = no. of options
pBA = probability of transition to B when currently at A
B>A <=> B defeats A <=> more voters prefer B to A than prefer A to B

The limit distribution of the Markov chain can easily be approximated
from the matrix M := (pAB|A,B) by taking the limit M^k*I for large k,
where I is the column vector (1/n,...,1/n).

The winner (winning set) is the option (set of options) whose limit
probability is maximal.

In the following, always assume that A and B are distinct options.

For every method fulfilling pBA>0 iff B>A, the support of the limit
distribution is exactly the Smith set (= top cycle).


1. TOURNAMENT APPROACH

Start with some option. When at A, choose B uniformly at random, go to B
if B>A, otherwise stay at A:

pBA := 1/(n-1) if B>A, 0 otherwise
pAA := 1 - sum{pBA|B}

This is the classic approach from the theory of tournaments where only
defeats but no strengths of defeats are considered. The method is
monotone, the winning set is always a subset of the iterated uncovered
set (that is, the uncovered set inside the uncovered set inside ... and
so on), and each winner beats at least half of the other options (see
e.g. Jean-Francois Laslier: Tournament Solutions and Majority Voting,
Springer 1997).

This method also equals the method M4 in the paper Cynthia Dwork / Ravi
Kumar / Moni Naor / D. Sivakumar: Rank Aggregation Methods for the Web,
http://www10.org/cdrom/papers/577/ as cited in Douglas Greene's post
"[EM] Forward from Warren Smith" from 23 Feb 2002.


2. PREFERENCE PROPORTIONAL APPROACH

Start with some option. When at A, choose some B and some voter
uniformly at random and let her decide whether to go to B. In other
words, go to B with a probability equal to the fraction of voters
preferring B to A, divided by n-1:

f(B>A) := no. of voters preferring B to A / no. of all voters

pBA := f(B>A)/(n-1)
pAA := 1 - sum{pBA|B}

Because pBA>0 for almost all pairs A,B, all options will have a positive
probability in this chain's limit distribution in most situations. It
would be interesting to know whether the winning set is always in the
Smith set anyway... and oh, of course whether this method is also
monotone...


3. MAGNITUDE OF DEFEATS PROPORTIONAL APPROACH

Start with some option. When at A, choose some B with B>A with a
probability proportional to the magnitude of B>A:

mag(B>A) := no. of voters preferring B to A if B>A, 0 otherwise.

pBA := mag(B>A) / (1 + sum{mag(C>A)|C})
pAA :=        1 / (1 + sum{mag(C>A)|C})


4. GLOBAL ORDER OF DEFEATS EXPONENTIAL APPROACH

Start with some option. At every step, process all (!) defeats by
decreasing magnitude. For each defeat, throw a coin and stop when the
first "face" occurs. When the current option is A and the defeat we
stopped at is B>A for some B, then go to B, otherwise stay at A. When no
"face" occurs at all, also stay at A. In other words, go to some B with
B>A with a probability whose logarithm is proportional to the rank of
the defeat B>A among all defeats:

pBA := 2^(-rank(B>A)) if B>A, 0 otherwise
pAA := 1 - sum{pBA|B}

This has two advantages over 3.: First of all, the transition
probabilities show more "contrast". Secondly, they depend only on the
order of the defeats, not on the actual magnitude. Hence this version is
somewhat closer to sequential affirming or dropping methods like
Beatpath, Tideman, or River.

I computed the winners of this version for the 104 examples with 4
options I posted some days ago, and from the results I conjecture that
this method always chooses an immune option. Could someone prove that,
please :-)


5. LOCAL ORDER OF DEFEATS EXPONENTIAL APPROACH

Start with some option. When at A, process all defeats B>A by decreasing
magnitude. For each defeat, throw a coin and stop when the first "face"
occurs. Follow this defeat. When no "face" occurs at all, stay at A. In
other words, go to some B with B>A with a probability whose logarithm is
proportional to the rank of the defeat B>A among the defeats against A:

pBA := (1/2)^(1 + no. of C with C>A and mag(C>A)>mag(B>A)) if B>A,
       0 otherwise
pAA := 1 - sum{pBA|B}