#OK to post homework
#Blair Seidler, 1/23/22, Assignment 1
with(combinat):

Help1:=proc():
print(` GameDB(), Rand2PlayerGame(a,b,K), IsDom(v1,v2)`):
print(` FindDominatedRowStrategy(G), FindDominatedColumnStrategy(G)`):
print(` ShrinkGame(G), ReducedGame(G)`):
end:


#2. Done

(*
3. Here are the games I generated, along with reductions:

First game:
[[[0, 2], [2, 1], [0, 3]],   Row 2 dominates row 1
 [[1, 1], [2, 3], [3, 1]],
 [[0, 2], [3, 0], [3, 0]]]

[[[1, 1], [2, 3], [3, 1]],   Column 1 dominates column 3
 [[0, 2], [3, 0], [3, 0]]]

[[[1, 1], [2, 3]],   Process terminates
 [[0, 2], [3, 0]]]

-----------------------------------------------------------
Second game:
[[[1, 2], [1, 1], [3, 3]],   Row 1 dominates row 3
 [[2, 2], [0, 1], [0, 3]],
 [[0, 1], [1, 2], [2, 3]]]

[[[1, 2], [1, 1], [3, 3]],   Column 3 dominates columns 1 and 2
 [[2, 2], [0, 1], [0, 3]]]

[[[3, 3]],    Row 1 dominates row 2
 [[0, 3]]]

[[[3,3]]]     Process terminates

-----------------------------------------------------------
Third game:
[[[1, 1], [3, 0], [0, 2]],   Column 3 dominates columns 1 and 2
 [[3, 0], [1, 0], [1, 2]],
 [[3, 2], [2, 1], [0, 2]]]

[[[0, 2]],   Row 2 dominates rows 1 and 3
 [[1, 2]],
 [[0, 2]]]

[[[1,2]]]    Process terminates

-----------------------------------------------------------
As it happens, two of my three games resulted in a 1x1 bimatrix.
*)

#4.

FindDominatedRowStrategy:=proc(G) local rows,cols,i,j,toprow,botrow:
rows:=nops(G):
if rows<2 then return(FAIL): fi:
cols:=nops(G[1]):
if cols<1 then return(FAIL): fi:
for i in choose(rows,2) do
  toprow:=[seq(G[i[1],j,1],j in 1..cols)]:
  botrow:=[seq(G[i[2],j,1],j in 1..cols)]:
  if IsDom(toprow,botrow) then RETURN(i[1]): fi:
  if IsDom(botrow,toprow) then RETURN(i[2]): fi:
od:
return(FAIL):
end:

FindDominatedColumnStrategy:=proc(G) local rows,cols,i,j,leftcol,rightcol:
rows:=nops(G):
if rows<1 then return(FAIL): fi:
cols:=nops(G[1]):
if cols<2 then return(FAIL): fi:
for i in choose(cols,2) do
  leftcol:=[seq(G[j,i[1],2],j in 1..rows)]:
  rightcol:=[seq(G[j,i[2],2],j in 1..rows)]:
  if IsDom(leftcol,rightcol) then RETURN(i[1]): fi:
  if IsDom(rightcol,leftcol) then RETURN(i[2]): fi:
od:
return(FAIL):
end:

#5.
ShrinkGame:=proc(G) local row,col,newG,i,j:
row:=FindDominatedRowStrategy(G):
if type(row,integer) then
  return([seq(G[i],i in 1..row-1),seq(G[i],i in row+1..nops(G))]):
fi:
col:=FindDominatedColumnStrategy(G):
if type(col,integer) then
  return([seq([seq(G[i,j],j in 1..col-1),seq(G[i,j],j in col+1..nops(G[1]))],i in 1..nops(G))]):
fi:
return(FAIL):
end:

ReducedGame:=proc(G) local curG,nextG:
nextG:=G:
while type(nextG,list) do
  curG:=nextG:
  nextG:=ShrinkGame(curG):
od:
curG:
end:


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


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