[EM] Participation criterion and Condorcet rules
Kristofer Munsterhjelm
km_elmet at t-online.de
Tue Aug 14 07:28:15 PDT 2018
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.
More information about the Election-Methods
mailing list