Jul, 2017

多获胜者投票规则中的稳健性

PDF
TL;DR研究了委员会选举结果对输入偏好顺序的微小变化的稳健性，探讨了不同投票规则的影响，发现单个偏好顺序内相邻候选人的一次交换可能导致最多一个委员会成员被替换或整个委员会被替换，并证明了计算导致选举结果改变的最小交换数通常是 NP-hard 的，但是存在自然的 FPT 算法，最后对一些规则的实验评估了改变选举结果所需的平均随机交换次数。
发现论文，激发创造
  • 具备多样性约束的多赢家选举

    本文提出了一种多赢家选举模型，结合了委员会质量的表现 - based 测量方法 (例如，委员会成员的 Borda 分数) 和多样性约束。我们主要关注于分析算法的复杂度和募集委员会的策略。

    Nov, 2017

  • 评估基于批准的多赢家投票在噪声稳健性方面的性能

    本文研究了基于批准的多赢家选举规则的噪声模型，发现该选举方式对合理噪声始终具有鲁棒性，并提出了按照鲁棒性等级划分的相关规则。

    Feb, 2020

  • 多赢家规则的比例程度

    本文研究了基于批准的多胜选举，旨在选择代表选民偏好的委员会，作者考察了不同的选举规则并探讨了它们的比例代表性，最终给出了一种关于选择代表性委员会与效用效率平衡的权衡方案。

    Oct, 2018

  • 选择最矛盾的候选人对

    我们从选民偏好的角度研究委员会选举，寻找最具冲突的候选人，即表示最大冲突量的候选人。通过提出基本公理来捕捉这一目标，我们发现著名的多赢家投票规则没有满足这些公理。因此，我们设计了符合我们要求的委员会投票规则，引入了冲突投票规则。随后的深入分析更加清楚地展示了它们的运作方式。我们的研究还确定了冲突的各个方面，提出了相关的公理和定量措施，这可能具有独立的研究价值。我们通过对实际数据和合成数据进行实验证实了我们的理论研究。

    May, 2024

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

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

    Jul, 2013

  • 多胜选人制度的类比：公理和算法观点

    研究了满足固定多数标准的委员会评分规则，发现大多数规则的获胜者计算复杂度很高（即 NP 难问题），但也提出了准确的 FPT 算法或近似多项式时间算法来解决这个问题。

    Feb, 2016

  • 全比例代表计算

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

    Feb, 2014

  • 使用单调可分的位置多赢家投票规则寻找多元代表委员会的复杂性分析

    通过使用位置多赢投票规则，仅在 P≠NP 的假设下，研究了如何找到兼具多样性和代表性的委员会的复杂度问题。

    Nov, 2022

  • 基于记分规则的选举中可能获胜者问题的二分研究

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

    Nov, 2009

  • 委员会选举中的折衷贿选复杂性

    本文主要研究多胜选规则下 SHIFT BRIBERY 问题的复杂性，特别关注于 SNTV、Bloc、k-Borda 以及 Chamberlin-Courant 规则及其近似变种的情况，发现当规则基于近似算法时，SHIFT BRIBERY 问题的复杂度会受到影响。

    Jan, 2016