Spilteori

Inden for spilteori studerer man veldefinerede matematiske objekter. Spillet består af gruppe spildeltagere, en række mulige træk (eller strategier) for disse spillere og en specifikation af udbyttet af hver strategikombination. I faglitteraturen er der to almindelige måder at gengive spil på.

Normale (eller strategiske) spil bliver sædvanligvis gengivet ved en matrix, som viser spillerne, strategierne og udbyttet (se eksemplet til højre). Mere generelt kan det blive repræsenteret ved enhver funktion, der tilordner et udbytte til hver spiller for alle mulige handlingskombinationer. I det viste eksempel er der to spillere; den ene vælger rækken, og den anden vælger søjlen. Hver spiller har to strategier, som er specificeret ved nummeret på rækken eller søjlen. Udbyttet fremgår af skemaets felter. Det første tal er udbyttet, som rækkespilleren (dvs. Spiller 1 i dette tilfælde) modtager, mens det andet tal er udbyttet for søjlespilleren (Spiller 2 i dette eksempel). Antag for eksempel, at Spiller 1 vælger op, og Spiller 2 vælger venstre. Da får Spiller 1 udbyttet 4, mens Spiller 2 får 3.

Når et spil gengives på normal form, antages det at hver spiller handler simultant eller i det mindste uden at kende den andens handling. Hvis spillerne er i besiddelse af information om de andres valg, bliver spillet normalt præsenteret på udvidet form.

 

Den udvidede form kan bruges til at formalisere spil med en vigtig rækkefølge. Sådanne spil bliver ofte gengivet ved et træ (se illustrationen til venstre). Her repræsenterer hvert knudepunkt et valg for en spiller. Spilleren bliver specificeret ved et nummer, der skrives ved punktet. Linjerne ud fra punktet symboliserer mulige handlinger for denne spiller. Udbyttet opskrives i bunden af træet.

I spillet til venstre er der to spillere. Spiller 1 trækker først og vælger enten F eller U. Spiller 2 ser den første spillers træk og vælger dernæst enten A eller R. Antag for eksempel, at Spiller 1 vælger U, og Spiller 2 derefter vælger A. Da får Spiller 1 udbyttet 8, mens spiller 2 får 2.

Den udvidede form kan også afbilde spil, hvor valgene foretages simultant, samt spil med uperfekt information. Enten tegnes en prikket linje eller en cirkel rundt om to forskellige knudepunkter for at fremstille dem som en del af den samme informationsmængde (dvs. spillerne ved ikke, hvilket punkt de er ved).

Et symmetrisk spil er et spil, hvor udbyttet for at vælge en given strategi kun afhænger af de andre benyttede strategier, men ikke af hvem der vælger dem. Hvis der kan byttes om på spildeltagernes identitet uden at ændre strategiernes udbytte, er spillet symmetrisk. Mange af de almindeligt studerede 2×2-spil er symmetriske. Standardgengivelsen af fangernes dilemma er et symmetrisk spil, omend nogle videnskabsfolk ligeledes betragter asymmetriske versioner af dette og lignende spil.

De mest normale asymmetriske spil er spil, hvor spillerne har forskellige mulige strategier, men et spil kan godt have identiske strategier og stadig være asymmetrisk. For eksempel er spillet til højre asymmetrisk, på trods af at strategierne for de to spillere er ens.

Nulsumsspil er et specialtilfælde af konstantsumspil, hvori spillernes valg hverken kan øge eller formindske de tilgængelige ressourcer. I nulsumsspil er den samlede gevinst for alle spillere, for hver strategikombination, lig med nul (uformelt sagt kan en spiller kun vinde på bekostning af andre). Poker er et eksempel på et nulsumsspil (hvis man ser bort fra kasinoets del af puljen), fordi man vinder præcist det beløb, som modstanderne taber. Blandt andre nulsumsspil kan nævnes de fleste klassiske brætspil, fx go og skak.

Mange af de spil, der studeres af spilteoretikere (inklusive det kendte fangernes dilemma), er ikke nulsumsspil, fordi visse udfald har nettogevinster større eller mindre end nul. Løst formuleret kan en spiller i spil, der ikke er et nulsumsspil, godt gavne sin egen sag uden dermed at påføre et tab på de andre spillere.

Konstantsumsspil svarer til aktiviteter såsom tyveri eller hasard, men ikke til de fundamentale økonomiske situationer, hvor der er en potentiel gevinst ved byttehandler. Det er muligt at transformere ethvert spil til et (muligvis assymetrisk) nulsumsspil ved at tilføje en ekstra fiktiv spiller, hvis tab kompenserer spillernes nettogevinster.

Simultane spil er spil, hvor begge spillere handler på samme tid, eller hvis de ikke trækker simultant, er de efterfølgende spillere uvidende om andre spillers tidligere valg (og dermed bliver spillet effektivt set simultant). Sekventielle spil (eller dynamiske spil) er spil, hvor spillerne har en vis viden om det foregående handlingsforløb. Dette behøver ikke at betyde perfekt information om enhver handling af tidligere spillere; det kan være meget lidt viden, der er tale om. For eksempel ved en spiller måske, at en tidligere spiller ikke foretog et bestemt valg, uden dog at vide hvilke af de andre mulige valg, denne spiller rent faktisk foretog.

Forskellen mellem simultane og sekventielle spil fremgår af de forskellige spilgengivelser, som er diskuteret ovenfor. Normal form bliver benyttet til at repræsentere simultane spil, og udvidet form bruges til at gengive sekventielle spil.

 

  Uddybende artikel: Perfekt information

En vigtig delmængde af sekventielle spil består af spil med perfekt information. I sådanne spil kender alle spillere de foregående spilleres handlinger. Derfor er det kun sekventielle spil, der kan indebære perfekt information, eftersom ikke alle spillere i simultane spil er bevidste om de andres valg. De fleste studerede spil i spilteori har imperfekt information, selvom der er interessante eksempler af spil med perfekt information, blandt andet skak, kalaha og go.

Perfekt information bliver ofte forvekslet med fuldstændig information, som er et lignende begreb. Fuldstændig information kræver, at enhver spiller kender de andre spilleres strategier og udbytte deraf, men ikke nødvendigvis deres handlinger.

Af gode grunde bliver spil, der studeres af økonomer og spildeltagere i den virkelige verden, normalt afgjort efter et endeligt antal træk. Rene matematikere er ikke så tilbageholdende, og i særdeleshed mængdeteoretikere studerer spil, der varer et uendeligt antal træk, og hvor vinderen (eller andre spilleres udbytte) først kendes efter alle disse valg er foretaget.

Normalt fokuseres ikke så meget på, hvad den bedste måde at spille sådan et spil på er, men snarere på, om én eller anden spiller har en vindende strategi. (Ved hjælp af udvalgsaksiomet kan det vises, at der findes spil – selv med perfekt information, og hvor de eneste mulige udfald er "vind" eller "tab" – for hvilke ingen af spillerne har en vindende strategi.) Eksistensen af sådanne strategier, for veludtænkte spil, har vigtige konsekvenser inden for deskriptiv mængdeteori.

Spil af én eller anden form er udbredt i mange forskellige akademiske discipliner.

Anvendelsen af spilteori i politisk videnskab fokuserer på de overlappende emner retfærdig fordeling, politisk økonomi, offentligt valg, positivistisk politisk teori og socialvalgsteori. I hver af disse felter har forskere udviklet spilteoretiske modeller, hvori spildeltagerne ofte er stemmeafgivere, stater, interessegrupper eller politikere.

Anthony Downs var en af de første, der overførte spilteori til politiske videnskab. I hans bog En økonomisk teori om demokrati (1957) anvender han Harold Hotellings firmalokationsmodel på den politiske proces. I Downs model binder politiske kandidater sig til en ideologi i et endimensionalt politikrum. Han viste så, hvordan de politiske kandidater ville bevæge sig mod den ideologi, der var foretrukket af medianvælgeren. Mere nutidige eksempler af spilteori inden for politisk videnskab omfatter bøger af George Tsebelis, Gene M. Grossman og Elhanan Helpman, David Austen-Smith og Jeffrey S. Banks.

En spilteoretisk forklaring på demokratisk fred er, at den offentlige og åbne interne debat i demokratier sender klar og pålidelig information om landets intentioner til andre stater. I kontrast hertil er det svært at vide sig sikker på ikkedemokratiske lederes valg, hvilken effekt indrømmelser vil have, og om løfter vil blive overholdt. Derfor vil der herske mistillid og uvilje mod at foretage indrømmelser, hvis bare én af parterne i konflikten er udemokratisk^[2].

Økonomer har længe brugt spilteori til at analysere et bredt udsnit af økonomiske fænomener, deriblandt auktioner, byttehandel, duopoler, retfærdig fordeling, oligopoler, dannelse af sociale netværk og stemmesystemer. Denne forskning koncentrerer sig normalt om særlige mængder af strategier kendt som ligevægte i spil. Disse "løsningskoncepter" er sædvanligvis baseret på normerne for rationalitet. Det mest berømte af disse er Nash-ligevægt. Et sæt af strategier er en Nash-ligevægt, hvis hver af dem udgør det bedste svar til de andre strategier. Så hvis alle spillerne vælger strategier i en Nash-ligevægt, har de intet incitament til at afvige, eftersom den pågældende strategi er deres bedste mulighed, givet de andre spilleres valg.

Udbyttet for spillene er generelt taget for at være individernes nytte. I modelsituationer symboliserer udbyttet ofte penge, hvilket antagelig svarer til personens lykke. Denne antagelse kan imidlertid være fejlagtig.

En typisk afhandling om spilteori i økonomi begynder med at gengive et spil, der er en abstraktion af en given økonomisk situation. Et eller flere løsningskoncepter bliver valgt, og forfatteren demonstrerer derefter, hvilke strategisæt der svarer til ligevægte af en passende type. Man kan spørge sig selv, hvad denne information skal gøre godt for. Økonomer foreslår to primære anvendelser: deskriptiv og normativ analyse.

 

Den første anvendelse er at informere os om, hvordan rigtige befolkningsgrupper opfører sig. Visse forskere mener, at ved at finde spilligevægte kan de forudsige, hvordan virkelige grupper af personer vil opføre sig, når de konfronteres med situationer, der er analoge med det studerede spil. Dette syn på spilteori er blevet udsat for kritik på det seneste. For det første bliver det anfægtet, fordi modellens antagelser ofte brydes. Spilteoretikere antager måske, at spillerne altid handler rationelt for at maksimere deres gevinst (Home economicus-modellen), men virkelige mennesker handler ofte enten irrationelt eller rationelt for at maksimere gevinsten for en større grupper personer (altruisme). Spilteoretikernes svar er at sammenligne deres antagelser med dem, der benyttes i fysik. Selvom antagelserne således ikke altid holder, betragter de spilteori som et fornuftigt videnskabeligt ideal, ikke ulig fysiske modeller. Imidlertid er denne brug af spilteori blevet kritiseret yderligere, fordi eksperimenter har vist, at individer ikke vælger ligevægtsstrategier. For eksempel vælger spillere i tusindbenspillet, gæt 2/3 af gennemsnittet-spillet og diktatorspillet ofte ikke Nash-ligevægten. Det debatteres stadig, hvor vigtigt resultatet af disse eksperimenter er.^[3]

Nogle forfattere påstår, at Nash-ligevægte ikke er forudsigelser for menneskegrupper, men snarere en forklaring på, hvorfor personer, der vælger Nash-ligevægte, bliver i den tilstand. Imidlertid er spørgsmålet om, hvordan man kommer til det punkt, stadig åbent.

En række spilteorikere har vendt sig til evolutionsspilteori for at løse disse problemer. Sådanne modeller antager enten ingen rationalitet eller begrænset rationalitet fra spillernes synspunkt. På trods af navnet tager evolutionsspilteori ikke nødvendigvis udgangspunkt i naturlig selektion i den biologiske betydning. Evolutionsspilteori omfatter både biologisk såvel som kulturel evolution og også modeller af individuel indlæring.

På den anden side ser visse forskere ikke spilteori som et værktøj til at forudsige menneskers adfærd, men som et forslag til, hvordan folk bør opføre sig. Eftersom en Nash-ligevægt i et spil udgør éns bedste svar til de andre spilleres handlinger, virker det passende at vælge en strategi, der er en del af en Nash-ligevægt. Imidlertid er denne brug af spilteori også blevet kritiseret. For det første er det passende at vælge en ikkeligevægtsstrategi, hvis man forventer, at de andre også gør dette (se for eksempel gæt 2/3 af gennemsnittet).

For det andet præsenterer fangernes dilemma et andet modeksempel. I fangernes dilemma ender begge spillere med at have det værre, hvis de forfølger deres egne mål, end hvis de ikke havde gjort dette. Dette betyder, at deres mål faktisk bør være ikke at gå efter egen vinding.

I modsætning til økonomi bliver udbyttet i spil inden for biologi ofte fortolket som svarende til fitness. Endvidere fokuserer man mindre på rationelle ligevægte, men snarere på ligevægte, der opretholdes af evolutionskræfter. Den mest velkendte ligevægt inden for biologi kaldes evolutionær stabil strategi (ESS) og blev først introduceret af John Maynard Smith (beskrevet i hans bog fra 1982). Selvom motivationen til teorien oprindeligt ikke involverede de mentale krav for Nash-ligevægte, er hver ESS en Nash-ligevægt.

I biologi er spilteori blevet benyttet til at forstå mange forskellige fænomener. Det blev først benyttet til at forklare udviklingen (og stabiliteten) af det omtrentlige 1:1-kønsforhold. Ronald Fisher foreslog i 1930, at 1:1-forholdet var et resultat af evolutionskræfter påvirkende individer, som kan antages at forsøge at maksimere deres antal børnebørn.

Biologer har også brugt evolutionsspilteori og ESS til at forklare dyrekommunikations opståen (Maynard Smith og Harper, 2003). Analysen af signalspil og andre kommunikationsspil har givet nogen indsigt i udviklingen af kommunikation mellem dyr.

Sidst, men ikke mindst, har biologer brugt høg-due-spillet (også kendt som "kylling") til at analysere krigerisk og territoriel adfærd.

Spilteori spiller en stadig større rolle inden for logik og datalogi. Adskillige logiske teorier baserer sig på spilteori, og dataloger har benyttet spil til at modellere interaktiv beregning.

Særskilt herfra har spilteori spillet en rolle i onlinealgoritmer, særligt k-server-problemet, der tidligere er blevet betegnet som spil med skiftende omkostninger og spørgsmål-svar-spil.^[4]

Spilteori bliver flittigt brugt inden for filosofi. Som et svar på to afhandlinger af W.V.O. Quine (1960, 1967) benyttede David Lewis i 1969 spilteori til at udvikle en filosofisk redegørelse for konventioner. Undervejs gennemførte han den første analyse af almindelig viden og anvendte den til at analysere samarbejdsspil. Endvidere foreslog han, at man kan forstå mening ud fra signalspil. Dette forslag er senere blevet fulgt op på af adskillige andre filosoffer (Skyrms 1996, Grim et al. 2004).

Inden for etik har visse forfattere forsøgt at træde i Thomas Hobbes' fodspor og udlede moral fra egennytte. Eftersom spil som fangernes dilemma præsenterer en konflikt mellem moral og egennytte, er det vigtigt for dette projekt at forklare, hvorfor egennytte kræver samarbejde. Denne strategi er en del af det generelle social kontrakt-synspunkt i politisk filosofi (se fx Gauthier 1987 og Kavka 1986).^[5]

Endelig har nogle forfattere prøvet at benytte evolutionsspilteori til at forklare fremkomsten af menneskets holdninger om moral og tilsvarende adfærd blandt dyr. Disse forfattere betragter flere forskellige spil, bl.a. fangernes dilemma, hjortejagt og Nashs forhandlingsspil (se fx Skyrms 1996, 2004; Sober and Wilson 1999).

 

Den tidligst kendte diskussion af spilteori foregik i et brev skrevet af James Waldegrave i 1713. I dette brev giver Waldegrave en minimax-blandet strategi-løsning til en topersoners udgave af kortspillet le Her. En generel spilteoretisk analyse blev først udført af Antoine Augustin Cournot i 1838 i en afhandling om de matematiske principper bag velfærdsteori. I dette værk betragter Cournot et duopol og præsenterer en løsning, som er en begrænset version af en Nash-ligevægt.

Selvom Cournots analyse var mere generel end Waldegraves, eksisterede spilteori ikke rigtig som et selvstændigt felt, indtil John von Neumann udgav en række afhandlinger i 1928. Selvom den franske matematiker Emile Borel havde arbejdet med spil tidligere, kan von Neumann med rette kaldes opfinderen af spilteori. Von Neumanns arbejde kulminerede med bogen Teorien om spil og økonomisk adfærd fra 1944, som han skrev sammen med Oskar Morgenstern. Værket indeholder metoden til at finde optimale løsninger for topersoners nulsumsspil. I løbet af denne tidsperiode koncentrerede spilteoretikere sig primært om teorien bag samarbejdsspil (eller kooperativt spil), der analyserer optimale strategier for grupper af individer under antagelsen, at de kan gennemføre aftaler mellem dem om de rette strategier.

I 1950 dukkede den første diskussion af fangernes dilemma op, og et tilhørende eksperiment blev startet ved RAND Corporation. Omkring den samme tid udviklede John Nash en definition af "optimale" strategier for spil med mange deltagere, hvor der ikke tidligere havde været defineret et sådant optimum. Dette blev kendt som Nash-ligevægte. Ligevægten er tilstrækkelig generel til at tillade analyse af ikkesamarbejdsspil (eller ikke-kooperativt spil) i tillæg til samarbejdsspil.

Spilteori oplevede en hektisk aktivitet i 1950'erne. Årtiet blev vidne til udviklingen af koncepter såsom kerner, spil i udvidet form, fiktive spil, gentagne spil og Shapley-værdi. Endvidere blev spilteori for første gang overført til filosofi og politiske videnskab.

I 1965 introducerede Reinhard Selten sin løsning til delspilsperfekte ligevægte, som viderebyggede Nash-ligevægten (senere indførte han også rystende hånd-perfektion). I 1967 udviklede John Harsanyi koncepterne fuldstændig information og Bayeske spil. Nash, Selten og Harsanyi modtog Nobelprisen i økonomi i 1994 for deres bidrag til økonomisk spilteori.

I 1970'erne blev spilteori i vid udstrækning anvendt inden for biologi, hvilket hovedsageligt skyldtes John Maynard Smiths arbejde. Derudover blev koncepterne korreleret ligevægt, rystende hånd-perfektion og almindelig viden^[6] introduceret og analyseret.

I 2005 vandt spilteoretikerne Thomas Schelling og Robert Aumann Nobelprisen. Schelling arbejdede med dynamiske modeller, tidlige eksempler på evolutionsspilteori. Aumann bidrog til teorien om korrelerede ligevægte og almindelig viden.

• Spil inden for spilteori

Wikimedia Commons har medier relateret til: Spilteori

• Bierman, H. S. og L. Fernandez: Game Theory with economic applications, Addison-Wesley, 1998
• Dutta, Prajit: Strategies and Games: Theory and Practice, MIT Press, 2000, ISBN 0-262-04169-3
• Fudenberg, Drew og Jean Tirole: Game Theory, MIT Press, 1991, ISBN 0-262-06141-4
• Gibbons, Robert (1992): A primer in game theory, Harvester Wheatsheaf (London), ISBN 0-7450-1159-4 (udgivet i USA under titlen Game Theory for Applied Economists, Princeton University Press, ISBN 0-691-00395-5)
• Gintis, Herbert (2000): Game Theory Evolving, Princeton University Press ISBN 0-691-00943-0
• Mas-Colell, Whinston og Green (1995): Microeconomic Theory, 1995. Oxford University Press, 1995, ISBN 0-19-507340-1
• Miller, James (2003): Game Theory At Work, McGraw-Hill ISBN 0-07-140020-6
• Myerson Roger B.: Game Theory: Analysis of Conflict, Harvard University Press, Cambridge, 1991, ISBN 0-674-34116-3
• Osborne, Martin J.: An Introduction to Game Theory, Oxford University Press, New York, 2004, ISBN 0-19-512895-8
• Osborne, Martin J. og Ariel Rubinstein: A Course in Game Theory, MIT Press, 1994, ISBN 0-262-65040-1
• Poundstone, William Prisoner's Dilemma: John von Neumann, Game Theory and the Puzzle of the Bomb, ISBN 0-385-41580-X
• Rasmusen, Eric: Games and information, 4. udgave, Blackwell, 2006. Tilgængelig online.

• Fisher, Ronald (1930) The Genetical Theory of Natural Selection Clarendon Press, Oxford.
• Luce, Duncan and Howard Raiffa Games and Decisions: Introduction and Critical Survey Dover, ISBN 0-486-65943-7
• Maynard Smith, John Evolution and the Theory of Games, Cambridge University Press 1982
• Morgenstern, Oskar og John von Neumann (1947) The Theory of Games and Economic Behavior, Princeton University Press
• Nash, John (1950) "Equilibrium points in n-person games" Proceedings of the National Academy of the USA 36(1):48-49.

• Camerer, Colin (2003) Behavioral Game Theory, Princeton University Press, ISBN 0-691-09039-4
• Gauthier, David (1987) Morals by Agreement Oxford University Press, ISBN 0-19-824992-6
• Green, Kesten C. (2002). Forecasting decisions in conflict situations: A comparison of game theory, role-playing, and unaided judgement. International Journal of Forecasting, 18, 321-344.
• Green, Kesten C. (2005). Game theory, simulated interaction, and unaided judgment for forecasting decisions in conflicts: Further evidence, International Journal of Forecasting, 21, 463-472.
• Grim, Patrick, Trina Kokalis, Ali Alai-Tafti, Nicholas Kilb, and Paul St Denis (2004) "Making meaning happen." Journal of Experimental & Theoretical Artificial Intelligence 16(4): 209-243.
• Kaminski, Marek M. (2004) Games Prisoners Play Princeton University Press. ISBN 0-691-11721-7 (http://webfiles.uci.edu/mkaminsk/www/book.html Arkiveret 4. november 2015 hos Wayback Machine)
• Kavka, Gregory (1986) Hobbesian Moral and Political Theory, Princeton University Press. ISBN 0-691-02765-X
• Lewis, David (1969) Convention: A Philosophical Study
• Maynard Smith, J. og Harper, D. (2003) Animal Signals. Oxford University Press. ISBN 0-19-852685-7
• Quine, W.v.O (1967) "Truth by Convention" i Philosophica Essays for A.N. Whitehead Russel and Russel Publishers. ISBN 0-8462-0970-5
• Quine, W.v.O (1960) "Carnap and Logical Truth" Synthese 12(4):350-374.
• Skyrms, Brian (1996) Evolution of the Social Contract Cambridge University Press. ISBN 0-521-55583-3
• Skyrms, Brian (2004) The Stag Hunt and the Evolution of Social Structure Cambridge University Press. ISBN 0-521-53392-9.
• Sober, Elliot and David Sloan Wilson (1999) Unto Others: The Evolution and Psychology of Unselfish Behavior Harvard University Press. ISBN 0-674-93047-9

• Kesten Green: Conflict Forecasting Arkiveret 11. april 2011 hos Wayback Machine – Se under "Papers" for beviser på de spilteoretiske forudsigelsers præcision. (engelsk)
• Paul Walker: Spilteoriens historie Arkiveret 15. august 2000 hos Wayback Machine. (engelsk)
• David Levine: Game Theory. Afhandlinger, forelæsningnoter og meget andet. (engelsk)
• Alvin Roth: Game Theory and Experimental Economics page Arkiveret 15. august 2000 hos Wayback Machine – Omfattende liste over links til information af spilteori på nettet. (engelsk)
• Mike Shor: Game Theory .net – Forelæsningsnote, interaktive illustrationer og anden information. (engelsk)
• Jim Ratliff: Kursus i spilteori – Forelæsningsnoter. (engelsk)
• Valentin Robus: Softwareværktøj Arkiveret 13. januar 2010 hos Wayback Machine til simulation af bilaterale forhandlinger (handel). (engelsk)
• Don Ross: Opslag om spilteori i Stanford Encyclopedia of Philosophy. (engelsk)
• Bruno Verbeek og Christopher Morris: Spilteori og etik. (engelsk)
• Elmer G. Wiens: Spilteori Arkiveret 29. juni 2006 hos Wayback Machine – Introduktion, gennemarbejdede eksempler, online topersoners nulsumsspil. (engelsk)
• Marek M. Kaminski: Spilteori og politik Arkiveret 20. oktober 2006 hos Wayback Machine – Pensum og forelæsningsnoter for spilteori og politisk videnskab. (engelsk)
• Hjemmesider om spilteori og social interaktion. (engelsk)