Mfrhtyj

I just compared a couple of example elections, as given on Wikipedia to show how Condorcet-methods differ from non-Condorcet ones, to what happens if you just interpret the underlying preference graphs as Continuous Time Markov chains (CTMC). At least in each of the example cases, while the exact ordering almost never matched, in the limes $ttoinfty$, the CTMC always gave the Condorcet winner. So I wonder: How well do CTMC actually do compared to more usual or sophisticated election methods? What criteria would they fulfill or fail? I've only ever seen them be used to simulate voting behavior over time rather than evaluating a single election, so there ought to be a catch.

To be more specific, for the remainder of this questions, here are some examples:

5 candidates, 45 voters

Tally:

$$
begin{matrix}
5 & A>C>B>E>D \
5 & A>D>E>C>B \
8 & B>E>D>A>C \
3 & C>A>B>E>D \
7 & C>A>E>B>D \
2 & C>B>A>D>E \
7 & D>C>E>B>A \
8 & E>B>A>D>C
end{matrix}
$$

In matrix-form, for the Schulze Method this looks like:

$$
begin{bmatrix}
downarrow beats rightarrow & A & B & C & D & E \
A & & 20 & 26 & 30 & 22 \
B & 25 & & 16 & 33 & 18 \
C & 19 & 29 & & 17 & 24 \
D & 15 & 12 & 28 & & 14 \
E & 23 & 27 & 21 & 31 &
end{bmatrix}
$$

And ultimately you arrive at the Schulze ranking $E>A>C>B>D$ with E being the winner.

Now the CTMC versions looks like this: Instead of leaving the diagonal of the above matrix empty, you put in the negative of the sum of the number of times the given candidate is beaten, i.e. you sum up the rest of the column and put it in the empty spot, such that each column sums to 0.

$$M=
begin{bmatrix}
-82 & 20 & 26 & 30 & 22 \
25 & -88 & 16 & 33 & 18 \
19 & 29 & -91 & 17 & 24 \
15 & 12 & 28 & -111 & 14 \
23 & 27 & 21 & 31 & -78
end{bmatrix}
$$

And to find the corresponding CTMC ranking, I have to calculate $limlimits_{ttoinfty} e^{t M}$ and multiply the resulting matrix by an arbitrary positive vector $v$. - If I want the result in terms of the number of voters to vote for what candidate, the vector should sum up to the number of voters. The exact vector doesn't matter though, because I'm looking for the steady state which, up to a scale-factor, will be the same for all input vectors.
So if I do that for this example I get:

$$limlimits_{ttoinfty} e^{t M} v = begin{bmatrix} 10.151 \ 8.989 \ 8.977 \ 5.983 \ 10.900 end{bmatrix}$$

And my CTMC ranking ends up being $E>A>B>C>D$ which is almost the same as the Schulze ranking above, except for B and C which end up being really close.

For the other examples I will only show the CTMC matrix and the final rankings. That should give all the necessary information.

9 voters, 4 candidates:

$$
begin{bmatrix}
-14 & 5 & 5 & 3 \
4 & -11 & 7 & 5 \
4 & 2 & -16 & 5 \
6 & 4 & 4 & -13
end{bmatrix}
$$

Schulze ranking: Ties: $B>C>D>A$, $B>D>A>C$, $B>D>C>A$, $D>B>A>C$, $D>B>C>A$ (so either B or D wins)

CTMC ranking: $B>D>A>C$

(relative voter count in %), 4 candidates:

$$
begin{bmatrix}
-1.74 & .42 & .42 & .42 \
.58 & -1.06 & .68 & .68 \
.58 & .32 & -1.27 & .83 \
.58 & .32 & .17 & -1.93
end{bmatrix}
$$

Ranked Pairs ranking: $B>C>D>A$
CTMC ranking: $B>C>A>D$
(non-Condorcet methods would have elected A)

Final Example:
(relative voter count), 3 candidates:

$$begin{bmatrix}
-.52 & .68 & 0 \
0 & -.68 & .72 \
.52 & 0 & -.72
end{bmatrix}$$

Ranked Pairs ranking: $A>B>C$ ($C>A$ would have caused a loop but is the last choice to be locked in and is therefore ignored)
CTMC ranking: $A>B>C$ (the weight for C is only .02 smaller than B, the vector $v$ was chosen to sum to $1$.)

Sources:
https://de.wikipedia.org/wiki/Schulze-Methode
https://en.wikipedia.org/wiki/Schulze_method
https://en.wikipedia.org/wiki/Ranked_pairs

EDIT: Ok it looks like all those examples were mostly lucky coincidences. I just tried to apply it to another example as given in https://en.wikipedia.org/wiki/CPO-STV and it completely fails.

In that example I'd have the transition matrix

$$begin{bmatrix}
-184 & 25 & 25 & 25 & 25 \
49 & -119 & 15 & 41 & 49 \
34 & 34 & -107 & 34 & 34 \
75 & 34 & 41 & -121 & 54 \
26 & 26 & 26 & 21 & -162
end{bmatrix}$$

Where:

IRV-based STV gives: $C>A>B$

CPO-STV gives: $C>A>E$

CTMC gives: $D>C>Bleft(>E>Aright)$

So all of a sudden one of the first winners regardless of whether you are going for a Condorcet method or not will be the loser of CTMC. It should be noted that, in the CPO-STV as used, the Hagenbach-Bischoff-quota $frac{votes}{seats+1}$ was used rather than the more popular Droop-quota $frac{votes}{seats+1}+1$ or the widely considered fairer Meek-quota which changes as votes are cast, and that A only is elected immediately because the HB-quota of 25 is fulfilled whereas the other two of 26 would not have been. However, A would still have been voted for in either method: With Droop-quota, if I did this right, IRV-STV would have given $C>E>A$ and CPO-STV would have given $C>A>D$ so the above result is still a rather weird outcome, but the quota did have a significant effect on the result.

Meanwhile, on Schulze-STV: https://en.wikipedia.org/wiki/Schulze_STV

there are two different examples. For the first one I get:

$$begin{bmatrix}
-40 & 63 & 50 \
27 & -114 & 39 \
13 & 51 & -89
end{bmatrix}$$

Where:

STV gives: $A>B>C$

Schulze-STV gives: $A>B>C$

CTMC gives: $A>B>C$

so they all agree, whereas in the other example with vote-management in (one possible attack on STV systems) you get:

$$begin{bmatrix}
-52 & 63 & 38 \
27 & -114 & 39 \
25 & 51 & -77
end{bmatrix}$$

Where:

STV gives $A>C>B$

Schulze-STV gives $A>B>C$

CTMC gives $A>C>B$

clearly showing that, if you were to use it as an STV method, CTMC would be vulnerable to vote management.

So if it's viable at all it probably is really bad still. The question remains open though. Just the tone changes: Just how bad is it? Is there anything good (in terms of this method fulfilling some interesting voting axiom) at all or were all the examples above really just this lucky to have it work at all?

Note that a much simpler way to find the stationary distribution of a CTMC is to solve $mathbf M boldsymbol pi = mathbf 0$.

One of the problems with this system is a severe vulnerability to candidate cloning. Imagine two candidates $A, B$ with a 60% majority preferring $A$. As expected, $A$ wins.

$$
begin{align*}
3 &: A > B \
2 &: B > A \
end{align*} \
mathbf M = begin{bmatrix}-2 & 3 \ 2 & -3end{bmatrix}, boldsymbol pi = begin{bmatrix}3 \ 2 end{bmatrix}
$$

Now suppose we add a candidate $C$ that’s almost an exact copy of $B$ whose only purpose is to be slightly worse than $B$. Now $B$ wins!

$$
begin{align*}
3 &: A > B > C \
2 &: B > C > A \
end{align*} \
mathbf M = begin{bmatrix}-4 & 3 & 3 \ 2 & -3 & 5 \ 2 & 0 & -8end{bmatrix}, boldsymbol pi = begin{bmatrix}12 \ 13 \ 3 end{bmatrix}
$$