[EM] Participation criterion and Condorcet rules
VoteFair
electionmethods at votefair.org
Fri Aug 10 22:22:32 PDT 2018
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 :-)
More information about the Election-Methods
mailing list