[EM] Idea Proposal: Listening Democracy

[Kristofer Munsterhjelm]

Andrew Myers wrote:
> 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.

Not the same "Dodgson's method" :) Yeah, naming methods after their 
inventors can get confusing when the inventor thought of more than one. 
In the case of Asset, however, I don't think it's actually called 
Dodgson's method -- it's just that Abd likes to mention that Dodgson did 
think of it, and so that the idea is not new.

(Incidentally, while Dodgson's Condorcet method is very difficult to 
calculate in the worst case, it may still be possible to get somewhere 
in the average case. Consider TSP solvers, or integer programming 
through branch and bound.)