Epsilon-jämvikt

Epsilon-jämvikt
Ett lösningskoncept i spelteori
Relationship
Superset av	Nash jämvikt
Betydelse
Används för	stokastiska spel

I spelteorin är en epsilon-jämvikt , eller nära-Nash-jämvikt, en strategiprofil som ungefär uppfyller villkoret för Nash-jämvikt . I en Nash-jämvikt har ingen spelare ett incitament att ändra sitt beteende. I en ungefärlig Nash-jämvikt är detta krav försvagat för att tillåta möjligheten att en spelare kan ha ett litet incitament att göra något annorlunda. Detta kan fortfarande anses vara ett adekvat lösningskoncept, om man till exempel antar status quo-bias . Detta lösningskoncept kan föredras framför Nash-jämvikt på grund av att det är lättare att beräkna, eller alternativt på grund av möjligheten att i spel med fler än 2 spelare behöver sannolikheterna som är involverade i en exakt Nash-jämvikt inte vara rationella tal .

Definition

Det finns mer än en alternativ definition.

Standarddefinitionen

Givet ett spel och en verklig icke-negativ parameter ${\displaystyle \varepsilon } sägs$ en strategiprofil vara en $\varepsilon$ -jämvikt om det inte är möjligt för någon spelare att få mer än ${\ displaystyle \varepsilon }$ i förväntad utdelning genom att ensidigt avvika från sin strategi . Varje Nash-jämvikt är ekvivalent med en $\varepsilon$ -jämvikt där $\varepsilon =0$ .

Formellt, låt $G=(N,A=A_{1}\times \dotsb \times A_{N}, u\colon A\to R^{N})$ vara ett $N$ -spel med actionuppsättningar $A_{i}$ för varje spelare $i$ och hjälpfunktion $u$ . Låt $u_{i}(s)$ beteckna utdelningen till spelare $i$ när strategiprofilen $s$ spelas. Låt $\Delta _{i}$ vara utrymmet för sannolikhetsfördelningar över $A_{i}$ . En vektor av strategier ${\displaystyle \sigma \in \Delta =\Delta _{1}\times \dotsb \times \Delta _{N}} är$ en $\varepsilon$ -Nash Equilibrium för $G$ if

$-i})-\varepsilon }$${\displaystyle u_{i}(\sigma )\geq u_{i}(\sigma _{i}^{'},\sigma _$$\sigma _{i}^{'}\in \Delta _{i},i\in N.$ för alla

Väl underbyggd ungefärlig jämvikt

Följande definition ställer det starkare kravet att en spelare endast får tilldela positiv sannolikhet till en ren strategi $a$ om utdelningen för $a$ har förväntat utdelning högst $\varepsilon$ mindre än bästa svarsutdelningen. Låt $x_{s}$ vara sannolikheten för att strategiprofilen $s$ spelas. För spelare $p$ låt $S_{-p}$ vara strategiprofiler för andra spelare än $p$ ; för $s\in S_{-p}$ och en ren strategi $j$ av $p$ låt $js$ vara strategiprofilen där ${ \displaystyle p}$ spelar $j$ och andra spelare spelar $s$ . Låt $u_{p}(s)$ vara utdelningen till $p$ när strategiprofilen $s$ används. Kravet kan uttryckas med formeln

$\sum _{s\in S_{-p}}u_{p}(js)x_{s}>\varepsilon +\sum _{s\in S_{-p}}u_{p}(j's)x_{s}\Longrightarrow x_{j '}^{p}=0.$

Resultat

Förekomsten av ett polynom-tidsapproximationsschema (PTAS) för ε-Nash-jämvikter är ekvivalent med frågan om det finns ett för ε-välstödda approximativa Nash-jämvikter, men förekomsten av en PTAS förblir ett öppet problem. För konstanta värden på e är polynomtidsalgoritmer för ungefärliga jämvikter kända för lägre värden på e än vad som är känt för väl understödda ungefärliga jämvikter. För spel med utdelningar i intervallet [0,1] och ε=0,3393 kan ε-Nash-jämvikter beräknas i polynomtid. För spel med utdelningar i intervallet [0,1] och ε=2/3, ε-brunn- stödda jämvikter kan beräknas i polynomtid

Exempel

Begreppet ε-jämvikter är viktigt i teorin om stokastiska spel av potentiellt oändlig varaktighet. Det finns enkla exempel på stokastiska spel utan Nash-jämvikt men med en ε-jämvikt för alla ε som är strikt större än 0.

Det kanske enklaste exemplet är följande variant av Matching Pennies , som föreslagits av Everett. Spelare 1 gömmer ett öre och spelare 2 måste gissa om det är heads up eller tails up. Om spelare 2 gissar rätt vinner han penny från spelare 1 och spelet slutar. Om spelare 2 felaktigt gissar att öre är heads up, slutar spelet med noll utdelning till båda spelarna. upprepas spelet . Om spelet fortsätter för evigt är utdelningen till båda spelarna noll.

Givet en parameter ε > 0, är ​​varje strategiprofil där spelare 2 gissar head up med sannolikhet ε och svansar upp med sannolikhet 1 − ε (i varje steg av spelet, och oberoende av tidigare steg) en ε -jämvikt för spelet. Den förväntade utdelningen för spelare 2 i en sådan strategiprofil är minst 1 − ε . Det är dock lätt att se att det inte finns någon strategi för spelare 2 som kan garantera en förväntad utdelning på exakt 1. Därför har spelet ingen Nash-jämvikt .

Ett annat enkelt exempel är det ändligt upprepade fångdilemmat för T-perioder, där utdelningen beräknas i medeltal över T-perioderna. Den enda Nash-jämvikten i detta spel är att välja Defekt i varje period. Tänk nu på de två strategierna tit-for-tat och grim trigger . Även om varken tit-for-tat eller grim trigger är Nash-jämvikter för spelet, är båda $\epsilon$ -jämvikter för vissa positiva $\epsilon$ . De acceptabla värdena för $\epsilon$ beror på utdelningen av det ingående spelet och på antalet T av perioder.

används begreppet en ren strategi epsilon-jämvikt när den blandade strategin ses som orealistisk. I en ren strategi epsilon-jämvikt väljer varje spelare en ren strategi som ligger inom epsilon av sin bästa rena strategi. Till exempel, i Bertrand–Edgeworth-modellen , där ingen ren strategijämvikt existerar, kan en ren strategiepsilon-jämvikt existera.

Inline-citat

Källor

• H Dixon Approximate Bertrand Equilibrium in a Replicated Industry , Review of Economic Studies, 54 (1987), sidorna 47–62.
• H. Everett. "Rekursiva spel". I HW Kuhn och AW Tucker, redaktörer. Bidrag till teorin om spel, vol. III, volym 39 av Annals of Mathematical Studies . Princeton University Press, 1957.
•   Leyton-Brown, Kevin; Shoham, Yoav (2008), Essentials of Game Theory: A Concise, Multidisciplinary Introduction , San Rafael, CA: Morgan & Claypool Publishers, ISBN 978-1-59829-593-1 . En 88-sidig matematisk introduktion; se avsnitt 3.7. Gratis online på många universitet.
• R. Radner . Samverkansbeteende i icke-kooperativa epsilonjämvikter av oligopol med långa men begränsade liv, Journal of Economic Theory, 22 , 121–157, 1980.
•   Shoham, Yoav; Leyton-Brown, Kevin (2009), Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations, New York: Cambridge University Press , ISBN 978-0-521-89943-7 . En omfattande referens ur ett beräkningsperspektiv; se avsnitt 3.4.7. Nedladdningsbar gratis online .
• SH Tijs. Nash equilibria for noncooperative n -person games in normal form , SIAM Review, 23 , 225–237, 1981.