# Experimental Math Rocks # Homework 20 # Phil Benjamin # Free to post (although incomplete) HelpHW20 := proc() print(`Problem 1: GathStat(n,K,L)`); print(`Problem 2: TBD ...`); print(`Problem 3: Pay2K(M2,K) NE2(A2,B2,K)`); print(`Problem 4: AllFraction3(K) Pay3K(M3,K) NE3(A3,B3,K)`); print(`Problem 5: AllFractionD(d,K) PayMK(M,K) NEK(A,B,K)`); end: # Problem 1 # GathStat(n,K,L) # Input: generate L random nxn matrices, A, with values 0..K # Output: list L: L[i] count number that have "i" Nash Equilibria # for PayOffs (A,transpose(A)) # Note: Use PNE(A,B) to find set of Nash equilibria GathStat := proc(n,K,L) local t,Count,A,B,NEset,i; Count := [0$(n^2+1)]; for t from 1 to L do A := GenRanMat(n,n,K); B := tra(A); NEset := PNE(A,B); i := nops(NEset)+1; Count[i] := Count[i] + 1; end; return Count; end: # Problem 2 # For modest n and K, but large L (say 1000), conjecture # probability distribution in Problem 1 # TBD ... # Problem 3 # NE2(A,B,K) # Using modified PNE(A,B), with A,B 2x2 matrices, # look for Nash equilibria of form [i/K,1-i/K] for y [and x?] # General strategy: expand 2x2 matrix into (K+1)x(K+1) matrix # with payoffs the weighted average of the original, then find # "pure" strategies in this matrix Pay2K := proc(M2,K) local MK,i,j; MK := [seq( [seq( (1-j/K)*(1-i/K)*M2[1][1] + (1-j/K)*(i/K)*M2[2][1] + (j/K)*(1-i/K)*M2[1][2] + (j/K)*(i/K)*M2[2][2], j=0..K)], i=0..K)]; return MK; end: # Note: A and B must be 2x2 matrices! NE2 := proc(A2,B2,K) local AK,BK; AK := Pay2K(A2,K); BK := Pay2K(B2,K); return PNE(AK,BK); end: # Problem 4 # Like Problem 3 with 3x3 matrices # General strategy like Problem 3 but each new vertex represents a weighted # average of 1,2,3 # Find all fractional combinations of 3 vertices with(combinat): AllFraction3 := proc(K) local AC,i,j; AC := composition(K+3,3); AC := sort(AC); return [seq([seq((AC[i][j]-1)/K,j=1..3)],i=nops(AC)..1,-1)]; end: Pay3K := proc(M3,K) local AF,i,j,MK,i3,j3,nf; AF := AllFraction3(K); nf := nops(AF); MK := [seq( [seq( add(add(AF[i][i3]*AF[j][j3]*M3[i3][j3],j3=1..3),i3=1..3), j=1..nf)], i=1..nf)]; return MK; end: # Note: A and B must be 3x3 matrices! NE3 := proc(A3,B3,K) local AK,BK; AK := Pay3K(A3,K); BK := Pay3K(B3,K); return PNE(AK,BK); end: # Problem 5 - optional challenge # Like problem 3 with nxn matrices # Strategy as in Problem 4 generalized to mxn matrices! AllFractionD := proc(d,K) local AC,i,j; AC := composition(K+d,d); AC := sort(AC); return [seq([seq((AC[i][j]-1)/K,j=1..d)],i=nops(AC)..1,-1)]; end: PayMK := proc(M,K) local m,n,AFm,AFn,i,j,MK,im,jn,nfm,nfn; m := nops(M); n := nops(M[1]); AFm := AllFractionD(m,K); AFn := AllFractionD(n,K); nfm := nops(AFm); nfn := nops(AFn); MK := [seq( [seq( add(add(AF[i][im]*AF[j][jn]*M3[im][jn],jn=1..n),im=1..m), j=1..nfn)], i=1..nfm)]; return MK; end: NEK := proc(A,B,K) local AK,BK; AK := PayMK(A,K); BK := PayMK(B,K); return PNE(AK,BK); end: # Problem 6 # LetsCooperate(A,B,i,j) # Input: A,B matrices with [i,j] pure Nash equilibrium # Output: set of [r,s] with A[r][s] > A[i,j] and B[r,s] > B[i][j] # (these are pairs of better solutions if A and B could agree! # TBD ############################################################################## # Classwork 20 material #April 8, 2013, Nash Equilibria for general two player games Help:=proc(): print(`MaxF(F,x,n) , BRrow(A,y) , BRcol(B,x) `): print(`PNE(A,B) , GenRanMat(m,n,K) , tra(A) `): end: #Given two matrices A and B m by n #PayOff for A: xAy Payoff for B: xBy (x is a row vector of #size m and y is a column of size n) #(x,y) is a Nash Equilibrium if x is in BestResponse(A,y) #and y is in BestResponse(B,x) #MaxF(F,x,n): inputs sumbol x, positive integer n #and a linear combination of x[1], ..., x[n] #outputs the set of i such that x[i]=1 makes F max #For example, #MaxF(3*x[1]+4*x[2]+4*x[3]+2*X[4],x,4); MaxF:=proc(F,x,n) local i,champs,rec,nathan: champs:={1}: rec:=coeff(F,x[1],1): for i from 2 to n do nathan:=coeff(F,x[i],1): if nathan=rec then champs:=champs union {i}: elif nathan>rec then champs:={i}: rec:=nathan: fi: od: champs: end: #BRrow(A,y): The best response by the ROW player #(whose payoff matrix is the m by n matrix A #to the strategy y of the column player #output is a set of pure strategies BRrow:=proc(A,y) local i,j,F,x,m,n: m:=nops(A): n:=nops(A[1]): F:=add(add(x[i]*A[i][j]*y[j],i=1..m),j=1..n): MaxF(F,x,m): end: #BRcol(B,x): The best response by the COL player #(whose payoff matrix is the m by n matrix B #to the strategy x of the row player #output is a set of pure strategies BRcol:=proc(B,x) local i,j,F,y,m,n: m:=nops(B): n:=nops(B[1]): F:=add(add(x[i]*B[i][j]*y[j],i=1..m),j=1..n): MaxF(F,y,n): end: #PNE(A,B) PNE:=proc(A,B) local m,n,nash,i,j,john: m:=nops(A): n:=nops(A[1]): nash:={}: for j from 1 to n do john:=BRrow(A,[0$(j-1),1,0$(n-j)]): for i in john do if j in BRcol(B,[0$(i-1),1,0$(m-i)]) then nash:=nash union {[i,j]}: fi: od: od: nash: end: #GenRanMat(m,n,K): a random m by n matrix with #entries from 0 to K GenRanMat:=proc(m,n,K) local i,j,tim: tim:=rand(0..K): [seq([seq(tim(),j=1..n)],i=1..m)]: end: #transpose of A tra:=proc(A) local i,j,m,n: m:=nops(A): n:=nops(A[1]): [seq([seq(A[j][i],j=1..m)],i=1..n)]: end: