More Web Proxy on the site http://driver.im/

Article

The Complexity of Power-Index Comparison

Authors:

Piotr Faliszewski,

Lane A. HemaspaandraAuthors Info & Claims

AAIM '08: Proceedings of the 4th international conference on Algorithmic Aspects in Information and Management

Pages 177 - 187

https://doi.org/10.1007/978-3-540-68880-8_18

Published: 23 June 2008 Publication History

Abstract

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 [16] and the Banzhaf power index [3,6]. 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 show that, unlike the Banzhaf power index, the Shapley-Shubik power index is not #P-parsimonious-complete. This finding sets a hard limit on the possible strengthenings of a result of Deng and Papadimitriou [5], who showed that the Shapley-Shubik power index is #P-metric-complete.

References

[1]

Bachrach, Y., Elkind, E.: Divide and conquer: False-name manipulations in weighted voting games. In: Proceedings of the 7th International Conference on Autonomous Agents and Multiagent Systems, May 2008 (to appear, 2008).

[2]

Balcázar, J., Book, R., Schöning, U.: The polynomial-time hierarchy and sparse oracles. Journal of the ACM 33(3), 603-617 (1986).

[3]

Banzhaf, J.: Weighted voting doesn't work: A mathematical analysis. Rutgers Law Review 19, 317-343 (1965).

[4]

Bovet, D., Crescenzi, P.: Introduction to the Theory of Complexity. Prentice-Hall, Englewood Cliffs (1993).

[5]

Deng, X., Papadimitriou, C.: On the complexity of comparative solution concepts. Mathematics of Operations Research 19(2), 257-266 (1994).

[6]

Dubey, P., Shapley, L.: Mathematical properties of the Banzhaf power index. Mathematics of Operations Research 4(2), 99-131 (1979).

[7]

Dwork, C., Kumar, R., Naor, M., Sivakumar, D.: Rank aggregation methods for the web. In: Proceedings of the 10th International World Wide Web Conference, pp. 613-622. ACM Press, New York (2001).

[8]

Faliszewski, P., Hemaspaandra, L.: The complexity of power-index comparison. Technical Report TR-929, Department of Computer Science, University of Rochester, Rochester, NY (January 2008).

[9]

Gill, J.: Computational complexity of probabilistic Turing machines. SIAM Journal on Computing 6(4), 675-695 (1977).

[10]

Hemaspaandra, L., Rajasethupathy, K., Sethupathy, P., Zimand,M.: Power balance and apportionment algorithms for the United States Congress. ACM Journal of Experimental Algorithmics 3(1) (1998), http://www.jea.acm.org/1998/HemaspaandraPower

[11]

Hunt, H., Marathe, M., Radhakrishnan, V., Stearns, R.: The complexity of planar counting problems. SIAM Journal on Computing 27(4), 1142-1167 (1998).

[12]

Krentel, M.: The complexity of optimization problems. Journal of Computer and System Sciences 36(3), 490-509 (1988).

[13]

Matsui, Y., Matsui, T.: NP-completeness for calculating power indices of weighted majority games. Theoretical Computer Science 263(1-2), 305-310 (2001).

[14]

Papadimitriou, C.: Computational Complexity. Addison-Wesley, Reading (1994).

[15]

Prasad, K., Kelly, J.: NP-completeness of some problems concerning voting games. International Journal of Game Theory 19(1), 1-9 (1990).

[16]

Shapley, L., Shubik, M.: A method of evaluating the distribution of power in a committee system. American Political Science Review 48, 787-792 (1954).

[17]

Simon, J.: On Some Central Problems in Computational Complexity. PhD thesis, Cornell University, Ithaca, N.Y, Available as Cornell Department of Computer Science Technical Report TR75-224 (January 1975).

[18]

Toda, S.: PP is as hard as the polynomial-time hierarchy. SIAM Journal on Computing 20(5), 865-877 (1991).

[19]

Valiant, L.: The complexity of computing the permanent. Theoretical Computer Science 8(2), 189-201 (1979).

[20]

Zankó, V.: #P-completeness via many-one reductions. International Journal of Foundations of Computer Science 2(1), 76-82 (1991).

Cited By

Diakonikolas IPavlou CPeebles JStewart APelachaud CTaylor MFaliszewski PMascardi V(2022)Efficient Approximation Algorithms for the Inverse Semivalue ProblemProceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems10.5555/3535850.3535891(354-362)Online publication date: 9-May-2022
https://dl.acm.org/doi/10.5555/3535850.3535891
Bachrach YZuckerman MWooldridge MRosenschein J(2013)Proof systems and transformation gamesAnnals of Mathematics and Artificial Intelligence10.1007/s10472-012-9323-967:1(1-30)Online publication date: 1-Jan-2013
https://dl.acm.org/doi/10.1007/s10472-012-9323-9
Faliszewski PElkind EWooldridge MSierra CCastelfranchi CDecker KSichman J(2009)Boolean combinations of weighted voting gamesProceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems - Volume 110.5555/1558013.1558039(185-192)Online publication date: 10-May-2009
https://dl.acm.org/doi/10.5555/1558013.1558039

Recommendations

The complexity of power-index comparison

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 ...
Computing the Banzhaf power index in network flow games
AAMAS '07: Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems

Preference aggregation is used in a variety of multiagent applications, and as a result, voting theory has become an important topic in multiagent system research. However, power indices (which reflect how much "real power" a voter has in a weighted ...
False name manipulations in weighted voting games: splitting, merging and annexation
AAMAS '09: Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems - Volume 1

An important aspect of mechanism design in social choice protocols and multiagent systems is to discourage insincere and manipulative behaviour. We examine the computational complexity of false-name manipulation in weighted voting games which are an ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

AAIM '08: Proceedings of the 4th international conference on Algorithmic Aspects in Information and Management

June 2008

348 pages

ISBN:9783540688655

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 23 June 2008

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Diakonikolas IPavlou CPeebles JStewart APelachaud CTaylor MFaliszewski PMascardi V(2022)Efficient Approximation Algorithms for the Inverse Semivalue ProblemProceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems10.5555/3535850.3535891(354-362)Online publication date: 9-May-2022
https://dl.acm.org/doi/10.5555/3535850.3535891
Bachrach YZuckerman MWooldridge MRosenschein J(2013)Proof systems and transformation gamesAnnals of Mathematics and Artificial Intelligence10.1007/s10472-012-9323-967:1(1-30)Online publication date: 1-Jan-2013
https://dl.acm.org/doi/10.1007/s10472-012-9323-9
Faliszewski PElkind EWooldridge MSierra CCastelfranchi CDecker KSichman J(2009)Boolean combinations of weighted voting gamesProceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems - Volume 110.5555/1558013.1558039(185-192)Online publication date: 10-May-2009
https://dl.acm.org/doi/10.5555/1558013.1558039

View Options

View options

Media

Figures

Other

Tables

View Table of Contents