# 1. Write a program 
# AllBetterDeals(G,i) 
# That inputs a generalized game G (given in our format) and a vertex i ( an integer between 1 and nops(G)) that is 
# not a sink, and finds ALL the smaller subgames H (obtained by deleting some of the edges, i.e. replacing some (or 
# all) of the entries of G that are sets by proper subsets and such that the payoffs for BOTH players are higher if 
# Player 1 starts at vertex i. You also want the improved payoffs. So the output should be the a set of pairs {[H,
# [a,b]} 
# What is 
# AllBetterDeals(ElsterG(),1)? 
# [Note: Of course this is exponential time in the number of edges so don't try it on too large graphs.]

with(combinat,powerset);

# We begin with a routine to generate the permissible subgraphs. We don't want to make any new sinks, and 
# we need to carry over the payoffs from the ones we already have.  exponential time :(
AllPossibleSubgraphs = proc(G) local n,s,S,T,p,P: option remember:
	if G = {} then
		# The empty graph has one subgraph - itself.
		RETURN({G});
	fi;
	
	n := nops(G);
	
	S := AllPossibleSubgraphs([op(1..n-1,G)]);
	T := {}; # Our new subgraphs
	
	for s in S do
		# If n is a sink there's little to do but copy over the payoff.
		if type(G[n],list) then
			P := {G[n]};
		else 
			P := powerset(G[n]) minus {{}}; # we subtract {} to avoid making sinks
		fi;
		
		for p in P do
				T := T union {[op(s),p]};
		od;
	od;
	
	RETURN(T);
end:

AllBetterDeals = proc(G,i) local n,H,S,curr,rec,champs:
	n := nops(G);
	
	# We have to beat P1(G,i) by trimming the graph in some way.  rec will stay fixed throughout the procedure -  
	# we want ALL the subgraphs that have higher payoffs, not just the best one.  
	rec := P1(G,i);
	
	 # champ keeps track of all the subgraphs that beat rec.  
	champs := {};
	
	S := AllPossibleSubgraphs(G);
	
	for H in S do
		curr := P1(H,i);
		if {seq(evalb(curr[k] > rec[k]),k=0..1)} = {true} then
			champs := champs union [H,curr];
		fi;
	od;
	
	RETURN(champs);
end:

# 2. Experiment with ten random graphs with n=6, k=2, Si=3, and L=10 (using RGG(n,k,Si,L) ).
# 
# Tests to be performed
#

# 3. Write a program 
# OneBetterDeals(G,i,K) 
# That inputs as above, and tries to find, by repeated random deletion of edges, K times, ONE subgame that is a 
# better deal for BOTH players if player 1 starts at vertex i. If no better deal is found, return FAIL.

OneBetterDeals := proc(G,i,K) local n,ra1,ra2,,roll1,roll2,H,rec,k,payout,j:
	n := nops(G);
	
	# we randomly choose one vertex...
	ra1 := rand(1..n);
	
	# We use H to keep track of the graph as we trim it.
	H := G;
	
	# The payoff to beat.
	rec := P1(G,i);
	
	for k from 1 to K do
		roll1 := ra1();
		if type(H[roll1],list) or nops(H[roll1])=1 then
			print("Roll failed.  Rolling again…");
			next;
		else
			#…and we then randomly choose one of the edges coming out of said vertex.
			roll2 := rand(H[roll1])();
			
			# we delete the edge from H, compute the new payout, and test against the record
			H := [op(1..(roll1-1),H),H[roll1] minus {roll2}, op(roll1+1..n,H)];
			payout := P1(H,i);
			if {seq(evalb(payout[j] > rec[j]),j=0..1)} = {true} then
				RETURN(H);
			fi;
end;

# 4. Experiment with ten random graphs with n=20, k=3, Si=4 and L=10 (using RGG(n,k,Si,L)) .
#
# Tests to be performed.