Computational aspects of strategic behaviour in elections with top-truncated ballots

Understanding when and how computational complexity can be used to protect elections against different manipulative actions has been a highly active research area over the past two decades. Much of this literature, however, makes the assumption that the voters or agents specify a complete preference ordering over the set of candidates. There are many multiagent systems applications, and even real-world elections, where this assumption is not warranted, and this in turn raises a series of questions on the impact of partial voting on the complexity of manipulative actions. In this paper, we focus on two of these questions. First, we address the question of how hard it is to manipulate elections when the agents specify only top-truncated ballots. Here, in particular, we look at the weighted manipulation problem—both constructive and destructive manipulation—when the voters are allowed to specify top-truncated ballots, and we provide general results for all scoring rules, for elimination versions of all scoring rules, for the plurality with runoff rule, for a family of election systems known as Copeland\(^{\alpha }\), and for the maximin protocol. The second question we address is the impact of top-truncated voting on the complexity of manipulative actions in electorates with structured preference profiles. In particular, we consider electorates that are single-peaked and we show how, for many voting protocols, allowing top-truncated voting reimposes the \(\mathcal {NP}\)-hardness shields that normally vanish in such electorates.