[EM] Why IRV is better than Condorcet

Warren Schudy wschudy at WPI.EDU
Thu Jul 29 15:57:11 PDT 2004


On Thu, 29 Jul 2004, Eric Gorr wrote:

> http://groups.yahoo.com/group/instantrunoff-freewheeling/message/785

I looked at the first article mentioned (the one available online), and it
purported to show that optimal strategic manipulation of IRV is
NP-complete. Summary of what NP-completeness is: no algorithm has been
found, after decades of searching by the computer science community, for
solving any of these problems in polynomial time. If any NP-complete
problem can be solved in polynomial time, they all can. This means that if
there are more than something on the order of 10 to 1000 voters,
determining optimum strategic voting strategies is for all practical
purposes impossible. This does not, however, prove that strategies that
work more often than not aren't easily knowable, but simply that finding a
strategy that will definately work, given perfect information, is too
hard.

One way of summarizing that point that makes IRV look a little less good 
is: IRV is provably unpredictable. One might argue that unpredictability 
is too high a price to pay for resistance of strategic manipulation. After 
all, the famous pick-a-random-ballot vote tallying technique resists 
strategic manipulation nicely, at the cost of unpredictability!

Even if one disagrees with the author's assertion that IRV is better from
a strategic point of view, we should allow ourselves to be reminded of the
importance of strategy in voting system design. Whether or not approval or
condorcet or IRV produces the highest societal utility given honest voting
is basically irrelevant for public elections, since voters do not, in
practice, vote honestly in public elections. (Honesty is probably closer
to true for other applications of voting systems, such as figure skating
judging.) Whether or not system X is monotonic, IIA, etc, is 
also somewhat illuminating, but isn't a reasonable judge of a voting 
system.

IMHO, a better way to evaluate a voting system is to assume that everyone
is voting strategically and look for Nash equilibria. One should assume
some information, but ideally not perfect information. Once strategic
equilibria have been characterized, one has to compare the results on
societal utility and other measures.

For more information on NP-completeness and Nash equilibria, see:
http://en.wikipedia.org/wiki/NP-Complete
http://en.wikipedia.org/wiki/Nash_equilibrium

If I remember tomorrow, I'll get the Behavioral Science article mentioned 
in the message Eric Gorr quoted.

-wjs

/-----------------------------------------\
| Warren Schudy                           |
| WPI Class of 2005                       |
| Physics and computer science major      |
| AIM: WJSchudy  email: wschudy at wpi.edu   |
| http://users.wpi.edu/~wschudy/          |
\-----------------------------------------/




More information about the Election-Methods mailing list