V
VoteFair
Thu, Jan 23, 2020 5:53 PM
On 1/22/2020 3:49 PM, Kristofer Munsterhjelm wrote:
Given this definition, there are two possibilities. Either the VoteFair
software implements the VoteFair method, or it does not. ...
If the default settings are used, and if the number of candidates is no
more than the check-all-sequence-scores setting (which I think is 6),
then the software implements the VoteFair popularity ranking method,
which yields the same results as the Condorcet-Kemeny method.
In other words you are not allowing for a third possibility, which -- of
course -- depends on the number of candidates.
... It seems that you instead are saying that, as you
define the VoteFair ranking, it does agree with Kemeny all the time, but
the software doesn't.
Yes, this is the third possibility. The software CAN always yield the
same results -- simply by limiting the number of candidates it can
handle (or, up to a limit based on computing power, increasing the
number of candidates checked by the full/slow method).
Could you give me a definition of the VoteFair method itself? Without
knowing what bit is the software and what bit is the method, it's
difficult to get further. For instance, it would be hard to know whether
the results that the VoteFair software gives when Kemeny orderings are
tied is a property of the method or of the software, because the
definition of the Kemeny method itself doesn't say what should happen in
such a case.
Originally I wrote the definition of VoteFair popularity ranking (which
at that time I called VoteFair ranking) on Wikipedia, and Markus Schulze
re-named the article to the "Kemeny-Young method" claiming that the two
methods are the same. So the definition there matches VoteFair
popularity ranking because I wrote it.
Yes, the issue of how to handle Condorcet-cycle ties is not stated by
John Kemeny (as far as I know), and I have not explicitly stated how
such ties are handled in VoteFair popularity ranking. If I did make such
a statement then you or others might argue that the two methods are not
the same.
The software does attempt to handle ties, either to use a tie-breaking
criteria or to declare an official tie. In the latter case, the VoteFair
approach presumably matches the Kemeny approach. In the former case the
candidates in the cycle can be re-sequenced and the sequence sums yield
the same highest sum, yet SOME of those "tied" sequences can yield
different sums. If this seems complex it's because it IS complex. It
took lots of work to get the software to handle these and other "edge"
cases. This approach is unlike what many software developers do, which
is to dismiss edge cases with some kind of error message. In other
words, my software looks deeper into the "tie."
So, keeping in mind that neither John Kemeny nor I have officially
stated how ties (in the sequence sums) are to be handled, both methods
are mathematically equivalent.
I avoid using the word "same" because John Kemeny defines the sequence
score in terms of counting votes that OPPOSE a candidate (and finding
the minimum score), whereas VoteFair popularity ranking (which I came up
with without knowing about the Kemeny method) defines the sequence score
in terms of counting votes that SUPPORT a candidate (and finding the
maximum score).
If this still isn't clear, please keep asking for clarifications. Thank
you for seeking to understand this method.
Richard Fobes
On 1/22/2020 3:49 PM, Kristofer Munsterhjelm wrote:
On 12/01/2020 05.34, VoteFair wrote:
Kristofer ~
It occurs to me that you might be thinking that the VoteFair Ranking
SOFTWARE provides the definition of VoteFair popularity ranking. That
is not the case.
VoteFair popularity ranking is defined in two of my books -- "The
Creative Problem Solver's Toolbox" and "Ending The Hidden Unfairness In
U.S. Elections" -- and in the Condorcet-Kemeny ("Kemeny-Young")
Wikipedia article.
Those definitions should make it clear to anyone who understands
mathematics that the difference between VoteFair popularity ranking and
the method John Kemeny published is that Kemeny counts opposition and
VoteFair counts support, and that otherwise the two methods are
mathematically equivalent.
Let me try to restate that to see if I got it right, because it seems
like an odd distinction.
A ranked voting method is a function that takes, as an input, a set of
ballots, and produces either a social ranking or a winner set (depending
on what definition you agree with).
What happens inside the function is irrelevant to the definition. You
could, if you had infinite memory, implement it as a huge table that you
would just look up to find out what the output would be for a given input.
Given this definition, there are two possibilities. Either the VoteFair
software implements the VoteFair method, or it does not. By "implements
the method" I mean that running the VoteFair software on some input
election always provides the output that the method would.
Now, I was assuming that the software was an accurate implementation of
the method, so that instead of a method, you actually had a family of
them (parameterized by that constant), none of which would agree with
Kemeny all the time. It seems that you instead are saying that, as you
define the VoteFair ranking, it does agree with Kemeny all the time, but
the software doesn't.
Could you give me a definition of the VoteFair method itself? Without
knowing what bit is the software and what bit is the method, it's
difficult to get further. For instance, it would be hard to know whether
the results that the VoteFair software gives when Kemeny orderings are
tied is a property of the method or of the software, because the
definition of the Kemeny method itself doesn't say what should happen in
such a case.
On 1/22/2020 3:49 PM, Kristofer Munsterhjelm wrote:
> Given this definition, there are two possibilities. Either the VoteFair
> software implements the VoteFair method, or it does not. ...
If the default settings are used, and if the number of candidates is no
more than the check-all-sequence-scores setting (which I think is 6),
then the software implements the VoteFair popularity ranking method,
which yields the same results as the Condorcet-Kemeny method.
In other words you are not allowing for a third possibility, which -- of
course -- depends on the number of candidates.
> ... It seems that you instead are saying that, as you
> define the VoteFair ranking, it does agree with Kemeny all the time, but
> the software doesn't.
Yes, this is the third possibility. The software CAN always yield the
same results -- simply by limiting the number of candidates it can
handle (or, up to a limit based on computing power, increasing the
number of candidates checked by the full/slow method).
> Could you give me a definition of the VoteFair method itself? Without
> knowing what bit is the software and what bit is the method, it's
> difficult to get further. For instance, it would be hard to know whether
> the results that the VoteFair software gives when Kemeny orderings are
> tied is a property of the method or of the software, because the
> definition of the Kemeny method itself doesn't say what should happen in
> such a case.
Originally I wrote the definition of VoteFair popularity ranking (which
at that time I called VoteFair ranking) on Wikipedia, and Markus Schulze
re-named the article to the "Kemeny-Young method" claiming that the two
methods are the same. So the definition there matches VoteFair
popularity ranking because I wrote it.
Yes, the issue of how to handle Condorcet-cycle ties is not stated by
John Kemeny (as far as I know), and I have not explicitly stated how
such ties are handled in VoteFair popularity ranking. If I did make such
a statement then you or others might argue that the two methods are not
the same.
The software does attempt to handle ties, either to use a tie-breaking
criteria or to declare an official tie. In the latter case, the VoteFair
approach presumably matches the Kemeny approach. In the former case the
candidates in the cycle can be re-sequenced and the sequence sums yield
the same highest sum, yet SOME of those "tied" sequences can yield
different sums. If this seems complex it's because it IS complex. It
took lots of work to get the software to handle these and other "edge"
cases. This approach is unlike what many software developers do, which
is to dismiss edge cases with some kind of error message. In other
words, my software looks deeper into the "tie."
So, keeping in mind that neither John Kemeny nor I have officially
stated how ties (in the sequence sums) are to be handled, both methods
are mathematically equivalent.
I avoid using the word "same" because John Kemeny defines the sequence
score in terms of counting votes that OPPOSE a candidate (and finding
the minimum score), whereas VoteFair popularity ranking (which I came up
with without knowing about the Kemeny method) defines the sequence score
in terms of counting votes that SUPPORT a candidate (and finding the
maximum score).
If this still isn't clear, please keep asking for clarifications. Thank
you for seeking to understand this method.
Richard Fobes
On 1/22/2020 3:49 PM, Kristofer Munsterhjelm wrote:
> On 12/01/2020 05.34, VoteFair wrote:
>> Kristofer ~
>>
>> It occurs to me that you might be thinking that the VoteFair Ranking
>> SOFTWARE provides the definition of VoteFair popularity ranking. That
>> is not the case.
>>
>> VoteFair popularity ranking is defined in two of my books -- "The
>> Creative Problem Solver's Toolbox" and "Ending The Hidden Unfairness In
>> U.S. Elections" -- and in the Condorcet-Kemeny ("Kemeny-Young")
>> Wikipedia article.
>>
>> Those definitions should make it clear to anyone who understands
>> mathematics that the difference between VoteFair popularity ranking and
>> the method John Kemeny published is that Kemeny counts opposition and
>> VoteFair counts support, and that otherwise the two methods are
>> mathematically equivalent.
>
> Let me try to restate that to see if I got it right, because it seems
> like an odd distinction.
>
> A ranked voting method is a function that takes, as an input, a set of
> ballots, and produces either a social ranking or a winner set (depending
> on what definition you agree with).
>
> What happens inside the function is irrelevant to the definition. You
> could, if you had infinite memory, implement it as a huge table that you
> would just look up to find out what the output would be for a given input.
>
> Given this definition, there are two possibilities. Either the VoteFair
> software implements the VoteFair method, or it does not. By "implements
> the method" I mean that running the VoteFair software on some input
> election always provides the output that the method would.
>
> Now, I was assuming that the software was an accurate implementation of
> the method, so that instead of a method, you actually had a family of
> them (parameterized by that constant), none of which would agree with
> Kemeny all the time. It seems that you instead are saying that, as you
> define the VoteFair ranking, it does agree with Kemeny all the time, but
> the software doesn't.
>
> Could you give me a definition of the VoteFair method itself? Without
> knowing what bit is the software and what bit is the method, it's
> difficult to get further. For instance, it would be hard to know whether
> the results that the VoteFair software gives when Kemeny orderings are
> tied is a property of the method or of the software, because the
> definition of the Kemeny method itself doesn't say what should happen in
> such a case.
>
KM
Kristofer Munsterhjelm
Tue, Feb 25, 2020 11:17 PM
I hope this reply isn't too late, so here we go:
On 23/01/2020 18.53, VoteFair wrote:
On 1/22/2020 3:49 PM, Kristofer Munsterhjelm wrote:
Given this definition, there are two possibilities. Either the VoteFair
software implements the VoteFair method, or it does not. ...
If the default settings are used, and if the number of candidates is no
more than the check-all-sequence-scores setting (which I think is 6),
then the software implements the VoteFair popularity ranking method,
which yields the same results as the Condorcet-Kemeny method.
In other words you are not allowing for a third possibility, which -- of
course -- depends on the number of candidates.
... It seems that you instead are saying that, as you
define the VoteFair ranking, it does agree with Kemeny all the time, but
the software doesn't.
Yes, this is the third possibility. The software CAN always yield the
same results -- simply by limiting the number of candidates it can
handle (or, up to a limit based on computing power, increasing the
number of candidates checked by the full/slow method).
Could you give me a definition of the VoteFair method itself? Without
knowing what bit is the software and what bit is the method, it's
difficult to get further. For instance, it would be hard to know whether
the results that the VoteFair software gives when Kemeny orderings are
tied is a property of the method or of the software, because the
definition of the Kemeny method itself doesn't say what should happen in
such a case.
Originally I wrote the definition of VoteFair popularity ranking (which
at that time I called VoteFair ranking) on Wikipedia, and Markus Schulze
re-named the article to the "Kemeny-Young method" claiming that the two
methods are the same. So the definition there matches VoteFair
popularity ranking because I wrote it.
Alright, that enabled me to track down the original definition by
looking at the Wikipedia history archive. I've quoted it below.
VoteFair ranking shall be done using software (such as accessible at
www.VoteFair.org) that performs the following calculations. The
preferences indicated in the ballots are counted to produce a tally
table in which all the possible pairs of candidates are listed, one
number for each pair indicates the number of voters who prefer one
candidate in the pair over the other candidate in the pair, another
number for each pair indicates the number of voters who have the
opposite preference for these two candidates, and a third number for
each pair indicates the number of voters who express no preference
between the two candidates. Using a computer, each possible sequence of
candidates is considered, where a sequence consists of one of the
candidates being regarded as the most popular candidate, another
candidate being regarded as the second-most popular candidate, and so
on. For each such sequence the numbers in the tally table that apply to
that sequence are added together to produce a sequence score for this
sequence. The sequence that has the highest sequence score indicates the
overall order of preference for the candidates. If there is more than
one sequence that has the same highest score, the sequences with this
score shall be analyzed to identify one or more ties at one or more
preference levels.
I agree that the definition above describes the Kemeny-Young method. I'd
even say it's the same (not just mathematically equivalent) even though
the mechanics are different:
There exist implementations of Kemeny-Young that don't rely on
enumerating all combinations and then choosing the best one. For
instance, integer programming implementations scale much better while
producing the optimal result. If the implementation mattered as to
whether one method is the same as another, then these implementations
would not be of the Kemeny-Young method because they don't use
exhaustive enumerations. But they are generally considered to be.
Yes, the issue of how to handle Condorcet-cycle ties is not stated by
John Kemeny (as far as I know), and I have not explicitly stated how
such ties are handled in VoteFair popularity ranking. If I did make such
a statement then you or others might argue that the two methods are not
the same.
The software does attempt to handle ties, either to use a tie-breaking
criteria or to declare an official tie. In the latter case, the VoteFair
approach presumably matches the Kemeny approach. In the former case the
candidates in the cycle can be re-sequenced and the sequence sums yield
the same highest sum, yet SOME of those "tied" sequences can yield
different sums. If this seems complex it's because it IS complex. It
took lots of work to get the software to handle these and other "edge"
cases. This approach is unlike what many software developers do, which
is to dismiss edge cases with some kind of error message. In other
words, my software looks deeper into the "tie."
So, keeping in mind that neither John Kemeny nor I have officially
stated how ties (in the sequence sums) are to be handled, both methods
are mathematically equivalent.
So it seems the situation is different than I thought. Instead of the
method not being the same as Kemeny, the case is more that the software
doesn't implement the method, but rather something that approximates
(and differs from) it.
As I've said before, I consider a method to be algorithm-agnostic.
Schulze implemented by the beatpath mechanism is the same method as
Schulze implemented by the cloneproof Schwartz dropping mechanism.
Furthermore, I think that a method is a function that takes an election
as its input and then provides either a winner set or a ranking (order
of finish).
If a method uses some kind of auxiliary input parameter, then the method
with one value of that auxiliary input parameter is not the same as the
method with another value of that parameter, unless it happens to be
inconsequential for the outcome. E.g. STV with a Droop quota is not the
same method as STV with the Hare method.
A software implementation is "of the method" or "implements the method"
if it agrees with the method for every input that it returns an output for.
Since the VoteFair method definition is the same (or equivalent) to the
Kemeny-Young method definition, the methods are the same. But the
software doesn't implement that method[1]. Instead, it implements a
family of approximations determined by the parameter. Each approximation
agrees with the full method if the number of candidates is below a
certain number, and returns undefined results above this number.
But the software doesn't give any impression that this is what it does.
Instead, from the documentation, one would get the impression that it
implements the Kemeny method (for any number of candidates). E.g. from
the VoteFair::VoteFairRanking Perl module documentation:
This module calculates VoteFair Ranking results. The portions of
VoteFair Ranking implemented here are:
- VoteFair popularity ranking. This voting method calculates the full
popularity ranking of all candidates (or choices in the case of a
survey) from most popular and second-most popular down to least
popular. It uses the preference information collected on 1-2-3
ballots (or any equivalent way of expressing "ranked" preferences).
When a single position is being filled, the most popular candidate is
declared the winner. This calculation method is mathematically
equivalent to the Condorcet-Kemeny election method.
VoteFair popularity ranking is described in Wikipedia, and is
mathematically equivalent to the Condorcet-Kemeny method. The following
comments explain the algorithm used here, which quickly calculates the
ranking results. This explanation is important because some academic
sources claim that the computations cannot be done quickly if there is a
large number of choices being ranked.
Calculation time:
The full algorithm used to calculate VoteFair popularity ranking
results has a calculation time that is less than or equal to the
following polynomial function:
T = A + ( B * N ) + ( C * ( N * N ) )
where T is the calculation time, N is the number of choices, and A
and B and C are constants. (In mathematical notation, N * N would be
written as N squared.) This function includes the calculation time
required for the Choice-Specific Pairwise-Score (CSPS) pre-sort
calculations.
This time contrasts with the slow execution times of the "NP-hard"
approach, in which every sequence score is calculated in order to find
the sequence with the highest score. If every sequence score were
calculated (from scratch), the calculation time would be proportional to:
N! * N * N
where N is the number of choices, N! is N factorial (2 * 3 * 4 * ...
- N), and N * N equals N squared. Note that N factorial equals the number
of possible sequences, and N squared times one-half approximately equals
the number of pairwise counts that are added to calculate each sequence
score.
This clarification about calculation time is included because there
is an academically common -- yet mistaken -- belief that calculating the
"Condorcet-Kemeny method" is "NP-hard" and cannot be calculated in a
time that is proportional to a polynomial function of N (the number of
choices).
This description gives the impression that the software calculates the
VoteFair ranking (period, i.e. no approximations), that it does so in
polynomial time, and that it is possible to determine the Kemeny-Young
winner in polynomial time. But what it does is calculate an
approximation, which is how it can manage to do so in polytime without
proving P=NP.
Similarly, in the VoteFair C++ README.txt file:
// * VoteFair popularity ranking. This voting method calculates the
// full popularity ranking of all candidates (or choices in the case
// of a survey) from most popular and second-most popular down to
// least popular. It uses the preference information collected on
// 1-2-3 ballots (or any equivalent way of expressing "ranked"
// preferences). When a single position is being filled, the most
// popular candidate is declared the winner. This calculation method
// is mathematically equivalent to the Condorcet-Kemeny election
// method.
which gives the impression that again, the software calculates the
method (although at least it doesn't mention being able to circumvent
NP-hardness :-).
Now, if I'm generous, I could say that what I understand you to be
saying is that when you say "this voting method calculates...", you're
talking about the software, but when you're saying "this calculation
method is mathematically equivalent...", you're talking about the
method. But it's easy to draw the wrong conclusion, as I did earlier.
The documentation could thus use being more clear about what the
software implements -- or the software could be rewritten so that it
implements the actual VoteFair (or Kemeny) method.
And again, I would suggest the latter as a good strategy. Instead of
producing correct results up to a certain number of candidates and then
producing undefined results - that it produces the correct results in
potentially exponential time, and that it just quits with a timeout if
it takes too long a time.
That way, it's immediately obvious to the user whether the method
produces a correct result (namely, that it'd do so when it does produce
a result at all). Instead of producing a result in managable time with
some probability (which you argue is low) of producing something
incorrect, it produces a result in managable time with similar (high if
you're right) probability of not getting a timeout.
In addition, if you use a reasonably good integer programming solver to
do so, you can quickly solve cases that the current software can't, e.g.
1000 candidates but no cycles at all.
[1] Strictly speaking, it implements a generalization of that method,
but I don't want to make things more confusing than they need to be; I'd
rather deal with one point at a time.
I hope this reply isn't too late, so here we go:
On 23/01/2020 18.53, VoteFair wrote:
> On 1/22/2020 3:49 PM, Kristofer Munsterhjelm wrote:
>> Given this definition, there are two possibilities. Either the VoteFair
>> software implements the VoteFair method, or it does not. ...
>
> If the default settings are used, and if the number of candidates is no
> more than the check-all-sequence-scores setting (which I think is 6),
> then the software implements the VoteFair popularity ranking method,
> which yields the same results as the Condorcet-Kemeny method.
>
> In other words you are not allowing for a third possibility, which -- of
> course -- depends on the number of candidates.
>
>> ... It seems that you instead are saying that, as you
>> define the VoteFair ranking, it does agree with Kemeny all the time, but
>> the software doesn't.
>
> Yes, this is the third possibility. The software CAN always yield the
> same results -- simply by limiting the number of candidates it can
> handle (or, up to a limit based on computing power, increasing the
> number of candidates checked by the full/slow method).
>
>> Could you give me a definition of the VoteFair method itself? Without
>> knowing what bit is the software and what bit is the method, it's
>> difficult to get further. For instance, it would be hard to know whether
>> the results that the VoteFair software gives when Kemeny orderings are
>> tied is a property of the method or of the software, because the
>> definition of the Kemeny method itself doesn't say what should happen in
>> such a case.
>
> Originally I wrote the definition of VoteFair popularity ranking (which
> at that time I called VoteFair ranking) on Wikipedia, and Markus Schulze
> re-named the article to the "Kemeny-Young method" claiming that the two
> methods are the same. So the definition there matches VoteFair
> popularity ranking because I wrote it.
Alright, that enabled me to track down the original definition by
looking at the Wikipedia history archive. I've quoted it below.
> VoteFair ranking shall be done using software (such as accessible at
> www.VoteFair.org) that performs the following calculations. The
> preferences indicated in the ballots are counted to produce a tally
> table in which all the possible pairs of candidates are listed, one
> number for each pair indicates the number of voters who prefer one
> candidate in the pair over the other candidate in the pair, another
> number for each pair indicates the number of voters who have the
> opposite preference for these two candidates, and a third number for
> each pair indicates the number of voters who express no preference
> between the two candidates. Using a computer, each possible sequence of
> candidates is considered, where a sequence consists of one of the
> candidates being regarded as the most popular candidate, another
> candidate being regarded as the second-most popular candidate, and so
> on. For each such sequence the numbers in the tally table that apply to
> that sequence are added together to produce a sequence score for this
> sequence. The sequence that has the highest sequence score indicates the
> overall order of preference for the candidates. If there is more than
> one sequence that has the same highest score, the sequences with this
> score shall be analyzed to identify one or more ties at one or more
> preference levels.
I agree that the definition above describes the Kemeny-Young method. I'd
even say it's the same (not just mathematically equivalent) even though
the mechanics are different:
There exist implementations of Kemeny-Young that don't rely on
enumerating all combinations and then choosing the best one. For
instance, integer programming implementations scale much better while
producing the optimal result. If the implementation mattered as to
whether one method is the same as another, then these implementations
would not be of the Kemeny-Young method because they don't use
exhaustive enumerations. But they are generally considered to be.
> Yes, the issue of how to handle Condorcet-cycle ties is not stated by
> John Kemeny (as far as I know), and I have not explicitly stated how
> such ties are handled in VoteFair popularity ranking. If I did make such
> a statement then you or others might argue that the two methods are not
> the same.
>
> The software does attempt to handle ties, either to use a tie-breaking
> criteria or to declare an official tie. In the latter case, the VoteFair
> approach presumably matches the Kemeny approach. In the former case the
> candidates in the cycle can be re-sequenced and the sequence sums yield
> the same highest sum, yet SOME of those "tied" sequences can yield
> different sums. If this seems complex it's because it IS complex. It
> took lots of work to get the software to handle these and other "edge"
> cases. This approach is unlike what many software developers do, which
> is to dismiss edge cases with some kind of error message. In other
> words, my software looks deeper into the "tie."
>
> So, keeping in mind that neither John Kemeny nor I have officially
> stated how ties (in the sequence sums) are to be handled, both methods
> are mathematically equivalent.
So it seems the situation is different than I thought. Instead of the
method not being the same as Kemeny, the case is more that the software
doesn't implement the method, but rather something that approximates
(and differs from) it.
As I've said before, I consider a method to be algorithm-agnostic.
Schulze implemented by the beatpath mechanism is the same method as
Schulze implemented by the cloneproof Schwartz dropping mechanism.
Furthermore, I think that a method is a function that takes an election
as its input and then provides either a winner set or a ranking (order
of finish).
If a method uses some kind of auxiliary input parameter, then the method
with one value of that auxiliary input parameter is not the same as the
method with another value of that parameter, unless it happens to be
inconsequential for the outcome. E.g. STV with a Droop quota is not the
same method as STV with the Hare method.
A software implementation is "of the method" or "implements the method"
if it agrees with the method for every input that it returns an output for.
Since the VoteFair method definition is the same (or equivalent) to the
Kemeny-Young method definition, the methods are the same. But the
software doesn't implement that method[1]. Instead, it implements a
family of approximations determined by the parameter. Each approximation
agrees with the full method if the number of candidates is below a
certain number, and returns undefined results above this number.
But the software doesn't give any impression that this is what it does.
Instead, from the documentation, one would get the impression that it
implements *the* Kemeny method (for any number of candidates). E.g. from
the VoteFair::VoteFairRanking Perl module documentation:
> This module calculates VoteFair Ranking results. The portions of
> VoteFair Ranking implemented here are:
>
> - VoteFair popularity ranking. This voting method calculates the full
> popularity ranking of all candidates (or choices in the case of a
> survey) from most popular and second-most popular down to least
> popular. It uses the preference information collected on 1-2-3
> ballots (or any equivalent way of expressing "ranked" preferences).
> When a single position is being filled, the most popular candidate is
> declared the winner. This calculation method is mathematically
> equivalent to the Condorcet-Kemeny election method.
and further,
> VoteFair popularity ranking is described in Wikipedia, and is
> mathematically equivalent to the Condorcet-Kemeny method. The following
> comments explain the algorithm used here, which quickly calculates the
> ranking results. This explanation is important because some academic
> sources claim that the computations cannot be done quickly if there is a
> large number of choices being ranked.
> Calculation time:
>
> The full algorithm used to calculate VoteFair popularity ranking
> results has a calculation time that is less than or equal to the
> following polynomial function:
>
> T = A + ( B * N ) + ( C * ( N * N ) )
>
> where T is the calculation time, N is the number of choices, and A
> and B and C are constants. (In mathematical notation, N * N would be
> written as N squared.) This function includes the calculation time
> required for the Choice-Specific Pairwise-Score (CSPS) pre-sort
> calculations.
>
> This time contrasts with the slow execution times of the "NP-hard"
> approach, in which every sequence score is calculated in order to find
> the sequence with the highest score. If every sequence score were
> calculated (from scratch), the calculation time would be proportional to:
>
> N! * N * N
>
> where N is the number of choices, N! is N factorial (2 * 3 * 4 * ...
> * N), and N * N equals N squared. Note that N factorial equals the number
> of possible sequences, and N squared times one-half approximately equals
> the number of pairwise counts that are added to calculate each sequence
> score.
>
> This clarification about calculation time is included because there
> is an academically common -- yet mistaken -- belief that calculating the
> "Condorcet-Kemeny method" is "NP-hard" and cannot be calculated in a
> time that is proportional to a polynomial function of N (the number of
> choices).
This description gives the impression that the software calculates the
VoteFair ranking (period, i.e. no approximations), that it does so in
polynomial time, and that it is possible to determine the Kemeny-Young
winner in polynomial time. But what it does is calculate an
approximation, which is how it can manage to do so in polytime without
proving P=NP.
Similarly, in the VoteFair C++ README.txt file:
> // * VoteFair popularity ranking. This voting method calculates the
> // full popularity ranking of all candidates (or choices in the case
> // of a survey) from most popular and second-most popular down to
> // least popular. It uses the preference information collected on
> // 1-2-3 ballots (or any equivalent way of expressing "ranked"
> // preferences). When a single position is being filled, the most
> // popular candidate is declared the winner. This calculation method
> // is mathematically equivalent to the Condorcet-Kemeny election
> // method.
which gives the impression that again, the software calculates the
method (although at least it doesn't mention being able to circumvent
NP-hardness :-).
Now, if I'm generous, I could say that what I understand you to be
saying is that when you say "this voting method calculates...", you're
talking about the software, but when you're saying "this calculation
method is mathematically equivalent...", you're talking about the
method. But it's easy to draw the wrong conclusion, as I did earlier.
The documentation could thus use being more clear about what the
software implements -- or the software could be rewritten so that it
implements the actual VoteFair (or Kemeny) method.
And again, I would suggest the latter as a good strategy. Instead of
producing correct results up to a certain number of candidates and then
producing undefined results - that it produces the correct results in
potentially exponential time, and that it just quits with a timeout if
it takes too long a time.
That way, it's immediately obvious to the user whether the method
produces a correct result (namely, that it'd do so when it does produce
a result at all). Instead of producing a result in managable time with
some probability (which you argue is low) of producing something
incorrect, it produces a result in managable time with similar (high if
you're right) probability of not getting a timeout.
In addition, if you use a reasonably good integer programming solver to
do so, you can quickly solve cases that the current software can't, e.g.
1000 candidates but no cycles at all.
[1] Strictly speaking, it implements a generalization of that method,
but I don't want to make things more confusing than they need to be; I'd
rather deal with one point at a time.
V
VoteFair
Sun, Mar 8, 2020 1:23 AM
On 2/25/2020 3:17 PM, Kristofer Munsterhjelm wrote:
So it seems the situation is different than I thought. Instead of the
method not being the same as Kemeny, the case is more that the software
doesn't implement the method, but rather something that approximates
(and differs from) it.
...
... the software doesn't give any impression that this is what it does.
Instead, from the documentation, one would get the impression that it
implements the Kemeny method (for any number of candidates). ...
...
The documentation could thus use being more clear about what the
software implements -- or the software could be rewritten so that it
implements the actual VoteFair (or Kemeny) method.
I agree that the software deserves better documentation, so I have added
the following clarification to the VoteFair ranking software (both in
README.txt and votefair_ranking.cpp).
// Clarification: For reasons of computation time, there are some
// very rare cases for which this software can produce results that
// differ from full VoteFair popularity ranking results.
// These exceptions involve more choices (candidates) than the
// value of the constant named "global_check_all_scores_choice_limit",
// which currently has a default value of 6.
// In those rare cases, the software estimates which top (6) choices
// are the most popular, and then does the full VoteFair popularity
// ranking to determine which of those top choices is most popular.
// The rare cases in which the estimation method produces different
// results involve one or more rock-paper-scissors-like cycles
// that include the top choices, which is a rare combination.
// As an analogy, those cases are like finding the highest
// sand dune in a desert, whereas most cases are like finding
// the highest mountain peak in a mountain range.
// As the number of ballots increases (such as beyond 50 ballots),
// the likelihood of such cycles greatly decreases.
// If this difference is important, the value of the constant
// "global_check_all_scores_choice_limit" can be increased, but
// that change will dramatically increase calculation time,
// to the point of requiring years of computation time for values
// even as small as 20. Therefore, values larger than 12 are not
// recommended.
Kristofer, thank you for taking the time to understand VoteFair Ranking
and the VoteFair ranking software, and for calling attention to this
need for better software documentation.
Richard Fobes
On 2/25/2020 3:17 PM, Kristofer Munsterhjelm wrote:
I hope this reply isn't too late, so here we go:
On 23/01/2020 18.53, VoteFair wrote:
On 1/22/2020 3:49 PM, Kristofer Munsterhjelm wrote:
Given this definition, there are two possibilities. Either the VoteFair
software implements the VoteFair method, or it does not. ...
If the default settings are used, and if the number of candidates is no
more than the check-all-sequence-scores setting (which I think is 6),
then the software implements the VoteFair popularity ranking method,
which yields the same results as the Condorcet-Kemeny method.
In other words you are not allowing for a third possibility, which -- of
course -- depends on the number of candidates.
... It seems that you instead are saying that, as you
define the VoteFair ranking, it does agree with Kemeny all the time, but
the software doesn't.
Yes, this is the third possibility. The software CAN always yield the
same results -- simply by limiting the number of candidates it can
handle (or, up to a limit based on computing power, increasing the
number of candidates checked by the full/slow method).
Could you give me a definition of the VoteFair method itself? Without
knowing what bit is the software and what bit is the method, it's
difficult to get further. For instance, it would be hard to know whether
the results that the VoteFair software gives when Kemeny orderings are
tied is a property of the method or of the software, because the
definition of the Kemeny method itself doesn't say what should happen in
such a case.
Originally I wrote the definition of VoteFair popularity ranking (which
at that time I called VoteFair ranking) on Wikipedia, and Markus Schulze
re-named the article to the "Kemeny-Young method" claiming that the two
methods are the same. So the definition there matches VoteFair
popularity ranking because I wrote it.
Alright, that enabled me to track down the original definition by
looking at the Wikipedia history archive. I've quoted it below.
VoteFair ranking shall be done using software (such as accessible at
www.VoteFair.org) that performs the following calculations. The
preferences indicated in the ballots are counted to produce a tally
table in which all the possible pairs of candidates are listed, one
number for each pair indicates the number of voters who prefer one
candidate in the pair over the other candidate in the pair, another
number for each pair indicates the number of voters who have the
opposite preference for these two candidates, and a third number for
each pair indicates the number of voters who express no preference
between the two candidates. Using a computer, each possible sequence of
candidates is considered, where a sequence consists of one of the
candidates being regarded as the most popular candidate, another
candidate being regarded as the second-most popular candidate, and so
on. For each such sequence the numbers in the tally table that apply to
that sequence are added together to produce a sequence score for this
sequence. The sequence that has the highest sequence score indicates the
overall order of preference for the candidates. If there is more than
one sequence that has the same highest score, the sequences with this
score shall be analyzed to identify one or more ties at one or more
preference levels.
I agree that the definition above describes the Kemeny-Young method. I'd
even say it's the same (not just mathematically equivalent) even though
the mechanics are different:
There exist implementations of Kemeny-Young that don't rely on
enumerating all combinations and then choosing the best one. For
instance, integer programming implementations scale much better while
producing the optimal result. If the implementation mattered as to
whether one method is the same as another, then these implementations
would not be of the Kemeny-Young method because they don't use
exhaustive enumerations. But they are generally considered to be.
Yes, the issue of how to handle Condorcet-cycle ties is not stated by
John Kemeny (as far as I know), and I have not explicitly stated how
such ties are handled in VoteFair popularity ranking. If I did make such
a statement then you or others might argue that the two methods are not
the same.
The software does attempt to handle ties, either to use a tie-breaking
criteria or to declare an official tie. In the latter case, the VoteFair
approach presumably matches the Kemeny approach. In the former case the
candidates in the cycle can be re-sequenced and the sequence sums yield
the same highest sum, yet SOME of those "tied" sequences can yield
different sums. If this seems complex it's because it IS complex. It
took lots of work to get the software to handle these and other "edge"
cases. This approach is unlike what many software developers do, which
is to dismiss edge cases with some kind of error message. In other
words, my software looks deeper into the "tie."
So, keeping in mind that neither John Kemeny nor I have officially
stated how ties (in the sequence sums) are to be handled, both methods
are mathematically equivalent.
So it seems the situation is different than I thought. Instead of the
method not being the same as Kemeny, the case is more that the software
doesn't implement the method, but rather something that approximates
(and differs from) it.
As I've said before, I consider a method to be algorithm-agnostic.
Schulze implemented by the beatpath mechanism is the same method as
Schulze implemented by the cloneproof Schwartz dropping mechanism.
Furthermore, I think that a method is a function that takes an election
as its input and then provides either a winner set or a ranking (order
of finish).
If a method uses some kind of auxiliary input parameter, then the method
with one value of that auxiliary input parameter is not the same as the
method with another value of that parameter, unless it happens to be
inconsequential for the outcome. E.g. STV with a Droop quota is not the
same method as STV with the Hare method.
A software implementation is "of the method" or "implements the method"
if it agrees with the method for every input that it returns an output for.
Since the VoteFair method definition is the same (or equivalent) to the
Kemeny-Young method definition, the methods are the same. But the
software doesn't implement that method[1]. Instead, it implements a
family of approximations determined by the parameter. Each approximation
agrees with the full method if the number of candidates is below a
certain number, and returns undefined results above this number.
But the software doesn't give any impression that this is what it does.
Instead, from the documentation, one would get the impression that it
implements the Kemeny method (for any number of candidates). E.g. from
the VoteFair::VoteFairRanking Perl module documentation:
This module calculates VoteFair Ranking results. The portions of
VoteFair Ranking implemented here are:
- VoteFair popularity ranking. This voting method calculates the full
popularity ranking of all candidates (or choices in the case of a
survey) from most popular and second-most popular down to least
popular. It uses the preference information collected on 1-2-3
ballots (or any equivalent way of expressing "ranked" preferences).
When a single position is being filled, the most popular candidate is
declared the winner. This calculation method is mathematically
equivalent to the Condorcet-Kemeny election method.
VoteFair popularity ranking is described in Wikipedia, and is
mathematically equivalent to the Condorcet-Kemeny method. The following
comments explain the algorithm used here, which quickly calculates the
ranking results. This explanation is important because some academic
sources claim that the computations cannot be done quickly if there is a
large number of choices being ranked.
Calculation time:
The full algorithm used to calculate VoteFair popularity ranking
results has a calculation time that is less than or equal to the
following polynomial function:
T = A + ( B * N ) + ( C * ( N * N ) )
where T is the calculation time, N is the number of choices, and A
and B and C are constants. (In mathematical notation, N * N would be
written as N squared.) This function includes the calculation time
required for the Choice-Specific Pairwise-Score (CSPS) pre-sort
calculations.
This time contrasts with the slow execution times of the "NP-hard"
approach, in which every sequence score is calculated in order to find
the sequence with the highest score. If every sequence score were
calculated (from scratch), the calculation time would be proportional to:
N! * N * N
where N is the number of choices, N! is N factorial (2 * 3 * 4 * ...
- N), and N * N equals N squared. Note that N factorial equals the number
of possible sequences, and N squared times one-half approximately equals
the number of pairwise counts that are added to calculate each sequence
score.
This clarification about calculation time is included because there
is an academically common -- yet mistaken -- belief that calculating the
"Condorcet-Kemeny method" is "NP-hard" and cannot be calculated in a
time that is proportional to a polynomial function of N (the number of
choices).
This description gives the impression that the software calculates the
VoteFair ranking (period, i.e. no approximations), that it does so in
polynomial time, and that it is possible to determine the Kemeny-Young
winner in polynomial time. But what it does is calculate an
approximation, which is how it can manage to do so in polytime without
proving P=NP.
Similarly, in the VoteFair C++ README.txt file:
// * VoteFair popularity ranking. This voting method calculates the
// full popularity ranking of all candidates (or choices in the case
// of a survey) from most popular and second-most popular down to
// least popular. It uses the preference information collected on
// 1-2-3 ballots (or any equivalent way of expressing "ranked"
// preferences). When a single position is being filled, the most
// popular candidate is declared the winner. This calculation method
// is mathematically equivalent to the Condorcet-Kemeny election
// method.
which gives the impression that again, the software calculates the
method (although at least it doesn't mention being able to circumvent
NP-hardness :-).
Now, if I'm generous, I could say that what I understand you to be
saying is that when you say "this voting method calculates...", you're
talking about the software, but when you're saying "this calculation
method is mathematically equivalent...", you're talking about the
method. But it's easy to draw the wrong conclusion, as I did earlier.
The documentation could thus use being more clear about what the
software implements -- or the software could be rewritten so that it
implements the actual VoteFair (or Kemeny) method.
And again, I would suggest the latter as a good strategy. Instead of
producing correct results up to a certain number of candidates and then
producing undefined results - that it produces the correct results in
potentially exponential time, and that it just quits with a timeout if
it takes too long a time.
That way, it's immediately obvious to the user whether the method
produces a correct result (namely, that it'd do so when it does produce
a result at all). Instead of producing a result in managable time with
some probability (which you argue is low) of producing something
incorrect, it produces a result in managable time with similar (high if
you're right) probability of not getting a timeout.
In addition, if you use a reasonably good integer programming solver to
do so, you can quickly solve cases that the current software can't, e.g.
1000 candidates but no cycles at all.
[1] Strictly speaking, it implements a generalization of that method,
but I don't want to make things more confusing than they need to be; I'd
rather deal with one point at a time.
On 2/25/2020 3:17 PM, Kristofer Munsterhjelm wrote:
> So it seems the situation is different than I thought. Instead of the
> method not being the same as Kemeny, the case is more that the software
> doesn't implement the method, but rather something that approximates
> (and differs from) it.
> ...
> ... the software doesn't give any impression that this is what it does.
> Instead, from the documentation, one would get the impression that it
> implements *the* Kemeny method (for any number of candidates). ...
> ...
> The documentation could thus use being more clear about what the
> software implements -- or the software could be rewritten so that it
> implements the actual VoteFair (or Kemeny) method.
I agree that the software deserves better documentation, so I have added
the following clarification to the VoteFair ranking software (both in
README.txt and votefair_ranking.cpp).
// Clarification: For reasons of computation time, there are some
// very rare cases for which this software can produce results that
// differ from full VoteFair popularity ranking results.
// These exceptions involve more choices (candidates) than the
// value of the constant named "global_check_all_scores_choice_limit",
// which currently has a default value of 6.
// In those rare cases, the software estimates which top (6) choices
// are the most popular, and then does the full VoteFair popularity
// ranking to determine which of those top choices is most popular.
// The rare cases in which the estimation method produces different
// results involve one or more rock-paper-scissors-like cycles
// that include the top choices, which is a rare combination.
// As an analogy, those cases are like finding the highest
// sand dune in a desert, whereas most cases are like finding
// the highest mountain peak in a mountain range.
// As the number of ballots increases (such as beyond 50 ballots),
// the likelihood of such cycles greatly decreases.
// If this difference is important, the value of the constant
// "global_check_all_scores_choice_limit" can be increased, but
// that change will dramatically increase calculation time,
// to the point of requiring years of computation time for values
// even as small as 20. Therefore, values larger than 12 are not
// recommended.
Kristofer, thank you for taking the time to understand VoteFair Ranking
and the VoteFair ranking software, and for calling attention to this
need for better software documentation.
Richard Fobes
On 2/25/2020 3:17 PM, Kristofer Munsterhjelm wrote:
> I hope this reply isn't too late, so here we go:
>
> On 23/01/2020 18.53, VoteFair wrote:
>> On 1/22/2020 3:49 PM, Kristofer Munsterhjelm wrote:
>>> Given this definition, there are two possibilities. Either the VoteFair
>>> software implements the VoteFair method, or it does not. ...
>>
>> If the default settings are used, and if the number of candidates is no
>> more than the check-all-sequence-scores setting (which I think is 6),
>> then the software implements the VoteFair popularity ranking method,
>> which yields the same results as the Condorcet-Kemeny method.
>>
>> In other words you are not allowing for a third possibility, which -- of
>> course -- depends on the number of candidates.
>>
>>> ... It seems that you instead are saying that, as you
>>> define the VoteFair ranking, it does agree with Kemeny all the time, but
>>> the software doesn't.
>>
>> Yes, this is the third possibility. The software CAN always yield the
>> same results -- simply by limiting the number of candidates it can
>> handle (or, up to a limit based on computing power, increasing the
>> number of candidates checked by the full/slow method).
>>
>>> Could you give me a definition of the VoteFair method itself? Without
>>> knowing what bit is the software and what bit is the method, it's
>>> difficult to get further. For instance, it would be hard to know whether
>>> the results that the VoteFair software gives when Kemeny orderings are
>>> tied is a property of the method or of the software, because the
>>> definition of the Kemeny method itself doesn't say what should happen in
>>> such a case.
>>
>> Originally I wrote the definition of VoteFair popularity ranking (which
>> at that time I called VoteFair ranking) on Wikipedia, and Markus Schulze
>> re-named the article to the "Kemeny-Young method" claiming that the two
>> methods are the same. So the definition there matches VoteFair
>> popularity ranking because I wrote it.
>
> Alright, that enabled me to track down the original definition by
> looking at the Wikipedia history archive. I've quoted it below.
>
>> VoteFair ranking shall be done using software (such as accessible at
>> www.VoteFair.org) that performs the following calculations. The
>> preferences indicated in the ballots are counted to produce a tally
>> table in which all the possible pairs of candidates are listed, one
>> number for each pair indicates the number of voters who prefer one
>> candidate in the pair over the other candidate in the pair, another
>> number for each pair indicates the number of voters who have the
>> opposite preference for these two candidates, and a third number for
>> each pair indicates the number of voters who express no preference
>> between the two candidates. Using a computer, each possible sequence of
>> candidates is considered, where a sequence consists of one of the
>> candidates being regarded as the most popular candidate, another
>> candidate being regarded as the second-most popular candidate, and so
>> on. For each such sequence the numbers in the tally table that apply to
>> that sequence are added together to produce a sequence score for this
>> sequence. The sequence that has the highest sequence score indicates the
>> overall order of preference for the candidates. If there is more than
>> one sequence that has the same highest score, the sequences with this
>> score shall be analyzed to identify one or more ties at one or more
>> preference levels.
>
> I agree that the definition above describes the Kemeny-Young method. I'd
> even say it's the same (not just mathematically equivalent) even though
> the mechanics are different:
>
> There exist implementations of Kemeny-Young that don't rely on
> enumerating all combinations and then choosing the best one. For
> instance, integer programming implementations scale much better while
> producing the optimal result. If the implementation mattered as to
> whether one method is the same as another, then these implementations
> would not be of the Kemeny-Young method because they don't use
> exhaustive enumerations. But they are generally considered to be.
>
>> Yes, the issue of how to handle Condorcet-cycle ties is not stated by
>> John Kemeny (as far as I know), and I have not explicitly stated how
>> such ties are handled in VoteFair popularity ranking. If I did make such
>> a statement then you or others might argue that the two methods are not
>> the same.
>>
>> The software does attempt to handle ties, either to use a tie-breaking
>> criteria or to declare an official tie. In the latter case, the VoteFair
>> approach presumably matches the Kemeny approach. In the former case the
>> candidates in the cycle can be re-sequenced and the sequence sums yield
>> the same highest sum, yet SOME of those "tied" sequences can yield
>> different sums. If this seems complex it's because it IS complex. It
>> took lots of work to get the software to handle these and other "edge"
>> cases. This approach is unlike what many software developers do, which
>> is to dismiss edge cases with some kind of error message. In other
>> words, my software looks deeper into the "tie."
>>
>> So, keeping in mind that neither John Kemeny nor I have officially
>> stated how ties (in the sequence sums) are to be handled, both methods
>> are mathematically equivalent.
>
> So it seems the situation is different than I thought. Instead of the
> method not being the same as Kemeny, the case is more that the software
> doesn't implement the method, but rather something that approximates
> (and differs from) it.
>
> As I've said before, I consider a method to be algorithm-agnostic.
> Schulze implemented by the beatpath mechanism is the same method as
> Schulze implemented by the cloneproof Schwartz dropping mechanism.
> Furthermore, I think that a method is a function that takes an election
> as its input and then provides either a winner set or a ranking (order
> of finish).
>
> If a method uses some kind of auxiliary input parameter, then the method
> with one value of that auxiliary input parameter is not the same as the
> method with another value of that parameter, unless it happens to be
> inconsequential for the outcome. E.g. STV with a Droop quota is not the
> same method as STV with the Hare method.
>
> A software implementation is "of the method" or "implements the method"
> if it agrees with the method for every input that it returns an output for.
>
> Since the VoteFair method definition is the same (or equivalent) to the
> Kemeny-Young method definition, the methods are the same. But the
> software doesn't implement that method[1]. Instead, it implements a
> family of approximations determined by the parameter. Each approximation
> agrees with the full method if the number of candidates is below a
> certain number, and returns undefined results above this number.
>
> But the software doesn't give any impression that this is what it does.
> Instead, from the documentation, one would get the impression that it
> implements *the* Kemeny method (for any number of candidates). E.g. from
> the VoteFair::VoteFairRanking Perl module documentation:
>
>> This module calculates VoteFair Ranking results. The portions of
>> VoteFair Ranking implemented here are:
>>
>> - VoteFair popularity ranking. This voting method calculates the full
>> popularity ranking of all candidates (or choices in the case of a
>> survey) from most popular and second-most popular down to least
>> popular. It uses the preference information collected on 1-2-3
>> ballots (or any equivalent way of expressing "ranked" preferences).
>> When a single position is being filled, the most popular candidate is
>> declared the winner. This calculation method is mathematically
>> equivalent to the Condorcet-Kemeny election method.
>
> and further,
>
>> VoteFair popularity ranking is described in Wikipedia, and is
>> mathematically equivalent to the Condorcet-Kemeny method. The following
>> comments explain the algorithm used here, which quickly calculates the
>> ranking results. This explanation is important because some academic
>> sources claim that the computations cannot be done quickly if there is a
>> large number of choices being ranked.
>
>> Calculation time:
>>
>> The full algorithm used to calculate VoteFair popularity ranking
>> results has a calculation time that is less than or equal to the
>> following polynomial function:
>>
>> T = A + ( B * N ) + ( C * ( N * N ) )
>>
>> where T is the calculation time, N is the number of choices, and A
>> and B and C are constants. (In mathematical notation, N * N would be
>> written as N squared.) This function includes the calculation time
>> required for the Choice-Specific Pairwise-Score (CSPS) pre-sort
>> calculations.
>>
>> This time contrasts with the slow execution times of the "NP-hard"
>> approach, in which every sequence score is calculated in order to find
>> the sequence with the highest score. If every sequence score were
>> calculated (from scratch), the calculation time would be proportional to:
>>
>> N! * N * N
>>
>> where N is the number of choices, N! is N factorial (2 * 3 * 4 * ...
>> * N), and N * N equals N squared. Note that N factorial equals the number
>> of possible sequences, and N squared times one-half approximately equals
>> the number of pairwise counts that are added to calculate each sequence
>> score.
>>
>> This clarification about calculation time is included because there
>> is an academically common -- yet mistaken -- belief that calculating the
>> "Condorcet-Kemeny method" is "NP-hard" and cannot be calculated in a
>> time that is proportional to a polynomial function of N (the number of
>> choices).
>
> This description gives the impression that the software calculates the
> VoteFair ranking (period, i.e. no approximations), that it does so in
> polynomial time, and that it is possible to determine the Kemeny-Young
> winner in polynomial time. But what it does is calculate an
> approximation, which is how it can manage to do so in polytime without
> proving P=NP.
>
> Similarly, in the VoteFair C++ README.txt file:
>
>> // * VoteFair popularity ranking. This voting method calculates the
>> // full popularity ranking of all candidates (or choices in the case
>> // of a survey) from most popular and second-most popular down to
>> // least popular. It uses the preference information collected on
>> // 1-2-3 ballots (or any equivalent way of expressing "ranked"
>> // preferences). When a single position is being filled, the most
>> // popular candidate is declared the winner. This calculation method
>> // is mathematically equivalent to the Condorcet-Kemeny election
>> // method.
>
> which gives the impression that again, the software calculates the
> method (although at least it doesn't mention being able to circumvent
> NP-hardness :-).
>
> Now, if I'm generous, I could say that what I understand you to be
> saying is that when you say "this voting method calculates...", you're
> talking about the software, but when you're saying "this calculation
> method is mathematically equivalent...", you're talking about the
> method. But it's easy to draw the wrong conclusion, as I did earlier.
> The documentation could thus use being more clear about what the
> software implements -- or the software could be rewritten so that it
> implements the actual VoteFair (or Kemeny) method.
>
> And again, I would suggest the latter as a good strategy. Instead of
> producing correct results up to a certain number of candidates and then
> producing undefined results - that it produces the correct results in
> potentially exponential time, and that it just quits with a timeout if
> it takes too long a time.
>
> That way, it's immediately obvious to the user whether the method
> produces a correct result (namely, that it'd do so when it does produce
> a result at all). Instead of producing a result in managable time with
> some probability (which you argue is low) of producing something
> incorrect, it produces a result in managable time with similar (high if
> you're right) probability of not getting a timeout.
>
> In addition, if you use a reasonably good integer programming solver to
> do so, you can quickly solve cases that the current software can't, e.g.
> 1000 candidates but no cycles at all.
>
> [1] Strictly speaking, it implements a generalization of that method,
> but I don't want to make things more confusing than they need to be; I'd
> rather deal with one point at a time.
>
