Communication complexity of common voting rules
Communication complexity of common voting rules
复制标题
通用投票规则的通信复杂性
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
T. Sandholm
中科院分区：
文献类型：
--
作者：
Vincent Conitzer;T. Sandholm
我们确定通用投票规则的通信复杂性。规则（按通信复杂性从低到高排序）为复数、决选复数、单次可转让投票 (STV)、孔多塞、批准、巴克林、杯、最大最小、博尔达、科普兰和排名对。对于每条规则，我们首先给出一个确定性的通信协议以及其中通信的位数的上限；然后，我们给出投票规则的（甚至是不确定的）通信要求的下限。边界匹配除 STV 和 maximin 之外的所有投票规则。
We determine the communication complexity of the common voting rules. The rules (sorted by their communication complexity from low to high) are plurality, plurality with runoff, single transferable vote (STV), Condorcet, approval, Bucklin, cup, maximin, Borda, Copeland, and ranked pairs. For each rule, we first give a deterministic communication protocol and an upper bound on the number of bits communicated in it; then, we give a lower bound on (even the nondeterministic) communication requirements of the voting rule. The bounds match for all voting rules except STV and maximin.