The complexity of power-index comparison

AbstractWe 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 and the Banzhaf power index. 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 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