[EM] Proportional Condorcet Voting

[Paul Kislanko]

>From a theoretical standpoint, this may look intractactable, but for any
finite N,K the problem is solvable in polynomial time in a manner that
depends only upon N, K, and the number of voters. From a practical
standpoint, the calculation is not difficult for up to N,K=293 by
demonstation (I do that daily in my report of records vs common opponents
for division 1 american college baseball teams on a Dell laptop. It takes a
few minutes to run only because it is also producing 294 web pages, and all
that I/O slows it down).


  _____  

From: election-methods-bounces at electorama.com
[mailto:election-methods-bounces at electorama.com] On Behalf Of Simmons,
Forest
Sent: Monday, May 01, 2006 2:29 PM
To: election-methods at electorama.com
Subject: Re: [EM] Proportional Condorcet Voting


Antonio Oneala lamented that proportional Condorcet methods tend to be
intractable.  This is because if there are N candidates from which to choose
K winners, there are  C(N,K)=N!/(K!*(N-K)!) subsets to be compared pairwise,
for a total of  C(C(N,K),2) pairwise comparisons of subsets.
 
However, suppose that instead of comparing all C(N,K) of the K candidate
subsets, we just compare all submitted proposals, including those sets that
would be elected by STV under various rules (Droop Quota, etc.).  There
might be ten thousand such proposals. But that would only require  C(10000,
2) = 49995000 comparisons, a few seconds of CPU time on a second rate
computer.
 
Forest

-------------- next part --------------
A non-text attachment was scrubbed...
Name: winmail.dat
Type: application/ms-tnef
Size: 3554 bytes
Desc: not available
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20060501/023ea286/attachment-0003.bin>