In [9]:
plotX(X4, log_timescale=True)
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.pyplot import cm
import pandas as pd
from cycler import cycler
import pylab as plb
plb.rcParams['font.size'] = 8
mat2 = np.array(
[
[2,3],
[1,0]
]
)
mat4 = np.array(
[
[2,0,0,3],
[0,6,7,0],
[0,5,0,4],
[1,0,0,0]
]
)
mat6 = np.array(
[
[2,0,0,0,0,3],
[0,6,0,0,7,0],
[0,0,10,11,0,0],
[0,0,9,0,8,0],
[0,5,0,0,0,4],
[1,0,0,0,0,0]
]
)
mat8 = np.array(
[
[2,0,0,0,0,0,0,3],
[0,6,0,0,0,0,7,0],
[0,0,10,0,0,11,0,0],
[0,0,0,14,15,0,0,0],
[0,0,0,13,0,12,0,0],
[0,0,9,0,0,0,8,0],
[0,5,0,0,0,0,0,4],
[1,0,0,0,0,0,0,0]
]
)
def FP(mat, T, state = None, eps=0, resample=False):
(n, m) = mat.shape
Vmax = np.max(mat)
x = np.zeros(n)
y = np.zeros(m)
X = []
Y = []
V = []
best_response_x = []
best_response_y = []
br_vector_x = []
br_vector_y = []
cntX = []
cntY = []
transitions = []
if state is None:
ei = np.random.randint(0,m)
ej = np.random.randint(0,n)
else:
ei, ej = state
per_y = np.random.uniform(0,eps, n)
per_x = np.random.uniform(0,eps, m)
'''
Fictitious play
'''
t = 0
while not (t == T):
t += 1
if (T == -1) and (Vmax == mat[ei,ej]):
break
'''
Rule: choose the best response;
ties are broken lexicographically due to
argmax operator, a different rule might
be used
'''
if not (t == 1):
util_y = mat.dot(y)
util_x = x.dot(mat)
if resample:
per_y = np.random.uniform(0,eps, n)
per_x = np.random.uniform(0,eps, m)
ei = np.argmax(util_y + per_y)
ej = np.argmax(util_x + per_x)
x[ei] += 1
y[ej] += 1
v_ei = np.zeros(m); v_ei[ei] = 1
v_ej = np.zeros(n); v_ej[ej] = 1
'''
Update statistics
'''
avgx = x/t; X.append(avgx)
avgy = y/t; Y.append(avgy)
cntX.append(x)
cntY.append(y)
V.append(
np.dot(avgx,mat).dot(avgy)
)
if(best_response_x and ei != best_response_x[-1]):
prev_ei = best_response_x[-1]
transitions.append((t, 'i', prev_ei, ei))
print(transitions[-1], mat[ei,ej])
if(best_response_y and ej != best_response_y[-1]):
prev_ej = best_response_y[-1]
transitions.append((t, 'j', prev_ej, ej))
print(transitions[-1], mat[ei,ej])
best_response_x.append(ei)
best_response_y.append(ej)
br_vector_x.append(v_ei)
br_vector_y.append(v_ej)
'''
Print any results
'''
# if(not t==1): print(util_y + per_y)
# print(avgx, avgy)
# print(best_response_x[-1], best_response_y[-1])
X = np.asarray(X)
Y = np.array(Y)
V = np.array(V)
br_vector_x = np.array(br_vector_x)
br_vector_y = np.array(br_vector_y)
cntX = np.array(cntX)
cntY = np.array(cntY)
return (X, Y, V, transitions, br_vector_x, br_vector_y, cntX, cntY)
def plotX(X, log_timescale=False, legend=True):
fig, ax1 = plt.subplots(1, 1, figsize=(4,3))
T, n = X.shape
time = np.arange(1,T,1)
ax1.plot(X)
if legend: ax1.legend(np.arange(n)+1)
ax1.set_xlabel('iterations')
if log_timescale:
ax1.set_xscale("log")
fig.tight_layout()
fig.savefig("row_strategy", dpi=1200)
def plot_nash_gap(mat, X, Y, V, log_timescale=False, time_lim=-1):
T, _ = X.shape
time = np.arange(1,T+1,1)
xtA = np.einsum('ki,ij->kj', X, mat)
br_v_y = np.max(xtA, axis=1)
Ayt = np.einsum('ij,kj->ki', mat, Y)
br_v_x = np.max(Ayt, axis=1)
fig, ax1 = plt.subplots(1, 1, figsize=(4,3))
ax1.plot(time, (br_v_x - V) + (br_v_y - V))
ax1.set_title(r'$Gap_X$')
ax1.set_xlabel('iterations')
ax1.set_ylim([0,1])
if log_timescale:
ax1.set_xscale("log")
fig.tight_layout(pad=0)
fig.savefig("nash_gap", dpi=1200)
T4 = 1000
X4, Y4, V4, transitions4, _, _, _, _ = FP(mat4, 100 * T4, (3,0))
(2, 'i', 3, 0) 2 (4, 'j', 0, 3) 3 (11, 'i', 0, 2) 4 (38, 'j', 3, 1) 5 (174, 'i', 2, 1) 6 (990, 'j', 1, 2) 7
df4 = pd.DataFrame(transitions4, columns=['t','player','from','to']); df4
| t | player | from | to | |
|---|---|---|---|---|
| 0 | 2 | i | 3 | 0 |
| 1 | 4 | j | 0 | 3 |
| 2 | 11 | i | 0 | 2 |
| 3 | 38 | j | 3 | 1 |
| 4 | 174 | i | 2 | 1 |
| 5 | 990 | j | 1 | 2 |
plotX(X4, log_timescale=True)
plot_nash_gap(mat4, X4, Y4, V4, log_timescale=True)
T6=4577014
X6, Y6, V6, transitions6, _, _, _, _ = FP(mat6, 2 * T6, (5,0))
(2, 'i', 5, 0) 2 (4, 'j', 0, 5) 3 (11, 'i', 0, 4) 4 (38, 'j', 5, 1) 5 (174, 'i', 4, 1) 6 (990, 'j', 1, 4) 7 (6703, 'i', 1, 3) 8 (52406, 'j', 4, 2) 9 (463734, 'i', 3, 2) 10 (4577014, 'j', 2, 3) 11
df6 = pd.DataFrame(transitions6, columns=['t','player','from','to']); df6
| t | player | from | to | |
|---|---|---|---|---|
| 0 | 2 | i | 5 | 0 |
| 1 | 4 | j | 0 | 5 |
| 2 | 11 | i | 0 | 4 |
| 3 | 38 | j | 5 | 1 |
| 4 | 174 | i | 4 | 1 |
| 5 | 990 | j | 1 | 4 |
| 6 | 6703 | i | 1 | 3 |
| 7 | 52406 | j | 4 | 2 |
| 8 | 463734 | i | 3 | 2 |
| 9 | 4577014 | j | 2 | 3 |
plotX(X6[::2], log_timescale=True, legend=False)
plot_nash_gap(mat6, X6[::2], Y6[::2], V6[::2], log_timescale=True)
