Ce document est lié à :
info:eu-repo/semantics/altIdentifier/doi/10.1016/j.mathsocsci.2020.07.001
Ce document est lié à :
info:eu-repo/grantAgreement//GA 639945/EU/ERC Starting Grant ACCORD/ACCORD
info:eu-repo/semantics/OpenAccess
Edith Elkind et al., « Cognitive hierarchy and voting manipulation in k-approval voting », HAL-SHS : sciences politiques, ID : 10.1016/j.mathsocsci.2020.07.001
By the Gibbard-Satterthwaite theorem, every reasonable voting rule for three or more alternatives is susceptible to manipulation: there exist elections where one or more voters can change the election outcome in their favour by unilaterally modifying their vote. When a given election admits several such voters, strategic voting becomes a game among potential manipulators: a manipulative vote that leads to a better outcome when other voters are truthful may lead to disastrous results when other voters choose to manipulate as well. We consider this situation from the perspective of a boundedly rational voter, using an appropriately adapted cognitive hierarchy framework to model voters' limitations. We investigate the complexity of algorithmic questions that such a voter faces when deciding on whether to manipulate. We focus on k-approval voting rules, with k ≥ 1. We provide polynomial-time algorithms for k = 1, 2 and hardness results for k ≥ 4 (NP and co-NP), supporting the claim that strategic voting, albeit ubiquitous in collective decision making, is computationally hard if the manipulators try to reason about each others' actions.