Voting according to one’s political stances is difficult : Problems definition, computational hardness, and approximate solutions

Abstract

This paper studies the computational complexity of two voting problems where the goal is deciding how a given voter should vote to favour their personal stances. In the first problem, given (a) the voter stance towards each law that will be voted by the parliament and (b) the political stance of each party towards each law (all party members are assumed to vote according to it), the goal is finding the parliamentary seats distribution maximizing the number of laws that will be approved/rejected as desired by the voter. In the second problem no parliament is involved, but a single issue with several possible answers is voted by citizens in a presidential election with several candidates. The problem consists in deciding how a group of voters, split in different electoral districts, all of them supporting the same candidate, should vote to make their candidate president. It is assumed that (a) all delegates of each electoral district are assigned to the candidate winning in the district, (b) after the election day, candidates may ask their assigned delegates to support other candidates receiving more votes than them, and these post-electoral supporting stances are known in advance by the electorate, and (c) the group of voters that is coordinated knows the votes that will be cast by the rest of the electorate. For each problem, its NP-hardness as well as its inapproximability are proved. This implies that something as essential as exercising the democratic right to vote, in such a way that the voting choice will be the best forp the voter’s political stances, is at least NP-hard. It is also shown how genetic algorithms can be used to obtain reasonable solutions in practice despite the limitations of theoretical approximation hardness.