RT Journal Article
T1 Voting according to one’s political stances is difficult : Problems definition, computational hardness, and approximate solutions
A1 Godoy, Aitor
A1 Rubio Díez, Fernando
A1 Rodríguez Laguna, Ismael
AB 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 problemno 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 receivingmore 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 obtainreasonable solutions in practice despite the limitations of theoretical approximation hardness.
PB Elsevier
SN 1877-7503
YR 2024
FD 2024-05-18
LK https://hdl.handle.net/20.500.14352/104712
UL https://hdl.handle.net/20.500.14352/104712
LA eng
DS Docta Complutense
RD 11 abr 2025