# On the complexity of problems on simple games

Josep Freixas; Xavier Molinero; Martin Olsen; Maria Serna

RAIRO - Operations Research (2012)

- 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 45.4 (2012): 295-314. <http://eudml.org/doc/222510>.

@article{Freixas2012,

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},

keywords = {Simple; weighted; majority games; NP-completeness; simple},

language = {eng},

month = {1},

number = {4},

pages = {295-314},

publisher = {EDP Sciences},

title = {On the complexity of problems on simple games},

url = {http://eudml.org/doc/222510},

volume = {45},

year = {2012},

}

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

DA - 2012/1//

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; simple

UR - http://eudml.org/doc/222510

ER -

## References

top- F. Carreras and J. Freixas, Complete simple games. Math. Soc. Sci.32 (1996) 139–155. Zbl0920.90143
- 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
- X. Deng and C.H. Papadimitriou, On the complexity of cooperative solution concepts. Math. Oper. Res.19 (1994) 257–266. Zbl0824.90146
- 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.
- 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
- 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
- J. Freixas and X. Molinero, Simple games and weighted games : A theoretical and computational viewpoint. Discrete Appl. Math.157 (2009) 1496–1508. Zbl1168.91011
- J. Freixas and W.S. Zwicker, Weighted voting, abstention, and multiple levels of approval. Soc. Choice Welfare21 (2003) 399–431. Zbl1073.91542
- 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.68039
- G.W. Harrison and T. McDaniel, Voting games and computational complexity. Oxford Econ. Papers602008546–565.
- T. Hegedüs and N. Megiddo, On the geometric separability of Boolean functions. Discrete Appl. Math.66 (1996) 205–218. Zbl0854.68034
- N. Karmarkar, A new polynomial-time algorithm for linear programming. Combinatorica4 (1984) 373–395. Zbl0557.90065
- L.G. Khachiyan, A polynomial algorithm for linear programming. Dokl. Akad. Nauk. SSSR244 (1979) 1093–1096; English translation Soviet Math. Dokl.20 (1979) 191–194. Zbl0414.90086
- Y. Matsui and T. Matsui, NP-completeness for calculating power indices of weighted majority games. Theor. Comput. Sci.263 (2001) 305–310. Zbl0991.91006
- D. Mehta and V. Raghavan, Decision tree approximations of Boolean functions. Theor. Comput. Sci.270 (2002) 609–623. Zbl0988.68136
- G. Owen, Game Theory, 3th edition. Academic Press, San Diego, USA (1995).
- C.H. Papadimitriou, Computational Complexity. Addison Wesley (1994).
- U.N. Peled and B. Simeone, Polynomial-time algorithms for regular set-covering and threshold synthesis. Discrete Appl. Math.12 (1985) 57–69. Zbl0619.05020
- K. Prasad and J.S. Kelly, NP-completeness of some problems concerning voting games. Int. J. Game Theory19 (1990) 1–9. Zbl0705.90103
- 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
- A.D. Taylor and W.S. Zwicker, Simple games and magic squares. J. Comb. Theory, Ser. A71 (1995) 67–68. Zbl0837.05026
- A.D. Taylor and W.S. Zwicker, Simple games : desirability relations, trading, and pseudoweightings. Princeton University Press, New Jersey, USA (1999). Zbl0943.91005
- J. Von Neumann and O. Morgenstern, Theory of Games and Economic Behavior. Princeton University Press, Princeton, New Jersey, USA (1944). Zbl0063.05930

## NotesEmbed ?

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