#OK to post homework 
#Natalya Ter-Saakov, April 24, Assignment 25
read "C25.txt":

#Problem 1
#BestPrune(G,R): nputs a directed graph G followed by the set of Rewards {[i,[a,b]], i is a sink} and tries to see whether there exists an edge whose deletion will make the label of vertex 1 (the pay-offs) better for BOTH players.

BestPrune:= proc(G,R) local n, i, j, curBest, Gtry, bestEdge, updated, current:
n:=nops(G):
curBest:=LaC(G,R)[1]:
updated:=false:
for i from 1 to n do
	for j in G[i] do
		Gtry:=G:
		Gtry[i]:=Gtry[i] minus {j}:
		current:=LaC(Gtry,R):
		if current<>FAIL then
		current:=current[1]:
		if (current[1]>curBest[1] and current[2]>curBest[2]) then 
			curBest:=current:
			bestEdge:=[i,j]:
			updated:=true:
		fi:
		fi:
	od:
od:
if updated then return(bestEdge): fi:
FAIL:
end:

BestPrune(Els()):
#[4,5]
BestPrune(WikiCent(20)):
#[40,81]

#Problem 2

#RandCent(n,p,K): generates a random centipded 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,k,i:
G:=RDG(n,p): 
R:={}: 
k:=rand(K+1):
for i from 1 to n do
	if G[i]={} then
		R:=R union {[i,[k(),k()]]}:
	fi:
od:
G,R:
end:

#Problem 3

#FindParadox(n,p,K,K1): tries K1 times to generate RandCent(n,p,K) and stops as soon as it finds something that is not FAIL. If it can't find anything, it should return FAIL.

FindParadox:=proc(n,p,K,K1) local i, game, pruned:
for i from 1 to K1 do
	game:=RandCent(n,p,K):
	pruned:=BestPrune(game):
	if pruned<>FAIL then return(game, pruned) fi:
od:
FAIL:
end:

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

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

#Proof: Consider what SG does. It starts by assigning 0 to all the elements in the youngest generation. From there, it looks at the higher generations. If an element in a higher generation has a neighbor that is a losing position, then T[i] will not be 0 (ie it is a winning position. Otherwise, T[i]=0 and i is a losing position. Note that since we go up one generation at a time, all neighbors of i will have already been assigned something, so there is no ambiguity.