Computational Aspects of Approval Voting and Declared-Strategy Voting

<p>Computational social choice is a relatively new discipline that explores issues at the intersection of social choice theory and computer science. Designing a protocol for collective decision-making is made difficult by the possibility of manipulation through insincere voting. In approval voting systems, voters decide whether to approve or disapprove available alternatives; however, the specific nature of rational approval strategies has not been adequately studied. This research explores aspects of strategy under three different approval systems, from chiefly a computational viewpoint.</p> <p>While traditional voting systems elicit only the outcome of a voter’s strategic thinking, a Declared-Strategy Voting (DSV) system accepts such strategies directly and applies them according to the voter’s preferences over the available alternatives. Ideally, when rational strategies are employed on behalf of the voters, voters are discouraged from expressing insincere preferences. Approval voting is a natural fit for use with DSV, but, unlike for the common plurality voting system, there is no extant theory regarding the most effective approval strategies in a DSV context. We propose such a theory.</p> <p>Approval-rating polls already serve an important role in assaying the views of an electorate on some subject of interest. Sites such as Rotten Tomatoes and Metacritic.com collect and display the results of approval-rating polls for movies and games. Moreover, sites such as Amazon and eBay collect approval ratings to estimate the worthiness of their buyers and sellers. In these polls, a rational voter’s approval or disapproval will sometimes be insincere so as to move the result in a desired direction. A nonmanipulable protocol would allow indication of a voter’s ideal outcome and would never reward an insincere such indication. We present and analyze a large new class of such nonmanipulable protocols motivated by the DSV concept.</p> <p>The minimax procedure is a multiwinner form of approval voting that aims to maximize the satisfaction with the outcome of the least satisfied voter. Unfortunately, computing the minimax winner set is computationally hard. We propose an approximation algorithm for this problem, a framework for polynomial-time heuristics that perform very well in practice, and a preliminary analysis of strategic voting under minimax.</p>

Name thesis:degree_name

Doctor of Philosophy (PhD)

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science & Engineering

Year dc:date.available

2008

Author dc:creator

• LeGrand, Robert Hampton, III

Contributors dc:contributor

• Ron K. Cytron
• Steven Brams, Jeremy Buhler, Robert Pless, Itai Sened, Aaron Stump

• Computer Engineering
• Engineering

Statement dc:rights

• I have not registered my thesis with the U.S. Copyright Office, and do not intend to.

Language dc:language

English (en)

Identifier

https://openscholarship.wustl.edu/eng_etds/1221

OAI identifier oai:identifier

oai:openscholarship.wustl.edu:eng_etds-2295