IJCAIMay, 2024

选择最矛盾的候选人对

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

    本文提供了委员会评分规则的公理化特征，证明了委员会评分规则通过四个标准公设和一个特定于多赢家规则的公设 “委员会优势” 来描述。同时，本文引入并公理化了多赢家决策评分规则，这是一类广泛推广已知的多数关系。

    Apr, 2016

  • 具备多样性约束的多赢家选举

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

    Nov, 2017

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

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

    Jul, 2017

  • 带有限信息和多个备选方案的投票

    本文探讨了私有信号对多数人投票的影响，研究发现使用多数投票制可以达到正确结果，但需要大量投票人才能确保正确率。

    Oct, 2011

  • 多赢家规则的比例程度

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

    Oct, 2018

  • 具有公平约束的多胜方投票

    我们介绍了一种算法框架，用于处理多获胜者投票问题，并在特定属性方面保持公平。该框架可以满足多个非不相交属性的公平性要求，并且可以指定一个评分函数。我们研究了单调和次模评分函数的计算复杂度，针对各种属性组结构和评分函数类型提出了几种近似算法和匹配的近似难度结果。我们还进行了模拟实验，结果表明添加公平约束可能不会对分数产生显著影响。

    Oct, 2017

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

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

    Feb, 2016

  • 一致的基于批准的多获胜者规则

    本文是对一种称为 “基于批准的多赢家规则” 的投票规则进行的公理化研究，介绍了计数规则，提供了基于一致性公理的这个类别的公理特征描述，并基于此，公理化刻画了三种重要的一致性多赢家规则：比例批准投票、多赢家批准投票和批准的钦定 -- 卡伦特规则。我们的研究结果展示了多赢家规则的种类和三个不同的正交原则，它们是：个人品质、多样性和比例性。

    Apr, 2017

  • 基于批准的多胜者规则的效用福利和代表性保障

    本文使用近似算法的方法定量分析多胜选者投票规则，估计它们与通过审批的 Chamberlin-Courant 规则和多胜选者批准投票中定义的两个极端目标的逼近程度，并通过理论和实验方法将多赢家规则分类到这两个对立目标的数量对齐方面，研究结果提供了关于多赢家规则的基本信息，尤其是在选择这样的规则时必要的权衡。

    Jan, 2018

  • 具有赞成偏好的多赢家投票

    本书对多胜选投票进行了深入详细的研究，基于赞成偏好进行了讨论，探讨了计算社会选择中的最新进展，主要关注公理分析和算法结果，并重点讨论了与现实应用相关的问题。

    Jul, 2020