It only takes a few: on the hardness of voting with a constant number of agents

Abstract

Many hardness results in computational social choice make use of the fact that every directed graph may be induced by the pairwise majority relation. However, this fact requires that the number of voters is almost linear in the number of alternatives. It is therefore unclear whether existing hardness results remain intact when the number of voters is bounded, as is for example typically the case in search engine aggregation settings. In this paper, we provide sufficient conditions for majority graphs to be obtainable using a constant number of voters and leverage these conditions to show that winner determination for the Banks set, the tournament equilibrium set, Slater's rule, and ranked pairs remains hard even when there is only a small constant number of voters.