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模型,确定了一系列可计算的情况。我们开发了适用于各种选民偏好类型的求解器,以量化每个选民对候选人的表现,并提出了一个优化计算的修剪策略。我们在真实和合成基准测试上广泛评估了所提出的求解器和修剪策略的性能,结果显示我们的方法是实用的。

0
下载
关闭预览

相关内容

自然语言处理顶会NAACL2022最佳论文出炉!
专知会员服务
42+阅读 · 2022年6月30日
专知会员服务
18+阅读 · 2021年7月11日
【论文笔记】基于强化学习的句子摘要排序
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
vae 相关论文 表示学习 1
CreateAMind
12+阅读 · 2018年9月6日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
16+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
1+阅读 · 2009年12月31日
国家自然科学基金
1+阅读 · 2008年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Arxiv
0+阅读 · 2023年5月29日
Arxiv
0+阅读 · 2023年5月25日
Arxiv
0+阅读 · 2023年5月25日
Arxiv
14+阅读 · 2020年12月17日
VIP会员
相关VIP内容
自然语言处理顶会NAACL2022最佳论文出炉!
专知会员服务
42+阅读 · 2022年6月30日
专知会员服务
18+阅读 · 2021年7月11日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
16+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
1+阅读 · 2009年12月31日
国家自然科学基金
1+阅读 · 2008年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Top
微信扫码咨询专知VIP会员