Skip to content
Jonathan Potter edited this page Apr 16, 2014 · 4 revisions

MS Thesis

We will study manipulation in election systems, looking specifically at random manipulation, and basing our work on the results of Friedgut, Kalai, and Nisan and by Xia and Conitzer. We will analyze these results and improve upon them by generalizing the results of Friedgut, Kalai, and Nisan, and loosening the conditions of Xia and Conitzer. These authors condition their results on voting rules having certain properties, and we intend to look at what happens when these conditions are replaced by stronger or weaker conditions. We would also like to tighten the bounds given by these two papers by a constant factor or by making them depend on the number of candidates.

Schedule

  • 2012-03-01 - Proposal
  • 2012-04-01 - Preliminary results
  • 2013-05-01 - Final results
  • 2013-08-01 - Thesis draft
  • 2014-01-01 - Thesis
  • 2014-04-30 - Defense

Draft Table of Contents

  1. Introduction
  2. Importance
  3. Difficulty
  4. Independent Work
  5. Proof Summary
  6. Structure of the Remaining Chapters
  7. Preliminaries
  8. Definitions
  9. Background
  10. Brief History of Social Choice Theory
  11. History of Manipulation
  12. Related Work
  13. Results
  14. Lattice Theory
  15. Main Theorem
  16. Generalized Lemma 6 of Friedgut
  17. Generalized Lemma 7 of Friedgut
  18. Generalized Lemma 8 of Friedgut
  19. Finished Step 3 of Friedgut
  20. Main Theorem of Friedgut
  21. Conclusion
  22. Open Problems

Abstract

Friedgut, Kalai, and Nisan have proved that social choice functions can be successfully manipulated by random preference reordering with non-negligible probability. However, their results require two restrictions: the social choice function must be neutral, and the election must have at most 3 alternatives. In this thesis we focus on removing the later restriction and generalizing the results to elections with any number of candidates. We also provide a survey of related work analyzing and comparing results from a number of authors.

Clone this wiki locally