Manipulation of elections by minimal coalitions

Show full item record

Title: Manipulation of elections by minimal coalitions
Author: Connett, Christopher
Abstract: Social choice is the study of the issues arising when a population of individuals attempts to combine its views with the objective of determining a collective policy. Recent research in artificial intelligence raises concerns of articial intelligence agents applying computational resources to attack an election. If we think of voting as a way to combine honest preferences, it would be undesirable for some voters cast ballots that differ from their true preferences and achieve a better result for themselves at the expense of the general social welfare. Such an attack is called manipulation. The Gibbard-Satterthwaite theorem holds that all reasonable voting rules will admit a situation in which some voter achieves a better result for itself by misrepresenting its preferences. Bartholdi and Orlin showed that finding a beneficial manipulation under the single transferable vote rule is NP-Complete. Our work explores the practical dificulty of the coalitional manipulation problem. We computed the minimum sizes of successful manipulating coalitions, and compared this to theoretical results.
Record URI: http://hdl.handle.net/1850/12947
Date: 2010

Files in this item

Files Size Format View
CConnettThesis6-18-2010.pdf 698.1Kb PDF View/Open

The following license files are associated with this item:

This item appears in the following Collection(s)

Show full item record

Search RIT DML


Advanced Search

Browse