Coreness of cooperative games with truncated submodular profit functions

doi:10.1016/j.tcs.2020.04.004

	Coreness of cooperative games with truncated submodular profit functions
	Chen, Wei 3; Shan, Xiaohan 4; Sun, Xiaoming 1,2; Zhang, Jialin 1,2
	2020-06-24
发表期刊	THEORETICAL COMPUTER SCIENCE
ISSN	0304-3975
卷号	822 页码:49-60
摘要	Coreness represents solution concepts related to core in cooperative games, which captures the stability of players. Motivated by the scale effect in social networks, economics and other scenario, we study the coreness of cooperative game with truncated submodular profit functions. Specifically, the profit function f(.) is defined by a truncation of a submodular function sigma (.): f (.) = sigma (.) if sigma (.) >= eta and f (.) = 0 otherwise, where eta is a given threshold. In this paper, we study the core and three core-related concepts of truncated submodular profit cooperative game. We first prove that whether core is empty can be decided in polynomial time and an allocation in core also can be found in polynomial time when core is not empty. When core is empty, we show hardness results and approximation algorithms for computing other core-related concepts including relative least-core value, absolute least-core value and least average dissatisfaction value. (C) 2020 Elsevier B.V. All rights reserved.
关键词	Cooperative game Core Submodular function Social network
DOI	10.1016/j.tcs.2020.04.004
收录类别	SCI
语种	英语
资助项目	973 Program of China[2016YFB1000201] ; National Natural Science Foundation of China[61832003] ; National Natural Science Foundation of China[61761136014] ; National Natural Science Foundation of China[61872334] ; National Natural Science Foundation of China[61433014] ; K. C. Wong Education Foundation ; NSFC for Distinguished 1062 Young Scholars[61525202] ; Beijing 1063 Academy of Artificial Intelligence (BAAI)
WOS研究方向	Computer Science
WOS类目	Computer Science, Theory & Methods
WOS记录号	WOS:000530067300005
出版者	ELSEVIER
引用统计
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/15437
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Shan, Xiaohan
作者单位	1.Chinese Acad Sci, Inst Comp Technol, CAS Key Lab Network Data Sci & Technol, Beijing, Peoples R China 2.Univ Chinese Acad Sci, Beijing, Peoples R China 3.Microsoft Res Asia, Beijing, Peoples R China 4.Tsinghua Univ, Dept Comp Sci & Technol, Beijing, Peoples R China
推荐引用方式 GB/T 7714	Chen, Wei,Shan, Xiaohan,Sun, Xiaoming,et al. Coreness of cooperative games with truncated submodular profit functions[J]. THEORETICAL COMPUTER SCIENCE,2020,822:49-60.
APA	Chen, Wei,Shan, Xiaohan,Sun, Xiaoming,&Zhang, Jialin.(2020).Coreness of cooperative games with truncated submodular profit functions.THEORETICAL COMPUTER SCIENCE,822,49-60.
MLA	Chen, Wei,et al."Coreness of cooperative games with truncated submodular profit functions".THEORETICAL COMPUTER SCIENCE 822(2020):49-60.