Algorithms for core stability, core largeness, exactness, and extendability of flow games

Abstract

We study core stability and some related properties of flow games defined on simple networks (all edge capacities are equal) from an algorithmic point of view. We first present a sufficient and necessary condition that can be tested efficiently for a simple flow game to have a stable core. We also prove the equivalence of the properties of core largeness, extendability, and exactness of simple flow games and provide an equivalent graph theoretic characterization which allows us to decide these properties in polynomial time.

Keywords

Flow network / series-parallel graph / imputation / cooperative game

References

[1] Bietenhader T, Okamoto Y. Core stability of minimum coloring games. In: Proceedings of 30th International Workshop on Graph-Theoretic Concept in Computer Science. Lecture Notes in Computer Science, Vol 3353. 2004, 389–401

[2] Biswas A. K., Parthasarathy T., Potters J. A. M., Voorneveld M. Large cores and exactness. Game and Economic Behavior, 1999, 28: 1-12.

[3] Deng X., Ibaraki T., Nagamochi H. Algorithmic aspects of the core of combinatorial optimization games. Mathematics of Operations Research, 1999, 24: 751-766.

[4] Deng X, Fang Q, Sun X. Finding nucleolus of flow game. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’06). 2006, 124–131

[5] Deng X., Papadimitriou C. H. On the complexity of cooperative solution concepts. Mathematics of Operations Research, 1994, 19: 257-266.

[6] Duffin R. Topology of series-parallel networks. Journal of Mathematical Analysis and Applications, 1965, 10: 303-318.

[7] Even S., Tarjan R. E. Network flow and testing graph connectivity. SIAM J Comput, 1975, 4: 507-518.

[8] Fang Q, Fleischer R, Li J, Sun X. Algorithms for core stability, core largeness, exactness and extendability of flow games. In: Proceedings of the 13th Annual International Computing and Combinatorics Conference. 2007, 439–447

[9] Fang Q., Zhu S., Cai M., Deng X. Membership for core of LP games and other games. Lecture Notes in Computer Science, 2001, 2108: 247-256.

[10] Ford L. R., Fulkerson D. R. Flows in Networks, 1962, Princeton: Princeton University Press.

[11] van Gellekom J. R. G., Potters J. A. M., Reijnierse J. H. Prosperity properties of TUgames. International Journal of Game Theory, 1999, 28: 211-227.

[12] Jakoby A., Liskiewicz M., Reischuk R. Space efficient algorithms for directed seriesparallel graphs. Journal of Algorithms, 2006, 60: 85-114.

[13] Kalai E., Zemel E. Totally balanced games and games of flow. Mathematics of Operations Research, 1982, 7: 476-478.

[14] Kalai E., Zemel E. Generalized network problems yielding totally balanced games. Operations Research, 1982, 30: 998-1008.

[15] Lucas W. F. A game with no solution. Bulletin of the American Mathematical Society, 1968, 74: 237-239.

[16] von Neumann J., Morgenstern O. Theory of Games and Economic Behaviour, 1944, Princeton: Princeton University Press.

[17] Schrijver A. Combinatorial Optimization: Polyhedra and Efficiency, 2003, Berlin: Springer-Verlag.

[18] Shapley L. S. Cores and convex games. International Journal of Game Theory, 1971, 1: 11-26.

[19] Sharkey W. W. Cooperative games with large cores. International Journal of Game Theory, 1982, 11: 175-182.

[20] Solymosi T., Raghavan T. E. S. Assignment games with stable cores. International Journal of Game Theory, 2001, 30: 177-185.

[21] Sun X, Fang Q. Core stability of flow games. In: Proceedings of the 2005 China-Japan Conference on Discrete Geometry, Combinatorics and Graph Theory. 2007, 189–199

[22] Tholey T. Solving the 2-disjoint paths problem in nearly linear time. Theory of Computing Systems, 2006, 39: 51-78.

[23] Valdes J, Tarjan R E, Lawler E L. The recognition of series-parallel digraphs. In: Proceedings of the 11th Annual ACM Symposium on Theory of Computing (STOC’79). 1979, 1–12