Games & Puzzles

Exact solution of a modified El Farol's bar problem: Efficiency and the role of market impact

Exact solution of a modified El Farol's bar problem: Efficiency and the role of market impact
of 38
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
    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 modified El Farol’s barproblem: Efficiency and the role of marketimpact Matteo Marsili Istituto Nazionale per la Fisica della Materia (INFM), Trieste-SISSA Unit,V. Beirut 2-4, Trieste I-34014 Damien Challet Institut de Physique Th´eorique, Universit´e de Fribourg, CH-1700  and Riccardo Zecchina The Abdus Salam International Centre for Theoretical Physics Strada Costiera 11,P.O. Box 586, I-34014 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 fixed by all of them. Agents follow a simple reinforcement-learning dynamicswhere the reinforcement, for each of their available strategies, is related to thepayoff delivered by that strategy. We derive the exact solution of the model in the“thermodynamic” limit of infinitely 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 “infinitesimally” for this dependence they can, in a whole range of parameters, reduce global fluctuations by a finite amount. Both global efficiencyand 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 profited greatly from critical discussions withA. Rustichini and F. Vega-Redondo on learning and dynamic games. This work waspartially supported by Swiss National Science Foundation Grant Nr 20-46918.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 first step in this direction. It indeed de-scribes a system of interacting agents with inductive rationality which face theproblem of finding 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 infinitelymany 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 easydefinition in words. This may be enough for setting up a computer code to runnumerical simulations, but it is clearly insufficient for an analytical approach.Therefore we shall, in the next section, define carefully its mathematical for-mulation. We shall only discuss briefly 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 financial markets (see sect.2.4), still we find 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 reflects our taste and surely more work needs to be doneto show the relation of the minority game with real financial markets. We be-2  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 inter-acting through a global quantity  via   a minority mechanism, such as markets.The minority game indeed captures the essential interaction between agentsbeliefs and market fluctuations – how individual beliefs, processing fluctua-tions, produce fluctuations in their turn. This interaction is usually shortcutin mathematical economy assuming market efficiency, i.e. that prices  instanta-neously   react to and incorporate agents beliefs. The motivation underlying theefficient market hypothesis, is, in few words that if there where inefficiencies – or arbitrage opportunities – that would be exploited by speculators in themarket and washed out very quickly. Implicitly one is assuming that there isan infinite 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 finite num-ber of heterogeneous agents interact in a complex system such as a market.It allows to ask to what extent this “stylized” market is inefficient and howagents really exploit arbitrage opportunities and to what extent.After defining the stage game, we shall briefly 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 difference between agents playing a Nash equilibrium andagents in the usual minority game is  not   that the first 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 affects aggregate quantities, such as prices. In the minoritygame [7,8] agents behave as “price takers”, i.e. as if their choices did notaffect 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 field, 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 func-tion of all relevant dynamical variables which decreases on all trajectoriesof the dynamics. This is a very important result since it turns the prob-lem of studying the stationary state of a stochastic dynamical systeminto that of characterizing the (local) minima of a function. Consider-3  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 minor-ity game ( η  = 0),  i)  the stationary state is unique.  ii)  the Lyapunov func-tion 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 fluctuations as first 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 ag-gregate would have changed for each of their choices. In this case,  i)  thereare exponentially many stationary states.  ii)  these states are Nash equi-libria,  iii)  the Lyapunov function measures market’s fluctuations, whichmeans that agents cooperate optimally in maximizing global wealth whenmaximizing their own utility. As a result, fluctuations 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 theyover-reward 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 payoffs – as shownin sect. 8 and in global efficiency with respect to the  η  = 0 case.(7) The most striking result comes when asking how does the collective be-havior interpolates between the two quite different 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 infinitesimal  η  is enough to reduce market’s fluctuations by a finiteamount.These results suggests that the neglect of market impact – which seems aninnocent approximation 1 and is usually at the very basis of mathematicaleconomy and finance 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 cus-tomary to consider prices as just exogenous processes, independent of the tradingstrategy really adopted. 4  2 The stage game: strategic structure 2.1 Actions and payoffs  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 payoffs 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 payoff to agents   i  u i  = − A 2 is always negative. Then the majority of agents, who have  a i  = sign A , receivesa negative payoff   −| A | , whereas the minority “wins” a payoff 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 commu-nication 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 wouldbenefit from this contract because it transforms the negative sum game into azero sum game for the two players. The contract would then be self-enforcing.Agents interact only through a  global   or  aggregate   quantity  A  which is pro-duced by all of them. This type of interaction is typical of market systems [7]ant it is similar to the long-range interaction assumed in mean-field 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


Apr 29, 2018
Similar documents
View more...
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!