Skip to main content
SpringerLink
Log in

Simplification of Shapley value for cooperative games via minimum carrier

  • Research Article
  • Published:
Control Theory and Technology Aims and scope Submit manuscript

Abstract

Shapley value is one of the most fundamental concepts in cooperative games. This paper investigates the calculation of the Shapley value for cooperative games and establishes a new formula via carrier. Firstly, a necessary and sufficient condition is presented for the verification of carrier, based on which an algorithm is worked out to find the unique minimum carrier. Secondly, by virtue of the properties of minimum carrier, it is proved that the profit allocated to dummy players (players which do not belong to the minimum carrier) is zero, and the profit allocated to players in minimum carrier is only determined by the minimum carrier. Then, a new formula of the Shapley value is presented, which greatly reduces the computational complexity of the original formula, and shows that the Shapley value only depends on the minimum carrier. Finally, based on the semi-tensor product (STP) of matrices, the obtained new formula is converted into an equivalent algebraic form, which makes the new formula convenient for calculation via MATLAB.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. von Neumann, J., & Morgenstern,. O. (1944). Theory of Games and Economic Behavior. Princeton: Princeton University Press.

    MATH  Google Scholar 

  2. Ichiishi, T., Neyman, A., & Tauman, Y. (1990). Game Theory and Applications. New York: Academic Press.

    MATH  Google Scholar 

  3. Matsumoto, A., & Szidarovszky, F. (2016). Game Theory and Its Applications. Berlin: Springer.

    Book  Google Scholar 

  4. Basar, T., & Olsder, G. J. (1999). Dynamic Noncooperative Game Theory. Philadelphia: SIAM.

    MATH  Google Scholar 

  5. Owen, G. (1995). Game Theory (3rd ed.). New York: Academic Press.

    MATH  Google Scholar 

  6. Nash, J. (1951). Non-cooperative games. Annals of Mathematics, 54(2), 286–295.

    Article  MathSciNet  Google Scholar 

  7. Myerson, R. B. (1991). Game Theory, Analysis of Conflict. Boston: Harvard University Press.

    MATH  Google Scholar 

  8. Bilbao, J. M. (2000). Cooperative Games on Combinatorial Structures. Dordrecht: Kluwer Academic Publishers.

    Book  Google Scholar 

  9. Gillies, D. B. (1959). Solutions to general non-zero-sum games. Annals of Mathematical Studies, 40, 47–85.

    MathSciNet  MATH  Google Scholar 

  10. Schmeidler, D. (1969). The nucleolus of a characteristic function game. SIAM Journal on Applied Mathematics, 17(6), 1163–1170.

    Article  MathSciNet  Google Scholar 

  11. Shapley, L. S. (1953). A value for \(n\)-person games. Annals of Mathematical Studies, 28, 307–317.

    MathSciNet  MATH  Google Scholar 

  12. Cheng, D., Xu, T. (2013). Application of STP to cooperative games. In Proceedings of 10th IEEE International Conference on Control and Automation (pp. 1680–1685). Hangzhou, China.

  13. Cheng, D. (2014). On finite potential games. Automatica, 50(7), 1793–1801.

    Article  MathSciNet  Google Scholar 

  14. Cheng, D., He, F., Qi, H., & Xu, T. (2015). Modeling, analysis and control of networked evolutionary games. IEEE Transactions on Automatic Control, 60(9), 2402–2415.

    Article  MathSciNet  Google Scholar 

  15. Cheng, D., Liu, T., Zhang, K., & Qi, H. (2016). On decomposed subspaces of finite games. IEEE Transactions on Automatic Control, 61(11), 3651–3656.

    Article  MathSciNet  Google Scholar 

  16. Cheng, D., & Qi, H. (2011). Analysis and Control of Boolean Networks: A Semi-tensor Product Approach. Berlin: Springer.

    MATH  Google Scholar 

  17. Fornasini, E., & Valcher, M. E. (2013). Observability, reconstructibility and state observers of Boolean control networks. IEEE Transactions on Automatic Control, 58(6), 1390–1401.

    Article  MathSciNet  Google Scholar 

  18. Fu, S., Wang, Y., Cheng, D., & Liu, J. (2017). Morgan’s problem of Boolean control networks. Control Theory and Technology, 15(4), 316–326.

    Article  MathSciNet  Google Scholar 

  19. Han, J., Zhang, H., & Tian, H. (2016). Complete synchronization of the periodically time-variant Boolean networks. Control Theory & Applications, 33(7), 863–869.

    MATH  Google Scholar 

  20. Li, H., & Wang, Y. (2017). Lyapunov-based stability and construction of Lyapunov functions for Boolean networks. SIAM Journal on Control and Optimization, 55(6), 3437–3457.

    Article  MathSciNet  Google Scholar 

  21. Liang, J., Chen, H., & Liu, Y. (2017). On algorithms for state feedback stabilization of Boolean control networks. Automatica, 84, 10–16. https://doi.org/10.1016/j.automatica.2017.06.040.

    Article  MathSciNet  MATH  Google Scholar 

  22. Meng, M., Liu, L., & Feng, G. (2017). Stability and \(l_1\) gain analysis of Boolean networks with Markovian jump parameters. IEEE Transactions on Automatic Control, 62(8), 4222–4228.

    Article  MathSciNet  Google Scholar 

  23. Li, R., Yang, M., & Chu, T. (2013). State feedback stabilization for Boolean control networks. IEEE Transactions on Automatic Control, 58(7), 1853–1857.

    Article  MathSciNet  Google Scholar 

  24. Zhang, K., Zhang, L., & Xie, L. (2015). Invertibility and nonsingularity of Boolean control networks. Automatica, 60, 155–164. https://doi.org/10.1016/j.automatica.2015.07.016.

    Article  MathSciNet  MATH  Google Scholar 

  25. Zou, Y., & Zhu, J. (2015). Kalman decomposition for Boolean control networks. Automatica, 54, 65–71. https://doi.org/10.1016/j.automatica.2015.01.023.

    Article  MathSciNet  MATH  Google Scholar 

  26. Li, F., Li, H., Xie, L., & Zhou, Q. (2017). On stabilization and set stabilization of multivalued logical systems. Automatica, 80, 41–47. https://doi.org/10.1016/j.automatica.2017.01.032.

    Article  MathSciNet  MATH  Google Scholar 

  27. Li, Y., Li, H., & Sun, W. (2018). Event-triggered control for robust set stabilization of logical control networks. Automatica, 95, 556–560. https://doi.org/10.1016/j.automatica.2018.06.030.

    Article  MathSciNet  Google Scholar 

  28. Tian, H., Zhang, H., Wang, Z., & Hou, Y. (2017). Stabilization of \(k\)-valued logical control networks by open-loop control via the reverse-transfer method. Automatica, 83, 387–390. https://doi.org/10.1016/j.automatica.2016.12.040.

    Article  MathSciNet  MATH  Google Scholar 

  29. Zhong, J., Lu, J., Huang, T., & Ho, D. W. C. (2017). Controllability and synchronization analysis of identical-hierarchy mixed-valued logical control networks. IEEE Transactions on Cybernetics, 47(11), 3482–3493.

    Article  Google Scholar 

  30. Li, C., He, F., Liu, T., & Cheng, D. (2018). Verification and dynamics of group-based potential games. IEEE Transactions on Control of Network Systems, 6(1), 215–224.

    Article  MathSciNet  Google Scholar 

  31. Li, Y., Li, H., Xu, X., & Li, Y. (2018). Semi-tensor product approach to minimal-agent consensus control of networked evolutionary games. IET Control Theory & Applications, 12(16), 2269–2275.

    Article  MathSciNet  Google Scholar 

  32. Liu, X., & Zhu, J. (2016). On potential equations of finite games. Automatica, 68, 245–253. https://doi.org/10.1016/j.automatica.2016.01.074.

    Article  MathSciNet  MATH  Google Scholar 

  33. Mei, S., Wei, W., & Liu, F. (2017). On engineering game theory with its application in power systems. Control Theory and Technology, 15(1), 1–12.

    Article  MathSciNet  Google Scholar 

  34. Wu, Y., Toyoda, M., & Shen, T. (2017). Linear dynamic games with polytope strategy sets. IET Control Theory & Applications, 11(13), 2146–2151.

    Article  MathSciNet  Google Scholar 

  35. Zhu, B., Xia, X., & Wu, Z. (2016). Evolutionary game theoretic demand-side management and control for a class of networked smart grid. Automatica, 70, 94–100. https://doi.org/10.1016/j.automatica.2016.03.027.

    Article  MathSciNet  MATH  Google Scholar 

  36. Han, X., Chen, Z., Liu, Z., & Zhang, Q. (2016). Calculation of siphons and traps in Petri nets using semi-tensor product of matrices. Control Theory & Applications, 33(7), 849–855.

    Google Scholar 

  37. Lu, J., Li, M., Liu, Y., Ho, D. W. C., & Kurths, J. (2018). Nonsingularity of Grain-like cascade FSRs via semi-tensor product. Science China Information Sciences, 61(1), 010204. https://doi.org/10.1007/s11432-017-9269-6.

    Article  MathSciNet  Google Scholar 

  38. Shen, X., Wu, Y., & Shen, T. (2018). Logical control scheme with real-time statistical learning for residual gas fraction in IC engines. Science China Information Sciences, 61(1), 010203. https://doi.org/10.1007/s11432-017-9268-2.

    Article  Google Scholar 

  39. Xu, X., & Hong, Y. (2013). Matrix approach to model matching of asynchronous sequential machines. IEEE Transactions on Automatic Control, 58(11), 2974–2979.

    Article  MathSciNet  Google Scholar 

  40. Zhao, J., Chen, Z., & Liu, Z. (2018). Modeling and analysis of colored petri net based on the semi-tensor product of matrices. Science China Information Sciences, 61(1), 010205. https://doi.org/10.1007/s11432-017-9283-7.

    Article  MathSciNet  Google Scholar 

  41. Cheng, D., Qi, H., & Liu, Z. (2018). From STP to game-based control. Science China Information Sciences, 61(1), 010201. https://doi.org/10.1007/s11432-017-9265-2.

    Article  MathSciNet  Google Scholar 

  42. Cheng, D., & Fu, S. (2018). A survey on game theoretical control. Control Theory & Applications, 35(5), 588–592.

    MATH  Google Scholar 

  43. Li, H., Zhao, G., Meng, M., & Feng, J. (2018). A survey on applications of semi-tensor product method in engineering. Science China Information Sciences, 61(1), 010202. https://doi.org/10.1007/s11432-017-9238-1.

    Article  MathSciNet  Google Scholar 

  44. Lu, J., Li, H., Liu, Y., & Li, F. (2017). Survey on semi-tensor product method with its applications in logical networks and other finite-valued systems. IET Control Theory & Applications, 11(13), 2040–2047.

    Article  MathSciNet  Google Scholar 

  45. Muros, F., Maestre, J., Algaba, E., Alamo, T., & Camacho, E. (2017). Networked control design for coalitional schemes using game-theoretic methods. Automatica, 78, 320–332. https://doi.org/10.1016/j.automatica.2016.12.010.

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

This work was supported by the National Natural Science Foundation of China (No. 62073202 and No. 61873150), the Young Experts of Taishan Scholar Project (No. tsqn201909076), and the Natural Science Fund for Distinguished Young Scholars of Shandong Province (No. JQ201613).

Author information

Authors and Affiliations

  1. School of Mathematics and Statistics, Shandong Normal University, Jinan, 250014, Shandong, China

    Haitao Li, Shuling Wang, Aixin Liu & Meixia Xia

Authors
  1. Haitao Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Shuling Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Aixin Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Meixia Xia
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Haitao Li.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Li, H., Wang, S., Liu, A. et al. Simplification of Shapley value for cooperative games via minimum carrier. Control Theory Technol. 19, 157–169 (2021). https://doi.org/10.1007/s11768-020-00003-1

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11768-020-00003-1

Keywords

Search

Navigation