# Viraj Pandya
# Homework Assignment 20 -- April 14, 2013
# I give permission to post

# Problem 1 -- purpose of t parameter not specified, assuming it's the max for i
# GatherStat(n,K,L,t) that inputs positive integers n, K, and L, and generates L times a random n by n matrices A, whose entries are from 0 to K, and outputs a list whose (i+1)-th item is the number of these that yield i Nash Equilibria for (A,tra(A)). In particular the first entry is the number of these matrices that have no pure equilibria. 

GatherStat:=proc(n,K,L,t) local V,num,i,S,A,s,j,k,c,l:

# S is a set of L random matrices generated via GenRanMat(n,n,K)
# "Generate L times... a random nxn matrix A" <-- this is how I read the statement
S:={}:

for i from 1 to L do
	S:={op(S),GenRanMat(n,n,K)}:
od:

# V[i] gives # of matrices A in the list s for which nops(PNE(A,tra(A)))==i-1. 
# example, V[1] (first element) should give # of A's for whom nops(PNE(A,tra(A)))==0.
V:=[]:
# t is the maximum # of equilibria you want to check (i.e. max for i)
# making the assumption that t>=1

s:=[]:
# finding the list of sets of pure NE for each A that was generated
for k from 1 to L do
	s:=[op(s),PNE(A,tra(A))]:
od:

# looping through to create list V

for j from 1 to t do 
	c:=0:
	for l from 1 to nops(s) do
		if (nops(s[l])=j-1) then
			c:=c+1:
		fi:
	od:
	V:=[op(V),c]:	
od:

V;

end:

####### problem 2#######

# with n=5, K=25, L=1000, t running from 1,2,3... based on part below

# (i) no pure nash equilibria (t=1)
# seq(GatherStat(5,25,1000,1),i=1..50);
# get all same output [0]
# 0 games with 0 nash equilibria
# feel like something is wrong, can't find error in my code for number 1
# else 100%

# (ii) exactly one NE (t=2)
# get all same output [0,1000]
# means all 1000 games have exactly 1 nash equilibrium, and none have 0 nash equilibria

# (iii) exactly two NE (t=3)
# get all same output [0,1000,0]
# means all 1000 games have 1 nash equilibria, and 0 have 0 or 2 nash equilibria


#Modify PNE(A,B) to write a procedure NE2(A,B,K) that inputs 2 by 2 matrices A, and B, and looks for not necessarily pure pairs [x,y] of Nash equilibria where y is the form [i/K,1-i/K] for i between 0 and K.

NE2:=proc(A,B,K) local m,n,nash,i,j,john,v:

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


nash:={}:

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

		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:
od:

nash:

end:


#Modify PNE2(A,B,K) to write a procedure NE3(A,B,K) that inputs 3 by 3 matrices A, and B, and looks for not necessarily pure Nash equilibria pairs [x,y] of Nash equilibria where y is the form [i/K,j/K,k/K] for i,j,k between 0 and K and, of course i+j+k=K 

NE3:=proc(A,B,K) local m,n,nash,i,j,john,u,v,w:

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


nash:={}:

for j from 1 to n do
	for u from 0 to K do
		for v from 0 to K-u do
			for w from 0 to K-v-u do
				john:=BRrow(A,[u/K,v/K,w/K]):
	

				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:	
		od:	
	od:
od:

nash:

end:



# LetsCooperate(A,B,i,j) inputs matrices A and B of the same size, i, j such that [i,j] is a pure Nash equilibrium, and outputs the (possibly empty) set of pairs [r,s] such that 
# A[r][s]>A[i][j]   B[r][s]>B[i][j]  
# In other words, if the "prisoners" had a secret cell phone or otherwise could communicate, they could propose to each other to choose strategies that are not Nash Equilibria, but are better for both of them (like to both cooporate in the famous original Prisoners' Dillema). 

LetsCooperate:=proc(A,B,i,j) local r,s,S:

S:={}:
#assume A and B are of same size 
# first loop runs from row to row  ( matrix = list of lists, remember?)
for r from 1 to nops(A) do
	for s from 1 to nops(A[1]) do
		if ((A[r][s]>A[i][j]) and (B[r][s]>B[i][j])) then
			S:={op(S),[r,s]}:
		fi:
	od:
od:

S;

end:






########################### OLD STUFF #############################

#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: