# 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

## Access Full Article

top## Abstract

top## How to cite

topFreixas, 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] F. Carreras and J. Freixas, Complete simple games. Math. Soc. Sci.32 (1996) 139–155. Zbl0920.90143MR1408858
- [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] X. Deng and C.H. Papadimitriou, On the complexity of cooperative solution concepts. Math. Oper. Res.19 (1994) 257–266. Zbl0824.90146MR1290500
- [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] 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] 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] 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] J. Freixas and W.S. Zwicker, Weighted voting, abstention, and multiple levels of approval. Soc. Choice Welfare21 (2003) 399–431. Zbl1073.91542MR2023717
- [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] G.W. Harrison and T. McDaniel, Voting games and computational complexity. Oxford Econ. Papers 60 2008546–565.
- [11] T. Hegedüs and N. Megiddo, On the geometric separability of Boolean functions. Discrete Appl. Math.66 (1996) 205–218. Zbl0854.68034MR1392316
- [12] N. Karmarkar, A new polynomial-time algorithm for linear programming. Combinatorica4 (1984) 373–395. Zbl0557.90065
- [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] 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] D. Mehta and V. Raghavan, Decision tree approximations of Boolean functions. Theor. Comput. Sci.270 (2002) 609–623. Zbl0988.68136MR1871086
- [16] G. Owen, Game Theory, 3th edition. Academic Press, San Diego, USA (1995). Zbl0544.90103MR1355082
- [17] C.H. Papadimitriou, Computational Complexity. Addison Wesley (1994). Zbl0833.68049MR1251285
- [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] K. Prasad and J.S. Kelly, NP-completeness of some problems concerning voting games. Int. J. Game Theory19 (1990) 1–9. Zbl0705.90103MR1047343
- [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] A.D. Taylor and W.S. Zwicker, Simple games and magic squares. J. Comb. Theory, Ser. A 71 (1995) 67–68. Zbl0837.05026MR1335777
- [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] J. Von Neumann and O. Morgenstern, Theory of Games and Economic Behavior. Princeton University Press, Princeton, New Jersey, USA (1944). Zbl0063.05930MR11937

## NotesEmbed ?

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