This is the notebook for the Module 2 Programming Assignment.
Here are a few tips for using the iPython HTML notebook:
You should rename this notebook to be <your JHED id>_PR2.ipynb Do it right now.
Make certain the entire notebook executes before you submit it. (See Hint #5 above)
Change the following variables:
In [1]:
name = "Shehzad Qureshi"
jhed_id = "squresh6"
if name == "Student Name" or jhed_id == "sname1":
raise Exception( "Change the name and/or JHED ID...preferrably to yours.")
Add whatever additional imports you require here. Stick with the standard libraries and those required by the class. The import gives you access to these functions: http://ipython.org/ipython-doc/stable/api/generated/IPython.core.display.html (Copy this link) Which, among other things, will permit you to display HTML as the result of evaluated code (see HTML() or display_html()).
In [2]:
from IPython.core.display import *
import numpy as np
We can represent a Normal Form Game for two players in Python as a list of list of tuples:
In [3]:
prisoners_dilemma = [
[( -5, -5), (-1,-10)],
[(-10, -1), (-2, -2)]]
prisoners_dilemma
Out[3]:
function payoff
Write a function that takes a game, player 0's strategy as an integer (0-based) and player 1's strategy as an integer and returns the payoff. Player 0's payoff is the first entry in the tuple. Player 1's payoff is the second entry in the tuple.
In [4]:
def payoff( game, player_0, player_1):
return game[player_0][player_1]
In [5]:
print payoff(prisoners_dilemma, 0, 0) == (-5, -5)
print payoff(prisoners_dilemma, 0, 1) == (-1, -10)
print payoff(prisoners_dilemma, 1, 0) == (-10, -1)
print payoff(prisoners_dilemma, 1, 1) == (-2, -2)
For this part of the assignment, you should make up three test games (2x2, 3x3, and 4x4) that you know have a pure strategy equilibrium and can be solved using successive elimination of dominated strategies and three test games (2x2, 3x3, 4x4) that you know either do not have a pure strategy equilibrium or have a pure strategy equilibrium but cannot be solved by using successive elimination of dominated strategies. (Extra: can you write a function that generates random solvable games?)
In [6]:
solvable_0 = [[(20, 20), (28, 15)],
[(15, 28), (25, 25)]]
solvable_1 = [[(10, 10), (14, 12), (14, 15)],
[(12, 14), (20, 20), (28, 15)],
[(15, 14), (15, 28), (25, 25)]]
solvable_2 = [[(10, 10), (14, 12), (14, 15), (10, 10)],
[(12, 14), (20, 20), (28, 15), (14, 12)],
[(15, 14), (15, 28), (25, 25), (14, 15)],
[(5, 6), (9, 1), (2, 3), (0, 4)]]
not_solvable_0 = [[(20, 20), (16, 15)],
[(19, 23), (25, 25)]]
not_solvable_1 = [[(10, 10), (22, 12), (14, 15)],
[(12, 22), (20, 20), (28, 15)],
[(15, 14), (15, 28), (25, 25)]]
not_solvable_2 = [[(10, 10), (14, 12), (14, 15), (10, 10)],
[(12, 14), (20, 20), (28, 15), (14, 12)],
[(15, 14), (15, 28), (25, 25), (14, 15)],
[(9, 15), (14, 12), (14, 15), (10, 10)]]
Now write a function that either solves a game by successive elimination of strongly dominated strategies or returns "no solution found". Write however many helper functions as you need, one per cell, with Markdown documentation that discusses their implementation and the AI concepts behind them (where appropriate).
function get_strategy_matrix
We first need a function that will return the strategy of a specific player. Our game is hopefully constrained to two players with player 0's strategies as rows and player 1's strategies as columns.
In [7]:
def get_strategy_matrix(game, player):
shape = np.array(game).shape
if player == 0:
return np.delete(game, 1, 2).reshape(shape[0], shape[1], 1)
else:
return np.delete(game, 0, 2).transpose().reshape(shape[0], shape[1], 1)
Test to ensure we get the correct matrix as a result. The strategies will be returned as rows.
In [8]:
print np.all(get_strategy_matrix(prisoners_dilemma, 0).reshape(2,2) == np.array([(-5, -1), (-10, -2)]))
print np.all(get_strategy_matrix(prisoners_dilemma, 1).reshape(2,2) == np.array([(-5, -1), (-10, -2)]))
function get_strongly_dominated_strategy
Now we need a way to compare strategies and return a strongly dominated one. We do this by iterating through the strategy matrix and comparing each strategy with the other strategies. The function returns the index of the first strongly dominated strategy.
In [9]:
def get_strongly_dominated_strategy(sMatrix):
for index in xrange(len(sMatrix)):
c = np.delete(sMatrix, index, 0)
if np.all(c > sMatrix[index]):
return index
return None
Let's test to make sure we're getting the right output again. We can use the prisoner's dillemna again.
In [10]:
print get_strongly_dominated_strategy(get_strategy_matrix(prisoners_dilemma, 0)) == 1
print get_strongly_dominated_strategy(get_strategy_matrix(prisoners_dilemma, 1)) == 1
function get_strategy_result
Since the output of the solve_game function is actually the payoff, we need to reverse-translate it to an index that will give us (strategy0, strategy1) as an output.
In [11]:
def get_strategy_result(game, payoff):
return [(x,y) for x, row in enumerate(game) for y, col in enumerate(row) if (col == payoff).all()][0]
Another simple function test to make sure the output is correct.
In [12]:
print get_strategy_result(np.array(prisoners_dilemma), (-5, -5)) == (0, 0)
print get_strategy_result(np.array(prisoners_dilemma), (-2, -2)) == (1, 1)
print get_strategy_result(np.array(prisoners_dilemma), (-1, -10)) == (0, 1)
function solve_game
The algorithm used to solve a game in normal form is a simple iterative process that eliminates strongly dominated strategies until the game is reduced to a single strategy. On every iteration it gets the strategy matrix from the current player - which is alternated every round - and proceeds to find a strongly dominated strategy. If one is found, that strategy is eliminated from the game. If one is not found it proceeds to the second player and repeats the process. If neither player 1 nor player 2 have a strongly dominated strategy then it is assumed that there is no nash equilibrium and no solution is returned.
In [13]:
def solve_game(game, debug=False):
game_copy, player, previous_strategy_failed = np.array(game), np.random.randint(0, 2, 1)[0], False
while True:
if game_copy.shape == (1, 1, 2): return get_strategy_result(game, game_copy)
dominated_strategy = get_strongly_dominated_strategy(get_strategy_matrix(game_copy, player))
if dominated_strategy is not None:
previous_strategy_failed = False
game_copy = np.delete(game_copy, dominated_strategy, 0)
game_copy = np.delete(game_copy, dominated_strategy, 1)
else:
if previous_strategy_failed is True: return "no solution found"
else: previous_strategy_failed = True
player = 0 if player == 1 else 1
And now we test with all our game matrices above.
In [14]:
print solve_game(prisoners_dilemma) == (0, 0)
print solve_game(solvable_0) == (0, 0)
print solve_game(solvable_1) == (1, 1)
print solve_game(solvable_2) == (1, 1)
print solve_game(not_solvable_0) == "no solution found"
print solve_game(not_solvable_1) == "no solution found"
print solve_game(not_solvable_2) == "no solution found"
Summary and more
This assignment wasn't as hard as I thought it would be. The algorithm itself is a very simple iterative process that reduces a matrix until a solution is found. I actually spent more time trying to get Numpy to do what I wanted it to do... and in all fairness, I haven't spent a lot of time with Numpy.
The process is very simple. Given a game-state matrix, which is a matrix of tuples, first we get the list of strategies for player 1. This was probably the hardest part of the assignment because our state matrix isn't really a matrix; it's a list of lists of tuples which aren't the easiest to manipulate. Numpy has fantastic array support and has the numpy.delete method which allowed me to delete a tuple from the entire state matrix without looping through everything!
Once we have a strategy matrix, which is a list of lists of integers, the next part is to compare all of them. I did struggle to see if there was a "pythonic" way of comparing all iterations in the matrix but I couldn't find one. In the end I had to settle for looping through the list and using numpy to determine if indeed a dominated stategy exists.
Once we find a strongly dominated strategy it is trivial to delete it from the state matrix. The process then repeats until a single payoff remains. Since I was actually deleting rows/columns from the state matrix I ended up using some pythonic hackery madness to figure out the index of the payoff in the original array. I'm sure there is a better way of doing this.
Randomly generated games
So let's see if we can write some functions to generate random games. First a function to generate a random list of numbers.
In [15]:
def generate_random_numbers(length, low=0, high=10):
return np.random.randint(low, high, length)
Test it...
In [16]:
print generate_random_numbers(5)
print generate_random_numbers(6, 2)
print generate_random_numbers(10, 5, 15)
Looks like it works like it should. Now we need to use it to generate a game state matrix.
In [17]:
def generate_random_game(game_size, low=0, high=10):
return generate_random_numbers(game_size * game_size * 2, low, high).reshape(game_size, game_size, 2)
Let's see if it works. Let's start with simple 2x2 and 3x3 matrices.
In [18]:
print generate_random_game(2)
print generate_random_game(3)
Now let's see if we can generate solvable games. The iteration count is a failsafe to keep the function from potentially running forever.
In [19]:
def generate_solvable_game(game_size, low=0, high=10, iteration_count=100):
while iteration_count > 0:
iteration_count = iteration_count - 1
game = generate_random_game(game_size, low, high)
solution = solve_game(game)
if solution != "no solution found":
return game, solution
return None, None
Add some code to display the game matrix in a table.
In [20]:
from IPython.display import HTML
def print_game(game):
if game is None: return
h = "<table>"
for row in game:
h += "<tr>"
for col in row:
h += "<td>{0}</td>".format(" / ".join([str(x) for x in col]))
h += "</tr>"
h += "</table>"
return HTML(h)
Let's try to generate a 2x2 game since those are easy to solve by inspection.
In [21]:
game, solution = generate_solvable_game(2)
print "Solution: {0}".format(solution)
print_game(game)
Out[21]:
In [22]:
game, solution = generate_solvable_game(3)
print "Solution: {0}".format(solution)
print_game(game)
Out[22]:
So far so good. I'm not sure if the generated games actually contain a Nash equilibrium, but they do have solutions from successive elimination.
In [25]:
game, solution = generate_solvable_game(4, high=100)
print "Solution: {0}".format(solution)
print_game(game)
Out[25]:
Need to increase the limits if we want bigger tables. Will probably need to increase the failsafe iteration count to generate bigger tables.
In [24]:
game, solution = generate_solvable_game(10, high=10000, iteration_count=1000)
print "Solution: {0}".format(solution)
print_game(game)
Seems impossible to find a solvable game with a big enough size :(
In [24]: