k-Majority digraphs and the hardness of voting with a constant number of voters

摘要

Many hardness results in computational social choice use the fact that every digraph may be induced as the pairwise majority relation of some preference profile. The standard construction requires a number of voters that is almost linear in the number of alternatives and it is unclear whether hardness holds when the number of voters is bounded. In this paper, we systematically study majority digraphs inducible by a constant number of voters. First, we characterize digraphs inducible by two or three voters, and give sufficient conditions for more voters. Second, we use SAT solvers to compute the minimum number of voters required to induce digraphs given by generated and real-world preference profiles. Finally, using our sufficient conditions, we show that several voting rules remain hard to evaluate for small constant numbers of voters. Kemeny's rule remains hard for 7 voters; previous methods could only prove this for constant even numbers of voters.