×

Stable families of coalitions and normal hypergraphs. (English) Zbl 0915.90277

Summary: The core of a game is defined as the set of outcomes acceptable for all coalitions. This is probably the simplest and most natural concept of cooperative game theory. However, the core can be empty because there are too many coalitions. Yet, some players may not like or know each other, so they cannot form a coalition. The following generalization seems natural. Let \({\mathcal K}\) be a fixed family of coalitions. The \({\mathcal K}\)-core is defined as the set of outcomes acceptable for all the coalitions from \({\mathcal K}\). Let us call a family \({\mathcal K}\) \(g\)-stable if the \({\mathcal K}\)-core is not empty for any finite normal form game, and similarly, let \({\mathcal K}\) be called \(V\)-stable if the \({\mathcal K}\)-core is not empty for any compact superadditive NTU-game. We prove that both \(V\)- and \(g\)-stability of a family \({\mathcal K}\) are equivalent with the normality of \({\mathcal K}\). Normal hypergraphs can be characterized by several equivalent properties, e.g. they are dual to clique hypergraphs of perfect graphs.

MSC:

91A12 Cooperative games
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aharoni, R., Hajnal, A., Milner E.C., 1994. Interval covers of a linearly ordered set. Manuscript.; Aharoni, R., Hajnal, A., Milner E.C., 1994. Interval covers of a linearly ordered set. Manuscript. · Zbl 0834.06002
[2] Berge, C., 1970. Graphes et Hypergraphes. Dunod, Paris, 1970. English translation: Graphs and Hypergraphs. North-Holland, Amsterdam, 1973.; Berge, C., 1970. Graphes et Hypergraphes. Dunod, Paris, 1970. English translation: Graphs and Hypergraphs. North-Holland, Amsterdam, 1973.
[3] Berge, C., Duchet, P., 1983. Seminaire MSH, Paris, Jan 1983.; Berge, C., Duchet, P., 1983. Seminaire MSH, Paris, Jan 1983.
[4] Bondareva, O.N., 1962. The core of \(N\); Bondareva, O.N., 1962. The core of \(N\) · Zbl 0122.15404
[5] Bondareva, O.N., 1963. Some applications of linear programming methods to the theory of cooperative games. Problemy Kibernetiki 10, 119-139 (in Russian).; Bondareva, O.N., 1963. Some applications of linear programming methods to the theory of cooperative games. Problemy Kibernetiki 10, 119-139 (in Russian). · Zbl 1013.91501
[6] Boros, E., Gurvich, V., 1994. Perfect graphs are kernel-solvable. Rutcor Research Report 16-1994, Discrete Mathematics 159, (1996) 35-55.; Boros, E., Gurvich, V., 1994. Perfect graphs are kernel-solvable. Rutcor Research Report 16-1994, Discrete Mathematics 159, (1996) 35-55. · Zbl 0861.05053
[7] Danilov, V., Sotskov, A., 1992. Generalized convexity: some fixed point theorems and their applications. CEPREMAP, Preprint, N 9213.; Danilov, V., Sotskov, A., 1992. Generalized convexity: some fixed point theorems and their applications. CEPREMAP, Preprint, N 9213.
[8] Demange, G., 1990. Intermediate preferences and stable coalition structures. Laboratorie d’Econometrie de l’Ecole Polytechnique. Preprint.; Demange, G., 1990. Intermediate preferences and stable coalition structures. Laboratorie d’Econometrie de l’Ecole Polytechnique. Preprint. · Zbl 0791.90078
[9] Farkas, J., Über die Theorie der Einfachen Ungleichungen, J. Reine und Angewandte Math., 124, 1-27 (1902) · JFM 32.0169.02
[10] Greenberg, J., Weber, S., 1986. Strong Tiebout equilibrium under restricted preferences domain. Journal Econ. Theory 38 (1986) 101-117.; Greenberg, J., Weber, S., 1986. Strong Tiebout equilibrium under restricted preferences domain. Journal Econ. Theory 38 (1986) 101-117. · Zbl 0592.90017
[11] Gurvich, V.A., Vasin, A.A., 1977. Reconcilable sets of coalitions. In: Questions of applied math. Sibirian Energetic Inst. Irkutsk, 1977, pp. 20-30 (in Russian). Author’s abstract in English. Math. Rev. 81b:90172.; Gurvich, V.A., Vasin, A.A., 1977. Reconcilable sets of coalitions. In: Questions of applied math. Sibirian Energetic Inst. Irkutsk, 1977, pp. 20-30 (in Russian). Author’s abstract in English. Math. Rev. 81b:90172.
[12] Gurvich, V.A., Vasin, A.A., 1978a. Reconcilable sets of coalitions for normal form games. In: Numerical methods in optimization theory (Appl. math.). Sibirian Energetic Inst. Irkutsk, 1978, pp. 27-38 (in Russian). Author’s abstract in English. Math. Rev. 81j:90147.; Gurvich, V.A., Vasin, A.A., 1978a. Reconcilable sets of coalitions for normal form games. In: Numerical methods in optimization theory (Appl. math.). Sibirian Energetic Inst. Irkutsk, 1978, pp. 27-38 (in Russian). Author’s abstract in English. Math. Rev. 81j:90147.
[13] Gurvich, V.A., Vasin, A.A., 1978b. On Reconcilable sets of coalitions, 3-rd USSR Conference on Operation Research, Gorky, 1978, Abstract, pp. 353-354 (in Russian).; Gurvich, V.A., Vasin, A.A., 1978b. On Reconcilable sets of coalitions, 3-rd USSR Conference on Operation Research, Gorky, 1978, Abstract, pp. 353-354 (in Russian).
[14] Gurvich, V.A., Menschikov, I.S., 1989. Institutions of agreement. In: Knowledge, News in the life, science and technics, serie Mathematics and Cybernetics 6, subsection 12.3 (1989) (in Russian).; Gurvich, V.A., Menschikov, I.S., 1989. Institutions of agreement. In: Knowledge, News in the life, science and technics, serie Mathematics and Cybernetics 6, subsection 12.3 (1989) (in Russian).
[15] Aharoni, R., Holzman, R., 1995. Fractional kernels in digraphs. Manuscript (1995), Dep. of Math., Technion, Haifa. To appear in J. Combinatorial Theory.; Aharoni, R., Holzman, R., 1995. Fractional kernels in digraphs. Manuscript (1995), Dep. of Math., Technion, Haifa. To appear in J. Combinatorial Theory. · Zbl 0904.05036
[16] Keiding, H., Necessary and sufficient conditions for stability of effectivity functions, International Journal of Game Theory, 14, 93-101 (1985) · Zbl 0567.90101
[17] Kaneko, M.; Wooders, M. H., Cores of partitioning games, Mathematical Social Sciences, 3, 313-327 (1982) · Zbl 0493.90089
[18] Kuipers, J., 1994. Combinatorial methods in cooperative game theory. Ph.D. Dissertation, Maastricht University, 1994.; Kuipers, J., 1994. Combinatorial methods in cooperative game theory. Ph.D. Dissertation, Maastricht University, 1994.
[19] Le Breton, M.; Owen, G.; Weber, S., Strongly balanced cooperative games, International Journal of Game Theory, 21, 419-427 (1992) · Zbl 0763.90103
[20] Lovász, L., Normal hypergraphs and the weak perfect graph conjecture, Discrete Math., 2, 3, 253-267 (1972) · Zbl 0239.05111
[21] Moulin, H.; Peleg, B., Cores of effectivity functions and implementation theory, J. of Mathematical Economics, 10, 115-145 (1982) · Zbl 0481.90004
[22] von Neumann, J., Morgenstern, O., 1944. Theory of games and economic behaviour, subsection 157.2,3. Princeton University Press, Princeton, 1944.; von Neumann, J., Morgenstern, O., 1944. Theory of games and economic behaviour, subsection 157.2,3. Princeton University Press, Princeton, 1944.
[23] Quint, T., Necessary and sufficient conditions for balancedness in partitioning games, Mathematical Social Sciences, 22, 87-91 (1991) · Zbl 0744.90111
[24] Quint, T., 1994. Restricted houswapping games. Mimeo, Yale University, 1994.; Quint, T., 1994. Restricted houswapping games. Mimeo, Yale University, 1994.
[25] Scarf, H., The core of \(n\) person game, Econometrica, 35, 1, 50-59 (1967) · Zbl 0183.24003
[26] Shapley, L.S., 1965. On balanced sets and cores. RAND corporation, RM-4601-PR, 1965.; Shapley, L.S., 1965. On balanced sets and cores. RAND corporation, RM-4601-PR, 1965.
[27] Shapley, L. S., On balanced sets and cores, Naval Research Logistics Quarterly, 14, 453-460 (1967)
[28] Shapley, L. S.; Shubik, M., The assignment game. I: The core, International Journal of Game Theory, 1, 111-130 (1972) · Zbl 0236.90078
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.