MinorityGames This page intentionally left blank Minority Games DAMIEN CHALLET, MATTEO MARSILI, YI-CHENG ZHANG 1 3 GreatClarendonStreet,OxfordOX26DP OxfordUniversityPressisadepartmentoftheUniversityofOxford. ItfurtherstheUniversity’sobjectiveofexcellenceinresearch,scholarship, andeducationbypublishingworldwidein Oxford NewYork Auckland Bangkok BuenosAires CapeTown Chennai DaresSalaam Delhi HongKong Istanbul Karachi Kolkata KualaLumpur Madrid Melbourne MexicoCity Mumbai Nairobi SãoPaulo Shanghai Taipei Tokyo Toronto OxfordisaregisteredtrademarkofOxfordUniversityPress intheUKandincertainothercountries PublishedintheUnitedStates byOxfordUniversityPressInc.,NewYork ©OxfordUniversityPress2005 Themoralrightsoftheauthorhavebeenasserted DatabaserightOxfordUniversityPress(maker) Firstpublished2005 Allrightsreserved.Nopartofthispublicationmaybereproduced, storedinaretrievalsystem,ortransmitted,inanyformorbyanymeans, withoutthepriorpermissioninwritingofOxfordUniversityPress, orasexpresslypermittedbylaw,orundertermsagreedwiththeappropriate reprographicsrightsorganization.Enquiriesconcerningreproduction outsidethescopeoftheaboveshouldbesenttotheRightsDepartment, OxfordUniversityPress,attheaddressabove Youmustnotcirculatethisbookinanyotherbindingorcover andyoumustimposethissameconditiononanyacquirer AcataloguerecordforthistitleisavailablefromtheBritishLibrary LibraryofCongressCataloginginPublicationData (Dataavailable) ISBN 0198566409(hbk) 10 9 8 7 6 5 4 3 2 1 TypesetbyNewgenImagingSystems(P)Ltd.,Chennai,India. PrintedinGreatBritain onacid-freepaperby BiddlesLtd.,King’sLynn Foreword Once in a while a model problem appears that is simple to describe but offers a wealth of lessons. If the model problem is a classic—like the Ising model or the Prisoner’s Dilemma—it both opens up our insight and gives us analytical pathways intoanintriguingworld.Challet,MarsiliandZhang’sMinorityGameproblemissuch amodel.Itisaclassic.Thegameitselfiseasytovisualize.Anumberofagentswishto takesomeparticularaction,buttheydonotbenefitifthemajorityofotherstakeittoo. Thecircumstanceswherethisoccursmayseemtobeveryspecific,butinfacttheyarise everywhere in the economy when agents must commit in advance to something that showsdiminishingreturns.(Diminishingreturns,thatis,tothenumberscommitting). Financialtradesmustbecommittedtoinadvance,andthebenefitsofmanystrategies may be arbitraged away if others use them too. Hence the minority situation arises alsoinfinancialmarkets. Damien Challet andYi-Cheng Zhang conceived of the Minority Game in 1997. They, and their co-worker Matteo Marsili who joined them later, were intrigued not only by the problem itself, but by the possibility of applying statistical mechanics techniques to economics and game theory more generally. Over the previous two decades, physics had become adept at analyzing systems with many particles inter- acting heterogeneously, and markets clearly consisted of such particles—investors. But these economic “particles” reacted by attempting to forecast the outcome that would be caused by the forecasts of other particles, and to react to that in advance. Theywerestrategic.Thiswasarecognizableworldforphysicistsbutanintriguingly different one, and the minority game provided a pathway into it. The problem was quicklytakenupbyotherphysicists.Itsformulationwassimplifiedandprogressively redefined to be closer to what physics was used to dealing with.Versions appeared, results appeared, and advances in understanding appeared. This book chronicles the progress of thought and the considerable insights gained. And it collects the papers thatbecamethemainmilestones. vi Foreword Onedistinctivefeatureofthisworkisitsemphasisonphasesinparameterspace— different qualitative properties of the outcome that obtain under different parameter sets.Delineatingphasesissecondnaturetophysicistsbutnottouseconomists,andwe canlearnmuchfromthispractice.Intheminoritygame,agentsaligntheirstrategiesto theconditionofthemarket:theywanttochoosethestrategythatonaverageminimizes their chance of being in the majority. As a result, strategies co-organize themselves soastominimizecollectivedissatisfaction.Butthiscollectiveresulthastwophases. With few players, the recent history of the game contains some useful information thatstrategiescanexploit.Butoncethenumberofplayerspassesacriticalvalue,all useful information has been used up. The properties of the outcome differ in these tworegimes.Information,infact,iscentraltothesituation.Anditsrolecanbeexpli- citlyobserved:playersactasiftominimizeaHamiltonianthatisitselfameasureof availableinformation.Sotheprocessbyhowinformationgetseatenupbyplayersis madeexplicit,andthisisanotherusefulpathwayintoexploringfinancialmarkets. Becausesomeinformationisleftunexploitediffewplayersareinthemarket,andall informationisusedupasplayersincreasepastacriticalnumber,Challet,Marsiliand Zhangpointoutthatplayersmayenterthemarketuntilthiscriticalnumberisreached. The market will therefore display self-ordered criticality. This is an important con- jecture,andnotjustatheoreticalone.Ittellsusthatspeculativeinvestors—technical traders,atleast—willseekoutthinmarketswherepossibleandavoiddeepones.Mar- kets may therefore hover on the edge of efficiency—a significant insight that can be madeexplicitwiththetechniquesusedhereandonethatisworthfurtherinvestigation. TheMinorityGamegrewoutofmyElFarolbarproblem, andtofillinsomepre- history I should say a few words about that. Legend is indeed correct: in 1988 on ThursdaynightsGalwaymusicianGerryCartyplayedIrishmusicatElFarol,andthe barwasnotpleasantifcrowded.EachweekImulledwhetheritwasworthshowingup, andImulledthatothersalsomulled.Itoccurredtomethatsituationwassomethinglike theforecastingequivalentofprisoner’sdilemma.Fewshowingupwasbest;butitwas ineveryone’sinteresttobeinthatfew.Butmymotivationwasnottofindaforecasting prisoner’sdilemma.Iwasinterestedatthetimeinrationalexpectations(orforecasts) and their meaning for economics. In solving forecasting problems, economics had founditusefultoimaginethateveryonehadthesameforecastingmachineandused it. You could then ask what forecasting machine would lead to agents’actions that would produce aggregate outcomes that on average would validate the machine’s forecasts. This would be the rational expectations solution—the forecasting method that“rational”agentswouldchoose.Asananalyticalstrategythisworked,atleastin the cases studied. But it bothered me. If someone were not smart enough to figure theproperforecasttheywouldskewtheoutcome.Thenforecastsshoulddeviate;then I should deviate. Then others should too, and the situation would unravel. Rational Foreword vii expectationsmayhavebeengoodtheory,butitwasnotgoodscience.IrealizedthatEl Farolmadethisplain.Ifwepostulateda“correct”bar-attendanceforecastingmachine thateveryonecoordinatedon,theiractionswouldcollectivelyinvalidateit.Therefore therecouldbenosuchcorrectmachine.Butifnodeductiveforecastingsolutionwas possible, what should agents in the economy do? The problem was behaviorally ill- defined. And so were most situations involving the future in economics, I realized. Thisfascinatedme. In1992IstrippedtheElFarolsituationtoitsessentialsandprogrammedit.Iwrote theproblemupandpresenteditattheJanuary1994AmericanEconomicAssociation meetings in a session on complexity in the economy chaired by Paul Krugman. The paper was received politely enough, but my discussant was irritated. He pointed out theproblemhadasolutioninmixedNashstrategies:thebar-goerscouldtosscoinsto reachasatisfactoryoutcome.Ihadthoughtofthat,buttomethatmissedthepoint.To me, El Farol was not a problem of how to arrive at a coordinated solution (although the Minority Game very much is). I saw it as a conundrum for economics: How do you proceed analytically when there is no deductive, rational solution? Defining the problem as a game lost this—all games have at least one Nash mixed-strategy equilibrium—soIresistedanygame-theoreticformulation.Mypaperdulyappeared, but economists didn’t quite know what to make of it. My colleague at Santa Fe, Per Bak, did know however. He saw the manuscript and began to fax it to his physics friends. The physics community took it up, and in the hands of Challet, Marsili and Zhang,itinspiredsomethingdifferentthanIexpected—theMinorityGame.ElFarol emphasized (for me) the difficulties of formulating economic behavior in ill-defined problems.TheMinorityGameemphasizessomethingdifferent: theefficiencyofthe solution. This is as should be. The investigation reveals explicitly how strategies co-adapt and how efficiency is related to information. This opens an important door tounderstandingfinancialmarkets. AsIwritethis,therearenowover200papersontheMinorityGame,andagrowing communityofeconophysicistswhohavebecomedeeplyimmersedinthedynamicsof markets—especially financial markets. Economists wonder at times whether all this workinphysicsisnotjustalengthyexerciseinphysicistslearningwhateconomists know. It is certainly not—and indeed this book shows it is not. Modern physics can offermuchtoeconomics.Notjustdifferenttoolsanddifferentmethodsofanalysis,but differentconceptssuchasphasetransitions,criticalvalues,andpowerlaws.Andnot justtheanalysisofpatternatstasis,buttheanalysisofpatternsinformation.Economics needsthis.Infacteconomicsischangingcurrentlyfromanemphasisonequilibrium andhomogeneitytoanemphasisontheformationofpatternandheterogeneity.And so,economicsinduecoursewouldbeforcedtousethekindoftoolsthatarebrought tobearinthisbook.Luckilyphysicsistheretosupplythem. viii Foreword Thepapershereandthetextareanimportantpartofamovement—lookingatthe economy under heterogeneity. Challet, Marsili and Zhang and the others described herehavedonemuchtopowerthismovement, andIcongratulatethemforthis. Itis indeedabenefittophysicistsandeconomiststohavethisworkcollectedinoneplace. W.BrianArthur SantaFe,NewMexico. Preface In the twenty-first century, science seems to be taking on a more interdisciplinary approach.Wallsbetweenthedisciplinesarebecomingporous.Anaturalresultofthis processisthatmanyresearcherswithdifferentbackgroundsfindthemselvesworking on the same subject, each having his own goals and dictionary, each bringing their ownmethods,concepts,andnotations. Financial markets have been a subject on which the interest of many researchers from different disciplines have converged. In the past decade many economists and physicistsalikehavebeenbusilystudyingmarket-relatedphenomena.Thisunpreced- ented surge in interest in understanding the mechanism of financial markets can be attributednotonlytotheirevermoreprominentimpactonsociety,butalsotothenow mucheasieraccesstoverylargequantityofdata. Inthemeantime,physicsisundergoingsomeprofoundchangesaswell:asignificant numberofphysicistspreviouslyworkingontraditionalhardsciencetopicsareshifting their attention to interdisciplinary areas bordering on biology, economics, and other social sciences. The main force behind this outflow is not so much that physicists have lost interest in physics, but the realization that there are incredibly interesting complex phenomena taking place in other disciplines which seem now within reach ofthepowerfultheoreticaltoolswhichhavebeensuccessfulinphysics. Thereisnothingnewaboutphysicistsbeinginterestedineconomicsorotherdiscip- linessuchasbiologyorcomputerscience.Ineconomics,thisisatrendwhichismore than a century old, many first-class economists and several Nobel laureates having a degree in physics in their earlier carrier. What is new is that nowadays physicists studyinginterdisciplinarysubjectsremainphysicistsanddonotbecomeeconomists, biologists, or computer scientists. They are interested in the wonders which such complexsystemsasafinancialmarketoraproteinunveil,andinunderstandingthese systemsfromadifferentperspective. Physicists feel uneasy about the formal mathematical approach used by theor- etical economists. Their view of a financial market may be close to a black box