The Complexity of Succinct Elections

AAAI 2017 pp. 4921-4922

doi:10.1609/AAAI.V31I1.11122 /aaai/2017/fitzsimmons2017aaai-complexity/

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.

PDF AAAI Semantic Scholar

Cite

Text

Fitzsimmons and Hemaspaandra. "The Complexity of Succinct Elections." AAAI Conference on Artificial Intelligence, 2017. doi:10.1609/AAAI.V31I1.11122

Markdown

[Fitzsimmons and Hemaspaandra. "The Complexity of Succinct Elections." AAAI Conference on Artificial Intelligence, 2017.](https://mlanthology.org/aaai/2017/fitzsimmons2017aaai-complexity/) doi:10.1609/AAAI.V31I1.11122

BibTeX

@inproceedings{fitzsimmons2017aaai-complexity,
  title     = {{The Complexity of Succinct Elections}},
  author    = {Fitzsimmons, Zack and Hemaspaandra, Edith},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2017},
  pages     = {4921-4922},
  doi       = {10.1609/AAAI.V31I1.11122},
  url       = {https://mlanthology.org/aaai/2017/fitzsimmons2017aaai-complexity/}
}