#OK to post homework
#Victoria Chayes, 2/20/2022, Assignment 9

with(combinat):
Help:=proc(): print(`All2NashEq(T,R,S,P), All3NashEq(a11,a12,a13,a21,a22,a23,a31,a32,a33), Snowdrift(T,R,S,P)`): end:

#############################################

#########

#3 For the Snowdrift (aka Ballet/Fight) symmetric 2-person [[[R,R],[S,T]],[[T,S],[P,P]] with the assumption T > R > S > P find a closed-form expression, in terms of the parameters T,R,S,P for the sum of tha payoffs in the MIXED Nash equilibrium, that always exists.

# We first want to calculate the mixed Equilibrium, using:

# assume(T>R, R>S, S>P)
# MNE22(Snowdrift(T,R,S,P))
#   {[0,1], [1,0], [(P-S)/(P+R-S-T), (P-S)/(P+R-S-T)]}
      
# As this is symmetric, the payoff can be calculated as 2*PayOffGG(Snowdrift(T,R,S,P),(P-S)/(P+R-S-T),(P-S)/(P+R-S-T))[1] as 

#2*( (P+R-S-T)*[(P-S)/(P+R-S-T)]^2 +(-2P+S+T)*[(P-S)/(P+R-S-T)] + P)


#########

#4 Using "assume", use MNE2, to find all the Nash Equilbria (pure and mixed) for all symmetric 2-player games with 2 strategies each, symbolically in terms of T,R,S,P. For all 24 orderings of T,R,S,P. How many of these permutations yield a mixed NE?

All2NashEq:=proc(T,R,S,P) local SD,C,L,i,count,G:
SD:=Snowdrift(T,R,S,P):
if type(T, numeric) then
G:=MNE2(SD):
if nops(G minus {[[0, 1], [1, 0]], [[1, 0], [0, 1]]})<>0 then
print(1):
else
print(0):
fi:
return({[[T,R,S,P],G]}):
fi:

C:=permute([T,R,S,P]):
L:={}:
count:=0:

for i from 1 to nops(C) do
 assume(C[i][1]>C[i][2], C[i][2]>C[i][3], C[i][3]>C[i][4]):
 G:=MNE2(SD):
 if nops(G minus {[[0, 1], [1, 0]], [[1, 0], [0, 1]]})<>0 then
  count:=count+1:
 fi:
 L:=L union {[C[i],G]}:
od:

print(count):
L:
end:

# If the above program worked correctly, all 24 permutations yield a mixed NE. 

#########

#5 For all possible 9!=362880 permutations of ordering a11,a12,a13,a21,a22,a23,a31,a32,a33, find the mixed Nash equibria for the symmetric game 
#  [a11,a11],[a12,a21],[a13,a31]
#  [a21,a12],[a22,a22],[a23,a32]
#  [a31,a13],[a32,a23],[a33,a33]
# and find how many have only mixed strategies.

#LazySym3x3: inputs a string of nine numbers or symbols, and outputs the bimatrix of the symmetric game with those payoff values.
LazySym3x3:=proc(a11,a12,a13,a21,a22,a23,a31,a32,a33):
[[[a11,a11],[a12,a21],[a13,a31]],[[a21,a12],[a22,a22],[a23,a32]],[[a31,a13],[a32,a23],[a33,a33]]]:
end:

All3NashEq:=proc(a11,a12,a13,a21,a22,a23,a31,a32,a33) local C,G,EQ,L,count,i:
C:=permute([a11,a12,a13,a21,a22,a23,a31,a32,a33]):
L:={}:
count:=0:
for i from 1 to nops(C) do
 assume(C[i][1]>C[i][2], C[i][2]>C[i][3], C[i][3]>C[i][4],C[i][4]>C[i][5],C[i][5]>C[i][6],C[i][6]>C[i][7],C[i][7]>C[i][8],C[i][8]>C[i][9]):
 G:=LazySym3x3(a11,a12,a13,a21,a22,a23,a31,a32,a33):
 EQ:=MNE2(G):
 if nops(EQ minus {[[0, 1], [1, 0]], [[1, 0], [0, 1]]})<>0 then
  count:=count+1:
 fi:
 L:=L union {[C[i],G]}:
od:

print(count):
L:
end:

# I have left this evaluating, and will let you know if overnight it resolves. 

#########

#############################################

#From Class and Previous HW

Snowdrift:=proc(T,R,S,P)
[[[ R, R ] , [ S, T ]],[[ T, S ] , [ P, P ]]]:
end:

#PayOffGG(G,p1,p2): Inputs a 2-player game with m:=nops(G) strategies for player Row, and n:=nops(G[1]) strategies for Player Col
#given in terms of its bi-matrix, and probability vectors [p1[1],...p1[m]] and probabilty vectors [p2[1],...p2[m]]
#outputs the pay-off vectors
PayOffGG:=proc(G,p1,p2) local i1,i2,m,n:
m:=nops(G):
n:=nops(G[1]):

if not (nops(p1)=m and nops(p2)=n) then
print(`bad input`):
 RETURN(FAIL):
fi:

[add(add(G[i1][i2][1]*p1[i1]*p2[i2],i2=1..n),i1=1..m), add(add(G[i1][i2][2]*p1[i1]*p2[i2],i2=1..n),i1=1..m)]:

end:

#BRLG(f,var): Given a linear expression f in x[1],..., x[nops(x)] finds the best response conditions as a set of sets of condtions
#Try:
#BRLG(a1*x+a2*y+a3*z,{x,y,z});
BRLG:=proc(f,var) local S,s,sC,CON,s1,i1:
S:=powerset(var) minus {{}}:

CON:={}:
for s in S do
sC:=var minus s:
CON:=CON union {{add(s1,s1 in s)=1, seq(coeff(f,s[1],1)>coeff(f,s1,1),s1 in sC), seq(coeff(f,s[1],1)=coeff(f,s[i1],1),i1=2..nops(s))}}:
od:
CON:
end:




#MNE2(G): The set of mixed Nash equilibria for a 2-person game with each player having two strategies, where G is given
#as a 2 by 2 bimatrix. It gives all the pairs (p1,p2) such that if 
#Player Row plays stragety R1 with prob. p1 (and hence strategy R2 with prob. 1-p1)
#and Player Col plays stragety C1 with prob. p2 (and hence strategy C2 with prob. 1-p2)
#these stochastic stragies are Best responses to each other, in the sense that for either player
#deviating from them (while the other player keeps his or her strategy) will make her or his
#EXPETED payoff worse. Try:
#G:=RG(3,3,100); MNE2(G):

MNE2:=proc(G) local p1,p2,P, m,n,L1,L2,i1,i2,eq,j,S,sol,BLAIR:
m:=nops(G):
n:=nops(G[1]):
P:=PayOffGG(G,[seq(p1[i1],i1=1..m)],[seq(p2[i1],i1=1..n)]):



L1:=BRLG(P[1],{seq(p1[i1],i1=1..m)}):
L2:=BRLG(P[2],{seq(p2[i1],i1=1..n)}):


S:={}:

#following a suggestion of Blair Seidler to compute the "infra-structre" condtions just once
BLAIR:=
{seq(p1[i1]>=0,i1=1..m),seq(p1[i1]<=1,i1=1..m),
seq(p2[i1]>=0,i1=1..n),seq(p2[i1]<=1,i1=1..n),
add(p1[i1],i1=1..m)=1,add(p2[i1],i1=1..n)=1}  :

for i1 from 1 to nops(L1) do
for i2 from 1 to nops(L2) do

eq:=BLAIR union L1[i1] union L2[i2]:

sol:=[solve(eq,{seq(p1[i1],i1=1..m),seq(p2[i1],i1=1..n)})]:


for j from 1 to nops(sol) do
S:=S union 
{subs(sol[j], [[seq(p1[i1],i1=1..m)],[seq(p2[i1],i1=1..n)]])}:
od:

od:
od:
S:
end: