#OK to post homework 
#Natalya Ter-Saakov, Feb 13, Assignment 7 
read "C7.txt":

#Problem 2: 
#TypeCounts22(K1,K2) - inputs a very large positive integer (at least ten million),
# and fairly large positive integer K2 (say, around 10000),
# uses RG(2,2,K1) K2 times and
# outputs the following list of length 4 of floating-point numbers 
# evalf([Number of Games with Exactly One Pure Nash Equilibrium, Number of Games with Exactly Two Pure Nash Equilibrium and No Mixed one, Number of Games with No Pure Nash Equilibrium and one Mixed , Number of Games with Two Pure and One Mixed]/K2) 

TypeCounts22:= proc(K1,K2) local G, OnePure, TwoPure, OneMix, TwoPureOneMix, i, pure, all:
 OnePure:=0: TwoPure:=0: OneMix:=0: TwoPureOneMix:=0: 
 for i from 1 to K2 do 
  G:=RG(2,2,K1):
  pure:= nops(NE(G)):
  all:= nops(MNE22(G)):
  if pure = 1 then
   OnePure+=1:
  elif pure=0 and all=1 then
   OneMix+=1:
  elif pure = 2 then
   if all=2 then
    TwoPure+=1:
   elif all=3 then
    TwoPureOneMix+=1:
   fi:
  fi:
 od:
 evalf([OnePure, TwoPure, OneMix, TwoPureOneMix]/K2):
 end:

for i from 1 to 5 do j:= TypeCounts22(10^8,10000); od;
#Output:
# [0.7583000000, 0., 0.1199000000, 0.1218000000]
# [0.7574000000, 0., 0.1221000000, 0.1205000000]
# [0.7526000000, 0., 0.1243000000, 0.1231000000]
# [0.7488000000, 0., 0.1264000000, 0.1248000000]
# [0.7499000000, 0., 0.1236000000, 0.1265000000]
#All of which look approximately like [0.75, 0, 0.12, 0.12].

#Problem 3:
#Claim: In a two by two game, if there are two pure Nash equilibia, there is also at least one mixed equilibirium.

#Proof:
#Case 1: One player has a (weak) dominating strategy.
#Suppose, without loss of generality, that player row has a dominating strategy, specifically row 1. 
#If the column player has different payoffs for [r1, c1] and [r1, c2], then there is only one pure Nash equilibrium, whichever one they prefer. 
#However, if the payoff for the column player in row 1 is always the same, then both entries are pure Nash equilibia,
# and the mixed equilibria are [p1, p2]=[1, p2] for all p2 from 0 to 1, inclusive.

#Case 2: Neither player has a dominating strategy.
#Suppose, without loss of generality that player row's best response to c1 is r1 and their best response to c2 is r2. 
#Then, to have 2 pure Nash equilibria, player col's best response to r1 must be c1 and their best response to r2 must be c2. 
#If the game is [[[a11,b11],[a12,b12]],[[a21,b21],[a22,b22]]], then 
#The payoff for player 1 is p1*p2*a11+p1*(1-p2)*a12+(1-p1)*p2*a21+(1-p1)*(1-p2)*a22=((a11 - a12 - a21 + a22)*p2 + a12 - a22)*p1 + (a21 - a22)*p2 + a22
#The payoff for player 2 is p1*p2*b11+p1*(1-p2)*b12+(1-p1)*p2*b21+(1-p1)*(1-p2)*b22=((b11 - b12 - b21 + b22)*p1 + b12 - b22)*p2 + (b21 - b22)*p1 + b22
#Note that both of these are linear, so the optimal response of player 1 is a pure strategy, determined by the sign on the coefficient of p1 in the first expression,
# unless that coefficient is 0. Since when p2=1, p1=1 is optimal and when p2=0, p1=0 is optimal, we know that as p2 goes from 0 to 1, the sign of the coefficient changes.
#Then, by Intermediate Value Theorem, there must exist a p2 in (0,1) such that the coefficient on p1 is 0. 
#Similarly, for the coefficient on p2 in the second expression, there must exist a p1 in (0,1) such that the coefficient on p2 is 0. 
#This pair of [p1,p2] is exactly the mixed equilibria we wished to prove exists.  

#Problem 4:
#Lemma: In a 2 by 2 game, there is one pure Nash equilibrium exactly when there exists a (strictly) dominating strategy and the other player has a preference.
#Proof: We already know that if iterated domination yields an equilibrium, this is a Nash equilibrium. 
#Suppose, without loss of generality, that the only Nash equilibrium in G:=[[[a11,b11],[a12,b12]],[[a21,b21],[a22,b22]]] is [1,1]. 
#This means that a11 >= a21 and b11 >= b12. 
#If a12 > a22, then row 1 strictly dominates row 2. In that case, if b11 = b12, then both [1,1] and [1,2] are pure Nash equilibria, so b11>b12 and we are done.
#If a12 <= a22, then if b22 >= b21, [2,2] is also a pure Nash equilibrium. Thus, b22 < b21, meaning that col 1 strictly dominates col 2, and similarly to the previous case, a11 > a21.

#Claim: The limiting value of the first experiment is 3/4 (as K1 and K2 go to infinity).

#Proof: 
#The first experiment counts the number of games with exactly one Pure Nash equilibrium. 
#By the above lemma, this is equivalent to counting the number of games with a strictly dominating strategy. 

#P(G has a strictly dominating strategy AND the other player has a preference)
# = P(G has a strictly dominating strategy)*P(other player has a preference) 
# = (1-P(G has no strictly dominating strategy))*(1-P(other player has no preference))
# = (1-P(G has no dominating row AND G has no dominating column))*(1-P(other player has no preference)
# = (1 - P((a11>a21 AND a12<a22) OR (a11<a21 AND a12>a22))*P((b11>b12 AND b21<b22) OR (b11<b12 AND b21>b22)))*(1-P(other player has no preference)
# = (1-(P(a11>a21)*P(a12<a22)+P(a11<a21)*P(a12>a22))*(P(b11>b12)*P(b21<b22)+P(b11<b12)*P(21>22)))*1-P(other player has no preference)

#At this point, note that P(x<y) = (K1^2-1)/(2*K1^2) and P(other player has no preference) = 1/K1^2.

#P(G has a strictly dominating strategy AND the other player has a preference)
# = (1-(K1^2-1)^4/(4*K1^8))*(1-1/K1^2) = (3*K1^10 + K1^8 - 10*K1^6 + 10*K1^4 - 5*K1^2 + 1)/(4*K1^10)

#In the limit as K1 goes to infinity, this goes to 3/4. 


#Problem 5:
#PayOffGG(G,p1,p2) inputs G, an arbitrary 2-person game,
# and probability vectors p1, p2 (i.e. they add up to 1) and
# outputs a list of length 2 with the payoffs of Player Row and Player Col.

PayOffGG:= proc(G,p1,p2) local i,j, r, c, P1, P2:
 if add(i,i in p1) <> 1 or add(j, j in p2) <> 1 then
  return(FALSE):
 fi:
 if nops(G) <> nops(p1) or nops(G[1]) <> nops(p2) then
  return(FALSE):
 fi:
 P1:=0: P2:=0:
 for r from 1 to nops(G) do
  for c from 1 to nops(G[1]) do
   P1+=p1[r]*p2[c]*G[r][c][1]:
   P2+=p1[r]*p2[c]*G[r][c][2]:
  od:
 od:
 [P1,P2]:
 end: