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

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 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
  1. F. Carreras and J. Freixas, Complete simple games. Math. Soc. Sci.32 (1996) 139–155.  
  2. V.G. Deĭneko and G.J. Woeginger, On the dimension of simple monotonic games. Eur. J. Oper. Res.170 (2006) 315–318.  
  3. X. Deng and C.H. Papadimitriou, On the complexity of cooperative solution concepts. Math. Oper. Res.19 (1994) 257–266.  
  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.  
  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.  
  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.  
  7. J. Freixas and X. Molinero, Simple games and weighted games : A theoretical and computational viewpoint. Discrete Appl. Math.157 (2009) 1496–1508.  
  8. J. Freixas and W.S. Zwicker, Weighted voting, abstention, and multiple levels of approval. Soc. Choice Welfare21 (2003) 399–431.  
  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).  
  10. G.W. Harrison and T. McDaniel, Voting games and computational complexity. Oxford Econ. Papers602008546–565.  
  11. T. Hegedüs and N. Megiddo, On the geometric separability of Boolean functions. Discrete Appl. Math.66 (1996) 205–218.  
  12. N. Karmarkar, A new polynomial-time algorithm for linear programming. Combinatorica4 (1984) 373–395.  
  13. 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.  
  14. Y. Matsui and T. Matsui, NP-completeness for calculating power indices of weighted majority games. Theor. Comput. Sci.263 (2001) 305–310.  
  15. D. Mehta and V. Raghavan, Decision tree approximations of Boolean functions. Theor. Comput. Sci.270 (2002) 609–623.  
  16. G. Owen, Game Theory, 3th edition. Academic Press, San Diego, USA (1995).  
  17. C.H. Papadimitriou, Computational Complexity. Addison Wesley (1994).  
  18. U.N. Peled and B. Simeone, Polynomial-time algorithms for regular set-covering and threshold synthesis. Discrete Appl. Math.12 (1985) 57–69.  
  19. K. Prasad and J.S. Kelly, NP-completeness of some problems concerning voting games. Int. J. Game Theory19 (1990) 1–9.  
  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.  
  21. A.D. Taylor and W.S. Zwicker, Simple games and magic squares. J. Comb. Theory, Ser. A71 (1995) 67–68.  
  22. A.D. Taylor and W.S. Zwicker, Simple games : desirability relations, trading, and pseudoweightings. Princeton University Press, New Jersey, USA (1999).  
  23. J. Von Neumann and O. Morgenstern, Theory of Games and Economic Behavior. Princeton University Press, Princeton, New Jersey, USA (1944).  

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.