Membership for core of LP games and other games

CSpace

	Membership for core of LP games and other games
	Fang, QZ ; Zhu, SF ; Cai, MC ; Deng, XT
	2001
发表期刊	COMPUTING AND COMBINATORICS
ISSN	0302-9743
卷号	2108 页码:247-256
摘要	Let Gamma drop (N,nu) be a cooperative game with the player set N and characteristic function nu : 2(N) --> 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.
关键词	cooperative game core network flow linear programming Steiner tree NP-completeness
语种	英语
WOS研究方向	Computer Science
WOS类目	Computer Science, Theory & Methods
WOS记录号	WOS:000179960000027
出版者	SPRINGER-VERLAG BERLIN
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/16870
专题	中国科学院数学与系统科学研究院
通讯作者	Fang, QZ
作者单位	1.Ocean Univ Qingdao, Dept Appl Math, Qingdao 266003, Peoples R China 2.City Univ Hong Kong, Dept Comp Sci, Hong Kong, Hong Kong, Peoples R China 3.Chinese Acad Sci, Inst Syst Sci, Beijing 100080, Peoples R China
推荐引用方式 GB/T 7714	Fang, QZ,Zhu, SF,Cai, MC,et al. Membership for core of LP games and other games[J]. COMPUTING AND COMBINATORICS,2001,2108:247-256.
APA	Fang, QZ,Zhu, SF,Cai, MC,&Deng, XT.(2001).Membership for core of LP games and other games.COMPUTING AND COMBINATORICS,2108,247-256.
MLA	Fang, QZ,et al."Membership for core of LP games and other games".COMPUTING AND COMBINATORICS 2108(2001):247-256.