#OK to post
#Kayla Gibson, 01/25/2022, Assignment 2 

#1 Sample of Garvan Exercises

gcd(28743, 552805); 			# = 11
a:={1,2,3,5,9}: b:={seq(i^2,i=1..4)}:
a union b; 				# = {1,2,3,4,5,9,16}
a intersect b;				# = {1,9}
f:=(x,y)->x^2+y^2;
diff(f(x,y),x); diff(f(x,y),y);		# = 2x ; = 2y
minimize(f(x,y),x,y);			# = 0
minimize(f(x,y),x);			# = y^2

#2 Finding the Best-Response lists of the Row and Column Player.
g1:=Rand2PlayerGame(3,3,5):
g2:=Rand2PlayerGame(5,5,20):
g3:=Rand2PlayerGame(3,3,100):
g4:=Rand2PlayerGame(5,4,17):
g5:=Rand2PlayerGame(3,5,5):

BR1v(g1); BR2v(g1);
BR1v(g2); BR2v(g2);
BR1v(g3); BR2v(g3);
BR1v(g4); BR2v(g4);
BR1v(g5); BR2v(g5);

# g1	[4,1] 	[4,5]	[1,2]
#	[3,3]	[5,4]	[2,0]
#	[4,1]	[2,1]	[1,3]
# BR1v(g1) = [{1,3},{2},{2}]; BR2v(g1) = [{2},{2},{3}]
#
# g2	[10,18]	[13,17]	[14,7]	[9,13]	[11,8]
#	[12,15]	[0,5]	[12,13]	[6,6]	[2,13]
#	[14,14]	[18,20]	[11,18]	[7,2]	[16,16]
#	[2,4]	[4,9]	[9,1]	[7,19]	[14,1]
#	[8,20]	[8,6]	[3,11]	[12,18]	[9,14]
# BR1v(g2) = [{3},{3},{1},{5},{3}]; BR2v(g2)=[{1},{1},{2},{4},{1}]
# 
# g3	[63,8]	[11,51]	[24,71]
#	[89,17]	[42,54]	[39,16]
#	[69,51]	[80,86]	[33,84]
# BR1v(g3) = [{2}, {3}, {2}]; BR2v(g3) = [{3}, {2}, {2}]
#
# g4 	[8,8]	[3,3]	[5,3]	[3,9]
#	[7,1]	[15,1]	[10,14]	[10,2]
#	[4,13]	[6,10]	[10,4]	[15,10]
#	[3,7]	[1,10]	[10,5]	[7,15]
#	[10,8]	[2,17]	[16,0]	[4,1]
# BR1v(g4) = [{5}, {2}, {5}, {3}]; BR2v(g4) = [{4}, {3}, {1}, {4}, {2}]
#
# g5 	[3,4]	[3,5]	[0,5]	[2,0]	[2,1]
#	[3,0]	[4,1]	[2,1]	[3,5]	[5,5]
#	[0,5]	[0,1]	[0,4]	[2,1]	[4,4]
# BR1v(g5) = [{1, 2}, {2}, {2}, {2}, {2}]; BR2v(g5) = [{2, 3}, {4, 5}, {1}]

#3 Read 1.1.C. of Robert Gibbons' book (done)

#4 Using procedures BR1v(G) and BR2v(G), write a one-line Maple procedure

# IsNash(G,a1,a2) takes as input 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.
# it outputs true or false according to whether [a1,a2] is a Nash Equilibrium.
IsNash := proc(G, a1, a2) member(a1, BR1v(G)[a2]) and member(a2, BR2v(G)[a1]); end:

#5 Write a procedure PureNashEqui(G)

# PureNashEqui(G) takes as input a bi-matrix G, and outputs the (possibly) emtpy set of pairs [a1,a2] that are (pure) Nash Equilibria.

with(LinearAlgebra);
PureNashEqui := proc(G) local m, n, i, j, M, NE; 
NE := []; 
M := Matrix(G); 
m := RowDimension(M); n := ColumnDimension(M); 
	for i to m do 
		for j to n do 
			if IsNash(G, i, j) then 
				NE := [op(NE), [i, j]]; 
			fi:
 		od: 
	od: 
RETURN(NE); 
end:

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

G1 := Rand2PlayerGame(10, 12, 5): PrintGame(G1);
G2 := Rand2PlayerGame(10, 12, 20): PrintGame(G2);
G3 := Rand2PlayerGame(10, 12, 100): PrintGame(G3);
G4 := Rand2PlayerGame(10, 12, 17): PrintGame(G4);
G5 := Rand2PlayerGame(10, 12, 5): PrintGame(G5);

PureNashEqui(G1);
PureNashEqui(G2);
PureNashEqui(G3);
PureNashEqui(G4);
PureNashEqui(G5);

# G1	[2,0]	[4,3]	[5,5]	[3,4]	[2,2]	[0,4]	[2,0]	[1,0]	[3,4]	[0,0]	[5,0]	[2,0]
#	[0,2]	[2,0]	[3,5]	[5,4]	[3,0]	[1,4]	[4,0]	[1,0]	[4,3]	[3,4]	[3,1]	[0,3]
#	[0,5]	[5,4]	[0,0]	[4,5]	[0,3]	[4,3]	[4,0]	[4,1]	[4,4]	[4,1]	[2,5]	[5,0]
#	[3,3]	[5,1]	[1,1]	[3,0]	[4,1]	[4,5]	[1,4]	[4,0]	[4,1]	[1,1]	[4,4]	[0,4]
#	[2,0]	[4,1]	[1,3]	[3,2]	[4,3]	[3,4]	[2,3]	[2,3]	[0,2]	[1,5]	[3,1]	[1,2]
#	[3,1]	[5,3]	[5,1]	[3,3]	[4,4]	[4,3]	[0,4]	[5,5]	[3,5]	[5,4]	[2,0]	[0,5]
#	[5,4]	[2,0]	[0,1]	[2,3]	[2,2]	[3,5]	[0,0]	[4,5]	[3,0]	[3,1]	[1,5]	[2,1]
#	[5,3]	[1,0]	[5,0]	[4,1]	[0,5]	[3,1]	[0,5]	[3,1]	[4,1]	[2,4]	[4,2]	[3,0]
#	[4,4]	[5,3]	[4,0]	[5,1]	[0,0]	[5,2]	[4,1]	[3,5]	[2,4]	[0,3]	[4,0]	[2,1]
#	[5,4]	[5,1]	[4,2]	[0,0]	[3,1]	[1,1]	[0,5]	[5,5]	[1,0]	[3,0]	[3,5]	[0,5]
# PureNashEqui(G1) = [[1, 3], [6, 8], [10, 8]]
#
# For the remaining games, I will just write the results (not the associate matrix)
#
# PureNashEqui(G2) =  []
#
# PureNashEqui(G2) = [[1, 9]]
#
# PureNashEqui(G4) = [[8, 12], [9, 3]]
#
# PureNashEqui(G5) = [[2, 4], [6, 8], [7, 7]]


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

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