中国科学院机构知识库网格
Chinese Academy of Sciences Institutional Repositories Grid
首页 机构 成果 学者
  
  1. CAS IR Grid
  2. 计算技术研究所
  3. 中国科学院计算技术研究所
  4. 中国科学院计算技术研究所期刊论文
  5. 英文
Computing the least-core and nucleolus for threshold cardinality matching games

文献类型：期刊论文

作者Fang, Qizhi2; Li, Bo3; Sun, Xiaoming1; Zhang, Jia1; Zhang, Jialin1
刊名THEORETICAL COMPUTER SCIENCE
出版日期2016-01-04
卷号609页码:500-510
关键词Game theory Linear programming Least-core Nucleolus Matching
ISSN号0304-3975
DOI10.1016/j.tcs.2015.11.015
英文摘要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.
资助项目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记录号WOS:000367496500019
出版者ELSEVIER SCIENCE BV
源URL[http://119.78.100.204/handle/2XEOYT63/8934]  
专题中国科学院计算技术研究所期刊论文_英文
通讯作者Li, Bo
作者单位1.Chinese Acad Sci, Inst Comp Technol, Beijing 10010, Peoples R China
2.Ocean Univ China, Sch Math Sci, Qingdao 266100, Peoples R China
3.SUNY Stony Brook, Dept Comp Sci, Stony Brook, NY 11794 USA
推荐引用方式
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.

入库方式： OAI收割

来源：计算技术研究所

浏览0
下载0
收藏0
其他版本

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。