#OK to post homework
#George Spahn, 1-23-2022, Assignment 1

#2

#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

#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

roll:=rand(0..3):
gen_rand_game := proc(r,c)
local i,j,l,m:
	m:=[]:
	for i from 1 to r do
		l:=[]:
		for j from 1 to c do
			l:=[[roll(),roll()],op(l)]:
		od:
		m:=[l,op(m)]:
	od:
end:

# output 1
# [[[3, 0], [3, 0], [0, 2]], [[3, 1], [2, 3], [1, 1]], [[0, 3], [2, 1], [0, 2]]]
# No strictly dominated strategies.

# output 2 
# [[[2, 3], [1, 2], [0, 1]], [[0, 3], [0, 1], [2, 2]], [[3, 3], [1, 1], [1, 2]]] 
# For player 2, strategies 2 and 3 are strictly dominated by strategy 1.
# [[[2, 3]], [[0, 3]], [[3, 3]]]
# Given that player 2 only plays 1, player 1 should play 3.
# [[[3,3]]]
# We are left with a 1x1 matrix

# output 3
# [[[0, 2], [2, 1], [3, 2]], [[1, 2], [1, 0], [3, 0]], [[0, 2], [3, 0], [1, 1]]]
# player 2 strategy 2 can be eliminated.
# [[[0, 2], [3, 2]], [[1, 2], [3, 0]], [[0, 2], [1, 1]]]
# player 1 strategy 3 can be eliminated.
# [[[0, 2], [3, 2]], [[1, 2], [3, 0]]]
# No more strictly dominated strategies.

#5 

FindDominatedRowStategy := proc(G)
local row1,row2,s1,s2:
	for row1 from 1 to nops(G) do
		for row2 from row1+1 to nops(G) do
			s1 := [seq(v[1], v in G[row1])]:
			s2 := [seq(v[1], v in G[row2])]:
			if IsDom(s1,s2) then
				RETURN( row1):
			elif IsDom(s2,s1) then
				RETURN( row2):
			fi:
			
		od:
	od:
	RETURN(FAIL):
end:

FindDominatedColumnStategy := proc(G)
local col1,col2,s1,s2:
	for col1 from 1 to nops(G[1]) do
		for col2 from col1+1 to nops(G[1]) do
			s1 := [seq(r[col1][2], r in G)]:
			s2 := [seq(r[col2][2], r in G)]:
			if IsDom(s1,s2) then
				RETURN( col1):
			elif IsDom(s2,s1) then
				RETURN( col2):
			fi:
			
		od:
	od:
	RETURN(FAIL):
end:


#6

FindStrictDominatedRowStategy := proc(G)
local row1,row2,s1,s2:
	for row1 from 1 to nops(G) do
		for row2 from row1+1 to nops(G) do
			s1 := [seq(v[1], v in G[row1])]:
			s2 := [seq(v[1], v in G[row2])]:
			if IsStrictDom(s1,s2) then
				RETURN( row1):
			elif IsStrictDom(s2,s1) then
				RETURN( row2):
			fi:
			
		od:
	od:
	RETURN(FAIL):
end:

FindStrictDominatedColumnStategy := proc(G)
local col1,col2,s1,s2:
	for col1 from 1 to nops(G[1]) do
		for col2 from col1+1 to nops(G[1]) do
			s1 := [seq(r[col1][2], r in G)]:
			s2 := [seq(r[col2][2], r in G)]:
			if IsStrictDom(s1,s2) then
				RETURN( col1):
			elif IsStrictDom(s2,s1) then
				RETURN( col2):
			fi:
			
		od:
	od:
	RETURN(FAIL):
end:

#7

ShrinkGame := proc(G)
local r,c:
	r := FindStrictDominatedRowStategy(G):
	if r <> FAIL then 
		RETURN(subsop(r=NULL,G)):
	fi:
	c := FindStrictDominatedColumnStategy(G):
	if c <> FAIL then 
		RETURN([seq(subsop(c=NULL,ro),ro in G)]):
	fi:
	RETURN(FAIL):
end:

ReducedGame := proc(G)
local rg1,rg2:
	rg1 := G:
	rg2 := ShrinkGame(G):
	while rg2 <> FAIL do
		rg1 := rg2:
		rg2 := ShrinkGame(rg2):
	od:
	RETURN(rg1):
end: