Ekstensivformspill og spilltre

Et dynamisk spill representeres som et spilltre der noder er beslutningspunkter og grener er handlinger. I et sekvensielt spill med perfekt informasjon observerer hver spiller alle tidligere handlinger. Eksempel: spiller 1 velger mellom å og B; spiller 2 observerer valget og velger deretter mellom C, D, E og F.

Strategi i dynamiske spill

En strategi for spiller 2 i det dynamiske spillet er en komplett plan som spesifiserer hvilken handling hun velger for hver informasjonsnode hun kan nå. Hvis spiller 2 kan nå to informasjonsnoder (én etter A og én etter B), har hun \(4 \times 4 = 16\) mulige strategier. Dette er langt flere enn i det statiske spillet.

Baklengs induksjon

Baklengs induksjon (backward induction) er løsningsmetoden for sekvensielle spill med perfekt informasjon. Vi starter ved de siste beslutningsnodene og arbeider oss bakover:

Identifiser hvilken handling den siste spilleren vil velge i hvert subspill.
Gitt disse valgene, identifiser hva den forrige spilleren velger.
Gjenta til vi når rotnoden.

Delspill-perfekt Nash-likevekt (SPNE)

En delspill-perfekt Nash-likevekt er en strategikombinasjon som utgjør en Nash-likevekt i hvert delspill av det totale spillet. SPNE eliminerer ikke-troverdige trusler: en trussel er ikke troverdig dersom det ikke er optimalt å gjennomføre den dersom man faktisk kommer til den noden. Baklengs induksjon gir alltid SPNE i spill med perfekt informasjon og endelig antall perioder.

Eksempel – Fra statisk til dynamisk spill

Vi bruker et nytt spill der spiller 1 (rad I eller U) velger først, og spiller 2 (kolonne g, k) observerer valget før hun velger. Første tall er nytten til spiller 1:

\(\begin{array}{c|cc} & g & k \\ \hline \text{I} & 2,2 & -1,-1 \\ \text{U} & 0,3 & 0,3 \end{array}\)

Spiller 2s delspill etter I: velger g (2 > −1). (Etter U er utfallet (0,3) uansett, så valget er irrelevant.)

Spiller 1 velger: I gir 2 (siden spiller 2 da velger g), U gir 0. Spiller 1 velger derfor I.

SPNE (baklengs induksjon): Spiller 1 velger I, spiller 2 velger g etter I.

Eksempel – Ikke-troverdig trussel

I spillet over kan spiller 2 true med: «Hvis du velger I, velger jeg k.» Det ville gitt spiller 1 nytte −1, så spiller 1 ville da heller valgt U (gir 0). Strategikombinasjonen «spiller 1 velger U, spiller 2 ville valgt k etter I» er faktisk en Nash-likevekt – ingen tjener på ensidig avvik gitt den andres strategi. Men den er ikke delspill-perfekt: hvis spiller 1 faktisk velger I, er k ikke optimalt for spiller 2 (g gir 2 mot −1 for k). Trusselen er ikke troverdig, og baklengs induksjon eliminerer denne likevekten.

Studieguide: Dynamisk spillteori og delspill-perfeksjon

Studieguide: Dynamisk spillteori og delspill-perfeksjon