#April 8, 2013, Nash Equilibria for general two player games

Help:=proc(): print(`MaxF(F,x,n) , BRrow(A,y) , BRcol(B,x) `): 
print(`PNE(A,B) , GenRanMat(m,n,K) , tra(A) `):
end:

#Given two matrices A and B m by n
#PayOff for A: xAy Payoff for B: xBy (x is a row vector of 
#size m and y is a column of size n)
#(x,y) is a Nash Equilibrium if x is in BestResponse(A,y)
#and y is in BestResponse(B,x)

#MaxF(F,x,n): inputs sumbol x, positive integer n
#and a linear combination of x[1], ..., x[n]
#outputs the set of i such that x[i]=1 makes F max
#For example,
#MaxF(3*x[1]+4*x[2]+4*x[3]+2*X[4],x,4);
MaxF:=proc(F,x,n) local i,champs,rec,nathan:

champs:={1}:
rec:=coeff(F,x[1],1):

for i from 2 to n do

nathan:=coeff(F,x[i],1):

 if nathan=rec then
   champs:=champs union  {i}:
 elif nathan>rec then
    champs:={i}:
   rec:=nathan:
 fi:

od:
    
champs:

end:

#BRrow(A,y): The best response by the ROW player
#(whose payoff matrix is the m by n matrix A
#to the strategy y of the column player
#output is a set of pure strategies
BRrow:=proc(A,y) local i,j,F,x,m,n:
m:=nops(A):
n:=nops(A[1]):
F:=add(add(x[i]*A[i][j]*y[j],i=1..m),j=1..n):

MaxF(F,x,m):

end:

#BRcol(B,x): The best response by the COL player
#(whose payoff matrix is the m by n matrix B
#to the strategy x of the row player
#output is a set of pure strategies
BRcol:=proc(B,x) local i,j,F,y,m,n:
m:=nops(B):
n:=nops(B[1]):
F:=add(add(x[i]*B[i][j]*y[j],i=1..m),j=1..n):

MaxF(F,y,n):

end:


#PNE(A,B)
PNE:=proc(A,B) local m,n,nash,i,j,john:

m:=nops(A):
n:=nops(A[1]):


nash:={}:

for j from 1 to n do
john:=BRrow(A,[0$(j-1),1,0$(n-j)]):

  for i in john do
 
     if j in BRcol(B,[0$(i-1),1,0$(m-i)]) then
       nash:=nash union {[i,j]}:
     fi:
  od:
od:

nash:

end:

#GenRanMat(m,n,K): a random m by n matrix with
#entries from 0 to K
GenRanMat:=proc(m,n,K) local i,j,tim:

tim:=rand(0..K):

[seq([seq(tim(),j=1..n)],i=1..m)]:

end:


#transpose of A
tra:=proc(A) local i,j,m,n:
m:=nops(A):
n:=nops(A[1]):
[seq([seq(A[j][i],j=1..m)],i=1..n)]:
end: