Help:=proc(): print(` RandGameGm(L),  Zmns(m,n,s) , Zmnt(m,n,t),  IsComp(S), WtSeq(L) , ZLs(L,s), ZLt(L,t) `): end:

Help22:=proc(): print(`MNE(M) , AllStrats(L) , RandGameG(L,K1,K2), IsNE(s,G), PNEg(G) `): end:



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

Help21:=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, BRcol(M,j)) and member(j, BRrow(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:

##End C21.txt

MNE:=proc(G) local p,q,P,N:

P:=ExGain(G,p,q) :

if coeff(P[2],q,1)=0 or coeff(P[1],p,1)=0 then
 RETURN({}):
fi:

if  (solve(coeff(P[2],q,1),p)=NULL or solve(coeff(P[1],p,1),q)=NULL) then
 RETURN({}):
fi:

N:=[solve(coeff(P[2],q,1),p), solve(coeff(P[1],p,1),q)]:

if not (N[1]>=0 and N[1]<=1 and N[2]>=0 and N[2]<=1) then
 RETURN({}):
fi:



if maximize(subs(q=N[2],P[1]),p=0..1)=subs({p=N[1],q=N[2]},P[1]) and maximize(subs(p=N[1],P[2]),q=0..1)=subs({p=N[1],q=N[2]},P[2]) then
 RETURN(N):
else
 RETURN({}):
fi:

end:


#AllStrats(L): inputs a list of positive integers L, describes all the possible strategies in a nops(L)-player game
#where player i has the L[i] possible strategies {1,..., L[i]}. For example Try:
#AllStrats([2,3,2]);
AllStrats:=proc(L) local S,L1,s,i:
if L=[] then
 RETURN({[]}):
fi:

L1:=[op(1..nops(L)-1,L)]:

S:=AllStrats(L1):

{seq(seq([op(s),i],s in S), i=1..L[nops(L)])}:

end:


#RandGameG(L,K1,K2): A random nops(L)-player game with payoffs between K1 and K2, presented as a table
#Try:
#RandGame([2,2,2],0,10);
RandGameG:=proc(L,K1,K2) local S,ra,T,s,i:
 S:=AllStrats(L):
 ra:=rand(K1..K2):

for s in S do
 T[s]:=[seq(ra(),i=1..nops(s))]:
od:

[L,S,op(T)]:

end:

#RandGameGm(L): A random nops(L)-player game with distinct payoffs each from 1 to the number of joint strategoes, presented as a table
#Try:
#RandGameGm([2,2,2]);
RandGameGm:=proc(L) local i,s,Per,S,NuS,T:

NuS:=mul(L[i],i=1..nops(L)):

 S:=AllStrats(L):

for i from 1 to nops(L) do

 Per[i]:=randperm(NuS):
od:

for s from 1 to nops(S)  do

 T[S[s]]:=[seq(Per[i][s],i=1..nops(L))]:
od:

[L,S,op(T)]:

end:


#IsNE(s,G): Is s a Nash Equilibrim of the game [S,T] where T[s] is the payoff-vector for the strategy choice s.
#Try:
#G:=RandGame([2,2,2],0,10); IsNE([1,1,1],[2,2,2],G):
IsNE:=proc(s,G) local L,S, T,Alts,s1,i,j:
L:=G[1]:
S:=G[2]:
T:=G[3]:

if not member(s, S) then
 print(s, `is not a valid strategy-choice`):
 RETURN(FAIL):
fi:


for i from 1 to nops(s)  do
 Alts:={seq([op(..i-1,s),j,op(i+1..nops(s),s)],j=1..L[i])}:
  if max(seq(T[s1][i],s1 in Alts))<>T[s][i] then
   RETURN(false):
  fi:
od:

true:

end:

   



#PNEg(G): The set of pure Nash Equilibria for the game G
PNEg:=proc(G) local S,s,N:
S:=G[2]:

N:={}:

for s in S do
 if IsNE(s,G) then
   N:=N union {s}:
 fi:
od:

N:

end:

###New stuff

#Zmns(m,n,s): The prob. that there are exactly s Pure Nash Equilbria in a random 2-player game where Players 1 and 2 having  m and n strategies
Zmns:=proc(m,n,s) local r:
add((-1)^(r-s)*binomial(r,s)*binomial(m,r)*binomial(n,r)*r!/(m*n)^r,r=s..min(m,n)):
end:

#Zmnt(m,n,t): The polynomial of degree min(m,n) in t whose coefficient of t^s is the prob. of  having exactly s pure Nash Equilibria in
#a random 2-player game where Players 1 and 2 having  m and n strategies
Zmnt:=proc(m,n,t) local s: 
add(Zmns(m,n,s)*t^s,s=0..min(m,n)):
end:


#IsComp(S): inputs a set of strategies, S, and outputs true iff they are compatible:
#Try:
#IsComp({[1,1],[1,2]});
IsComp:=proc(S) local g,i, s, S1:

if S={} then
 RETURN(true):
fi:

g:=nops(S[1]):

for i from 1 to g do
 S1:={seq([op(1..i-1,s),op(i+1..g,s)], s in S)}:
 if nops(S1)<nops(S) then
  RETURN(false):
 fi:
od:

true:

end:

#WtSeq(L): The weight sequence if the list of available stragegies is L, it is a list of length mul(L[i],i=1..nops(L))
#Try:
#WtSeq([2,2]);
WtSeq:=proc(L) local  w,g,i,S,T,r,s:
option remember:
w:=1/mul(L[i],i=1..nops(L)):

S:=AllStrats(L):
g:=nops(S):
S:=powerset(S):

for r from 1 to g do
 T[r]:=0:
od:

for  s in S do
 if IsComp(s) then
  T[nops(s)]:=T[nops(s)]+w^nops(s):
 fi:
od:

[seq(T[r],r=1..g)]:

end:






#ZLs(L,s): The prob. that there are exactly s Pure Nash Equilbria in a random nops(L)-player game where Players  i has L[i] strategy choices.
#Try
#ZLs([2,2],0);
ZLs:=proc(L,s) local W,r:
W:=WtSeq(L):
if s=0 then
1+add((-1)^(r)*W[r],r=1..nops(W)):
else
add((-1)^(r-s)*binomial(r,s)*W[r],r=s..nops(W)):
fi:
end:

#ZLt(L,t): The polynomial  in t whose coefficient of t^s is the prob. of  having exactly s pure Nash Equilibria in
#a random nops(L)-player game where Player i has L[i] strategy choices. Warning, VERY slow (but exact)
ZLt:=proc(L,t) local g,s: 
g:=convert(L,`*`):
add(ZLs(L,s)*t^s,s=0..g):
end: