# [EM] Participation criterion and Condorcet rules

Kristofer Munsterhjelm km_elmet at t-online.de
Fri Aug 10 05:58:31 PDT 2018

```On 2018-08-10 07:20, VoteFair wrote:
> On 8/8/2018 11:43 AM, John wrote:
>  > That method is NP-hard and involves complex tabulation.
>
> Keep in mind that NP-hardness of the Condorcet-Kemeny method applies to
> ranking ALL the choices, from most popular, second-most popular, and so
> on down to least popular.
>
> In an election, only the winner needs to be identified.

Determining the winner is also NP-hard, as given in

BARTHOLDI, John; TOVEY, Craig A.; TRICK, Michael A. Voting schemes for
which it can be difficult to tell who won the election. Social Choice
and welfare, 1989, 6.2: 157-165,

theorem 2 (p. 163).

> So, if there are, say, 150 candidates, most of those candidates can
> easily be identified as not winning, and I'd guess there would be, at
> most, 15 candidates who might be able to win, and, in a worst-case
> scenario, the full ranking of those 15 candidates can be calculated --
> with the raw Condorcet-Kemeny method -- within a few hours at most.  If
> there are "just" 12 might-win candidates, the calculations take just a
> few seconds at most.

What you're saying here is more that the intractability of an NP-hard
problem is a worst case property. That is true (assuming P != NP). For
instance, 3-SAT or integer linear programming is NP-hard, but many
instances of 3-SAT of IP problems are easy to solve in practice (e.g.
integer programs with totally unimodular constraint matrices). Likewise,
some Kemeny instances are very easy indeed, but the problem of finding
the winner is still NP-hard.

> Another way to say this is that if there is circular ambiguity that
> amounts to a near-tie among 20 or more candidates, then, yes, the
> calculations, in theory, would take a very long time.  How often would
> that occur?  So rarely that it's not an issue in real-life elections.
> It's more of an academic issue.

> As for "complex tabulation," the results are calculated from the
> pairwise counts, the same as for any Condorcet method.  If you are
> referring to the task of writing the code to do the calculations, I've
> already done that, and posted the code here:
>
>    https://github.com/cpsolver/VoteFair-ranking

To my knowledge, that method is not the same as the Kemeny method. That
is, there exist elections where the Kemeny winner is X and the VoteFair
ranking software returns Y as the winner. They may be unlikely, but as
long as there exists at least one such election, the method is not the
same, mathematically speaking.

After adjusting an old script of mine, it finds the following example:

1: A>E>G>B>D>F>C
1: B>F>D>A>G>E>C
1: C>G>B>E>F>D>A
1: F>A>E>D>B>C>G
1: F>C>D>A>E>G>B

The script says that VoteFair elects B here (with full ordering
B>F>A>D>E>C>G).
The best Kemeny ordering starting with B is B>F>D>A>E>C>G with score 64,
but the best Kemeny ordering starting with F is F>A>E>B>D>C>G with score
65. 65 is the maximum Kemeny score for this election, so F is the winner
according to Kemeny.

> The code also handles ties, meaning that if there are any ties at any
> ranking levels, the full-ranking results include which choices are tied
> at which levels.  In other words, unlike some vote-counting code, this
> code does not give up when it reaches a tie; instead it fully calculates
> the full ranking, ties included.

If a tie between A and B for first place should exist whenever the
maximum Kemeny score achievable by an ordering starting with A is the
same as the maximum Kemeny score by an ordering starting with B, then
there are instances where two candidates are tied according to that
definition, but VoteFair doesn't find the tie. In my 2012 example, both
C>D>B>A and B>C>D>A have Kemeny score 44, but VoteFair does not rank C
and B equal.

The other direction is also possible. The script finds:

1: C>A>F>G>E>B>D
1: E>B>G>C>D>A>F
1: F>D>B>C>E>A>G

where C is the unique Kemeny winner (C>F>E>B>D>A>G with score 40), but
VoteFair considers B, C, and F tied for first (full ordering:
B=C=F>E>A=D=G).

There may be bugs in my scripts, of course; if I've got any of those
observations wrong, tell me and I'll try to fix the bugs :-)
```