Decision-implementation complexity of cooperative game systems

doi:10.1007/s11432-017-9117-0

CORC > 数学与系统科学研究院 > 中国科学院数学与系统科学研究院 > 系统科学研究所

	Decision-implementation complexity of cooperative game systems
	Xu, Changbao 1,2; Zhao, Yanlong1,2 ; Zhang, Ji-Feng1,2
刊名	SCIENCE CHINA-INFORMATION SCIENCES
	2017-11-01
卷号	60 期号:11 页码:18
关键词	cooperative game distributed protocol optimal control decision-implementation complexity two-phase protocol
ISSN号	1674-733X
DOI	10.1007/s11432-017-9117-0
英文摘要	This paper focuses on the decision-implementation complexity (DIC) of cooperative games. The complexity of a control law is a fundamental issue in practice because it is closely related to control cost. First, we formulate implementation measures of strategies as system control protocols. Then, for a class of cooperative games, a decision-implementation system model is established, and an energy-based DIC index is given as the energy expectation under Nash equilibrium strategies. A definition of DIC is presented to describe the optimal values of the DIC index. DIC is calculated by the exhaust algorithm in some specific cases, whereas the one for general cases is too complex to be calculated. In order to obtain a general calculation method, the problem is described in the form of matrices; an analytical expression describing DIC is obtained by using the properties of matrix singular values. Furthermore, when only partial information of actions is shared among players, DIC can be reduced and an improved protocol can be designed as a two-phase protocol. A numerical example is given to show that the DIC obtained in this study is the same as the one obtained by the exhaust algorithm, and that the calculation complexity of the proposed algorithm is much lower.
资助项目	National Basic Research Program of China (973 Program)[2014CB845301] ; National Natural Science Foundation of China[61227902]
WOS研究方向	Computer Science
语种	英语
出版者	SCIENCE PRESS
WOS记录号	WOS:000417334600014
内容类型	期刊论文
源URL	[http://ir.amss.ac.cn/handle/2S8OKBNM/27103]
专题	系统科学研究所
通讯作者	Zhang, Ji-Feng
作者单位	1.Chinese Acad Sci, Acad Math & Syst Sci, Key Lab Syst & Control, Beijing 100190, Peoples R China 2.Univ Chinese Acad Sci, Sch Math Sci, Beijing 100049, Peoples R China
推荐引用方式 GB/T 7714	Xu, Changbao,Zhao, Yanlong,Zhang, Ji-Feng. Decision-implementation complexity of cooperative game systems[J]. SCIENCE CHINA-INFORMATION SCIENCES,2017,60(11):18.
APA	Xu, Changbao,Zhao, Yanlong,&Zhang, Ji-Feng.(2017).Decision-implementation complexity of cooperative game systems.SCIENCE CHINA-INFORMATION SCIENCES,60(11),18.
MLA	Xu, Changbao,et al."Decision-implementation complexity of cooperative game systems".SCIENCE CHINA-INFORMATION SCIENCES 60.11(2017):18.