[EM] Participation criterion and Condorcet rules

[Kristofer Munsterhjelm]

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 :-)