We investigate the problem of computing the probability of winning in an election where voter attendance is uncertain. More precisely, we study the setting where, in addition to a total ordering of the candidates, each voter is associated with a probability of attending the poll, and the attendances of different voters are probabilistically independent. We show that the probability of winning can be computed in polynomial time for the plurality and veto rules. However, it is computationally hard (#P-hard) for various other rules, including $k$-approval and $k$-veto for $k>1$, Borda, Condorcet, and Maximin. For some of these rules, it is even hard to find a multiplicative approximation since it is already hard to determine whether this probability is nonzero. In contrast, we devise a fully polynomial-time randomized approximation scheme (FPRAS) for the complement probability, namely the probability of losing, for every positional scoring rule (with polynomial scores), as well as for the Condorcet rule.


翻译:我们调查了在选民出席率不确定的选举中计算获胜概率的问题。更准确地说,我们研究的是,除了候选人的总顺序之外,每个选民都与参加投票的概率相关,而不同选民的出席概率是概率独立的。我们显示,在多元和否决规则的多元时间里,获胜概率可以计算为多球时间。然而,对于其他各种规则,包括美元批准和美元1美元、博尔达、康多塞特和马克西敏,计算得票的可能性非常困难(#P-hard ) 。对于其中一些规则来说,甚至很难找到一个重复的近似值,因为已经很难确定这种概率是不是非零。相反,我们为补充概率设计了一个完全多球时随机近比计划(FPRAS ), 即对于每一项职位评分规则(加多球分)以及康多球规则来说, 都很难找到一个重复的近比值。

0
下载
关闭预览

相关内容

专知会员服务
50+阅读 · 2020年12月14日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
【经典书】C语言傻瓜式入门(第二版),411页pdf
专知会员服务
51+阅读 · 2020年8月16日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【新书】Python编程基础,669页pdf
专知会员服务
194+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
已删除
将门创投
4+阅读 · 2019年8月22日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
VIP会员
相关资讯
已删除
将门创投
4+阅读 · 2019年8月22日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员