[EM] Participation criterion and Condorcet rules

[Kristofer Munsterhjelm]

On 2018-08-11 07:22, VoteFair wrote:
> On 8/10/2018 5:58 AM, Kristofer Munsterhjelm wrote:
>  > ....
>  > 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
> 
> This is a good example of my point that real-life elections would almost 
> never have a carefully constructed situation like this where it would be 
> "NP-hard" to correctly calculate the winner using the Condorcet-Kemeny 
> method.
> 
> I do agree with Kristofer's correction that, in SOME cases, it can be 
> NP-hard to calculate the winner.

As I said, it's always NP-hard, because NP-hard is a *worst-case property*.

The subset sum problem "given a set of numbers A and a number b, find a 
subset of A that sums to b" is NP-hard (and the decision problem is 
NP-complete).
However, if the numbers in A are so that the every number is greater in 
value than the sum of all the numbers smaller than it, then it's easy. 
All you have to do is find the greatest number less than b, add it to 
the solution, subtract this number from b, and repeat. If you end up 
with excess at the end, then there's no such subset of A that sums to b.

NP-hard is not always hard :-)

> Currently that setting is, I believe, without looking, 6 choices.
> That's why the example here has 7 choices.

That was mainly for convenience. I have one with 5 as well, but it's 
more messy as I haven't let the script run through as many different 
examples:

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

According to Kemeny score, there's a tie for first between D and E 
(score 93 for orderings D>C>B>E>A and E>C>A>D>B), but VoteFair says that 
C (score 92 for C>E>A>D>B) is the unique winner.

In any case, I see what you're saying, but the introduction of "real 
life cases" makes analysis much harder and can potentially open up 
loopholes. For instance, IRV advocates sometimes claim that monotonicity 
failure happens so rarely that IRV should be considered to pass 
monotonicity in all real-world settings. From a mathematical point of 
view, a method fails some property as long as there's at least one 
example, but a common response is "but that one doesn't count, find 
another".

For VoteFair, I don't think it's too likely that it gets the result 
wrong in real life. But I could be wrong. I don't know if the number of 
wrong-call elections stay low as the number of candidates increases, or 
if there's some strategy that exploits these. In contrast, the behavior 
of Kemeny itself is well known.

To avoid that tangle, perhaps you could use an algorithm that is always 
correct, but in a few rare cases runs for a very long time (or times out 
with "can't tell in the time allotted").

That way, all properties that hold for Kemeny would also hold for 
VoteFair, and the counters would know whether they were in what a 
hard-to-tell election or not without having to calculate the exact 
Kemeny scores for comparison.

The simplest way to do that, that I can think of, is to use an integer 
programming library/interface like Math::LP and set up the program for 
solving a Kemeny election. 
https://www.cs.cmu.edu/~conitzer/kemenyAAAI06.pdf page 4 gives a linear 
programming approximation to determining the Kemeny score of a 
candidate. The approximation is exact if the x_(a,b) variables are 
specified to be integers.

There are also fixed-parameter tractable algorithms whose runtime is 
polynomial if the number of upsets is fixed, but exponential in the 
number of upsets, e.g.

RAMAN, Venkatesh; SAURABH, Saket. Parameterized algorithms for feedback 
set problems and their duals in tournaments. Theoretical Computer 
Science, 2006, 351.3: 446-458,

but coding them from scratch could be tedious.