[EM] Idea Proposal: Listening Democracy

[Andrew Myers]

On 7/22/64 2:59 PM, Abd ul-Rahman Lomax wrote:
> However, I strongly urge people who attempt to analyze the situation
> and to propose reforms to:
>
> 1. Keep it simple. An extraordinarily powerful system for fully
> proportional representation consisting of a seemingly-simple tweak on
> Single Transferable Vote was proposed in 1883 or so by Charles
> Dodgson (Lewis Carroll). If a simple system that is*obviously*  far
> more democratic doesn't attract notice for more than a hundred years,
> what chance does something more complicated and dodgier (i.e.,
> involving lots of unknowns) have?
>    
This description is misleading. It omits that there are no known good 
algorithms for implementing this method: the computational complexity of 
Dodgson's voting method is prohibitive. In fact, it was not even known 
until a few years ago, when the problem was shown to be complete for 
parallel access to an NP oracle (class Theta_2^p).

     http://www.springerlink.com/content/wg040716q8261222/

This result means it is extremely far from being usable in practice. 
Unless P=NP, there are no polynomial-time algorithms for deciding 
elections with Dodgson's method.

-- Andrew

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20100421/41b141da/attachment-0004.htm>