Game theory on networks

Game theory on networks is a field that studies strategy in competing interest interactions among rational or adaptive players that are affected by the topology of networks. ^[1] This contains concepts from game theory, nonlinear dynamics, and graph theory to analyze behavioral player-player phenomena like cooperation, and collective behavior as well as competition and percolation in networked systems. ^{[2] [3]}

This field has applications in areas such as economics, computer science, biology, and engineering, where players (nodes) interact through network connections (edges) instead of fully homogeneously mixed populations. ^[4]

Overview

Typical models in game theory assume that all players interact with every other player in a well-mixed population that is homogeneous. ^[5] However, in networked game theory, nodes are limited to interact only through edges to other neighboring nodes. ^[1] In these networks, each node denotes a unique player while each edge denotes a path through which interactions are possible. These can be represented by payoff matrices that quantify utilities of different competing strategies. ^[6]

Furthermore, topological features (e.g. degree distribution, clustering, modularity, centrality) in networks can be studied in game theory settings, which may change the evolution, stability, and equilibria of strategies and therefore players. ^[3]

Mathematical formulation

Consider a network ${\displaystyle G=(V,E)}$ with ${\displaystyle N=|V|}$ nodes and with an adjacency matrix ${\displaystyle A=[A_{ij}]}$. ^[4] Each node ${\displaystyle i\in V}$ denotes a unique player with a strategy ${\displaystyle s_{i}}$ chosen from a set of strategies ${\displaystyle S_{i}}$. The payoff for node ${\displaystyle i}$ is: ^[5]

${\displaystyle u_{i}(s_{i},\mathbf {s} _{{\mathcal {N}}_{i}})=\sum _{j\in {\mathcal {N}}_{i}}A_{ij}P(s_{i},s_{j})}$

where ${\displaystyle P(s_{i},s_{j})}$ is some payoff function pairwise between node ${\displaystyle i}$ each of its neighbors, ${\displaystyle {\mathcal {N}}_{i}}$. ^[1]

A Nash equilibrium of a network is a collection of strategies for each player ${\displaystyle \mathbf {s} ^{*}=(s_{1}^{*},\dots ,s_{N}^{*})}$ such that ^[5] ${\displaystyle u_{i}(s_{i}^{*},s_{-i}^{*})\geq u_{i}(s_{i},s_{-i}^{*})\quad \forall i,s_{i}\in S_{i}.}$

Evolutionary dynamics

In evolutionary networked game theory, each node's strategy changes over time based on its payoff relative to its neighbors. ^[1] Let ${\displaystyle x_{i}(t)}$ be the probability that node ${\displaystyle i}$ uses strategy ${\displaystyle s_{i}}$. The replicator dynamics in this network are: ^[5]

${\displaystyle {\dot {x}}_{i}=x_{i}(1-x_{i})[\Pi _{i}^{s_{1}}-\Pi _{i}^{s_{2}}],}$

${\displaystyle \Pi _{i}^{s_{1}}=\sum _{j}A_{ij}P(s_{1},s_{j}),\quad \Pi _{i}^{s_{2}}=\sum _{j}A_{ij}P(s_{2},s_{j}).}$

These dynamics are the networked population version of the classical replicator equation for well-mixed populations. ^[2]

${\displaystyle {\dot {x}}=x(1-x)[\Pi _{s_{1}}-\Pi _{s_{2}}],}$

One often-used structure updating mechanism is the Fermi rule: ^[1]

${\displaystyle \Pr(i\leftarrow j)={\frac {1}{1+e^{-(\Pi _{j}-\Pi _{i})/K}}},}$

where ${\displaystyle K}$ controls the level of randomness in the imitation process, which is reminiscent of the Boltzmann distribution. ^[6] In this way, we can compare game theory dynamics to statistical mechanics models. ^[3]

Spectral and topological effects

The graph Laplacian, ${\displaystyle L=D-A}$ (where ${\displaystyle D}$ is the degree matrix), can be used to determine specific characteristics of the node dynamics. ^[3] Linearizing the networked replicator dynamics around an equilibrium yields: ^[1] ${\displaystyle {\dot {\mathbf {x} }}=-LW\mathbf {x} ,}$

where ${\displaystyle W}$ logs the payoff gradients for local neighbors. The eigenvalues of ${\displaystyle L}$ (especially the algebraic connectivity ${\displaystyle \lambda _{2}(L)}$) can be used to calculate rates of convergence and the equilibrium stability. ^[4] Networks with a modular structure may exhibit slow strategy transition or extremely stable cooperative clusters, which is similar to phenomena observed in spin systems and synchronization. ^[3]

Network formation games

For network formation games, players can decide to form or delete links in order to strategically maximize utility. ^[4] If creating a link creates a cost ${\displaystyle c}$ and yields benefit ${\displaystyle b_{ij}}$, a player's payoff can be written as: ^[4]

${\displaystyle u_{i}(G)=\sum _{j}b_{ij}-ck_{i},}$

where ${\displaystyle k_{i}}$ is the node's degree. A network ${\displaystyle G^{*}}$ is pairwise stable if: ^[4]

${\displaystyle u_{i}(G^{*})\geq u_{i}(G^{*}-ij)\quad {\text{and}}\quad u_{i}(G^{*}+ij)<u_{i}(G^{*}){\text{ or }}u_{j}(G^{*}+ij)<u_{j}(G^{*}).}$

Models like these can explain the natural formation of social, economic, and communication networks as being the equilibrium outcomes of decentralized optimization. ^[4]

Applications

Game theory in network science has applications in many fields. ^[6]

• economics - modeling competition and cooperation in trade networks ^[4]
• biology - modeling evolution of inter- or intra-species cooperation, and host–parasite interactions ^[2]
• computer science - distributed algorithms, routing, and cybersecurity ^[3]
• sociology - opinion dynamics, cultural evolution, and collective behavior ^[6]
• engineering - resource allocation in energy networks ^[3]

There are many current areas of research ^[6] that include the following. Multi-layer and temporal networks are games played on multiplex topologies. ^[3] Quantum game theory, which is the application of quantum information to strategic interactions on networks. ^[1] Learning and reinforcement dynamics which covers machine learning in evolutionary games. ^[6] Control and optimization, which means designing network structures to create desired equilibria ^[4]

Theoretical challenges include extending equilibrium concepts to non-stationary networks and developing scalable analytical approximations. ^[5] In nonlinear dynamics, it is also a large question of how to link microscopic dynamics to macroscopic observables. ^[3]

See also

• Evolutionary game theory
• Network science
• Complex systems
• Statistical mechanics
• Graph theory
• Nash equilibrium
• Synchronization

References

1. Szabó, György; Fáth, Gábor (2007). "Evolutionary games on graphs". Physics Reports. 446 (4–6): 97–216. arXiv: cond-mat/0607344 . Bibcode:2007PhR...446...97S. doi:10.1016/j.physrep.2007.04.004.
2. Nowak, Martin A.; May, Robert M. (1992). "Evolutionary games and spatial chaos". Nature. 359 (6398): 826–829. Bibcode:1992Natur.359..826N. doi:10.1038/359826a0.
3. Barrat, Alain; Barthelemy, Marc; Vespignani, Alessandro (2008). Dynamical processes on complex networks. Cambridge University Press. ISBN   9780521879507.
4. Jackson, Matthew O. (2008). Social and economic networks. Princeton University Press. ISBN   9780691134406.
5. Hofbauer, Josef; Sigmund, Karl (1998). Evolutionary Games and Population Dynamics. Cambridge University Press. ISBN   9780521623650.
6. Perc, Matjaž; Szolnoki, Attila (2010). "Coevolutionary games—A mini review". Biosystems. 99 (2): 109–125. arXiv: 0910.0826 . Bibcode:2010BiSys..99..109P. doi:10.1016/j.biosystems.2009.10.003. PMID   19837129.