TY - GEN
T1 - Membership for core of LP games and other games
AU - Fang, Qizhi
AU - Zhu, Shanfeng
AU - Cai, Maocheng
AU - Deng, Xiaotie
N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].
PY - 2001
Y1 - 2001
N2 - Let Γ ≡ (N, v) be a cooperative game with the player set N and characteristic function v: 2N → R. An imputation of the game is in the core if no subset of players could gain advantage by splitting from the grand coalition of all players. It is well known that, for the linear production game, and the flow game, the core is always non-empty (and a solution in the core can be found in polynomial time). In this paper, we show that, given an imputation x, it is NP-complete to decide it is not a member of the core, in both games. The same also holds for Steiner tree game. In addition, for Steiner tree games, we prove that testing the total balacedness is NP-hard. © Springer-Verlag Berlin Heidelberg 2001.
AB - Let Γ ≡ (N, v) be a cooperative game with the player set N and characteristic function v: 2N → R. An imputation of the game is in the core if no subset of players could gain advantage by splitting from the grand coalition of all players. It is well known that, for the linear production game, and the flow game, the core is always non-empty (and a solution in the core can be found in polynomial time). In this paper, we show that, given an imputation x, it is NP-complete to decide it is not a member of the core, in both games. The same also holds for Steiner tree game. In addition, for Steiner tree games, we prove that testing the total balacedness is NP-hard. © Springer-Verlag Berlin Heidelberg 2001.
KW - Cooperative game
KW - Core
KW - Linear programming
KW - Network flow
KW - NP-completeness
KW - Steiner tree
UR - http://www.scopus.com/inward/record.url?scp=33244472766&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-33244472766&origin=recordpage
U2 - 10.1007/3-540-44679-6_27
DO - 10.1007/3-540-44679-6_27
M3 - RGC 32 - Refereed conference paper (with host publication)
SN - 9783540424949
VL - 2108
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 247
EP - 256
BT - Computing and Combinatorics - 7th Annual International Conference, COCOON 2001, Proceedings
PB - Springer Verlag
T2 - 7th Annual International Conference on Computing and Combinatorics, COCOON 2001
Y2 - 20 August 2001 through 23 August 2001
ER -