#OK to post homework

#Kayla Gibson, 1/20/2022, Assignment 1

################################################################
# Class 1 Maple Code:

#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:
#Rand2PlaerGame(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:


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

#Problem 1 (Sample of Frank Garven examples):

p := x^3 + 16*x^2 + 28*x:
factor(p);
expand(x(x+14)(x+2));
f:=sqrt(x+2)*sqrt(x+3):
#expand will not work here
expand(f);
#but combine will
combine(f);
readlib(rationalize):
3/(sqrt(5)+3);
rationalize(%);

#Problem 2:

matrix(GameDB()[4]);
#Player 1: Row; Player 2: Column
#u[1]([1,0]) = 1; u[2]([1,0]) = 0
#u[1]([1, 2]) = 1; u[2]([1, 2]) = 2
#u[1]([0,1]) = 0; u[2]([0,1]) = 1
#u[1]([0,3]) = 0; u[2]([0,3]) = 3
#u[1]([0,1]) = 0; u[2]([0,1]) = 1
#u[1]([2,0]) = 2; u[2]([2,0]) = 0

matrix(GameDB()[5]);
#Player 1: Row; Player 2: Column
#u[1]([0,4]) = 0; u[2]([0,4]) = 4
#u[1]([4,0]) = 4; u[2]([4,0]) = 0
#u[1]([5,3]) = 5; u[2]([5,3]) = 3
#u[1]([4,0]) = 4; u[2]([4,0]) = 0
#u[1]([0,4]) = 0; u[2]([0,4]) = 4
#u[1]([5,3]) = 5; u[2]([5,3]) = 3
#u[1]([3,5]) = 3; u[2]([3,5]) = 5
#u[1]([3,5]) = 3; u[2]([3,5]) = 5
#u[1]([6,6]) = 6; u[2]([6,6]) = 6

#Problem 3: Read pp.1-7

#Problem 4: Generating random 2-player games

#For each game, Player 1 will be the Rows and have strategies T, M, B for the Top, Middle, and Bottom Rows, 
#and Player 2 will be the Columns and have strategies L, C, R for the Left, Center, and Right Columns (as seen in the text).

g1 := Rand2PlayerGame(3, 3, 3);

#Eliminating Strategies for game g1:
g1 := [[[1, 2], [2, 2], [0, 1]], [[2, 3], [1, 1], [0, 1]], [[0, 1], [2, 2], [1, 3]]]:
M1 := matrix(g1);
#Since there are no strictly dominated strategies, the process produces no prediction about the play of this game.
#It is noted that there are some weakly dominated strategies in this matrix

g2 := Rand2PlayerGame(3, 3, 3);

#Eliminating Strategies for game g2:
g2 := [[[2, 3], [3, 0], [3, 1]], [[0, 3], [0, 1], [1, 0]], [[2, 2], [0, 0], [0, 1]]]:
M2 := matrix(g2);
print("Player 1 (Row) has that strategy M is strictly dominated  by strategy T, so we may eliminate row  2.");
g2 := [[[2, 3], [3, 0], [3, 1]], [[2, 2], [0, 0], [0, 1]]]:
matrix(g2);
print("Player 2 (Col) has that strategy M is dominated by strategy R and strategy L, so we eliminate column 2");
g2 := [[[2, 3], [3, 1]], [[2, 2], [0, 1]]]:
matrix(g2);
print("Now,  for player 2, the 2nd column is strictly dominated by the first, so we may eliminate column 2.");
g2 := [[[2, 3]], [[2, 2]]]:
matrix(g2);
print("Finally, the bottom row is strictly dominated by the top row for player 1, so we may eliminate row 2,  This leaves us with the 1x1 bimatrix:");
g2 := [[[2, 3]]]:
matrix(g2);

g3 := Rand2PlayerGame(3, 3, 3);

#Eliminating Strategies for game g3:
g3 := [[[1, 3], [0, 3], [3, 1]], [[2, 0], [2, 1], [2, 0]], [[2, 2], [1, 3], [0, 0]]]:
M3 := matrix(g3);
print("Column 3 may be eliminated because it is dominated by column 2.");
g3 := [[[1, 3], [0, 3]], [[2, 0], [2, 1]], [[2, 2], [1, 3]]]:
matrix(g3);
print("Now Row 2 may be eliminated because it is strictly dominated by both row 1 and row 3.");
g3 := [[[1, 3], [0, 3]], [[2, 2], [1, 3]]]:
matrix(g3);
print("Now we may eliminate row 1, as it is dominated by row 2");
g3 := [[[2, 2], [1, 3]]]:
matrix(g3);
print("Finally. we may eliminate column 1, since it is dominated by column 2");
g3 := [[[1, 3]]]:
matrix(g3);

#`Yes, it is possible to eliminate down to a 1x1 bimatrix as shown in examples 2 & 3 above.`

#Problem 5: Write procedures using IsDom

#FindDominatedRowStrategy(G) Takes as input a game G, written as a matrix.
#It should output the index of the row which should be eliminated 
#If no column can be eliminated, it should output false.

FindDominatedRowStrategy:=proc(G) local M,numrow,numcol,L,V,i,j:
M := Matrix(G):
numrow := RowDimension(M):
numcol := ColumnDimension(M):
L:=[];
V:=[];

#This loop should extract player 1's (player row) payoff from a strategy (row) in the game (matrix)
# it turns the payoffs for a given strategy into a list, and adds that list to V   
for i from 1 to numrow do
    for j from 1 to numcol do 
	L := [op(L), M[i, j][1]]; 
    od:
    V := [op(V), L];
    L := [];
od:

#This loop should compare each row (or strategy) from the game, 
#if a strategy is dominated, it is returned, if we go through each comparison,
#with no dominated strategies, this loop ends, and we return false. 
for i from 1 to numrow-1 do
     for j from i+1 to numrow do 
                if IsDom(V[i],V[j]) then
		   RETURN(i):
	        fi:
		if IsDom(V[j],V[i]) then
		   RETURN(j):
		fi:
     od:
od:
false:
end:

#FindDominatedColumnStrategy(G) Takes as input a game G, written as a matrix.
#It should output the index of the column which should be eliminated
#If no column can be eliminated, it should output false.

FindDominatedColumnStrategy:=proc(G) local M,numrow,numcol,L,V,i,j:
M := Matrix(G):
numrow := RowDimension(M):
numcol := ColumnDimension(M):
L:=[];
V:=[];

#This loop should extract player 2's (player column) payoff from a strategy (column) in the game (matrix)
# it turns the payoffs for a given strategy into a list, and adds that list to V   
for i from 1 to numcol do
    for j from 1 to numrow do 
	L := [op(L), M[j, i][2]]; 
    od:
    V := [op(V), L];
    L := [];
od:

#This loop should compare each column (or strategy) from the game, 
#if a strategy is dominated, it is returned, if we go through each comparison,
#with no dominated strategies, this loop ends, and we return false. 
for i from 1 to numcol-1 do
     for j from i+1 to numcol do 
                if IsDom(V[i],V[j]) then
		   RETURN(i):
	        fi:
		if IsDom(V[j],V[i]) then
		   RETURN(j):
		fi:
     od:
od:
false:
end:

#Problem 6: Write procedures using IsStrictDom

#FindDominatedRowStrategy(G) Takes as input a game G, written as a matrix.
#It should output the index of the row which should be eliminated 
#If no column can be eliminated, it should output false.

FindStrictDominatedRowStrategy:=proc(G) local M,numrow,numcol,L,V,i,j:
M := Matrix(G):
numrow := RowDimension(M):
numcol := ColumnDimension(M):
L:=[];
V:=[];

#This loop should extract player 1's (player row) payoff from a strategy (row) in the game (matrix)
# it turns the payoffs for a given strategy into a list, and adds that list to V   
for i from 1 to numrow do
    for j from 1 to numcol do 
	L := [op(L), M[i, j][1]]; 
    od:
    V := [op(V), L];
    L := [];
od:

#This loop should compare each row (or strategy) from the game, 
#if a strategy is strictly dominated, it is returned, if we go through each comparison,
#with no strictly dominated strategies, this loop ends, and we return false. 
for i from 1 to numrow-1 do
     for j from i+1 to numrow do 
                if IsStrictDom(V[i],V[j]) then
		   RETURN(i):
	        fi:
		if IsStrictDom(V[j],V[i]) then
		   RETURN(j):
		fi:
     od:
od:
false:
end:


FindStrictDominatedColumnStrategy:=proc(G) local M,numrow,numcol,L,V,i,j:
M := Matrix(G):
numrow := RowDimension(M):
numcol := ColumnDimension(M):
L:=[];
V:=[];

#This loop should extract player 2's (player column) payoff from a strategy (column) in the game (matrix)
# it turns the payoffs for a given strategy into a list, and adds that list to V   
for i from 1 to numcol do
    for j from 1 to numrow do 
	L := [op(L), M[j, i][2]]; 
    od:
    V := [op(V), L];
    L := [];
od:

#This loop should compare each column (or strategy) from the game, 
#if a strategy is strictly dominated, it is returned, if we go through each comparison,
#with no stricylu dominated strategies, this loop ends, and we return false. 
for i from 1 to numcol-1 do
     for j from i+1 to numcol do 
                if IsStrictDom(V[i],V[j]) then
		   RETURN(i):
	        fi:
		if IsStrictDom(V[j],V[i]) then
		   RETURN(j):
		fi:
     od:
od:
false:
end:



#Problem 7: Write a shrinking and a reducing procedure

#ShrinkGame(G) takes as input a game written as a matrix, and if possible, shrinks it,
#by eliminating either a row or a column. If not it returns false.

ShrinkGame:=proc(G) local numrow,numcol,del,L,i global M:   
M:=Matrix(G):  
numrow:=RowDimension(M);  
numcol:=ColumnDimension(M);
if type(FindDominatedRowStrategy(G), integer) then
    del := FindDominatedRowStrategy(G):
    RETURN(subsop(del = NULL, G));
fi:

#This piece of the code is not working, I keep coming up with an error.
if  type(FindDominatedColumnStrategy(G),integer) then  
del:=FindDominatedColumnStrategy(G): 
if del>1 then
for i from 1 to numrow do
G[i] := G[i][1 .. del - 1, del + 1 .. -1]
od:   
RETURN(G);  
fi:
for i to numrow do
    G[i] := G[i][del + 1 .. -1];
od:
RETURN(G);
i:
false:
end:

#ReducedGame(G) takes as input a game written as a matrix, and shrinks it, until it there are no
#more columns or rows to eliminate. 

ReducedGame:=proc(G)global M :
M := G
while ShrinkGame(M) <>false do  
ShrinkGame(M):
od:
RETURN(Matrix(M)):
end: