Approximate Inference of Outcomes in Probabilistic Elections
Approximate Inference of Outcomes in Probabilistic Elections
复制标题
概率选举结果的近似推断
DOI：
10.1609/aaai.v33i01.33012061
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
B. Kimelfeld
中科院分区：
文献类型：
--
作者：
Batya Kenig;B. Kimelfeld
我们研究了在选举中估计结果对概率投票的概率的复杂性。重点放在表达为位置评分规则的投票规则和概率选民的两个模型：部分投票概况（由每个选民对候选人的部分订购）和重复的插入模型（由候选人的部分订购）和重复的插入模型（在候选人上的边缘），包括木棍分布的特殊情况。过去的研究已经确定，尽管对获胜的可能性的确切推断在计算上是硬的（＃p-hard），但通过采样和平均来实现添加剂多项式近似（添加剂FPRA）。但是，经常需要需要乘法近似保证，这对于诸如条件概率之类的重要措施至关重要。不幸的是，赢得概率的乘法近似不能有效（在常规复杂性假设下），因为确定此概率是否为非零是NP完整的。相反，我们为补体事件的概率（即失去选举）设计了乘法多项式时间近似（乘法FPRA）。
We study the complexity of estimating the probability of an outcome in an election over probabilistic votes. The focus is on voting rules expressed as positional scoring rules, and two models of probabilistic voters: the uniform distribution over the completions of a partial voting profile (consisting of a partial ordering of the candidates by each voter), and the Repeated Insertion Model (RIM) over the candidates, including the special case of the Mallows distribution. Past research has established that, while exact inference of the probability of winning is computationally hard (#P-hard), an additive polynomial-time approximation (additive FPRAS) is attained by sampling and averaging. There is often, though, a need for multiplicative approximation guarantees that are crucial for important measures such as conditional probabilities. Unfortunately, a multiplicative approximation of the probability of winning cannot be efficient (under conventional complexity assumptions) since it is already NP-complete to determine whether this probability is nonzero. Contrastingly, we devise multiplicative polynomial-time approximations (multiplicative FPRAS) for the probability of the complement event, namely, losing the election.