资源论文Control in the Presence of Manipulators: Cooperative and Competitive Cases Zack Fitzsimmons Edith Hemaspaandra Lane A. Hemaspaandra

Control in the Presence of Manipulators: Cooperative and Competitive Cases Zack Fitzsimmons Edith Hemaspaandra Lane A. Hemaspaandra

2019-11-08 | |  75 |   37 |   0
Abstract Control and manipulation are two of the most studied types of attacks on elections. In this paper, we study the complexity of control attacks on elections in which there are manipulators. We study both the case where the “chair” who is seeking to control the election is allied with the manipulators, and the case where the manipulators seek to thwart the chair. In the latter case, we see that the order of play substantially influences the complexity. We prove upper bounds, holding over every election system with a polynomial-time winner problem, for all standard control cases, and some of these bounds are at the second or third level of the polynomial hierarchy, and we provide matching lower bounds to prove these tight. Nonetheless, for important natural systems the complexity can be much lower. We prove that for approval and plurality elections, the complexity of even competitive clashes between a controller and manipulators falls far below those high bounds, even as low as polynomial time. Yet we for a Borda-voting case show that such clashes raise the complexity unless NP = coNP.

上一篇:C-Link: A Hierarchical Clustering Approach to Large-Scale Near-Optimal Coalition Formation?

下一篇:Action Translation in Extensive-Form Games with Large Action Spaces:

用户评价
全部评价

热门资源

  • The Variational S...

    Unlike traditional images which do not offer in...

  • Learning to Predi...

    Much of model-based reinforcement learning invo...

  • Stratified Strate...

    In this paper we introduce Stratified Strategy ...

  • A Mathematical Mo...

    Direct democracy, where each voter casts one vo...

  • Rating-Boosted La...

    The performance of a recommendation system reli...