Game theory on networks

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) No issues specified. Please specify issues, or remove this template. (Learn how and when to remove this template message)

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] 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.^[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]

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]

Consider a graph (or 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{𝐬}}_{{{𝒩}}_i})=\sum _{j\in {{𝒩}}_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 {{𝒩}}_i}$.^[1]

A Nash equilibrium of a network is a collection of strategies for each player ${\displaystyle {\mathbf{𝐬}}^{*}=(s_1^{*},\dots ,s_N^{*})}$ such that^[5] ${\displaystyle u_i(s_i^{*},s_{-i}^{*})\ge u_i(s_i,s_{-i}^{*})\mathrm{\forall }i,s_i\in S_i.}$

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)[{\mathrm{\Pi }}_i^{s_1}-{\mathrm{\Pi }}_i^{s_2}],}$

${\displaystyle {\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.^[2]

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

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

${\displaystyle \mathrm{Pr}(i\leftarrow j)=\frac{1}{1+e^{-({\mathrm{\Pi }}_j-{\mathrm{\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]

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

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]

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}-c{k}_i,}$

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

${\displaystyle 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.^[4]

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]

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

0.00 (0 votes) Original source: https://en.wikipedia.org/wiki/Game theory on networks. Read more