On the Distortion of Voting with Multiple Representative Candidates
On the Distortion of Voting with Multiple Representative Candidates
复制标题
论多代表候选人投票的扭曲
DOI：
10.1609/aaai.v32i1.11469
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
D. Kempe
中科院分区：
文献类型：
--
作者：
Yu Cheng;S. Dughmi;D. Kempe
我们研究位置投票规则时，候选人和选民被嵌入在一个共同的度量空间，和基数的偏好，很自然地给出了度量空间中的距离。在按位投票规则中，每个候选人根据选票的排名顺序从每张选票中获得分数;总分数最高的候选人赢得选举。候选人的成本是他与所有选民的距离之和，而选举的失真是当选候选人的成本与最佳候选人的成本之间的比率。我们考虑的情况下，当候选人是代表人口，在这个意义上，他们是独立的。从选民的人口，并分析预期扭曲的立场投票规则。我们的主要结果是一个干净和严格的位置投票规则，具有恒定的预期失真（独立的候选人的数量和度量空间）的特征。我们的表征结果立即意味着恒定的预期失真博尔达计数和选举中，每个选民批准一个常数部分的所有候选人。另一方面，我们得到了超常数的期望失真的Plurality，否决权，并批准一个常数的候选人。这些结果与以前的结果与度量偏好投票：当候选人被选中的对抗，所有的前面的投票规则有失真的候选人或选民的数量线性。因此，代表候选人的模型允许我们区分在最坏情况下似乎同样糟糕的投票规则。
We study positional voting rules when candidates and voters are embedded in a common metric space, and cardinal preferences are naturally given by distances in the metric space. In a positional voting rule, each candidate receives a score from each ballot based on the ballot's rank order; the candidate with the highest total score wins the election. The cost of a candidate is his sum of distances to all voters, and the distortion of an election is the ratio between the cost of the elected candidate and the cost of the optimum candidate. We consider the case when candidates are representative of the population, in the sense that they are drawn i.i.d. from the population of the voters, and analyze the expected distortion of positional voting rules. Our main result is a clean and tight characterization of positional voting rules that have constant expected distortion (independent of the number of candidates and the metric space). Our characterization result immediately implies constant expected distortion for Borda Count and elections in which each voter approves a constant fraction of all candidates. On the other hand, we obtain super-constant expected distortion for Plurality, Veto, and approving a constant number of candidates.These results contrast with previous results on voting with metric preferences: When the candidates are chosen adversarially, all of the preceding voting rules have distortion linear in the number of candidates or voters. Thus, the model of representative candidates allows us to distinguish voting rules which seem equally bad in the worst case.
DOI：
10.1145/3033274.3085138
发表时间：
2017
期刊：
EC '17 Proceedings of the 2017 ACM Conference on Economics and Computation
影响因子：
--
作者：
Goel, Ashish;Krishnaswamy, Anilesh K.;Munagala, Kamesh
通讯作者：
Munagala, Kamesh