#C21.txt: April 9, 2020
##Nash Equilibrium

Help:=proc(): print(`DB(), BRrow(M,j), BRcol(M,i) , PNE(M) , RandGame(A,B,K1,K2), ExGain(M,p,q) , All2Games()`):end:

with(combinat):

#DB(): A set of 5 classical 2-player games taken from the bible of Game Theory:
#A Course in Game Theory by Martin J. Osborne and Ariel Rubinstein [ a true masterpiece]
#https://sites.math.rutgers.edu/~zeilberg/EM20/OsborneRubinsteinMasterpiece.pdf
#

DB:=proc():
[
#Bach Or Stravisky, Fig. 16.1 (p. 16)
 [
  [[2,1],[0,0]],
  [[0,0],[1,2]]
 ],
#Mozart or Mahler, Fig. 16.2 (p. 16)
 [
  [[2,2],[0,0]],
  [[0,0],[1,1]]
 ],
#Prisoner's dillema, Fig. 17.1 (p. 17)
 [
  [[3,3],[0,4]],
  [[4,0],[1,1]]
 ],
#Hawk-Dove, Fig. 17.2 (p. 17)
 [
  [[3,3],[1,4]],
  [[4,1],[0,0]]
 ],
#Matching Pennies, Fig. 17.3 (p. 17)
 [
  [[1,-1],[-1,1]],
  [[-1,1],[1,-1]]
 ]

]
:
end:



#BRrow(M,j): Inputs
#(i) a bimatrix M , the so-called NORMAL FORM of a finite two-player game, that
#is  A by B list of lists where M[a][b] is the pair [PayoffForRowPlayer,PayoffForColPlayer]
#if Row Player adopts stragey a amd Col player adopts strategy b
#(ii) an integer j from 1 to B (One of the Column player's avaiable strategy
#outputs
#the Best Response(s) of the Row Player to that strategy. The set is usually a singleton, but in case of ties
#may have more than one element. For example, for the Best Response of the Row Player
#to Column's strategy 2  "Confess" type:
#BRrow(DB()[3],2);
BRrow:=proc(M,j) local rec,champs,A,B,i:
A:=nops(M): B:=nops(M[1]):

if not (1<=j and j<=B) then
 print(j, `is not a valid strategy for Col player`):
 RETURN(FAIL):
fi:

#champs is the current set of best responses to Col's strategy j, as we examine
#Row's possible responses, rec is the current record
champs:={1}:
rec:=M[1][j][1]:

for i from 2 to A do
if M[i][j][1]>rec then
#if strategy i is better than the previous best response it is now the only champion
  champs:={i}:
  rec:=M[i][j][1]:
elif M[i][j][1]=rec then
#the record is the same but there is a co-winnder
 champs:=champs union {i}:
fi:
od:
#We return the set of Champions
champs:
end:


#BRcol(M,i): Inputs
#(i) a bimatrix M , the so-called NORMAL FORM of a finite two-player game, that
#is  A by B list of lists where M[a][b] is the pair [PayoffForRowPlayer,PayoffForColPlayer]
#if Row Player adopts stragey a amd Col player adopts strategy b
#(ii) an integer i from 1 to A (One of the Row    player's avaiable strategy
#outputs
#the Best Response(s) of the Col Player to that strategy. The set is usually a singleton, but in case of ties
#may have more than one element. For example, for the Best Response of the Col Player
#to Row's strategy 2  "Confess" type:
#BRcol(DB()[3],1);
BRcol:=proc(M,i) local rec,champs,A,B,j:
A:=nops(M): B:=nops(M[1]):

if not (1<=i and i<=A) then
 print(i, `is not a valid strategy for Row player`):
 RETURN(FAIL):
fi:

#champs is the current set of best responses to Row's strategy i, as we examine
#Col's possible responses, rec is the current record
champs:={1}:
rec:=M[i][1][2]:

for j from 2 to B do
if M[i][j][2]>rec then
#if strategy j is better than the previous best response it is now the only champion
  champs:={j}:
  rec:=M[i][j][2]:
elif M[i][j][2]=rec then
#the record is the same but there is a co-winnder
 champs:=champs union {j}:
fi:
od:
#We return the set of Champions
champs:
end:





#PNE(M): Inputs
#a bimatrix M , the so-called NORMAL FORM of a finite two-player game, that
#is  A by B list of lists where M[a][b] is the pair [PayoffForRowPlayer,PayoffForColPlayer]
#if Row Player adopts stragey a amd Col player adopts strategy b
#outputs
#the (possibly empty) set of PURE NASH EQUILBRIA. Try:
#PNE(DB()[3]);

PNE:=proc(M) local A,B,i,j,S:
A:=nops(M):
B:=nops(M[1]):

#Row Player has A strategies {1, ..., A}
#Col Player has B strategies {1, ..., B}

#Recall that [i,j] is a Pure Nash Equilibrium if i is a member of BRcol(M,j) and j is a member of BRrow(M,i)
#Let S be the set of Pure Nash Equilibria
S:={};

for i from 1 to A do
 for j from 1 to B do

   if member(i, BRrow(M,j)) and member(j, BRcol(M,i)) then
    S:=S union {[i,j]}:
   fi:
 od:
od:

S:

end:

#RandGame(A,B,K1,K2): A random 2-player game 
#with A available strategies for the Row Player
#and  B available strategies for the Column Player
#with random pay-offs from K1 to K2, Try:
#RandGame(2,2,-1,1);
RandGame:=proc(A,B,K1,K2) local i,j,ra:
ra:=rand(K1..K2):

[seq([seq([ra(),ra()],j=1..B)],i=1..A)]:

end:

#ExGain(M,p,q): inputs a bi-matrix of  2 by 2 bi-matrix describing the payoffs of Row and Column player
#outputs the par [ExpectedGainForRow,ExpectedGainForCol] if 
#Player Row adopts strategy 1 with prob. p (and strategy 2 with prob. 1-p)
#Player Col adopts strategy 1 with prob. q (and strategy 2 with prob. 1-q)
#Note that these are polynomials of degree 1 in p and in q separately
ExGain:=proc(M,p,q) local k:

if not (nops(M)=2 and nops(M[1])=2) then
 print(`Not 2 by 2`):
 RETURN(FAIL):
fi:

expand([seq(M[1][1][k]*p*q+M[1][2][k]*p*(1-q)+M[2][1][k]*(1-p)*q+M[2][2][k]*(1-p)*(1-q),k=1..2)]):

end:


##Added right before class, APril 9, 2020
#All2Games(): All 2-person games with different payoffs for each player from {1,2,3,4}. Try:
#All2Games();
All2Games:=proc() local P,pi1,pi2:

P:=permute(4):

{
seq(
  seq(
     [
       [ [pi1[1],pi2[1]],[pi1[2],pi2[2]] ],
       [ [pi1[3],pi2[3]],[pi1[4],pi2[4]] ]
     ],
pi1 in P),
pi2 in P)
}:

end: