The Complexity of Power-Index Comparison

Details The Complexity of Power-Index Comparison The Complexity of Power-Index Comparison

2008-01-30

arxiv.org/abs/0801.4585v1

Computer Science

Computational Complexity

12 pages

Scientific paper

We 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.

Affiliated with

Also associated with

No associations

Rating

The Complexity of Power-Index Comparison does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Complexity of Power-Index Comparison, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Complexity of Power-Index Comparison will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-121210