logo

SCIENCE CHINA Information Sciences, Volume 62, Issue 1: 012207(2019) https://doi.org/10.1007/s11432-017-9411-0

Symmetry-based decomposition of finite games

More info
  • ReceivedOct 28, 2017
  • AcceptedMar 5, 2018
  • PublishedDec 19, 2018

Abstract

The symmetry-based decompositions of finite games are investigated.First, the vector space of finite games is decomposed into a symmetric subspace and an orthogonal complement of the symmetric subspace. The bases of the symmetric subspace and those of its orthogonal complement are presented.Second, the potential-based orthogonal decompositions of two-player symmetric/antisymmetric games are presented. The bases and dimensions of all dual decomposed subspaces are revealed.Finally, some properties of these decomposed subspaces are obtained.


Acknowledgment

This work was supported by National Natural Science Foundation of China (Grant Nos. 61473099, 61273013, 61333001).


References

[1] Nowak M A, May R M. Evolutionary games and spatial chaos. Nature, 1992, 359: 826-829 CrossRef ADS Google Scholar

[2] Tembine H, Altman E, El-Azouzi R. Evolutionary games in wireless networks. IEEE Trans Syst Man Cybern B, 2010, 40: 634-646 CrossRef PubMed Google Scholar

[3] Santos F C, Santos M D, Pacheco J M. Social diversity promotes the emergence of cooperation in public goods games. Nature, 2008, 454: 213-216 CrossRef PubMed ADS Google Scholar

[4] Heikkinen T. A potential game approach to distributed power control and scheduling. Comput Netw, 2006, 50: 2295-2311 CrossRef Google Scholar

[5] Marden J R, Arslan G, Shamma J S. Cooperative control and potential games. IEEE Trans Syst Man Cybern B, 2009, 39: 1393-1407 CrossRef PubMed Google Scholar

[6] Niyato D, Hossain E. A noncooperative game-theoretic framework for radio resource management in 4G heterogeneous wireless access networks. IEEE Trans Mobile Comput, 2008, 7: 332-345 CrossRef Google Scholar

[7] Arslan G, Marden J R, Shamma J S. Autonomous vehicle-target assignment: a game-theoretical formulation. J Dyn Syst Meas Control, 2007, 129: 584-596 CrossRef Google Scholar

[8] Candogan O, Menache I, Ozdaglar A. Flows and decompositions of games: harmonic and potential games. Math Oper Res, 2011, 36: 474-503 CrossRef Google Scholar

[9] Kalai A T, Kalai E. Cooperation and competition in strategic games with private information. In: Proceedings of the 11th ACM Conference on Electronic Commerce, Cambridge, 2010. 345--346. Google Scholar

[10] Hwang S H, Rey-Bellet L. Decompositions of two player games: potential, zero-sum, and stable games. 2011,. arXiv Google Scholar

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

[12] Cheng D, Liu T, Zhang K. On decomposed subspaces of finite games. IEEE Trans Autom Control, 2016, 61: 3651-3656 CrossRef Google Scholar

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

[14] Cheng D, Liu T. Linear representation of symmetric games. IET Control Theory Appl, 2017, 11: 3278-3287 CrossRef Google Scholar

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

[16] Nash J. Non-cooperative games. Ann Math, 1951, 54: 286-295 CrossRef Google Scholar

[17] Cao Z G, Yang X G. Symmetric games revisited. 2016. https://ssrn.com/abstract=2637225. Google Scholar

[18] Cheng D Z, Qi H S, Zhao Y. An Introduction to Semi-Tensor Product of Matrices and Its Applications. Singapore: World Scientific, 2012. Google Scholar

[19] Wang Y H, Liu T, Cheng D Z. Some notes on semi-tensor product of matrices and swap matrix. J Syst Sci Math Sci, 2016, 36: 1367--1375. Google Scholar

[20] Webb J N. Game Theory. Berlin: Springer, 2007. Google Scholar

[21] Li C X, Liu T, He F H, et al. On finite harmonic games. In: Proceedings of the 55th Conference on Decision and Control, Las Vegas, 2016. 7024--7029. Google Scholar

  • Table 1   Payoff bi-matrix of rock-paper-scissors
    Rock PaperScissor
    Rock 0, 0 $-1$, 11, $-1$
    Paper 1, $-1$ 0, 0$-1$,$~1$
    Scissor $-1$,$~1$ 1, $-1$0, 0
  • Table 2   Payoff bi-matrix of matching pennies
    Heads Tails
    Heads 1, $-1$ $-1$, 1
    Tails $-1$,$~1$ 1, $-1$

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

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