[EM] Kemeny's Rule/Condorcet's Method

[Forest Simmons]

Adam's response is precisely correct and well written.

I would add only this:

Determining the Kemeny order from ranked preference ballots suffers the
"combinatorial explosion" because there is no way of getting around one by
one testing of most of the N! permutations of candidates in order to see
which of these permutations minimizes the average distance to the ballot
orders.

Distance is measured by the number of "neighbor swaps" required to convert
one order into another.

So the Kemeny order is computationally intractable for large number of
candidates.  In other words, it's the large number of candidates, rather
than the large number of voters, that makes the Kemeny order prohibitively
difficult.




On Thu, 19 Dec 2002, Adam Tarr wrote:

>
> >What's that you say?: "this minimization is an NP complete problem." No
> >capisci.
>
> Some problems can be done in "polynomial time".  This means that if the
> size of the problem (number of voters, or candidates, in our case) is N,
> then the amount of steps you need to solve the problem is some polynomial
> of N, say twenty plus six times N cubed.  For a problem of this type
> (called "P-type problems") a computer can usually crunch out an answer
> pretty fast.
>
> Other problems take an exponential amount of time, say 3^N.  For large
> enough N, a computer might solve a P-type problem in minutes, while an
> exponential problem might take decades or more.  The problems just explode
> for large values of N.
>
> "NP-type" problems are problems that can be VERIFIED in polynomial time:
> that is, if you have a guess at the answer, you can check it in polynomial
> time.  Obviously, any P-type problem is also an NP-type problem.
>
> "NP-complete" is one type of NP problem.  Every NP-complete problem can be
> converted to another NP-complete problem, so if you can solve one you can
> solve any of them.  The NP-complete problems have no known polynomial-time
> solution, so right now they're in the exponential category.  There is a
> standing one million dollar prize to either find a polynomial time solution
> for NP-complete problems, or prove that none exists.
>
> >Let me ask again, is there any freeware available which will do
> >Kemeny Rule tallies?
>
> Assuming I understand Forest right, if you come up with a program that
> works for decent-sized elections, that's one million dollars for you!
>
> -Adam
>
>
> ----
> For more information about this list (subscribe, unsubscribe, FAQ, etc),
> please see http://www.eskimo.com/~robla/em
>
>

----
For more information about this list (subscribe, unsubscribe, FAQ, etc), 
please see http://www.eskimo.com/~robla/em