[EM] Simple Smith method

[Kristofer Munsterhjelm]

Here's a simple Smith-efficient method that I thought of while reading
statistics:

The method has a score list and a current candidate.

1. Initially, let the current candidate be an arbitrary candidate and
let every candidate have a score of zero, then do the following:

2. Increment the current candidate (call him X)'s score by one point.
3. Pick a random candidate Y.
4. If Y beats X, then switch the current candidate to Y with probability
(Y>X)/(number of voters).
5. Otherwise, let the current candidate stay as it is.
6. Go to 2.

The winner is the candidate that is most often the current candidate,
i.e. has the greatest score after you've done this lots of times.

It's clearly Condorcet because if the current candidate ever becomes the
CW, there's no way it can become anything else. (The CW is an absorbing
state.) It's also Smith by similar reasoning: if the process ever falls
into the Smith set, it can't get out again because no non-Smith-set
member beats a Smith-set member. Since the selection in step 3 is
random, it'll eventually stumble across a Smith set member (or CW, if
there is one), and then it can't get out.

It should be monotone: suppose A>B>C is turned into B>A>C. All this does
is increase B's victory against A, so if the current candidate is A, it
increases the probability that it'll switch to B; and if the current
candidate *isn't* A, it has no effect.

I don't think it is cloneproof, though. E.g. if you split A into A1 and
A2, then the probability of going from B to one of the As, assuming the
voters that were A>B are now a mix of A1>A2>B and A2>A1>B, goes from

1/n * (A>B)/numvoters

(i.e. pick A out of the n candidates and then pass the roll in 4.)

to

2/(n+1) * (A>B)/numvoters

(i.e. pick either A1 or A2 out of the n+1 and then pass the same roll)

and since 2/(n+1) > 1/n for n>1, there seems to be a teaming incentive.
Oh well. But perhaps it does well on regret tests since other linear
algebra methods (Keener and Sinkhorn) seem to do so.

Perhaps it would be possible to make cloneproof in this way:

1. As above.
2. As above.
3. Pick a random ballot and find the first candidate that both pairwise
beats X and is ranked above X on that ballot. Call that candidate Y.
4. If there is such a candidate Y, switch to him.
5. Otherwise stay in X.
(Rest as above)

the point being that if you clone, the chance of switching to either A1
or A2 combined is the same as switching to A before the cloning. But I'm
not sure about the monotonicity, and the increased time spent in A1 and
A2 from switching from A1 to A2 and vice versa may still make it fail
clone independence.

-

Mathematically, the first method is: let X be a Markov chain where the
states are the candidates and the transition probabilities p_ij are given by
	p_ij = 1/numcands * d[j, i]/numvoters  if i != j
	       1 - (sum over all j != i: p_ij) if i == j
where d[x, y] is the WV matrix entry for X>Y, i.e. X>Y if X beats Y, 0
otherwise.

Then find the stationary distribution for X and elect the candidate with
the greatest stationary probability.