Abstract
In this paper we deal with several classes of simple games; the first class is the one of ordered simple games (i.e. they admit of a complete desirability relation). The second class consists of all zero-sum games in the first one.
First of all we introduce a “natural” partial order on both classes respectively and prove that this order relation admits a rank function. Also the first class turns out to be a rank symmetric lattice. These order relations induce fast algorithms to generate both classes of ordered games.
Next we focus on the class of weighted majority games withn persons, which can be mapped onto the class of weighted majority zero-sum games withn+1 persons.
To this end, we use in addition methods of linear programming, styling them for the special structure of ordered games. Thus, finally, we obtain algorithms, by combiningLP-methods and the partial order relation structure. These fast algorithms serve to test any ordered game for the weighted majority property. They provide a (frequently minimal) representation in case the answer to the test is affirmative.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aumann RJ, Peleg B, Rabinowitz P (1965) A method for computing the kernel ofn-person games. Mathematics of Computation 19:531–551
Brickmann L (1989) Mathematical introduction to linear programming and game theory. Springer-Verlag New York
Dubey P, Shapley LS (1978) Mathematical properties of the banzhaf power index. The Rand Corporation 99-31
Einy E (1985) The desirability relation of simple games. Math Social Sc 10:155–168
Einy E, Lehrer E (1989) Regular simple games. Int Journal of Game Theory 18:195–208
Engel K, Gronau HD (1985) Sperner theory in partially ordered sets. Teubner Verlag Leipzig
Erdös P (1965) Extremal problems in number theory. Theory of numbers. Whiteman AL (Ed) Amer Math Soc Proc Symp Pure Math 8:181–189
Euler L (1750) De partitione numerorum. Commentationes Arithmeticae
Isbell JR (1959) On the enumeraton of majority games. Math Tables Aids Comput 13:21–28
Kopelowitz A (1967) Computation of the kernel of simple games and the nucleolus ofn-person games. Research program in game theory and math economics. Dept of Math The Hebrew University of Jerusalem RM 31
Maschler M, Peleg B (1966) A characterization, existence proof and dimension bounds for the kernel of a game. Pacific J Math 18:289–328
Maschler M, Peleg B, Shapley LS (1979) Geometric properties of the kernel, nucleolus and related solution concepts. Math of Operations Research 4:303–338
von Neumann J, Morgenstern O (1944) Theory of games and economic behavior. Princeton University Press New Jersey
Ostmann A (1987) Life-length of a process with elements of decreasing importance. Working Paper 156 Inst of Math ec University of Bielefeld
Ostmann A (1987a) On the minimal representation of homogeneous games. Int Journal of Game Theory 16:69–81
Ostmann A (1989) Simple games: On order and Symmetrie. Working Paper 169 Inst of Math University of Bielefeld
Peleg B (1968) On weights of constant-sum majority games. SIAM J of Appl Math 16:527–532
Peleg B, Rosenmüller J (1992) The least-core, nucleolus, and kernel of homogeneous weighted majority games. Games and Economic Behaviour 4:588–605
Peleg B, Rosenmüller J, Sudhölter P (1994) The kernel of homogeneous games with steps. Essays in game theory in honor of Michael Maschler, Jerusalem. Nimrod M (ed) 163–192
Proctor RA (1982a) Representations of sl (2, ℂ) on posets and the sperner property. SIAM J Algebraic Discrete Methods 3:275–280
Proctor RA (1982b) Solution of two difficult combinatorial problems with linear algebra. The American Mathematical Monthly 89:721–734
Rosenmüller J (1981) The theory of games and markets. North Holland Publ Comp
Rosenmüller (1987) Homogeneous games: Recursive structure and computation. Math of Operations Research 12:309–330
Rosenmüller J, Sudhölter P (1994) The nucleolus of homogeneous games with steps. Discrete Applied Mathematics 50:53–76
Schmeidler D (1966) The nucleolus of a characteristic function game. Research program in game theory and math economics. The Hebrew University of Jerusalem RM 23
Shapley LS (1962) Simple games: An outline of the descriptive theory. Behavioral Sci 7:59–66
Stanley RP (1980) Weyl groups, the hard lefschetz theorem, and the sperner property. SIAM J Algebraic Discrete Methods 1:168–184
Sudhölter P (1989) Homogeneous games as anti step functions. Int Journal of Game Theory 18: 433–469
Wolsey LA (1976) The nucleolus and kernel of simple games or special valid inequalities for 0–1 linear integer programs. Int Journal of Game Theory 5:227–238
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Krohn, I., Sudhölter, P. Directed and weighted majority games. ZOR - Methods and Models of Operations Research 42, 189–216 (1995). https://doi.org/10.1007/BF01415753
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01415753