Abstract
Gvozdeva et al. (Int J Game Theory, doi:10.1007/s00182-011-0308-4, 2013) have introduced three hierarchies for simple games in order to measure the distance of a given simple game to the class of (roughly) weighted voting games. Their third class \({\mathcal {C}}_\alpha \) consists of all simple games permitting a weighted representation such that each winning coalition has a weight of at least \(1\) and each losing coalition a weight of at most \(\alpha \). For a given game the minimal possible value of \(\alpha \) is called its critical threshold value. We continue the work on the critical threshold value, initiated by Gvozdeva et al., and contribute some new results on the possible values for a given number of voters as well as some general bounds for restricted subclasses of games. A strong relation between this concept and the cost of stability, i.e. the minimum amount of external payment to ensure stability in a coalitional game, is uncovered.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
Some authors, e.g. Gvozdeva et al. (2013), allow \(q=0\), which makes sense in other contexts like circuits or Boolean algebra. Later on, we want to rescale the quota \(q\) to one, so that we forbid a quota of zero by definition. Another unpleasant consequence of allowing \(q=0\) would be that each simple game on \(n\) voters is contained in a roughly weighted game on \(n+1\) voters, i.e., we can add to each given simple game a voter who forms a winning coalition on its own to obtain a roughly weighted game.
We remark that usually \(f(\emptyset )=1\) is possible for Boolean functions too. In our context the notion of \(\alpha \)-roughly weightedness makes sense for \(f(\emptyset )=0\), so that we generally require this property.
Complete simple games with one shift-minimal winning vector and more than two equivalence classes of voters can have dimensions larger than two and as large as \(\frac{n}{4}\)Freixas and Puente (2008).
We have to remark that currently SCIP is not capable of solving the stated problem without further information because there are some problems if the intermediate LP relaxations are unbounded. So one has to provide upper and lower bounds for the continuous variables \(u_S\) and \(v_S\).
Since the possible spectrum of determinants is given by \(\{0,\ldots , 40,42,44,45,48,56\}\), see e.g.http://www.indiana.edu/~maxdet/spectrum.html, only \(\frac{45}{44}\) had to be ruled out.
Here the possible spectrum of determinants is given by \(\{0,\ldots ,102,104,105, 108, 110, 112, 116,\) \(117, 120, 125, 128, 144\}\) so that only \(\frac{117}{116}\) might be possible.
References
Algaba E, Bilbao JM, Fernández JR (2007) The distribution of power in the European Constitution. Eur J Oper Res 176(3):1752–1766
Bachrach Y (2011) The least-core of threshold network flow games. In: Murlak F, Sankowski P (eds) Mathematical foundations of computer science 2011. Proceedings of the 36th international symposium, MFCS 2011, Warsaw, Poland, 22–26 August, 2011. Lecture Notes in Computer Science 6907, Springer, Berlin, pp 36–47
Bachrach Y, Elkind E, Meir R, Pasechnik D, Zuckerman M, Rothe J, Rosenschein J (2009) The cost of stability in coalitional games. In: Proceedings of the 2nd international symposium on algorithmic game theory, SAGT ’09, Berlin, Springer, pp 122–134
Berthold T, Gleixner AM, Heinz S, Vigerske S (2011) On the computational impact of MIQCP solver components. ZIB-Report 11–01, Zuse Institute Berlin. http://vs24.kobv.de/opus4-zib/frontdoor/index/index/docId/1199/. Accessed 09 Dec 2013
Berthold T, Heinz S, Vigerske S (2012) Extending a CIP framework to solve MIQCPs. In: Lee J, Leyffer S (eds) Mixed-integer nonlinear optimization: algorithmic advances and applications, IMA volumes in Mathematics and its Applications, vol 154. Springer, pp 427–444
Brenner J, Cummings L (1972) The Hadamard maximum determinant problem. Am Math Mon 79:626–630
Carreras F, Freixas J (1996) Complete simple games. Math Soc Sci 32:139–155
Carreras F, Freixas J (2004) A power analysis of linear games with consensus. Math Soc Sci 48(2):207–221
Craigen R (1990) The range of the determinant function on the set of \(n \times n\) (0,1)- matrices. J Comb Math Comb Comput 8:161–171
Deĭneko VG, Woeginger GJ (2006) On the dimension of simple monotonic games. Eur J Oper Res 170(1):315–318
Diakonikolas I, Servedio R (2013) Improved approximation of linear threshold functions. Comput Complex 22(3):623–677
Felsenthal DS, Machover M (1997) Ternary voting games. Int J Game Theory 26:335–351
Freixas J, Molinero X (2010) Weighted games without a unique minimal representation in integers. Optim Methods Softw 25:203–215
Freixas J, Puente MA (2008) Dimension of complete simple games with minimum. Eur J Oper Res 188(2):555–568
Freixas J, Zwicker W (2003) Weighted voting, abstention, and multiple levels of approval. Soc Choice Welf 21(3):399–431
Granot D, Granot F (1992) On some network flow games. Math Oper Res 17(4):792–841
Gvozdeva T, Hemaspaandra LA, Slinko A (2013) Three hierarchies of simple games parameterized by “resource“ parameters. Int J Game Theory 42(1):1–17. doi:10.1007/s00182-011-0308-4
Gvozdeva T, Slinko A (2011) Weighted and roughly weighted simple games. Math Soc Sci 61(1):20–30
Isbell J (1958) A class of simple games. Duke Math J 25:423–439
Kalai E, Zemel E (1982) Totally balanced games and games of flow. Math Oper Res 7:476–478
Koch T (2004) Rapid mathematical programming. PhD Thesis, Technische Universität Berlin
Kurz S (2012a) On minimum sum representations for weighted voting games. Ann Oper Res 196(1):361–369
Kurz S (2012b) On the inverse power index problem. Optimization 16(8):989–1011
Letchford AN, Galli L (2011) Reformulating mixed-integer quadratically constrained quadratic programs. SIAM J Opt, p 23, submitted. http://www.optimization-online.org/DB_HTML/2011/02/2919.html. Accessed 09 Dec 2013
Metropolis N (1971) Spectra of determinant values in (0,1) matrices. Computers in number theory. In: Proceedings of the atlas symposium, No. 2. Oxford 1969:271–276
Peleg B (1992) Voting by count and account. In: Selten R (ed) Rational interaction. Essays in honor of John C. Harsanyi. Springer, Berlin, pp 45–51
Resnick E, Bachrach Y, Meir R, Rosenschein J (2009) The cost of stability in network flow games. In: Královič R, Niwiński D (eds) Mathematical foundations of computer science 2009. Proceedings of the 34th international symposium, MFCS 2009, Novy Smokovec, High Tatras, Slovakia, 24–28 August, 2009. Lecture notes in computer science 5734, Springer, Berlin, pp 636–650
Storcken T (1997) Effectivity functions and simple games. Int. J Game Theory 26:235–248
Taylor A, Zwicker W (1993) Weighted voting, multicameral representation, and power. Games Econ Behav 5(1):170–181
Taylor AD, Zwicker WS (1999) Simple games. Desirability relations, trading, pseudoweightings. Princeton University Press, Princeton
Tijs S (2011) Introduction to game theory. Texts and readings in mathematics 23, vol viii. Hindustan Book Agency, New Dehli, p 176
Vanderbei R (2008) Linear programming. Foundations and extensions. In: International series in operations Research & Management Science 114, 3rd edn., vol xix. Springer, New York, 464 p
von Neumann J, Morgenstern O (2007) Chapter X: Simple games. In: Kuhn H, A Rubinstein (eds) Theory of games and economic behavior, vol xxxii. Princeton University Press, Princeton, 739 p
Acknowledgments
We would like to thank Tatyana Gvozdeva, Stefan Napel and two anonymous referees for their thoughtful comments that helped very much to improve the presentation of the paper. Josep Freixas author acknowledges the support of the Barcelona Graduate School of Economics and of the Government of Catalonia.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Freixas, J., Kurz, S. On \({\alpha }\)-roughly weighted games. Int J Game Theory 43, 659–692 (2014). https://doi.org/10.1007/s00182-013-0402-x
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00182-013-0402-x