# Please do not post 
# Daniela Elizondo
# Assignment 25
# April 24, 2022


read "C25.txt":

##### Problem 2 #####

# Note: I'm not sure if this is correct. It seemed to be working until I tried to use it in FindParadox.
# Sometimes calling LaC on the randomly generated graph with an edge deleted failed, and I couldn't figure out why.
# So, I added an extra check to ignore such cases and make BestPrune run, but in doing so I might have made it return something false.

# BestPrune(G,R): inputs a directed graph G followed by the set of Rewards {[i,[a,b]], i is a sink}  
# tries to see whether there exists an edge whose deletion will make the label of vertex 1 (the pay-offs) better for BOTH players. 
# Either outputs the edge (if it exists) in the form {v1, v2} or returns FAIL

BestPrune := proc(G,R) local v1Label, n, i, v, newG, newV1Label,j, newLabel: 
v1Label := LaC(G,R)[1]:
n := nops(G):

for i from 1 to n do:
    for v in G[i] do:
        newG := [seq(G[j], j=1..i-1), G[i] minus {v}, seq(G[j], j=i+1..n)]:
        newLabel := LaC(newG,R):
        if newLabel <> FAIL then
            newV1Label := newLabel[1]:
            if newV1Label[1] > v1Label[1] and newV1Label[2] > v1Label[2] then
            return {i,v}:
            fi:
        fi:
    od:
od:

return(FAIL):
end:

##### Problem 3 #####

# RandCent(n,p,K): generates a random centipede pair G,R, where G is RDG(n,p) and the payoffs for the sinks of G are random integers from 0 to K 

RandCent := proc(n,p,K) local G,R,i,ra:
G := RDG(n,p):
R := {}:
ra := rand(K+1):

for i from 1 to nops(G) do:
    if G[i] = {} then 
        R := R union {[i, [ra(), ra()]]}:
    fi:
od:

(G,R):
end:

##### Problem 4 #####

# FindParadox(n,p,K,K1): generates RandCent(n,p,K) K1 times and stops as soon as it finds something that does not fail under BestPrune. 
# If it finds such a game, it returns the game. If it can't find anything, it returns FAIL.

FindParadox := proc(n,p,K,K1) local i,G:

for i from 1 to K1 do:
    G := RandCent(n,p,K):
    if BestPrune(G) <> FAIL then return G: fi:
    od:

return(FAIL):
end:

# FindParadox(30,1/2,100,1000) returned
#[{2, 3, 5, 9, 12, 15, 16, 17, 18, 21, 22, 24, 26}, {3, 4, 5, 7, 
#  8, 12, 15, 17, 18, 19, 20, 21, 23, 24, 25, 26, 27, 30}, 
#  {8, 10, 11, 12, 13, 14, 15, 18, 22, 25, 26, 27, 28, 30}, {5, 6, 
#  7, 8, 9, 10, 11, 14, 16, 17, 19, 21, 22, 23, 24, 26, 29, 30}, {
#  7, 8, 10, 12, 13, 14, 15, 16, 18, 19, 20, 21, 22, 23, 25, 26, 
#  27, 28, 29, 30}, 
#  {7, 11, 12, 13, 14, 15, 17, 19, 20, 22, 24, 25, 26, 28, 29}, 
#  {8, 9, 12, 13, 15, 16, 17, 18, 19, 20, 28, 30}, 
#  {10, 11, 13, 14, 15, 18, 21, 26, 27}, 
#  {18, 19, 20, 21, 22, 24, 25, 26, 28}, 
#  {11, 17, 19, 20, 22, 25, 27, 28, 30}, 
#  {16, 17, 18, 20, 22, 23, 24, 25, 26, 30}, 
#  {13, 14, 15, 16, 17, 18, 25, 26, 28, 29}, 
#  {14, 16, 17, 19, 21, 23, 24, 26, 27, 28}, {16, 21, 23, 29, 30}, 
#  {16, 19, 20, 22, 23, 24, 26, 29}, {17, 18, 19, 23, 27, 28, 29}, 
#  {21, 22, 24, 25, 26, 28}, {20, 24, 27, 28}, 
#  {20, 21, 22, 23, 24, 26, 27, 28}, {22, 23, 25, 30}, 
#  {23, 25, 26, 28, 30}, {30}, {24, 25, 26, 27, 29, 30}, 
#  {25, 26, 27}, {26, 29, 30}, {28}, {28}, {}, {}, {}], 
#  {[28, [93, 18]], [29, [99, 22]], [30, [48, 71]]}



##### Problem 5 #####
# Prove that a position (i.e. vertex), i, is a losing position (i.e. LaGn(G)[i]=0) if and only if SG(G)[i]=0. 

# Suppose that SG[i]=0. Then either i is a sink, in which case i is losing, or mex({SG(G)[j], j is reachable from i})=0. 
# Therefore SG(G)[j] <> 0 for all positions j that are reachable from i. So, by definition of mex, there exists position k that is two away from i with SG(G)[k] = 0.
# Either k is a sink in which case k is losing (hence j is winning and i is losing) or there exists a position l that is two away from k with SG(G)[l] = 0.
# We continue finding positions that are two away until we find a sink (which must exist since G is finite and SG(G)[i]=0. Since i is always an even number of positions
# away from the sink, i must be a losing position.

# Now suppose that vertex i is a losing position. Then either i is a sink, in which case SG(G)[i]=0, or every
# position in G[i] is a winning one. We already know from the above that winning positions j satisfy SG(G)[j] <> 0 so mex({SG(G)[j], j is reachable from i})=0
# and therefore SG(G)[i] = 0.