#OK to post homework 
#Natalya Ter-Saakov, Jan 30, Assignment 2 read "C3.txt";

read "hw2NatalyaTer-Saakov.txt":
G:=RandDisGame(4,4):
matrix(G);
# [[[1, 16], [11, 9], [14, 1], [12, 12]], [[16, 11], [2, 4], [10, 2], [9, 5]], [[15, 14], [5, 8], [8, 13], [4, 3]], [[6, 10], [7, 6], [3, 15], [13, 7]]]

#If Player Row goes first and... 
# if R1, then Col plays C1 
# if R2, then Col plays C1 
# if R3, then Col plays C1 
# if R4, then Col plays C3 
#So the outcome will be [16,11] with strategies (2,1) 

#If Player Col goes first and... 
# if C1, then Row plays R2 
# if C2, then Row plays R1 
# if C3, then Row plays R1 
# if C4, then Row plays R4 
#So the outcome will be [16,11] with strategies (2,1)

#The set of pure Nash equilibria is {[2,1]} 
#This can be verified by running... 
DynRC(G);DynCR(G);PureNashEqui(G);
#                               [2, 1], [16, 11]
#                               [2, 1], [16, 11]
#                                   {[2, 1]}

G1:=RandDisGame(5,7): matrix(G1);
#[[[28, 6], [9, 15], [8, 20], [35, 30], [6, 19], [16, 1], [20, 34]], [[7, 27], [11, 14], [25, 17], [30, 21], [5, 32], [17, 28], [15, 16]], [[26, 25], [33, 2], [21, 11], [4, 26], [34, 3], [29, 4], [23, 9]], [[13, 13], [19, 10], [14, 18], [1, 5], [10, 29], [18, 33], [27, 12]], [[3, 23], [32, 22], [31, 35], [24, 8], [12, 7], [2, 24], [22, 31]]]

#If Player Row goes first and... 
# if R1, then Col plays C7 
# if R2, then Col plays C6 
# if R3, then Col plays C4 
# if R4, then Col plays C6 
# if R5, then Col plays C3 
#So the outcome will be [31,35] with strategies (5,3) 

#If Player Col goes first and... 
# if C1, then Row plays R1 
# if C2, then Row plays R3 
# if C3, then Row plays R5 
# if C4, then Row plays R1 
# if C5, then Row plays R3
# if C6, then Row plays R3 
# if C7, then Row plays R4 
#So the outcome will be [31,35] with strategies (5,3) 

#The set of pure Nash equilibria is {[5,3]}
#This can be verified by running... 
DynRC(G1);DynCR(G1);PureNashEqui(G1);
#                               [5, 3], [31, 35]
#                               [5, 3], [31, 35]
#                                   {[5, 3]}

with(combinat):

#AllGames is slow, there are two improvements on it below, AllGamesFaster and AllGamesFastest

#AllGames(a,b): inputs positive integers a and b and outputs the set of (a*b)!^2 Games where each player's payoffs are distinct that drawn from {1, ..., a*b}
AllGames:= proc(a,b) local per, pi1,pi2,i1,j1, games:
 games:= {}:
 per:= permute(a*b):
 for pi1 in per do
  for pi2 in per do 
   games:= games union {[seq([seq([pi1[b*i1+j1],pi2[b*i1+j1]],j1=1..b)],i1=0..a-1)]}: 
  od:
 od:
 games:
end:

#AllGamesFaster(a,b): inputs positive integers a and b and outputs the set of(a*b)!^2 Games where each player's payoffs are distinct that drawn from {1,..., a*b} 
AllGamesFaster:= proc(a,b) local per, pi1,pi2,i1,j1, games:
 games:= {}:
 per:= permute(a*b):
 for pi1 in per do
  games:= games union {seq([seq([seq([pi1[b*i1+j1],pi2[b*i1+j1]],j1=1..b)],i1=0..a-1)],pi2 in per)}:
 od:
 games: 
end:

#AllGamesFastest(a,b): inputs positive integers a and b and outputs the set of (a*b)!^2 Games where each player's payoffs are distinct that drawn from {1, ..., a*b} 
AllGamesFastest:= proc(a,b) local per, pi1,pi2,i1,j1, games:
 per:= permute(a*b):
 games:= {seq(seq([seq([seq([pi1[b*i1+j1],pi2[b*i1+j1]],j1=1..b)],i1=0..a-1)],pi2 in per), pi1 in per)}:
 games: 
end:

#Just like AllGames, there are three versions of FullStat: FullStatSlow, FullStat, and FullStatFast. I have no idea whether FullStat or FullStatFast runs faster.
#FullStatSlow(a,b): inputs positive integes a and b (not too big!) and outputs the following list (using AllGames) 
#[Number of Games with No Nash Equilibria, Number of Games with One Nash Equilibria, Number of Games with Two Nash Equilibria, 
#Number of Games where the Row Player was better off playing second, Number of Games where the Column Player was better off playing second, Number of Games where DynRC(G)=DynCR(G)] 

FullStatSlow:= proc(a,b) local games, game, nash, dynRC, dynCR, noNash, oneNash, twoNash, rowSec, colSec, sameRes:
 games:=AllGames(a,b): 
 noNash:=0: oneNash:=0: twoNash:=0: rowSec:=0: colSec:=0: sameRes:=0:
 for game in games do 
  nash:=PureNashEqui(game): dynRC:=DynRC(game): dynCR:=DynCR(game):
  if nops(nash)=0 then
   noNash+=1 
  elif nops(nash)=1 then
   oneNash+=1
  elif nops(nash)=2 then
   twoNash+=1:
  fi: 
#If col going first yields a better result for row than row going first... 
  if dynCR[2][1]>dynRC[2][1] then
   rowSec+=1: 
  fi: 
#If row going first yields a better result for col than col going first... 
  if dynRC[2][2]>dynCR[2][2] then 
   colSec:= colSec +1: 
  fi: 
  if dynRC=dynCR then
   sameRes+=1:
  fi: 
 od: 
 return [noNash, oneNash, twoNash, rowSec, colSec,sameRes]: 
nd:

#FullStat(a,b): inputs positive integes a and b (not too big!) and outputs the following list 
#[Number of Games with No Nash Equilibria, Number of Games with One Nash Equilibria, Number of Games with Two Nash Equilibria,
# Number of Games where the Row Player was better off playing second, Number of Games where the Column Player was better off playing second, Number of Games where DynRC(G)=DynCR(G)]

FullStat:= proc(a,b) local per, pi1, pi2,i1, j1, game, nash, dynRC, dynCR, noNash, oneNash, twoNash, rowSec, colSec, sameRes:
 noNash:=0: oneNash:=0: twoNash:=0: rowSec:=0: colSec:=0: sameRes:=0: per:= permute(a*b):
 for pi1 in per do
  for pi2 in per do
   game:= [seq([seq([pi1[b*i1+j1],pi2[b*i1+j1]],j1=1..b)],i1=0..a-1)]:
   nash:=PureNashEqui(game): dynRC:=DynRC(game): dynCR:=DynCR(game): 
   if nops(nash)=0 then
    noNash+=1 
   elif nops(nash)=1 then
    oneNash+=1 
   elif nops(nash)=2 then 
    twoNash+=1: 
   fi: 
#If col going first yields a better result for row than row going first... 
   if dynCR[2][1]>dynRC[2][1] then rowSec+=1: fi:
#If row going first yields a better result for col than col going first... 
   if dynRC[2][2]>dynCR[2][2] then colSec+=1: fi:
   if dynRC=dynCR then sameRes+=1: fi: 
  od:
 od:
 return [noNash, oneNash, twoNash, rowSec, colSec,sameRes]: 
end:

FullStat(2,2);
#                          [72, 432, 72, 72, 72, 420]

FullStat(3,2);
#                 [86400, 345600, 86400, 86760, 83952, 331560]


#FullStatFast(a,b): inputs positive integes a and b (not too big!) and outputs the following list (using AllGames) 
#[Number of Games with No Nash Equilibria, Number of Games with One Nash Equilibria, Number of Games with Two Nash Equilibria, 
# Number of Games where the Row Player was better off playing second, Number of Games where the Column Player was better off playing second, Number of Games where DynRC(G)=DynCR(G)] 

FullStatFast:= proc(a,b) local games, game, nash, dynRC, dynCR, noNash, oneNash, twoNash, rowSec, colSec, sameRes:
 games:=AllGamesFastest(a,b): 
 noNash:=0: oneNash:=0: twoNash:=0: rowSec:=0: colSec:=0: sameRes:=0: 
 for game in games do 
  nash:=PureNashEqui(game): dynRC:=DynRC(game): dynCR:=DynCR(game): 
  if nops(nash)=0 then 
   noNash+=1 
  elif nops(nash)=1 then 
   oneNash+=1 
  elif nops(nash)=2 then
   twoNash+=1: 
  fi: 
#If col going first yields a better result for row than row going first... 
  if dynCR[2][1]>dynRC[2][1] then rowSec+=1: fi: 
#If row going first yields a better result for col than col going first... 
  if dynRC[2][2]>dynCR[2][2] then colSec+=1: fi: 
  if dynRC=dynCR then sameRes+=1: fi:
 od: 
 return [noNash, oneNash, twoNash, rowSec, colSec,sameRes]: 
end:

FullStatFast(3,2);
#                 [86400, 345600, 86400, 86760, 83952, 331560]

#SampleStat(a,b,K): inputs positive integers a and b, and a fairly large positive integer K, and generates K random games where Row has a strategies and Col has b strategies 
# then calculates evalf( [(Number of Games with No Nash Equilibria)/K, (Number of Games with One Nash Equilibria)/K, (Number of Games with Two Nash Equilibria)/K, 
#  (Number of Games where the Row Player was better off playing second)/K, (Number of Games where the Column Player was better off playing second)/K, (Number of Games where DynRC(G)=DynCR(G))/K]): 

SampleStat:= proc(a,b,K) local i, games, game, nash, dynRC, dynCR, noNash, oneNash, twoNash, rowSec, colSec, sameRes:
 noNash:=0: oneNash:=0: twoNash:=0: rowSec:=0: colSec:=0: sameRes:=0: 
 for i from 1 to K do:
  game:=RandDisGame(a,b): nash:=PureNashEqui(game): dynRC:=DynRC(game): dynCR:=DynCR(game):
  if nops(nash)=0 then 
   noNash+=1 
  elif nops(nash)=1 then
   oneNash+=1 
  elif nops(nash)=2 then 
   twoNash+=1: 
  fi: 
#If col going first yields a better result for row than row going first... 
  if dynCR[2][1]>dynRC[2][1] then rowSec+=1: fi: 
#If row going first yields a better result for col than col going first... 
  if dynRC[2][2]>dynCR[2][2] then colSec+=1: fi: 
  if dynRC=dynCR then sameRes+=1: fi:
 od:
 return evalf([noNash/K, oneNash/K, twoNash/K, rowSec/K, colSec/K,sameRes/K]): 
end:

SampleStat(10,10,10000);
#   [0.3321000000, 0.4144000000, 0.2001000000, 0.2994000000, 0.2976000000, 0.3375000000]

SampleStat(10,10,10000);
#   [0.3276000000, 0.4073000000, 0.2048000000, 0.2873000000, 0.2944000000, 0.3391000000]

SampleStat(10,10,10000);
#   [0.3369000000, 0.4036000000, 0.1976000000, 0.2981000000, 0.2993000000, 0.3392000000]

SampleStat(10,10,10000);
#   [0.3283000000, 0.4090000000, 0.2023000000, 0.2953000000, 0.2920000000, 0.3348000000]

SampleStat(10,10,10000);
#   [0.3226000000, 0.4127000000, 0.2003000000, 0.2911000000, 0.2922000000, 0.3441000000]

#These are all approximately [0.33, 0.41, 0.20, 0.29, 0.29, 0.34]