gtnash Tutorial
Illustration of the functionalities of the gtnash module.
Before executing this notebook, you should open a jupyter notebook under Python 3.0 (instead of Sagemath 9.0) in the gtnash directory and run: pip install -e .
Then, you need to import the following packages:
import numpy as np
import gtnash
from sage.all import *
from gtnash.game.normalformgame import *
1. Normal form games
A normal-form game can be built from (i) a list of lists of available actions for every player and (ii) a list of lists of utilities for every player (one utility for each joint action).
1.1 Defining a NFG object
A NFG can be built from a Python’s list of lists. Alternately, .nfg format (Gambit’s format: http://gambit.sourceforge.net/ ) ascii files can be read and written.
players_actions = [[0, 1], [0, 1], [0, 1]]
utilities=[[6,7,0,5,1,4,2,3],[0,3,7,4,6,5,1,2],[4,7,4,0,3,2,6,1]]
current_nfg=NFG(players_actions,utilities)
print("Utilities of the game")
print(current_nfg)
Utilities of the game
[['A0' 'A1' 'A2' 'U0' 'U1' 'U2']
['0' '0' '0' '6' '0' '4']
['0' '0' '1' '7' '3' '7']
['0' '1' '0' '0' '7' '4']
['0' '1' '1' '5' '4' '0']
['1' '0' '0' '1' '6' '3']
['1' '0' '1' '4' '5' '2']
['1' '1' '0' '2' '1' '6']
['1' '1' '1' '3' '2' '1']]
1.2 Solving using Wilson’s algorithm
This uses the implementation of Wilson’s method:
Robert Wilson. 1971. Computing equilibria of N-person games. SIAM J. Appl. Math. 21, 1 (1971), 80–87.
described here:
Hélène Fargier, Paul Jourdan and Régis Sabbadin. A path-following polynomial equations systems approach for computing Nash equilibria. AAMAS, 2022.
and which code can be found there:
Put Git repository and/or webpage address here.
from gtnash.solver.wilsonalgorithm import *
Applying Wilson’s algorithm returns allows to compute a mixed Nash equilibrium:
equilibrium = wilson(current_nfg)
print(equilibrium)
print("Is this an equilibrium? ",current_nfg.is_equilibrium(equilibrium))
{0: [0.4166666666666667?, 0.5833333333333333?], 1: [0.2857142857142857?, 0.714285714285715?], 2: [1.000000000000000?, 0]}
Is this an equilibrium? True
Remark
These coordinates are actually not an approximation of the equilibrium, but are exact “algebraic numbers”, which radical expression (exact representations in terms of single variable polynomials) can be recovered. In the present example, the equilibrium coordinates are rational numbers:
for n in equilibrium.keys():
print(f"Player {n}: {[x.radical_expression() for x in equilibrium[n]]}")
Player 0: [5/12, 7/12]
Player 1: [2/7, 5/7]
Player 2: [1, 0]
Returning a Nash equilibrium using Wilson’s algorithm, in one command
%time print(wilson(current_nfg))
{0: [0.4166666666666667?, 0.5833333333333333?], 1: [0.2857142857142857?, 0.714285714285715?], 2: [1.000000000000000?, 0]}
CPU times: user 784 ms, sys: 16 ms, total: 800 ms
Wall time: 798 ms
1.3 Solving using Porter, Nudelman and Shoam’s algorithm
We can solve the same game using Porter, Nudelman and Shoam’s algorithm.
Ryan Porter and Eugene Nudelman and Yoav Shoham. Simple Search Methods for Finding a Nash Equilibrium. AAAI , 2004.
from gtnash.solver.pns import *
%time print(PNS_solver(current_nfg).launch_pns())
{0: [0.4166666666666667?, 0.5833333333333333?], 1: [0.2857142857142857?, 0.714285714285715?], 2: [1.000000000000000?, 0]}
CPU times: user 186 ms, sys: 16.4 ms, total: 203 ms
Wall time: 330 ms
2. Polymatrix games
2.1 Definition of a polymatrix game
Definition of a polymatrix game: Object, ascii representation…
Elena B. Yanovskaya. 1968. Equilibrium points in polymatrix games. Litovskii Matematicheskii Sbornik 8 (1968), 381–384.
from gtnash.game.polymatrixgame import *
from gtnash.solver.lemkehowson_polymatrix import *
Here is a polymatrix game with three players and three actions each:
utilities = [[[8, 2, 5, 5, 1, 7, 1, 5, 1], [4, 1, 4, 5, 6, 2, 4, 7, 3]],
[[2, 2, 4, 7, 9, 4, 5, 5, 5], [2, 5, 4, 7, 1, 5, 2, 1, 6]],
[[9, 3, 4, 9, 5, 5, 9, 5, 4], [8, 8, 6, 9, 1, 4, 9, 1, 3]]]
hypergraph = [[0, 1], [0, 2], [1, 2]]
players_actions = [[0, 1, 2], [0, 1, 2], [0, 1, 2]]
current_pmg=PMG(players_actions,utilities,hypergraph)
print("Utilities of the game")
print(current_pmg)
Utilities of the game
Local game 0 :
[['A0' 'A1' 'U0' 'U1']
['0' '0' '8' '4']
['0' '1' '2' '1']
['0' '2' '5' '4']
['1' '0' '5' '5']
['1' '1' '1' '6']
['1' '2' '7' '2']
['2' '0' '1' '4']
['2' '1' '5' '7']
['2' '2' '1' '3']]
Local game 1 :
[['A0' 'A2' 'U0' 'U2']
['0' '0' '2' '2']
['0' '1' '2' '5']
['0' '2' '4' '4']
['1' '0' '7' '7']
['1' '1' '9' '1']
['1' '2' '4' '5']
['2' '0' '5' '2']
['2' '1' '5' '1']
['2' '2' '5' '6']]
Local game 2 :
[['A1' 'A2' 'U1' 'U2']
['0' '0' '9' '8']
['0' '1' '3' '8']
['0' '2' '4' '6']
['1' '0' '9' '9']
['1' '1' '5' '1']
['1' '2' '5' '4']
['2' '0' '9' '9']
['2' '1' '5' '1']
['2' '2' '4' '3']]
Hypergraph:
[[0, 1], [0, 2], [1, 2]]
2.2 Solving a polymatrix game using the Lemke-Howson algorithm
More precisely, this is an implementation of:
Joseph T. Howson. Equilibria of polymatrix games. Management Science , 18(5):pp. 312–318, 1972.
solver = LHpolymatrix(PMG(players_actions, utilities, hypergraph))
omega0 = [0,0,0] # Initial joint action used to initialize the Lemke-Howson algorithm
%time sol_dict = solver.launch_solver(omega0)
for key in sol_dict.keys():
mixed_strat = [float(p) for p in sol_dict[key]]
print(f'player {key} -> mixed strategy -> {mixed_strat}')
CPU times: user 4.33 ms, sys: 19 µs, total: 4.35 ms
Wall time: 3.94 ms
player 0 -> mixed strategy -> [0.0, 0.0, 1.0]
player 1 -> mixed strategy -> [0.0, 1.0, 0.0]
player 2 -> mixed strategy -> [1.0, 0.0, 0.0]
We can check that this mixed strategy is a Nash equilibrium:
print("Is it a Nash equilibrium? ",current_pmg.is_equilibrium(sol_dict))
Is it a Nash equilibrium? True
2.3 Game conversion
We may also convert the game to a normal form game and try to solve it again:
converted_nfg = current_pmg.convert_to_NFG()
print(converted_nfg)
%time equilibrium = wilson(converted_nfg)
print(equilibrium)
for n in equilibrium.keys():
print(f"Player {n}: {[x.radical_expression() for x in equilibrium[n]]}")
[['A0' 'A1' 'A2' 'U0' 'U1' 'U2']
['0' '0' '0' '10' '13' '10']
['0' '0' '1' '10' '7' '13']
['0' '0' '2' '12' '8' '10']
['0' '1' '0' '4' '10' '11']
['0' '1' '1' '4' '6' '6']
['0' '1' '2' '6' '6' '8']
['0' '2' '0' '7' '13' '11']
['0' '2' '1' '7' '9' '6']
['0' '2' '2' '9' '8' '7']
['1' '0' '0' '12' '14' '15']
['1' '0' '1' '14' '8' '9']
['1' '0' '2' '9' '9' '11']
['1' '1' '0' '8' '15' '16']
['1' '1' '1' '10' '11' '2']
['1' '1' '2' '5' '11' '9']
['1' '2' '0' '14' '11' '16']
['1' '2' '1' '16' '7' '2']
['1' '2' '2' '11' '6' '8']
['2' '0' '0' '6' '13' '10']
['2' '0' '1' '6' '7' '9']
['2' '0' '2' '6' '8' '12']
['2' '1' '0' '10' '16' '11']
['2' '1' '1' '10' '12' '2']
['2' '1' '2' '10' '12' '10']
['2' '2' '0' '6' '12' '11']
['2' '2' '1' '6' '8' '2']
['2' '2' '2' '6' '7' '9']]
CPU times: user 1.62 s, sys: 11.7 ms, total: 1.63 s
Wall time: 1.63 s
{0: [0, 0, 1.000000000000000?], 1: [0, 1.000000000000000?, 0], 2: [1.000000000000000?, 0, 0]}
Player 0: [0, 0, 1]
Player 1: [0, 1, 0]
Player 2: [1, 0, 0]
3. Hypergraphical games
3.1 Definition of a hypergraphical game
Definition of a hypergraphical game: Object, ascii representation…
C.H. Papadimitriou and T. Roughgarden. Computing correlated equilibria in multi-player games. Journal of the ACM 55, 3(14), 2008.
from gtnash.game.hypergraphicalgame import *
utilities = [
[[74, 6, 9, 60, 77, 30, 47, 0], [51, 97, 98, 83, 90, 1, 2, 47],
[18, 16, 29, 86, 100, 96, 93, 64]],
[[84, 48, 27, 5, 100, 62, 16, 62], [10, 88, 72, 47, 13, 24, 42, 72],
[1, 36, 68, 0, 53, 5, 61, 97]]]
hypergraph = [[0, 1, 3], [0, 2, 3]]
players_actions = [[0, 1], [0, 1], [0, 1], [0, 1]]
current_hgg = HGG(players_actions, utilities, hypergraph)
print("Utilities of the hypergraphical game:")
print(current_hgg)
Utilities of the hypergraphical game:
Local game 0 :
[['A0' 'A1' 'A3' 'U0' 'U1' 'U3']
['0' '0' '0' '74' '51' '18']
['0' '0' '1' '6' '97' '16']
['0' '1' '0' '9' '98' '29']
['0' '1' '1' '60' '83' '86']
['1' '0' '0' '77' '90' '100']
['1' '0' '1' '30' '1' '96']
['1' '1' '0' '47' '2' '93']
['1' '1' '1' '0' '47' '64']]
Local game 1 :
[['A0' 'A2' 'A3' 'U0' 'U2' 'U3']
['0' '0' '0' '84' '10' '1']
['0' '0' '1' '48' '88' '36']
['0' '1' '0' '27' '72' '68']
['0' '1' '1' '5' '47' '0']
['1' '0' '0' '100' '13' '53']
['1' '0' '1' '62' '24' '5']
['1' '1' '0' '16' '42' '61']
['1' '1' '1' '62' '72' '97']]
Hypergraph:
[[0, 1, 3], [0, 2, 3]]
3.2 Solving a hypergraphical game, using Wilson’s algorithm
We solve the hypergraphical game, using Wilson’s algorithm:
%time equilibrium = wilson(current_hgg)
print(equilibrium)
print("Is this an equilibrium? ",current_hgg.is_equilibrium(equilibrium))
print("Algebraic number representation:")
for n in equilibrium.keys():
print(f"Player {n}: {[x.radical_expression() for x in equilibrium[n]]}")
CPU times: user 6.87 s, sys: 10.3 ms, total: 6.88 s
Wall time: 6.89 s
{0: [0.651851851851852?, 0.3481481481481481?], 1: [0.7714285714285714?, 0.2285714285714286?], 2: [0, 1.000000000000000?], 3: [1.000000000000000?, 0]}
Is this an equilibrium? True
Algebraic number representation:
Player 0: [88/135, 47/135]
Player 1: [27/35, 8/35]
Player 2: [0, 1]
Player 3: [1, 0]
In this case, the PNS algorithm on the normal form game conversion of the hypergraphical game is faster and returns a different equilibrium:
converted_nfg = current_hgg.convert_to_NFG()
%time equilibrium_PNS = PNS_solver(converted_nfg).launch_pns()
print(equilibrium_PNS)
print("Is this an equilibrium? ",current_hgg.is_equilibrium(equilibrium_PNS))
print("Algebraic number representation:")
for n in equilibrium_PNS.keys():
print(f"Player {n}: {[x.radical_expression() for x in equilibrium_PNS[n]]}")
CPU times: user 420 ms, sys: 8.15 ms, total: 428 ms
Wall time: 426 ms
{0: [0.7666666666666667?, 0.2333333333333334?], 1: [0.5476190476190476?, 0.4523809523809524?], 2: [1.000000000000000?, 0], 3: [0, 1.000000000000000?]}
Is this an equilibrium? True
Algebraic number representation:
Player 0: [23/30, 7/30]
Player 1: [23/42, 19/42]
Player 2: [1, 0]
Player 3: [0, 1]
But Wilson’s algorithm on the converted NFG is also faster (Wilson’s algorithm on hypergraphical games solves PCP of smaller degree, but with a larger number of variables):
%time equilibrium_wilson = wilson(converted_nfg)
print(equilibrium_wilson)
print("Is this an equilibrium? ",current_hgg.is_equilibrium(equilibrium_wilson))
print("Algebraic number representation:")
for n in equilibrium_wilson.keys():
print(f"Player {n}: {[x.radical_expression() for x in equilibrium_wilson[n]]}")
CPU times: user 2.53 s, sys: 8.1 ms, total: 2.54 s
Wall time: 2.54 s
{0: [0.651851851851852?, 0.3481481481481481?], 1: [0.7714285714285714?, 0.2285714285714286?], 2: [0, 1.000000000000000?], 3: [1.000000000000000?, 0]}
Is this an equilibrium? True
Algebraic number representation:
Player 0: [88/135, 47/135]
Player 1: [27/35, 8/35]
Player 2: [0, 1]
Player 3: [1, 0]
4. Bayesian games and hypergraphical bayesian games
Here are a few examples of Bayesian games definition and conversion to hypergraphical games.
First, a bimatrix Bayesian game:
players_actions = [[0, 1, 2], [0, 1]]
utilities = [[[-3, -7, -10, -1, -5, -9], [-3, -7, -1, -5, -10, -9]],
[[-2, -6, -9, -1, -4, -8], [-2, -6, -1, -4, -9, -8]],
[[-2, -5, -8, -1, -3, -7], [-2, -5, -1, -3, -8, -7]],
[[-2, -4, -7, -1, -3, -6], [-2, -4, -1, -3, -7, -6]],
[[-2, -4, -6, -1, -3, -5], [-2, -4, -1, -3, -6, -5]],
[[-3, -7, -1, -5, -10, -9], [-3, -7, -10, -1, -5, -9]]]
theta = [[0, 1], [0, 1, 2]]
p = [2, 4, 4, 4, 2, 4]
bg = BG(players_actions, utilities, theta, p)
print(bg)
Theta 0 = [[0 0]] and P(Theta 0 ) = 1/10
[['A0' 'A1' 'U0' 'U1']
['0' '0' '-3' '-3']
['0' '1' '-7' '-7']
['1' '0' '-10' '-1']
['1' '1' '-1' '-5']
['2' '0' '-5' '-10']
['2' '1' '-9' '-9']]
Theta 1 = [[0 1]] and P(Theta 1 ) = 1/5
[['A0' 'A1' 'U0' 'U1']
['0' '0' '-2' '-2']
['0' '1' '-6' '-6']
['1' '0' '-9' '-1']
['1' '1' '-1' '-4']
['2' '0' '-4' '-9']
['2' '1' '-8' '-8']]
Theta 2 = [[0 2]] and P(Theta 2 ) = 1/5
[['A0' 'A1' 'U0' 'U1']
['0' '0' '-2' '-2']
['0' '1' '-5' '-5']
['1' '0' '-8' '-1']
['1' '1' '-1' '-3']
['2' '0' '-3' '-8']
['2' '1' '-7' '-7']]
Theta 3 = [[1 0]] and P(Theta 3 ) = 1/5
[['A0' 'A1' 'U0' 'U1']
['0' '0' '-2' '-2']
['0' '1' '-4' '-4']
['1' '0' '-7' '-1']
['1' '1' '-1' '-3']
['2' '0' '-3' '-7']
['2' '1' '-6' '-6']]
Theta 4 = [[1 1]] and P(Theta 4 ) = 1/10
[['A0' 'A1' 'U0' 'U1']
['0' '0' '-2' '-2']
['0' '1' '-4' '-4']
['1' '0' '-6' '-1']
['1' '1' '-1' '-3']
['2' '0' '-3' '-6']
['2' '1' '-5' '-5']]
Theta 5 = [[1 2]] and P(Theta 5 ) = 1/5
[['A0' 'A1' 'U0' 'U1']
['0' '0' '-3' '-3']
['0' '1' '-7' '-7']
['1' '0' '-1' '-10']
['1' '1' '-5' '-1']
['2' '0' '-10' '-5']
['2' '1' '-9' '-9']]
Type:
[[0, 1], [0, 1, 2]]
This bayesian bimatrix game can be converted into a polymatrix game:
hgg_from_bg,index_to_players = bg.convert_to_HGG()
print(hgg_from_bg)
print("Correspondance between players in the transformed game and the (player,type) tuples of the bayesian game:")
print(index_to_players)
print("Is the new game a polymatrix game? ",hgg_from_bg.is_PMG())
print("So, it can be solved using Lemke-Howson's algorithm:")
%time solver = LHpolymatrix(hgg_from_bg)
omega0 = [1,1,1,1,1] # Initial joint action used to initialize the Lemke-Howson algorithm
sol_dict = solver.launch_solver(omega0)
for key in sol_dict.keys():
mixed_strat = [float(p) for p in sol_dict[key]]
print(f'player {key} -> mixed strategy -> {mixed_strat}')
print("Is this really an equilibrium?",hgg_from_bg.is_equilibrium(sol_dict))
Local game 0 :
[['A0' 'A2' 'U0' 'U2']
['0' '0' '-3/5' '-1']
['0' '1' '-7/5' '-7/3']
['1' '0' '-2' '-1/3']
['1' '1' '-1/5' '-5/3']
['2' '0' '-1' '-10/3']
['2' '1' '-9/5' '-3']]
Local game 1 :
[['A0' 'A3' 'U0' 'U3']
['0' '0' '-4/5' '-4/3']
['0' '1' '-12/5' '-4']
['1' '0' '-18/5' '-2/3']
['1' '1' '-2/5' '-8/3']
['2' '0' '-8/5' '-6']
['2' '1' '-16/5' '-16/3']]
Local game 2 :
[['A0' 'A4' 'U0' 'U4']
['0' '0' '-4/5' '-1']
['0' '1' '-2' '-5/2']
['1' '0' '-16/5' '-1/2']
['1' '1' '-2/5' '-3/2']
['2' '0' '-6/5' '-4']
['2' '1' '-14/5' '-7/2']]
Local game 3 :
[['A1' 'A2' 'U1' 'U2']
['0' '0' '-4/5' '-4/3']
['0' '1' '-8/5' '-8/3']
['1' '0' '-14/5' '-2/3']
['1' '1' '-2/5' '-2']
['2' '0' '-6/5' '-14/3']
['2' '1' '-12/5' '-4']]
Local game 4 :
[['A1' 'A3' 'U1' 'U3']
['0' '0' '-2/5' '-2/3']
['0' '1' '-4/5' '-4/3']
['1' '0' '-6/5' '-1/3']
['1' '1' '-1/5' '-1']
['2' '0' '-3/5' '-2']
['2' '1' '-1' '-5/3']]
Local game 5 :
[['A1' 'A4' 'U1' 'U4']
['0' '0' '-6/5' '-3/2']
['0' '1' '-14/5' '-7/2']
['1' '0' '-2/5' '-5']
['1' '1' '-2' '-1/2']
['2' '0' '-4' '-5/2']
['2' '1' '-18/5' '-9/2']]
Hypergraph:
[[0, 2], [0, 3], [0, 4], [1, 2], [1, 3], [1, 4]]
Correspondance between players in the transformed game and the (player,type) tuples of the bayesian game:
{0: (0, 0), 1: (0, 1), 2: (1, 0), 3: (1, 1), 4: (1, 2)}
Is the new game a polymatrix game? True
So, it can be solved using Lemke-Howson's algorithm:
CPU times: user 1.84 ms, sys: 41 µs, total: 1.89 ms
Wall time: 1.75 ms
player 0 -> mixed strategy -> [1.0, 0.0, 0.0]
player 1 -> mixed strategy -> [1.0, 0.0, 0.0]
player 2 -> mixed strategy -> [1.0, 0.0]
player 3 -> mixed strategy -> [1.0, 0.0]
player 4 -> mixed strategy -> [1.0, 0.0]
Is this really an equilibrium? True
Now, let us try a large bayesian hypergraphical game:
from gtnash.game.bayesian_hypergraphicalgame import *
players_actions = [[0, 1], [0, 1], [0, 1], [0, 1]]
theta = [[0, 1], [0, 1], [0, 1], [0, 1]]
utilities = [[[[39, 19, 95, 0, 32, 97, 65, 69],
[22, 40, 67, 14, 100, 60, 5, 34],
[46, 27, 72, 45, 18, 84, 100, 33]],
[[61, 96, 22, 34, 34, 35, 39, 54],
[39, 42, 77, 76, 27, 45, 56, 0],
[21, 94, 80, 74, 100, 20, 55, 65]],
[[34, 47, 56, 73, 55, 59, 31, 17],
[57, 43, 0, 23, 41, 100, 73, 86],
[24, 53, 95, 45, 38, 17, 28, 76]],
[[47, 37, 100, 6, 20, 16, 17, 59],
[40, 44, 64, 13, 0, 73, 76, 71],
[23, 52, 19, 70, 41, 43, 30, 28]],
[[53, 38, 44, 33, 9, 71, 31, 82],
[62, 100, 70, 65, 74, 22, 47, 59],
[66, 82, 20, 0, 15, 3, 57, 60]],
[[46, 33, 0, 31, 50, 50, 35, 50],
[26, 77, 56, 47, 37, 51, 56, 57],
[28, 27, 100, 21, 29, 26, 83, 25]],
[[70, 88, 0, 15, 7, 34, 100, 58],
[53, 68, 17, 17, 16, 26, 84, 61],
[63, 80, 10, 15, 11, 43, 84, 50]],
[[91, 49, 99, 85, 62, 38, 21, 87],
[18, 36, 74, 84, 40, 45, 39, 88],
[63, 54, 57, 100, 45, 20, 0, 76]]],
[[[72, 67, 47, 94, 73, 92, 80, 81],
[55, 66, 45, 62, 78, 91, 55, 53],
[54, 75, 47, 42, 0, 52, 47, 100]],
[[64, 79, 39, 7, 43, 22, 68, 26],
[48, 67, 62, 5, 74, 82, 77, 65],
[40, 65, 38, 0, 59, 69, 100, 86]],
[[44, 53, 46, 82, 44, 89, 69, 97],
[61, 96, 88, 93, 70, 20, 100, 46],
[31, 89, 0, 61, 48, 77, 84, 46]],
[[59, 74, 63, 100, 34, 31, 38, 45],
[55, 52, 83, 74, 10, 65, 5, 50],
[74, 64, 65, 96, 19, 70, 0, 38]],
[[32, 100, 0, 54, 5, 37, 45, 66],
[2, 23, 49, 3, 62, 21, 23, 44],
[11, 54, 67, 8, 37, 69, 83, 27]],
[[41, 67, 72, 12, 65, 74, 65, 53],
[68, 68, 57, 49, 0, 91, 80, 61],
[97, 78, 86, 100, 34, 62, 57, 87]],
[[52, 54, 63, 18, 37, 67, 75, 73],
[47, 65, 93, 91, 59, 60, 0, 43],
[82, 76, 49, 91, 100, 82, 95, 50]],
[[39, 19, 95, 0, 32, 97, 65, 69],
[22, 40, 67, 14, 100, 60, 5, 34],
[46, 27, 72, 45, 18, 84, 100, 33]]]]
p = [[6, 9, 8, 6, 6, 4, 3, 3], [1, 7, 9, 1, 7, 3, 6, 9]]
hypergraph = [[0, 1, 2], [0, 2, 3]]
bhgg = BHGG(players_actions, utilities, hypergraph, theta, p)
print(f"Bayesian game with {bhgg.n_players} players, {len(bhgg.theta[0])} types, \
{len(bhgg.players_actions[0])} actions each and {len(bhgg.hypergraph)} local bayesian games.")
Bayesian game with 4 players, 2 types, 2 actions each and 2 local bayesian games.
And we can solve it, through first transforming it into a hypergraphical game and then into a normal form game:
hgg_from_bhgg,index_to_players = bhgg.convert_to_HGG()
print("We can compute first a:")
print(f"Hypergraphical game with {hgg_from_bhgg.n_players} players, {len(hgg_from_bhgg.players_actions[0])} \
actions each and {len(hgg_from_bhgg.hypergraph)} local games of size {len(hgg_from_bhgg.hypergraph[0])}.")
nfg_from_bhgg = hgg_from_bhgg.convert_to_NFG()
print("Then, we compute a normal form game from this HGG.")
print("We solve it using the PNS solver:")
%time equilibrium_PNS = PNS_solver(nfg_from_bhgg).launch_pns()
print("The corresponding equilibrium is:")
print(equilibrium_PNS)
print("Solving the same NFG using Wilson's algorithm takes far more time, so we do not do it")
We can compute first a:
Hypergraphical game with 8 players, 2 actions each and 16 local games of size 3.
Then, we compute a normal form game from this HGG.
We solve it using the PNS solver:
CPU times: user 11.4 s, sys: 487 ms, total: 11.9 s
Wall time: 12 s
The corresponding equilibrium is:
{0: [1, 0], 1: [0, 1], 2: [0, 1], 3: [1, 0], 4: [1, 0], 5: [1, 0], 6: [0, 1], 7: [0, 1]}
Solving the same NFG using Wilson's algorithm takes far more time, so we do not do it
Let us try a smaller BHGG (indeed, a Bayesian polymatrix game):
players_actions = [[0, 1], [0, 1], [0, 1]]
theta = [[0, 1], [0, 1], [0, 1]]
hypergraph = [[1, 2], [0, 1]]
p = [[Fraction(7, 19), Fraction(1, 19), Fraction(2, 19), Fraction(9, 19)],
[Fraction(1, 17), Fraction(4, 17), Fraction(5, 17), Fraction(7, 17)]]
utilities = [[[[15, 41, 0, 7], [14, 23, 65, 100]],
[[0, 41, 58, 92], [100, 51, 72, 93]],
[[56, 38, 0, 14], [100, 95, 43, 0]],
[[53, 69, 17, 15], [98, 12, 100, 0]]],
[[[39, 12, 42, 50], [0, 78, 38, 100]],
[[0, 7, 100, 58], [15, 10, 66, 78]],
[[74, 100, 96, 76], [0, 29, 98, 35]],
[[52, 21, 10, 100], [0, 43, 81, 56]]]]
bhgg = BHGG(players_actions, utilities, hypergraph, theta, p)
print(f"Bayesian game with {bhgg.n_players} players, {len(bhgg.theta[0])} types, \
{len(bhgg.players_actions[0])} actions each and {len(bhgg.hypergraph)} local bayesian games.")
hgg_from_bhgg,index_to_players = bhgg.convert_to_HGG()
print("We can compute first a:")
print(f"Hypergraphical game with {hgg_from_bhgg.n_players} players, {len(hgg_from_bhgg.players_actions[0])} \
actions each and {len(hgg_from_bhgg.hypergraph)} local games of size {len(hgg_from_bhgg.hypergraph[0])}.")
print("We can solve the HGG using Lemke and Howson's algorithm, since it is a polymatrix game:")
Bayesian game with 3 players, 2 types, 2 actions each and 2 local bayesian games.
We can compute first a:
Hypergraphical game with 6 players, 2 actions each and 8 local games of size 2.
We can solve the HGG using Lemke and Howson's algorithm, since it is a polymatrix game:
print("Is the obtained hypergraphical game a polymatrix game?")
print(hgg_from_bhgg.is_PMG())
print("So, we can solve it using the Lemke-Howson algorithm:")
omega0 = [0,0,0,0,0,0]
%time sol_dict = LHpolymatrix(hgg_from_bhgg).launch_solver(omega0)
for key in sol_dict.keys():
mixed_strat = [float(p) for p in sol_dict[key]]
print(f'player {key} -> mixed strategy -> {mixed_strat}')
print("Is this an equilibrium? ",hgg_from_bhgg.is_equilibrium(sol_dict))
print("In order to solve it using Wilson's algorithm, we first transform it into a normal-form game:")
nfg_from_bhgg = bhgg.convert_to_NFG()
print("We first solve it using the PNS solver:")
%time equilibrium_PNS = PNS_solver(nfg_from_bhgg).launch_pns()
print(equilibrium_PNS)
print("Is this an equilibrium? ",nfg_from_bhgg.is_equilibrium(equilibrium_PNS))
#print(nfg_from_bhgg)
print("Then, we solve it using Wilson's algorithm:")
%time equilibrium_wilson_bhgg = wilson(nfg_from_bhgg)
print("Here is the Nash equilibrium: ",equilibrium_wilson_bhgg)
Is the obtained hypergraphical game a polymatrix game?
True
So, we can solve it using the Lemke-Howson algorithm:
CPU times: user 4.9 ms, sys: 39 µs, total: 4.94 ms
Wall time: 4.28 ms
player 0 -> mixed strategy -> [0.0, 1.0]
player 1 -> mixed strategy -> [1.0, 0.0]
player 2 -> mixed strategy -> [0.0, 1.0]
player 3 -> mixed strategy -> [1.0, 0.0]
player 4 -> mixed strategy -> [0.0, 1.0]
player 5 -> mixed strategy -> [1.0, 0.0]
Is this an equilibrium? True
In order to solve it using Wilson's algorithm, we first transform it into a normal-form game:
We first solve it using the PNS solver:
CPU times: user 589 ms, sys: 23.8 ms, total: 613 ms
Wall time: 615 ms
{0: [0, 1], 1: [1, 0], 2: [0, 1], 3: [1, 0], 4: [0, 1], 5: [1, 0]}
Is this an equilibrium? True
Then, we solve it using Wilson's algorithm:
CPU times: user 1.67 s, sys: 7.81 ms, total: 1.68 s
Wall time: 1.67 s
Here is the Nash equilibrium: {0: [0, 1], 1: [1, 0], 2: [0, 1], 3: [1, 0], 4: [0, 1], 5: [1, 0]}
5. Game files formats
There are several methods for reading and writing normal-form games as ASCII files in Gambit format. We have also defined file formats for hypergraphical games, polymatrix games, bayesian games, etc. See the documentation of these functions.