统计学选举学家研究了在通常非常困难获取全部选民偏好的情况下,最常用的赢家预测算法是将选举在少量随机选票中运行,并将获胜者作为预测结果的性能。研究了 $(\epsilon, \delta)$-winner determination 问题,并给出了多种常见投票规则下解决该问题所需样本数量的有趣下界和上界。
Feb, 2015
本文提出了基于采样的方法来估算选举胜利的边际差,并研究了许多流行的投票规则。
May, 2015
文章研究了选举中预测获胜者的问题,给出了根据不同选举规则计算加减候选人和选民的控制变体的算法和 #P - 完全性结果。
May, 2014
研究了社会选择中度量失真问题,给出了一种新的投票规则,通过随机化最大允许值与新规则可实现失真小于 2.753,其为计算社会选择中重要而具有挑战性的问题。
Jun, 2023
本文探讨了得票规则定义的广泛类别下的可能获胜者问题的计算复杂度,发现对于除了多数制、否决制和得分向量为(2,1,...,1,0)的所有纯得分规则外,所有但一个规则在无限数量的候选人和未加权投票者情况下是 NP 完全的,而他们可以通过多数制和否决制在多项式时间内得出结果。
Nov, 2009
研究了基于歪曲的社会选择规则和基于度量空间的投票机制,在确定性社会选择规则和随机化社会选择规则中探讨畸变和沟通量之间的比较,并构建了一种新的随机化社会选择规则,达到了期望畸变的下界。
Nov, 2019
考察了两种完全比例代表制方法,试图发掘是否可以找到方案和选民组合使得这些问题有高效解法,同时研究了两种规则的参数复杂度,结果表明大多数问题都有多项式时间算法,但单峰选民组合下的 Monroe 规则仍是 NP 难问题。
Feb, 2014
研究 Monroe 规则和 Chamberlin-Courant 规则下基于总 (不) 满意度的多赢家决策的复杂性,提供了计算总满意度和总不满意度的适应性和不适应性算法,并通过实验评估验证了这些算法的可用性和优越性。
Dec, 2013
本文提出了一种考虑选民有限理性和可靠信息获取的策略性投票模型,该模型基于局部优势的行为启发式方法,建立了投票均衡,证明了其在广泛的局部优势关系中存在,经过大量的仿真实验证明,该模型的这种策略性投票的行为模式模拟了常见的人类投票模式,如杜弗格定律。
Apr, 2014
论文考虑了具有不完整信息的选举情景,研究了在该情境下如何确定一名可能赢家,发现了有些评选规则下,即使每个选民只有至多一个未决定的选择,也存在最小未决对数使得可能赢家问题为 NP 难题。
Oct, 2016