Abstract
Hierarchical simple games—both disjunctive and conjunctive—are natural generalizations of \(k\)-out-of-\(n\) games. They are ideal in the sense that they allow most efficient and secure secret sharing schemes to be defined on these games as access structures. Another important generalization of \(k\)-out-of-\(n\) games with origin in economics and politics are weighted and roughly weighted majority games. Weighted hierarchical games have been classified by Beimel et al. (SIAM J Discret Math 22(1):360–397, 2008) and Gvozdeva et al. (Math Soc Sci. doi:10.1016/j.mathsocsci.2012.11.007, 2012); it appeared that they cannot have more than two nontrivial levels in their hierarchy. In this paper we characterize roughly weighted hierarchical games and show that they cannot have more than three nontrivial levels. This shows that hierarchical games are rather far from weighted and even roughly weighted games, and hence provide an interesting set of examples for the theory of simple games. Our methods are purely game-theoretic.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
In some earlier papers (see e.g., Shapley 1962) some additional assumptions are imposed like \(P\in W\) and \(\emptyset \notin W\), however these assumptions cause difficulties in treatment of subgames and reduced games.
References
Baugh C (1970) Pseudo-threshold Logic: A Generalization of Threshold Logic Department of Computer Science, University of Illinois
Beimel A (2011) Secret-Sharing Schemes: A Survey In Coding and Cryptology, Third Interna- tional Workshop iwcc 2011 (pp. 11–46). Springer-Verlag, Lecture Notes in Computer Science #6639
Beimel A, Tassa T, Weinreb E (2008) Characterizing ideal weighted threshold secret sharing. SIAM J. Discrete Math. 22(1):360–397
Brickell E (1989) Some ideal secret sharing schemes. J. Combin. Math. and Combin. Comput. 9:105–113
Carreras F, Freixas J (1996) Complete simple games. Math. Soc. Sci. 32(2):139–155
Gvozdeva T, Hameed A, Slinko A (2012) Weightedness and structural characterization of hierarchical simple games. Math. Soc. Sci., Online First 1–9. (doi:10.1016/j.mathsocsci.2012.11.007)
Gvozdeva T, Hemaspaandra L, Slinko A (2011) Three hierarchies of simple games parameterized by “resource” parameters. Int. J. Game Theory, Online First 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
Krohn I, Sudhölter P (1995) Directed and weighted majority games. Zeitschrift für Operations Research 42:189–216
Muroga S (1971) Threshold logic and its applications. New York: Wiley-Interscience [John Wiley & Sons]
Shamir A (1979) How to share a secret. Commun. ACM 22:612–613
Shapley LS (1962) Simple games: An outline of the descriptive theory. Behavioral Science 7(1):59–66
Simmons GJ (1990) How to (really) share a secret. In Proceedings on Advances in cryptology Proceedings on advances in cryptology (pp. 390–448) New York, NY, USA:Springer-Verlag New York Inc
Stinson D (1992) An explication of secret sharing schemes. Design Code Cryptogr. 2:357–390
Tassa T (2007) Hierarchical threshold secret sharing. J. Cryptol. 20:237–264
Taylor A, Zwicker W (1999) Simple games. Princeton University Press,
von Neumann J, Morgenstern O (1944) Theory of games and economic behavior. Princeton University Press,
Acknowledgments
We are grateful for the very useful comments of the two anonymous referees. We are also grateful to Bill Zwicker and Tanya Gvozdeva and all participants of the Summer Workshop of The Centre for Mathematics in Social Science (Auckland, December, 13–22, 2010) for their advice and useful comments.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Hameed, A., Slinko, A. Roughly weighted hierarchical simple games. Int J Game Theory 44, 295–319 (2015). https://doi.org/10.1007/s00182-014-0430-1
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00182-014-0430-1