<div dir="auto"><div dir="auto">Improved procedures for counting Kemeny-Young interest me to the degree that they shed light on the de-cloned version based on the Swap Cost metric rather than the Kendall-tau metric.<div dir="auto"><br></div><div dir="auto">Kendall-tau does not make the cost of a single swap depend on the relative popularity of the two candidates being swapped.</div><div dir="auto"><br></div><div dir="auto">In contrast, the Swap Cost metric of swapping A>B to B>A is the product ab', where a is alternative A's random ballot favorite probability, and b is B's random ballot anti-favorite probability.</div><div dir="auto"><br></div><div dir="auto">These probabilities are deterministic values that can be found in the same way that you can calculate the deterministic fraction 1/36 to be the probability of "snake eyes" on the first roll of a pair of fair dice.</div><div dir="auto"><br></div><div dir="auto">So a reversal that raises B by lowering A has a democratic cost jointly proportional to the popularity of A and the "anti-popularity" of B.</div><div dir="auto"><br></div><div dir="auto">In this context a natural a-priori nominal order places A ahead of B iff a/a'>b/b'.</div><div dir="auto"><br></div><div dir="auto">The Kendall-tau metric yields no such nominal order because Kendall-tau is insensitive to the relative popularity of the transposing candidates; every swap has the same cost regardless of the relative levels of democratic support of the candidates involved in the swap.</div><div dir="auto"><br></div><div dir="auto">Having a natural nominal order gives a natural agenda order that can be refined by sorting pairwise counts; for example.</div><div dir="auto"><br></div><div dir="auto">-Forest</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Sun, Apr 2, 2023, 1:36 PM Kristofer Munsterhjelm <<a href="mailto:km_elmet@t-online.de" target="_blank" rel="noreferrer">km_elmet@t-online.de</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">On 02.04.2023 19:20, Richard, the VoteFair guy wrote:<br>
<br>
> Clarification:  As Kristofer points out, there are contrived (highly <br>
> cyclic) cases where the results do not match Kemeny results.  Yet the <br>
> top 7 or so candidates can be identified and run through the full Kemeny <br>
> calculations to identify the winner.  It's possible the Kemeny winner <br>
> from the full set of candidates does not get identified as one of the <br>
> top 7 candidates, but in those contrived cases any winner would be <br>
> controversial (in the same way that an algorithm for finding the highest <br>
> mountain would produce controversial results if it were used to find the <br>
> highest sand dune in a desert).<br>
<br>
I'd like to also clarify that mixed integer programming solvers can do <br>
Kemeny of Smith sets of size 20 or more in reasonable time. If I recall <br>
correctly, state of the art like CPLEX or Gurobi can do up to 40, but <br>
I'm not completely sure I got those figures correct.<br>
<br>
If the sorting approach is Monte Carlo (takes a fixed time though being <br>
incorrect with small probability), then MIP is Las Vegas (always correct <br>
but sometimes takes a very long time) - though the analogy is incomplete <br>
as they're deterministic algorithms.<br>
<br>
In practice, it may not matter; but then, in practice, we could use a <br>
polytime election method, get similar results, and please theoreticians <br>
too :-)<br>
<br>
-km<br>
----<br>
Election-Methods mailing list - see <a href="https://electorama.com/em" rel="noreferrer noreferrer noreferrer" target="_blank">https://electorama.com/em</a> for list info<br>
</blockquote></div></div>