#OK to post
#Rebecca Embar, 1-25-2022, Homework 2

#Homework problems

#2
game1:=Rand2PlayerGame(3,3,3):
#Matrix is,
#[[3,0] [2,3] [3,0]]
#[				   ]
#[[2,3] [0,0] [1,1]]
#[                 ]
#[[2,3] [2,0] [3,0]]
BR1v(game1[1]);
#Outputs [{1},{1,3},{1,3}]
BR2v(game1[1]);
#Outputs [{2},{1},{1}]

game2:=Rand2PlayerGame(3,3,3):
#Matrix is,
#[[1,3] [0,2] [1,0]]
#[                 ]
#[[0,0] [0,3] [2,0]]
#[                 ]
#[[2,3] [1,3] [3,1]]
BR1v(game2[1]);
#Outputs [{3},{3},{3}]
BR2v(game2[1]);
#Outputs [{1},{2},{1,2}]

game3:=Rand2PlayerGame(2,2,5):
#Matrix is,
#[[1,1] [2,4]]
#[           ]
#[[4,3] [2,2]]
BR1v(game3[1]);
#Outputs [{2},{1,2}]
BR2v(game3[1]);
#Outputs [{2},{1}]

game4:=Rand2PlayerGame(2,2,5):
#Matrix is,
#[[4,5] [2,2]]
#[           ]
#[[4,2] [3,2]]
BR1v(game4[1]);
#Outputs [{1,2},{2}]
BR2v(game4[1]);
#Outputs [{1},{1,2}]

game5:=Rand2PlayerGame(2,2,5):
#Matrix is,
#[[5,1] [4,1]]
#[           ]
#[[2,2] [5,5]]
BR1v(game5[1]);
#Outputs [{1},{2}]
BR2v(game5[1]);
#Outputs [{1,2},{2}]

#4
IsNash:=proc(G,a1,a2):
	return(member(a1,BR1v(G)[a2]) and member(a2,BR2v(G)[a1])):
end:

#5
PureNashEqui:=proc(G) local pairs,i,j:
	pairs := {}:
	for i from 1 to nops(G) do
		for j from 1 to nops(G[1]) do
			if IsNash(G,i,j) then
				pairs := pairs union {[i,j]}:
			fi:
		od:
	od:
	return(pairs):
end:

#From class
#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)]]:

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:



#BR1(G,a2): Inputs a 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 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): 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:=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: