Abstract
In cooperative game theory, a characterization of games with stable cores is known as one of the most notorious open problems. We study this problem for a special case of the minimum coloring games, introduced by Deng, Ibaraki & Nagamochi, which arises from a cost allocation problem when the players are involved in conflict. In this paper, we show that the minimum coloring game on a perfect graph has a stable core if and only if every vertex of the graph belongs to a maximum clique. We also consider the problem on the core largeness, the extendability, and the exactness of minimum coloring games.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Biswas, A.K., Parthasarathy, T., Potters, J.A.M., Voorneveld, M.: Large cores and exactness. Games and Economic Behavior 28, 1–12 (1999)
Chudnovsky, M., Seymour, P.: Recognizing Berge graphs (Submitted)
Corneil, D.G., Perl, Y.: Clustering and domination in perfect graphs. Discrete Applied Mathematics 9, 27–39 (1984)
Cornuéjols, G., Liu, X., Vus̆ković, K.: A polynomial algorithm for recognizing perfect graphs. In: Proc. 44th FOCS, pp. 20–27 (2003)
Curiel, I.J.: Cooperative Game Theory and Applications: Cooperative Games Arising from Combinatorial Optimization Problems. Kluwer Academic Publishers, Dordrecht (1997)
Deng, X., Ibaraki, T., Nagamochi, H.: Algorithmic aspects of the core of combinatorial optimization games. Math. Oper. Res. 24, 751–766 (1999)
Deng, X., Ibaraki, T., Nagamochi, H., Zang, W.: Totally balanced combinatorial optimization games. Math. Program. 87, 441–452 (2000)
Deng, X., Papadimitriou, C.H.: On the complexity of cooperative solution concepts. Math. Oper. Res. 19, 257–266 (1994)
Farber, M.: Independent domination in chordal graphs. Oper. Res. Lett. 1, 134–138 (1982)
Fulkerson, D.R., Gross, O.A.: Incidence matrices and interval graphs. Pacific J. Math. 15, 835–855 (1965)
Gillies, D.B.: Some theorems on n-person games. Ph.D. Thesis. Princeton University, Princeton (1953)
Grötschel, M., Lovász, L., Schrijver, A.: Geometric algorithms and combinatorial optimization, 2nd edn. Springer, Berlin (1993)
Kikuta, K., Shapley, L.S.: Core stability in n-person games. (1986) (Manuscript)
Kratsch, D.: Algorithms. In: Haynes, T.W., Hedetniemi, S.T., Slater, P.J. (eds.) Domination in Graphs (Advanced Topics), pp. 191–231. Marcel Dekker Inc., New York (1998)
Kratsch, D., Stewart, L.: Domination on cocomparability graphs. SIAM J. Discrete Math. 6, 400–417 (1993)
Lovász, L.: Normal hypergraphs and the perfect graph conjecture. Discrete Math. 2, 253–267 (1972)
Okamoto, Y.: Submodularity of some classes of the combinatorial optimization games. Math. Methods Oper. Res. 58, 131–139 (2003)
Okamoto, Y.: Fair cost allocations under conflicts — A game-theoretic point of view —. In: Ibaraki, T., Katoh, N., Ono, H. (eds.) ISAAC 2003. LNCS, vol. 2906, pp. 686–695. Springer, Heidelberg (2003)
Schmeidler, D.: Cores of exact games I. J. Math. Anal. Appl. 40, 214–225 (1972)
Shapley, L.S.: Cores of convex games. Internat. J. Game Theory 1, 11–26 (1971); Errata is in the same volume, pp. 199 (1972)
Sharkey, W.W.: Cooperative games with large cores. Internat. J. Game Theory 11, 175–182 (1982)
Solymosi, T., Raghavan, T.E.S.: Assignment games with stable cores. Internat. J. Game Theory 30, 177–185 (2001)
van Gellekom, J.R.G., Potters, J.A.M., Reijnierse, J.H.: Prosperity properties of TU-games. Internat. J. Game Theory 28, 211–227 (1999)
von Neumann, J., Morgenstern, O.: Theory of Games and Economic Behaviour. Princeton University Press, Princeton (1944)
Zverovich, I.E.: Independent domination on 2P 3-free perfect graphs. DIMACS Technical Report 2003-22 (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bietenhader, T., Okamoto, Y. (2004). Core Stability of Minimum Coloring Games. In: Hromkovič, J., Nagl, M., Westfechtel, B. (eds) Graph-Theoretic Concepts in Computer Science. WG 2004. Lecture Notes in Computer Science, vol 3353. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30559-0_33
Download citation
DOI: https://doi.org/10.1007/978-3-540-30559-0_33
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-24132-4
Online ISBN: 978-3-540-30559-0
eBook Packages: Computer ScienceComputer Science (R0)