Simulate the fictitious play dynamic for the game in Shapley (1964).

shapley.py

"""
Simulate the fictitious play dynamic
for the game in section 5.3 of 
Shapley, Lloyd S. "Some topics in two-person games." 
Advances in game theory 52 (1964): 1-29.

Author: Jyotirmoy Bhattacharya, [email protected]

The author has placed this program in the public domain


Usage: python3 shapley.py [number of iterations]

The program runs the fictitious play dynamic for the
given number of iterations. It prints the successive
strategy pairs played and the number of successive 
iterations for which a pair is played. 
The strategies are numbered from 0.

In case of multiple best response a random pure
strategy is chosen.
"""

import random
import sys

def game_matrices(inmat):
  """
  Take a matrices of tuples representing payoffs in a
  two-player game. Return a tuple of two matrices, one for
  each player. The rows of a player's matrix correspond
  to that player's actions, the columns to the opponent's 
  actions
  """

  R = len(inmat)
  C = len(inmat[0])

  outmat1 = list([0]*C for i in range(R))
  outmat2 = list([0]*R for j in range(C))

  for i in range(R):
    for j in range(C):
      outmat1[i][j] = inmat[i][j][0]
      outmat2[j][i] = inmat[i][j][1]

  return outmat1,outmat2

def best_response(mat,w):
  """
  Given a payoff matrix and a vector of weights w
  calculate the best response to the opponent's mixed strategy
  corresponding to distribution obtained by normalising w.
  """

  R,C = len(mat),len(mat[0])
  payoffs = [0]*R
  for i in range(R):
    for j in range(C):
      payoffs[i] += mat[i][j]*w[j]
  M = max(payoffs)
  return [i for i in range(R) if payoffs[i]==M]


shapley = game_matrices([[(1,0), (0,0), (0,1)],
                         [(0,1), (1,0), (0,0)],
                         [(0,0), (0,1), (1,0)]])


if __name__=="__main__":
  if len(sys.argv)!=2:
    sys.stderr.write("Usage: shapley.py [number of iterations]\n")
    sys.exit(1)
  N = int(sys.argv[1])

  #Start from the strategy pair (0,0)
  w = [[1,0,0],[1,0,0]]
  old = [0,0]
  count = 1

  for n in range(N):
    t = [0,0]
    for k in range(2):
      t[k] = random.choice(best_response(shapley[k],w[1-k]))
    for i,s in enumerate(t):
      w[i][s]+=1
    if t==old:
      count += 1
    else:
      print("{0} {1}".format(old,
                             count))
      old = t
      count =1