Game theory on networks: Difference between revisions

 

Line 96: Line 96:

* ”’sociology”’ – opinion dynamics, cultural evolution, and collective behavior<ref name=”perc2010coevolutionary”/>

* ”’sociology”’ – opinion dynamics, cultural evolution, and collective behavior<ref name=”perc2010coevolutionary”/>

* ”’engineering”’ – resource allocation in energy networks<ref name=”barrat2008dynamical”/>

* ”’engineering”’ – resource allocation in energy networks<ref name=”barrat2008dynamical”/>

== Research directions ==

Current research areas include:<ref name=”perc2010coevolutionary”/>

* Multi-layer and temporal networks: games played on multiplex topologies<ref name=”barrat2008dynamical”/>

* Quantum game theory: application of quantum information to strategic interactions on networks<ref name=”szabo2007evolutionary”/>

* Learning and reinforcement dynamics: machine learning in evolutionary games<ref name=”perc2010coevolutionary”/>

* Control and optimization: designing network structures to create desired equilibria<ref name=”jackson2008social”/>

Theoretical challenges include extending equilibrium concepts to non-stationary networks and developing scalable analytical approximations.<ref name=”hofbauer1998evolutionary”/> In nonlinear dynamics, it is also a large question of how to link microscopic dynamics to macroscopic observables.<ref name=”barrat2008dynamical”/>

== See also ==

== See also ==

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

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 an 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 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}.}$

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]

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]

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]

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]