Sep, 2008

简单博弈中玩家影响比较的复杂性

PDF
TL;DR该文研究了关于多方投票博弈中玩家影响比较的复杂性，通过使用基本玩家类型、期望关系和 Shapley-Shubik 指数、Banzhaf 指数、Holler 指数、Deegan-Packel 指数和 Chow 参数等经典的功率指标来对不同表示形式的简单博弈进行分析，并且证明了对于其它形式的博弈，它们都是判定 NP 难的，因此多重加权投票博弈是唯一需要使用多项式算法才能验证其线性性的表示形式。
发现论文，激发创造
  • 权力指数比较的复杂性

    研究了加权投票游戏中的幂指数值高问题，并证明了对于 Shapley-Shubik 指数和 Banzhaf 指数来说，该问题是概率多项式时间完全的。同时，探讨了原始 Shapley-Shubik 指数的复杂性，证明了该指数是 #P-Metric 完全的和 #P-Many-one 完全的。

    Jan, 2008

  • 关于加权投票博弈逆半价值问题的复杂性

    本研究探讨了加权投票游戏的逆问题，在计算难度方面，我们证明了逆问题在半值类幂指标的广泛家族中是计算难以实现的，并且特别说明了逆问题对于 Banzhaf 指数和 Shapley 值的计算难度。

    Dec, 2018

  • 逆功率指标问题

    本研究探讨了基于加权投票模型的力量指数测量方法，提出了一种解决给定影响向量和力量指数的加权投票游戏的逆问题的算法，并对 Shapley-Shubik 和 Banzhaf 指数进行了精确计算和计算结果分析。

    Nov, 2012

  • 带有部分信息的投票操纵复杂性

    本文探究了在不完整信息情况下的联合操纵问题及其计算性质，并提出了三种自然的操纵计算概念。我们提出的操纵问题在很多情况下都是计算上难以处理的，即使在很少信息缺失的情况下也是如此，这也使得本文的研究有着重要的实际应用意义。

    Apr, 2016

  • 选民联盟对大选结果的影响可能性有多大？

    研究扩展了先前的研究，提出一种更一般的半随机模型来考虑多数决原则下的联合影响问题。主要结论确定了在各种投票规则下，存在可以成功影响选举的大小为 B 的联合体的半随机的可能性。技术上的贡献是对于泊松多项式变量的性质进行了进一步的表征。

    Feb, 2022

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

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

    May, 2014

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

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

    Nov, 2009

  • 选举中的贿赂有多难？

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

    Aug, 2006

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

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

    Jan, 2018

  • 网络中的影响、稳定行为和最具影响力的个体：一种博弈论方法

    本文介绍了一种新的方法来研究策略环境中的影响力问题，提出了 “影响力博弈” 作为大型但有限的网络人口行为的博弈理论模型，通过计算纯策略 Nash 均衡来确定影响力游戏的稳定结果并预测潜在结果，提供了各种影响力博弈问题的复杂性特征、高效算法和近似算法，并通过实验和数学建模将影响力博弈与潜力游戏和多元游戏等关键博弈理论模型相连接。

    Mar, 2013