On the complexity of problems on simple games

Josep Freixas; Xavier Molinero; Martin Olsen; Maria Serna

RAIRO - Operations Research - Recherche Opérationnelle (2011)

  • Volume: 45, Issue: 4, page 295-314
  • ISSN: 0399-0559

Abstract

top
Simple games cover voting systems in which a single alternative, such as a bill or an amendment, is pitted against the status quo. A simple game or a yes-no voting system is a set of rules that specifies exactly which collections of “yea” votes yield passage of the issue at hand. Each of these collections of “yea” voters forms a winning coalition. We are interested in performing a complexity analysis on problems defined on such families of games. This analysis as usual depends on the game representation used as input. We consider four natural explicit representations: winning, losing, minimal winning, and maximal losing. We first analyze the complexity of testing whether a game is simple and testing whether a game is weighted. We show that, for the four types of representations, both problems can be solved in polynomial time. Finally, we provide results on the complexity of testing whether a simple game or a weighted game is of a special type. We analyze strongness, properness, weightedness, homogeneousness, decisiveness and majorityness, which are desirable properties to be fulfilled for a simple game. Finally, we consider the possibility of representing a game in a more succinct and natural way and show that the corresponding recognition problem is hard.

How to cite

top

Freixas, Josep, et al. "On the complexity of problems on simple games." RAIRO - Operations Research - Recherche Opérationnelle 45.4 (2011): 295-314. <http://eudml.org/doc/275027>.

@article{Freixas2011,
abstract = {Simple games cover voting systems in which a single alternative, such as a bill or an amendment, is pitted against the status quo. A simple game or a yes-no voting system is a set of rules that specifies exactly which collections of “yea” votes yield passage of the issue at hand. Each of these collections of “yea” voters forms a winning coalition. We are interested in performing a complexity analysis on problems defined on such families of games. This analysis as usual depends on the game representation used as input. We consider four natural explicit representations: winning, losing, minimal winning, and maximal losing. We first analyze the complexity of testing whether a game is simple and testing whether a game is weighted. We show that, for the four types of representations, both problems can be solved in polynomial time. Finally, we provide results on the complexity of testing whether a simple game or a weighted game is of a special type. We analyze strongness, properness, weightedness, homogeneousness, decisiveness and majorityness, which are desirable properties to be fulfilled for a simple game. Finally, we consider the possibility of representing a game in a more succinct and natural way and show that the corresponding recognition problem is hard.},
author = {Freixas, Josep, Molinero, Xavier, Olsen, Martin, Serna, Maria},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {simple; weighted; majority games; NP-completeness},
language = {eng},
number = {4},
pages = {295-314},
publisher = {EDP-Sciences},
title = {On the complexity of problems on simple games},
url = {http://eudml.org/doc/275027},
volume = {45},
year = {2011},
}

TY - JOUR
AU - Freixas, Josep
AU - Molinero, Xavier
AU - Olsen, Martin
AU - Serna, Maria
TI - On the complexity of problems on simple games
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 2011
PB - EDP-Sciences
VL - 45
IS - 4
SP - 295
EP - 314
AB - Simple games cover voting systems in which a single alternative, such as a bill or an amendment, is pitted against the status quo. A simple game or a yes-no voting system is a set of rules that specifies exactly which collections of “yea” votes yield passage of the issue at hand. Each of these collections of “yea” voters forms a winning coalition. We are interested in performing a complexity analysis on problems defined on such families of games. This analysis as usual depends on the game representation used as input. We consider four natural explicit representations: winning, losing, minimal winning, and maximal losing. We first analyze the complexity of testing whether a game is simple and testing whether a game is weighted. We show that, for the four types of representations, both problems can be solved in polynomial time. Finally, we provide results on the complexity of testing whether a simple game or a weighted game is of a special type. We analyze strongness, properness, weightedness, homogeneousness, decisiveness and majorityness, which are desirable properties to be fulfilled for a simple game. Finally, we consider the possibility of representing a game in a more succinct and natural way and show that the corresponding recognition problem is hard.
LA - eng
KW - simple; weighted; majority games; NP-completeness
UR - http://eudml.org/doc/275027
ER -

References

top
  1. [1] F. Carreras and J. Freixas, Complete simple games. Math. Soc. Sci.32 (1996) 139–155. Zbl0920.90143MR1408858
  2. [2] V.G. Deĭneko and G.J. Woeginger, On the dimension of simple monotonic games. Eur. J. Oper. Res.170 (2006) 315–318. Zbl1134.68369
  3. [3] X. Deng and C.H. Papadimitriou, On the complexity of cooperative solution concepts. Math. Oper. Res.19 (1994) 257–266. Zbl0824.90146MR1290500
  4. [4] E. Elkind and D. Pasechnik, Computing the nucleolus of weighted voting games, in SODA ’09 : Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics. Philadelphia, PA, USA (2009) 327–335. MR2809333
  5. [5] E. Elkind, L.A. Goldberg, P.W. Goldberg and M. Wooldridge, Computational complexity of weighted threshold games, in Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence. Vancouver, British Columbia, Canada (2007) 718–723. Zbl1185.91081
  6. [6] E. Elkind, L.A. Goldberg, P.W. Goldberg and M. Wooldridge, On the dimensionality of voting games, in Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence. Hyatt Regency McCormick Place, Chicago (2008) 69–74. Zbl1185.91081
  7. [7] J. Freixas and X. Molinero, Simple games and weighted games : A theoretical and computational viewpoint. Discrete Appl. Math.157 (2009) 1496–1508. Zbl1168.91011MR2510230
  8. [8] J. Freixas and W.S. Zwicker, Weighted voting, abstention, and multiple levels of approval. Soc. Choice Welfare21 (2003) 399–431. Zbl1073.91542MR2023717
  9. [9] M.R. Garey and D.S. Johnson, Computers and Intractability : A Guide to the Theory of NP-Completness, edited by W.H. Freeman. San Francisco, New York, USA (1979). Zbl0411.68039MR519066
  10. [10] G.W. Harrison and T. McDaniel, Voting games and computational complexity. Oxford Econ. Papers 60 2008546–565. 
  11. [11] T. Hegedüs and N. Megiddo, On the geometric separability of Boolean functions. Discrete Appl. Math.66 (1996) 205–218. Zbl0854.68034MR1392316
  12. [12] N. Karmarkar, A new polynomial-time algorithm for linear programming. Combinatorica4 (1984) 373–395. Zbl0557.90065
  13. [13] L.G. Khachiyan, A polynomial algorithm for linear programming. Dokl. Akad. Nauk. SSSR 244 (1979) 1093–1096; English translation Soviet Math. Dokl. 20 (1979) 191–194. Zbl0414.90086MR522052
  14. [14] Y. Matsui and T. Matsui, NP-completeness for calculating power indices of weighted majority games. Theor. Comput. Sci.263 (2001) 305–310. Zbl0991.91006MR1846937
  15. [15] D. Mehta and V. Raghavan, Decision tree approximations of Boolean functions. Theor. Comput. Sci.270 (2002) 609–623. Zbl0988.68136MR1871086
  16. [16] G. Owen, Game Theory, 3th edition. Academic Press, San Diego, USA (1995). Zbl0544.90103MR1355082
  17. [17] C.H. Papadimitriou, Computational Complexity. Addison Wesley (1994). Zbl0833.68049MR1251285
  18. [18] U.N. Peled and B. Simeone, Polynomial-time algorithms for regular set-covering and threshold synthesis. Discrete Appl. Math.12 (1985) 57–69. Zbl0619.05020MR798011
  19. [19] K. Prasad and J.S. Kelly, NP-completeness of some problems concerning voting games. Int. J. Game Theory19 (1990) 1–9. Zbl0705.90103MR1047343
  20. [20] J. Rosenmüller, An algorithm for the construction of homogeneous games, in Ökonomie und Mathematik, edited by O. Opitz and B. Rauhut. Springer-Verlag (1987) 63–74. Zbl0696.90092
  21. [21] A.D. Taylor and W.S. Zwicker, Simple games and magic squares. J. Comb. Theory, Ser. A 71 (1995) 67–68. Zbl0837.05026MR1335777
  22. [22] A.D. Taylor and W.S. Zwicker, Simple games : desirability relations, trading, and pseudoweightings. Princeton University Press, New Jersey, USA (1999). Zbl0943.91005MR1714706
  23. [23] J. Von Neumann and O. Morgenstern, Theory of Games and Economic Behavior. Princeton University Press, Princeton, New Jersey, USA (1944). Zbl0063.05930MR11937

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.