AAAI Publications, Thirty-First AAAI Conference on Artificial Intelligence

Font Size: 
The Complexity of Succinct Elections
Zack Fitzsimmons, Edith Hemaspaandra

Last modified: 2017-02-12

Abstract


The computational study of elections generally assumes that the preferences of the electorate come in as a list of votes. Depending on the context, it may be much more natural to represent the preferences of the electorate succinctly, as the distinct votes and their counts. Though the succinct representation may be exponentially smaller than the nonsuccinct, we find only one natural case where the complexity increases, in sharp contrast to the case where each voter has a weight, where the complexity usually increases.

Keywords


elections; complexity; manipulative actions; succinct representation

Full Text: PDF