[EM] Fast Condorcet-Kemeny calculation times, clarification of NP-hardness issue
Finally, after reading the articles cited by Warren Smith (listed at the bottom of this reply) plus some related articles, I can reply to his insistence that Condorcet-Kemeny calculations take too long to calculate. Also, this reply addresses the same claim that appears in Wikipedia both in the Kemeny-Young method article and in the comparison table within the Wikipedia Voting systems article (in the polynomial time column that Markus Schulze added). One source of confusion is that Warren, and perhaps others, regard the Condorcet-Kemeny problem as a decision problem that only has a yes or no answer. This view is suggested by Warren's reference (below and in other messages) to the problem as being NP-complete, which only applies to decision problems. Although it is possible to formulate a decision problem based on one or more specified characteristics of the Condorcet-Kemeny method, that is a different problem than the Condorcet-Kemeny problem. In the real world of elections, the Condorcet-Kemeny problem is to calculate a ranking of all choices (e.g. candidates) that maximizes the sequence score (or minimizes the Kemeny score). Clearly the Condorcet-Kemeny problem is an optimization problem, not a decision problem (and not a search problem). It is an optimization problem because we have a way to measure how closely the solution reaches its goal. (For contrast, consider the NP-hard subset sum problem in which the goal is to determine whether a specified list of integers contains a subset that can be added and/or subtracted to yield zero. Any subset either sums to zero or it doesn't sum to zero. This makes it easy to formulate the related decision (yes/no) problem that asks whether such a subset exists for a given set of numbers.) Because the Condorcet-Kemeny problem is an optimization problem, the solution to the Condorcet-Kemeny problem can be an approximation. If this approach is used, it becomes relevant to ask how closely the approximation reaches the ranking that has the highest sequence score. Yet even this question -- of how close? -- is not a decision problem (because it goes beyond a yes or no answer). Keeping in mind that VoteFair popularity ranking calculations are mathematically equivalent to the Condorcet-Kemeny method, my claim is that VoteFair popularity ranking calculations yield, at the least, the same top-ranked choice, and the same few top-ranked choices, as the solution produced by examining every sequence score -- except (and this is the important part) in cases where the voter preferences are so convoluted that any top-ranked choice and any few top-ranked choices would be controversial. As one academic paper elegantly put it: garbage in, garbage out. More specifically, here is a set of claims that more rigorously state the above ambiguous claim. Claim 1: For _some_ _instances_, a polynomial-time calculation can identify the full ranking that produces the highest Condorcet-Kemeny sequence score. Claim 2: For _some_ _instances_, a polynomial-time calculation can rank the top most-popular candidates/choices and this partial ranking will be the same as the top portion of the full ranking as determined by identifying the highest Condorcet-Kemeny sequence score. Claim 3: For the _remaining_ _instances_ (not covered in Claims 1 and 2), an approximation of the full Condorcet-Kemeny ranking can be calculated in polynomial time. Claim 4: For any cases in which the top-ranked candidate/choice according to the VoteFair popularity ranking algorithm differs from the top-ranked candidate/choice according to a full calculation of all sequence scores, the outcome of a runoff election between the two candidates/choices would be difficult to predict. As done in the academic literature, I am excluding the cases in which more than one sequence has the same highest sequence score. To help clarify the validity of these claims, I'll use an analogy. Consider a special case of the rigorously studied Traveling Salesman Problem (TSP), which is NP-hard to solve. (The TSP also can be expressed as a decision problem, in which case the decision problem is NP-complete, but that variation is not the problem discussed here.) The special case -- which I will refer to as the non-returning Traveling Salesman Problem -- is that we want to know which city the salesman visits first, and we want to know, with successively less interest, which city the salesman visits second, third, and so on. Additionally, for this special case, we specify that the cities to be visited are roughly located between a beginning point B and and ending point E. To make this special case mathematically equivalent to the normal Traveling Salesman Problem in which the salesman returns to the starting city, we create a path of closely spaced cities (labeled + below) that lead back to the starting city B. Here is a diagram of this problem. Remember
Re: [EM] Fast Condorcet-Kemeny calculation times, clarification of NP-hardness issue
On Sun, Mar 4, 2012 at 3:44 PM, Richard Fobes electionmeth...@votefair.org wrote: Finally, after reading the articles cited by Warren Smith (listed at the bottom of this reply) plus some related articles, I can reply to his insistence that Condorcet-Kemeny calculations take too long to calculate. Also, this reply addresses the same claim that appears in Wikipedia both in the Kemeny-Young method article and in the comparison table within the Wikipedia Voting systems article (in the polynomial time column that Markus Schulze added). One source of confusion is that Warren, and perhaps others, regard the Condorcet-Kemeny problem as a decision problem that only has a yes or no answer. This view is suggested by Warren's reference (below and in other messages) to the problem as being NP-complete, which only applies to decision problems. Although it is possible to formulate a decision problem based on one or more specified characteristics of the Condorcet-Kemeny method, that is a different problem than the Condorcet-Kemeny problem. --the optimization problem is at least as hard as the decision problem.You are erroneously creating the impression I somehow was unaware of this, or that you somehow have here got some new insight. Neither is true. In the real world of elections, the Condorcet-Kemeny problem is to calculate a ranking of all choices (e.g. candidates) that maximizes the sequence score (or minimizes the Kemeny score). Clearly the Condorcet-Kemeny problem is an optimization problem, not a decision problem (and not a search problem). It is an optimization problem because we have a way to measure how closely the solution reaches its goal. (For contrast, consider the NP-hard subset sum problem in which the goal is to determine whether a specified list of integers contains a subset that can be added and/or subtracted to yield zero. Any subset either sums to zero or it doesn't sum to zero. This makes it easy to formulate the related decision (yes/no) problem that asks whether such a subset exists for a given set of numbers.) Because the Condorcet-Kemeny problem is an optimization problem, the solution to the Condorcet-Kemeny problem can be an approximation. If this approach is used, it becomes relevant to ask how closely the approximation reaches the ranking that has the highest sequence score. Yet even this question -- of how close? -- is not a decision problem (because it goes beyond a yes or no answer). Keeping in mind that VoteFair popularity ranking calculations are mathematically equivalent to the Condorcet-Kemeny method, my claim is that VoteFair popularity ranking calculations yield, at the least, the same top-ranked choice, and the same few top-ranked choices, as the solution produced by examining every sequence score -- except (and this is the important part) in cases where the voter preferences are so convoluted that any top-ranked choice and any few top-ranked choices would be controversial. As one academic paper elegantly put it: garbage in, garbage out. More specifically, here is a set of claims that more rigorously state the above ambiguous claim. Claim 1: For _some_ _instances_, a polynomial-time calculation can identify the full ranking that produces the highest Condorcet-Kemeny sequence score. --oh whoo-whee. Here's another claim: for SOME planets, I can readily find a million dollars in gold piled up right next to me. Claim 2: For _some_ _instances_, a polynomial-time calculation can rank the top most-popular candidates/choices and this partial ranking will be the same as the top portion of the full ranking as determined by identifying the highest Condorcet-Kemeny sequence score. Claim 3: For the _remaining_ _instances_ (not covered in Claims 1 and 2), an approximation of the full Condorcet-Kemeny ranking can be calculated in polynomial time. --what kind of approximation? I can find an approximation to a million dollars in gold, namely, 1 penny. Claim 4: For any cases in which the top-ranked candidate/choice according to the VoteFair popularity ranking algorithm differs from the top-ranked candidate/choice according to a full calculation of all sequence scores, the outcome of a runoff election between the two candidates/choices would be difficult to predict. As done in the academic literature, I am excluding the cases in which more than one sequence has the same highest sequence score. --I'm not sure what that meant, but it sounds like garbage too. To help clarify the validity of these claims, I'll use an analogy. Consider a special case of the rigorously studied Traveling Salesman Problem (TSP), which is NP-hard to solve. (The TSP also can be expressed as a decision problem, in which case the decision problem is NP-complete, but that variation is not the problem discussed here.) The special case -- which I will refer to as the non-returning Traveling Salesman Problem -- is that we want to
Re: [EM] Fast Condorcet-Kemeny calculation times, clarification of NP-hardness issue
On 3/4/12 5:44 PM, Warren Smith wrote: On Sun, Mar 4, 2012 at 3:44 PM, Richard Fobes electionmeth...@votefair.org wrote: Finally, after reading the articles cited by Warren Smith (listed at the bottom of this reply) plus some related articles, I can reply to his insistence that Condorcet-Kemeny calculations take too long to calculate. Also, this reply addresses the same claim that appears in Wikipedia both in the Kemeny-Young method article and in the comparison table within the Wikipedia Voting systems article (in the polynomial time column that Markus Schulze added). One source of confusion is that Warren, and perhaps others, regard the Condorcet-Kemeny problem as a decision problem that only has a yes or no answer. This view is suggested by Warren's reference (below and in other messages) to the problem as being NP-complete, which only applies to decision problems. Although it is possible to formulate a decision problem based on one or more specified characteristics of the Condorcet-Kemeny method, that is a different problem than the Condorcet-Kemeny problem. --the optimization problem is at least as hard as the decision problem.You are erroneously creating the impression I somehow was unaware of this, or that you somehow have here got some new insight. Neither is true. I might try to say all this in a more friendly way than Warren does, but he is 100% right about all the technical issues here. This is basic computer science. Nothing fancy and no judgment calls are involved. -- Andrew attachment: andru.vcf Election-Methods mailing list - see http://electorama.com/em for list info
