* ”’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]
Mathematical formulation
[edit]
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]
![{\displaystyle A=[A_{ij}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7541d7b18811f18a2bb654d5af0efa03d52b7b11)
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}.}
Evolutionary dynamics
[edit]
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}}],}
![{\displaystyle {\dot {x}}_{i}=x_{i}(1-x_{i})[\Pi _{i}^{s_{1}}-\Pi _{i}^{s_{2}}],}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5dcfa3983a776d36af8173fe65e7a6cd797169b4)
Π 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}}],}
![{\displaystyle {\dot {x}}=x(1-x)[\Pi _{s_{1}}-\Pi _{s_{2}}],}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e79991b86165dff641455ea84264e6d092392bb0)
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]
Spectral and topological effects
[edit]
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]
Network formation games
[edit]
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]
- ^ a b c d e f Szabó, György; Fáth, Gábor (2007). “Evolutionary games on graphs”. Physics Reports. 446 (4–6): 97–216. arXiv:cond-mat/0607344. Bibcode:2007PhR…446…97S. doi:10.1016/j.physrep.2007.04.004.
- ^ a b c Nowak, Martin A.; May, Robert M. (1992). “Evolutionary games and spatial chaos”. Nature. 359 (6398): 826–829. Bibcode:1992Natur.359..826N. doi:10.1038/359826a0.
- ^ a b c d e f g Barrat, Alain; Barthelemy, Marc; Vespignani, Alessandro (2008). Dynamical processes on complex networks. Cambridge University Press. ISBN 978-0-521-87914-2.
- ^ a b c d Hofbauer, Josef; Sigmund, Karl (1998). Evolutionary Games and Population Dynamics. Cambridge University Press. ISBN 978-0-521-62545-9.
- ^ a b c d Perc, Matjaž; Szolnoki, Attila (2010). “Coevolutionary games—A mini review”. Biosystems. 99 (2): 109–125. arXiv:0910.0826. Bibcode:2010BiSys..99..109P. doi:10.1016/j.biosystems.2009.10.003. PMID 19837129.
