CaltechAUTHORS
  A Caltech Library Service

Information-Theoretic Study of Voting Systems

Yaakobi, Eitan and Langberg, Michael and Bruck, Jehoshua (2013) Information-Theoretic Study of Voting Systems. California Institute of Technology , Pasadena, CA. (Unpublished) http://resolver.caltech.edu/CaltechAUTHORS:20130215-092855327

[img]
Preview
PDF
See Usage Policy.

300Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20130215-092855327

Abstract

The typical paradigm in voting theory involves n voters and m candidates. Every voter ranks the candidates resulting in a permutation of the m candidates. A key problem is to derive the aggregate result of the voting. A popular method for vote aggregation is based on the Condorcet criterion. The Condorcet winner is the candidate who wins every other candidate by pairwise majority. However, the main disadvantage of this approach, known as the Condorcet paradox, is that such a winner does not necessarily exist since this criterion does not admit transitivity. This paradox is mathematically likely (if voters assign rankings uniformly at random, then with probability approaching one with the number of candidates, there will not be a Condorcet winner), however, in real life scenarios such as elections, it is not likely to encounter the Condorcet paradox. In this paper we attempt to improve our intuition regarding the gap between the mathematics and reality of voting systems. We study a special case where there is global intransitivity between all candidates. We introduce tools from information theory and derive an entropy-based characterization of global intransitivity. In addition, we tighten this characterization by assuming that votes tend to be similar; in particular they can be modeled as permutations that are confined to a sphere defined by the Kendalls τ distance.


Item Type:Report or Paper (Technical Report)
Related URLs:
URLURL TypeDescription
http://www.paradise.caltech.edu/papers/etr120.pdfAuthorUNSPECIFIED
Group:Parallel and Distributed Systems Group
Funders:
Funding AgencyGrant Number
NSFECCS-0801795
Binational Science Foundation (BSF)2010075
Other Numbering System:
Other Numbering System NameOther Numbering System ID
ParadiseETR120
Record Number:CaltechAUTHORS:20130215-092855327
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20130215-092855327
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:36943
Collection:CaltechPARADISE
Deposited By: Kristin Buxton
Deposited On:15 Feb 2013 19:35
Last Modified:10 Nov 2014 20:26

Repository Staff Only: item control page