logo

SCIENCE CHINA Information Sciences, Volume 62, Issue 2: 022201(2019) https://doi.org/10.1007/s11432-018-9414-5

Matrix expression of Shapley values and its application to distributed resource allocation

More info
  • ReceivedJan 27, 2018
  • AcceptedMar 5, 2018
  • PublishedDec 25, 2018

Abstract

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.


Acknowledgment

This work was supported by National Natural Science Foundation of China (Grant No. 61773371).


References

[1] Mei S W, Wang Y Y, Liu F. Game approaches for hybrid power system planning. IEEE Trans Sustain Energ, 2012, 3: 506-517 CrossRef ADS Google Scholar

[2] Zhu M H, Martinez S. Distributed coverage games for energy-aware mobile sensor networks. SIAM J Control Optim, 2013, 51: 1-27 CrossRef Google Scholar

[3] Gopalakrishnan R, Marden J R, Wierman A. An architectural view of game theoretic control. SIGMETRICS Perform Eval Rev, 2011, 38: 31-36 CrossRef Google Scholar

[4] Marden J R, Wierman A. Distributed welfare games. Oper Res, 2013, 61: 155-168 CrossRef Google Scholar

[5] Shapley L S. A value for $n$-person games. Contrib Theory Games, 1953, 2: 307--317. Google Scholar

[6] Perez-Castrillo D, Wettstein D. Bidding for the surplus: a non-cooperative approach to the Shapley value. J Econ Theory, 2001, 100: 274-294 CrossRef Google Scholar

[7] Shapley L S. Additive and non-additioe set functions. Dissertation for Ph.D. Degree. Princeton: Princeton University, 1953. Google Scholar

[8] Kalai E, Samet D. On weighted Shapley values. Int J Game Theory, 1987, 16: 205-222 CrossRef Google Scholar

[9] Chun Y. On the symmetric and weighted shapley values. Int J Game Theory, 1991, 20: 183-190 CrossRef Google Scholar

[10] Nowak A S, Radzik T. On axiomatizations of the weighted Shapley values. Games Econ Behav, 1995, 8: 389-405 CrossRef Google Scholar

[11] Cheng D Z, Qi H S, Li Z Q. Analysis and Control of Boolean Networks: A Semi-tensor Product Approach. Berlin: Springer, 2011. Google Scholar

[12] Li F F, Sun J T. Stability and stabilization of Boolean networks with impulsive effects. Syst Control Lett, 2012, 61: 1-5 CrossRef Google Scholar

[13] Li H T, Zhao G D, Meng M. A survey on applications of semi-tensor product method in engineering. Sci China Inf Sci, 2018, 61: 010202 CrossRef Google Scholar

[14] Meng M, Liu L, Feng G. Stability and $l_1$ gain analysis of Boolean networks with Markovian jump parameters. IEEE Trans Autom Control, 2017, 62: 4222-4228 CrossRef Google Scholar

[15] Lu J Q, Zhong J, Huang C. On pinning controllability of Boolean control networks. IEEE Trans Autom Control, 2016, 61: 1658-1663 CrossRef Google Scholar

[16] Zhao G D, Fu S H. Matrix approach to trajectory control of higher-order k-valued logical control networks. IET Control Theory Appl, 2017, 11: 2110-2115 CrossRef Google Scholar

[17] Liu Z B, Wang Y Z, Li H T. Two kinds of optimal controls for probabilistic mix-valued logical dynamic networks. Sci China Inf Sci, 2014, 57: 052201 CrossRef Google Scholar

[18] Zheng Y T, Li H T, Ding X Y. Stabilization and set stabilization of delayed Boolean control networks based on trajectory stabilization. J Franklin Inst, 2017, 354: 7812-7827 CrossRef Google Scholar

[19] Wang Y Z, Zhang C H, Liu Z B. A matrix approach to graph maximum stable set and coloring problems with application to multi-agent systems. Automatica, 2012, 48: 1227-1236 CrossRef Google Scholar

[20] Zhong J, Lu J Q, Huang C. Finding graph minimum stable set and core via semi-tensor product approach. Neurocomputing, 2016, 174: 588-596 CrossRef Google Scholar

[21] Zhao J T, Chen Z Q, Liu Z X. Modeling and analysis of colored petri net based on the semi-tensor product of matrices. Sci China Inf Sci, 2018, 61: 010205 CrossRef Google Scholar

[22] Cheng D Z, Xu T T. Application of STP to cooperative games. In: Proceedings of 10th IEEE International Conference on Control and Automation (ICCA), Hangzhou, 2013. 1680--1685. Google Scholar

[23] Cheng D Z. On finite potential games. Automatica, 2014, 50: 1793-1801 CrossRef Google Scholar

[24] Wang Y H, Liu T, Cheng D Z. From weighted potential game to weighted harmonic game. IET Control Theor Appl, 2017, 11: 2161-2169 CrossRef Google Scholar

[25] Cheng D Z, He F H, Qi H S. Modeling, analysis and control of networked evolutionary games. IEEE Trans Autom Control, 2015, 60: 2402-2415 CrossRef Google Scholar

[26] Wang Y H, Cheng D Z. Dynamics and stability for a class of evolutionary games with time delays in strategies. Sci China Inf Sci, 2016, 59: 092209 CrossRef Google Scholar

[27] Guo P L, Zhang H X, Alsaadi F E. Semi-tensor product method to a class of event-triggered control for finite evolutionary networked games. IET Control Theory Appl, 2017, 11: 2140-2145 CrossRef Google Scholar

[28] Branzei R, Dimitrov D, Tijs S. Models in Cooperative Game Theory. Berlin: Springer, 2008. Google Scholar

[29] Sedgewick R. Permutation generation methods. ACM Comput Surv, 1977, 9: 137-164 CrossRef Google Scholar

[30] Rosen K H, Michaels J G, et al. Handbook of Discrete and Combinatorial Mathematics. Boca Raton: CRC Press, 1999. Google Scholar

  • Table 1   Payoff function using symmetric Shapley value
    $r_2$$r_3$
    $r_1$$1,~1$$1,~0.5$
    $r_2$$1.5,~0.5$$2,~0.5$
  • Table 2   Global objective $W(a)$
    $r_2$$r_3$
    $r_1$$2$$1.5$
    $r_2$$2$$2.5$
  • Table 3   Payoff function using the weighted Shapley value
    $r_2$$r_3$
    $r_1$$1,~1$$1,~0.5$
    $r_2$$1.8,~0.2$$2,~0.5$

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1       京公网安备11010102003388号