Probabilistic Inference of Winners in Elections by Independent Random Voters
Probabilistic Inference of Winners in Elections by Independent Random Voters
复制标题
独立随机选民选举获胜者的概率推断
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
B. Kimelfeld
中科院分区：
文献类型：
--
作者：
Aviram Imber;B. Kimelfeld
我们调查了计算选举尚不确定的选举中获胜的可能性的问题。更确切地说，我们研究了一个环境，除了候选人的总订购外，每个选民还与参加民意调查的可能性相关联，而不同选民的出勤率在概率上是独立的。我们表明，可以在多项式时间内计算获胜的概率，以实现多项性和否决规则。但是，对于其他各种规则，在计算上很难（＃p-hard），包括$ k $ approval和$ k $ - veto $ k> 1 $，Borda，Condorcet和Maximin。对于其中一些规则，甚至很难找到乘法近似，因为已经很难确定此概率是否为非零。相比之下，我们为补体概率设计了一个完全多项式的随机近似方案（FPRA），即对于每个位置评分规则（具有多项式得分）以及condorcet规则的损失概率。
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.
受贿选民不确定性的选举：硬度和近似算法
DOI：
10.1609/aaai.v33i01.33012572
发表时间：
2019
期刊：
Proceedings of the ... AAAI Conference on Artificial Intelligence
影响因子：
--
作者：
Chen, L.;Xu, L.;Xu, S. H.;Gao, Z.M.;Shi, W.D.
通讯作者：
Shi, W.D.
具有贿赂效应不确定性的选举：二分法结果
DOI：
10.24963/ijcai.2019/23
发表时间：
2019
期刊：
International Joint Conference on Artificial Intelligence
影响因子：
--
作者：
Chen, Lin;Xu, Lei;Xu, Shouhuai;Gao, Zhimin;Shi, Weidong
通讯作者：
Shi, Weidong