[EM] Sorting algorithms applied to candidate ranking

[Forest Simmons]

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.

Kendall-tau does not make the cost of a single swap depend on the relative
popularity of the two candidates being swapped.

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.

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.

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.

In this context a natural a-priori nominal order places A ahead of B iff
a/a'>b/b'.

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.

Having a natural nominal order gives a natural agenda order that can be
refined by sorting pairwise counts; for example.

-Forest

On Sun, Apr 2, 2023, 1:36 PM Kristofer Munsterhjelm <km_elmet at t-online.de>
wrote:

> On 02.04.2023 19:20, Richard, the VoteFair guy wrote:
>
> > Clarification:  As Kristofer points out, there are contrived (highly
> > cyclic) cases where the results do not match Kemeny results.  Yet the
> > top 7 or so candidates can be identified and run through the full Kemeny
> > calculations to identify the winner.  It's possible the Kemeny winner
> > from the full set of candidates does not get identified as one of the
> > top 7 candidates, but in those contrived cases any winner would be
> > controversial (in the same way that an algorithm for finding the highest
> > mountain would produce controversial results if it were used to find the
> > highest sand dune in a desert).
>
> I'd like to also clarify that mixed integer programming solvers can do
> Kemeny of Smith sets of size 20 or more in reasonable time. If I recall
> correctly, state of the art like CPLEX or Gurobi can do up to 40, but
> I'm not completely sure I got those figures correct.
>
> If the sorting approach is Monte Carlo (takes a fixed time though being
> incorrect with small probability), then MIP is Las Vegas (always correct
> but sometimes takes a very long time) - though the analogy is incomplete
> as they're deterministic algorithms.
>
> In practice, it may not matter; but then, in practice, we could use a
> polytime election method, get similar results, and please theoreticians
> too :-)
>
> -km
> ----
> Election-Methods mailing list - see https://electorama.com/em for list
> info
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20230402/7161dc88/attachment.htm>