Core stability of dominating set games
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
In this paper, we study the core stability of the dominating set game which has arisen from the cost allocation problem related to domination problem on graphs. Let G be a graph whose neighborhood matrix is balanced. Applying duality theory of linear programming and graph theory, we prove that the dominating set game corresponding to G has the stable core if and only if every vertex belongs to a maximum 2- packing in G. We also show that for dominating set games corresponding to G, the core is stable if it is large, the game is extendable, or the game is exact. In fact, the core being large, the game being extendable and the game being exact are shown to be equivalent.
Abstract
In this paper, we study the core stability of the dominating set game which has arisen from the cost allocation problem related to domination problem on graphs. Let G be a graph whose neighborhood matrix is balanced. Applying duality theory of linear programming and graph theory, we prove that the dominating set game corresponding to G has the stable core if and only if every vertex belongs to a maximum 2- packing in G. We also show that for dominating set games corresponding to G, the core is stable if it is large, the game is extendable, or the game is exact. In fact, the core being large, the game being extendable and the game being exact are shown to be equivalent.
참고문헌 (14)
- T. Bietenhader, "Core Stability of Minimum Coloring Games, Graphtheoretic concepts in computer science", Lecture Notes in Computer Science, 3353, pp.389~401 (2004), Springer
- X. Deng, "Algorithmic aspects of the core of combinatorial optimization games", Mathematics of Operations Research, 24(3), pp.751~766 (1999)
- X. Deng, "On the complexity of cooperative solution concepts", Mathematics of Operations Research, 19(2), pp.257~266 (1994)
- Applications of LP Duality to Problems Involving Independence and Domination, Technical Report, Department of Computer Science, "M. Farber", Simon Fraser University, ~ (1981)
- D. Fulkerson, "On balanced matrices, Pivoting and extensions", mathematical programming studies, 1, pp.120~132 (1974)
- K. Kikuta, "Core Stability in n-person Games" (1986), Manuscript
- 김혜경, "Balancedness of Integer Domination Games", 대한수학회보, 43(2), pp.297~309 (2006), 대한수학회
- A. Lubiw, "¡-free matrices", 석사, Department of Combinatorics and Optimization, pp.1982
- L. S. Shapley, "Cores of convex games", International Journal of Game Theory, 1, pp.11~26 (1971)
- W. W. Sharkey, "Cooperative games with large cores", International Journal of Game Theory, 11(3), pp.175~182 (1982)
- T. Solymosi, "Assignment games with stable core", International Journal of Game Theory, 30(2), pp.177~185 (2001)
- J. R. G. van Gellekom, "Prosperity properties of TU-games", International Journal of Game Theory, 28(2), pp.211~227 (1999)
- B. van Velzen, "Dominating set games", Operations Research Letters, 32(6), pp.565~573 (2004)
- J. von Neumann, "Theory of Games and Economic Behavior" (1944), Princeton University Press