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

with(ArrayTools):
Help:=proc(): print(`GenRand2PGame(i,j,pmin,pmax), FindDominatedRowStategy(G), FindStrictdDominatedRowStategy(G), FindStrictDominatedColumnStategy(G), ShrinkGame(G), ReducedGame(G)`) end:

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

#########

#2 For each of the games, GameDB()[4] and GameDB()[5], printout matrix(GameDB()[4]); matrix(GameDB()[5]); and for each of these two games, spell-out (like we did in class), for each choice (i,j), write the pay-off functions u_1(i,j) and u_2(i,j)

# print(matrix(GameDB()[4]));
# u_1(1,1)=1 ; u_1(1,2)=1 ; u_1(1,3)=0 ; u_1(2,1)=0 ; u_1(2,2)=0 ; u_1(2,3)=2
# u_2(1,1)=0 ; u_2(1,2)=2 ; u_2(1,3)=1 ; u_2(2,1)=3 ; u_2(2,2)=1 ; u_2(2,3)=0

# print(matrix(GameDB()[5])); 
# u_1(1,1)=0 ; u_1(1,2)=4 ; u_1(1,3)=5 ; u_1(2,1)=4 ; u_1(2,2)=0 ; u_1(2,3)=5 ; u_1(3,1)=3 ; u_1(3,2)=3 ; u_1(3,3)=6 
# u_2(1,1)=4 ; u_2(1,2)=0 ; u_2(1,3)=3 ; u_2(2,1)=0 ; u_2(2,2)=4 ; u_2(2,3)=3 ; u_2(3,1)=5 ; u_2(3,2)=5 ; u_2(3,3)=6 

#########

#4 After reading section 1.1.B. of Gibbons, generate three random 2-player games with both players with 3 strategy-choices, and pay-offs between 0 and 3, and eliminate, BY HAND, as many strategies as you can, until you are left with a possibly smaller game (i.e. bimatrix). Is it ever a 1 by 1 bimatrix?

#We begin by creating a procedure to randomly generate such games:

#PROCEDURE: GenRand2PGame: generates a random 2-player game 
#INPUTS: i: number of strategies for player 1
#        j: number of strategies for player 2
#        pmin: minimum payoff 
#        pmax: maximum payoff 
#OUTPUTS: a random game matrix corresponding to i strategies for player 1 and j strategies for player 2, with randomly assigned payoffs between pmin and pmax associated with each strategy. 

GenRand2PGame:=proc(i,j,pmin,pmax) local ra:
ra:=rand(pmin..pmax):
matrix([seq([seq([ra(),ra()],k=1..i)],l=1..j)]):
end:

#GAME 1:
# [[2, 2], [0, 3], [2, 2]] 
# [[3, 1], [2, 0], [0, 2]] 
# [[0, 0], [1, 1], [1, 2]]
# There are no dominated strategies for player 1, either strict or non-strict. There are also no dominated strategies for player 2, either strict or non-strict. 

#GAME 2:
# [[1, 3], [3, 2], [1, 0]] 
# [[0, 0], [2, 3], [3, 0]] 
# [[2, 1], [2, 3], [0, 1]]
# There are no dominated strategies for player 1, either strict or non-strict. However, Column 3 is always a worse choice for player 2; therefore, with a rational player 2, the game reduces to: 
# [[1, 3], [3, 2]] 
# [[0, 0], [2, 3]] 
# [[2, 1], [2, 3]]
# Now for player 1, Row 2 is always a worse choice, so the game reduces to:
# [[1, 3], [3, 2]] 
# [[2, 1], [2, 3]]
# The game cannot reduce further. 

#GAME 3:
# [[3, 0], [2, 3], [3, 0]]
# [[2, 3], [0, 0], [1, 1]]
# [[2, 3], [2, 0], [3, 0]]
# We start out noticing for player 1, Row 2 is always a worse pick: 
# [[3, 0], [2, 3], [3, 0]]
# [[2, 3], [2, 0], [3, 0]]
# Now, for player 2, Column 3 is a worse pick:
# [[3, 0], [2, 3]]
# [[2, 3], [2, 0]]
# Now, for player 1, Row 2 is the worse pick:
# [[3, 0], [2, 3]]
# And player 2 can now pick Column 2, reducing our game to:
# [[2, 3]]


#########

#5 Using procedure IsDom(v1,v2) (that I added after class), Write a Maple procedure FindDominatedRowStategy(G), FindDominatedColumnStategy(G), that inputs a 2-player game, G, and outputs either a row or column (respectively) that can be (weakly) eliminated, or returns FAIL.

FindDominatedRowStategy:=proc(G) local s, G1,i,j:
s:=Size(G):
G1:=Matrix([seq([seq(G[i,j][1],j=1..s[2])],i=1..s[1])]): 
for i from 1 to s[1] do
 for j from 1 to s[1] do
  if i<>j then
  if IsDom(convert(G1[i,..],list),convert(G1[j,..],list)) then
    return(i):
  fi:
   fi:
  od:
od:
false:
end:

FindDominatedColumnStategy:=proc(G) local s, G1,i,j:
s:=Size(G):
G1:=Matrix([seq([seq(G[i,j][2],j=1..s[2])],i=1..s[1])]): 
for i from 1 to s[2] do
 for j from 1 to s[2] do
  if i<>j then
  if IsDom(convert(G1[..,i],list),convert(G1[..,j],list)) then
    return(i):
  fi:
   fi:
  od:
od:
false:
end:


#########


#6 Using procedure IsStictDom(v1,v2) (that I added Jan. 23), Write a Maple procedure FindStrictdDominatedRowStategy(G), FindStrictDominatedColumnStategy(G) that inputs a 2-player game, G, and outputs either a row or column (respectively) that can be (strongly) eliminated, or returns FAIL.


FindStrictdDominatedRowStategy:=proc(G) local s, G1,i,j:
s:=Size(G):
G1:=Matrix([seq([seq(G[i,j][1],j=1..s[2])],i=1..s[1])]): 
print(`G1 ok`):
for i from 1 to s[1] do
 for j from 1 to s[1] do
  if i<>j then
print([i,j]):
  if IsStrictDom(convert(G1[i,..],list),convert(G1[j,..],list)) then
    return(i):
  fi:
   fi:
  od:
od:
false:
end:

FindStrictDominatedColumnStategy:=proc(G) local s, G1,i,j:
s:=Size(G):
G1:=Matrix([seq([seq(G[i,j][2],j=1..s[2])],i=1..s[1])]): 
for i from 1 to s[2] do
 for j from 1 to s[2] do
  if i<>j then
  if IsStrictDom(convert(G1[..,i],list),convert(G1[..,j],list)) then
    return(i):
  fi:
   fi:
  od:
od:
false:
end:



#########

#7  Using the above, write a procedure ShrinkGame(G) that tries to shrink a game, if possible, or returns FAIL, then iterate it and write ReducedGame(G) that keeps shrinking the game until it not shrinkable any more.

ShrinkGame:=proc(G) local a,b,Gnew:
if not type(G, Matrix) then
Gnew:=convert(G,Matrix):
  a:=FindDominatedRowStategy(Gnew):
     if type(a,integer) then
       return(DeleteRow(Gnew,a)):
     fi:
  b:=FindDominatedColumnStategy(Gnew):
     if type(b, integer) then
       return(DeleteColumn(Gneq,b)):
     fi:
fi:
a:=FindDominatedRowStategy(G):
  if type(a,integer) then
    return(DeleteRow(G,a)):
  fi:
b:=FindDominatedColumnStategy(G):
  if type(b, integer) then
    return(DeleteColumn(G,b)):
  fi:
false:
end:

ReducedGame:=proc(G) local Gnew, Gnewnew:
if not type(G, Matrix) then
  Gnew:=convert(G,Matrix):
else 
  Gnew:=G:
fi:
while true do
Gnewnew:=ShrinkGame(Gnew):
if not type(Gnewnew, Matrix) then
 return(Gnew):
else
Gnew:=Gnewnew:
fi:
od:
end:

#########


#############################################
#  Programs From C1.txt  



Help1:=proc(): print(` GameDB(), Rand2PlayerGame(a,b,K), IsDom(v1,v2), IsStictDom(v1,v2)`):end:

#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
#matrix(GameDB()[1])
GameDB:=proc():
[
[ [[-1,-1],[-9,0]], [[0,-9],[-6,-6]]],
[ [[2,1],[0,0]], [[0,0],[1,2]]],
[ [[-1,1],[1,-1]], [[1,-1],[-1,1]]],
[ [ [1,0],[1,2],[0,1]], [ [0,3],[0,1],[2,0]]],
[ [ [0,4],[4,0],[5,3]],[ [4,0],[0,4],[5,3]], [ [3,5],[3,5],[6,6]]]
]:
end:


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

end:

#IsDom(v1,v2): Given two lists of numbers is v1[i]<=v2[i] for all i. For example
#IsDom([1,3,2],[2,4,3]); should return true but IsDom([1,3,2],[2,4,1]); should return false
IsDom:=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:


##Added Jan. 23, 2022, thanks to comments by Lucy Martinez, Rebecca Embar, and George Spahn
#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: