Computing the least-core and nucleolus for threshold cardinality matching games

doi:10.1016/j.tcs.2015.11.015

	Computing the least-core and nucleolus for threshold cardinality matching games
	Fang, Qizhi 1; Li, Bo 2; Sun, Xiaoming 3; Zhang, Jia 3; Zhang, Jialin 3
	2016-01-04
发表期刊	THEORETICAL COMPUTER SCIENCE
ISSN	0304-3975
卷号	609 页码:500-510
摘要	Cooperative games provide a framework for fair and stable profit allocation in multi-agent systems. Core, least-core and nucleolus are such solution concepts that characterize stability of cooperation. In this paper, we study the algorithmic issues of the least-core and nucleolus of threshold cardinality matching games (TCMG). A TCMG is defined on a graph G = (V, E) and a threshold T, in which the player set is V and the profit of a coalition S subset of V is I if the size of a maximum matching in G[S] meets or exceeds T, and 0 otherwise. We first show that for a TCMG, the problems of computing least-core value, finding and verifying least-core payoff are all polynomial-time solvable. We also provide a general characterization of the least-core for a large class of TCMG (cf. Theorem 2). Next, based on Gallai-Edmonds Decomposition in matching theory, we establish a concise formulation of the nucleolus for a special case of TCMG (when the threshold T equals 1). For arbitrary T, we prove that the nucleolus of TCMG can be obtained in polynomial time for bipartite graphs and graphs with a perfect matching. (C) 2015 Elsevier B.V. All rights reserved.
关键词	Game theory Linear programming Least-core Nucleolus Matching
DOI	10.1016/j.tcs.2015.11.015
收录类别	SCI
语种	英语
资助项目	National Natural Science Foundation of China (NSFC)[61170062] ; National Natural Science Foundation of China (NSFC)[61222202] ; National Natural Science Foundation of China (NSFC)[61433014] ; National Natural Science Foundation of China (NSFC)[61173009] ; National Natural Science Foundation of China (NSFC)[11271341]
WOS研究方向	Computer Science
WOS类目	Computer Science, Theory & Methods
WOS记录号	WOS:000367496500019
出版者	ELSEVIER SCIENCE BV
引用统计	被引频次：3[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/8935
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Li, Bo
作者单位	1.Ocean Univ China, Sch Math Sci, Qingdao 266100, Peoples R China 2.SUNY Stony Brook, Dept Comp Sci, Stony Brook, NY 11794 USA 3.Chinese Acad Sci, Inst Comp Technol, Beijing 10010, Peoples R China
推荐引用方式 GB/T 7714	Fang, Qizhi,Li, Bo,Sun, Xiaoming,et al. Computing the least-core and nucleolus for threshold cardinality matching games[J]. THEORETICAL COMPUTER SCIENCE,2016,609:500-510.
APA	Fang, Qizhi,Li, Bo,Sun, Xiaoming,Zhang, Jia,&Zhang, Jialin.(2016).Computing the least-core and nucleolus for threshold cardinality matching games.THEORETICAL COMPUTER SCIENCE,609,500-510.
MLA	Fang, Qizhi,et al."Computing the least-core and nucleolus for threshold cardinality matching games".THEORETICAL COMPUTER SCIENCE 609(2016):500-510.