Possible Voter Control in k-Approval and k-Veto Under Partial Information

Abstract

We study the complexity of possible constructive/destructive control by adding voters (PCCAV/PDCAV) and deleting voters (PCCDV/PDCDV) under nine different models of partial information for k-Approval and k-Veto. For the two destructive variants, we can further settle a polynomial-time result holding even for each scoring rule. Generally, in voter control, an external agent (called the chair) tries to change the outcome of the election by adding new voters to the elec- tion or by deleting voters from the election. Usually there is full information in voting theory, i.e., the chair knows the candidates, each voter’s complete ranking about the candidates and the voting rule used. In this paper, we assume the chair to have partial information about the votes and ask if the chair can add (delete) some votes so that his preferred (despised) candidate is (not) a winner for at least one completion of the partial votes to complete votes.