Innovative Dynamics Of Bimatrix Games

Innovative Dynamics of Bimatrix Games Mahdi Rahimi, University of Vienna

November 2, 2009

Mahdi Rahimi, University of Vienna

Innovative Dynamics of Bimatrix Games

Definition

Heuristic: In games of innovative dynamics, players play innovative, which means that they don’t imitate but play all possible strategies, whether in use, known or extinct as long as it is sufficiently rewarding

Mahdi Rahimi, University of Vienna

Innovative Dynamics of Bimatrix Games

Definition

Heuristic: In games of innovative dynamics, players play innovative, which means that they don’t imitate but play all possible strategies, whether in use, known or extinct as long as it is sufficiently rewarding Heuristic(Hofbauer, Sandholm 2009):If an unplayed strategy is sufficiently rewarding, then some members of the population will discover and select it

Mahdi Rahimi, University of Vienna

Innovative Dynamics of Bimatrix Games

Definition (Weibull 1995) For the population dynamics x˙ i = fi (x, y )

y˙ j = gj (x, y )

(1)

let Γ1 (x, y ) be the subset of Better than Average pure strategies of player 1, Γ1 (x, y ) = {i : ai > ¯a} and respectively Γ2 (x, y ) for player 2. We call the dynamics innovative if its vector field satisfies the following axiom: (IN): If Γ1 (x, y ) 6= ∅ then fi (x, y ) > 0 for some i ∈ Γ1 (x, y ) and if Γ2 (x, y ) 6= 0 then gj (x, y ) > 0 for some j ∈ Γ2 (x, y ).

Mahdi Rahimi, University of Vienna

Innovative Dynamics of Bimatrix Games

Why are innovative dynamics awesome?

Mahdi Rahimi, University of Vienna

Innovative Dynamics of Bimatrix Games

Why are innovative dynamics awesome?

More realistic model for rational players

Mahdi Rahimi, University of Vienna

Innovative Dynamics of Bimatrix Games

Why are innovative dynamics awesome?

More realistic model for rational players Restpoints are Nash Equilibria(Nash Stationarity)

Mahdi Rahimi, University of Vienna

Innovative Dynamics of Bimatrix Games

Why are innovative dynamics awesome?

More realistic model for rational players Restpoints are Nash Equilibria(Nash Stationarity) BNN and PD dynamics are both Lipschitz continuous and fulfill existence and uniqueness theorem for ODEs

Mahdi Rahimi, University of Vienna

Innovative Dynamics of Bimatrix Games

Why are innovative dynamics awesome?

More realistic model for rational players Restpoints are Nash Equilibria(Nash Stationarity) BNN and PD dynamics are both Lipschitz continuous and fulfill existence and uniqueness theorem for ODEs Little research done on either of the two dynamics

Mahdi Rahimi, University of Vienna

Innovative Dynamics of Bimatrix Games

Innovative Dynamics Payoff matrices (A,B)  a11 a12 · · · a21 a22 · · ·  A= . .. ..  .. . . an1 an2 · · ·

 a1m a2m   ..  .  anm

Mahdi Rahimi, University of Vienna



b11  b21  B= .  ..

b12 a22 .. .

··· ··· .. .

bm1 bm2 · · ·

Innovative Dynamics of Bimatrix Games

 b1n a2n   ..  .  bmn

Innovative Dynamics Payoff matrices (A,B)  a11 a12 · · · a21 a22 · · ·  A= . .. ..  .. . . an1 an2 · · ·

 a1m a2m   ..  .  anm



b11  b21  B= .  ..

b12 a22 .. .

··· ··· .. .

bm1 bm2 · · ·

 b1n a2n   ..  .  bmn

The payoff for the pure strategy i for player 1 and j of player 2 are given by ai = (Ay )i =

m X

aik yk

k=1

Mahdi Rahimi, University of Vienna

bj = (Bx)j =

n X

bjl xl

l=1

Innovative Dynamics of Bimatrix Games

Innovative Dynamics Payoff matrices (A,B)  a11 a12 · · · a21 a22 · · ·  A= . .. ..  .. . .

 a1m a2m   ..  . 

an1 an2 · · ·



b11  b21  B= .  ..

··· ··· .. .

b12 a22 .. .

bm1 bm2 · · ·

anm

 b1n a2n   ..  .  bmn

The payoff for the pure strategy i for player 1 and j of player 2 are given by ai = (Ay )i =

m X

aik yk

bj = (Bx)j =

k=1

n X

bjl xl

l=1

The average payoffs ¯a and b¯ are given by ¯a =

n X i=1

x i ai =

n X m X

xi aik yk

i=1 k=1 Mahdi Rahimi, University of Vienna

b¯ =

m X j=1

y j bj =

m X n X j=1 l=1

Innovative Dynamics of Bimatrix Games

yj ajl xl

Pairwise Difference Dynamics In general: x˙i = y˙j =

n X k=1 m X

xk (ai − ak )+ − xi yl (bj − bl )+ − yj

l=1

Mahdi Rahimi, University of Vienna

n X

(ak − ai )+

k=1 m X

(bl − bj )+

l=1

Innovative Dynamics of Bimatrix Games

(2)

Pairwise Difference Dynamics In general: x˙i = y˙j =

n X k=1 m X

xk (ai − ak )+ − xi yl (bj − bl )+ − yj

l=1

n X

(ak − ai )+

k=1 m X

(2)

(bl − bj )+

l=1

For 2 × 2 games: x˙ = (1 − x)(a1 − a2 )+ − x(a2 − a1 )+ y˙ = (1 − y )(b1 − b2 )+ − y (b2 − b1 )+

Mahdi Rahimi, University of Vienna

Innovative Dynamics of Bimatrix Games

(3)

Pairwise Difference Dynamics In general: x˙i = y˙j =

n X k=1 m X

xk (ai − ak )+ − xi yl (bj − bl )+ − yj

l=1

n X

(ak − ai )+

k=1 m X

(2)

(bl − bj )+

l=1

For 2 × 2 games: x˙ = (1 − x)(a1 − a2 )+ − x(a2 − a1 )+ y˙ = (1 − y )(b1 − b2 )+ − y (b2 − b1 )+

(3)

Used first by MJ Smith(1984) for traffic assignment. Also called Smith-Dynamics by Sandholm(2008) Mahdi Rahimi, University of Vienna

Innovative Dynamics of Bimatrix Games

BNN dynamics In general: x˙ i = αi − xi

n X

αk

k=1

y˙ j = βj − yj

m X

(4) βl

l=1

¯ + where αi = (ai − ¯a)+ andβj = (bj − b)

Mahdi Rahimi, University of Vienna

Innovative Dynamics of Bimatrix Games

BNN dynamics In general: x˙ i = αi − xi

n X

αk

k=1

y˙ j = βj − yj

m X

(4) βl

l=1

¯ + where αi = (ai − ¯a)+ andβj = (bj − b) For 2 × 2 games: x˙ = (1 − x)2 (a1 − a2 )+ − x 2 (a2 − a1 )+ y˙ = (1 − y )2 (b1 − b2 )+ − y 2 (b2 − b1 )+

Mahdi Rahimi, University of Vienna

Innovative Dynamics of Bimatrix Games

(5)

BNN dynamics

Used by Brown-von Neumann(1950) and Nash(1951) Nash stationarity was of great use for existence proof by Nash

Mahdi Rahimi, University of Vienna

Innovative Dynamics of Bimatrix Games

BNN dynamics

Used by Brown-von Neumann(1950) and Nash(1951) Nash stationarity was of great use for existence proof by Nash Arrow, Debreu(1953) used it also in an existence proof in General Equilibrium Theory

Mahdi Rahimi, University of Vienna

Innovative Dynamics of Bimatrix Games

Bimatrix Games

2 × 2 games Generic and Degenerate games Bimatrix game is generic for 2 × 2 games, if no column of a payoff matrix is all zero Overall 14 different classes, while 4 are generic and 10 degenerate

Mahdi Rahimi, University of Vienna

Innovative Dynamics of Bimatrix Games

Generic games Cyclic game: a1 , a2 < 0, b1 , b2 > 0

Figure: Buyer Seller Game for PD and BNN dynamics

Mahdi Rahimi, University of Vienna

Innovative Dynamics of Bimatrix Games

Generic games

Figure: Cyclic game for Replicator dynamics and Best-response dynamics

Mahdi Rahimi, University of Vienna

Innovative Dynamics of Bimatrix Games

Generic games

Interior equilibrium asymptotically stable No periodic orbits

Mahdi Rahimi, University of Vienna

Innovative Dynamics of Bimatrix Games

Generic games Coordination game

Figure: Coordination game for PD and BNN dynamics

Mahdi Rahimi, University of Vienna

Innovative Dynamics of Bimatrix Games

Two locally asymptotically stable pure equilibria Interior Nash equilibrium is a saddle

Mahdi Rahimi, University of Vienna

Innovative Dynamics of Bimatrix Games

1 degenerate strategy a1 > a2 and b1 = 0, b1 > b2

Figure: PD and BNN for 1a

Mahdi Rahimi, University of Vienna

Innovative Dynamics of Bimatrix Games

1 degenerate strategy a2 > a1 , b1 = 0, b1 > b2

Figure: PD and BNN for 1b

Mahdi Rahimi, University of Vienna

Innovative Dynamics of Bimatrix Games

For PD dynamics all quasi strict Nash Equilibria are stable and reachable For BNN dynamics (0, 1) is ω-limit set of all interior orbits and only stable and reachable Nash Equilibrium

Mahdi Rahimi, University of Vienna

Innovative Dynamics of Bimatrix Games

For PD dynamics all quasi strict Nash Equilibria are stable and reachable For BNN dynamics (0, 1) is ω-limit set of all interior orbits and only stable and reachable Nash Equilibrium All other restpoints of BNN are Nash equilibria but not reachable

Mahdi Rahimi, University of Vienna

Innovative Dynamics of Bimatrix Games

Centipede Game a1 , a2 < 0, b1 > b2 = 0

Figure: Centipede Game

Mahdi Rahimi, University of Vienna

Innovative Dynamics of Bimatrix Games

Centipede Game

Figure: Centipede Game for Replicator dynamics and best-response

Mahdi Rahimi, University of Vienna

Innovative Dynamics of Bimatrix Games

Chain-store game a1 , a2 < 0, b1 < b2 = 0

Figure: Chain-store game

Mahdi Rahimi, University of Vienna

Innovative Dynamics of Bimatrix Games

Nash equilibria on degenerate edge all reachable for PD dynamics

Mahdi Rahimi, University of Vienna

Innovative Dynamics of Bimatrix Games

Nash equilibria on degenerate edge all reachable for PD dynamics But not reachable and stable for BNN dynamics

Mahdi Rahimi, University of Vienna

Innovative Dynamics of Bimatrix Games

Nash equilibria on degenerate edge all reachable for PD dynamics But not reachable and stable for BNN dynamics For PD dynamics strict Nash equilibrium (0, 0) locally asymptotically stable For BNN dynamics perfect Nash equilibrium even globally asymptotically stable

Mahdi Rahimi, University of Vienna

Innovative Dynamics of Bimatrix Games

2 degenerate strategies 0 = a1 < a2 , 0 = b1 < b2

Figure: 2d for PD and BNN dynamics

Mahdi Rahimi, University of Vienna

Innovative Dynamics of Bimatrix Games

2 degenerate strategies 0 = a1 < a2 , b1 < b2 = 0

Figure: 2d for PD and BNN dynamics

Mahdi Rahimi, University of Vienna

Innovative Dynamics of Bimatrix Games

Analyzing Stability

Linearisation around restpoints does not always work well, especially with BNN dynamics, where it does not work at all

Mahdi Rahimi, University of Vienna

Innovative Dynamics of Bimatrix Games

Analyzing Stability

Linearisation around restpoints does not always work well, especially with BNN dynamics, where it does not work at all Stability analyzed through Liapunov functions

Mahdi Rahimi, University of Vienna

Innovative Dynamics of Bimatrix Games

Analyzing Stability

Linearisation around restpoints does not always work well, especially with BNN dynamics, where it does not work at all Stability analyzed through Liapunov functions Sandholm(2007), MJ Smith(1984) Brown, von Neumann(1950) and Nash(1951) all gave Liapunov functions that are of use

Mahdi Rahimi, University of Vienna

Innovative Dynamics of Bimatrix Games

Analyzing Stability

Linearisation around restpoints does not always work well, especially with BNN dynamics, where it does not work at all Stability analyzed through Liapunov functions Sandholm(2007), MJ Smith(1984) Brown, von Neumann(1950) and Nash(1951) all gave Liapunov functions that are of use Tried to find a quadratic form and use it as a Liapunov function, which is very useful for generic cases

Mahdi Rahimi, University of Vienna

Innovative Dynamics of Bimatrix Games

Analyzing Stability

L(u, v ) = α

u2 v2 +β 2 2

(6)

with u = x − x¯ and v = y − y¯ . For PD dynamics α and β can be found by linearization around the restpoint in each quadrant.

Mahdi Rahimi, University of Vienna

Innovative Dynamics of Bimatrix Games

Conclusions

For BNN and PD dynamics all restpoints are Nash equilibria For both dynamics pure Nash equilibria are asymptotically stable iff they are strict Both dynamics have no periodic orbits around the interior equilibria

Mahdi Rahimi, University of Vienna

Innovative Dynamics of Bimatrix Games

Conclusions

For BNN and PD dynamics all restpoints are Nash equilibria For both dynamics pure Nash equilibria are asymptotically stable iff they are strict Both dynamics have no periodic orbits around the interior equilibria For PD dynamics all quasi-strict Nash equilibria are reachable, which bears similarities to the Replicator dynamics

Mahdi Rahimi, University of Vienna

Innovative Dynamics of Bimatrix Games

Conclusions

For BNN and PD dynamics all restpoints are Nash equilibria For both dynamics pure Nash equilibria are asymptotically stable iff they are strict Both dynamics have no periodic orbits around the interior equilibria For PD dynamics all quasi-strict Nash equilibria are reachable, which bears similarities to the Replicator dynamics For the BNN dynamics the perfect equilibria are reachable

Mahdi Rahimi, University of Vienna

Innovative Dynamics of Bimatrix Games

Outlook

Behaviour for 2 × 3 and 2 × n games Behaviour of perfect and quasi-strict equilibria in higher dimensions. Are they still reachable for the respective dynamics or not?

Mahdi Rahimi, University of Vienna

Innovative Dynamics of Bimatrix Games