|
|
|
Algorithms for core stability, core largeness,
exactness, and extendability of flow games |
| Qizhi FANG1,Rudolf FLEISCHER2,Jian LI3,Xiaoxun SUN4, |
| 1.Department of Mathematics,
Ocean University of China, Qingdao 266100, China; 2.Department of Computer
Science and Engineering, Fudan University, Shanghai 200433, China; 3.Department of Computer
Science, University of Maryland, College Park, MD 20742, USA; 4.Department of Mathematics
and Computing, University of Southern Queensland, Toowoomba QLD 4350,
Australia; |
|
|
|
|
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
|
|
Issue Date: 05 March 2010
|
|
|
Bietenhader T, Okamoto Y. Core stability of minimumcoloring games. In: Proceedings of 30th InternationalWorkshop on Graph-Theoretic Concept in Computer Science. Lecture Notes in Computer Science, Vol 3353. 2004, 389―401
|
|
Biswas A K, Parthasarathy T, Potters J A M, Voorneveld M. Largecores and exactness. Game and EconomicBehavior, 1999, 28: 1―12
doi: 10.1006/game.1998.0686
|
|
Deng X, Ibaraki T, Nagamochi H. Algorithmic aspects of the core of combinatorial optimizationgames. Mathematics of Operations Research, 1999, 24: 751―766
doi: 10.1287/moor.24.3.751
|
|
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
|
|
Deng X, Papadimitriou CH. On the complexityof cooperative solution concepts. Mathematicsof Operations Research, 1994, 19: 257―266
doi: 10.1287/moor.19.2.257
|
|
Duffin R. Topologyof series-parallel networks. Journal ofMathematical Analysis and Applications, 1965, 10: 303―318
doi: 10.1016/0022-247X(65)90125-3
|
|
Even S, Tarjan R E. Network flow and testinggraph connectivity. SIAM J Comput, 1975, 4: 507―518
doi: 10.1137/0204043
|
|
Fang Q, Fleischer R, Li J, Sun X. Algorithmsfor core stability, core largeness, exactness and extendability offlow games. In: Proceedings of the 13thAnnual International Computing and Combinatorics Conference. 2007, 439―447
|
|
Fang Q, Zhu S, Cai M, Deng X. Membershipfor core of LP games and other games. In: Lecture Notes in Computer Science, Vol 2108. 2001, 247―256
|
|
Ford L R, Fulkerson D R. Flows in Networks. Princeton: Princeton University Press, 1962
|
|
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
doi: 10.1007/s001820050106
|
|
Jakoby A, Liskiewicz M, Reischuk R. Space efficient algorithms for directed seriesparallelgraphs. Journal of Algorithms, 2006, 60: 85―114
doi: 10.1016/j.jalgor.2004.06.010
|
|
Kalai E, Zemel E. Totally balanced games andgames of flow. Mathematics of OperationsResearch, 1982, 7: 476―478
doi: 10.1287/moor.7.3.476
|
|
Kalai E, Zemel E. Generalized network problemsyielding totally balanced games. OperationsResearch, 1982, 30: 998―1008
doi: 10.1287/opre.30.5.998
|
|
Lucas W F. A game with no solution. Bulletin of theAmerican Mathematical Society, 1968, 74: 237―239
doi: 10.1090/S0002-9904-1968-11901-9
|
|
von Neumann J, Morgenstern O. Theory of Games and EconomicBehaviour. Princeton: Princeton University Press, 1944
|
|
Schrijver A. CombinatorialOptimization: Polyhedra and Efficiency. Berlin: Springer-Verlag, 2003
|
|
Shapley L S. Cores and convex games. InternationalJournal of Game Theory, 1971, 1: 11―26
doi: 10.1007/BF01753431
|
|
Sharkey W W. Cooperative games with large cores. InternationalJournal of Game Theory, 1982, 11: 175―182
doi: 10.1007/BF01755727
|
|
Solymosi T, Raghavan T E S. Assignment games with stablecores. International Journal of Game Theory, 2001, 30: 177―185
doi: 10.1007/s001820100072
|
|
Sun X, Fang Q. Core stability of flow games. In: Proceedings of the 2005 China-Japan Conferenceon Discrete Geometry, Combinatorics and Graph Theory. 2007, 189―199
|
|
Tholey T. Solvingthe 2-disjoint paths problem in nearly linear time. Theory of Computing Systems, 2006, 39: 51―78
doi: 10.1007/s00224-005-1256-9
|
|
Valdes J, Tarjan R E, Lawler E L. The recognition of series-parallel digraphs. In: Proceedings of the 11th Annual ACM Symposiumon Theory of Computing (STOC’79). 1979, 1―12
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
