[EM] Approval is non-manipulable for utility maximizers

[Jameson Quinn]

Endriss, U. “Vote Manipulation in the Presence of Multiple Sincere
Ballots.” In Proceedings of the 11th Conference on Theoretical Aspects of
Rationality and Knowledge, 125–134, 2007.
http://dl.acm.org/citation.cfm?id=1324268.

Abstract

A classical result in voting theory, the Gibbard-Satterthwaite Theorem,
states that for any non-dictatorial voting rule for choos- ing between
three or more candidates, there will be situations that give voters an
incen- tive to manipulate by not reporting their true preferences. However,
this theorem does not immediately apply to all voting rules that are used
in practice. For instance, it makes the implicit assumption that there is a
unique way of casting a sincere vote, for any given preference ordering
over candidates. Ap- proval voting is an important voting rule that does
not satisfy this condition. In approval voting, a ballot consists of the
names of any subset of the set of candidates standing; these are the
candidates the voter approves of. The candidate receiving the most
approvals wins. A ballot is considered sincere if the voter prefers any of
the approved candidates over any of the disapproved candidates. In this
paper, we explore to what extent the pres- ence of multiple sincere ballots
allows us to circumvent the Gibbard-Satterthwaite The- orem. Our results
show that there are sev- eral interesting settings in which no voter will
have an incentive not to vote by means of some sincere ballot.

----

Jameson here: in particular, they show that if ties are broken randomly,
then for any set of fixed votes for everyone else, there is always some
dominant non-dishonest strategy for any voter who has fixed utilities for
each of the candidates and is an expected-utility maximizer. They also show
it for optimistic and pessimistic voters (who value ties as the best or
worst candidate in the tie). Having skimmed their proof, I conjecture that
it could straightforwardly be extended to voters who were risk averse in
any form, even forms more extreme than pessimism. However, there are
probably some cases of voters who were risk-seeking even beyond optimism
where manipulability works.

I'm sure that some people on the list are familiar with this result, but
since I just found it, I'm also sure that some here are unfamiliar with it.
Since I find it very interesting, I'm sharing it here. (In fact, I found it
after reading Gibbard's proof and hypothesizing that it was true.)

Basically, approval voting escapes Gibbard-Satterthwaite because there are
multiple honest ballots possible.

I suspect that this result could be extended to show that there is always a
dominant semi-honest (approval-style) ballot in Score and MJ (and CMJ).

Jameson
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20120929/c3ae99a2/attachment-0003.htm>