Weitere Artikel dieser Ausgabe durch Wischen aufrufen
The conference version of this paper  appears in the Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems.
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
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 list succinctly, as the distinct votes of the electorate and their counts, i.e., high-multiplicity representation. We consider how this representation affects the complexity of election problems. High-multiplicity representation may be exponentially smaller than standard representation, and so many polynomial-time algorithms for election problems in standard representation become exponential-time. Surprisingly, for polynomial-time election problems, we are often able to either adapt the same approach or provide new algorithms to show that these problems remain polynomial-time in the high-multiplicity case; this is in sharp contrast to the case where each voter has a weight, where the complexity usually increases. In the process we explore the relationship between high-multiplicity scheduling and manipulation of high-multiplicity elections. And we show that for any fixed set of job lengths, high-multiplicity scheduling on uniform parallel machines is in P, which was previously known for only two job lengths. We did not find any natural case where a polynomial-time election problem does not remain in P when moving to high-multiplicity representation. However, we found one natural NP-hard election problem where the complexity does increase, namely winner determination for Kemeny elections.
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten
Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:
Bachrach, Y., Lev, O., Lewenberg, Y., & Zick, Y. (July 2016). Misrepresentation in district voting. In Proceedings of the 25th international joint conference on artificial intelligence (pp. 81–87). IJCAI/AAAI Press.
Bartholdi, J., III., Tovey, C., & Trick, M. (1989). The computational difficulty of manipulating an election. Social Choice and Welfare, 6(3), 227–241.
Bartholdi, J., III., Tovey, C., & Trick, M. (1992). How hard is it to control an election? Mathematical and Computer Modeling, 16(8/9), 27–40.
Betzler, N., Niedermeier, R., & Woeginger, G. (July 2011). Unweighted coalitional manipulation under the Borda rule is NP-hard. In Proceedings of the 22nd international joint conference on artificial intelligence (pp. 55–60). IJCAI/AAAI Press.
Brandt, F., Conitzer, V., Endriss, U., Lang, J., & Procaccia, A. (2016). Handbook of Computational Social Choice. Cambridge: Cambridge University Press. CrossRef
Conitzer, V., Sandholm, T., & Lang, J. (2007). When are elections with few candidates hard to manipulate? Journal of the ACM, 54(3), Article 14.
Davies, J., Katsirelos, G., Narodytska, N., & Walsh, T. (August 2011). Complexity and algorithms for Borda manipulation. In Proceedings of the 25th AAAI conference on artificial intelligence (pp. 657–662). AAAI Press.
Dwork, C., Kumar, R., Naor, M., & Sivakumar, D. (March 2001). Rank aggregation methods for the web. In Proceedings of the 10th international world wide web conference (pp. 613–622). ACM Press.
Fitzsimmons, Z., & Hemaspaandra, E. (February 2017). The complexity of succinct elections. In Proceedings of the 31st AAAI conference on artificial intelligence (Student Abstract) (pp. 4921–4922). AAAI Press.
Fitzsimmons, Z., & Hemaspaandra, E. (July 2018). High-multiplicity election problems. In Proceedings of the 17th international conference on autonomous agents and multiagent systems (pp. 1558–1566). IFAAMAS.
Garey, M., & Johnson, D. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: W. H. Freeman and Company. MATH
Goemans, M., & Rothvoß, T. (January 2014). Polynomiality for bin packing with a constant number of item types. In Proceedings of the 25th annual ACM-SIAM symposium on discrete algorithms (pp. 830–839). SIAM.
Hemaspaandra, E., Hemaspaandra, L., & Schnoor, H. (July 2014). A control dichotomy for pure scoring rules. In Proceedings of the 28th AAAI conference on artificial intelligence (pp. 712–720). AAAI Press.
Hemaspaandra, E., Hemaspaandra, L., & Schnoor, H. (April 2014). A control dichotomy for pure scoring rules. Technical Report. arXiv:1404.4560 [cs.GT].
Hemaspaandra, E., & Schnoor, H. (April 2016). Complexity dichotomies for unweighted scoring rules. Technical Report. arXiv:1604.05264 [cs.CC].
Hemaspaandra, E., & Schnoor, H. (August/September 2016). Dichotomy for pure scoring rules under manipulative electoral actions. In Proceedings of the 22nd European conference on artificial intelligence (pp. 1071–1079). IOS Press.
Karp, R. (March 1972). Reducibilities among combinatorial problems. In Proceedings of a symposium on the complexity of computer computations (pp. 85–103). Plenum Press.
Kemeny, J. (1959). Mathematics without numbers. Daedalus, 88, 577–591.
Lenstra, H., Jr. (1983). Integer programming with a fixed number of variables. Mathematics of Operations Research, 8(4), 538–548.
Lin, A. (2012). Solving hard problems in election systems. PhD thesis, Rochester Institute of Technology, Rochester, NY.
Mattei, N., & Walsh, T. (November 2013). PrefLib: A library for preferences. In Proceedings of the 3rd international conference on algorithmic decision theory (pp. 259–270). Springer.
Russell, N. (2007). Complexity of control of Borda count elections. Master’s thesis, Rochester Institute of Technology.
Schrijver, A. (2003). Combinatorial optimization: Polyhedra and efficiency. Berlin: Springer. MATH
Xia, L., Conitzer, V., & Procaccia, A. (June 2010). A scheduling approach to coalitional manipulation. In Proceedings of the 11th ACM conference on electronic commerce (pp. 275–284). ACM Press.
- High-multiplicity election problems
- Springer US
Autonomous Agents and Multi-Agent Systems
Print ISSN: 1387-2532
Elektronische ISSN: 1573-7454
Neuer Inhalt/© ITandMEDIA