Matrix expression of Shapley values and its application to distributed resource allocation
Matrix expression of Shapley values and its application to distributed resource allocation作者机构:School of Management Science and Engineering Shandong Normal University Academy of Mathematics and Systems Science Chinese Academy of Sciences
出 版 物:《Science China(Information Sciences)》 (中国科学:信息科学(英文版))
年 卷 期:2019年第62卷第2期
页 面:46-56页
核心收录:
学科分类:07[理学] 070104[理学-应用数学] 0701[理学-数学]
基 金:supported by National Natural Science Foundation of China (Grant No. 61773371)
主 题:semi-tensor product of matrices Shapley value matrix formula distributed resource allocation
摘 要:The symmetric and weighted Shapley values for cooperative n-person games are studied. Using the semi-tensor product of matrices, it is first shown that a characteristic function can be expressed as a pseudo-Boolean function. Then, two simple matrix formulas are obtained for calculating the symmetric and weighted Shapley values. Finally, using these new formulas, a design technique for the agents’ payoff functions in distributed resource allocation problems is proposed. It is possible to design payoff functions with the weighted Shapley value by the nonsymmetric weights defined on the players, thus ensuring that the optimal allocation is a pure Nash equilibrium. Practical examples are presented to illustrate the theoretical results.