#OK to post homework 
#Natalya Ter-Saakov, Jan 30, Assignment 4 
read "C5.txt":
 
#Problem 1: 
# The payoff to player 1 is (a-p1+b*p2)*(p1-c) and the payoff to player 2 is (a-p2+b*p1)*(p2-c). 
# The best response of player 1 to p2 is found by taking the derivative of the payoff of player 1, setting it equal to 0 and solving for p1:
PP1:= (a-p1+b*p2)*(p1-c):

diff(PP1, p1);
# PP1' = b*p2+a+c-2p1

#Thus the best response of player 1 is (b*p2+a+c)/2 and the best response of player 2 is (b*p1+a+c)/2. 
#The Nash Equilibrium is found at the intersection of the two linear equations: 
solve({p1=(b*p2+a+c)/2,p2=(b*p1+a+c)/2},{p1,p2});
#(p1=(a+c)/(2-b), p2=(a+c)/(2-b)}

with(plots):
implicitplot([p1=(0.5*p2+10+5)/2, p2=(0.5*p1+10+5)/2],p1=0..20,p2=0..20,scaling=constrained);

G1:=RG(30,30,10000):NE(G1);BestTot(G1);
#The first game has Nash equilibium at {[6, 2]} and max total welfare at {[6, 2]}, equal to 19947.

G2:=RG(30,30,10000):NE(G2);BestTot(G2);
#The second game has no (pure) Nash equilibium and max total welfare at {[7, 14]}, equal to 19752.

G3:=RG(30,30,10000):NE(G3);BestTot(G3);
#The first game has Nash equilibium at {[8, 6]} and max total welfare at {[29, 1]}, equal to 19474.

BetterForBoth(G3,8,6);
#The following strategy pairs are better than the Nash equilibrium for both players: {[11, 7], [29, 1]}

#From HW3 #AllGames(a,b): inputs positive integers a and b and outputs the set of (a*b)!^2 Games where each player's payoffs are distinct that drawn from {1, ..., a*b} 
AllGames:= proc(a,b) local per, pi1,pi2,i1,j1, games:
 per:= permute(a*b):
 games:= {seq(seq([seq([seq([pi1[b*i1+j1],pi2[b*i1+j1]],j1=1..b)],i1=0..a-1)],pi2 in per), pi1 in per)}: 
 games: 
end:

#BeatNE(a,b):inputs positive integers a and b and outputs the set of all games (given as bi-matrices) for which there is a unique Nash Equilibrium, AND there exist a strategy choice that is better for BOTH players. 
BeatNE:= proc(a,b) local games, game, beatNE, nash, a1, a2:  
 beatNE:={}: 
 games := AllGames(a,b):
 for game in games do 
  nash := NE(game): 
  if nops(nash) = 1 then 
   if nops(BetterForBoth(game,nash[1][1],nash[1][2]))>0 then 
    beatNE := beatNE union {game}: 
   fi:
  fi:
 od:
 beatNE:
end:

BeatNE(2,2);
# {[[[1, 1], [3, 2]], [[4, 3], [2, 4]]], [[[1, 1], [3, 4]], [[2, 3], [4, 2]]], 

#  [[[1, 2], [3, 4]], [[2, 3], [4, 1]]], [[[1, 3], [3, 4]], [[2, 2], [4, 1]]], 

#  [[[1, 4], [3, 3]], [[2, 2], [4, 1]]], [[[1, 4], [4, 3]], [[2, 2], [3, 1]]], 

#  [[[1, 4], [4, 3]], [[3, 2], [2, 1]]], [[[2, 1], [3, 2]], [[4, 3], [1, 4]]], 

#  [[[2, 2], [3, 1]], [[1, 4], [4, 3]]], [[[2, 2], [4, 1]], [[1, 3], [3, 4]]], 

#  [[[2, 2], [4, 1]], [[1, 4], [3, 3]]], [[[2, 3], [4, 1]], [[1, 2], [3, 4]]], 

#  [[[2, 3], [4, 2]], [[1, 1], [3, 4]]], [[[2, 4], [4, 3]], [[3, 2], [1, 1]]], 

#  [[[3, 1], [2, 2]], [[4, 3], [1, 4]]], [[[3, 2], [1, 1]], [[2, 4], [4, 3]]], 

#  [[[3, 2], [2, 1]], [[1, 4], [4, 3]]], [[[3, 3], [1, 4]], [[4, 1], [2, 2]]], 

#  [[[3, 4], [1, 1]], [[4, 2], [2, 3]]], [[[3, 4], [1, 2]], [[4, 1], [2, 3]]], 

#  [[[3, 4], [1, 3]], [[4, 1], [2, 2]]], [[[4, 1], [2, 2]], [[3, 3], [1, 4]]], 

#  [[[4, 1], [2, 2]], [[3, 4], [1, 3]]], [[[4, 1], [2, 3]], [[3, 4], [1, 2]]], 

#  [[[4, 2], [2, 3]], [[3, 4], [1, 1]]], [[[4, 3], [1, 4]], [[2, 1], [3, 2]]], 

#  [[[4, 3], [1, 4]], [[3, 1], [2, 2]]], [[[4, 3], [2, 4]], [[1, 1], [3, 2]]]}

BeatNE(2,3);
# This produced the error that the output exceeded the legth of output limit

with(combinat):
#BeatNEcount(a,b):inputs positive integers a and b and outputs the number of all games (given as bi-matrices) for which there is a unique Nash Equilibrium, AND there exist a strategy choice that is better for BOTH players. 
BeatNEcount:= proc(a,b) local i1, j1, per, pi1, pi2, games, game, beatNE, nash, a1, a2:
 beatNE:=0:
 per := permute(a*b):
 for pi1 in per do
  for pi2 in per do 
   game := [seq([seq([pi1[b*i1+j1],pi2[b*i1+j1]],j1=1..b)],i1=0..a-1)]: 
   nash := NE(game):
   if nops(nash) = 1 then 
    if nops(BetterForBoth(game,nash[1][1],nash[1][2]))>0 then 
     beatNE +=1:
    fi:
   fi:
  od:
 od:
 beatNE: 
end:

BeatNEcount(2,2);
#There are 28 2x2 games that have an outcome that is better than the Nash equilibrium for both players.

BeatNEcount(2,3);
#There are 32400 2x3 games that have an outcome that is better than the Nash equilibrium for both players.

#TotPay(G,s): inputs game G and set s with (at least one) strategy and finds the total payoff of the first strategy 
TotPay:= proc(G,s) local a1,a2:
 a1:=s[1][1]:
 a2:=s[1][2]:
 return G[a1][a2][1]+G[a1][a2][2]: 
end:

#EstBeatNE(a,b,K,M):inputs a,b,K (as for RG(a,b,K) and a large integer M, generates M random games, and counts, out of these M games, 
# how many have the property that they have exactly one Nash Equilibria,
# followed by the number of those, among the former, that have the property that the total pay-offs is better than the total pay-off of the Nash Equilibria,
# followed by the number of those (games with exactly one NE) that have the property that there exists a strategy choice that is NOT a NE but nevertheless is better for both of them (like (Silent, Silent) in the Prisoner's Dilemma).
# Divide these numbers by M, and take evalf 
EstBeatNE:= proc(a,b,K,M) local game,i, oneNash, bestNotNash, existsBetter, nash:
 oneNash:=0: bestNotNash:=0: existsBetter:=0:
 for i from 1 to M do 
  game:=RG(a,b,K):
  nash:=NE(game):
  if nops(nash)=1 then
   oneNash+=1:
   if TotPay(game, BestTot(game))>TotPay(game, nash) then
    bestNotNash+=1: 
   fi:
   if nops(BetterForBoth(game, nash[1][1],nash[1][2]))>0 then
    existsBetter+=1:
   fi:
  fi: 
 od:
 evalf([oneNash/M, bestNotNash/M, existsBetter/M]): 
end:

for i from 1 to 5 do print (EstBeatNE(10, 10, 1000, 1000)):od:
#                  [0.4100000000, 0.2110000000, 0.1070000000]
#                  [0.3880000000, 0.2130000000, 0.1140000000]
#                 [0.3980000000, 0.2140000000, 0.08700000000]
#                  [0.4200000000, 0.2220000000, 0.1110000000]
#                  [0.3760000000, 0.1910000000, 0.1010000000]

#It seems that about 0.4 of the 10 by 10 games have exactly one Nash equilibrium,
# that 0.2 have a Nash equilibrium and a better total payoff elsewhere and
# that 0.1 have a Nash equilibrium and an outcome that is better for both players

#Problem 5
#The utility functions for the two players are:
u1:=q1*(1-q1-q2)^(d1); u2:=q2*(1-q1-q2)^(d2);

#We take the derivative of each with respect to their strategy, set them equal to 0 and then solve this to find the Nash equilibrium.
solve({diff(u1,q1)=0,diff(u2,q2)=0},{q1,q2});
#The output is {q1 = d2/(d1*d2+d1+d2), q2 = d1/(d1*d2+d1+d2)}. Note that this lines up with q1=q2=1/3 when d1=d2=1.

q1 := d2/(d1*d2 + d1 + d2); q2 := d1/(d1*d2 + d1 + d2);
simplify(u1+u2); 
#Then the total output is [d1*((d1*d2)/(d1*d2+d1+d2))^d2 + d2*((d1*d2)/(d1*d2+d1+d2))^d1]/(d1*d2+d1+d2).         


#Problem 6

#We  define the output functions again:
u1:=p1*(1-p1-p2)^(d1); u2:=p2*(1-p1-p2)^(d2);

#take the derivative of the sum (which is the quantity we are trying to optimize) with respect to the strategies p1 and p2
diff(u1+u2, p1); diff(u1+u2,p2);
  
#set them equal to 0 and solve for p1 and p2
solve({diff(u1+u2,p1)=0,diff(u1+u2,p2)=0},{p1,p2});

#This gives {p1 = 1/(d1-d2), p2 = 1/(d2-d1)}. 
#Then the total output is 0, which is a minimum, not a maximum.