Nollsummespel

Ett nollsummespel definieras genom att summan av vinsten och förlusten i spelet alltid är noll för varje tänkbar strategi spelarna kan använda sig av. Finns det ett enda utfall där summan skiljer sig från noll så sägs spelet vara ett icke-nollsummespel. Konsekvensen av detta är att en spelare kan vinna endast genom att någon annan förlorar.

En speciell kategori av nollsummespel är alla tvåmansspel med en vinnare och en förlorare. Typiska exempel är go och tennis.

Exempel

I spelet "Matchande mynt" finns två spelare som får bestämma sig för att den ena är "A" och den andra är "B". Båda spelarna har varsitt mynt och tänks visa ena sidan av myntet för den andra precis samtidigt med varandra. Om båda spelarna visar samma sida vinner "A" en krona från "B". Om de visar olika sidor av myntet vinner "B" en krona från "A". Förtjänsten för spelarna kan då visas med hjälp av en förtjänstmatris:

A,B	Krona	Klave
Krona	+1, -1	-1, +1
Klave	-1, +1	+1, -1

Vi ser att varje tänkbar kombination mellan mynten ger +1,-1 i vinst/förlust vilket ger summan noll. Alltså är detta ett nollsummespel.

Spelteori

År 1928 formulerade John von Neumann en teori där man kan beräkna den strategi man ska använda sig av för att den maximala förlusten ska vara så liten som möjligt. Detta kallas för Minimax-teorin och existerar för alla nollsummespel med 2 spelare samt med ett ändligt antal strategier. Denna teori har senare vidareutvecklats till att omfatta mer komplicerade spel och kallas då Nash-jämvikt.

Exemplet ovan är ett spel där Minimax-satsen kan tillämpas och säger då att den optimala strategin är att välja krona eller klave slumpmässigt med lika stor sannolikhet. Om spelare "A" bestämmer sig för att visa klave varje gång märker spelare "B" detta och bestämmer sig för att visa krona för att vinna och vice versa.

Minimax

I ett nollsummespel där förtjänsten för spelarna representeras med en förtjänstmatris som i exemplet ovan hittas minimaxlösningen genom att hitta en så kallad sadelpunktslösning. Tänk nu att det som står i varje cell i matrisen nedan är spelare A:s förtjänst. Spelare B:s förtjänst är alltså -1 multiplicerad med A:s vinst eftersom detta är ett nollsummespel.

A,B	B1	B2	B3	B4
A1	5	7	6	4
A2	3	8	7	9
A3	5	8	10	11
A4	6	11	9	13

A och B är spelare och A1, A2, A3, A4, B1, B2, B3, B4 är deras möjliga strategier för spelet.

Icke-stokastisk minimaxlösning

En så kallad icke-stokastisk minimaxlösning vill man alltid söka efter i första hand. Om denna lösning inte existerar kan man hitta en stokastisk minimaxlösning till spelet med hjälp av avancerad programmering.

En sadelpunkt i en förtjänstmatris är en cell som både kan ses som lokalt maximum och lokalt minimum på samma gång. Det vi är intresserade av är att hitta denna cell för hela matrisen.

Steg 1 – Hitta dina minsta förtjänster

För att hitta sadelpunktslösningen till spelet med tillhörande förtjänstmatris, beteckna varje rad i matrisen med dess minsta möjligaste förtjänst för spelare A. På detta sätt har vi nu definierat den sämsta förtjänsten för de olika strategierna spelare A kan välja.

A,B	B1	B2	B3	B4	Sämsta scenarierna för A
A1	5	7	6	4	Förtjänst = +4
A2	3	8	7	9	Förtjänst = +3
A3	5	8	10	11	Förtjänst = +5
A4	6	11	9	13	Förtjänst = +6

Steg 2 – Hitta din motståndares minsta förtjänster

Beteckna nu varje kolumn med dess största möjligaste förtjänst för spelare A. På detta sätt har vi nu definierat den sämsta förtjänsten för de olika strategierna motståndaren B kan välja. Nu kan vi ta reda på vilken förtjänst som är den högsta bland de sämsta scenarierna för A samt vilken förlust som är den lägsta för de sämsta scenarierna för B .

A,B	B1	B2	B3	B4
A1	5	7	6	4
A2	3	8	7	9
A3	5	8	10	11
A4	6	11	9	13
Sämsta scenarierna för B	Förtjänst = -6	Förtjänst = -11	Förtjänst = -10	Förtjänst = -13

Den högsta förtjänsten bland de sämsta scenarierna för A = +6. Den högsta förtjänsten bland de sämsta scenarierna för B = -6.

Steg 3 – Jämför

Om dessa två värden matchar har vi funnit en cell med sadelpunkt för förtjänstmatrisen. Detta kallas då för en icke-stokastisk minimaxlösning. Det är då troligt att både A och B använder sig just av dessa strategier för på så sätt maximeras förtjänsten av det värsta tänkbara scenariot. Därav kommer ordet minimaxlösning och det är även därför man använder begreppet sadelpunkt för cellen.

I vårt exempel finner vi att minimaxlösningen är att spelare A väljer strategi A4 samt att spelare B väljer strategi B1. Dessa kallas då för "äkta" minimax strategier.

Stokastisk minimaxlösning

Finns inte en icke-stokastisk minimaxlösning till förtjänstmatrisen så krävs ganska avancerad programmering för att hitta en stokastisk minimaxlösning istället. Spelarna kommer då inte använda sig av en lösning hela tiden för att maximera förtjänsten av sitt värsta tänkbara scenario. Den stokastiska minimaxlösningen säger med vilken sannolikhet vi ska välja vissa strategier för att vår förtjänst ska maximeras. Dessa kallas då för "blandade" strategier.

Exemplet nedan är taget från engelska Wikipedia och visar spelaren A:s förtjänster för de olika strategierna denna kan välja.

A,B	B1	B2	B3
A1	+3	-2	+2
A2	-1	0	+4
A3	-4	-3	+1

Då är minimaxlösningen för spelare A att välja strategi A2 eftersom det sämsta tänkbara scenariot är att denna då måste betala 1. Minimaxlösningen för spelare B är att välja strategi B2 eftersom det sämsta tänkbara scenariot då är att varken betala eller vinna någonting.

Dessa strategier är dock inte "äkta" minimaxstrategier. Om spelare B vet att spelare A kommer att välja strategi A2 så kommer spelare B så klart att välja strategi B1 eftersom denna då får förtjänsten +1. På samma sätt fås om spelare A vet att spelare B kommer att välja strategi B1 så kommer A att välja A1 för att få förtjänsten +3.

Alltså kommer det att bli väldigt svårt för spelarna att veta vilken strategi de ska välja för att minimaxkriteriet ska uppfyllas. Vissa strategier dominerar dock över andra och man kan på så vis eliminera vissa strategier. I exemplet ovan kommer spelare A aldrig att välja strategi A3 eftersom strategi A1 och A2 alltid ger en bättre förtjänst oavsett vad spelare B väljer. Spelare B kommer inte att välja B3 eftersom B2 alltid ger en bättre förtjänst.

Löser man detta exempel får man att den stokastiska minimaxlösningen blir att spelare A ska välja strategi A1 med sannolikheten ${\frac {1}{6}}$ samt strategi A2 med sannolikheten ${\frac {5}{6}}$ oavsett vad spelare B väljer.

Spelare B ska välja strategi B1 med sannolikheten ${\frac {1}{3}}$ samt strategi B2 med sannolikheten ${\frac {2}{3}}$ oavsett vad spelare A väljer.

Sions minimaxteori

Denna sats är en generalisering av John von Neumanns minimaxteori och säger följande  :

Låt $X$ vara en kompakt konvex mängd av ett linjärt topologiskt rum och $Y$ vara en konvex mängd av ett linjärt topologiskt rum. Låt funktionen $f$ vara en reellvärd funktion på $X\times Y$ så att

$f(x,\cdot )$ är övre semikontinuerlig och kvasikonkav på $Y,\forall x\in X$ samt

$f(\cdot ,y)$ är nedre semikontinuerlig och kvasikonvex på $X,\forall y\in Y$

Då gäller:

$\min _{x\in X}\max _{y\in Y}f(x,y)=\max _{y\in Y}\min _{x\in X}f(x,y).$

Betydelser

John von Neumanns upptäckt, men även spelteori i allmänhet, har idag stor betydelse för att inte bara förutsäga strategier hos spel av olika slag utan även i till exempel ekonomi. Tillämpningar inom området är bland annat auktioner och kollektivförhandlingar. Även i politik tar man ibland hjälp av spelteori för att förutsäga hur resultatet kommer att bli i till exempel en viktig omröstning. Spelarna representeras av bland annat röstare, stater, politiker eller speciella intresseorganisationer. Forskare inom området har då tagit fram olika teoretiska modeller för dessa vilket gör det möjligt att tillämpa spelteorier och på så sätt kunna säga något om hur utfallet kommer att bli.

Exempel på andra tillämpningar är biologi, datavetenskap, logik samt filosofi^{[källa behövs]}.

Källor

• Kan spelteorin rädda världen? Nyteknik, publicerad den 20 december 2005