#OK to post homework
#Victoria Chayes, 1/30/2022, Assignment 2

Help:=proc(): print(`IsNash(G,a1,a2),PureNashEqui(G)`) end:

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

#2  Read, understand, and experiment with the Maple code of C2.txt , by generating five random games, and finding the Best-Response lists of the Row and Column Player.

# For ease of space, recording one such game: 

# G:=Rand2PlayerGame(3,3,5): matrix(G)
#  [[4, 1], [2, 2], [1, 2]]
#  [[4, 2], [5, 1], [1, 4]] 
#  [[5, 1], [4, 1], [1, 0]]
# BR1v(G)
#   [{3}, {2}, {1, 2, 3}]
# BR2v(G)
#   [{2, 3}, {3}, {1, 2}]


#########

#4 Using procedures BR1v(G) and BR2v(G), write a one-line Maple procedure IsNash(G,a1,a2) that inputs a 2-player game bi-matrix G, and members a1,a2 of A1, A2 respectively (that in our convention are integers from {1, ..., nops(G)} and {1, ..., nops(G[1])}) and outputs true or false according to whether [a1,a2] is a Nash Equilibrium.

IsNash:=proc(G,a1,a2):
if member(a1, BR1(G,a2)) and member(a2, BR2(G,a1)) then
return(true):
fi:
false:
end:

#Note: it seemed more efficient to use BR1 and BR2 to reduce the number of calculations, rather than BR1v and BR2v. Considering the if statement as one line, this program is 2 lines, but I didn't see an easy way to shorten it. 

#########

#5 Write a procedure PureNashEqui(G) that inputs a bi-matrix G, and outputs the (possibly empty) set of pairs [a1,a2] that are (pure) Nash Equilibria. Generate 5 random 2-player games where Player Row has 10 strategies, and Player Column has 12 strategies, and for each find their set of (pure) Nash Equilibria

PureNashEqui:=proc(G) local N1,N2,S,i,j,k:
N1:=BR1v(G):
N2:=BR2v(G):
S:={}:
for i from 1 to nops(N1) do
  for j from 1 to nops(N1[i]) do
    k:=N1[i][j]:
    if member(i,N2[k]) then
     S:=S union {[k,i]}:
    fi:
 od:
od:
S:
end:

# For ease of space, recording one such game: 
# G:=Rand2PlayerGame(10,12,5): matrix(G)
# [[4, 5], [2, 4], [0, 1], [1, 4], [1, 1], [4, 1], [4, 4], [4, 3], [1, 2], [2, 3], [2, 2], [4, 5]] 
# [[0, 1], [0, 0], [4, 2], [4, 5], [3, 5], [3, 4], [1, 0], [0, 0], [2, 1], [4, 0], [0, 3], [0, 4]] 
# [[0, 2], [1, 3], [2, 2], [2, 5], [2, 1], [4, 0], [0, 0], [3, 1], [3, 4], [2, 5], [0, 1], [4, 1]] 
# [[2, 4], [0, 1], [3, 2], [5, 4], [4, 1], [5, 3], [2, 1], [3, 1], [2, 4], [4, 1], [2, 5], [0, 2]] 
# [[1, 0], [3, 0], [5, 3], [0, 1], [0, 1], [1, 4], [1, 4], [3, 5], [5, 2], [1, 0], [3, 2], [3, 0]] 
# [[1, 0], [1, 3], [4, 1], [1, 4], [5, 0], [2, 0], [1, 4], [0, 0], [0, 5], [4, 2], [2, 1], [2, 4]] 
# [[0, 2], [3, 0], [4, 5], [2, 5], [1, 3], [0, 2], [3, 5], [1, 5], [1, 3], [5, 4], [0, 0], [1, 0]] 
# [[4, 4], [2, 3], [0, 4], [3, 1], [3, 4], [2, 3], [1, 1], [5, 0], [2, 3], [3, 3], [3, 0], [4, 3]] 
# [[4, 1], [5, 1], [1, 1], [2, 4], [5, 1], [5, 0], [1, 1], [4, 2], [1, 2], [3, 2], [4, 5], [4, 4]] 
# [[2, 0], [0, 1], [2, 3], [4, 3], [1, 1], [2, 2], [1, 1], [0, 5], [1, 5], [3, 2], [0, 3], [1, 0]]])

# BR1v(G)
# [{1, 8, 9}, {9}, {5}, {4}, {6, 9}, {4, 9}, {1}, {8}, {5}, {7},  {9}, {1, 3, 8, 9}]
# BR2v(G)
# [{1, 12}, {4, 5}, {4, 10}, {11}, {8}, {9}, {3, 4, 7, 8}, {1, 3, 5}, {11}, {8, 9}]

#PureNashEqui(G)
#  {[1, 1], [1, 12], [8, 1], [9, 11]}


#########

#############################################
#  Programs From C2.txt  


#C2.txt: Maple Code for Lecture 2 of Math640 (Spring 2022)

Help2:=proc(): print(` GameDB(), Rand2PlayerGame(a,b,K), IsStictDom(v1,v2), FindR(G), FindC(G), ShrinkGame(G), ReducedGame(G) , MyMaxIndex(L), LoadedCoin(p), BR1(G,a2), BR2(G,a1), BR1v(G), BR2v(G)  `):end:



###PREPARED BEFORE CLASS

#GameDB(): A list of length 5 consisiting of a a "data base"  of famous gamess (and less famous ones): 
#Prisoner's dillema, Boattle of the Sexes,  Matching pennies, Figure 1.1.1. in Gibbons, Figure 1.1.4 in Gibbons
#For example, to see the Prisoner's dillema, type
#GameDB()[1])
GameDB:=proc():
[

[ [ [[-1,-1],[-9,0]], [[0,-9],[-6,-6]]], [`Mum`, `Fink`], [`Mum`, `Fink`]],

[ [ [[2,1],[0,0]], [[0,0],[1,2]]], [`Box`, `Opera`],[`Box`, `Opera`]],

[ [ [[-1,1],[1,-1]], [[1,-1],[-1,1]]], [`Odd`, `Even`], [`Odd`, `Even`]],

[ [ [ [1,0],[1,2],[0,1]], [ [0,3],[0,1],[2,0]]],[`Up`, `Down`], [`Left`, `Middle`, `Right`]],

[[ [ [0,4],[4,0],[5,3]],[ [4,0],[0,4],[5,3]], [ [3,5],[3,5],[6,6]]], [`T`, `M`, `B`],[`L`,`C`,`R`]],
[
[
[[0,0],[-1,1],[1,-1]],
[[1,-1],[0,0],[-1,1]],
[[-1,1],[1,-1],[0,0]]
],
[`Scissors`, `Rock`, `Paper`],
[`Scissors`, `Rock`, `Paper`]
]

]:
end:



PrintGame:=proc(G) local i:
matrix(
[
[" ", op(G[3])],
seq([G[2][i],op(G[1][i])],i=1..nops(G[2]))
]):

end:



#Rand2PlayerGame(a,b,K): A random 2-player (static) game where the Row player has a strategies (Row 1, .., Row a), the Column player has b strategies (Col. 1, ..., Crol. b)
#and the pay-offs are from 0 to K. For example, to see a random game where Player Row has four strategy choices, and Player Column has five strategy choices
#and the pay-offs are integers from 0 to 20 type:
#matrix(Rand2PlayerGame(4,5,20));
Rand2PlayerGame:=proc(a,b,K)  local ra,i,j:
ra:=rand(0..K):

#[ [seq([seq([ra(),ra()],j=1..b)],i=1..a)],[seq(i,i=1..a)],[seq(j,j=1..b)]]:
[seq([seq([ra(),ra()],j=1..b)],i=1..a)]:
end:

#IsStictDom(v1,v2): Given two lists of numbers is v1[i]<=v2[i] for all i. For example
#IsStrictDom([1,3,2],[2,4,3]); should return true but IsDom([1,3,2],[2,4,1]); should return false
IsStrictDom:=proc(v1,v2) local i:

for i from 1 to nops(v1) do
 if v1[i]>=v2[i] then
  RETURN(false):
 fi:
od:
true:
end:


#FindR(G): Finds a strictly dominated row stategy
FindR:=proc(G) local G1,RowS,i1,i2,j,v1,v2:
G1:=G[1]:
RowS:=G[2]:

for i1 from 1 to nops(RowS) do
for i2 from i1+1 to nops(RowS) do
  v1:=[seq(G1[i1][j][1],j=1..nops(G1[i1]))]:
  v2:=[seq(G1[i2][j][1],j=1..nops(G1[i2]))]:
  if IsStrictDom(v1,v2) then
   RETURN(i1):
  elif IsStrictDom(v2,v1) then
   RETURN(i2):
  fi:
od:
od:
FAIL:
end:


#FindC(G): Finds a strictly dominated row stategy
FindC:=proc(G) local G1,ColS,j1,j2,i,v1,v2:
G1:=G[1]:
ColS:=G[3]:

for j1 from 1 to nops(ColS) do
for j2 from j1+1 to nops(ColS) do
  v1:=[seq(G1[i][j1][2],i=1..nops(G1))]:
  v2:=[seq(G1[i][j2][2],i=1..nops(G1))]:
  if IsStrictDom(v1,v2) then
   RETURN(j1):
  elif IsStrictDom(v2,v1) then
   RETURN(j2):
  fi:
od:
od:
FAIL:
end:


#ShrinkGame(G): Given a game G, tries to shrink it, if it can't it returs it
ShrinkGame:=proc(G) local i,j,G1,RowS,ColS,i1:

G1:=G[1]:
RowS:=G[2];
ColS:=G[3]:

i:=FindR(G):

if i<>FAIL then
 RETURN([
[op(1..i-1,G1),op(i+1..nops(G1),G1)], 
[op(1..i-1,RowS),op(i+1..nops(RowS),RowS)],ColS
]):
fi:

j:=FindC(G):

if j<>FAIL then

 RETURN([
[seq( [op(1.. j-1,G1[i1]),op(j+1..nops(G1[i1]),G1[i1])],i1=1..nops(G1))],RowS, [op(1..j-1,ColS),op(j+1..nops(ColS),ColS)]]):
fi:

FAIL:

end:

#ReducedGame(G): The reduced game of G after all the possible Elimination of dominated  strategy
ReducedGame:=proc(G) local G1,G2:
G1:=G:
G2:=ShrinkGame(G1):

while G2<>FAIL do
G1:=G2:
G2:=ShrinkGame(G1):
od:
G1:
end:




####END PREPARED BEFORE CLASS

#DONE DURING CLASS WITH STUDENTS' HELP

#MyMaxIndex(L): [Suggested by Victoria Chayes]. 
#Inputs a list L of numbers, output the SET of places (indices) where it is maximum. For example
#MyMaxIndex([5,6,7,7,1,7]); should give {3,4,6}
MyMaxIndex:=proc(L) local i,m,S:
m:=max(L):
S:={}:
for i from 1 to nops(L) do
 if L[i]=m then
    S:=S union {i}:
 fi:
od:
S:
end:



#Clarification (Jan. 26, 2022) thanks to Blair Seidler: Note that G is the actual BI-MATRIX, so to experiment with it use, for example
#G:=Rand2PlayerGame(10,20,100)[1] 
#BR1(G,a2): Inputs a bi-matrix of a 2-player game G and a member a2 of A2 outputs the SUBSET of A1 that consists of the best response  
BR1:=proc(G,a2) local a1:
MyMaxIndex([seq(G[a1][a2][1],a1=1..nops(G))]):
end:



#BR2(G,a1): Inputs a bimatrix of a game G and a member a1 of A1 outputs the SUBSET of A2 that consists of the best response  
BR2:=proc(G,a1) local a2:
MyMaxIndex([seq(G[a1][a2][2],a2=1..nops(G[a1]))]):
end:

#BR1v(G): Inputs a bimatrix of a game G, outputs The list of size A2 with all the set of best responses
#
BR1v:=proc(G) local a2: [seq(BR1(G,a2),a2=1..nops(G[1]))]:end:

#BR2v(G): Inputs a bimatrix of a game G, outputs The list of size A1 with all the set of best responses
BR2v:=proc(G) local a1: [seq(BR2(G,a1),a1=1..nops(G))]:end:

#end DURING CLASS WITH STUDENTS' HELP

#Dne after class

#LoadedCoin(p): outputs 1 or 2 with probability p and 1-p respecively. Try:
#[seq(LoadedCon(1/3)),i=1..300)];
LoadedCoin:=proc(p) local m,n,ra:
m:=numer(p):
n:=denom(p):

ra:=rand(1..n)():

if ra<=m then
 1:
else
 2:
fi:

end: