Generating Functional Analysis of

Minority Games with Inner Product Strategy Definitions

(work in progress)

ACC Coolen King’s College London

• Brief intro to Minority Games

• Lookup-table versus inner product MGs

• Generalization of GFA for MGs with real histories • Analysis of macroscopic laws

– fake history limit

– true history: random matrix theory Brief introduction to MGs

[figure: www.mammon.com; Handbook; of; Trading; Trading; Made; Simple; Predict; Currency; Markets; Buy; Sell]

N agents, i = 1 … N:

• At each round ℓ:

all get info I(ℓ) ∈ {I_{1}, …, I_{p}} each places a bid b_{i}(ℓ) ∈ IR

• Those in the minority group win ∑_{j} b_{j}(ℓ) > 0 : b_{i}(ℓ) < 0 wins ∑_{j} b_{j}(ℓ) < 0 : b_{i}(ℓ) > 0 wins

• Each agent i has S strategies converting I(ℓ) into bid b_{i}(ℓ)

• dynamics:

choice of strategy a ∈ {1, …, S}, as a function of time, for all agents, based on strategies’ performance overall bid: A(ℓ) = N^{−\frac{1}{2}} ∑_{i} b_{i}(ℓ): Lookup table MGs (Challet, Marsili, Zhang, ...):

info :  m step history ,  λ(ℓ) = (sgn [A(ℓ−1)], …, sgn [A(ℓ−m)])
strat :  lookup table ,  R_{ia} = (R_{ia}^{1}, …, R_{ia}^{p})
bid : strategy a, info λ, b_{i}(ℓ) = R_{ia}^{λ}
history window: Δt = Δℓ/N = O(N^{−1} log N)

Inner product MGs (Cavagna, Sherrington, Garrahan, ...):

info : p step history , λ(ℓ) = (f[A(ℓ−1)], …, f[A(ℓ−p)])
strat : linear functional ,  R_{ia} = (R_{ia}^{1}, …, R_{ia}^{p})
bid : strategy a, info λ,  b_{i}(ℓ) = p^{−\frac{1}{2}} _{μ≤p}^{∑} R_{ia}^{μ}λ_{μ}(ℓ)

history window: Δt = Δℓ/N = O(1)

Why renewed interest in Inner product MGs?

• Inner product MGs closer to how real agents predict time series (generalized linear models, ARMA, ARIMA, etc)

• Lookup-table MGs analyzed extensively using replica & GFA techniques (including real history version)

• Not true for inner product MGs

• Lookup table: history window O(N^{−1} log N) → 0 Inner product: history window O(N^{0})

• Lookup table MGs with real market history crucial object: history frequency distribution ϱ(f)

history strings:

λ(ℓ) = (sgn [A(ℓ − 1)], …, sgn [A(ℓ − m)]) 2^{m} = αN

π_{λ} = lim_{L→∞} \frac{1}{L} _{ℓ≤L}^{∑} δ_{λ,λ(ℓ)} ϱ(f) = lim_{N→∞} 2^{−m} _{λ}^{∑} δ[f − 2^{m}π_{λ}]

f ϱ(f)  f ϱ(f) α < α_{c}  α > α_{c}

• Inner product MGs with real market history no such thing as ϱ(f), history string is of length O(N) ...

Generalization of the GFA theory for MGs with real history inner product and lookup table MGs as special cases

(always S = 2)

• decision noise:

sgn [q_{i}(ℓ)] → σ[q_{i}(ℓ), z_{i}(ℓ)] \begin{matrix}additive : & σ[q, z] = sgn [q + T z] \\ multipl : & σ[q, z] = sgn [q]sgn [1 + T z] \end{matrix}

• real vs fake history:

A(ℓ − μ) → (1 − ζ)A(ℓ − μ) + ζZ(ℓ, μ)
Z(ℓ, μ) : Gaussian, ⟨Z⟩ = 0
consistent :  Z(ℓ, μ) = Z(ℓ − μ),  ⟨Z(ℓ)Z(ℓ′)⟩ = S^{2}δ_{ℓℓ′}
inconsistent :  Z(ℓ, μ) all indep ,  ⟨Z(ℓ, μ)Z(ℓ′, μ′)⟩ = S^{2}δ_{ℓℓ′}δ_{μμ′}

• Lookup table MGs:

info :  λ(ℓ) = (sgn [A(ℓ−1)], …, sgn [A(ℓ−m)])
strategy :  R_{ia} = (R_{ia}^{1}, …, R_{ia}^{p}) 2^{m} = p
bid :  b_{i}(ℓ) = R_{ia}^{λ}

Inner product MGs:

info :  λ(ℓ) = (f[A(ℓ−1)], …, f[A(ℓ−p)])
strategy :  R_{ia} = (R_{ia}^{1}, …, R_{ia}^{p})
bid :  b_{i}(ℓ) = p^{−\frac{1}{2}} ∑_{μ≤p} R_{ia}^{μ}λ_{μ}(ℓ)

• add bid perturbation term:

A(t) = \frac{1}{√N} _{i}^{∑} b_{i}(t) + A_{e}(t)

generating functional ⟨ ⟩: over {z_{i}(ℓ), Z(ℓ, λ)} \overline{[ ]}: over \{R_{ia}^{μ}\}

\overline{Z [ψ]} = \overline{⟨e^{−i ∑_{iℓ} ψ_{i}(ℓ)σ[q_{i}(ℓ),z_{i}(ℓ)]} ⟩}

manipulations:

\overline{Z [ψ]} = ∫ DCDĈDGDĜ … e^{NΨ[C,Ĉ,G,Ĝ,...]}

saddle-point equations for dynamic order parameters

C(ℓ, ℓ′) = lim_{N→∞} \frac{1}{N} _{i}^{∑} \overline{⟨σ[q_{i}(ℓ), z_{i}(ℓ)]σ[q_{i}(ℓ′), z_{i}(ℓ′)]⟩}
G(ℓ, ℓ′) = lim_{N→∞} \frac{1}{N} _{i}^{∑} \frac{∂}{∂θ_{i}(ℓ′)} \overline{⟨σ[q_{i}(ℓ), z_{i}(ℓ)]⟩}

Unified theory

• Effective single agent process:

\frac{d}{dt}q(t) = θ(t) − α ∫_{0}^{t}dt′ R(t, t′) σ[q(t′)] + √α η(t)

Gaussian η(t), ⟨η(t)⟩ = 0, ⟨η(t)η(t′)⟩ = Σ(t, t′)

σ[q] = ∫ Dz σ[q, z]

• closed eqns for order parameters:

C(t, t′) = ⟨σ[q(t)]σ[q(t′)]⟩_{⋆} G(t, t′) = \frac{δ}{δθ(t′)} ⟨σ[q(t)]⟩_{⋆}

• All complications: in relation between {R, Σ} and {C, G} involves effective overall bid process Time-translation invariant stationary states what do we need to know of {R, Σ}?

C(t, t′) = C(t − t′), G(t, t′) = G(t − t′) R(t, t′) = R(t − t′), Σ(t, t′) = Σ(t − t′)

static order pars:

χ = ∫_{0}^{∞}dt G(t), χ_{R} = ∫_{0}^{∞}dt R(t)

c = lim_{t→∞} C(t), ϕ : fraction of ‘frozen′ agents

given by

ϕ = 1 − Erf [u]
c = σ^{2}[∞]\{1 − Erf [u] + \frac{1}{2u^{2}} Erf [u] − \frac{1}{u√π}e^{−u^{2}}\}
χ = Erf [u]/αχ_{R}
u = √αχ_{R}σ[∞]/S_{0}√2,  S_{0}^{2} = Σ(∞)

so for statics we need only • S_{0}^{2} = Σ(∞) and χ_{R} = ∫_{0}^{∞}dt R(t)

χ_{R} = lim_{δ→0} \{\overline{W} [0, 0; \{A, Z\}] + ∞ ; ∑ ; ℓ=1 \frac{∂}{∂A(0)} ⟨⟨\overline{W} [ℓ, 0; \{A, Z\}]A(ℓ)⟩ ⟩_{\{A,Z\}}\}
S_{0}^{2} = lim_{δ→0} lim_{L→∞} \frac{η̃}{L^{2}δ} L ; ∑ ; ℓ,ℓ′=1 ⟨⟨\overline{W} [ℓ, ℓ′; \{A, Z\}]A(ℓ)A(ℓ′)⟩ ⟩_{\{A,Z\}}

• Differences between models: \overline{W} [ℓ, ℓ′; \{A, Z\}] similarity between histories observed at times ℓ and ℓ′

lookup table :  \overline{W} [ℓ, ℓ′; \{A, Z\}] = δ_{λ(ℓ,A,Z),λ(ℓ′,A,Z)}
inner product :  \overline{W} [ℓ, ℓ′; \{A, Z\}] =

\frac{1}{αN} _{λ≤p}^{∑} f [(1−ζ)A(ℓ−λ) + ζZ(ℓ, λ)] f [(1−ζ)A(ℓ′−λ) + ζZ(ℓ′, λ)]

• Effective overall bid process:

A(ℓ) = A_{e}(ℓ) + ϕ_{ℓ} − \frac{1}{2} η̃ _{ℓ′<ℓ}^{∑} G(ℓ, ℓ′)\overline{W} [ℓ, ℓ′; \{A, Z\}]A(ℓ′)

Gaussian random fields:

⟨ϕ_{ℓ}⟩_{\{ϕ|A,Z\}} = 0, ⟨ϕ_{ℓ}ϕ_{ℓ′}⟩_{\{ϕ|A,Z\}} = \frac{1}{2}[1 + C(ℓ, ℓ′)]\overline{W} [ℓ, ℓ′; \{A, Z\}]

Inner product MG with inconsistent fake market history

• Put ζ → 1, calculate kernels (grammatically), define κ = ∫ Dz f^{2}[Sz]

• Inner product and lookup table MGs differ only in characteristic amplitude, that can be transformed away:

G_{IP}(t, t′) = κ^{−1}G_{LU}(t, t′), θ_{IP}(t) = κθ_{LU}(t), σ_{IP}^{2} = κσ_{LU}^{2} The real problem: generalized MGs with true market history

• define random matrix B(ℓ):

B_{λλ′}(ℓ) = F_{λ}[ℓ, A, Z]F_{λ′}[ℓ, A, Z]

LU : F_{λ}[ℓ, A, Z] = √αN δ_{λ,λ(ℓ,A,Z)} λ ∈ {−1, 1}^{m}
IP : F_{λ}[ℓ, A, Z] = f[(1 − ζ)A(ℓ − λ) + ζZ(ℓ, λ)]  λ ∈ {1, …, p}

• {R, Σ} can be written in terms of

Δ_{r+1} (ℓ_{0}, …, ℓ_{r}) = \frac{1}{p} Tr ⟨⟨B(ℓ_{0})B(ℓ_{1}) … B(ℓ_{r})⟩⟩_{\{A,Z\}}

Δ̃_{r+r′+2} (ℓ_{0}, …, ℓ_{r}; ℓ′_{0}, …, ℓ′_{r′}) =

\frac{1}{p} Tr ⟨⟨B(ℓ_{0})B(ℓ_{1}) … B(ℓ_{r})B(ℓ′_{r′}) … B(ℓ′_{1})B(ℓ′_{0})⟩⟩_{\{A,Z\}}

˜Δ̃_{r+r′+1} (ℓ_{0}, ℓ_{1} …, ℓ_{r}; ℓ_{0}, ℓ′_{1}, …, ℓ′_{r′}) =

\frac{1}{p} Tr ⟨⟨B(ℓ_{0})B(ℓ_{1}) … B(ℓ_{r})B(ℓ′_{r′}) … B(ℓ′_{1})⟩⟩_{\{A,Z\}}

Short history correlation times in TTI stationary states In working out static eqns:

r ; ∏ ; i=1 B(ℓ_{i}) → B^{r}(A, Z) B(A, Z) = lim_{L→∞} \frac{1}{L} _{ℓ≤L}^{∑} B(ℓ)

μ_{i}(A, Z) ev of B(A, Z) : ϱ(μ) = ⟨⟨\frac{1}{p} p ; ∑ ; i=1 δ[μ − μ_{i}(A, Z)]⟩⟩_{\{A,Z\}}

Δ_{r+1} (ℓ_{0}, …, ℓ_{r}) → ∫_{0}^{∞}dμ ϱ(μ) μ^{r+1}
Δ̃_{r+r′+2} (ℓ_{0}, …, ℓ_{r}; ℓ′_{0}, …, ℓ′_{r′}) → ∫_{0}^{∞}dμ ϱ(μ) μ^{r+r′+2}
˜Δ̃_{r+r′+1} (ℓ_{0}, ℓ_{1} …, ℓ_{r}; ℓ_{0}, ℓ′_{1}, …, ℓ′_{r′}) → ∫_{0}^{∞}dμ ϱ(μ) μ^{r+r′+1}

χ_{R} = ∫_{0}^{∞}dμ ϱ(μ)\frac{μ}{1 + μχ} S_{0}^{2} = (1 + c) ∫_{0}^{∞}dμ ϱ(μ)\frac{μ^{2}}{(1 + μχ)^{2}}

• Generalized MGs with real market history:

eigenvalue distribution ϱ(μ) of random matrix B(A, Z) takes over role of history frequency distribution ϱ(f) in lookup table MGs

• link with lookup table MG theory:

B_{λλ′}(A, Z) = pδ_{λ}_{λ}_{′}π_{λ}(A, Z)

ϱ(μ) = lim_{p→∞} \frac{1}{p} _{λ}^{∑}⟨⟨δ [μ − pπ_{λ}(A, Z)]⟩⟩_{\{A,Z\}}

(recover the history frequency distr)

Conclusions and summary

• Generation functional analysis of MGs can be generalized, to include lookup table & inner product as special cases

• Exact macroscopic theory in terms of effective single agent, and (in case of real histories) an effective overall bid process

• Fake histories:

inner product and lookup table MGs differ only in simple rescaling of observables, phase diagrams identical

• Real histories:

− Short history correlation time ansatz can be generalized − Role of history frequency distribution in lookup table MGs

taken over by eigenvalue spectrum of a random matrix (randomness: generated by the effective bid process)

• To be finished:

calculation of random matrix eigenvalue spectrum ...