#########################################################################
## EM20ProjNash.txt Save this file as   EM20ProjNash.txt to use it,	#
## set the file directory to the directory containing this file		#
## in Maple type " read   `EM20ProjNash.txt`: <Enter>"			#
## and then type:  read   EM19ProjNash.txt: <Enter>			#
## Then follow the instructions given there				#
## 									#
## Written by students of Dr. Z.'s Math 640 , Spring 2020, class	#
##  Coordinated by Alan Chernoff, arc177@economics.rutges.edu		#
#########################################################################

with(ArrayTools):
with(combinat):
with(GraphTheory):

print(`This is EM20ProjNash.txt, a final project for Dr. Z.'s Math 640, Spring 2020, class, Math 640, written by`):
print(`Alan Chernoff (coordinator), Khizar Anjun, Jingyang Deng, & Zidong Zhang `):

print(`code analzying relation between the number of PNE in simultaneous & sequential move games`):

Help:=proc()
if args=NULL then

print(` EM20ProjNash.txt: A Maple package for Analyzing the relation between the number of PNE`):
print(`Primary procedures are: CentipedeAll, Centipede, DrawCent, CentCount`):
print(`Secondary procedures are: RandGameCentB, RandGameCentU, PGFCent`):
print(`Tertiary procedures include: RandGameG, PNEg, PGFSimul, CentContract `):
print(`To find out more information about a procedure, enter it in the argument of Help()`):
print(`   `):


elif nargs=1 and args[1]=Centipede then
print(`Centipede(L): inputs L list of lists containing an earning for each player at each stage`):
print(`Output is the payoffs under "rational play", solved by backwards induction`):
print(`Try: Centipede(RandGameCentB(2,3,0,10));`):

elif nargs=1 and args[1]=CentipedeAll then
print(`CentipedeAll(L): inputs L list of lists containing an earning for each player at each stage`):
print(` Output is the payoffs under "rational play", solved by backwards induction`):
print(`Try: CentipedeAll(RandGameCentB(2,3,0,10));`):

elif nargs=1 and args[1]=CentCount then
print(`CentCount(L): inputs L list of lists containing an earning for each player at each stage`):
print(`returns the number of NE in a centipede game under "rational play", solved by backwards induction`):
print(`Try: CentCount(RandGameCentB(2,3,0,10));`):

elif nargs=1 and args[1]=RandGameCentU then
print(`RandGameCentU(n, round): inputs n players, round # of rounds`):
print(`Generate a round-rounds sequential move game where at each round, player may take current`):
print(`payoff and conclude the game, or pass to following player, with unique payoffs at every round`):
print(`Try: RandGameCentU(2,3);`):

elif nargs=1 and args[1]=RandGameCentB then
print(`RandGameCentB(n, round, K1, K2): inputs n players, round # of rounds, K1 and K2 min and max payoffs`):
print(`Generate a round-rounds sequential move game where at each round, player may take current`):
print(`payoff and conclude the game, or pass to following player, with payoffs ranging from K1 to K2`):
print(`Try: RandGameCentB(2,3,0,10);`):


elif nargs=1 and args[1]=CentContract then
print(`CentContract(L): inputs L list of lists containing an earning for each player at each stage`):
print(`where nops(L[n]) is the number of players and L is a list of lists, representing earnings of each player at each outcome`):
print(`Try: CentContract(RandGameCentB(2,3,0,10));`):


elif nargs=1 and args[1]=DrawCent then
print(`DrawCent(L): inputs L list of lists containing an earning for each player at each stage`):
print(`Try: DrawCent(RandGameCentB(2,3,0,10));`):


elif nargs=1 and args[1]=RandGameG then
print(`RandGameG(L,K1,K2): inputs list L of number of options for nops(L) players`):
print(`with payoffs in a range of K1 to K2, outputs game presented as a table`):
print(`Try: RandGameG([2,2,2],0,10);`):


elif nargs=1 and args[1]=PNEg then
print(`PNEg(G): inputs game G with RandGameG structure`):
print(`returns the set of pure Nash Equilibria for the game G`):
print(`Try: PNEg(RandGameG([2,2,2],0,10));`):


elif nargs=1 and args[1]=PGFSimul then
print(`PGFSimul(L,K1,K2,M): inputs list L of number of options for nops(L) players,`):
print(`payoff boundaries K1, K2, and number of iterations M`):
print(`returns PGF for the number of Nash Equilibria`):
print(`Try: PGFSimul([3,3],1,5,1000);`):


elif nargs=1 and args[1]=PGFCent then
print(`PGFCent(n, round, K1, K2,M): inputs n players, round # of rounds,`):
print(`payoff boundaries K1, K2, and number of iterations M`):
print(`returns PGF for the number of Nash Equilibria`):
print(`Try: PGFCent(3,3,1,5,1000);`):



print(``):

print(``):



else
 print(`There is no procedure named`, args):

fi:


end:
















# MAIN PROCEDURE: output one PNE
# Centipede(L): L is a list of lists, representing earnings of each players in different outcomes.
# Output is the payoffs under "rational play", solved by backwards induction.
# Suppose every players are rational, so that they will consider their own interests at first,
# and they will be altruistic only if their interests can be protected.
Centipede := proc(L) local n, round, expwin, player, pointer:
n:=nops(L[1]):
round := nops(L) - 1:
pointer := nops(L) - 1:
expwin := L[-1]:
player := (round - 1) mod n + 1:
while pointer > 0 do
if L[pointer][player] > expwin[player] or (L[pointer][player] = expwin[player] and add(L[pointer]) > add(expwin)) then
    expwin := L[pointer]:
elif L[pointer][player] = expwin[player] and add(L[pointer]) = add(expwin) and rand(0.. 1) = 1 then
    expwin := L[pointer]:
fi:
pointer := pointer - 1:
player := NextPlayer(player, n):
od:
expwin:
end:




# MAIN PROCEDURE: output all PNEs
# CentipedeAll(L): L is a list of lists, representing earnings of each players in different outcomes.
# Output is the payoffs under "rational play", solved by backwards induction.
# Suppose every players are rational, so that they will only consider their own interests.
CentipedeAll := proc() local n, L, expwin, player, tmp1, tmp2, exp: option remember:

if nargs=1 then :
 L:=args[1]:
 expwin:={}: 
fi:
if nargs=2 then 
 L:=args[1]:
 expwin:=args[2]: 
fi:
n:=nops(L[1]):
if expwin = {} then
    tmp1 := expwin union {L[-1]}:
    tmp2 := tmp1:
    player := (nops(L) - 2) mod n + 1:
    for exp in tmp1 do
        #print(exp):
        if L[-2][player] > exp[player] then
            tmp2 := (tmp2 minus {exp}) union {L[-2]}:
        elif L[-2][player] = exp[player] then
            tmp2 := tmp2 union {L[-2]}:
        fi:
    od:
    CentipedeAll([op(1 .. nops(L) - 2, L)], tmp2):
else
    tmp1 := expwin:
    tmp2 := tmp1:
    player := (nops(L) - 1) mod n + 1:
    for exp in tmp1 do
        if L[-1][player] > exp[player] then
            tmp2 := (tmp2 minus {exp}) union {L[-1]}:
        elif L[-1][player] = exp[player] then
            tmp2 := tmp2 union {L[-1]}:
        fi:
    od:
    if nops(L) = 1 then RETURN(tmp2): fi:
    CentipedeAll([op(1 .. nops(L) - 1, L)], tmp2):
fi:
end:


#CentCount(L): returns the number of NE in a centipede game with structure L
CentCount:=proc(L): local i:
nops(CentipedeAll(L)):
end:

#PGFCent(n, round, K1, K2, M)
PGFCent:=proc(n, round, K1, K2, M) local i:
add(t^CentCount(RandGameCentB(n, round, K1, K2)),i=1...M)/M:
end: