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.)
----
Election-Methods mailing list - see http://electorama.com/em for list info
