Abstrakt. En individs inlärningsregel är helt frikopplad om den inte är beroende av någon annans handlingar eller belöningar. Vi föreslår en variant av log linjär inlärning som är helt frikopplad och som väljer en effektiv ren Nash jämvikt i alla generiska nperson spel som har minst en ren Nash jämvikt. I spel som inte har en sådan jämvikt, det finns en enkel formel som uttrycker den långsiktiga sannolikheten för de olika disequilibrium tillstånd i termer av två faktorer: i) summan av utbetalningar över alla agenter, och ii) den maximala vinst som är resultatet av en unilateral avvikelse av någon agent. Detta välfärd / stabilitet kompromiss-off kriterium ger en ny ram för att analysera valet av disequilibrium samt jämviktstillstånd i n-person spel. JEL: C72, C73 2 Spelteorin har traditionellt fokuserat på situationer som involverar ett litet antal spelare. I dessa miljöer är det vettigt att anta att spelarna känner till spelets struktur och kan förutsäga sina motståndares strategiska beteende. Men det finns många situationer med ett stort antal spelare där dessa antaganden inte är särskilt övertygande. Kommunister i stadstrafik är engagerade i ett spel eftersom varje persons val av rutt påverkar körtiden för många andra förare, men det är tveksamt om någon "vet spelet" eller helt tar hänsyn till de andra spelarnas strategier som vanligtvis ges i spelteori. Andra exempel är förfaranden för att routing data på internet, och utformningen av protokoll information delning för distribuerade sensorer som försöker lokalisera ett mål. Dessa typer av spel utgör nya och utmanande frågor. Kan sådana system likriktas även om agenter är omedvetna om de flesta (eller kanske alla) av de andra agenternas strategier och beteenden? Vilka regler för adaptiv inlärning är meningsfulla i sådana miljöer? Hur lång tid tar det att nå jämvikt om man antar att man kan nå den över huvud taget? Och vad kan sägas om de välfärdsegenskaper hos jämvikten som är ett resultat av särskilda inlärningsregler? Under de senaste åren har undersökningen av dessa frågor utvecklats snabbt bland datavetare och distribuerade kontrollteoretiker (Papadimitriou, 2001; Roughgarden, 2005; Mannor och Shamma, 2007; Marden och Shamma, 2008; Asadpour och Saberi, 2009; Shah and Shin, 2010). Samtidigt spel teoretiker har undersökt frågan om decentraliserade regler kan utformas som konvergerar till Nash jämvikt (eller korrelerad jämvikt) i allmänna n-person spel Mas-Colell, 2003, 2006; Young, 2003, 2006; Hart och Mansour, 2010). Bland kontrollteoretiker och dataforskare är frågan inte om en given inlärningsregel är beskrivande exakt som en modell för mänskligt beteende, utan om det leder till bra systemomfattande prestanda när agenter är utrustade med detta beteende; med andra ord inlärningsproceduren och agenternas belöningar behandlas som konstruktionselement i systemet. Hittills har fokus legat på potentiella spel, eftersom dessa uppstår ofta i tillämpningar (Marden och Shamma, 2008;. För denna klass av spel finns det extremt enkla och intuitivt tilltalande inlärningsförfaranden som 3 gör att systemet att jämvikt från alla ursprungliga förhållanden. Ett anmärkningsvärt exempel är logitinlärning, där en agent väljer åtgärder med logsannolikhet som är en linjär funktion av deras utdelningar. I detta fall sker jämvikten på ett lokalt eller globalt maximum av den potentiella funktionen. Den potentiella funktionen behöver dock inte mäta det totala välbefinnandet hos smittämnena, varför den valda jämvikten kan vara ganska ineffektiv. Detta är ett välkänt problem i t.ex. trängselspel. Problemet med ineffektivt jämviktsval kan lösas genom ett prissättningssystem för överbelastning, men detta kräver någon typ av centraliserad (eller åtminstone inte helt decentraliserad) mekanism för att fastställa priset på varje linje (Sandholm, 1998). Bidraget från denna uppsats är att visa en enkel inlärningsregel som införlivar log linjärt lärande som en komponent, och som väljer en effektiv jämvikt i alla spel med generiska payoffs som har minst en ren Nash jämvikt. (En jämvikt är effektiv om det inte finns någon annan jämvikt där någon har det bättre och ingen har det sämre.) Med "select" menar vi att processen, från godtyckliga inledande förhållanden, befinner sig i en effektiv jämvikt i en hög andel av alla tidsperioder. Vår inlärningsregel är helt frikopplad, dvs. uppdateringsförfarandet beror inte på någon annans handlingar eller utbetalningar. Således kan det genomföras även i miljöer där spelarna vet ingenting om spelet, eller ens om de är i ett spel. Allt de gör är att reagera på mönstret för den senaste tidens belöningar, i stort sett som när det gäller att förstärka lärandet (även om regeln skiljer sig åt i vissa viktiga avseenden från att förstärka lärandet). Vår uppfattning om urval - i jämvikt en hög andel av tiden - är avgörande för detta resultat. Det är inte sant att processen konvergerar till jämvikt eller ens att den konvergerar till jämvikt med hög sannolikhet. Det kan faktiskt visas att för allmänna n-person spel finns det inga helt okopplade regler med ändligt minne som väljer en Nash jämvikt i denna starkare betydelse (Babichenko, 2010; se även Hart och Mas-Colell, 2003, 2006). Den inlärningsregel som vi föreslår är relaterad till försöks- och felinlärningsförfarandet för Young (2009), och mer avlägset relaterad till "inlärning genom provtagning" förfarandet för Foster och Young (2006) och Germano och Lugosi (2007). 1 En väsentlig del av regeln är att en spelare har två olika söklägen: i) avsiktliga experiment, som inträffar med låg 1 En annan avlägsen släkting är aspiration-baserad inlärningsmodell av Karantikar et al. (1998)................................................................................................. I detta förfarande varje spelare har en endogen genererad aspirationsnivå som är baserad på ett utjämnat genomsnitt av hans tidigare 4 sannolikhet och leder till en förändring av strategin endast om den senare har en högre payoff; ii) slumpmässig sökning, vilket leder till en förändring av strategin som kan eller kanske inte har en högre payoff (sannolikheten för acceptans är bara partisk mot strategier med hög payoff). En avgörande skillnad mellan vårt förfarande och försöks- och felinlärning är att en spelare inte alltid accepterar resultatet av ett experiment även när det resulterar i högre utbetalningar: acceptans är probabilistisk. Vår regel skiljer sig också åt genom att sannolikheten för att acceptera resultatet av ett experiment (eller en slumpmässig sökning) kan uttryckas som en log linjär funktion av vinst (i fallet med ett experiment) eller vinstnivå (i fallet med en slumpmässig sökning). Fördelen med detta tillvägagångssätt är att det leder till en enkel formel för att beräkna stokastiskt stabila tillstånd i processen. Denna formel visar att inlärningsprocessen väljer en effektiv ren Nash jämvikt när en ren Nash jämvikt existerar, och identifierar disequilibrium tillstånd som väljs när en ren Nash jämvikt inte existerar. I det senare fallet finns det en avvägning mellan välfärd och stabilitet: den mest sannolika obalansen är en stat som maximerar en linjär kombination av: i) den totala välfärden (summan av ersättningar) över alla agenter och ii) den vinst som skulle bli resultatet av en avvikelse av någon agent, där den första viktas positivt och den andra negativt. Först beskriver vi inlärningsregeln informellt, sedan ger vi en detaljerad definition. Ett viktigt inslag i regeln är att en agent kan söka på ett av två sätt. I "tyst" sökande han ibland experimenterar med nya strategier och antar en ny med en sannolikhet som ökar med den realiserade vinsten i payoff jämfört med hans tidigare strategi. I "noisy" sökande försöker han ofta ut nya strategier och antar en ny med en sannolikhet som ökar i den realiserade nivån av payoff. Dessa två former av sökning kan associeras med olika "psykologiska tillstånd". En innehållsagent är inte starkt motiverad att söka men ibland gör det ändå (tyst sökning). En missnöjd agent fladdrar runt och prövar ut nya saker ofta (buller sökande). I den första typen av sökning bestäms sannolikheten för acceptans av förändringen i avlöning, medan i den andra situationen sannolikheten för acceptans bestäms av avlöningsnivån. Motivet är att en agent i ett bullrande sökande försöker sig på många olika belöningar. Han ändrar strategi med positiv sannolikhet om hans nuvarande lön faller under hans nuvarande ambitioner. Till skillnad från den nuvarande metoden, detta förfarande leder inte nödvändigtvis till Nash jämvikt beteende även i 2 x 2 spel. 5 strategier innan avveckling på en av dem, därav payoff nivån verkar mer framträdande än förändringen i payoff från föregående period. Ett andra inslag i inlärningsprocessen är den mekanism som utlöser övergångar mellan innehålls- och missnöjesstater. Den grundläggande tanken är att en övergång från innehåll (c) till
En ny naturlig dynamik som konvergerar till Nash equilibria med optimal social välfärd i allmänna spel har föreslagits i REF.
Learning Efficient Nash Equilibria in Distributed Systems
{'venue': None, 'journal': None, 'mag_field_of_study': ['Computer Science', 'Economics']}