Spillteori

John von Neumann er den matematiske spillteoriens opphavsmann.

John F. Nash ga viktige bidrag til spillteorien og introduserte den for den økonomiske forskning.

Spillteori er en matematisk teori som anvendes for å simulere atferd og valgsituasjoner for aktører som står overfor gitte handlingsalternativer, og hvordan de velger i møte med på forhånd kjente konsekvenser av ulike valgutfall. Hensikten med spillteori er å simulere komplekse prosesser og utviklingsforløp, hvor flere aktører handler med eller uten informasjon om andre aktørers strategi. Gitt rasjonell atferd studeres det også hvordan ulike forventninger om belønning eller straff påvirker aktørenes atferd i de studerte situasjonene.

Spillteori benyttes innenfor blant annet militærteori, informatikk, kybernetikk, økonomi, sosiologi, statsvitenskap og evolusjonsbiologi. Spillteori er også nyttig i situasjoner med forhandling, eller i kompliserte auksjonsforløp. Teorien forsøker å modellere og forstå individuelle valg og gruppeatferd i strategiske situasjoner, særlig der hvor resultatet av enkeltindividets valg avhenger av andre aktørers valg. Opprinnelig fokuserte spillteorien på nullsumspill hvor én aktørs suksess skjedde på bekostning av én eller flere andre aktører, men er etterhvert utvidet til å anvendes i studier av en rekke valgsituasjoner og handlingssituasjoner for rasjonelle menneskelige aktører, biologiske aktører, eller sågar maskiner. Ofte søker studiene å finne ulike former for likevekt eller optimale resultater i de strategiske spillsituasjonene, for eksempel en likevekt hvor alle aktører har gjort valg de ikke angrer på, eller resultater hvor noen har fått det bedre uten at andre har fått det verre. Nashlikevekt og paretooptimalitet er eksempler på ofte søkte resultater.

Historie

Spillteori ble utviklet av ungarsk-amerikaneren John von Neumann i 1928, men oppstod som eksplisitt matematisk teoriverk og disiplin i 1944 da von Neumann og Oskar Morgenstern publiserte: Theory of Games and Economic behavior. På 1950-tallet ble det forsket intensivt innen spillteori, ikke minst ved RAND Corporation i California, som simulerte utfall av atomkrig. Spillteori ble introdusert i biologisk forsking på 1970-tallet. Viktige anvendelser i biologien er studiet av hvordan biologiske systemer og økosystemer kan utvikle seg under visse betingelser, og i kombinasjon med menneskelig påvirkning.

Opprinnelig beskriver spillteori en situasjon med to spillere og deres mulige strategier overfor hverandre. Et kjent eksempel på problemstillinger innen spillteori er Fangens dilemma. Innenfor samfunnsøkonomien videreutviklet nobelprisvinner og matematikeren John Forbes Nash jr. – figuren i filmen Et vakkert sinn – teorien til å omfatte mer enn to spillere. Andre viktige økonomer som har utviklet spillteorien, er Kenneth Arrow og John Maynard Smith. I Norge er professor Nils Henrik von der Fehr en representant for spillteoretikere innen samfunnsøkonomien. Professor Aanund Hylland er regnet som en av Norges fremste spillteoretikere.^{[trenger referanse]} Spillteori anvendes i økonomisk forskning blant annet til å simulere framtidig investering, sparing, konsum eller annen atferd i et marked eller en nasjonal økonomi under ulike betingelser for skattlegging, rente, prisutvikling, osv. Hele åtte spillteoretikere har vunnet Nobels minnepris i økonomi.

Typer av spill

I spillteori modelleres stilistiske strategiske situasjoner som forenkles for å muliggjøre matematisk analyse og simulering. Et antall aktører tildeles et begrenset antall strategiske trekk som kan gjøres i en viss rekkefølge. Det spesifiseres visse individuelle belønninger for hver kombinasjon av handlingsvalg.

Enkelt spill med belønningsverdier.
Her er aktør 1 representert til venstre og aktør 2 øverst. Vi ser at begge aktørenes belønning avhenger av den andres valg, ingen av aktørene kan følge en dominant strategi som gir beste resultat uavhengig av hva den andre gjør.

	Aktør 2 velger venstre	Aktør 2 velger høyre
Aktør 1 velger topp	4, 3	-1, -1
Aktør 1 velger bunn	0, 0	3, 4

Eksempel på illustrasjon av komplisert spill. Aktør 1 velger først enten F eller U. Aktør 2 ser den første aktørens valg og kan selv velge A eller R. Gitt at aktør 1 velger U og aktør 2 velger A, vil aktør 1 i dette tilfellet få 8 i belønning, mens aktør 2 får 2 i belønning.

Enkle spill på såkalt normal form med to eller få aktører representeres gjerne grafisk i en matriseform, hvor aktører og handlingsvalg grupperes med tilhørende gevinst eller negativt resultat. Man kan illustrere to aktører på henholdsvis rekke eller kolonne i en firefeltstabell dersom de har to strategiske trekk å velge mellom, i seksfeltstabell hvis de har tre mulige trekk hver, osv. Aktørene i et slikt normalt spill handler simultant eller tilnærmet simultant og kjenner normalt ikke til de andre aktørenes handlingsvalg. Det klassiske Fangens dilemma er et slikt enkelt spill med to aktører som ikke kjenner hverandres handlinger i de strategiske valgsituasjonene.

Kombinasjonen av belønning avgjør om det finnes en dominant strategi aktørene kan følge, det vil si en strategi som gir den enkelte aktør beste resultat uavhengig av hva andre aktører gjør. Dersom det finnes slike dominante strategier for alle, kan man oppnå Nash-likevekt hvor ingen aktør angrer sine valg når spillsituasjonen er overstått. I spillet til høyre ser vi derimot at en slik likevekt ikke kan oppnås, hver aktørs belønning ved hvert valgalternativ er her helt avhengig av hva den andre velger.

Kompliserte spill på såkalt utvidet form er mer avanserte, for eksempel ved at det er mange spillere, at enkelte av dem har mer informasjon eller fler handlingsvalg enn andre, eller ved at aktørene handler i rekkefølge og delvis kjenner til de andre aktørenes trekk. Grafisk illustreres slike spill ofte i en forgrenet trestruktur hvor sekvenser av handlingsvalg medfører at aktørenes handlinger skiller lag eller berører hverandre. I modellen kan man velge hvorvidt aktørene skal se hverandres valg og hvorvidt de skal se underveis hvor de befinner seg, også i forhold til de andre aktørene. Når det tilgjengelige antall handlingsvalg (illustrert som forgreninger) er gjennomført, framstår aktørenes belønning under den node deres handlingssekvens ender ved.

Symmetriske og asymmetriske spill

Asymmetrisk spill

	E	F
E	1, 2	0, 0
F	0, 0	1, 3

Et symmetrisk spill er et spill hvor belønningen for å velge en gitt strategi kun avhenger av de andre aktørenes strategier, og ikke av hvem som velger hvilke strategier. Hvis aktørene kunne bytte plass uten at spillets utfall ville blitt annerledes, er spillet symmetrisk. Mange vanlige 2×2-spill er symmetriske. Standardgjengivelsen av fangens dilemma er et symmetrisk spill, selv om det også kan studeres som et asymmetrisk spill.

De mest normale asymmetriske spill er spill hvor aktørene har forskjellige mulige strategier, men et spill kan gjerne ha identiske strategier og likevel være asymmetrisk. For eksempel er spillet til høyre asymmetrisk, på tross av at strategiene for de to aktørene er like.

Nullsumspill

Utdypende artikkel: Nullsumspill

Nullsumspill

	A	B
A	-1, 1	3, -3
B	0, 0	-2, 2

Nullsumspill er et spesialtilfelle av konstantsumspill, hvor aktørenes valg hverken kan øke eller redusere de tilgjengelige ressurser. I nullsumspill er den samlede belønning for alle aktører, for hver eneste strategikombinasjon lik null, slik at en aktør kun kan oppnå positiv belønning på bekostning av andre. Poker er et eksempel på et nullsumspill hvor man vinner nøyaktig det beløp motstanderne taper. Blant andre nullsumspill kan nevnes de fleste klassiske brettspill, f.eks go og sjakk.

Mange av de spill som studeres av spillteoretikere – inklusive fangens dilemma – er ikke nullsumspill, fordi visse resultater har nettobelønninger som i sum er større eller mindre enn null. Løst formulert kan en aktør i slike ikke-nullsumspill gjerne forbedre sin belønning uten å påføre noen av de andre aktørene tap. Ved å føye til en fiktiv sisteaktør som aksepterer tap, eksempelvis staten innenfor økonomisk atferd, kan mange spill utvikles til å bli nullsumspill.

Simultane og sekvensielle spill

Simultane spill er spill hvor begge aktører handler samtidig, eller i det minste er uvitende om hverandres tidligere valg (og dermed blir spillet reelt sett simultant). Et eksempel er selskapsleken stein-saks-papir, hvor den beste strategien er å velge henholdsvis stein, saks og papir like ofte, men i uregelmessige intervaller. Sekvensielle (dynamiske) spill er spill hvor aktørene har en viss kunnskap om det foregående handlingsforløp. Dette behøver ikke å bety at de har perfekt informasjon om hver tidligere handling. For eksempel vet en aktør kanskje at en tidligere spiller ikke foretok et bestemt valg, uten dermed å vite hvilke av de andre mulige valg denne andre aktør faktisk foretok.

Forskjellen mellem simultane og sekvensielle spill fremgår av de forskjellige spillgjengivelser, som er diskutert ovenfor. Normal form blir benyttet til å representerer simultane spill, og utvidet form brukes til å gjengi sekvensielle spill.

Perfekt og imperfekt informasjon

Et spill med imperfekt informasjon (den prikkede linjen representerer aktør 2's uvitenhet)

En betydelig andel sekvensielle spill består av spill med perfekt informasjon. I slike spill kjenner alle aktører de foregående aktørers handlinger. Derfor er det kun sekvensielle spill som kan innebære perfekt informasjon, siden ikke alle aktører i simultane spill kjenner de andres valg. De fleste studerte spill i spillteori har imperfekt informasjon, selv om det finnes interessante eksempler på spill med perfekt informasjon, blant annet sjakk, kalaha og go.

Perfekt informasjon blir ofte forvekslet med fullstendig informasjon, som er et lignende begrep. Fullstendig informasjon krever at hver aktør kjenner de andre aktørers strategier og belønninger, men ikke nødvendigvis deres handlinger. Et eksempel på slike spillsituasjoner kan være halvlukkede, oppstykkede auksjoner hvor hver budgiver kjenner hvor mye som kan auksjoneres bort til hver aktør (belønningen), og hvor sterkt ønske hver aktør har om å nå opp i auksjonen, men ikke kjenner til hva hver enkelt aktør byr. Mange auksjoner over radiofrekvenser auksjoneres ut under slike forhold for å maksimere statens inntekter og hindre samarbeid mellom budgiverne.

Uendelig lange spill

Av praktiske årsaker blir modellerte spill som studeres innen økonomi normalt avgjort etter et endelig antall trekk. Rene matematikere – særlig innenfor mengdeteori – studerer gjerne spill som varer i et uendelig antall trekk, og hvor målet er å identifisere gode eller dominerende strategier snarere enn å identifisere vinnere og tapere. Ved hjelp av utvalgsaksiomet kan det vises at det finnes spill hvor ingen av aktørene har en vinnende strategi – selv i spill med perfekt informasjon. Eksistensen av slike strategier i kompliserte spill har viktige konsekvenser for studiet av deskriptiv mengdeteori.

Se også

• Nytteforventningsteoremet

Eksterne lenker

• (en) Game theory – kategori av bilder, video eller lyd på Commons
• (en) Game theory – galleri av bilder, video eller lyd på Commons
• Paul Walker: History of Game Theory Page Arkivert 15. august 2000 hos Wayback Machine..
• David Levine: Game Theory – notater, forelesninger og annet materiale.
• Alvin Roth: Game Theory and Experimental Economics page – omfattende liste over ressurser innen spillteori på internett.
• Adam Kalai: Game Theory and Computer Science – Forelesningsnotater om spillteori og informatikk.
• Mike Shor: Game Theory .net – forelesningsnotater, interaktive illustrasjoner og annet materiale.
• Jim Ratliff's Graduate Course in Game Theory (forelesningsnotater).
• Valentin Robu's Software for simulering av bilaterale forhandlingssituasjoner.
• Don Ross: Review Of Game Theory, i Stanford Encyclopedia of Philosophy.
• Bruno Verbeek and Christopher Morris: Game Theory and Ethics.
• Chris Yiu's Game Theory Lounge
• Elmer G. Wiens: Game Theory – introduksjon, arbeidseksempler og online nullsumspill.
• Marek M. Kaminski: Game Theory and Politics Arkivert 20. oktober 2006 hos Wayback Machine. – undersøkelser og forelesningsnotater om spillteori og statsvitenskap.
• Nettsider om spillteori og soial interaksjon, fra Social Capital Gateway.
• Kesten Green's Conflict Forecasting – notater med vurdering av nøyaktigheten i prediksjoner framsatt gjennom spillteori versus andre matematiske metoder.
• McKelvey, Richard D., McLennan, Andrew M., and Turocy, Theodore L. (2007) Gambit: Software Tools for Game Theory.
• Benjamin Polak: Åpent kurs i spillteori ved Yale University Arkivert 3. august 2010 hos Wayback Machine. med video fra kurset.
• McKelvey, Richard D., McLennan, Andrew M., and Turocy, Theodore L. (2007) Gambit: Software Tools for Game Theory.
• Benjamin Moritz, Bernhard Könsgen, Danny Bures, Ronni Wiersch, (2007) Spieltheorie-Software.de: An application for Game Theory implemented in JAVA.