Aug, 2011

在纯计分规则下实现可能获胜方问题的完全分离

PDF
TL;DR本研究探讨了在选民偏好只有局部指定的选举中，给定一位指定候选人是否能通过合适地扩展所有选票成为赢家的可能赢家问题，并证明了对于未加权选民和无限数量候选人的纯计分规则，在除多数派、否决票和表示为向量（2，1，...，1，0）的计分规则外，所有纯计分规则的可能赢家问题都是 NP-complete 的，但多数派和否决票的可能赢家问题可以在多项式时间内解决。 最后证明了对于用向量（2，1，...，1，0）表示的计分规则的可能赢家问题也是 NP-complete 的。
possible winner problemvoters' preferencespure scoring rulesnp-completeveto
发现论文，激发创造
  • 基于记分规则的选举中可能获胜者问题的二分研究

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

    Nov, 2009

  • 关于使得寻找获胜者困难的确实遗漏信息量

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

    Oct, 2016

  • 在部分排序中确定可能和必要的获胜者

    研究在无限数量的投票规则下，利用部分订单解决选举中可能产生的获胜问题以及必要胜利问题及其复杂性。

    Jan, 2014

  • 选举中可能的获胜者和联盟操纵问题的核化复杂度

    本文针对计算社会选择理论中可能获胜者问题，以及围绕所述问题的投票规则和多项式核心化方面的挑战等，进行了研究，并对常见投票规则的可能获胜者问题是否具有多项式核心化进行了描述，同时，对所研究问题与合谋操纵问题的关系进行了探讨。

    May, 2014

  • 投票系统的二分法

    研究不同投票制度中为什么有些具有轻松操纵的 NP 完全性质，而其他一些则具有较难操纵的多项式时间，发现了多样的嫌恶情感是决定性因素：对于每个给候选人分配两个或两个以上的点值的打分协议选举系统来说，它是 NP 完全的，对于其他系统，则可以多项式时间内操纵。

    Apr, 2005

  • 关于年轻选举的获胜者问题的精确复杂度

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

    Dec, 2001

  • 确定带有缺席投票的选举获胜者

    选举中一个重要的问题是确定在一些选票缺失的情况下候选人是否能够成为赢家。我们研究了当选票被截断时的缺失选票决策问题，证明了在单个可转移选票、最低得分和 Copeland 方面，缺失选票决策问题是 NP 完全的，并提出了一种特殊情况的位置评分规则，使问题可以在多项式时间内计算。我们在截断排名中的结果与完整排名的结果不同，因为当候选人数量或缺失选票数量受限时，它们的难度结果仍然成立，而我们则证明该问题在任一情况下都可以在多项式时间内解决。

    Oct, 2023

  • 全比例代表计算

    考察了两种完全比例代表制方法，试图发掘是否可以找到方案和选民组合使得这些问题有高效解法，同时研究了两种规则的参数复杂度，结果表明大多数问题都有多项式时间算法，但单峰选民组合下的 Monroe 规则仍是 NP 难问题。

    Feb, 2014

  • 嘈杂选举中可能获胜者

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

    May, 2014

  • 单交叉选民的完全比例代表制的复杂性

    本文研究单交叉选举中的获胜者确定复杂度，在 Chamberlin-Courant 的规则和 Monroe 的规则下，对于宽度有边界的单交叉选举，我们提供了一个多项式时间算法，但 Monroe 的规则仍然是 NP 难问题。在考虑了满足额外约束条件的单交叉选举（每个候选人至少被一个选民排在第一位的选举），我们为 Monroe 的平等版本提供了一个高效的算法。

    Jul, 2013