Approximating power indices: theoretical and empirical analysis
Approximating power indices: theoretical and empirical analysis
复制标题
近似功效指数：理论和实证分析
DOI：
10.1007/s10458-009-9078-9
复制
发表时间：
2010
影响因子：
1.9
通讯作者：
A. Saberi
中科院分区：
文献类型：
--
作者：
Yoram Bachrach;E. Markakis;Ezra Resnick;Ariel D. Procaccia;J. Rosenschein;A. Saberi
许多代理商之间的合作对于实现共同目标至关重要的多种领域可以作为联盟游戏建模。探索的权力指数反映了选民的“真正的权力”，尽管这些索引可以用于任何简单的联盟游戏。已知在各种域中都在计算上很难，因此有时必须使用近似方法来计算它们。取决于游戏的特定表示，因此可以在任何简单的联盟游戏中使用它们。我们还提供有关我们方法的经验结果，并表明它通常比所需的方法更好的准确性和信心要好得多。
Many multiagent domains where cooperation among agents is crucial to achieving a common goal can be modeled as coalitional games. However, in many of these domains, agents are unequal in their power to affect the outcome of the game. Prior research on weighted voting games has explored power indices, which reflect how much “real power” a voter has. Although primarily used for voting games, these indices can be applied to any simple coalitional game. Computing these indices is known to be computationally hard in various domains, so one must sometimes resort to approximate methods for calculating them. We suggest and analyze randomized methods to approximate power indices such as the Banzhaf power index and the Shapley–Shubik power index. Our approximation algorithms do not depend on a specific representation of the game, so they can be used in any simple coalitional game. Our methods are based on testing the game’s value for several sample coalitions. We show that no approximation algorithm can do much better for general coalitional games, by providing lower bounds for both deterministic and randomized algorithms for calculating power indices. We also provide empirical results regarding our method, and show that it typically achieves much better accuracy and confidence than those required.