[EM] A Markov Steady State Distribution Lottery and Related Deterministic Method

Simmons, Forest simmonfo at up.edu
Wed Jan 10 10:24:04 PST 2007


Form a matrix M whose entry in row  i  and column  j  is the percentage of ballots on which alternative  j  is the highest ranked alternative that is not majority defeated by alternative  i.
 
[By definition no alternative is majority defeated by itself, so if every alternative ranked higher than alternative i is majority defeated by i, then alternative i itself is the highest ranked alternative that is not majority defeated by i.]
 
Each column of M sums to 100 percent, so M is a stochastic matrix.  In fact, M is the transition matrix for the following Markov process:
 
Given an alternative A(k), let A(k+1) be the highest ranked alternative that isn't majority defeated by A(k) on a randomly chosen (and replaced) ballot.
 
To each initial probability distribution vector V  there corresponds a steady state distribution vector  V' = MV which can be approximated by pre-multiplying V by a high power of M.  In the limit of infinitely many iterations (of  V replaced by M times previous V)  we get  V' . 
 
For our proposed lottery method we take the initial state vector  V to consist of the random ballot probabilities for the respective alternatives.
 
Then the lottery determined by the 100th power of  M times V is equivalent to choosing A(0) in the (above mentioned Markov process) by random ballot, and letting A(100) be the winner.
 
If I am not mistaken, increasing the rank of alternative  i  relative to the other alternatives cannot decrease the steady state probability of  alternative i.  
 
Also, if alternative i  is replaced by a clone set {x,y,z}, then the steady state probabilities of the other alternatives are not affected.  And, furthermore, the steady state probabilities of x, y, and z will be in the same relative proportion as they would be if all of the other alternatives were deleted from the ballots.
 
Now let's leave the realm of non-determinism for awhile and consider an idea for a related deterministic method:
 
Let v1, v2, v3, etc. be the initial state vectors consist of all zeros except for a one in the respective positions 1, 2, 3, etc.
 
Let  v1', v2', v3', etc. be the corresponding steady state vectors.
 
The alternative i that loses the least probability in going from vi to vi' is the winner.
 
I don't have time to post any examples right now, but I will later.
 
Forest
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/ms-tnef
Size: 5784 bytes
Desc: not available
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20070110/58872b1b/attachment-0002.bin>


More information about the Election-Methods mailing list