Mar, 2024

挑战冠军比赛中行贿的参数化分析

PDF
TL;DR对于初始冠军的竞争中，玩家可以通过贿赂降低胜率，研究目标是通过贿赂其他玩家来最大化初始冠军赢得比赛的概率，而不超过给定的贿赂预算。通过研究该问题的复杂性，我们发现通过玩家数量参数化时该问题是弱 NP 难问题和 W [1]-hard 问题。此外，我们提出了一种设计混合整数线性规划的新方法，确保所有变量都是整数并获得最优解。
challenge the champ tournamentsbriberyprobabilityparameterized complexitymixed integer linear programs
发现论文，激发创造
  • 价格对于参数化复杂度的 Shift 贿赂问题很重要

    研究了 Shift Bribery 问题在各个参数情况下的计算复杂度，发现以影响选民数量为参数时无论使用 Borda、Maximin 还是 Copeland 算法，问题都是 W [2]-hard。同时，发现以 $p$ 被转移的总位置数为参数时，对于 Borda 和 Maximin 算法为固定参数可解，而针对 Copeland 算法则是 W [1]-hard。而以预算为参数时，结果取决于价格函数。同时，Shift Bribery 在以选民数量为参数时 tend to be tractable，但是以候选人数量为参数时结果则更加复杂。

    Feb, 2015

  • 交换贿赂的多元分析

    本文研究了投票系统中贿赂问题的计算复杂度，特别关注 Swap Bribery 的 k-approval 情况，并研究了不同成本函数对问题计算复杂性的影响。结果表明，对于某些特定情况，该问题可以用多项式时间解决，而对于更一般化的情况则是 NP 困难的。同时，对于某些自然参数，该问题具有固定参数易解性与 W [1] 难度。

    Nov, 2010

  • 在单指数时间内进行投票和贿赂

    该论文解决了计算社会选择中九个挑战之一的 “挑战＃2”，通过引入一般的选举贿赂问题，我们介绍了一个最小化费用的问题，以便在投票规则 R 下选出所需的候选人，对于许多自然的投票规则 R 参数化复杂度得到了解决。

    Dec, 2018

  • 选举中的贿赂有多难？

    本文探讨了在选举中进行贿选的复杂度问题，包括得分协议和 Dodgson 投票等不同的投票系统以及不同情况下的选择。结果表明贿选的复杂度与具体情况密切相关，即使在同一类的选举方式（例如，多数票、Borda、k approval 和 veto 中）中，对加权选民进行贿选的复杂度也可能是 NP 完全的，而对于设定了个人贿选门槛的选民则是 P 的，还有许多分析结果。

    Aug, 2006

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

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

    Jan, 2016

  • 一个操作问题的统一框架

    本文提出了一种统一框架来研究少数几种人的选票操作模型，并解决了 R-Swap 贿选问题的复杂性问题，同时发现选票规则的复杂性对贿选问题的难度有很大影响。

    Jan, 2018

  • 贿赂作为候选人成功的衡量方式：基于批准的多胜者规则的复杂性结果

    本文研究多个候选人选举中的贿赂问题，分析了各种基于赞成票的多赢家规则的时间复杂度、近似度和可解性，重点研究了参数化的时间复杂度

    Apr, 2021

  • 贿选不确定性问题的选举：难度和近似算法

    介绍一个考虑选民不确定性的新型投票贿赂问题 BVU，没有多项式 $O (1)$- 逼近算法，但有一种返回具有可接受误差的近似算法。

    Nov, 2018

  • Chamberlin-Courant 规则和 Monroe 规则下的多赢家选举的参数难度

    我们解决了多胜者决策问题在两个投票规则下的参数化复杂性，即 Chamberslin-Courant 规则和 Monroe 规则，并证明了该问题在两个规则下都是 W [1]-hard 难解的。

    Feb, 2022

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

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

    Oct, 2016