# OK to post homework
# RDB, 2022-01-23, HW1

read "C1.txt":

# 1. I identify as someone who knows Maple.

# 2.

print(Matrix(GameDB()[4])):

# u_1(1, 1) = 1     u_2(1, 1) = 0
# u_1(1, 2) = 1     u_2(1, 2) = 2
# u_1(1, 3) = 0     u_2(1, 3) = 1

# u_1(2, 1) = 0     u_2(2, 1) = 3
# u_1(2, 2) = 0     u_2(2, 2) = 1
# u_1(2, 3) = 2     u_2(2, 3) = 0

print():

print(Matrix(GameDB()[5])):

# u_1(1, 1) = 0     u_2(1, 1) = 4
# u_1(1, 2) = 4     u_2(1, 2) = 0
# u_1(1, 3) = 5     u_2(1, 3) = 3

# u_1(2, 1) = 4     u_2(2, 1) = 0
# u_1(2, 2) = 0     u_2(2, 2) = 4
# u_1(2, 3) = 5     u_2(2, 3) = 3

# u_1(3, 1) = 3     u_2(3, 1) = 5
# u_1(3, 2) = 3     u_2(3, 2) = 5
# u_1(3, 3) = 6     u_2(3, 3) = 6

# 3. Done!

# Objection: We should define "rational" as "refuses to play a strictly
# dominated strategy," or something similar. As it stands, it's a vague filler
# for "whatever assumptions seem plausible to me," which may or may not be
# useful in a "real" competitive game.

# 4.

randomGame := proc(n, m)
    local ra:
    ra := rand(0..3):
    [seq([seq([ra(), ra()], j=1..m)], i=1..n)]:
end:

# First game I generated:

# [[1, 0]    [3, 0]    [1, 1]]
# [                          ]
# [[2, 2]    [3, 1]    [1, 3]]
# [                          ]
# [[0, 0]    [2, 3]    [0, 1]]

# Strategy 2 for Player 1 strictly dominates Strategy 3, so we can remove the
# last row.

# [[1, 0]    [3, 0]    [1, 1]]
# [                          ]
# [[2, 2]    [3, 1]    [1, 3]]

# Player 1 has no more strictly dominating strategies.
# Player 2, on the other hand, has Strategy 3, which dominates both of its
# other options, so we can remove the first two columns.

# [[1, 1]]
# [      ]
# [[1, 3]]

# Now we're stuck, because Player 1 doesn't care at this point.

# Second game I generated:

# [[0, 1]    [2, 3]    [2, 2]]
# [                          ]
# [[1, 0]    [2, 2]    [2, 0]]
# [                          ]
# [[3, 2]    [2, 3]    [1, 2]]

# Player 1 does not have any strict dominance relations.
# For Player 2, Strategy 2 dominates Strategies 1 and 3, so we zoom in on the
# second column.

# [[2, 3]]
# [      ]
# [[2, 2]]
# [      ]
# [[2, 3]]

# We're stuck again, because Player 1 doesn't care anymore.

# 5 / 6. I identify as an expert.

# (Also I'm cheating by only doing 6.)

FindStrictDominatedRowStrategy := proc(G, selector:=1)
    local M, rows, cols, i, v1, j, v2:
    M := Matrix(G):
    rows, cols := op(1, M):
    for i from 1 to rows do
        v1 := convert(map(L -> L[selector], M[i]), list):
        for j from i + 1 to rows do
            v2 := convert(map(L -> L[selector], M[j]), list):
            if IsStrictDom(v1, v2) then
                return i:
            elif IsStrictDom(v2, v1) then
                return j:
            fi:
        od:
    od:

    FAIL:
end:

with(LinearAlgebra):

FindStrictDominatedColumnStrategy := proc(G)
    FindStrictDominatedRowStrategy(Transpose(Matrix(G)), 2):
end:

# Call this a few times to make sure everything is working.
testDom := proc(n, m)
    local x:
    x := Matrix(randomGame(n, m)):
    print(x):
    print(FindStrictDominatedRowStrategy(x)):
    print(FindStrictDominatedColumnStrategy(x)):
end:

# 7. I identify as an expert.

RowShrink := proc(G)
    local M, row:
    M := Matrix(G):
    row := FindStrictDominatedRowStrategy(M):

    if row <> FAIL then
        return DeleteRow(M, row):
    fi:

    FAIL:
end:

ColShrink := proc(G)
    local M, col:
    M := Matrix(G):
    col := FindStrictDominatedColumnStrategy(M):

    if col <> FAIL then
        return DeleteColumn(M, col):
    fi:

    FAIL:
end:

ShrinkGame := proc(G)
    local M, res:

    M := Matrix(G):
    res := RowShrink(M):
    if res <> FAIL then
        return res:
    fi:

    res := ColShrink(M):
    if res <> FAIL then
        return res:
    fi:

    FAIL:
end:

ReducedGame := proc(G)
    local M, res:

    M := Matrix(G):
    res := ShrinkGame(M):
    while res <> FAIL do
        M := res:
        res := ShrinkGame(M):
    od:

    M:
end: