Efficient voting via the top-k elicitation scheme: a probabilistic approach
Efficient voting via the top-k elicitation scheme: a probabilistic approach
复制标题
通过 top-k 启发方案进行有效投票：概率方法
DOI：
10.1145/2600057.2602829
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
J. Oren
中科院分区：
文献类型：
--
作者：
Yuval Filmus;J. Oren
Top-i投票是一种常见的偏好诱导形式，因为它在选民和决策者方面都具有概念上的简单性。在一个典型的设置中，给定一组候选人，投票者只需要提交他们的候选人的固有排名的k长度前缀。然后，决策者尝试根据规定的投票规则，相对于完整的偏好简档正确地预测获胜的候选人。这引起了通信成本（给定指定的k值）和正确预测赢家的能力之间的权衡。我们专注于任意位置的评分规则，其中选民的候选人的分数是由一个矢量，分配的排名真实的值。我们研究了三种偏好分布概率模型下的top-k启发性能：中性分布（公平文化）;有偏见的分布，如Mallow分布;和最坏情况（但完全已知）分布。对于一个公正的文化，我们提供了一种技术来分析性能的top-k投票。对于任意位置的评分规则的情况下，我们提供了一个简洁的一组标准，这是足够的最小k的下限和上限，以确定真正的赢家具有很高的概率。我们的下限适用于任何实施的top-k投票计划，而我们的上限，我们提供了一个具体的top-k启发算法。我们进一步证明了使用这种技术对科普兰的投票规则。对于有偏分布的情况下，我们表明，对于任何非常数的评分规则，赢家可以预测的概率很高，而无需查看投票。对于最坏情况下的分布，我们表明，指数衰减的评分规则，k = O（log m）是足够的所有分布。
Top-i voting is a common form of preference elicitation due to its conceptual simplicity both on the voters' side and on the decision maker's side. In a typical setting, given a set of candidates, the voters are required to submit only the k-length prefixes of their intrinsic rankings of the candidates. The decision maker then tries to correctly predict the winning candidate with respect to the complete preference profile according to a prescribed voting rule. This raises a tradeoff between the communication cost (given the specified value of k), and the ability to correctly predict the winner. We focus on arbitrary positional scoring rules in which the voters' scores for the candidates is given by a vector that assigns the ranks real values. We study the performance of top-k elicitation under three probabilistic models of preference distribution: a neutral distribution (impartial culture); a biased distribution, such as the Mallows distribution; and a worst-case (but fully known) distribution. For an impartial culture, we provide a technique for analyzing the performance of top-k voting. For the case of arbitrary positional scoring rules, we provide a succinct set of criteria that is sufficient for obtaining both lower and upper bounds on the minimal k necessary to determine the true winner with high probability. Our lower bounds pertain to any implementation of a top-k voting scheme, whereas for our upper bound, we provide a concrete top-k elicitation algorithm. We further demonstrate the use of this technique on Copeland's voting rule. For the case of biased distributions, we show that for any non-constant scoring rule, the winner can be predicted with high probability without ever looking at the votes. For worst-case distributions, we show that for exponentially decaying scoring rules, k = O(log m) is sufficient for all distributions.