Of the People: Voting Is More Effective with Representative Candidates
Of the People: Voting Is More Effective with Representative Candidates
复制标题
人民的：有代表候选人的投票更有效
DOI：
10.1145/3033274.3085155
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
D. Kempe
中科院分区：
文献类型：
--
作者：
Yu Cheng;S. Dughmi;D. Kempe
鉴于阿罗以及吉伯德和萨特思韦特关于序数规则投票的经典不可能性结果，近期人们对描述常见投票规则接近社会最优的程度产生了兴趣。为了量化近似的质量，很自然地将候选人和选民视为嵌入在一个共同的度量空间中，并询问与社会最优候选人相比，所选候选人离选民群体远多少。我们使用这个度量偏好模型来探讨一个基本且适时的问题：当候选人能够代表选民群体时，该群体的社会福利是否会提高？如果是，那么提高多少，以及答案如何取决于度量空间的复杂性？我们将注意力限制在最基本和常见的社会选择设定上：一群选民，两个独立抽取的候选人，以及一次多数决选举。当候选人不能代表选民群体时，已知多数决规则选出的候选人离选民群体的距离可能是社会最优候选人的三倍；即使基础度量是一条直线时也是如此。我们研究当候选人从选民群体中独立抽取时这个比例如何改善。我们的结果有两方面：当度量是一条直线时，该比例从3提高到4 - 2√2，约为1.1716；这个界限是紧的。当度量是任意的时，我们证明多数决规则的近似比例的下界为1.5，并且有一个严格优于2的常数上界。积极的结果部分取决于候选人是独立同分布的假设。然而，我们表明仅独立性不足以达到上界：即使候选人是独立抽取的，如果候选人总体可以与选民不同，那么近似比例为2的上界是紧的。因此，我们表明了代表性候选人和非代表性候选人之间存在一个常数差距。
In light of the classic impossibility results of Arrow and Gibbard and Satterthwaite regarding voting with ordinal rules, there has been recent interest in characterizing how well common voting rules approximate the social optimum. In order to quantify the quality of approximation, it is natural to consider the candidates and voters as embedded within a common metric space, and to ask how much further the chosen candidate is from the population as compared to the socially optimal one. We use this metric preference model to explore a fundamental and timely question: does the social welfare of a population improve when candidates are representative of the population? If so, then by how much, and how does the answer depend on the complexity of the metric space? We restrict attention to the most fundamental and common social choice setting: a population of voters, two independently drawn candidates, and a majority rule election. When candidates are not representative of the population, it is known that the candidate selected by the majority rule can be thrice as far from the population as the socially optimal one; this holds even when the underlying metric is a line. We examine how this ratio improves when candidates are drawn independently from the population of voters. Our results are two-fold: When the metric is a line, the ratio improves from 3 to 4-2 √2}, roughly 1.1716; this bound is tight. When the metric is arbitrary, we show a lower bound of 1.5 and a constant upper bound strictly better than 2 on the approximation ratio of the majority rule. The positive result depends in part on the assumption that candidates are independent and identically distributed. However, we show that independence alone is not enough to achieve the upper bound: even when candidates are drawn independently, if the population of candidates can be different from the voters, then an upper bound of 2 on the approximation is tight. Thus, we show a constant gap between representative and non-representative candidates.
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