A characterization of weighted voting
HTML articles powered by AMS MathViewer
- by Alan Taylor and William Zwicker PDF
- Proc. Amer. Math. Soc. 115 (1992), 1089-1094 Request permission
Abstract:
A simple game is a structure $G = (N,W)$ where $N = \{ 1, \ldots ,n\}$ and $W$ is an arbitrary collection of subsets of $N$. Sets in $W$ are called winning coalitions and sets not in $W$ are called losing coalitions. $G$ is said to be a weighted voting system if there is a function $w:N \to \mathbb {R}$ and a "quota" $q \in \mathbb {R}$ so that $X \in W$ iff $\sum {\{ w(x):x \in X\} \geq q}$. Weighted voting systems are the hypergraph analogue of threshold graphs. We show here that a simple game is a weighted voting system iff it never turns out that a series of trades among (fewer than ${2^{{2^n}}}$ not necessarily distinct) winning coalitions can simultaneously render all of them losing. The proof is a self-contained combinatorial argument that makes no appeal to the separating of convex sets in ${\mathbb {R}^n}$ or its algebraic analogue known as the Theorem of the Alternative.References
-
S. J. Brams, Rational politics, Congressional Quarterly Press, Washington, 1985.
- Václav Chvátal and Peter L. Hammer, Aggregation of inequalities in integer programming, Studies in integer programming (Proc. Workshop, Bonn, 1975) Ann. of Discrete Math., Vol. 1, North-Holland, Amsterdam, 1977, pp. 145–162. MR 0479384
- E. Einy and E. Lehrer, Regular simple games, Internat. J. Game Theory 18 (1989), no. 2, 195–207. MR 1012448, DOI 10.1007/BF01268159
- P. L. Hammer, T. Ibaraki, and U. N. Peled, Threshold numbers and threshold completions, Studies on graphs and discrete programming (Brussels, 1979) Ann. Discrete Math., vol. 11, North-Holland, Amsterdam-New York, 1981, pp. 125–145. MR 653822
- J. R. Isbell, A class of majority games, Quart. J. Math. Oxford Ser. (2) 7 (1956), 183–187. MR 97027, DOI 10.1093/qmath/7.1.183
- Uri N. Peled, Matroidal graphs, Discrete Math. 20 (1977/78), no. 3, 263–286. MR 505874, DOI 10.1016/0012-365X(77)90175-3
- L. S. Shapley, Simple games: an outline of the descriptive theory, Behavioral Sci. 7 (1962), 59–66. MR 136457, DOI 10.1002/bs.3830070104 A. Taylor and W. Zwicker, Threshold hypergraphs, simple voting games, and magic squares, preprint. —, Weighted voting, multicameral representation, and power, preprint.
- John von Neumann and Oskar Morgenstern, Theory of Games and Economic Behavior, Princeton University Press, Princeton, N.J., 1944. MR 0011937
- Douglas B. West, Parameters of partial orders and graphs: packing, covering, and representation, Graphs and order (Banff, Alta., 1984) NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., vol. 147, Reidel, Dordrecht, 1985, pp. 267–350. MR 818499
Additional Information
- © Copyright 1992 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 115 (1992), 1089-1094
- MSC: Primary 90A28
- DOI: https://doi.org/10.1090/S0002-9939-1992-1092927-0
- MathSciNet review: 1092927