在这篇论文中，我们研究了一种游戏，其中每个玩家需要在给定的无向图中选择一个顶点（设施）。然后，所有顶点（客户）都被分配给最近的设施，玩家的回报是分配给它的客户数量。我们证明了在给定图中决定 Nash 均衡的存在是 NP 难问题，这是我们所知的这种零和游戏的首个结果。我们还引入了一个新的度量，社会成本差异，定义为最差和最佳纳什均衡之间成本的比率。我们证明了在我们的游戏中，社会成本差异为 Omega (sqrt (n/k)) 和 O (sqrt (kn))，其中 n 是顶点数量，k 是玩家数量。

Feb, 2007

本文探讨了得票规则定义的广泛类别下的可能获胜者问题的计算复杂度，发现对于除了多数制、否决制和得分向量为（2,1,...,1,0）的所有纯得分规则外，所有但一个规则在无限数量的候选人和未加权投票者情况下是 NP 完全的，而他们可以通过多数制和否决制在多项式时间内得出结果。

Nov, 2009

统计学选举学家研究了在通常非常困难获取全部选民偏好的情况下，最常用的赢家预测算法是将选举在少量随机选票中运行，并将获胜者作为预测结果的性能。研究了 $(\epsilon, \delta)$-winner determination 问题，并给出了多种常见投票规则下解决该问题所需样本数量的有趣下界和上界。

Feb, 2015

论文考虑了具有不完整信息的选举情景，研究了在该情境下如何确定一名可能赢家，发现了有些评选规则下，即使每个选民只有至多一个未决定的选择，也存在最小未决对数使得可能赢家问题为 NP 难题。

Oct, 2016

本文研究了三种投票方案的胜者问题和排名问题的复杂度，发现 Young 的方案和 Lewis Carroll 的方案都是 NP 难问题，而 Fishburn 的方案可以通过线性规划高效求解。

Dec, 2001

本文利用基于抽样的算法预测基于选区的选举中的获胜者，证明了预测选举结果的最低样本复杂度，并扩展了模型以适用于各种投票规则和未知的胜利余数情况，同时提供了估算胜利余数的方法和误差范围

Feb, 2022

文章研究了选举中预测获胜者的问题，给出了根据不同选举规则计算加减候选人和选民的控制变体的算法和 #P - 完全性结果。

May, 2014

研究了基于歪曲的社会选择规则和基于度量空间的投票机制，在确定性社会选择规则和随机化社会选择规则中探讨畸变和沟通量之间的比较，并构建了一种新的随机化社会选择规则，达到了期望畸变的下界。

Nov, 2019

本文提出了一种改进的算法来解决凸体追逐问题，实现了广义范数空间上的常数竞争比，而在欧几里得空间中，我们的算法同时还实现了接近于研究数量函数的 Steiner 点的最佳竞争比 O (根号 dlogN)。

May, 2019

本研究探讨了在选民偏好只有局部指定的选举中，给定一位指定候选人是否能通过合适地扩展所有选票成为赢家的可能赢家问题，并证明了对于未加权选民和无限数量候选人的纯计分规则，在除多数派、否决票和表示为向量（2，1，...，1，0）的计分规则外，所有纯计分规则的可能赢家问题都是 NP-complete 的，但多数派和否决票的可能赢家问题可以在多项式时间内解决。 最后证明了对于用向量（2，1，...，1，0）表示的计分规则的可能赢家问题也是 NP-complete 的。

Aug, 2011