# OK to post homework
# Vikrant, Feb 20 2022, Assignment 9

# ================================================================================
# 0. Code that has been given.
# ================================================================================

read("C9.txt"):

# ================================================================================
# 1. Read and understand C9.txt.
# ================================================================================

# Done.
# Initially thought there was something wrong with SolOpt2(G) -- what about mixed strategies??? -- but a moments thought reveals that social optima can always come from pure strategies.

# ================================================================================
# 2. StatSymGames.
#    n is stated to be the number of players, but I am assuming it's the number 
#    of strategies for a two player game instead (otherwise, the number of strategies
#    is unspecified and it is unclear why RGs(n,K) was written in C9.txt).
# ================================================================================

StatSymGames:=
    proc(n,K1,K2)
        local i,G:
        local Gs:= [seq(RGs(n,K1),i=1..K2)]:
        evalf(
            [
                nops([seq(`if`(nops(NE(G))=nops(MNE2(G)),1,NULL),G in Gs)]),
                nops([seq(`if`(nops(NE(G))=0,1,NULL),G in Gs)]),
                nops([seq(`if`(nops(NE(G))>0 and nops(MNE2(G))>nops(NE(G)),1,NULL),G in Gs)]),
                nops([seq(`if`(BestSocialVal(G,MNE2(G))<>SolOpt2(G),1,NULL),G in Gs)])
            ]/K2 
        ):
    end:

BestSocialVal:=
    proc(G,P)
        local p:
        max(seq(add(PayOffGG(G,p[1],p[2])),p in P)):
    end:

(*

# No time to run.

randomize(651144596):
for i from 1 to 5 do
    print(StatSymGames(3,10^10,1000));
od:

*)

(* 

# No time to run.

randomize(1298223775):
for i from 1 to 5 do
    print(StatSymGames(4,10^10,1000));
od:

*)

(*

# No time to run.

randomize(2130619772):
for i from 1 to 5 do
    print(StatSymGames(5,10^10,1000));
od:

*)

# ================================================================================
# 3. Closed-form expression for SnowDrift social value for mixed Nash Equilibrium.
# ================================================================================

(*

assume(T>R and R>S and S>P):
G:= [[[R,R],[S,T]],[[T,S],[P,P]]]:
Sol:= (MNE22(G) minus {[1,0],[0,1]})[1]:
simplify(add(PayOffG(G,Sol[1],Sol[2])));
T:= 'T': R:= 'R': S:= 'S': P:= 'P':

*)

# ================================================================================
# 4. All Nash Equilibria for symmetric two player games.
# ================================================================================

(*

with(combinat,permute):

Equis:=
    proc(d)
        local i,j,v,Vs,G,Es:
        Vs:= [seq(seq(a[i,j],i=1..d),j=1..d)]:
        G:= [seq([seq([a[i,j],a[j,i]],j=1..d)],i=1..d)]:
        Es:= {}:
        for v in permute(Vs) do
            for i from 1 to nops(v)-1 do
                assume(v[i]>v[i+1]):
            od:
            # C9.txt needs to be modified to make the call to MNE2(G) work.
            # Things which need to be dealt with: list-sols, piecewise-sols, etc.
            Es:= Es union MNE2(G):
            for i from 1 to nops(v) do
                assume(v[i]::'real'):
            od:
        od:
        Es:
    end:

Equis(2);

*)


# ================================================================================
# 5. All Nash Equilibria for symmetric three player games.
# ================================================================================

(*

# No optimization.
# Takes way too long (to even print all 9! permutations let alone equilibria for all of them).

Equis(3);

*)

# ================================================================================
# 6. Read Polya, Tarjan, Wood Chapter 10.
# ================================================================================

# Done.