Abstract
An equivalence between simplen-person cooperative games and linear integer programs in 0–1 variables is presented and in particular the nucleolus and kernel are shown to be special valid inequalities of the corresponding 0–1 program. In the special case of weighted majority games, corresponding to knapsack inequalities, we show a further class of games for which the nucleolus is a representation of the game, and develop a single test to show when payoff vectors giving identical amounts or zero to each player are in the kernel. Finally we give an algorithm for computing the nucleolus which has been used successfully on weighted majority games with over twenty players.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aumann, R. J., B. Peleg, andP. Rabinowitz: A method for computing the kernel ofn-person games. Mathematics of Computation19 (92), 1965, 531–551.
Balas, E.: Facets of the knapsack polytope. Mathematical Programming8, 1975, 146–164.
Bradley, G. H., P. L. Hammer, andL. A. Wolsey: Coefficient reduction for inequalities in 0–1 variables. Mathematical Programming7, 1974, 263–282.
Hammer, P. L., E. L. Johnson, andU. N. Peled: Facet of regular 0–1 polytopes. Mathematical Programming8, 1975, 179–206.
Isbell, J. R.: A class of majority games. Quarterly Journal Math. Oxford Ser.,7, 1956, 183–187.
Kohlberg, E.: On the nucleolus of a characteristic function game. SIAM App. Math,20 (1), 1971, 62–66.
Kopelowitz, A.: Computation of the kernel of simple games and the nucleolus ofN-person games. Research Program in Game Theory and Mathematical Economies, Dept. of Math., The Hebrew University of Jerusalem, RM 31, 1967.
Maschler, M.: Bibliography on the theory of the bargaining sets, VIIIth International Symposium on Mathematical Programming, Stanford, August 1973.
Maschler, M., andB. Peleg: A characterization, existence proof and dimension bounds for the kernel of a game. Pacific J. Math.18, 1966, 289–328.
Muroga, S.: Threshold Logic and its Applications. New York 1971.
Peleg, B.: On the kernel of constant sum simple games with homogeneous weights. Illinois J. Math.10, 1966, 39–48.
—: On weights of constant sum majority games. SIAM App. Math.16 (3), 1968, 527–532.
Wolsey, L. A.: Generalized dynamic programming methods in integer programming. Mathematical Programming4, 1973, 222–232.
—: Faces for linear inequalities in 0–1 variables. Mathematical Programming8, 1975a, 165–178.
-: Valid Inequalities, Covering Problems and Discrete Dynamic Programs, CORE Discussion Paper No 7526, Louvain 1975b.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Wolsey, L.A. The nucleolus and kernel for simple games or special valid inequalities for 0–1 linear integer programs. Int J Game Theory 5, 227–238 (1976). https://doi.org/10.1007/BF01761605
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01761605