solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看211次
k-Majority Digraphs and the Hardness of Voting with a Constant Number of Voters. (arXiv:1704.06304v1 [cs.GT])
来源于:arXiv
Many hardness results in computational social choice make use of the fact
that every directed graph may be induced as the pairwise majority relation of
some preference profile. However, this fact requires a number of voters that is
almost linear in the number of alternatives. It is therefore unclear whether
these 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 a systematic study of majority digraphs for a constant number
of voters resulting in analytical, experimental, and complexity-theoretic
insights. First, we characterize the set of digraphs that can be induced by two
and three voters, respectively, and give sufficient conditions for larger
numbers of voters. Second, we present a surprisingly efficient implementation
via SAT solving for computing the minimal number of voters that is required to
induce a given digraph and experimentally evaluate how many voters are req 查看全文>>