Game theory on networks: Difference between revisions

 

Line 114: Line 114:

<ref name=”nowak1992evolutionary”>{{cite journal| last1=Nowak | first1=Martin A. | last2=May | first2=Robert M. | title=Evolutionary games and spatial chaos | journal=Nature | date=1992 | volume=359 | issue=6398 | pages=826–829 | doi=10.1038/359826a0 | bibcode=1992Natur.359..826N }}</ref>

<ref name=”nowak1992evolutionary”>{{cite journal| last1=Nowak | first1=Martin A. | last2=May | first2=Robert M. | title=Evolutionary games and spatial chaos | journal=Nature | date=1992 | volume=359 | issue=6398 | pages=826–829 | doi=10.1038/359826a0 | bibcode=1992Natur.359..826N }}</ref>

<ref name=”szabo2007evolutionary”>{{cite journal| last1=Szabó| first1=György| last2=Fáth| first2=Gábor| title=Evolutionary games on graphs| journal=Physics Reports| date=2007| volume=446| issue=4–6| pages=97–216| doi=10.1016/j.physrep.2007.04.004| arxiv=cond-mat/0607344| bibcode=2007PhR…446…97S}}</ref>

<ref name=”szabo2007evolutionary”>{{cite journal| last1=Szabó| first1=György| last2=Fáth| first2=Gábor| title=Evolutionary games on graphs| journal=Physics Reports| date=2007| volume=446| issue=4–6| pages=97–216| doi=10.1016/j.physrep.2007.04.004| arxiv=cond-mat/0607344| bibcode=2007PhR…446…97S}}</ref>

<ref name=”jackson2008social”>{{cite book | last1=Jackson |first1=Matthew O. |date=2008 |title=Social and economic networks | publisher=Princeton University Press |isbn=978-0-691-13075-2}}</ref>

<ref name=”jackson2008social”>{{cite book | last1=Jackson |first1=Matthew O. |date=2008 |title=Social and economic networks | publisher=Princeton University Press |isbn=}}</ref>

<ref name=”perc2010coevolutionary”>{{cite journal| last1=Perc| first1=Matjaž| last2=Szolnoki| first2=Attila| title=Coevolutionary games—A mini review| journal=Biosystems| date=2010| volume=99| issue=2| pages=109–125| doi=10.1016/j.biosystems.2009.10.003| pmid=19837129| arxiv=0910.0826| bibcode=2010BiSys..99..109P}}</ref>

<ref name=”perc2010coevolutionary”>{{cite journal| last1=Perc| first1=Matjaž| last2=Szolnoki| first2=Attila| title=Coevolutionary games—A mini review| journal=Biosystems| date=2010| volume=99| issue=2| pages=109–125| doi=10.1016/j.biosystems.2009.10.003| pmid=19837129| arxiv=0910.0826| bibcode=2010BiSys..99..109P}}</ref>

<ref name=”barrat2008dynamical”>{{cite book|last1=Barrat |first1=Alain |last2=Barthelemy |first2=Marc |last3=Vespignani |first3=Alessandro | date=2008 |title=Dynamical processes on complex networks |publisher= Cambridge University Press |isbn=978-0-521-87914-2}}</ref>

<ref name=”barrat2008dynamical”>{{cite book|last1=Barrat |first1=Alain |last2=Barthelemy |first2=Marc |last3=Vespignani |first3=Alessandro | date=2008 |title=Dynamical processes on complex networks |publisher= Cambridge University Press |isbn=}}</ref>

<ref name=”hofbauer1998evolutionary”>{{cite book | last1=Hofbauer |first1=Josef |last2= Sigmund |first2= Karl |date=1998 |title=Evolutionary Games and Population Dynamics | publisher=Cambridge University Press | isbn=978-0-521-62545-9}}</ref>

<ref name=”hofbauer1998evolutionary”>{{cite book | last1=Hofbauer |first1=Josef |last2= Sigmund |first2= Karl |date=1998 |title=Evolutionary Games and Population Dynamics | publisher=Cambridge University Press | isbn=}}</ref>

</references>

</references>

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]

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]