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 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}]} .^[4]
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:^[5]

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

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

In evolutionary networked game theory, each node’s strategy changes over time based on its payoff relative to its neighbors.^[1]
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:^[5]

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

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:^[1]

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.^[6] In this way, we can compare game theory dynamics to statistical mechanics models.^[3]

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.^[3]
Linearizing the networked replicator dynamics around an equilibrium yields:^[1]
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.^[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 c {\displaystyle c} and yields benefit b i j {\displaystyle b_{ij}} , a player’s payoff can be written as:^[4]

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:^[4]

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