Spelteori är det standardverktyg som används för att modellera strategiska interaktioner inom evolutionär biologi och samhällsvetenskap. Traditionell spelteori studerar jämvikten i enkla spel. Men är traditionell spelteori tillämplig om spelet är komplicerat, och om inte, vad är? Vi undersöker denna fråga här, definierar ett komplicerat spel som en med många möjliga drag, och därför många möjliga utbetalningar villkorade av dessa drag. Vi undersöker två-personers spel där spelarna lär sig baserat på erfarenhet. Genom att generera spel på måfå visar vi att under vissa omständigheter konvergerar de två spelarnas strategier till fasta poäng, men under andra följer de gränscykler eller kaotiska attraherare. dimension kaotiska attraherare kan vara mycket hög, vilket innebär att dynamiken i strategierna är effektivt slumpmässiga. I den kaotiska regimen fluktuerar utbetalningarna intermittent, visar utbrott av snabba förändringar intermitterade av perioder av quiescence, liknande vad som observeras i flytande turbulens och finansmarknader. Våra resultat tyder på att sådan intermittens är ett mycket generiskt fenomen, och att det finns en stor parameter regim för vilken komplicerade strategiska interaktioner genererar naturligt oförutsägbart beteende som bäst beskrivs i språket för dynamiska systemteori. Traditionell spelteori ger vanligtvis en god förståelse för enkla spel med några få spelare, eller med bara några få möjliga drag, som karakteriserar lösningarna i termer av deras jämvikt [1, 2]. Tillämpningen av detta tillvägagångssätt är inte klar när spelet blir mer komplicerat, till exempel på grund av fler spelare eller ett större strategiutrymme, som kan orsaka en explosion i antalet möjliga jämvikt [3] [4] [5] [6]. Detta är ytterligare komplicerat om spelarna inte är rationella och måste lära sig sina strategier [7] [8] [9] [10] [11]. I ett fåtal särskilda fall har det konstaterats att strategierna uppvisar komplexa dynamiker och inte konvergerar till jämviktslösningar [12] [13] [14]. Är sådana spel speciella, eller är detta typiskt beteende? Mer allmänt, under vilka omständigheter bör vi förvänta oss att spel blir så svåra att lära sig att deras dynamik misslyckas med att konvergera? Vad slags beteende bör vi förvänta oss och hur bör vi karakterisera lösningarna? Som exempel på vad vi menar jämför spelen tic-tac-toe och schack. Tic-tac-toe är ett enkelt spel med endast 765 möjliga positioner och 26, 830 distinkta sekvenser av rörelser. Små barn upptäcker lätt Nash jämvikt, vilket resulterar i en dragning, då spelet blir ointressant. I kontrast, schack är ett komplicerat spel med ungefär 10 47 möjliga positioner och 10 123 möjliga sekvenser av rörelser; trots en enorm ansträngning, Nash jämvikt (motsvarande ett idealiskt spel) förblir okänd. Equilibrium begrepp spelteori är inte användbara för att beskriva komplicerade partier som schack eller gå (som har ett ännu större spel träd med ungefär 10 360 möjliga sekvenser av rörelser). En ex- * Elektronisk adress: tobias.galla@manchester.ac.uk † Elektronisk adress: jdf@santafe.edu gott om som är ännu närmare vad vi har i åtanke här är att investera i finansmarknader, vilket är en icke-noll summa spel där spelare kan välja mellan tusentals tillgångar och en rik uppsättning möjliga strategier. Här visar vi att om spelarna använder en standardstrategi för lärande, för komplicerade spel finns det ett stort parametersystem där man bör förvänta sig komplex dynamik. Med detta menar vi att spelarna aldrig konvergerar till en fast strategi. Istället varierar deras strategier ständigt när varje spelare svarar på tidigare förhållanden och försöker göra bättre än de andra spelarna. Trajectorierna i strategirymden uppvisar högdimensionellt kaos, vilket tyder på att beteendet i de flesta syften och syften i huvudsak är slumpmässigt, och den framtida utvecklingen är i sig oförutsägbar. För att ta itu med de frågor som ställs ovan studerar vi tvåspelarspel. För bekvämlighet ring de två spelarna Alice och Bob. Vid varje gång steg t spelare μ  på {Alice = A, Bob = B} väljer mellan en av N möjliga drag, väljer i th flytta med frekvens x För tydlighet använder vi logaritmisk skala. Som dimensionen av attraheraren ökar, så gör intervallet x μ i. För den högsta dimensionen ett givet drag har tillfälliga sprickor där det är mycket troligt, och långa perioder där det är extremt osannolikt (så lågt som 10 −72 ). tidigare spelas oftare och drag som har varit mindre framgångsrika spelas mindre ofta. För att vara mer specifik, sannolikheten för ett givet drag är där Q μ i kallas attraktionen för spelare i till strategi μ. I det speciella fallet av erfarenhet viktad attraktion som vi använder här, Alice attraktioner uppdateras enligt (2) och på liknande sätt för Bob med A och B utbytte. Dynamiken för att uppdatera strategier x μ av de två spelarna är helt deterministiska. Detta approximerar den situation där spelarna varierar sina strategier långsamt jämfört med den tidsplan på vilken de spelar spelet. De nyckelparametrar som kännetecknar inlärningsstrategin är α och β. Parametern β kallas intensiteten av valet; när β är stor en liten historisk fördel för en given rörelse orsakar som flyttar att vara mycket troligt, och när β = 0 alla rörelser är lika sannolika. Parametern α anger minnet i inlärningen; när α = 1 finns det inget minne av tidigare inlärningssteg, och när α = 0 alla inlärningssteg är ihågkomna och ges samma vikt, oavsett hur långt i det förflutna. Fallet α = 0 motsvarar den mycket studerade replikatordynamik som används för att beskriva evolutionära processer i befolkningsbiologi [15] [16] [17]. Vi väljer spel slumpmässigt genom att dra elementen i payoff matriser Π μ ij från en normal distribution [3] [4] [5] [6] 18]. Medeltalet och kovariansen väljs så att E[Π Variabeln Ε är en avgörande parameter som mäter avvikelsen från ett nollsummespel. När â = −1 spelet är noll summa, dvs. Det belopp Alice vinner är lika med det belopp Bob förlorar, medan när â = 0 deras utbetalningar är okorrelerade. Vi simulerar slumpmässigt konstruerade spel med N = 50 möjliga rörelser, vilket motsvarar ett 98-dimensionellt tillstånd utrymme (det finns två 50 dimensionella strategivektorer och två sannolikhetsbegränsningar). Det beteende som observeras beror på parametrarna. I vissa fall ser vi en stabil inlärningsdynamik, där båda spelarnas strategier x μ konvergerar på en fast punkt. För en stor del av parameterrymden konvergerar emellertid strategierna till en mer komplicerad omloppsbana, antingen en gränscykel eller en kaotisk attraherare. Vi karakteriserar den lokala stabiliteten egenskaper attraherare genom att numeriskt beräkna Lyapunov exponenter λ i, i = 1,..., 2N − 2, som kvantifierar graden av expansion eller sammandragning av närliggande punkter i tillstånd 3 utrymme. Lyapunov exponenter bestämmer också Lyapunov dimension D, som mäter antalet grader av frihet för rörelsen på attraheraren. Vi ger flera exempel på den observerade inlärningsdynamiken vid olika parametervärden i Bild. 1................................................................ Dessa inkluderar en gränscykel och kaotiska attraherare av varierande dimensionalitet. Det kan också finnas långa transienter där banan följer en komplicerad omloppsbana under en lång tid och sedan plötsligt kollapsar in i en fast punkt. I allmänhet beteendet observerade beror på slumpmässiga dragningar av payoff matriser Π μ ij, Men som vi flyttar bort från stabilitetsgränsen, för en given uppsättning parametrar vi observera ganska konsekvent beteende. Simulera spel med många olika parametervärden visar stabilitetsschemat i bild. 2............................................................... Grovt sett finner vi att dynamiken är stabil [19] när â -1 (nollsummespel) och α är stor (kort minne), dvs.. i den nedre högra delen av diagrammet, och instabil när okorrelerad vinst) och α är liten (långt minne), d.v.s. längst upp till vänster. Intressant, av skäl som vi inte förstår den högsta dimensionen beteende observeras när payoffs är måttligt anti-korrelelated (ρ  och -0.6) och när spelare har lång-minne (α  på 0). För att göra problemet analytiskt dragbart har vi gjort specifika val i parametrarna för erfarenhet viktad attraktion (EWA). Jämförelse med beteendeexperiment modellerade med EWA som rapporterats i [7] visar att den särskilda form vi använder här är ungefär inom det intervall som observerats i verkliga experiment. Värden för parametrar för minnesförlust och intensitet av val som rapporterats från experiment tyder på att det verkliga beslutsfattandet mycket väl kan fungera nära eller i den kaotiska fasen (se Kompletterande information). De flesta experimentella data är dock begränsade till lågdimensionella spel, medan vi här studerar spel med ett stort antal möjliga drag. Ett bra exempel där högdimensionellt kaotiskt beteende sannolikt är på finansmarknaderna, där det finns ett stort antal möjliga rörelser och inlärningstider mäts i år. Högdimensionellt kaotiskt beteende kan effektivt vara oskiljbart från buller. En god approximation av gränsen mellan de stabila och instabila regionerna i parameterutrymmet kan beräknas analytiskt med hjälp av tekniker från statistisk fysik. Vi använder path-integral metoder från teorin om oordnade system [5, 20] för att beräkna stabiliteten i gränsen för oändliga payoff matriser, N → ∞. Vi gör detta i en kontinuerlig-tidsfrist där, för fast â, stabilitet då beror endast på förhållandet α/β (se Kompletterande information). Vi har simulerat spel för olika värden av N. Om D > 0 vid små N, dimension D tenderar att öka med N. I detta skede har vi inte kunnat avgöra om D når en ändlig gräns eller växer utan bindning som N → ∞. En intressant egenskap hos detta system är tidsberoendet av de mottagna utbetalningarna. Som visas i bild. 3, När dynamiken är kaotiska den totala payoff till alla spelare varierar, med intermittenta sprickbildningar av stora fluktua- Den solida linjen är den stabilitet gräns uppskattas med hjälp av väg-integral metoder. De färgade rutorna är från simuleringar av inlärningsdynamiken och representerar den typiska dimensionen av attraheraren (i genomsnitt över 10 eller fler oberoende payoffmatriser per datapunkt).
För två spelare spel med ett stort antal tillgängliga strategier (komplicerade spel), Galla och Farmer REF hävdar att erfarna viktade attraktion (EWA) lärande, en beteendeekonomi modell av lärande dynamik, uppvisar också kaotiska beteenden i en stor parameter utrymme.
Complex dynamics in learning complicated games
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Medicine', 'Mathematics', 'Physics', 'Computer Science']}