a r X i v : c o n d  m a t / 9 9 0 8 4 8 0 v 3 [ c o n d  m a t . s t a t  m e c h ] 8 D e c 1 9 9 9
Exact solution of a modiﬁed El Farol’s barproblem: Eﬃciency and the role of marketimpact
Matteo Marsili
Istituto Nazionale per la Fisica della Materia (INFM), TriesteSISSA Unit,V. Beirut 24, Trieste I34014
Damien Challet
Institut de Physique Th´eorique, Universit´e de Fribourg, CH1700
and Riccardo Zecchina
The Abdus Salam International Centre for Theoretical Physics Strada Costiera 11,P.O. Box 586, I34014 Trieste
Abstract
We discuss a model of heterogeneous, inductive rational agents inspired by the ElFarol Bar problem and the Minority Game. As in markets, agents interact througha collective aggregate variable – which plays a role similar to price – whose valueis ﬁxed by all of them. Agents follow a simple reinforcementlearning dynamicswhere the reinforcement, for each of their available strategies, is related to thepayoﬀ delivered by that strategy. We derive the exact solution of the model in the“thermodynamic” limit of inﬁnitely many agents using tools of statistical physicsof disordered systems. Our results show that the impact of agents on the marketprice plays a key role: even though price has a weak dependence on the behavior of each individual agent, the collective behavior crucially depends on whether agentsaccount for such dependence or not. Remarkably, if the adaptive behavior of agentsaccounts even “inﬁnitesimally” for this dependence they can, in a whole range of parameters, reduce global ﬂuctuations by a ﬁnite amount. Both global eﬃciencyand individual utility improve with respect to a “price taker” behavior if agentsaccount for their market impact.
⋆
We acknowledge J. Berg, S. Franz and Y.C. Zhang for discussions and usefulsuggestions. On the economic side we proﬁted greatly from critical discussions withA. Rustichini and F. VegaRedondo on learning and dynamic games. This work waspartially supported by Swiss National Science Foundation Grant Nr 2046918.98.
Preprint submitted to Elsevier Preprint 1 February 2008
1 Introduction
The El Farol bar problem [1] has become a popular paradigm of complexsystems. It describes the situation where
N
persons have to choose whetherto go or not to a bar which is enjoyable only if it is not too crowded. In orderto choose, each person forms mental schemes, hypotheses or behavioral rulesbased on her beliefs and she adopts the most successful one on the basis of pastperformance. Inductive [1], low [2] or generally bounded rationality based on
learning theory [3] is regarded as a more realistic approach to the behavior of real agents in complex strategic situations[4]. This is specially true in contextsinvolving many heterogeneous agents with limited information, such as the ElFarol bar problem. Theoretical advances, beyond numerical simulations, istechnically very hard on these problems and it has been regarded as a majorstep forward in the understanding of complex systems[5].The minority game [6,7] represents a ﬁrst step in this direction. It indeed describes a system of interacting agents with inductive rationality which face theproblem of ﬁnding which of two alternatives shall be chosen by the minority.This problem is quite similar in nature to the El Farol bar problem as theresult for each agent depends on what all other agents will do and there isno
a priori
best alternative. These same kind of situations arise generally insystems of many interacting adaptive agents, such as markets[7,8].Numerical simulations by several authors [6,8 –12] have shown that the minor
ity game (MG) displays a remarkably rich emergent collective behavior, whichhas been qualitatively understood to some extent by approximate schemes[7,13,14]. In this paper, which follows refs. [11,15], we study a generalized mi
nority game and show that a full statistical characterization of its stationarystate can be derived analytically in the “thermodynamic” limit of inﬁnitelymany agents. Our approach is based on tools and ideas of statistical physicsof disordered systems[16].The minority game, as the El Farol bar problem, allows for a relatively easydeﬁnition in words. This may be enough for setting up a computer code to runnumerical simulations, but it is clearly insuﬃcient for an analytical approach.Therefore we shall, in the next section, deﬁne carefully its mathematical formulation. We shall only discuss brieﬂy its motivation, for which we refer thereader to refs. [6 –8]. Even though the behavioral assumptions on which the
MG is based may be questionable when applied to ﬁnancial markets (see sect.2.4), still we ﬁnd it convenient to consider and discuss the model as a toymodel for a market, in line with refs. [7,8,17]. The relation to markets, at thislevel, may just be seen as a convenient language to discuss the results in simpleterms. This choice reﬂects our taste and surely more work needs to be doneto show the relation of the minority game with real ﬁnancial markets. We be2
lieve, however, that because of the statistical nature of the collective behavior – which are usually quite robust with respect to microscopic changes – ourresults may be qualitatively representative of generic systems of agents interacting through a global quantity
via
a minority mechanism, such as markets.The minority game indeed captures the essential interaction between agentsbeliefs and market ﬂuctuations – how individual beliefs, processing ﬂuctuations, produce ﬂuctuations in their turn. This interaction is usually shortcutin mathematical economy assuming market eﬃciency, i.e. that prices
instantaneously
react to and incorporate agents beliefs. The motivation underlying theeﬃcient market hypothesis, is, in few words that if there where ineﬃciencies – or arbitrage opportunities – that would be exploited by speculators in themarket and washed out very quickly. Implicitly one is assuming that there isan inﬁnite number of agents in the market who are using very sophisticatedstrategies which can detect, exploit and eliminate arbitrages very quickly. As“stylized” as it may be, the minority game allows to study how a ﬁnite number of heterogeneous agents interact in a complex system such as a market.It allows to ask to what extent this “stylized” market is ineﬃcient and howagents really exploit arbitrage opportunities and to what extent.After deﬁning the stage game, we shall brieﬂy discuss its Nash equilibria: theseare the reference equilibria of deductive rational agents. Finally we shall pass tothe repeated game with adaptive agents which follow exponential learning. Weshow that the key diﬀerence between agents playing a Nash equilibrium andagents in the usual minority game is
not
that the ﬁrst are deductive whereasthe latter are inductive. Rather the key issue is whether agents account fortheir “market impact” or not. By market impact we refer to the fact that thechoice of each agent aﬀects aggregate quantities, such as prices. In the minoritygame [7,8] agents behave as “price takers”, i.e. as if their choices did notaﬀect the aggregate. However, due to the minority nature of the interaction,the market impact reduces the “perceived” performance of strategies whichagents use in the market with respect to those which which are not used andwhose performance is monitored on the basis of a virtual trade (assuming thesame price). In order to analyze in detail this issue, we generalize the MG andallow agents to assign an extra reward
η
to a strategy when it is played. Thisparameter allows agents to account for their market impact and it plays thesame role as the Onsager reaction term, or cavity ﬁeld, in spin glasses[16].Our main results are:(1) We derive a continuum time limit for the dynamics of learning.(2) We show that this dynamics admits for a Lyapunov function, i.e. a function of all relevant dynamical variables which decreases on all trajectoriesof the dynamics. This is a very important result since it turns the problem of studying the stationary state of a stochastic dynamical systeminto that of characterizing the (local) minima of a function. Consider3
ing this function as an Hamiltonian, we can apply the tools of statisticalmechanics to solve the problem.(3) When agents do not consider their impact on the market, as in the minority game (
η
= 0),
i)
the stationary state is unique.
ii)
the Lyapunov function is a measure of the asymmetry of the market. In loose words, agentsminimize market’s predictability.
iii)
When the number of agents exceedsa critical number the market becomes symmetric and unpredictable, withlarge ﬂuctuations as ﬁrst observed in [8].(4) If agents know what is the dependence of the aggregate variable on theirbehavior they can consider their impact on the market. We refer to this asthe
full information
case since agents have full information on how the aggregate would have changed for each of their choices. In this case,
i)
thereare exponentially many stationary states.
ii)
these states are Nash equilibria,
iii)
the Lyapunov function measures market’s ﬂuctuations, whichmeans that agents cooperate optimally in maximizing global wealth whenmaximizing their own utility. As a result, ﬂuctuations always decreasesas the number of agents increase.(5) This state is recovered when
η
= 1. This means that agents need not havefull information in order to reach this optimal state. It is enough that theyoverreward the strategy they are currently playing with respect to thosethey are not playing, by a quantity
η
.(6) Any
η >
0 implies an improvement both in individual payoﬀs – as shownin sect. 8 and in global eﬃciency with respect to the
η
= 0 case.(7) The most striking result comes when asking how does the collective behavior interpolates between the two quite diﬀerent limits when changing
η
from 0 to 1. The result is that when there are few agents the changeis mild and continuous – even though there is a phase transition, thatis a continuous one (second order). When there are many agents thechange happens suddenly and discontinuously as soon as
η >
0. Evenan inﬁnitesimal
η
is enough to reduce market’s ﬂuctuations by a ﬁniteamount.These results suggests that the neglect of market impact – which seems aninnocent approximation
1
and is usually at the very basis of mathematicaleconomy and ﬁnance
2
– plays a very important role in complex systems suchas markets.
1
The impact of each agent on the aggregate is of relative order 1
/N
and it vanishesas
N
→∞
.
2
For example, in determining optimal investment strategies or pricing, it is customary to consider prices as just exogenous processes, independent of the tradingstrategy really adopted.
4
2 The stage game: strategic structure
2.1 Actions and payoﬀs
The minority game describes a situation where a large number
N
of agentshave to make one of two opposite actions – such as e.g. “buy” or “sell” – andonly those agents who choose the minority action are rewarded. This is similarto the El Farol bar problem, where each one of
N
agents may either chooseto go or not to a bar which is enjoyable only when it is not too crowded. Inorder to model this situation, let
N
= (1
,...,N
) be the set of agents and let
A
= (
−
1
,
+1) be the set of the two possible actions. If
a
i
∈A
is the action of agent
i
∈N
, the payoﬀs to agent
i
is given by
u
i
(
a
i
,a
−
i
) =
−
a
i
A
where
A
=
i
∈N
a
i
,
(1)where
a
−
i
=
{
a
j
, j
=
i
}
stands for opponents actions. The game rewards theminority group. To see this, note that the total payoﬀ to agents
i
u
i
=
−
A
2
is always negative. Then the majority of agents, who have
a
i
= sign
A
, receivesa negative payoﬀ
−
A

, whereas the minority “wins” a payoﬀ of

A

. Eq. (1)can be generalized to
u
i
(
a
i
,a
−
i
) =
−
a
i
U
(
A
): if the function
U
(
x
) is such that
xU
(
x
) =
−
xU
(
−
x
)
≥
0 for all
x
∈
IR
, the game again rewards the minority.The srcinal model[6,7] takes
U
(
x
) = sign
x
, but the collective behavior isqualitatively the same [11] as that of the linear case
U
(
x
) =
x
on which wefocus. Note that the “inversion” symmetry
u
i
(
−
a
i
,
−
a
−
i
) =
u
i
(
a
i
,a
−
i
) impliesthat the two actions are
a priori
equivalent: there cannot be any best actions,because otherwise everybody would do that and loose.The key issue, clearly, is that of coordination. With respect to coordinationgames [18, chapt. 6], we remark that agents cannot communicate. If communication were possible, agents would have incentives to stipulate contracts –such as “We toss a coin, if the outcome is head I do
a
me
= +1 and you do
a
you
=
−
1, and if it is tail we do the other way round”. Both players wouldbeneﬁt from this contract because it transforms the negative sum game into azero sum game for the two players. The contract would then be selfenforcing.Agents interact only through a
global
or
aggregate
quantity
A
which is produced by all of them. This type of interaction is typical of market systems [7]ant it is similar to the longrange interaction assumed in meanﬁeld models of statistical physics[16]. Finally note that the El Farol bar problem has a similarstructure but with
A
replaced by (
A
−
A
0
) in Eq. (1) where
A
0
is related tothe bar’s comfort level [1,19].5