Vi visar att evolutionärt stabila tillstånd i allmänhet (icke-linjära) populationsspel (som kan ses som kontinuerliga vektorfält som begränsas av en polytop) är asymptotiskt stabila under en multiplikativ vikt dynamisk (under lämpliga val av en parameter som kallas inlärningshastighet eller stegstorlek, som vi visar att vara avgörande för att uppnå konvergens, eftersom annars även kaotiskt beteende är möjligt att manifestera). Vårt resultat innebär att evolutionära teorier baserade på multiplikativa vikter är förenliga (i princip mer generella) med dem som bygger på begreppet evolutionär stabilitet. Vårt resultat etablerar dock ytterligare multiplikativa vikter som en icke-linjär programmerings primitiv (jämfört med vanliga ickelinjära programmeringsmetoder) eftersom olika icke-linjära optimeringsproblem, såsom att hitta Nash/Wardrop equilibria i icke-atomiska trängselspel, som är välkända för att vara utrustade med en konvex potentiell funktion, och att hitta strikt lokal maxima av quadratic programmeringsproblem, är specialfall av problemet med datorutvecklingsstabila tillstånd i ickelinjära populationsspel. Motiveringen till denna uppsats har sitt ursprung i inlärningsteorin på nätet. Ett av problemen i inlärningsteorin är hur algoritmer klarar sig i en kontradiktorisk miljö. Prestanda fångas av en algoritms ånger, som, med tanke på en uppsättning möjliga åtgärder, är skillnaden mellan kostnaden för algoritmen och kostnaden för den bästa åtgärden i efterhand. Hedge Schapire, 1997, 1999], till exempel, en välkänd online lärande algoritm som har hittat tillämpningar i en mängd olika praktiska inställningar, är en multiplikativ-vikter algoritm för dynamiskt tilldela ett belopp till en uppsättning alternativ över en sekvens av steg som generaliserar viktad majoritet algoritm av Littlestone och Warmuth [1994]. Freund och Schapire visar att genom att justera en parameter av algoritmen, kallas inlärningshastigheten, algoritmen anpassar sig väl till ett kontradiktoriskt mönster av kostnader i att ångra försvinner med antalet steg. Tänk om mönstret inte är motsträvigt? I den här artikeln studerar vi hur multiplikativa viktalgoritmer (t.ex. Hedge) klarar sig i evolutionära miljöer som är allmänna nog att till och med fånga föreställningar om icke-linjär optimering. (Våra resultat kommer att visa att multiplikativa vikter inte bara kan beräkna "evolutionärt stabila tillstånd" utan kan också fungera som icke-linjär programmering primitiv.) Den arketypiska evolutionsmiljön, som ursprungligen introducerades av Darwin, eftersom den matematiskt formaliseras med hjälp av (evolutionär) spelteori, är ganska allmän: Darwins evolutionsteori har haft en djupgående inverkan inte bara inom biologin utan också inom samhällsvetenskap och ekonomi i ett brett spektrum av modellering miljöer inom dessa discipliner. Det finns två distinkta metoder med vilka evolutionsteorier kan närma sig analytiskt. Den första är genom föreställningar om evolutionär stabilitet och den andra genom föreställningar om evolutionär dynamik. I denna uppsats för vi dessa föreställningar närmare varandra genom att betrakta det dynamiska beteendet hos en (diskret-tid) multiplikativ viktdynamik, vilket är mycket relevant för den välkända i evolutionsteorin (kontinuerlig-tid) replikatordynamiken, i grannskapet av ett "evolutionärt stabilt tillstånd". Låt oss emellertid diskutera dessa begrepp mer formellt. ArXiv:1601.07267v2 [cs.GT] 1 Feb 2016 En av de riktmärkesmodellering metoder matematiska biologer och ekonomer är den evolutionärt stabila strategi (ESS), som infördes av Maynard Smith och Price [1973] för att modellera populationsstater stabila under evolutionära krafter. Maynard Smith [1982] (informellt) definierar ett ESS som "strategi sådan att, om alla medlemmar av en befolkning antar det, ingen mutant strategi kan invadera befolkningen under inflytande av naturligt urval." Maynard Smith och Price [1973] anser att en strategi är ett ESS om den genetiska lämplighet som den ger befolkningen är större än den lämplighet som varje mutant strategi med tillräckligt liten befolkningsmassa ger. Tänk på en oändlig population av organismer som samverkar i par. Varje organism är genetiskt programmerad att agera enligt ett visst beteende (eller strategi) i parvisa interaktioner. Resultatet av interaktionen påverkar organismernas biologiska lämplighet, mätt som antalet avkomma de kan bära. Låta = {1,..., n} vara den, gemensam för båda spelarna, uppsättning möjliga rena beteenden (strategier) och anta att ett par organismer träffas så att en använder strategi i  på och den andra använder j  på. Låt en ij vara payoff (gain i kondition) till den första organismen och låt b ij vara payoff till den andra på grund av interaktionen. Ett vanligt antagande är att utdelningarna är oberoende av spelarens position så att b ij = a ji. Då kan vi representera utdelningarna för alla möjliga interaktioner som en n × n matris C = [c ij ]. I allmänhet kan organismer använda blandade strategier. Därefter den förväntade vinsten i kondition av en organism som använder blandad strategi X mot en organism som använder Y är X · CY. Med denna bakgrund i åtanke, låt oss göra det tidigare uttalandet formellt. Betrakta en dominerande population av enhet massa där alla organismer använder beteende X * och anta att en mutation uppstår så att en - brott av organismerna växla till Y. Låt Y = (1 − )X * + Y vara det genomsnittliga beteendet i den blandade populationen. Då den förväntade lämpligheten hos de etablerade är X * · CY och den av mutanterna är Y · CY. Den dominerande strategin, X *, kallas en ESS om för alla sådana Y och för alla tillräckligt liten den förväntade lämpligheten hos de etablerade är högre än den förväntade lämpligheten hos mutanterna, dvs X · CY > Y · CY. Intuitivt är ett ESS ett beteende som är "framgångsrikt" mot alla möjliga mutationer av tillräckligt liten storlek. Men det finns alternativa vinklar där man kan närma sig evolutionär stabilitet. I den ursprungliga definitionen anges till exempel att X * · CX * ≥ X · CX *,  och X * och X * · CX * = X · CX *  på X * · CX > X · CX på CX, X på ett sådant sätt att X = X *, där X är utrymmet för blandade strategier. För att förstå denna definition, betrakta en bimorfisk population nästan alla vars medlemmar (säg en 1 - fraktion) är X * - strateger medan de återstående medlemmarna (fraktionen) är X- strateger. Sedan konditionen hos de etablerade (X * - strategerna) är (1 − )X * · CX * + X * · CX medan lämpligheten hos mutanterna (X- strategerna) är (1 − )X · CX * + X · CX. Eftersom det är mycket litet, som kräver att de etablerade företagen är bättre än mutanternas, ger villkoren i definitionen. En annan karakterisering av ESS, en som är analytiskt behändig och som direkt kopplar begreppet evolutionär stabilitet till mer abstrakta föreställningar inom matematiken i förhållande till den variationella ojämlikhetslitteraturen, har tillhandahållits av Hofbauer et al. [1979]................................................................ Denna senare karakterisering anger att en strategi X *  på X är en ESS om den är lokalt överlägsen (jfr. [Weibull, 1995] ), nämligen, om det finns ett område O av X * sådan att X * · CX > X · CX för alla X = X * i O. De tidigare definitionerna generaliseras till mer allmänna inställningar där utdelningar är icke-linjära så kallade populationsspel (jfr. Detta beslut riktar sig till Konungariket Spanien. Populationsspel är vektorfält som begränsas av en simplex, eller, mer allmänt, på en Cartesian produkt av simplex, varje simplex motsvarar en population. Vi betecknar detta utrymme av möjliga tillstånd av X och vektorfältet av F : X → R m, 2 X R m. I denna inställning, payoff av X X mot Y X är X · F (Y ). X * X är ett ESS om det finns ett område O av X * sådan att för alla X O vi har att (X * - X) · F (X) > 0. En välkänd klass av befolkning spel, populär i datavetenskap litteratur av arbetet i Roughgarden och Tardos [2002] på priset för anarki [Koutsoupias och Papadimitriou, 2009], är klassen av ickeatomiska trängsel spel. Hofbauer och Sandholm [2009] visar att Wardrop Equilibria, som Nash Equilibria i icke-atomiska trängsel spel också kallas, är, under milda antaganden, globalt stabil i att grannskapet O (där Nash Equilibria är överlägsen enligt den ovan nämnda definitionen) motsvarar hela statsrymden X. Det är värt att notera att icke-atomiska trängselspel medger en potentiell funktion, som enligt samma milda antaganden som ger upphov till förekomsten av en (global) ESS, är strikt konvex. Den tidigare iakttagelsen att den stationära punkten för en strikt konvex potentiell funktion i icke-atomiska trängselspel är ett ESS tyder på ett nära samband mellan begreppet evolutionär stabilitet och ett strikt lokalt maximum i icke-linjär optimeringsteori. Ett annat exempel där sådana begrepp sammanfaller är klassen av dubbelt symmetriska bimatrixspel, det vill säga symmetriska bimatrixspel (C, C T ) där payoff-matrisen C är symmetrisk (C = C T ). I denna spelklass visar Hofbauer och Sigmund [1988] att begreppet ESS sammanfaller med begreppet strikt lokalt maximum av det fyrfaldiga programmeringsproblemet där S är motsvarande symmetriska payoff-matris och X är det dubbla av blandade strategier i det dubbla symmetriska bimatrixspelet (S, S). Bomze [1998] hänvisar till program av denna form som standard quadratic programmering problem; Bomze et al. [2008] visar att det allmänna quadratic programmering problemet över en polytop kan kastas som en standard quadratic program. Ett annat riktmärke för modellering av evolutionära teoretiker är den evolutionära dynamiken. Sandholm [2010] anser till exempel att evolutionär spelteori är studiet av "en stor populations beteende hos strategiskt interagerande agenter som ibland omvärderar sina val mot bakgrund av aktuella vinstmöjligheter". Ett exempel på en evolutionär dynamik är replikatordynamiken hos Taylor och Jonker [1978], som föreslogs kort efter införandet av ESS. I ett symmetriskt bimatrix spel vars payoff matris är C replikator dynamisk är differentialen equatio och där n är antalet rena strategier. Observera att sannolikheten (befolkning) massa strategier som går bättre än genomsnittet ökar medan sannolikheten massa strategier som går sämre än genomsnittet minskar. Replikatorn dynamisk generaliserar på ett naturligt sätt till befolkning spel med icke-linjära utbetalningar. Begreppet dynamik är i sig besläktat med begreppet algoritm. Till exempel är replikatordynamiken och dess diskreta motsvarighet nära relaterad till den viktade majoritetsalgoritmen för Littlestone och Warmuth [1994]. Nyligen var denna algoritm på ett ganska starkt sätt knuten till Darwins evolutionsteori: Chastain et al. [2014] ser evolutionen som ett "samordningsspel" (dvs. ett potentiellt spel som i litteraturen också kallas ett partnerskapsspel) löst med en multiplikativ viktalgoritm (jfr. (Arora et al., 2012)............................................................................................................. 3 I detta dokument anser vi en (diskret tid) multiplikativ vikt dynamik som liknar Hedge Schapire, 1997, 1999] och en modell för evolution som fortskrider i rundor. I inställningen av symmetriska bimatrix spel (dvs linjär en-befolkning spel), i varje omgång, den multiplikativa vikter dynamisk väljer en, allmänt blandad, strategi i en symmetrisk bimatrix spel vars payoff matris är, till exempel C, då utdelningar av enskilda rena strategier bestäms enligt C, och den dynamiska förstärker befolkningen (sannolikhet) massa på rena strategier som klarade sig bra i den föregående omgången. Formellt, denna process kännetecknas av kartan M W : X → X där X är utrymmet för blandade strategier för den symmetriska bimatrix spel (C, C T ) (en simplex), E i är en sannolikhet vektor vars massa är koncentrerad i position i, n är antalet rena strategier, och α > 0 är en parameter som vi kallar inlärningshastigheten eller stegstorleken. Vi noterar att tidigare ekvation (vanligtvis känd som den diskreta tiden replikator dynamik) visas i en preliminär form i [Taylor och Jonker, 1978] och senare studeras av Thomas och Pohley [1982] och Nachbar [1990]. Ur ett matematiskt biologiperspektiv, (2) kan ses som en modell för asexuell reproduktion i en art där generationer inte överlappar (till exempel, se [Maynard Smith, 1982, Weibull, 1995 för en härledning av (2) i denna miljö). Denna modell är således mer elementär än den modell för evolution genom sexuell reproduktion som föreskrivs av Chastain et al. [2014] (och ytterligare utforskas av Mehta et al. [2015]) där den multiplikativa uppdateringsregeln tillämpas i varje spelarposition, är det dock också på något sätt mer allmänt, eftersom vi antar en allmän payoff-struktur snarare än den mer specifika payoff-strukturen i ett partnerskap (dubbelt symmetriskt) spel. Beroende på sammanhang kan multiplikativa vikter dynamiska (2) anta liknande formaliseringar, erkänna tolkningar ganska olikartade från dem i biologi. För att ytterligare motivera vår diskreta evolutionsregel (vis-á-vis dess kontinuerliga, mer omfattande, motsvarighet), låt oss till exempel betrakta modellen för icke-atomiska trängselspel, som också är mer allmänt känd i datavetenskaplig litteratur som självisk routing. Själviska routing spel äger rum på en riktad graf vars bågar motsvarar överbelastade resurser, till exempel vägar i ett transportnät eller kommunikationslänkar i ett datornät, och vars hörn motsvarar antingen skärningspunkter, i det förra fallet, eller routers, i det senare. En viktig fråga, som är inriktad på kommunikationsnät som Internet, är hur man kan fördela nätverkstrafiken från källor till destinationer längs nätvägar. I denna inställning, multiplikativa vikter kan fungera som en primitiv för en routing uppdatering beslut regel i intresse av last balansera trafik för att minska kommunikationsförseningar. Sådana beslut revideras genom formgivning i diskreta steg, och därför är diskret dynamik mer naturlig än deras kontinuerliga motsvarigheter. Med denna tillämpning i åtanke, uppstår följande fråga naturligt: Kommer adaptiva routing beslut konvergera till jämvikt för att undvika de dåliga prestanda som vanligtvis förknippas med oförutsägbara oscillerande beteende? Svaret, inte förvånande, beror på hur stegstorleken väljs. Fokusering uppmärksamhet på steg storlek regel, vår huvudfråga i detta papper är: Med tanke på en befolkning spel F : X → R m, där X är i allmänhet en simplotope (det vill säga en polytope som är en cartesian produkt av simplexes), och en ESS, säger X *, i detta spel, är X * asymptotiskt stabil under en motsvarande formalisering av (2) i denna mer allmänna inställning och under vilka omständigheter? Det finns två allmänna skilda tillvägagångssätt som kan användas för att besvara en sådan fråga. Den första metoden innebär en linearisering av motsvarande dynamiska system i grannskapet av jämvikten (ESS) och studien av eigenvärden av den resulterande jakobiska matrisen; om alla eigenvärden av denna matris är inne i enheten disk, asymptotic stabilitet följer medan om minst 4 ett eigenvärde är utanför enheten disk, systemet är instabil. Att påvisa asymptotisk stabilitet med denna metod har fördelen att en geometrisk konvergenshastighet (nära jämvikten) är omedelbart underförstådd, men det finns två betydande nackdelar, nämligen att om minst ett eigenvärde finns på enhetscirkeln, är testet ofullständigt (under förutsättning att de återstående eigenvärdena finns inom enhetscirkeln), och dessutom är denna metod ofta analytiskt oåtkomlig, särskilt när den formel som beskriver det dynamiska systemets utveckling blir mer allmän. Den andra, mer kreativ, metoden innebär att hitta en lämplig Lyapunov-funktion, som har den fördelen att det i princip är lättare att bevisa globala asymptotiska stabilitetsresultat med hjälp av denna metod. Innan vi beskriver våra bidrag anser vi att några observationer är i sin ordning: Den föregående frågan har besvarats ganska utförligt med avseende på den kontinuerliga replikatordynamiken: Varje ESS i ett allmänt ickelinjärt kontinuerligt populationsspel är asymptotiskt stabil under replikatordynamiken (genom ett argument som är jämförbart med det som används i samband med stabila spel, som är populationsspel som kännetecknas av en monotonitets egenskap som generaliserar begreppet konvexitet från skalära funktioner till vektorfält, med hjälp av den relativa entropin som en Lyapunov-funktion), men den linjära stabiliteten i ett ESS kräver en viss regelbundenhet (nämligen att ESS är en kvasistrikt jämvikt; se [Sandholm, 2010] ). Att upprätta linjär stabilitet utan ett sådant regelbundenhetsvillkor skulle ha den oväntade innebörden att P = NP: I dubbelt symmetriska bimatrixspel sammanfaller ESS med begreppet asymptotisk stabilitet under replikatordynamiken Hofbauer och Sigmund [1988]. Eftersom den linjära stabiliteten hos en vilopunkt kan kontrolleras i polynom tid och eftersom problemet med att känna igen en ESS, även i dubbelt symmetriska bimatrix spel, är coNP-fullständig [Etessami och Lochbihler, 2008, Nisan, 2006], 1 ovan nämnda oväntade resultat skulle följa. I den här tidningen visar vi att om inte stegstorleken noga väljs kan evolutionsregler som använder multiplikativa vikter resultera i kaotiskt beteende även i enkla befolkningsspel. Vårt huvudsakliga resultat är att ett ESS i ett allmänt kontinuerligt populationsspel är asymptotiskt stabilt under den diskreta tidsreplikatordynamiken (för lämpliga val av stegstorleksregeln) med hjälp av ett Lyapunov-funktionsargument baserat på den relativa entropin. Vårt bevis är konstruktivt genom att vi tillhandahåller en uttrycklig regel som uppnår detta mål, och ytterligare notera att analysen är betydligt mer involverad i att det kontinuerliga tidsfallet eftersom vi inte kan förlita oss på den analytiskt behändiga formeln för derivatan av den relativa entropin utan i stället åberopa Kantorovitjs ojämlikhet. Ojämlikheten i Kantorovitj är i viss mån ett välkänt verktyg i analysen av ickelinjära optimeringsproblem, och den motiverades i själva verket av analytiska insatser relaterade till linjär programmering (den används också i konvergensanalysen av gradientbaserade ickelinjära programmeringsalgoritmer för att begränsa konvergenskvoten). Befolkningsspel generaliserar dock icke-linjära programmeringsproblem för att ställa in vektorfält. Observera att alla olika icke-linjära optimeringsproblem kan representeras som ett vektorfält genom att ta lutningen av den objektiva funktionen, men vektorfält fångar mer allmänna modellering miljöer. Ojämlikheten i Kantorovitj i sig räcker för att bevisa asymptotisk stabilitet i ett ESS förutsatt att vi kan använda ESS själv i regeln för att välja en stegstorlek från iteration till iteration. Även om vi motiverar miljöer där ett sådant antagande är rimligt, skulle vår analys kanske inte vara fullständig om inte en stegstorleksregel som är oberoende av målstaten gavs. För att konstruera en sådan regel bevisar vi ytterligare två lemmas, en som visar (remarkable, vi tror) 1 Vi noterar i förbigående att problemet med att känna igen en ESS i (allmänna) symmetriska bimatrix spel är välkänt för att vara coNP-komplett, men att problemet fortfarande coNP-komplett även i dubbelt symmetriska bimatrix spel, kan härledas genom att noggrant överväga bevis i Nisan [2006] derivatation. egenskap diskret-tid replikator dynamisk att, genom att tillämpa denna dynamik på någon population tillstånd X som inte är en fast punkt, vi får en annan stateX som är ett bättre svar på X än X är för sig själv för alla värden av stegstorlek, och den andra lemma visar att, förutsatt att en liten tillräckligt steg storlek, målet ESS X * är ett bättre svar på X än X är till X i ett område av X *. Ett ytterligare bidrag av detta papper är att konstruera ett rigoröst fall att multiplikativa vikter mycket väl kan fungera som en optimering primitiv: Även om den möjliga tillämpningen av multiplikativa vikter i icke-linjär optimering har diskuterats i litteraturen [Arora et al., 2012], i den utsträckning vi vet, är detta det första papper som underbygger detta påstående med en rigorös analys. I denna anda diskuterar vi också analoger av begreppet ESS för att optimera teorin att utnyttja arbetet med Minty variationell ojämlikhet, en ganska allmän ram i ren matematik, vars formalisering starkt relaterar till formaliseringen av ESS i befolkning spel. Våra resultat visar inte bara trovärdigheten av multiplikativa viktuppdateringar som en modelleringsmetod i evolutionära miljöer, men på grund av ovanstående observationer att vissa klasser av befolkning spel (såsom trängselspel och dubbelt symmetriska spel) tillåter potentiella funktioner, visar att sådana uppdateringar kan mycket väl fungera som en icke-linjär programmering primitivt möjligt i par med lutning uppstigning / descent och Newton metoder, till exempel. Vikten av det huvudsakliga analytiska tillvägagångssätt som beaktas i detta dokument baserat på Lyapunov funktioner argumenteras av en linjär stabilitetsanalys som vi utför för en särskild typ av population spel vid fastställande av ickeatomisk trängsel spel, där det visas att stabilitetsanalys baserad på linjärisering snabbt blir analytiskt intractable i (diskrete) inställning som vi anser. Det viktigaste tidigare resultatet vi använder i vår (långt ifrån triviala) bevis i denna speciella inställning (som bygger på metoder från matrisanalys) är Perron-Frobenious teorem. Vi noterar att Weissing [1991] nämner att en interiör ESS är globalt asymptotiskt stabil under den diskreta tidsreplikatordynamiken för en tillräckligt liten stegstorlek, men han publicerade aldrig ett bevis på sitt påstående. 2 Våra resultat, som diskuteras i detalj i uppföljaren, innebär (inre) global asymptotisk stabilitet i en interiör ESS under denna dynamik, men vi kunde inte visa att en sådan implikation håller om stegstorleken förblir konstant från iteration till iteration. Slutligen, mot slutet av denna uppsats, ger vi en intuitiv tolkning av begreppet evolutionär stabilitet (att ovannämnda Lyapunov stabilitet resulterar i ett starkt samband med multiplikativ viktdynamik) i utformningen av Internetarkitektur, i synnerhet när det gäller de evolutionära egenskaperna hos routing protokoll (även om utvidga vår analys till mer allmänna inställningar är säkert tänkbart). Eftersom evolutionär stabilitet, som diskuterats tidigare, vanligtvis motiveras av den biologiska utvecklingen, anser vi att vi på detta sätt gör ett påstående om att föreställningar om evolutionär stabilitet, och därmed också om multiplikativ viktdynamik, kommer att spela en betydande roll i förståelsen av arkitektoniska fenomen på Internet för att underlätta bättre, stabilare och mer robusta metoder för nätverksdesign. Klassen av befolkning spel som kallas ickeatomiska trängsel spel, även ibland kallas en självisk routing spel, som nämnts tidigare, har fått stor uppmärksamhet i den teoretiska datavetenskap litteratur. Dessa spel har den utmärkande egenskap som, som diskuterats mer i detalj senare, de är utrustade med en konvex potential funktion, därför, vilket motsvarar en mycket restriktiv inställning av det allmänna problem som vi anser i detta dokument (även om en del av vår analys, stärka våra mer allmänna argument, äger rum i denna miljö). Det finns två distinkta metoder som har använts i litteraturen i analysen av dynamisk utveckling i själviska routing spel, nämligen att antingen överväga kontinuerlig tid evolution 2 Vi vill tacka en anonym recensent för att påpeka detta faktum. 6 regler eller direkt analysera deras diskreta motsvarigheter. Fischer och Voecking [2004] visar, i ett av de tidigaste verken inom detta område, att Nash equilibria av själviska routing spel (även ibland kallas Wardrop equilibria) är asymptotiskt stabila under kontinuerlig tid replikator dynamik, vilket är starkt relaterat, som diskuterats tidigare, till multiplikativa vikt uppdateringar. Dock kan routing vara mer lämpligt modellerad efter diskreta regler för evolution som routing uppdateringar naturligtvis sker i diskreta steg snarare än på ett kontinuerligt sätt. Även om härleda differentialekvationer från parametriska diskreta tidsutvecklingsregler (genom att ta derivatan och låta parametern närma sig noll) och studera istället differentialekvationen är en metod som ofta används i litteraturen (till exempel, en sådan metod används i [Kleinberg et al., 2009] i studien av multiplikativa vikter i atomära trängselspel), finns det inga allmänna resultat som direkt binder beteendet hos det kontinuerliga systemet till det diskreta från vilket det härleds. Den senare frågan är relaterad till den betydande mängden arbete i evolutionär spelteori ägnas åt studier av kontinuerligt-tids evolutionsregler (till exempel, bygger på begreppet översyn protokoll, det vill säga enkla regler som icke-atomiska agenter i en befolkning kan använda för att revidera sina strategier enligt utdelningar som det kollektiva resultatet av strategiska beslut ger). Eftersom en mängd olika fenomen i naturen och i datorsystem (t.ex. Internet) kan modelleras på ett lämpligare sätt efter diskreta evolutionsregler (på grund av den diskreta karaktären hos t.ex. datorsystem), anser vi att det är värt att överväga att se över det arbete som utförts i den evolutionära spelteorilitteraturen (med hjälp av den algoritmiska linsen) och istället studera diskreta motsvarigheter till kontinuerliga evolutionsregler, som vi gör i den här tidningen. Diskreta utvecklingsregler relaterade till multiplikativa vikter (och online lärande primitiva) har också beaktats, till exempel av Fischer et al. Men [2010] sådana utvecklingsregler skräddarsys genom design för att uppnå goda resultat i självisk routing. Vår analys visar att multiplikativa vikter mycket väl kan fungera som en primitiv anpassning i en mängd olika miljöer (ett argument som intuitivt motsvarar den framgång som multiplikativa vikter-baserade öka algoritmer i maskininlärning teori, såsom AdaBoost, har mött praktiska tillämpningar). I Avsnitt 2, vi börjar med preliminärer, i synnerhet, diskuterar vi symmetriska bimatrix spel, den ram på vilken mycket av teorin om evolutionär stabilitet har baserats, men vi presenterar också generaliseringar av evolutionära stabilitetsbegrepp i den allmänna inställningen av befolkning spel (nära relaterat till den abstrakta variationen ojämlikhet formalisering). Vi introducerar vidare den allmänna formen av multiplikativa vikter dynamisk samt specialfallet av diskret-tid replikator dynamisk (som erhålls som steg storlek närmar sig noll). I Avsnitt 3 visar vi att en ESS är asymptotiskt stabil under den diskreta tidsreplikatordynamiken i symmetriska bimatrixspel. Detta bevis generaliseras i Avsnitt 4 i inställningen av allmänna (icke-linjära) befolkning spel. I avsnitt 5 behandlas frågan om hur evolutionär stabilitet, i sin allmänna definition i icke-linjära populationsspel, avser begreppet strikt lokal optimal i icke-linjär programmering och ger en tolkning av den diskreta tidsreplikatordynamiken som en form av gradient. Avsnitt 6 behandlar en viss klass av befolkning spel, nämligen den välkända i datavetenskap litteratur klass av själviska routing spel, där möjligheten av kaotiskt beteende visas, och en geometrisk takt av konvergens bevisas i ett enkelt specialfall av självisk routing problem. I samma avsnitt ger vi tillräcklig motivation för begreppet evolutionär stabilitet i en miljö som motiveras av routing på Internet och begreppet "inkrementell utplaceringsförmåga", en term som har sitt ursprung i nätverkslitteraturen. Slutligen avslutar vi dokumentet i avsnitt 7. ESS, som det ursprungligen definierades Pris, 1973, Maynard Smith, 1982, är en förfining av den symmetriska Nash-jämvikten i symmetriska bimatrisspel. Låt oss därför börja med att införa spelteoretiska begrepp i samband med bimatrixspel. Ett spel med 2 spelare (bimatrix) i normal form anges av ett par n × m matriser A och B, det förra som motsvarar radspelaren och det senare till kolumnspelaren. Om B = A T, där A T är införlivandet av A, spelet kallas symmetrisk. En blandad strategi för radspelaren är en sannolikhetsvektor P  på R n och en blandad strategi för kolumnspelaren är en sannolikhetsvektor Q  på R m. Utbetalningen till radspelaren av P mot Q är P · AQ och det till kolumnspelaren är P · BQ. Låt oss beteckna utrymmet för sannolikhetsvektorer för radspelaren med P och motsvarande utrymme för kolumnspelaren med Q. En Nash jämvikt av ett 2-spelarspel (A, B) är ett par blandade strategier P * och Q * sådan att alla ensidiga avvikelser från dessa strategier inte är lönsamma, det vill säga, för alla P  på P och Q på Q, vi samtidigt har att observera att om bimatrix spelet är symmetrisk, den andra ojämlikheten är överflödig. Låta (C, C T ) vara en symmetrisk bimatrix spel.Vi kallar en Nash jämviktsstrategi, säger P *, symmetrisk, om (P *, P * ) är en jämvikt, i vilket fall vi kallar jämvikten (P *, P * ) en symmetrisk jämvikt. Vi är nu redo att ge den formella definitionen av ett ESS (motsvarande den ursprungliga definitionen på grund av Maynard Smith och Price [1973] och Maynard Smith [1982] såsom framgår av Hofbauer et al. [1979]............................................................................................................ Denna förordning träder i kraft den tjugonde dagen efter det att den har offentliggjorts i Europeiska unionens officiella tidning. Låta (C, C T ) vara en symmetrisk bimatrix spel. Vi säger att X * X är en ESS, om Här X är utrymmet för blandade strategier (C, C T ) (en simplex i R n där n är antalet rena strategier) och O är ett område av X *. Den tidigare definitionen generaliserar till (icke-linjära) populationsspel: Befolkningsspel är vektorfält begränsade på en polytop (som också ibland kallas en simplotope eftersom det är den kartesiska produkten av simplexer). Formellt är ett populationsspel ett par (X, F ). X, spelets tillstånd utrymme, har produktform, dvs X = X 1 × · · × X n, där X i är simplexes och i = 1,..., n avser en spelare position (eller befolkning). För varje population motsvarar i motsvarar en uppsättning S i av m i rena strategier och en befolkningsmassa i > 0. Strategin utrymme X i av befolkningen i har formen Vi hänvisar till elementen i X som stater. Varje tillstånd X X kan brytas ner i en vektor strategier, d.v.s. X = (X 1,. ., X n ) T. Låt m = i m i. F : X → R m, spelets payoff funktion, kartor X, spelets tillstånd utrymme, vektorer av payoffs där varje position i vektorn motsvarar 8 till en ren strategi. Det antas normalt att F är kontinuerlig. Vi antar följande konvention: I en-befolkning spel, X(i) kommer att hänvisa till befolkningsmassan på ren strategi i, medan, i multi-befolkning spel, X j i kommer att hänvisa till befolkningsmassan på strategi j av befolkningen i. I en allmän befolkning spel, Nash jämvikt och ESS erkänna följande definitioner (till exempel hänvisar vi läsaren till [Sandholm, 2010] ). I denna förordning gäller följande definitioner: Låt (X, F ) vara en befolkning spel. Vi säger att X * X är en Nash jämvikt, om vi säger att X * X är en ESS, om Här O är ett område av X *. X * kallas global ESS (GESS) om O sammanfaller med X. Definitionen av Nash jämvikt i symmetriska bimatrix spel kan lätt visas vara ett specialfall av den ovannämnda mer allmänna definitionen. Den senare definitionen bär nära släktskap med (i synnerhet är det ett specialfall av) den allmänna uppfattningen av kritiska (equilibrium) punkter av en variationell ojämlikhet. Observera att en ESS nödvändigtvis är en Nash jämvikt (i själva verket isolerad). Ett annat ord är att akronymen ESS, som nämndes tidigare, hänvisar till en evolutionärt stabil strategi i samband med spel med en enda befolkning. Termen strategi används i betydelsen av en blandad strategi (dvs. en sannolikhetsfördelning över uppsättningen av rena strategier). Akronymen ESS betyder emellertid evolutionärt stabilt tillstånd, vilket motsvarar en kombination av (blandade, i allmänhet) strategier, en för varje population. Med detta i åtanke leder ingen tvetydighet till att man hänvisar till båda situationerna med termen ESS (vilket är vanligt i litteraturen). Vi gör följande notationella konventioner: Det finns två likvärdiga perspektiv som visar befolkningen spel, nämligen en där agenter i befolkningen försöker maximera utbetalningar och en där de försöker minimera kostnaderna. Vi tycker att det är bekvämt att anta båda perspektiven i olika delar av detta dokument. När vi antar att agenter har incitamentet att maximera kommer vi att använda F (·) för att beteckna populationsspelets vektorfält och när som helst för att minimera vi kommer att använda c(·). Dessutom kommer tillstånd att betecknas med versaler i maximeringsperspektivet (t.ex. X) och gemener i minimeringsperspektivet (t.ex. x). Observera att de ovannämnda definitionerna av Nash jämvikt och evolutionär stabilitet kan formaliseras i minimeringsperspektivet genom att ändra notationen (från F (·) till c(·)) och vända ojämlikheten. De tidigare (abstrakta) definitionerna är visserligen ganska torra, särskilt ur ett datavetenskapligt perspektiv. Även om matematisk analys vanligtvis drar nytta av en hög abstraktionsnivå, eftersom det innebär en bredare tillämpning av de resultat den producerar, noterar vi att det ändå finns en god intuition om hur dessa begrepp kan sättas in i problem av praktiskt intresse för nätverksdesign, mot slutet av pappret, särskilt i avsnitt 6.4. Den vanliga spelteoretiska miljö där multiplikativa viktmetoder tillämpas gäller att spela ett upprepat spel mot en motståndare (jfr. [Freund och Schapire, 1999]........................................................................................................... I vår miljö antar vi att miljön inte kontrolleras av en motståndare utan snarare antar strukturen av befolkningen spel (vare sig i den allmänna eller mer specifika inställningar). 9 Med tanke på, Hedge, en av de mest allmänna instantieringar av multiplikativa vikter algoritmer, uppdateras regeln i den allmänna inställningen av befolkning spel ges av kartan X → T (X), där X X är det aktuella tillståndet för befolkningen spelet (X, F ), och T (X) är tillståndet för befolkningen spelet efter kartan tillämpas, där T (X) = (T 1 (X),. .., T n (X)) T, och, där i = 1,.., n och j  på........................................................................................... Observera, genom att ta Taylor expansion av exponentiella i det föregående uttrycket, att om parametern α (kallas inlärningshastigheten eller stegstorlek) är tillräckligt liten så att andra ordningen termer i Taylor expansion kan ignoreras, och antar ytterligare en enda befolkning spel med linjära payoffs (dvs, antar F (X) = CX) och enhet massa ( ∂ = 1), sedan det föregående uttrycket minskar till diskret tid replikator dynamisk (2). Tills vidare antar vi en sådan förenklad version av multiplikativa vikter dynamik, som vi kommer att generalisera i uppföljaren. En del av vår analys görs i en något mer allmän form än vad som faktiskt är nödvändigt för att få våra huvudsakliga resultat, för att underlätta tillämpningen av respektive resultat på den allmänna inställningen. För att utföra denna analys, kommer vi att använda följande notation: och Matrisen C är en n × n matris som motsvarar payoff matrisen i en allmän symmetrisk bimatrix spel. Vi kallar α > 0 inlärningsgraden eller den multiplikativa uppdateringsregelns stegstorlek. Observera att för alla α ≥ 0, Detta innebär att multiplikativa vikter evolutionsregeln har en egenskap som vanligtvis kallas framåt invarians. Vi noterar, utan bevis för tillfället, att symmetriska Nash Equilibria (och därför också evolutionärt stabila strategier) nödvändigtvis vilopunkter av multiplikativa vikter karta, men att resten punkter på denna karta är inte nödvändigtvis symmetriska Nash Equilibria, utan snarare Nash Equilibria av "begränsade" fall av spelet (där vissa rena strategier saknas). (Detta påstående är bevisat som Theorem 2 i den allmänna flerpopulationsinställningen). 10 Låt oss slutligen notera att vi i vår analys av den multiplikativa viktdynamiken kommer att förlita oss på den relativa entropifunktionen mellan sannolikhetsfördelningen (även kallad Kullback-Leibler divergens). Den relativa entropin mellan n × 1 sannolikhet vektorer P och Q ges av Genom hela detta papper antar vi att 0/0. = 1 och 0 · ∞. = 0. Är du säker på att du är säker på att du är säker på det? Enligt dessa notationskonventioner behöver P och Q inte ha fullt stöd för att definitionen ska vara giltig. Det räcker helt enkelt att stödet för P är en del av stödet för Q. Vi noterar vidare den allmänt kända egenskapen hos den relativa entropin att RE(P, Q) ≥ 0 och RE(P, Q) = 0 om och endast om P = Q. Vi börjar med att kortfattat introducera några relevanta begrepp och välkända resultat från teorin om diskreta tidsdynamiska system (jfr. [LaSalle, 1986]......................................................................................................... Betrakta kartan T : R n → R n där T är kontinuerlig och låt X * vara en fast punkt för T, det vill säga T (X * ) = X *. Vi säger att X * är stabilt under T om där O och ska är kvarter av X *. Om X * inte är stabilt, säger vi att det är instabilt. Låt V : R n → R, och defineV Låt X vara någon uppsättning i R n. Vi säger att V är Lyapunov funktion för T på X om V är kontinuerlig på R n ochV (X) ≤ 0 för alla X  på X. Vi säger att funktionen V : R n → R är positiv med avseende på X * om V (X * ) = 0 och det finns ett område O av X * sådan att, för alla X = X * i O, vi har att V (X) > 0. Följande förslag kallas Lyapunovs stabilitetsteorem. Förslag 1. Om V är Lyapunov funktion för T på något område av X * och V är positiv definitivt med avseende på X *, då X * är en stabil fast punkt av T. X * är asymptotiskt stabil under T om det är stabilt och det finns ett område O av X * sådan att Proposition 2. Om V och −V är positiva definitivt med avseende på X *, X * är asymptotiskt stabil. Innan vi bevisar vårt huvudsakliga resultat behöver vi följande lemma. Det här är Lemma 1. Låt P *, P, Q  på P, där P är utrymmet för blandade strategier för en symmetrisk bimatrix spel (C, C T ), vara sådan att P * och Q är godtyckliga, supp( P * ) Supp( P ), och låtP = M W α (P, Q). Bevisa det då. Vi har nu, för alla y > 0, ln y ≤ y − 1, och, därför, Beviset för nästa lemma förlitar sig på Kantorovich ojämlikhet (jfr. (Steele, 2004)......................................................................................................................... Låt Lemma 2. Låt P *, P, och Q som i föregående lemma. Bevisa det då. Från Kantorovitj ojämlikhet vi har som i uttalandet av lemma. Låt (C, C T ) vara ett symmetriskt bimatrix spel där C är en n × n matris sådan att 0 < C < 1, i att alla delar av C är i detta intervall, notera att det senare antagandet görs utan förlust av generalitet, låt X vara utrymmet för blandade strategier (C, C T ) (sannolikheten simplex i R n ), och betrakta kartan T : X → X där E i är en sannolikhet vektor vars massa är koncentrerad i position i, och α : X → R + är en funktion som vi hänvisar till som steg storlek regel. Observera att genom att ta derivatan av T med avseende på α och låta α = 0, får vi på höger sida vektorfältet av differentialekvationen av kontinuerlig-tid replikator dynamik i (1). Även om det är känt att en ESS är asymptotiskt stabil under (1), som nämns i inledningen, är vi inte medvetna om några allmänna resultat som binder beteendet hos (4) med det av (1). Den oberoende studie av den diskreta evolutionsregeln som vi anser är därför nödvändig. I denna anda har vi följande teorem. Teorin 1. Om X * X är ett ESS av (C, C T ) där 0 < C < 1, då finns det en steg storlek regel α sådan att X * är asymptotiskt stabil under (4). Bevis. Vårt bevis är konstruktivt genom att vi tillhandahåller en explicit steg storlek regel α sådan att X * är asymptotiskt stabil under (4). Vi noterar att regeln som vi tillhandahåller här beror på kunskap om X *. De tekniker som utvecklats i detta dokument räcker dock för att lyfta detta beroende av X *, För att undvika en onödig upprepning hänvisar vi läsaren till nästa avsnitt för motsvarande analys i multi-populationsinställningen av icke-linjära belöningar, som generaliserar Theorem 1. Men vi väljer att behålla denna analys för att illustrera vissa punkter som diskuterats mot slutet av bevisen. Vår analys är med hjälp av följande Lyapunov funktion: Använda standard egenskaper hos den relativa entropi kan det verifieras att V är positiv definitivt i ett område av X *. Dessutom tyder Lemmas 1 och 2 på att eftersom X * är ett ESS, där (5) innebär att f (α) − 1 ≥V (X) (för alla α > 0). Observera att Observera vidare att dessutom, och eftersom h(0) = g(0) = 1, vi får det och, därför, Vi får därför ytterligare Noting att eftersom f är en kontinuerlig funktion av α, kan vi omedelbart dra slutsatsen att är antingen strikt minska för alla α > 0 eller annars det uppnår ett minimum i ett område av 0 vid, säger α *, sådan att f (α * ) < 1. Men låt oss undersöka (5) mer noggrant. 14 Vi skulle vilja få ett värde av α så att högersidan av (5) är negativ, det vill säga, Vi kan skriva det tidigare uttrycket som, eftersom α > 0, är likvärdigt att observera nu att eftersom X · CX < X * · CX, och använda rak algebra, det kvadratiska uttrycket på vänster sida av den tidigare ojämlikheten är mindre än Det, därför räcker att beakta värden av α > 0 så att det senare uttrycket är < 0. Observera att det senare kvadratiska uttrycket är konvext, negativt när α = 0, och eftersom det är konvext uppnår det ett minimum vid den stationära punkten α = −(1/2). Att låta sig vara discriminant av det kvadratiska uttrycket, det vill säga den stegvisa storleksregeln som väljer någon α sådan som garanterat är positiv, innebär asymptotisk stabilitet av diskret-tid replikator dynamisk (4) av Proposition 2 (sedan för alla X i ett område av X *,V (X) < 0). Steg storlek regel i (6) kräver kunskap om X *. Vi noterar att det finns tillämpningar där en sådan regel kan vara till hjälp. Till exempel, en fråga av praktiskt intresse är, med tanke på en symmetrisk bimatrix spel (C, C T ) och en strategi Y i sannolikheten simplex av detta spel, om Y är en ESS (till exempel, se [Etessami och Lochbihler, 2008, Nisan, 2006]). Om inte Y är asymptotiskt stabilt enligt ovan nämnda steg storleksregel, kan vi dra slutsatsen att Y inte är en ESS. I ett annat program finns det agentpopulationer (t.ex. själviska Internetanvändare) som styrs av evolutionär dynamik såsom den diskreta tidsreplikatordynamiken (som vid inställning av Internet kan motsvara algoritmer som rutttrafik), och ingenjörer som är intresserade av att vägleda 15 sådana populationer mot önskvärda jämviktsresultat kan bara manipulera dessa dynamikers respektive parametrar (snarare än efterfrågan). I dessa miljöer kan kunskap om X * lätt antas; till exempel, i självisk routing, ett ämne som diskuteras mer ingående senare i denna uppsats, X * kan beräknas med någon konvex programmeringsalgoritm förutsatt att trafikefterfrågan är känd. Multiplikativ viktdynamik är, på grund av deras goda ångerprestanda, mer tilltalande än t.ex. gradientprojektionsalgoritmer i händelse av nätverksfel och fel, som de lättare kan kringgå, därför en sådan inställning är inte orimligt i praktiska tillämpningar. Innan vi avslutar denna diskussion, låt oss titta närmare på (6). Observera att för alla X i ett område av X *,  på > 0, vilket är en konsekvens av definitionen av en ESS (dvs., X * · CX > X · CX, X i ett område O). Observera vidare att när X närmar sig X *, α närmar sig värdet 0, vilket är en enkel konsekvens av noggrann inspektion av (6). Därför kan den tidigare formeln inte ge en (begränsat) positiv övre gräns på α så att för alla värden α mindre än denna övre gräns, den potentiella funktionen garanteras att sjunka, även om vi antar kunskap om X *. Det är en intressant fråga om det finns en sådan övre gräns. Även om vår utlovade stegstorleksregel som är oberoende av ESS inte kommer att definieras och analyseras förrän i nästa avsnitt, anser vi att det är rimligt att diskutera Weissings resultat här. Låt oss först visa, i denna anda, att en inre ESS (dvs. en ESS som stöds av varje ren strategi) är (inre) globalt asymptotiskt stabil under diskret-tid replikator dynamisk (notera att, något missbruka terminologi, använder vi termen inre när vi hänvisar till asymptotisk stabilitet som innebär att asymptotisk stabilitet är underförstådd från en inre punkt av varje coface av sannolikheten simplex som stöder ESS, som i fallet med en inre ESS är hela simplex). Vårt bevis bygger på följande karakterisering av ett ESS i ett symmetriskt bimatrixspel (motsvarande den ursprungliga definitionen av Maynard Smith och Price [1973] och Maynard Smith [1982]). Förslag 3. Låta (C, C T ) vara en symmetrisk bimatrix spel. X * X, där X är utrymmet för blandade strategier (C, C T ), är ett ESS om och endast om X * · CX * ≥ X · CX *,  och X, och ett bevis på Proposition 3 kan till exempel hittas i [Weibull, 1995]. Observera nu att genom en elementär egenskap hos Nash Equilibria, om X * är en inre Nash jämvikt, då, för alla X X X, (X * - X) · CX * = 0, och, därför, genom Proposition 3, om X * är en inre ESS, för alla X  på X, (X * - X) · CX > 0. Detta innebär att X * är ett GESS. Att X * är (inre) globalt asymptotiskt stabil under den diskreta tiden replikator dynamik följer nu av ett argument som liknar beviset för Theorem 1 (med början från en inre strategi, den potentiella funktionen sjunker). Weissing [1991] hävdar i sitt teorem 6.5 att ett sådant ESS är en global attraherare för den diskreta tid replikatordynamiken (med antagande om en tillräckligt liten, konstant stegstorlek). Även om global stabilitet helt klart är en omöjlighet eftersom det, med början på gränsen för sannolikheten simplex, inte kan få positiv befolkningsmassa utan stöd, är det fortfarande en intressant fråga om det är möjligt att förlänga vår asymptotiska stabilitetsanalys med antagandet att stegstorleken är konstant. 16 I detta avsnitt generaliserar vi Theorem 1 till allmänna befolkningen spel. Evolutionsregeln vi anser är en approximation av (3) för en tillräckligt liten stegstorlek:, där i = 1,.., n och j  till S i. Observera att (7) sammanfaller med (4) om vi låter n = 1 och F (X) = CX. Vår analys utgår från samma mönster som i föregående avsnitt, även om den till slut blir mer involverad på grund av interaktionseffekterna mellan populationerna och härledningen av en stegvis storleksregel som inte är beroende av kunskap om ESS. Innan vi går vidare med analysen, låt oss först identifiera de fasta punkterna av (7) i denna mer allmänna inställning. Vi visar i själva verket att de fasta punkterna i (7) sammanfaller med de fasta punkterna i (3), vilket, även om det förväntas, är något intuitivt tilltalande. Följande teorem utlovades i prequel. ., X n ) T är en fast punkt av (7) om och endast om, för alla i = 1,..., n, och, för alla j 1, j 2 S + (X i ), F Bevis. Först visar vi tillräcklighet: Om för alla i och för alla j 1, j 2 S + (X i ), F Några av koordinaterna för X i är noll och några är positiva. Det är uppenbart att nollkoordinaterna inte kommer att bli positiva efter att kartan har tillämpats. Lägg nu märke till att, för alla j  till S + (X i ), 1 + αF j i (X) = 1 + α(1/ på ) k tills i X i · F i (X), och, därför, T i (X) = X i, och detta gäller för alla i. Nu visar vi nödvändighet: Om X är en fast punkt av (7), sedan för alla i och för alla j 1, j 2 S + (X i ), F Ekvation (8) innebär att, för alla i = 1,..., n och för alla j S i, där c är en konstant. Detta kompletterar beviset. Följande teorem hävdar att den allmänna dynamiken (3) har samma fasta punkter som (7). ., X n ) T är en fast punkt av (3) om och endast om, för alla i = 1,..., n, och, för alla j 1, j 2 S + (X i ), F Bevis. Först visar vi tillräcklighet: Om för alla i och för alla j 1, j 2 S + (X i ), F Några av koordinaterna för X i är noll och några är positiva. Det är uppenbart att nollkoordinaterna inte kommer att bli positiva efter att kartan har tillämpats. Lägg nu märke till att, för alla j  till S + (X i ), exp{αF Därför, T i (X) = X i, och detta gäller för alla i. Nu visar vi nödvändighet: Om X är en fast punkt av Hedge, sedan för alla i och för alla j 1, j 2 S + (X i ), F Ekvation (9) De tidigare teorem antyder att Nash Equilibria (i deras allmänna definition som anges tidigare) nödvändigtvis är fasta punkter av både (3) och (7). Detta följer omedelbart av en karakterisering av Nash equilibria i befolkning spel enligt vilken en stat är en Nash jämvikt om och endast om alla strategier som är i bruk (dvs. få en (strikt) positiv befolkningsmassa) i varje befolkning får samma avkastning och att strategier som inte används (deras befolkning massa är noll) får en payoff som inte är lägre än den payoff som mottas av strategier som är i bruk. (Med denna karakterisering i åtanke, innebär de tidigare teorem också att det finns fasta punkter i den ovan nämnda diskret dynamik som inte Nash equilibria.) Eftersom evolutionärt stabila tillstånd nödvändigtvis Nash equilibria, de är också fasta punkter i en sådan dynamik. I resten av detta avsnitt handlar det om stabiliteten i utvecklingsstabila stater. Låt X * X vara en ESS av befolkningen spelet (X, F ). Vi anser att diskret-tid replikator dynamisk kartläggning X X toX X wherê, och där i = 1,..., n och j  till S i. Kom ihåg att, som tidigare nämnts, om α är tillräckligt liten, (3) minskar till denna ekvation. Vår stabilitetsanalys av denna evolutionsregel är baserad på Lyapunov-funktionen RE(X *, X). Eftersom vår definition av relativ entropi använder sannolikhetsvektorer antar vi att i i = 1. Som vi hävdar senare görs detta antagande utan förlust av allmängiltighet. Vi har: Eftersom, för alla y > 0, ln y ≤ y − 1, vi får, Det tidigare uttrycket blir Vårt mål är att hitta en steg storlek regel så att höger sida av den tidigare ojämlikheten är negativ. I detta syfte använder vi kantorovitj ojämlikhet: där G min = min ij G ij (X) och G max = max ij G ij (X) där i och j varierar i strategier i stöd för X. Observera att, med det aritmetiska medelvärdet / geometriska medelvärdet ojämlikhet, För att Kantorovich ojämlikhet att vara användbar i analysen, måste vi sedan ha innan bevisa detta, några observationer är i ordning: Vi kan anta, utan förlust av generalitet, att F j i (X) > 0, för alla i = 1,..., n, j  på S i, och X X, sedan lägga till en tillräckligt stor konstant till varje F j i (X) påverkar inte de evolutionära egenskaperna hos en Nash jämvikt. Eftersom att multiplicera alla sådana poster med samma positiva konstant inte heller påverkar de evolutionära egenskaperna hos en jämvikt, kan vi på liknande sätt anta, utan förlust av generalitet att F j i (X) < 1, och dessutom, att n i=1 i = 1. Under dessa antaganden, för alla i = 1,..., n, 0 Hänvisa till (11), tar en Taylor expansion av 1/ (1 + α(1/ och i )X i · F i (X)), och förutsatt att α är tillräckligt liten för att erhålla en konvergent oändlig serie, vi få den högra sidan av det tidigare uttrycket kan skrivas som som vi kan skriva om som Omstrukturerande termer vi får och raka algebra ger som är likvärdigt med. Påminner om att, för alla i = 1,..., n, 0 som önskat. Låt oss nu överväga uttrycket, Att notera att vårt mål är att hitta en steg storlek regel sådan att detta uttryck är < n i=1 i = 1. Därför fortsätter vi på ett sätt som liknar det som användes i den tidigare (särskilda) inställningen av symmetriska bimatrixspel. Låt oss därför först överväga g(α). Med hjälp av notationen får vi följande lemma. Innan vi anger lemma noterar vi att O(·) notation i detta dokument hänvisar till standarddefinitionen i verklig analys och icke-linjär optimering [Chong and Zak, 2008, s. 72] snarare än som vanligtvis används i teorin om algoritmer. - Vad är det? - Lemma 4. Bevis. Vi har därför, Rak algebra fullbordar beviset. Lemma 4 innebär g(0) = 1 och g (0) = 0. Därför erinrar man från beviset för Lemma 3 om att det är lätt att kontrollera att X * genom antagandena är ett ESS och i i = 1, och därmed genom (13) att f (0) < 0. För att avsluta vårt argument förlitar vi oss på följande lemmas. Det här är Lemma 5. Låt X X X,X = T (X) där T motsvarar (7), och anta X är inte en fast punkt av T. Sedan, för alla α > 0,X Det vill säga, X är ett bättre svar på X än X själv. Bevis. Den relativa entropi mellan sannolikhetsvektorer (1/ på )X i och (1/ på i )X i är positiv: Därför, Exponentiera båda sidor vi får Använda Jensens ojämlikhet, vi får Därför, exponentiera båda termerna vi får Combining (15) och (16), vi får Summing över i = 1,...., n, avslutar beviset. Det är Lemma 6. Det finns > 0, som kan bero på X, sådan att, för alla 0 < α ≤, där T definieras enligt (7). Bevis. Vi har i den tidigare härledningen vi har tagit Taylor expansionen av 1/(1 + α(1/en i X i · F i (X)), notera att motsvarande oändliga serien är konvergerande förutsatt att α är tillräckligt liten. Notera vidare att den tredje till sista ojämlikhet är en implikation att i ≤ 1 på grund av ovan nämnda antagande att i i = 1 och att den andra till sista ojämlikhet är en implikation av Jensens ojämlikhet. Resten av argumentet sammanfattas i beviset för följande teorem. Teorin 4. Om X * X är en ESS av befolkningen spelet (X, F ), då finns det en steg storlek regel α sådan att X * är asymptotiskt stabil under (7). Bevis. Vi använder V (X) = RE(X *, X) som vår Lyapunov funktion. Därför,V (X) = f (α) − 1. Kom ihåg från beviset för Lemma 3 att (sedan i i = 1) LettingX som i Lemma 6 och med hjälp av denna lemma, vi få för alla 0 < α ≤. (I det tidigare uttrycket som visar X:s beroende av α är betoningen.) Lemma 5 innebär att en (α) < 1 för alla α > 0. Tar Taylor expansionen av g(a) på a = 0 och Taylor expansionen av ska(α), får vi emellertid, g(0) = 1 och g (0) = 0, och, därför, 24 innebär att, för liten nog α, f (α) < 1, av Lemma 5. Denna analys föreslår därför följande steg storlek regel: Välj några initialt värde, säger α 0, för stegstorleken, och jämföra värdet f (α 0 ) med en. Iff (α 0 ) < 1, övergång till den nya statenX(α 0 ). Annars låt α 1 = α 0 / 2, och upprepa denna process tillsf (α k ) < 1, där α k = α 0 /2 k och k är ett positivt heltal. Lemma 6 och (17) säkerställa att denna process avslutas i ett begränsat antal steg. Genom att använda denna steg storlek regel (liknar linje sökning i icke-linjär optimering) och åberopa Proposition 2 kompletterar beviset. I resten av detta avsnitt diskuterar vi fallet med att använda enklare steg storlek regler såsom en konstant steg storlek i diskret-tid replikator dynamik. Observera att även om och med hänvisning till Lemma 4, g(α) kan approximera värdet 1 med godtycklig noggrannhet för ett tillräckligt litet värde av α. Uttrycket i Lemma 4, innebär i själva verket att g(α) närmar sig värdet 1 (uppifrån) mycket snabbare (kvadratiskt så) än α när α närmar sig 0, vilket är önskvärt med hänsyn till konvergenskvoten. Kom vidare ihåg att, genom Lemma 3 och Kantorovitj ojämlikhet, den första skillnaden i Lyapunov funktionen RE(X *, X), som uttrycks i (10), är negativ överallt men i små grannskap, säger N, av X *, som kan göras godtyckligt liten genom ett lämpligt urval av stegstorlek α (eftersom, genom Lemma 4, g (a) närmar sig 1 kvadratiskt, från ovan, medan h(α) närmar sig 1, underifrån, endast linjärt som α → 0 för fast X). Dessutom, eftersom, som är välkänt, den relativa entropi mellan två sannolikhetsfördelningar överstiger kvadraten på Euclidean avståndet mellan dessa fördelningar (förutsatt att ett sådant avstånd är positivt), den tidigare observationen om förekomsten av en stadsdel N runt X * där den första skillnaden i Lyapunov funktionen är negativ, innebär förekomsten av en godtyckligt liten stadsdel runt X * (det vill säga, en boll av godtyckligt liten radie och center X * skär evolutionsrymden X), säger N *, sådan att den diskreta tiden replikator dynamik garanteras att gå in och förbli därefter även om en konstant steg storlek regel används. Vi förväntar oss därför att ett ESS i praktiken kan approximeras med godtycklig precision även genom en regel om konstant stegstorlek. Den tidigare analysen innebär dock också att andra stegstorleksregler, mer sofistikerade än att använda en konstant stegstorlek men mindre krävande när det gäller funktionsutvärderingar än den tidigare som innebär asymptotisk stabilitet, också räcker för att säkerställa en egenskap som är jämförbar med vad vi just har beskrivit. I denna ven, eftersom den inställning vi överväger är en där flera populationer interagerar, är det meningsfullt att generalisera diskret-tid replikator dynamik så att varje population anpassar sig enligt en populationsberoende inlärningsfrekvens α i enligt följande: Låta nu där σ är en liten konstant (som alltid kan väljas som sådan eftersom F är kontinuerlig och domänen F är en kompakt polytop), och påminna om att f (α) = g(α)h(α) där h(α) och hänvisar till antingen (11) eller (14), vi får (utan att tillgripa argumentet i Lemma 3) att och, därför, att det tidigare argumentet om förekomsten av N * för konstant steg storlek regel gäller för denna senare (adaptiv) steg storlek regel också. När vi avslutar detta avsnitt bör vi notera att vi inte kan utesluta att asymptotisk stabilitet med hjälp av en tillräckligt liten regel om konstant stegstorlek mycket väl kan inträffa, och vår oförmåga att bevisa ett sådant resultat kan bero på det analytiska tillvägagångssätt vi har valt. Vi anser dock att våra argument stämmer överens med ett ganska övertygande fall att regeln om konstant stegstorlek skulle kunna fungera bra i praktiken. I detta avsnitt relaterar vi multiplikativa vikter med begrepp från icke-linjär optimeringsteori. I detta syfte relaterar vi först ESS med idén om en strikt lokal optimal. Vårt primära mål, i denna anda, är att ytterligare motivera generaliteten av våra resultat på asymptotic stabilitet av ESS under multiplicativ vikt dynamik (i synnerhet, Theorem 4) med den allmänna icke-linjära optimeringsramen. I samma anda relaterar vi därefter den multiplikativa viktdynamiken med lutningen av en kontinuerligt differentierad objektiv funktion. Befolkningsspel är en ganska allmän modelleringsmiljö. Ett specialfall av ett populationsspel är ett ickelinjärt programmeringsproblem där begränsningssetet är en simplotope och den objektiva funktionen ständigt kan varieras. (Detta är lätt att se enligt följande: Eftersom den objektiva funktionen kontinuerligt skiljer sig åt, är motsvarande gradientfält som erhålls genom att ta lutningen av den objektiva funktionen kontinuerlig. Därför, att betrakta en sådan optimering problem som en särskild instans av en befolkning spel är ingenting annat än ett alternativt sätt att representera samma problem.) Ett viktigt lösningskoncept i ickelinjär programmering är strikt lokal optimal (minimi eller maximum), som motsvarar en punkt i restriktionen uppsättning vars objektiva värde är strikt lägre (förutsatt ett minimum) än de objektiva värdena för alla närliggande punkter (i ett grannskap). Begreppet strikt lokalt minimum sammanfaller inte med begreppet evolutionärt stabilt tillstånd för godtyckliga objektiva funktioner; intressanta motexempel kan påvisas genom granskning av objektiva funktioner som Absil och Kurdyka har beaktat [2006]. Med tanke på dessa exempel är det naturligt att fråga i vilken utsträckning begreppet evolutionärt stabila tillstånd i potentiella spel (dvs. spel som medger en potentiell funktion), eller motsvarande kontinuerligt olika icke-linjära programmeringsproblem över en simplotope, sammanfaller med strikt lokala optima. Hofbauer och Sandholm [2009] visar att om den potentiella funktionen är strikt konvex (åtminstone lokalt), då sammanfaller dessa begrepp. Dessutom, som nämnts tidigare i inledningen, i dubbelt symmetriska bimatrix spel, det vill säga symmetriska bimatrix spel (C, C T ) där C är en symmetrisk matris (C = C T ), strikt lokala maxima är kända för att sammanfalla med evolutionärt stabila tillstånd (eller, mer exakt, strategier i denna speciella miljö) som visas av Hofbauer och Sigmund [1988]. I själva verket, som nämndes i inledningen, kan det allmänna problemet med quadratic programmering över en polytop kastas i denna miljö. Men detta är inte de enda fall där en sådan tillfällighet mellan strikt lokala optima och evolutionärt stabila stater inträffar. Notioner av konvexitet av kontinuerligt differentierade skalärfunktioner kan fångas upp genom föreställningar om monotonitet i deras motsvarande gradientfält (ses som operatörer). Till exempel, konvexa funktioner ger upphov till monoton lutning fält. Monoton vektorfält är mer allmänna än konvexa funktioner, men ett monoton vektorfält som medger en potentiell funktion ger upphov till en konvex funktion. Faktum är att ovan nämnda arbete Hofbauer och Sandholm [2009] på stabila spel motiverades av observationer längs dessa linjer: Stabila spel generaliserar potentiella spel med en konkava potentiell funktion. Observera att strikt stabila spel ger upphov till ett GESS. Kvasimonotonoperatörer generaliserar monotona operatörer: Om en kvasimonotonoperatör medger en potentiell funktion är motsvarande skalärfält en kvasikonvex eller kvasikonkavfunktion; till exempel är den Gaussiska sannolikhetsfördelningen kvasikonkav. Konnov [1998] visar att strikt kvasimonotonoperatör F över en kompakt konvex domän X innebär att det finns ett unikt element X * X så att, för alla X X X, (X * − X) · F (X) > 0. Om X är simplotope, (X, F ) är ett populationsspel, och Konnov resultat innebär X * är ett GESS. En enkel konsekvens av detta resultat är att den stationära punkten för en (lokalt) strikt kvasikonvex funktion också är ett ESS. I resten av detta avsnitt fortsätter vi vår utredning om icke-linjär optimering. Ett elementärt resultat i kalkylen anger att i inställningen av oöverskådlig optimering, lutningen av en kontinuerlig differentierad objektiv funktion pekar på riktningen för maximal ökning av den objektiva funktionen. Det är därför inte förvånande att en mängd icke-linjära programmeringsalgoritmer baseras på lutningen. Till exempel, i minimering problem, iteraterna av lutning nedstigning algoritmer motsvarar att ta linjära steg längs riktningen av lutningen (och projicering den punkt som erhålls efter ett sådant linjärt steg till begränsning uppsättningen av motsvarande problem, förutsatt att en sådan punkt är ogenomförbar). I resten av detta avsnitt visar vi att stegen multiplikativ viktdynamik tar i den begränsning uppsättning av ickelinjära optimeringsproblem bär nära släktskap med sådana gradient-baserade metoder. Att påminna om den tidigare nämnda begreppet framåt varians, som lätt kan visas hålla i den allmänna inställningen, multiplikativa vikt uppdateringar kräver inte en projektion steg. Med ett minimeringsperspektiv visar vi att multiplikativ viktdynamik till en början sänker den objektiva funktionen genom att anta en tillräckligt liten stegstorlek. I denna mening skulle det inte vara en överdrift att säga att de motsvarar en form av lutning i godtyckliga ickelinjära program (där begränsningsuppsättningen är en simplotope). Vi har i stor utsträckning representerat befolkningsspel ur ett "maximeringsperspektiv" där incitamentsstrukturen representeras av en (vektor värderad) payoff-funktion. Befolkning spel är ibland mer lämpligt representerade med tanke på en likvärdig "minimering" perspektiv med hjälp av en (vektor-värderad) kostnadsfunktion (lönefunktionen är negativ). Vi kommer att beteckna en sådan kostnadsfunktion genom c vars domän är utrymmet för genomförbara tillstånd X. Vi kommer att anta samma notationella konvention som i payoff vektorer, nämligen c j i (x) är kostnaden för strategi j i befolkningen i vid state x. I denna inställning, (3) blir, Där i = 1,.., n och j  till S i. Vi noterar i förbigående att titta befolkning spel från perspektivet att minimera kostnader är ett särskilt lämpligt perspektiv i inställningen av själviska routing spel som vi anser i nästa avsnitt. I inställningen av självisk routing, stater motsvarar nätverksflöden, populationer motsvarar råvaror, och strategier inom i befolkningen / vara motsvarar nätverk vägar. Målet är att minimera förseningen från källa till destination, och kostnaderna tolkas som sådana. Vi betraktar ett populationsspel vars stimulansstruktur kan representeras av en ständigt differentierad skalärfunktion, till exempel 0, vars domän är X. Som tidigare nämnts, själviska routing spel, till exempel erkänna en potentiell funktion som faktiskt är konvex. För närvarande antar vi dock inte konvexitet. Det algebraiska uttrycket för den potentiella funktionen kan vara komplicerat, men allt vi bryr oss om är att dess gradient är lika med kostnadsfunktionen c, det vill säga, vid alla tänkbara tillstånd 27 x  på X,  för x = c(x). Låt oss vidare erinra oss från optimeringsteorin begreppet sublevel uppsättning av en skalär funktion: sublevel uppsättning av 0 i en genomförbar tillstånd x, betecknad som L 0 (x), är Om 0 är, till exempel, en konvex eller kvasi-konvex funktion, dess sublevel uppsättningar är konvexa uppsättningar men, i allmänhet sublevel uppsättningar kan ta på godtyckliga former. Observera att vid okonstruerade optimeringsproblem är lutningen av den objektiva funktionen vid en punkt i domänen vinkelrät mot motsvarande nivå som är inställd på den punkten. Eftersom vi har att göra med ett begränsat optimeringsproblem, är det analoga påståendet att projektionen av kostnadsvektorn, c(x), vid ett inre tillstånd x vid tangentutrymmet i begränsningsutrymmet är vinkelrät mot undernivån som L 0 (x) vid x. Med tanke på ett potentiellt spel med potentiell funktion 0 : X → R visar nästa teorem att Hedge (som ges av uppdateringsregeln i (18) är minimeringsanalogen av (3)) en nedstigningsalgoritm (i betydelsen ickelinjär programmering), under antagande om en tillräckligt liten stegstorlek, för spelets potentiella funktion. Observera, i denna ven, att med tanke på ett potentiellt spel och med början vid något tillstånd x i utrymmet för genomförbara tillstånd X, (18) definierar en (icke-linjär) kurva C x : (0, +∞) → X på utrymmet för genomförbara tillstånd parametrized av inlärningshastigheten α, och, beroende på valet av α, nästa iterat genereras genom att flytta till en punkt längs C x. (Kontrast detta med det linjära steg som majoriteten av icke-linjära programmeringsalgoritmer tar.) Eftersom hela kurvan C x ligger på utrymmet X av genomförbara flöden, behöver Hedge inte en extra projektion steg för att uppnå genomförbarhet (vilket är en fastighet som vi tidigare kallade framåt invariance). Nästa sats visar att C x (α) definierar (initialt, för ett litet värde på stegstorleken) en nedstigningsriktning i den meningen att tangenten i denna kurva vid x (motsvarande α = 0) är en riktning där den objektiva funktionen minskar lokalt. Teorin 5. Med tanke på alla interiörer x X som inte är en fast punkt är tangenten C x vid x en nedstigningsriktning på 0. Bevis. Tangenten för C x vid x är (dC x /dα)(0). Normalvärdet för den nivå som är inställd på 0 i x är + = [c(x)] + där [·] + betecknar projiceringen av c(x) på tangentutrymmet i X. För att bevisa teorem räcker det att bevisa att vinkeln mellan dessa vektorer är trubbig, dvs. (dC x /dα(0) · [c(x)] + < 0. Med rak analys har vi (uttrycket på höger sida är en vektor av storlek m = i m i vars element som motsvarar population i och strategi j ges inom parentes. Observera att detta vektorfält, som en funktion av x, exakt motsvarar vektorfältet i den kontinuerliga tidsreplikatordynamiken.) Dessutom visar Sandholm [2010] att där 1 är en m × 1 vektor av sådana. Därför, genom Jensens ojämlikhet. För att förstå det föregående teorem minns du att vektorn [c(x)] + vid x är vinkelrät mot nivån som är L 0 (x) vid x. Teoremet anger sedan att för ett tillräckligt litet värde av stegstorleken α ligger nästa iterat inuti L 0 (x), och det objektiva värdet minskas. Vi bör dock notera att α fortsätter att öka C x (α) inte garanteras att förbli i nivå L 0 (x). Vikten av att noggrant välja stegstorlek argumenteras ytterligare i nästa avsnitt. I detta avsnitt är vi intresserade av att ställa in själviska routing spel vars ursprung kan spåras till vägtrafik forskning [Wardrop, 1952). De populariserades i datavetenskaplig litteratur av Roughgardens och Tardos arbete [2002] på priset av anarki [Koutsoupias och Papadimitriou, 2009]. Själviska routing spel är befolkning spel där varje befolkning motsvarar en vara från en källa nod till en destination nod i en riktad graf vars bågar motsvarar överbelastade resurser (t.ex. kommunikationslänkar i ett datornätverk). Denna klass av spel är utrustad med en konvex potentiell funktion, som är strikt konvex under (rimlig i många praktiska inställningar) antagandet att länk kostnadsfunktioner ökar strikt. Genom ett argument analogt som används i beviset för Theorem 4, är (unik) stationär punkt av denna potentiella funktion (som motsvarar Nash / Wardrop jämvikt), (inre) globalt asymptotiskt stabil under Hedge (och diskret tid replikator dynamisk). I uppföljaren går vi vidare med detta resultat. I synnerhet våra mål, i denna anda, är tvåfaldiga: För det första visar vi ett exempel på en enkel självisk routing spel där det finns en steg storlek så att det inducerade beteende Hedge är kaotisk (imply försiktig måste tas i valet av steg storlek i praktiken). För det andra, vi analyserar en enkel självisk routing spel (bestående av parallella bågar mellan ett par hörn) med hjälp av linjärisering, visar att alla eigenvärden av motsvarande Jacobian matris ligger inuti enheten skiva (i alla utom ett antal system som har mäta noll). Vår analys innebär starkare resultat av asymptotisk stabilitet under en tillräckligt liten konstant stegstorlek samt en geometrisk konvergenshastighet (i just denna inställning), men exemplet används också för att visa svårigheten att använda denna typ av analys (baserat på linjärisering) i den allmänna inställningen av den evolutionära dynamik som beaktas i detta dokument. När vi avslutar detta avsnitt, ger vi en intuitiv tolkning av evolutionär stabilitet i ett praktiskt, från ett datavetenskapligt perspektiv, problem relaterade till nätverkssystem design och Internet. Även om begreppet evolutionär stabilitet ursprungligen motiverades och utvecklades ur matematiska biologins perspektiv, hävdar vi att datavetenskap och nätverkade system 29 designforskning i princip kan dra nytta av att få närmare kännedom om detta begrepp. Själviska routing spel ger en lämplig ram för att grundligt formulera ett sådant fall. Själviska routing spel är ett speciellt fall av ickeatomiska trängsel spel när den senare antar en tolkning som motsvarar routing flöde i ett nätverk som representeras som en (riktad) graf. Vi kan definiera en icke-atomisk trängsel spel som följande fem-tuple (E, N, {en i} i.N, {S i} i.N, {c e (·)} e.E ). E är en begränsad uppsättning resurser som kommunikationslänkar i ett nätverk som representeras av en graf. N = {1,..., n} är en ändlig uppsättning varor såsom källdestinationspar. Till varje vara i motsvarar en skalar efterfrågan i > 0 och en uppsättning banor (eller rena strategier) S i 2 E. De rena strategierna motsvarar normalt enkla banor i nätverkets graf. Efterfrågan på varje vara fördelas på vägar av (infinitesimala) agenter (eller paket) som inducerar flödet av resurser. Ett ickeatomiskt trängselspel är ett specialfall av ett populationsspel där N motsvarar (finita) uppsättningen n populationer, i, i N är massan av befolkningen i, och S i är uppsättningen av rena strategier för samma befolkning. Stater motsvarar (flera varor, som de vanligtvis kallas) flöden. Vi betecknar utrymmet för alla multi-varor flöden med X. En multi-commodity flow x X är den "aggregerade beteende" av en population av agenter (som vi föredrar att tänka på som paket) av massa n i=1  på i där varje paket har oändligt liten massa (därav namnet nonatomic). Vi kan se befolkningen som partitionerad i n-delpopulationer (en för varje vara) så att fraktionen av paket som tilldelas delpopulationen i är i /( i  på i ). I den tidigare definitionen av en icke-atomisk trängselspel, varje ren strategi är en del av insamlingen av resurser i E (dvs. de länkar som utgör den väg som den rena strategin motsvarar). Låta S e vara den uppsättning av rena strategier som tilldelar positivt flöde till resurs E, och låt x e flow tilldelas e, det vill säga x e = i-N,j-Se x j i. För varje resurs motsvarar e en ökande kostnadsfunktion c e (·) som mäter kostnaden (eller fördröjningen) för resursen som en funktion av x e. Fördröjningen c j i (x) av sökvägen j  på S i ges sedan av c j i (x) = elj c e (x e ), och det är lika med fördröjningen som ett paket (av vara i) lider när det skickas längs väg j under flödet x. Beckmann et al. [1956] visar att enligt de tidigare antagandena är själviska routingspel potentiella spel och att den potentiella funktionen är konvex; om fördröjningsfunktionen hos varje länk är en strikt ökande funktion av flödet i länken, då är den potentiella funktionen strikt konvex, i vilket fall Hofbauer och Sandholm [2009] visar att den kritiska punkten i den potentiella funktionen är ett GESS, ett ESS som är "överlägsen" mot varje annat tillstånd i det själviska routingspelet. Om inlärningshastigheten är tillräckligt stor, kan Hedge framkalla kaotiskt beteende. Vi visar denna möjlighet genom ett exempel på ett skalärt system som har period tre; detta innebär möjligheten av kaotiskt beteende av den berömda teorem att "period tre innebär kaos" [Li och Yorke, 1975]. Med tanke på att Hedge verkar på ett system med två parallella länkar ger upphov till ett skalar dynamiskt system, vårt exempel består av två länkar med kostnadsfunktioner c 1 (x) = x och c 2 (x) = 10 · x respektive, och en inlärningshastighet α som är lika med 5. Med hjälp av denna särskilda inställning (18) blir Om x 0, 1) är en punkt i en periodisk omlopp av period tre, tillämpa H tre gånger x ger tillbaka x, det vill säga H(H(H(x))) = x eller H 3 (x) = x. Figur 1 visar de fasta punkterna i H 3. Dessa inkluderar den fasta punkten i H (som en punkt av period ett trivialt också har period tre) och dessutom innehåller en periodisk omloppsbana av period tre som anges av pilarna visas i figuren. I återstoden av detta avsnitt, anser vi en självisk routing spel som består av parallella länkar (arcs) mellan ett par hörn, en källa och en destination. Vi utgår från att flödet från källa till destination är lika med ett (utan förlust av allmängiltighet) och att länkkostnadsfunktionerna är affina. Vårt mål är att visa att Wardrop jämvikten i en sådan självisk routing spel är attraktiv under Hedge med hjälp av en strategi baserad på linjärisering av motsvarande dynamiska systemet. Det första steget består av att beräkna den Jacobian matris av det dynamiska systemet som uppstår när vi använder Hedge för att distribuera (enhet) mängden flöde över systemet av parallella länkar; den Jacobian matrisen är naturligt beräknas vid motsvarande Wardrop jämvikt (som lätt visas vara unik förutsatt att sluttningarna av kostnadsfunktionerna är strikt positiva). Vårt mål är att visa att eigenvärdena av sådan jakobisk matris är (strikt) inne i enhetsdisken. (Vi uppnår detta mål för alla utom en del av system av parallella länkar av affin kostnadsfunktioner som har mäta noll.) För att avgränsa det område där eigenvärdena finns förlitar vi oss på Perron-Frobenius-teoremet och det mellanliggande värdet-teoremet. Enligt Perron-Frobenius-teoremet har en icke-negativ matris (dvs. en matris med icke-negativa poster) ett verkligt eigenvärde som är lika med dess spektralradie (definierat som modulen för det största in-modulvärdet). Det visar sig att för en tillräckligt liten inlärningstakt är jakobian verkligen en icke-negativ matris, vilket innebär att dess största i modul eigenvärde är verkligt. Resten av beviset syftar till att visa att detta eigenvärde är (begränsat) mindre än ett (vilket därför innebär att alla eigenvärden har en modul mindre än en och därmed att Wardrop-jämvikten är asymptotiskt stabil med en geometrisk konvergenshastighet nära jämvikten). Detta åstadkoms genom en kontinuitetsargumentering av det jakobinska och det mellanliggande värdeteoremets eigenvärden. 31 Kom ihåg (från dynamisk systemteori) att Jacobian J av en karta M vars domän och räckvidd är undergrupper av R m (den m-dimensionella Euclidean utrymme) vid en punkt x av domänen ges av: där de partiella derivata utvärderas vid x. Som tidigare nämnts, eftersom själviska routing spel är mer lämpligt sett ur ett minimeringsperspektiv, vi tog på det perspektivet i detta avsnitt med hjälp av små bokstäver, t.ex. x, för att beteckna flöden snarare än kapital fall. Vi kommer också att använda j som körindex för en länk (i stället för i). Låt oss ge Jacobian formeln vid en Wardrop jämvikt (i ett routing spel som består av parallella länkar) av fullt stöd (dvs. en jämvikt sådan att varje länk bär befolkningsmassa). Låt x = (x 1,. .., x m ) vara en sådan full stöd jämvikt (och därför också en fast punkt Hedge). Förutsatt (för enkelhet och utan förlust av generalitet) enhet efterfrågan, Jacobian J m av (18) vid x ges av: Här i betecknar en rad av Jacobian matrisen och j en kolumn. J m har eigen value noll (det är lätt att verifiera sina rader summa till noll). Vi tycker att det är praktiskt att använda deflation (se till exempel [Horn och Johnson, 1985]) för att få en fyrkantig matris K m, av storlek en mindre, vars egenvärden är de återstående egenvärden av J m. Det är möjligt att utföra deflationen på ett sådant sätt att den resulterande matrisen K m ges av följande uttryck: I ett system av m parallella länkar vars kostnadsfunktioner är affina och strängt ökande (det vill säga c j (x j ) = ρ j + σ j x j, σ j > 0), är en full-stöd jämvikt den unika lösningen av följande system av ekvationer: 32 Dessutom, K m förenklar enligt följande: I uppföljaren, visar vi att eigenvärden av J m är inne i enheten disk för en tillräckligt liten inlärningsgrad α. Låt oss därför påminna om definitionen av spektralradien. Denna förordning träder i kraft den tjugonde dagen efter det att den har offentliggjorts i Europeiska unionens officiella tidning. Om λ i, i = 1,..., m är eigenvärden för en fyrkantig matris A, då dess spektralradie ρ(A) definieras som ρ(A) := max i { tillλ i  på}. Vårt mål är att bevisa följande teorem (överväga fallet med fullt stöd jämvikt först). Teorin 6. Det finns en övre gräns för inlärningshastigheten > 0 så att om inlärningshastigheten α inte är större än denna övre gräns (dvs. 0 < α ≤ ska), är Jacobianens spektralradie vid en Wardrop-jämvikt av fullt stöd i ett system med m parallella länkar vars kostnadsfunktioner är affina (och har positiva sluttningar) mindre än en. När beviset för detta teorem är komplett, vi kommer att följa upp med fallet med Wardrop likvilibria har partiellt stöd (dvs jämviktsflödet i minst en länk är noll) ganska lätt. Genom att fortsätta med beviset, finner vi först en övre gräns på inlärningshastigheten så att för alla värden av inlärningshastigheten upp till denna övre gräns, jakobian är en icke-negativ matris. Detta innebär, genom Perron-Frobenius-teorem, att för alla sådana värden i inlärningshastigheten har jakobinen ett verkligt och positivt eigenvärde som är lika med dess spektralradie. - Lemma 7. - Vad är det? Betrakta ett system av m parallella länkar sådan att c j (x) = ρ j + σ j x j, σ j > 0, j = 1...., m vars Wardrop jämvikt har fullt stöd och antar att länkarna har numrerats så att ρ 1 ≥ ρ j, j = 2,..., m. Sedan finns det sådan att om 0 < α ≤ på K m har ett eigenvärde som är lika med dess spektral radie. Bevis. Eftersom ρ 1 ≥ ρ j, j = 2,..., m, de icke-diagonala posterna av K m är icke-negativa. Eftersom ρ j + σ j > ρ j + σ j x j = ρ 1 + σ 1 x 1 > ρ 1, if Således, genom en tillämpning av Perron-Frobenius teorem (se, till exempel, [Horn och Johnson, 1985, s. 503]), K m har ett (verkligt och positivt) eigenvärde som är lika med dess spektralradie. Sedan, för att visa att spektralradien är mindre än en (och därför alla eigenvärden är inne i enheten disk) vi förlitar oss på det mellanliggande värdet teorem. Vi tillämpar detta teorem på en funktion som kartlägger par bestående av vektorer av offset och sluttningar av länkarna till den största magnituden eigenvärde (som är verkligt och positivt) förutsatt att inlärningshastigheten är lika med ovan nämnda övre gräns. Låt oss beteckna denna funktion med f. Låtting ρ = (ρ 1,. .., ρ m ) och σ = (σ 1,................................................... ., σ m ), domänen f är utrymmet för alla parametrar (ρ, σ) som motsvarar system av m parallella länkar vars Wardrop jämvikt har fullt stöd. Dessutom f (ρ, σ) = ρ(K m) ( ska (ρ, σ), ρ, σ). Först visar vi att denna funktion är kontinuerlig, sedan visar vi att domänen för denna funktion är ansluten, och slutligen visar vi att jakoberna inte kan ha ett eigenvärde som är lika med ett. Lemma 8. f är en kontinuerlig funktion av ρ och σ. Bevis. Eigenvärdena för en matris är kontinuerliga funktioner hos grundämnena i matrisen, och grundämnena för K m (-(ρ, σ), ρ, σ) är kontinuerliga funktioner av ρ och σ. Därför, genom sammansättning, eigenvärden av K m är kontinuerliga funktioner av ρ och σ. Låt oss beteckna domänen f genom S. Vi har S = {(ρ, σ)  till R m × R m +  på x (ρ, σ) har fullt stöd } där R m är den m-dimensionella Euclidean utrymme och R m + är dess positiva ortant. - Lemma 9. - Vad är det? S är ansluten. Bevis. Det set {(ρ, σ 0 ) till x j > 0, j = 1,.., m, σ 0 är konstant} som resulterar om vi fixar sluttningarna och låt förskjutningarna variera är skärningspunkten mellan m öppna halvrymder (se Ekvation 21 ) och därför är det konvex, och därmed ansluten. Den uppsättning {(0, σ) till j > 0, j = 1,... m} som resulterar om vi fixerar offset till 0 och låter sluttningarna varierar också är ansluten eftersom det är homeomorfic till den öppna positiva ortanten av R m. Därför, S = {(ρ, σ) och j > 0, j = 1,...., m} är ansluten eftersom det är möjligt att ansluta två punkter (ρ, σ) och (ρ, σ ) i S enligt följande: (ρ, σ) → (0, σ) → (0, σ ) → (ρ, σ ). Det här är Lemma 10. K m har inte eigenvärde 1 för något värde av inlärningshastigheten. Bevis. För att bevisa att K m inte har eigenvärde 1, på grund av ekvation (20), räcker det att bevisa att K m, ges genom följande uttryck, Det är lätt att visa att det N (x 1 ) är täljaren av x 1 i (21). Därför, visar att det K m = (−1) m−1 det N (x 1 ) räcker för att slutföra beviset eftersom x 1 = 0 genom antagande. Vi utför elementära kolumnoperationer till N (x 1 ), multiplicera alla kolumner utom den första med −1 och sedan lägga den första kolumnen till alla andra kolumner, för att få följande matris Vi är nu redo att dra slutsatsen, med det mellanliggande värdet teorem, att antingen alla system av parallella länkar med affin kostnadsfunktioner och positiva sluttningar är instabila (har en spektral radie större än en) eller de är asymptotiskt stabila. Vi bevisar det senare genom att ge ett exempel på ett system som är asymptotiskt stabilt. Exemplet ges i nästa lemma. - Lemma 11. - Vad är det? I ett system som består av m parallella länkar sådana att c j (x j ) = σ j x j, σ j > 0, j = 1,...., m, det finns en. > 0 sådan att, om 0 < α ≤ till, Eigenvärdena av K m är inne i enheten disk. Bevis. Notera först att Wardrop jämvikten har fullt stöd (i alla sådana system av parallella länkar), och därför K m ges av (22). Observera nu att om ρ 1 = · · · = ρ m = 0, då K m är diagonal, och, därför, om α < β min{ 2 x j σ j}, j = 2,...., m, för varje β sådan att 0 < β < 1, då K m har spektralradie mindre än 1. Detta kompletterar beviset. Observera att beviset för Theorem 6 nu är komplett.
Möjligheten att tillämpa Li-Yorke typ argument för MWU i trängsel spel med två agenter inspirerades av en anmärkning i REF för fallet med continuum av agenter.
Evolutionary stability implies asymptotic stability under multiplicative weights
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}