A Control Dichotomy for Pure Scoring Rules


  • Edith Hemaspaandra Rochester Institute of Technology
  • Lane Hemaspaandra University of Rochester
  • Henning Schnoor University of Kiel




voting systems, computational social choice, complexity, scoring rules, control of elections, dichotomy theorems


Scoring systems are an extremely important class of election systems. A length-m (so-called) scoring vector applies only to m-candidate elections. To handle general elections, one must use a family of vectors, one per length. The most elegant approach to making sure such families are "family-like'' is the recently introduced notion of (polynomial-time uniform) pure scoring rules, where each scoring vector is obtained from its precursor by adding one new coefficient. We obtain the first dichotomy theorem for pure scoring rules for a control problem. In particular, for constructive control by adding voters (CCAV), we show that CCAV is solvable in polynomial time for k-approval with k<=3, k-veto with k<=2, every pure scoring rule in which only the two top-rated candidates gain nonzero scores, and a particular rule that is a "hybrid" of 1-approval and 1-veto. For all other pure scoring rules, CCAV is NP-complete. We also investigate the descriptive richness of different models for defining pure scoring rules, proving how more rule-generation time gives more rules, proving that rationals give more rules than do the natural numbers, and proving that some restrictions previously thought to be "w.l.o.g." in fact do lose generality.




How to Cite

Hemaspaandra, E., Hemaspaandra, L., & Schnoor, H. (2014). A Control Dichotomy for Pure Scoring Rules. Proceedings of the AAAI Conference on Artificial Intelligence, 28(1). https://doi.org/10.1609/aaai.v28i1.8800



AAAI Technical Track: Game Theory and Economic Paradigms