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 ), 即对于每一项职位评分规则(加多球分)以及康多球规则来说, 都很难找到一个重复的近比值。