Digits:=50:
interface(displayprecision=10):
with(GroupTheory):
with(ListTools):
with(combinat):
with(CurveFitting):

####################################################################################################
#
#CommonPayoffNash.txt: Save this file as CommonPayoffNash.txt
#In order to use it, point Maple to the directory this file is in and type: read "CommonPayoffNash.txt":
#You may then follow the instrustions on screen.
#
#Written by Richard Voepel, Rutgers University
#rzv2@math.rutgers.edu
#
####################################################################################################

print(`This is CommonPayoffNash.txt`):
print(`It is a small Maple package that accompanies the following article:`):
print(`A COMBINATORIAL AND EXPERIMENTAL ANALYSIS OF NASH EQUILIBRIA FOR FINITE COMMON PAYOFF GAMES`):
print(`by Richard Voepel`):
print(``):
print(`Please report any bugs to Richard Voepel at: rzv2@math.rutgers.edu`):
print(`The most current version of this package and the associated paper can be found at:`):
print(`http://sites.math.rutgers.edu/~rzv2/Nash`):
print(``):
print(`For a list of procedures, type the following: Help();`):

####################################################################################################

Help:=proc()

if nargs=0 then
print(`Contains primary procedures: TablePureNash, CommonPayoffGame, CommonDataGen`):
print(`For information about a primary procedure P, type Help(P).`):
print(`For auxiliary procedures, type HelpAux().`):

elif nargs=1 and args[1]=TablePureNash then
print(`TablePureNash(T): Given a table form game, such as the output of CommonPayoffGame,`):
print(`computes the pure Nash equilibria of that game and outputs the set containing the strategy`):
print(`profiles corresponding to those equilibria.`):
print(``):
print(`For example, try typing the following: G1:=CommonPayoffGame([3,3]): TablePureNash(G1);`):

elif nargs=1 and args[1]=CommonPayoffGame then
print(`CommonPayoffGame(L): Given a list of naturals L=[m_1,...,m_k], constructs a game`):
print(`in table form with k players indexed by the set [k], with player i having a strategy`):
print(`space of size m_i, indexed by the set [m_i]. The output table T has entries`):
print(`T[i,[n_1,...,n_k]] that are strict ordinal rankings of the utilities that player i earns`):
print(`when the strategy profile of the players is [n_1,...,n_k]. This game is generated`):
print(`by selecting a strict ordinal utility function uniformly at random for player 1, and setting`):
print(`all other players' utility functions to be equal to player 1's utility function.`):
print(``):
print(`For example, try typing the following: G1:=CommonPayoffGame([3,4]): G1[1,[2,3]]; G1[2,[2,3]]; G1[1,[1,1]];`):

elif nargs=1 and args[1]=CommonDataGen then
print(`CommonDataGen(L,N): Computes a running tally of the pure Nash equilibria in N many`):
print(`games generated by the procedure CommonPayoffGame(L). Outputs a table T with entries`):
print(`T[x] that are either the number of times the set x of equilibria was counted,`):
print(`or the number of times any set of equilibria of cardinality x were counted.`):
print(`Due to the data structure used, any time the command "T[x];" returns a placeholder`):
print(`value "T[x]", that is an indication that the set x or the cardinality x was never`):
print(`seen in the N games, i.e. treat the value as 0.`):
print(``):
print(`For example, try typing the following: N1:=CommonDataGen([3,3],1000): N1[0]; N1[1]; N1[{[1,1]}];`):

else
print(`There is no help for`, args):
fi:

end:

####################################################################################################

HelpAux:=proc()

if nargs=0 then
print(`Contains auxiliary procedures: FindTuple, FindIndex, TableDimensions`):
print(`For information about an auxiliary procedure P, type HelpAux(P).`):

elif nargs=1 and args[1]=FindTuple then
print(`FindTuple(n,L): Returns the nth element under lex ordering of the poset of tuples of natural`):
print(`numbers determined by L=[m_1,...,m_k]. This is the inverse operation to FindIndex.`):
print(``):
print(`For example, try typing the following: tup:=FindTuple(17,[3,4,5]); FindIndex(tup,[3,4,5]);`):

elif nargs=1 and args[1]=FindIndex then
print(`FindIndex(L1,L): Returns the index under lex ordering of the element L1 in the poset of tuples of`):
print(`natural numbers determined by L=[m_1,...,m_k]. This is the inverse operation to FindTuple.`):
print(``):
print(`For example, try typing the following: n1:=FindIndex([2,2,2],[3,4,5]); FindTuple(n1,[3,4,5]);`):

elif nargs=1 and args[1]=TableDimensions then
print(`TableDimensions(T): Given a table form game, such as the output of CommonPayoffGame,`):
print(`computes the dimensions of the strategy spaces for the players of that game.`):
print(``):
print(`For example, try typing the following: G1:=CommonPayoffGame([3,2,4]): TableDimensions(G1);`):

else
print(`There is no help for`, args):
fi:

end:

####################################################################################################

#FindTuple(n,L): Returns the nth element under lex ordering of the poset on tuples of natural
#numbers determined by L=[m_1,...,m_k]. This is the inverse operation to FindIndex.

FindTuple:=proc(n,L) local l,m,k,i,j,tuple:
m:=n:
k:=nops(L):
if n>mul(L[i],i=1..k) then
RETURN("Error: n is too large."):
fi:
if n<1 then
RETURN("Error: n is too small."):
fi:
tuple:=[1$k]:
for j from 1 to k-1 do
l:=mul(L[i],i=1..k-j):
if m>l then
tuple[k-j+1]:=tuple[k-j+1]+iquo(m-1,l):
m:=m-iquo(m-1,l)*l:
fi:
od:
tuple[1]:=m:
RETURN(tuple):
end:

###################################################################################################

#FindIndex(L1,L): Returns the index under lex ordering of the element L1 of the poset on tuples of
#natural numbers determined by L=[m_1,...,m_k]. This is the inverse operation to FindTuple.

FindIndex:=proc(L1,L) local k,index,i,j:
if nops(L1)<>nops(L) then
RETURN("Dimension mismatch.")
fi:
k:=nops(L):
for i from 1 to k do
if L1[i]>L[i] or L1[i]<1 then
RETURN("L1 must be bounded by 1 and L"):
fi:
od:
index:=0:
for j from 0 to k-2 do
index:=index+(L1[k-j]-1)*mul(L[i],i=1..k-j-1):
od:
index:=index+L1[1]:
RETURN(index):
end:

###################################################################################################

#TableDimensions(T): Given a table form game, computes the dimensions of the strategy spaces for
#the players of that game.

TableDimensions:=proc(T) local k,L,i:
k:=1:
while whattype(T[1,[1$k]])=indexed do
k:=k+1:
od:
L:=[1$k]:
for i from 1 to k do
while not evalb(whattype(T[1,L])=indexed) do
L[i]:=L[i]+1:
od:
L[i]:=L[i]-1:
od:
RETURN(L):
end:

###################################################################################################

#TablePureNash(T): Given a table form game, computes the pure Nash equilibria of that game and 
#outputs the set containing the strategy profiles corresponding to those equilibria.
#
#For example, try: TablePureNash(RandomGame([3,3,3]));

TablePureNash:=proc(T) local m,S,i,j,boool,test,k,j1,total,L:
L:=TableDimensions(T):
m:=nops(L):
S:={}:
total:=mul(i,i in L):
for j from 1 to total do
boool:=true:
for i from 1 to m do
test:=T[i,FindTuple(j,L)]:
for k from 1 to L[i] do
j1:=FindTuple(j,L):
j1[i]:=k:
if test<T[i,j1] then
boool:=false:
fi:
od:
od:
if boool then
S:=S union {FindTuple(j,L)}:
fi:
od:
RETURN(S):
end:

###################################################################################################

#CommonPayoffGame(L): Given a list of naturals L, constructs a game in table form with m:=nops(L) 
#players, indexed by the set [m], with player i having a strategy space of size L[i], indexed by
#the set [L[i]]. The output table T has entries T[i,[n[1],n[2],...,n[m]]] that are ordinal rankings
#of the utilities that player i earns when the strategy profile of the players is [n[1],...,n[m]],
#where the ordinal rankings are generated uniformly at random for player 1, and all other players
#have the same ordinal rankings.
#
#For example, try: T:=CommonPayoffGame([3,3,3]);

CommonPayoffGame:=proc(L) local m,i,j,S,T,sigma:
m:=nops(L):
S:=mul(i, i in L):
T:=table():
sigma:=randperm(S):
for i from 1 to m do
for j from 1 to S do
T[i,FindTuple(j,L)]:=sigma[j]:
od:
od:
RETURN(T):
end:

###################################################################################################

#CommonDataGen(L,N): Computes a running tally of the pure Nash equilibria in N many games generated
#by the procedure CommonPayoffGame(L). Outputs a table T with entries T[x] that are the number of times
#the set x of equilibria were counted or the number of times any set of equilibria of cardinality x
#were counted.
#
#For example, try: T:=CommonDataGen([3,3],1000);T[0];T[1];T[{[1,1]}];

CommonDataGen:=proc(L,N) local i,T,G:
T:=table():
for i from 1 to N do
G:=TablePureNash(CommonPayoffGame(L)):
if whattype(T[G])=indexed then
T[G]:=1
else
T[G]:=T[G]+1:
fi:
if whattype(T[nops(G)])=indexed then
T[nops(G)]:=1
else
T[nops(G)]:=T[nops(G)]+1:
fi:
od:
RETURN(T):
end:

###################################################################################################