It remains an open question how to determine the winner of an election when voter preferences are incomplete or uncertain. One option is to assume some probability space over the voting profile and select the Most Probable Winner (MPW) -- the candidate or candidates with the best chance of winning. In this paper, we propose an alternative winner interpretation, selecting the Most Expected Winner (MEW) according to the expected performance of the candidates. We separate the uncertainty in voter preferences into the generation step and the observation step, which gives rise to a unified voting profile combining both incomplete and probabilistic voting profiles. We use this framework to establish the theoretical hardness of \mew over incomplete voter preferences, and then identify a collection of tractable cases for a variety of voting profiles, including those based on the popular Repeated Insertion Model (RIM) and its special case, the Mallows model. We develop solvers customized for various voter preference types to quantify the candidate performance for the individual voters, and propose a pruning strategy that optimizes computation. The performance of the proposed solvers and pruning strategy is evaluated extensively on real and synthetic benchmarks, showing that our methods are practical.
翻译:当选民偏好不完整或不确定时,如何确定选举的获胜者仍然是一个未解决的问题。其中一个选择是在投票档案上假设一个概率空间并选择最可能获胜者(MPW)--即具有最佳获胜机会的候选人或候选团队。在本文中,我们提出了一种选择最有望获胜者(MEW)的替代获胜者解释,该获胜者解释基于候选人的预期表现。我们将选民偏好的不确定性分成生成步骤和观察步骤,从而产生一个统一的投票档案,同时结合不完整和概率化的投票档案。我们利用这个框架来证明在自然偏好中\mew 的理论难度,然后针对多种投票档案,包括基于流行的重复插入模型(RIM)及其特例,Mallows模型,确定了一系列可计算的情况。我们开发了适用于各种选民偏好类型的求解器,以量化每个选民对候选人的表现,并提出了一个优化计算的修剪策略。我们在真实和合成基准测试上广泛评估了所提出的求解器和修剪策略的性能,结果显示我们的方法是实用的。