Normalt spil - Normal-form game

I spilteori er normal form en beskrivelse af et spil . I modsætning til omfattende form er repræsentationer i normal form ikke i sig selv grafiske , men snarere repræsenterer spillet ved hjælp af en matrix . Selvom denne tilgang kan være mere nyttig til at identificere strengt dominerede strategier og Nash-ligevægte , går nogle oplysninger tabt i forhold til repræsentationer i omfattende form. Den normale repræsentation af et spil inkluderer alle synlige og tænkelige strategier og deres tilhørende gevinster for hver spiller.

I statiske spil med komplet , perfekt information , er en normal repræsentation af et spil en specifikation af spillernes strategirum og udbetalingsfunktioner. Et strategirum for en spiller er sættet med alle strategier, der er til rådighed for den pågældende spiller, hvorimod en strategi er en komplet handlingsplan for hver fase af spillet, uanset om den fase faktisk opstår i spillet. En udbetalingsfunktion for en spiller er en kortlægning fra krydsproduktet fra spillernes strategirum til spillerens sæt af udbetalinger (normalt sættet med reelle tal, hvor tallet repræsenterer en kardinal eller ordinal nytteværdi- ofte kardinal i normalform repræsentation) af en spiller, dvs. en spillers udbetalingsfunktion tager som input en strategiprofil (det er en specifikation af strategier for hver spiller) og giver en repræsentation af payoff som output.

Et eksempel

Den medfølgende matrix er en repræsentation i normal form af et spil, hvor spillerne bevæger sig samtidigt (eller i det mindste ikke observerer den anden spillers træk, før de foretager deres eget) og modtager gevinsten som specificeret for kombinationerne af handlinger, der spilles. For eksempel, hvis spiller 1 spiller top og spiller 2 spiller til venstre, modtager spiller 1 4 og spiller 2 modtager 3. I hver celle repræsenterer det første tal udbetalingen til rækspilleren (i dette tilfælde spiller 1) og det andet nummer repræsenterer udbetalingen til kolonneafspilleren (i dette tilfælde spiller 2).

Andre repræsentationer

En delvis topologi af to-spiller, to-strategispil, herunder spil som fangenes dilemma , hjortejagt og kylling

Ofte er symmetriske spil (hvor gevinsten ikke afhænger af hvilken spiller, der vælger hver handling) repræsenteret med kun én udbetaling. Dette er gevinsten for rækspilleren. For eksempel repræsenterer udbetalingsmatricerne til højre og venstre nedenfor det samme spil.

Det topologiske område med spil med tilhørende udbetalingsmatricer kan også kortlægges, hvor tilstødende spil har de mest lignende matricer. Dette viser, hvordan trinvise incitamentændringer kan ændre spillet.

Anvendelser af normal form

Dominerede strategier

Udbetalingsmatricen letter eliminering af dominerede strategier , og den bruges normalt til at illustrere dette koncept. For eksempel kan vi i fangens dilemma se, at hver fange enten kan "samarbejde" eller "defekte". Hvis præcis den ene fange defekterer, kommer han let af, og den anden fange er låst inde i lang tid. Men hvis de begge defekter, vil de begge blive låst inde i kortere tid. Man kan bestemme, at Cooperate er strengt domineret af Defekt . Man skal sammenligne de første tal i hver kolonne, i dette tilfælde 0> −1 og −2> −5. Dette viser, at uanset hvad kolonneafspilleren vælger, gør rækspilleren det bedre ved at vælge Defekt . På samme måde sammenligner man den anden udbetaling i hver række; igen 0> −1 og −2> −5. Dette viser, at uanset hvilken række der gør, gør kolonnen det bedre ved at vælge Defekt . Dette demonstrerer den unikke Nash -ligevægt i dette spil ( Defekt , Defekt ).

Sekventielle spil i normal form

Både omfattende og normal formillustration af et sekventielt spil med underspil ufuldkommen og perfekt Nash -ligevægt markeret med henholdsvis rød og blå.

Disse matricer repræsenterer kun spil, hvor træk er samtidige (eller mere generelt er information ufuldkommen ). Ovenstående matrix repræsenterer ikke det spil, hvor spiller 1 bevæger sig først, observeret af spiller 2, og derefter spiller 2 bevæger sig, fordi den ikke specificerer hver af spiller 2's strategier i dette tilfælde. For at repræsentere dette sekventielle spil skal vi specificere alle spiller 2's handlinger, selv i tilfælde, der aldrig kan opstå i løbet af spillet. I dette spil har spiller 2 handlinger, som før, Venstre og Højre . I modsætning til før har han fire strategier, afhængig af spiller 1's handlinger. Strategierne er:

1. Venstre hvis spiller 1 spiller Top og Venstre ellers
2. Venstre hvis spiller 1 spiller Top og højre ellers
3. Højre hvis spiller 1 spiller Top og Venstre ellers
4. Højre hvis spiller 1 spiller Top og højre ellers

Til højre ses dette spil i normal form.

Generel formulering

For at et spil skal være i normal form, får vi følgende data:

Der er et begrænset sæt I af spillere, hver spiller er betegnet med i . Hver spiller jeg har en endelig k antal rene strategier

${\ displaystyle S_ {i} = \ {1,2, \ ldots, k \}.}$

EN ren strategiprofil er en sammenslutning af strategier til spillere, det vil sige enI-tuple

${\ displaystyle {\ vec {s}} = (s_ {1}, s_ {2}, \ ldots, s_ {I})}$

sådan

${\ displaystyle s_ {1} \ i S_ {1}, s_ {2} \ i S_ {2}, \ ldots, s_ {I} \ i S_ {I}}$

EN udbetalingsfunktion er en funktion

${\ displaystyle u_ {i}: S_ {1} \ gange S_ {2} \ gange \ ldots \ gange S_ {I} \ højrepil \ mathbb {R}.}$

hvis tilsigtede fortolkning er prisen, der gives til en enkelt spiller ved spillets udfald. Derfor skal udbetalingsfunktionen specificeres for hver spiller i spillersættet I = {1, 2, ..., I } for at angive et spil fuldstændigt .

Definition : Et spil i normal form er en struktur

${\ displaystyle \ mathrm {T} = \ langle I, \ mathbf {S}, \ mathbf {u} \ rangle}$

hvor:

${\ displaystyle I = \ {1,2, \ ldots, I \}}$

er et sæt spillere,

${\ displaystyle \ mathbf {S} = \ {S_ {1}, S_ {2}, \ ldots, S_ {I} \}}$

er en I -dobbelte af rene strategisæt, et til hver spiller og

${\ displaystyle \ mathbf {u} = \ {u_ {1}, u_ {2}, \ ldots, u_ {I} \}}$

er en I -dobbelte af udbetalingsfunktioner.

Referencer

• Fudenberg, D .; Tirole, J. (1991). Spelteori . MIT Tryk. ISBN 0-262-06141-4.
• Leyton-Brown, Kevin; Shoham, Yoav (2008). Essentials of Game Theory: En kortfattet, tværfaglig introduktion . San Rafael, CA: Morgan & Claypool Publishers. ISBN 978-1-59829-593-1.. En matematisk introduktion på 88 sider; gratis online på mange universiteter.
• Luce, RD ; Raiffa, H. (1989). Spil og beslutninger . Dover Publications. ISBN 0-486-65943-7.
• Shoham, Yoav; Leyton-Brown, Kevin (2009). Multiagent-systemer: Algoritmisk, spilteoretisk og logisk fundament . New York: Cambridge University Press . ISBN 978-0-521-89943-7.. En omfattende reference fra et beregningsmæssigt perspektiv; se kapitel 3. Kan downloades gratis online .
• Weibull, J. (1996). Evolutionær spilteori . MIT Tryk. ISBN 0-262-23181-6.
• J. von Neumann og O. Morgenstern , Theory of games and Economic Behavior , John Wiley Science Editions, 1964. Som oprindeligt blev udgivet i 1944 af Princeton University Press.