#########################################################################
## 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:


#DrawCent(L): draws centipede game with structure L
DrawCent:=proc(L) local i, E,H,G,T,labelist,n:
E:={}:
n:=nops(L[1]):

for i from 0 to nops(L)+1 do
 i:=i+1:
 E:={op(E),{i,i+1},{i,i+2}}:
od:
G:=Graph(E):

labelist:=[]:
for i from 1 to nops(L)-1 do
 labelist:=[op(labelist),cat("P",(i-1 mod n)+1, " Turn ", floor((i-1)/n)+1),convert(L[i],string)]:
od:
labelist:=[op(labelist),convert(L[nops(L)],string)]:
H:=RelabelVertices(G,labelist):
T:=SpanningTree(H):
DrawGraph(T):

end:



# RandGameCentU(n, round): Generate a round-rounds Centipede game on n players, where each payoffs are different from each other.
#Try:
#RandGameCentU(2,3);
RandGameCentU := proc(n, round) local A:
A := Array(randperm(n * (round + 1))):
A := Reshape(A, round + 1, n):
A := convert(A, list, nested):
end:




# RandGameCentB(n, round, K1, K2): Generate a round-rounds Centipede game on n players, each payoffs are randomly selected from K1 to K2.
#Try:
#RandGameCentB(2,3,0,10);
RandGameCentB := proc(n, round, K1, K2) local A, i:
if K1 > K2 then RETURN("lower bound must be less than upperbound"): fi:
A := Array([seq(rand(K1 .. K2)(), i = 1 .. n * (round + 1))]):
A := Reshape(A, round + 1, n):
A := convert(A, list, nested):
end:



# NextPlayer(m, n): m is current player, n is the number of total players.
# n->n-1, n-1->n-2, ..., 3->2, 2->1, 1->n.
NextPlayer := proc(m, n):
if m >= 1 and m <= n then
    RETURN((m - 2) mod n + 1):
else
    RETURN(FAIL):
fi:
end:



# CentContract(L), where L is a list of lists representing earnings of each player in different outcomes. 
# outputs if not selecting the rational outcome at the end is beneficial for all the players, 
# returns if the players should sign a contract for the N-th player to not terminate.
CentContract := proc(L) local n, rational_out, comp_outs, contract_out, round, pointer, expwin, winpointer, player, w, k, M:
    n:=nops(L[1]):
    rational_out := Centipede(L):
    
    # finding out what is the rational last choice, and then making it impossible.
    # since, its backward induction, it should be the first step 
    round := nops(L) - 1:
    pointer := nops(L) - 1:
    expwin := L[-1]:
    winpointer := -1:
    player := (round - 1) mod n + 1:

    if L[pointer][player] > expwin[player] or (L[pointer][player] = expwin[player] and add(L[pointer]) > add(expwin)) then
        expwin := L[pointer]:
        winpointer := -2:
    elif L[pointer][player] = expwin[player] and add(L[pointer]) = add(expwin) and rand(0.. 1) = 1 then
        expwin := L[pointer]:
        winpointer := -2:
    fi:
    
    M := L:
    M[winpointer] := [seq(-infinity, i = 1..n)]: # whatever the rational choice for the last step is, make it impossible. 
    # now calculate the outcome
    contract_out := Centipede(M):
    
    # compare if the contract PNE is strictly good for all players. 
    comp_outs := `>`~(contract_out, rational_out):
    comp_outs:
    w := true:
    for k in comp_outs do
        w := w and k:
        if w = false then
            break:
        end if:
    end do:
    
    if w = true then 
        [w, contract_out]:
    else
        [w, rational_out]:
    fi:
end:

















##Code Developed in Class

#PGFSimul(L,K1,K2,M)
PGFSimul:=proc(L,K1,K2,M) local i:
add(t^nops( PNEg( RandGameG(L,K1,K2))),i=1...M)/M:
end:


#RandGameG(L,K1,K2): A random nops(L)-player game with payoffs between K1 and K2, presented as a table
#Try:
#RandGame([2,2,2],0,10);
RandGameG:=proc(L,K1,K2) local S,ra,T,s,i:
 S:=AllStrats(L):
 ra:=rand(K1..K2):

for s in S do
 T[s]:=[seq(ra(),i=1..nops(s))]:
od:

[L,S,op(T)]:

end:





#AllStrats(L): inputs a list of positive integers L, describes all the possible strategies in a nops(L)-player game
#where player i has the L[i] possible strategies {1,..., L[i]}. For example Try:
#AllStrats([2,3,2]);
AllStrats:=proc(L) local S,L1,s,i:
if L=[] then
 RETURN({[]}):
fi:

L1:=[op(1..nops(L)-1,L)]:

S:=AllStrats(L1):

{seq(seq([op(s),i],s in S), i=1..L[nops(L)])}:

end:




#RandGameG(L,K1,K2): A random nops(L)-player game with payoffs between K1 and K2, presented as a table
#Try:
#RandGameG([2,2,2],0,10);
RandGameG:=proc(L,K1,K2) local S,ra,T,s,i:
if K1 > K2 then RETURN("lower bound must be less than upperbound"): fi:
 S:=AllStrats(L):
 ra:=rand(K1..K2):

for s in S do
 T[s]:=[seq(ra(),i=1..nops(s))]:
od:

[L,S,op(T)]:

end:


#IsNE(s,G): Is s a Nash Equilibrim of the game [S,T] where T[s] is the payoff-vector for the strategy choice s.
#Try:
#G:=RandGame([2,2,2],0,10); IsNE([1,1,1],[2,2,2],G):
IsNE:=proc(s,G) local L,S, T,Alts,s1,i,j:
L:=G[1]:
S:=G[2]:
T:=G[3]:

if not member(s, S) then
 print(s, `is not a valid strategy-choice`):
 RETURN(FAIL):
fi:


for i from 1 to nops(s)  do
 Alts:={seq([op(..i-1,s),j,op(i+1..nops(s),s)],j=1..L[i])}:
  if max(seq(T[s1][i],s1 in Alts))<>T[s][i] then
   RETURN(false):
  fi:
od:

true:

end:

   



#PNEg(G): The set of pure Nash Equilibria for the game G
PNEg:=proc(G) local S,s,N:
S:=G[2]:

N:={}:

for s in S do
 if IsNE(s,G) then
   N:=N union {s}:
 fi:
od:

N:

end:






Procedure CentCount( L ) on lines 199 to 201
  These local variables were never used:  i
Procedure PGFCent( n, round, K1, K2, M ) on lines 204 to 206
  These names were used as global names but were not declared:  t
Procedure RandGameCentU( n, round ) on lines 236 to 240
  These names were used as global names but were not declared:  nested
Procedure RandGameCentB( n, round, K1, K2 ) on lines 248 to 253
  These names were used as global names but were not declared:  nested
Procedure CentContract( L ) on lines 272 to 313
  These names were used as global names but were not declared:  i
Procedure PGFSimul( L, K1, K2, M ) on lines 334 to 336
  These names were used as global names but were not declared:  t