Cognitive hierarchy and voting manipulation in k-approval voting

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 other's actions.