TY - GEN

T1 - Information-theoretic study of voting systems

AU - Yaakobi, Eitan

AU - Langberg, Michael

AU - Bruck, Jehoshua

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84890359627&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2013.6620394

DO - 10.1109/ISIT.2013.6620394

M3 - ???researchoutput.researchoutputtypes.contributiontobookanthology.conference???

AN - SCOPUS:84890359627

SN - 9781479904464

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 1087

EP - 1091

BT - 2013 IEEE International Symposium on Information Theory, ISIT 2013

T2 - 2013 IEEE International Symposium on Information Theory, ISIT 2013

Y2 - 7 July 2013 through 12 July 2013

ER -