The Complexity of Power-Index Comparison

Simple item page
dc.creatorFaliszewski, Piotr
dc.creatorHemaspaandra, Lane A.
dc.date2008-01-30
dc.date.accessioned2026-07-07T08:57:15Z
dc.date.available2026-07-07T08:57:15Z
dc.descriptionWe study the complexity of the following problem: Given two weighted voting games G' and G'' that each contain a player p, in which of these games is p's power index value higher? We study this problem with respect to both the Shapley-Shubik power index [SS54] and the Banzhaf power index [Ban65,DS79]. Our main result is that for both of these power indices the problem is complete for probabilistic polynomial time (i.e., is PP-complete). We apply our results to partially resolve some recently proposed problems regarding the complexity of weighted voting games. We also study the complexity of the raw Shapley-Shubik power index. Deng and Papadimitriou [DP94] showed that the raw Shapley-Shubik power index is #P-metric-complete. We strengthen this by showing that the raw Shapley-Shubik power index is many-one complete for #P. And our strengthening cannot possibly be further improved to parsimonious completeness, since we observe that, in contrast with the raw Banzhaf power index, the raw Shapley-Shubik power index is not #P-parsimonious-complete.
dc.description12 pages
dc.identifierhttps://arxiv.org/abs/0801.4585
dc.identifierhttp://arxiv.org/abs/0801.4585
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/146894
dc.subjectComputational Complexity
dc.subjectComputer Science and Game Theory
dc.subjectI.2.11; F.2.2; F.1.3
dc.titleThe Complexity of Power-Index Comparison
dc.typetext

Files

Collections

arXiv