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: .. code:: ipython3 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. .. code:: ipython3 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) .. parsed-literal:: 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: .. container:: alert alert-block alert-info Robert Wilson. 1971. Computing equilibria of N-person games. SIAM J. Appl. Math. 21, 1 (1971), 80–87. described here: .. container:: alert alert-block alert-info 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: .. container:: alert alert-block alert-warning Put Git repository and/or webpage address here. .. code:: ipython3 from gtnash.solver.wilsonalgorithm import * Applying Wilson’s algorithm returns allows to compute a mixed Nash equilibrium: .. code:: ipython3 equilibrium = wilson(current_nfg) print(equilibrium) print("Is this an equilibrium? ",current_nfg.is_equilibrium(equilibrium)) .. parsed-literal:: {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: .. code:: ipython3 for n in equilibrium.keys(): print(f"Player {n}: {[x.radical_expression() for x in equilibrium[n]]}") .. parsed-literal:: 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 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. code:: ipython3 %time print(wilson(current_nfg)) .. parsed-literal:: {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. .. container:: alert alert-block alert-info Ryan Porter and Eugene Nudelman and Yoav Shoham. Simple Search Methods for Finding a Nash Equilibrium. AAAI , 2004. .. code:: ipython3 from gtnash.solver.pns import * %time print(PNS_solver(current_nfg).launch_pns()) .. parsed-literal:: {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… .. container:: alert alert-block alert-info Elena B. Yanovskaya. 1968. Equilibrium points in polymatrix games. Litovskii Matematicheskii Sbornik 8 (1968), 381–384. .. code:: ipython3 from gtnash.game.polymatrixgame import * from gtnash.solver.lemkehowson_polymatrix import * Here is a polymatrix game with three players and three actions each: .. code:: ipython3 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) .. parsed-literal:: 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: .. container:: alert alert-block alert-info Joseph T. Howson. Equilibria of polymatrix games. Management Science , 18(5):pp. 312–318, 1972. .. code:: ipython3 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}') .. parsed-literal:: 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: .. code:: ipython3 print("Is it a Nash equilibrium? ",current_pmg.is_equilibrium(sol_dict)) .. parsed-literal:: 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: .. code:: ipython3 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]]}") .. parsed-literal:: [['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… .. container:: alert alert-block alert-info C.H. Papadimitriou and T. Roughgarden. Computing correlated equilibria in multi-player games. Journal of the ACM 55, 3(14), 2008. .. code:: ipython3 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) .. parsed-literal:: 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: .. code:: ipython3 %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]]}") .. parsed-literal:: 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: .. code:: ipython3 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]]}") .. parsed-literal:: 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): .. code:: ipython3 %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]]}") .. parsed-literal:: 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: .. code:: ipython3 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) .. parsed-literal:: 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: .. code:: ipython3 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)) .. parsed-literal:: 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: .. code:: ipython3 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.") .. parsed-literal:: 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: .. code:: ipython3 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") .. parsed-literal:: 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): .. code:: ipython3 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:") .. parsed-literal:: 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: .. code:: ipython3 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) .. parsed-literal:: 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.