<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
<title></title>
</head>
<body bgcolor="#ffffff" text="#000000">
On 7/22/64 2:59 PM, Abd ul-Rahman Lomax wrote:
<blockquote
cite="mid:%3C20100421150205.88B6E8DB00BB@zapata.dreamhost.com%3E"
type="cite">
<pre wrap="">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 <b
class="moz-txt-star"><span class="moz-txt-tag">*</span>obviously<span
class="moz-txt-tag">*</span></b> 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?
</pre>
</blockquote>
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).<br>
<br>
<a class="moz-txt-link-freetext" href="http://www.springerlink.com/content/wg040716q8261222/">http://www.springerlink.com/content/wg040716q8261222/</a><br>
<br>
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.<br>
<br>
-- Andrew<br>
<br>
</body>
</html>