[EM] Participation criterion and Condorcet rules

[VoteFair]

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.

Both of theses concepts are related to the point that in a real-life 
election of, say, 50 candidates or more, most of those candidates can be 
dismissed as clearly not being a winner.

Yes, as the above example demonstrates, it is possible to carefully 
construct a case where none of the candidates is easily dismissed, but 
the key word here is "carefully."

In a real-life election, if such a convoluted/balanced/whatever case 
arose, the ballots would be counted a second time, and that recount 
would probably produce a different pairwise count.

Another way to say this (which I've said before) is that such cases are 
analogous to correctly identifying which sand dune in a desert is really 
the tallest sand dune.  In contrast, real-life elections seldom involve 
such closeness, and are more analogous to identifying the tallest 
mountain peak in a mountain range, where the correct identification is 
much easier to objectively recognize.

When an election is THAT "sand-dune-like" close, it's essentially a tie, 
and there are time-honored ways to deal with ties.

Regarding cases where the VoteFair ranking software differs from the 
Condorcet-Kemeny method, the software uses a setting that determines how 
many top choices are used in the final calculation.  Currently that 
setting is, I believe, without looking, 6 choices.  That's why the 
example here has 7 choices.  If that setting is changed to 12, then 13 
choices would be needed in order to construct a case in which the 
results differ (between VoteFair software and raw Condorcet-Kemeny 
calculations).

In a real-life election such an uncertain result difference -- between 
Condorcet-Kemeny and any other method, including Condorcet-Schulze and 
even Instant-Runoff Voting -- would be analyzed by looking at the 
pairwise counts for only the winners according to each method, and the 
actual winner would be the choice that is confirmed to be preferred by 
more than half the voters (not counting same-preference votes).

The only real-life election I've heard of where there were carefully 
balanced ballots is in a city where everyone was related to everyone and 
the voters paired up while in line to vote, and one person in the pair 
agreed to vote for candidate/relative A and the other person agreed to 
vote for candidate/relative B. The result, as intended, was an exact tie.

So, again, these edge cases are of interest to academic discussions -- 
including the ones here -- but these differences are not important in 
the typical results of real-life elections involving thousands (or even 
just hundreds) of voters.  After all, as long as Instant-Runoff Voting 
is seriously being considered by many people to be "fair," then the 
subtleties that Kristofer refers to are way too insignificant to be 
important in an actual election.

As a refinement, I'll more fully state that I predict that the 
Condorcet-Kemeny method, and the "insertion-sort" calculation method 
that is used in VoteFair popularity ranking to reduce the number of 
candidates used in the final Condorcet-Kemeny calculations, will have 
fewer failures according to most fairness criteria, compared to the 
failures of other vote-counting methods.

To clarify, strictly speaking Kristofer is correct in all his 
statements.  Yet it's important to remember:

* The default setting specified in the VoteFair ranking software can be 
increased so that the difference between "Kemeny" and "VoteFair" 
requires more and more choices.

* As more and more choices are needed to carefully construct cases where 
"Kemeny" and "VoteFair" differ, the probability of those cases occurring 
in a real-life election are so small that they are similar to the odds 
of getting an exact tie in plurality elections, and they can be handled 
in the same way (typically involving a judicial ruling).

* Real-life elections so rarely involve NP-hard cases (that affect who 
wins) that a long Condorcet-Kemeny computation time is as unlikely as an 
exact tie in plurality counting.  If a week-long calculation time were 
needed to be certain of the Condorcet-Kemeny result, then the election 
does not have a Condorcet winner, and ANY reasonable result -- by ANY 
method -- is going to be very controversial, and probably subject to 
judicial oversight.

When academic research finally analyzes the different vote-counting 
methods to measure HOW OFTEN each method fails each fairness criterion, 
then we will know whether the Condorcet-Kemeny method indeed has fewer 
failures.  Assuming it does, the minor issue of extremely rare, 
carefully constructed, NP-hard (long-computation-time) cases becomes 
insignificant as a barrier to its use.

Richard Fobes


On 8/10/2018 5:58 AM, Kristofer Munsterhjelm wrote:
> 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 :-)