1 March 2007, Computational Social Choice Seminar, Ulle Endriss

Abstract

A classical result in voting theory, the Gibbard-Satterthwaite Theorem, states that for any non-dictatorial voting rule for choosing between three or more candidates, there will be situations that give voters an incentive to manipulate by not reporting their true preferences. However, in the form it is usually stated, this theorem does not immediately apply to a range of 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. Approval 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 presence of multiple sincere ballots allows us to circumvent the Gibbard-Satterthwaite Theorem. Our results show that there are several interesting settings in which no voter will have an incentive not to vote by means of /some/ sincere ballot. For instance, if there are no more than four candidates, if ties are broken using a uniform probability distribution, and if we assume that voters are expected-utility maximisers, then approval voting is strategy-proof in this sense. Some of these results have been derived with the assistance of a computer. The necessary background information on voting theory required to follow the presentation will be introduced at the beginning of the talk.

For more information, see http://www.illc.uva.nl/~ulle/seminar/ or contact Ulle Endriss (ulle at illc.uva.nl).