Fwd: [EM] Why IRV is better than Condorcet

[Bill Clark]

---------- Forwarded message ----------
From: Bill Clark <wclarkxoom at gmail.com>
Date: Thu, 29 Jul 2004 21:18:30 -0400
Subject: Re: [EM] Why IRV is better than Condorcet
To: Warren Schudy <wschudy at wpi.edu>

On Thu, 29 Jul 2004 18:57:11 -0400 (EDT), Warren Schudy <wschudy at wpi.edu> wrote:

> 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.

http://www.isye.gatech.edu/~jjb/papers/stv.pdf

Here is the way they characterize the problem of strategic voting:

GIVEN: A set C of candidates; a distinguished candidate c; and the set
V of sincere, transitive, strict, and complete preferences of the
voters.

QUESTION: Is there a preference ordering on C that when tallied with
the preferences of V will ensure the election of c?

The paper claims to prove that answering that question is NP-complete
in the size of a description of the election: O(|V||C|).

> 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.

Just to nit-pick a little: NP (and NP-complete) problems are further
distinguished from (say) exponential-time problems in that a
non-deterministic polynomial time solution is known (or equivalently,
the answer to the question can be _verified_ in polynomial time).

> 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.

Actually, the paper claims that even figuring out whether there IS a
strategy that will definitely work is too hard.  Actually finding such
a strategy would be one way of answering the question, but a pure
existence proof is possible as well (and its demonstration would also
be NP-complete).

> One way of summarizing that point that makes IRV look a little less good
> is: IRV is provably unpredictable.

I don't follow you.  What do you mean by "unpredictable" here?

> 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!

I doubt you're suggesting IRV is non-deterministic, so again: what do
you mean by "unpredictability" here (and above)?

> 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.

I think that's a ''convenient'' way to evaluate voting systems, but
I'm not sure it's better.  I find the assumption that everyone votes
strategically just as implausible as the one that everybody votes (or
ever would vote) sincerely.  I think part of the reason so many people
choose not to vote is because they find strategic voting morally
repugnant, and would rather abstain than "waste" their vote or vote
insincerely (I've known many people like this, but perhaps I'm
over-generalizing).

-Bill Clark