Game theory on networks

Short description: Study of strategic interactions 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. 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)$ with $N=|V|$ nodes and with an adjacency matrix $A=[A_{ij}]$. Each node $i\in V$ denotes a unique player with a strategy $s_i$ chosen from a set of strategies $S_i$. The payoff for node $i$ is:

$u_i(s_i,{\mathbf{𝐬}}_{{{𝒩}}_i})=\sum _{j\in {{𝒩}}_i}{A}_{ij}P(s_i,s_j)$

where $P(s_i,s_j)$ is some payoff function pairwise between node $i$ each of its neighbors, ${{𝒩}}_i$.

A Nash equilibrium of a network is a collection of strategies for each player ${\mathbf{𝐬}}^{*}=(s_1^{*},\dots ,s_N^{*})$ such that $u_i(s_i^{*},s_{-i}^{*})\ge u_i(s_i,s_{-i}^{*})\mathrm{\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)$ be the probability that node $i$ uses strategy $s_i$. The replicator dynamics in this network are:

${\dot{x}}_i=x_i(1-x_i)[{\mathrm{\Pi }}_i^{s_1}-{\mathrm{\Pi }}_i^{s_2}],$

${\mathrm{\Pi }}_i^{s_1}=\sum _j{A}_{ij}P(s_1,s_j),{\mathrm{\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.

$\dot{x}=x(1-x)[{\mathrm{\Pi }}_{s_1}-{\mathrm{\Pi }}_{s_2}],$

One often-used structure updating mechanism is the Fermi rule:

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

where $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$ (where $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: $\dot{\mathbf{𝐱}}=-LW\mathbf{𝐱},$

where $W$ logs the payoff gradients for local neighbors. The eigenvalues of $L$ (especially the algebraic connectivity ${\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$ and yields benefit $b_{ij}$, a player's payoff can be written as:

$u_i(G)=\sum _j{b}_{ij}-c{k}_i,$

where $k_i$ is the node's degree. A network $G^{*}$ is pairwise stable if:

$u_i(G^{*})\ge u_i(G^{*}-ij)\text{and}{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