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. Players' interactions are modeled by a network (a graph with nodes for each player, plus additional data). 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. 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.
Overview Typical models in game theory assume that all players interact with every other player in a well-mixed population that is homogeneous. However, in networked game theory, nodes are limited to interact only through edges to other neighboring nodes. 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. 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.
Mathematical formulation Consider a graph (or network) G = ( V , E ) {\displaystyle G=(V,E)} with N = | V | {\displaystyle N=|V|} nodes and with an adjacency matrix A = [ A i j ] {\displaystyle A=[A_{ij}]} . Each node i ∈ V {\displaystyle i\in V} denotes a unique player with a strategy s i {\displaystyle s_{i}} chosen from a set of strategies S i {\displaystyle S_{i}} . The payoff for node i {\displaystyle i} is:
u i ( s i , s N i ) = ∑ j ∈ N i A i j P ( s i , s j ) {\displaystyle u_{i}(s_{i},\mathbf {s} _{{\mathcal {N}}_{i}})=\sum _{j\in {\mathcal {N}}_{i}}A_{ij}P(s_{i},s_{j})}
where P ( s i , s j ) {\displaystyle P(s_{i},s_{j})} is some payoff function pairwise between node i {\displaystyle i} each of its neighbors, N i {\displaystyle {\mathcal {N}}_{i}} . A Nash equilibrium of a network is a collection of strategies for each player s ∗ = ( s 1 ∗ , … , s N ∗ ) {\displaystyle \mathbf {s} ^{*}=(s_{1}^{*},\dots ,s_{N}^{*})} such that
u i ( s i ∗ , s − i ∗ ) ≥ u i ( s i , s − i ∗ ) ∀ i , s i ∈ S i . {\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. Let x i ( t ) {\displaystyle x_{i}(t)} be the probability that node i {\displaystyle i} uses strategy s i {\displaystyle s_{i}} . The replicator dynamics in this network are:
x ˙ i = x i ( 1 − x i ) [ Π i s 1 − Π i s 2 ] , {\displaystyle {\dot {x}}_{i}=x_{i}(1-x_{i})[\Pi _{i}^{s_{1}}-\Pi _{i}^{s_{2}}],}
Π i s 1 = ∑ j A i j P ( s 1 , s j ) , Π i s 2 = ∑ j A i j P ( s 2 , s j ) . {\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.
x ˙ = x ( 1 − x ) [ Π s 1 − Π s 2 ] , {\displaystyle {\dot {x}}=x(1-x)[\Pi _{s_{1}}-\Pi _{s_{2}}],}
One often-used structure updating mechanism is the Fermi rule:
Pr ( i ← j ) = 1 1 + e − ( Π j − Π i ) / K , {\displaystyle \Pr(i\leftarrow j)={\frac {1}{1+e^{-(\Pi _{j}-\Pi _{i})/K}}},}
where K {\displaystyle K} controls the level of randomness in the imitation process, which is reminiscent of the Boltzmann distribution. In this way, we can compare game theory dynamics to statistical mechanics models.
Spectral and topological effects The graph Laplacian, L = D − A {\displaystyle L=D-A} (where D {\displaystyle D} is the degree matrix), can be used to determine specific characteristics of the node dynamics. Linearizing the networked replicator dynamics around an equilibrium yields:
x ˙ = − L W x , {\displaystyle {\dot {\mathbf {x} }}=-LW\mathbf {x} ,}
where W {\displaystyle W} logs the payoff gradients for local neighbors. The eigenvalues of L {\displaystyle L} (especially the algebraic connectivity λ 2 ( L ) {\displaystyle \lambda _{2}(L)} ) can be used to calculate rates of convergence and the equilibrium stability. 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.
Network formation games For network formation games, players can decide to form or delete links in order to strategically maximize utility. If creating a link creates a cost c {\displaystyle c} and yields benefit b i j {\displaystyle b_{ij}} , a player's payoff can be written as:
u i ( G ) = ∑ j b i j − c k i , {\displaystyle u_{i}(G)=\sum _{j}b_{ij}-ck_{i},}
where k i {\displaystyle k_{i}} is the node's degree. A network G ∗ {\displaystyle G^{*}} is pairwise stable if:
u i ( G ∗ ) ≥ u i ( G ∗ − i j ) and u i ( G ∗ + i j ) < u i ( G ∗ ) or u j ( G ∗ + i j ) < u j ( G ∗ ) . {\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.
Applications Game theory in network science has applications in many fields.
economics - modeling competition and cooperation in trade networks biology - modeling evolution of inter- or intra-species cooperation, and host–parasite interactions computer science - distributed algorithms, routing, and cybersecurity sociology - opinion dynamics, cultural evolution, and collective behavior engineering - resource allocation in energy networks There are many current areas of research that include the following. Multi-layer and temporal networks are games played on multiplex topologies. Quantum game theory, which is the application of quantum information to strategic interactions on networks. Learning and reinforcement dynamics which covers machine learning in evolutionary games. Control and optimization, which means designing network structures to create desired equilibria Theoretical challenges include extending equilibrium concepts to non-stationary networks and developing scalable analytical approximations. In nonlinear dynamics, it is also a large question of how to link microscopic dynamics to macroscopic observables.
See also Evolutionary game theory Network science Complex systems Statistical mechanics Graph theory Nash equilibrium Synchronization
References