Antagonistiska spel med kontinuerliga strategier. Lösa matrisantagonistiska spel Lösa antagonistiska spel online

Ett nollsummespel för två personer kallas, där var och en av dem har en ändlig uppsättning strategier. Reglerna för matrisspelet bestäms av utdelningsmatrisen, vars element är den första spelarens utdelning, vilket också är förlusterna för den andra spelaren.

Matrix spel är ett antagonistiskt spel. Den första spelaren får den maximala garanterade (inte beroende på beteendet hos den andra spelaren) lika med priset på spelet, på samma sätt uppnår den andra spelaren den minsta garanterade förlusten.

Under strategi förstås som en uppsättning regler (principer) som bestämmer valet av en variant av åtgärder för varje personligt drag av en spelare, beroende på den aktuella situationen.

Nu om allt i ordning och detalj.

Payoff matris, rena strategier, spelpris

PÅ matrisspel dess regler är fastställda payoff matris .

Tänk på ett spel där det finns två deltagare: den första spelaren och den andra spelaren. Låt den första spelaren ha m rena strategier och till den andra spelarens förfogande - n rena strategier. Eftersom ett spel övervägs är det naturligt att det finns vinster och förluster i detta spel.

PÅ betalningsmatris elementen är siffror som uttrycker spelarnas vinster och förluster. Vinster och förluster kan uttryckas i poäng, pengar eller andra enheter.

Låt oss skapa en utbetalningsmatris:

Om den första spelaren väljer i-den rena strategin och den andra spelaren j-th rena strategin, då är utdelningen för den första spelaren aI j enheter, och förlusten av den andra spelaren är också aI j enheter.

Därför att aij + (- a ij) = 0, då är det beskrivna spelet ett nollsummematrisspel.

Det enklaste exemplet på ett matrisspel är att kasta ett mynt. Spelets regler är följande. Den första och andra spelaren kastar ett mynt och resultatet är huvuden eller svansar. Om huvuden och huvuden eller svansar eller svansar rullas samtidigt, kommer den första spelaren att vinna en enhet, och i andra fall kommer han att förlora en enhet (den andra spelaren kommer att vinna en enhet). Samma två strategier står till den andra spelarens förfogande. Motsvarande utbetalningsmatris skulle vara:

Uppgiften med spelteorin är att bestämma valet av strategin för den första spelaren, vilket skulle garantera honom den maximala genomsnittliga vinsten, såväl som valet av strategin för den andra spelaren, vilket skulle garantera honom den maximala genomsnittliga förlusten.

Hur väljs en strategi i ett matrisspel?

Låt oss titta på utdelningsmatrisen igen:

Först bestämmer vi utdelningen för den första spelaren om han använder i den rena strategin. Om den första spelaren använder i-th ren strategi, då är det logiskt att anta att den andra spelaren kommer att använda en sådan ren strategi, på grund av vilken utdelningen för den första spelaren skulle vara minimal. I sin tur kommer den första spelaren att använda en sådan ren strategi som skulle ge honom maximal utdelning. Baserat på dessa villkor, utdelningen av den första spelaren, som vi betecknar som v1 , kallas maximal vinst eller lägre spelpris .

På för dessa värden ska den första spelaren fortsätta enligt följande. Från varje rad, skriv ut värdet på minimielementet och välj det maximala från dem. Således kommer utdelningen för den första spelaren att vara den högsta av minimumen. Därav namnet - maximin win. Radnumret för detta element kommer att vara numret på den rena strategin som valts av den första spelaren.

Låt oss nu avgöra förlusten av den andra spelaren om han använder j-e strategin. I det här fallet använder den första spelaren sin egen rena strategi, där förlusten för den andra spelaren skulle vara maximal. Den andra spelaren måste välja en sådan ren strategi där hans förlust skulle vara minimal. Förlusten av den andra spelaren, som vi betecknar som v2 , kallas minimax förlust eller högsta spelpriset .

På lösa problem med priset på spelet och bestämma strategin för att bestämma dessa värden för den andra spelaren, fortsätt enligt följande. Från varje kolumn, skriv ut värdet för det maximala elementet och välj ett minimum från dem. Således kommer förlusten av den andra spelaren att vara minimum av maximum. Därav namnet - minimax gain. Kolumnnumret för detta element kommer att vara numret på den rena strategin som valts av den andra spelaren. Om den andra spelaren använder "minimax" så kommer han att förlora högst oavsett vilken strategi den första spelaren väljer v2 enheter.

Exempel 1

.

Den största av de minsta elementen i raderna är 2, detta är det lägre priset på spelet, den första raden motsvarar det, därför är den första spelarens maximinstrategi den första. Den minsta av de största elementen i kolumnerna är 5, detta är det övre priset för spelet, den andra kolumnen motsvarar det, därför är den andra spelarens minimaxstrategi den andra.

Nu när vi har lärt oss hur man hittar det lägre och övre priset på spelet, maximin- och minimax-strategierna, är det dags att lära sig hur man formellt betecknar dessa koncept.

Så den garanterade utdelningen för den första spelaren är:

Den första spelaren måste välja en ren strategi som skulle ge honom det maximala av minimiutbetalningarna. Denna vinst (maximin) betecknas som följer:

.

Den första spelaren använder sin rena strategi så att förlusten för den andra spelaren är maximal. Denna förlust definieras enligt följande:

Den andra spelaren måste välja sin rena strategi så att hans förlust blir minimal. Denna förlust (minimax) betecknas enligt följande:

.

Ytterligare ett exempel från samma serie.

Exempel 2 Givet ett matrisspel med en utdelningsmatris

.

Bestäm maximin-strategin för den första spelaren, minimax-strategin för den andra spelaren, det lägre och övre priset för spelet.

Lösning. Till höger om utdelningsmatrisen skriver vi ut de minsta elementen i dess rader och markerar det maximala av dem, och från botten av matrisen - de största elementen i kolumnerna och väljer det minsta av dem:

Den största av de minsta delarna av raderna är 3, detta är det lägre priset på spelet, den andra raden motsvarar det, därför är den första spelarens maximinstrategi den andra. Den minsta av de största elementen i kolumnerna är 5, detta är det övre priset för spelet, den första kolumnen motsvarar det, därför är den andra spelarens minimaxstrategi den första.

Sadelpunkt i matrisspel

Om det övre och lägre priset på spelet är detsamma, anses matrisspelet ha en sadelpunkt. Det omvända är också sant: om ett matrisspel har en sadelpunkt, är de övre och lägre priserna för matrisspelet desamma. Motsvarande element är både det minsta i raden och det största i kolumnen och är lika med spelets pris.

Således, om , då är den optimala rena strategin för den första spelaren, och är den optimala rena strategin för den andra spelaren. Det vill säga, lika lägre och övre priser på spelet uppnås på samma par strategier.

I detta fall matrisspelet har en lösning i rena strategier .

Exempel 3 Givet ett matrisspel med en utdelningsmatris

.

Lösning. Till höger om utdelningsmatrisen skriver vi ut de minsta elementen i dess rader och markerar det maximala av dem, och från botten av matrisen - de största elementen i kolumnerna och väljer det minsta av dem:

Det lägre priset på spelet är detsamma som det övre priset på spelet. Således är priset på spelet 5. Det vill säga . Priset på spelet är lika med värdet på sadelpoängen. Maximinstrategin för den första spelaren är den andra rena strategin, och minimaxstrategin för den andra spelaren är den tredje rena strategin. Detta matrisspel har en lösning i rena strategier.

Lös matrisspelsproblemet själv och se sedan lösningen

Exempel 4 Givet ett matrisspel med en utdelningsmatris

.

Hitta det lägre och övre priset på spelet. Har detta matrisspel en sadelpunkt?

Matrixspel med optimal blandad strategi

I de flesta fall har matrisspelet ingen sadelpunkt, så motsvarande matrisspel har inga rena strategilösningar.

Men det har en lösning i optimala blandade strategier. För att hitta dem måste man utgå från att spelet upprepas tillräckligt många gånger för att man utifrån erfarenhet kan gissa vilken strategi som är att föredra. Därför är beslutet förknippat med begreppet sannolikhet och medelvärde (förväntning). I den slutliga lösningen finns det både en analog av sadelpunkten (det vill säga likheten mellan de lägre och övre priserna i spelet) och en analog av de strategier som motsvarar dem.

Så, för att den första spelaren ska få den maximala genomsnittliga vinsten och för den andra spelaren att ha den minsta genomsnittliga förlusten, bör rena strategier användas med en viss sannolikhet.

Om den första spelaren använder rena strategier med sannolikheter , sedan vektorn kallas den första spelarens blandade strategi. Det är med andra ord en "blandning" av rena strategier. Summan av dessa sannolikheter är lika med en:

.

Om den andra spelaren använder rena strategier med sannolikheter , sedan vektorn kallas den blandade strategin för den andra spelaren. Summan av dessa sannolikheter är lika med en:

.

Om den första spelaren använder en blandad strategi sid, och den andra spelaren - en blandad strategi q, då är det vettigt förväntat värde den första spelaren vinner (den andra spelaren förlorar). För att hitta den måste du multiplicera den första spelarens blandade strategivektor (som kommer att vara en enradsmatris), payoffmatrisen och den andra spelarens blandade strategivektor (som kommer att vara en enkolumnsmatris):

.

Exempel 5 Givet ett matrisspel med en utdelningsmatris

.

Bestäm den matematiska förväntan på den första spelarens vinst (den andra spelarens förlust), om den blandade strategin för den första spelaren är , och den blandade strategin för den andra spelaren är .

Lösning. Enligt formeln för den matematiska förväntan av den första spelarens vinst (förlust av den andra spelaren) är den lika med produkten av den första spelarens blandade strategivektor, utdelningsmatrisen och den andra spelarens blandade strategivektor:

Den första spelaren kallas en sådan blandad strategi som skulle ge honom den maximala genomsnittliga utdelningen om spelet upprepas tillräckligt många gånger.

Optimal blandad strategi Den andra spelaren kallas en sådan blandad strategi som skulle ge honom den minsta genomsnittliga förlusten om spelet upprepas tillräckligt många gånger.

I analogi med notationen maximin och minimax i fall av rena strategier, betecknas optimala blandade strategier enligt följande (och är kopplade till den matematiska förväntan, det vill säga genomsnittet av den första spelarens vinst och den andra spelarens förlust):

,

.

I det här fallet för funktionen E det finns en sadelpunkt , vilket betyder jämlikhet.

För att hitta de optimala blandade strategierna och sadelpunkten, d.v.s. lösa matrisspelet i blandade strategier , måste du reducera matrisspelet till ett linjärt programmeringsproblem, det vill säga till ett optimeringsproblem, och lösa motsvarande linjära programmeringsproblem.

Reduktion av ett matrisspel till ett linjärt programmeringsproblem

För att lösa ett matrisspel i blandade strategier måste du komponera en rak linje linjärt programmeringsproblem och dess dubbla uppgift. I det dubbla problemet transponeras den förstärkta matrisen, som lagrar koefficienterna för variabler i begränsningssystemet, konstanta termer och koefficienter för variabler i målfunktionen. I detta fall är minimum av målfunktionen för det ursprungliga problemet associerat med maximum i det dubbla problemet.

Målfunktion i direktlinjär programmeringsproblem:

.

Systemet av begränsningar i det direkta problemet med linjär programmering:

Målfunktion i det dubbla problemet:

.

Systemet av begränsningar i det dubbla problemet:

Ange den optimala planen för det direktlinjära programmeringsproblemet

,

och den optimala planen för det dubbla problemet betecknas med

Linjära former för motsvarande optimala mönster kommer att betecknas med och ,

och du måste hitta dem som summan av motsvarande koordinater för de optimala planerna.

I enlighet med definitionerna i föregående avsnitt och koordinaterna för optimala planer är följande blandade strategier för de första och andra spelarna giltiga:

.

Matematiker har bevisat det spelpris uttrycks i termer av linjära former av optimala planer enligt följande:

,

det vill säga det är den ömsesidiga summan av koordinaterna för de optimala planerna.

Vi, utövare, kan bara använda denna formel för att lösa matrisspel i blandade strategier. Tycka om formler för att hitta optimala blandade strategier första respektive andra spelaren:

där de andra faktorerna är vektorer. Optimala blandade strategier är också vektorer, som vi redan definierade i föregående stycke. Därför, multiplicera numret (priset på spelet) med vektorn (med koordinaterna för de optimala planerna), får vi också en vektor.

Exempel 6 Givet ett matrisspel med en utdelningsmatris

.

Hitta priset på ett spel V och optimala blandade strategier och .

Lösning. Vi komponerar det linjära programmeringsproblemet som motsvarar detta matrisspel:

Vi får lösningen på det direkta problemet:

.

Vi finner den linjära formen av optimala planer som summan av de hittade koordinaterna.

Skicka ditt goda arbete i kunskapsbasen är enkelt. Använd formuläret nedan

Studenter, doktorander, unga forskare som använder kunskapsbasen i sina studier och arbete kommer att vara er mycket tacksamma.

Introduktion

1. Teoretisk del

1.3 Spelordning 2v2

1.4 Algebraisk metod

1.5 Grafisk metod

1.6 Spel 2xn eller mx2

1.7 Lösa spel med matrismetoden

2. Praktisk del

2.2 2xn och mx2 spel

2.3 Matrismetod

2.4 Brun metod

Analys av resultat

Introduktion

Det antagonistiska spelet är ett nollsummespel. Ett antagonistiskt spel är ett icke-samarbetsspel där två spelare deltar, vars utdelning är motsatt.

Formellt kan ett antagonistiskt spel representeras av en trippel , där X och Y är uppsättningarna av strategier för den första respektive andra spelaren, F är payoff-funktionen för den första spelaren, som associerar varje par av strategier (x, y), där är ett reellt tal som motsvarar nyttan av den första spelaren som insåg denna situation.

Eftersom spelarnas intressen är motsatta representerar funktionen F samtidigt den andra spelarens förlust.

Historiskt sett är antagonistiska spel den första klassen av matematiska modeller av spelteori, som användes för att beskriva spelande. Man tror att tack vare detta forskningsämne fick spelteori sitt namn. För närvarande betraktas antagonistiska spel som en del av en bredare klass av icke-kooperativa spel.

1. Teoretisk del

1.1 Grundläggande definitioner och bestämmelser i spelet

Spelet kännetecknas av ett system av regler som bestämmer antalet deltagare i spelet, deras möjliga åtgärder och fördelning av vinster beroende på deras beteende och resultat. En spelare anses vara en deltagare eller en grupp av deltagare i spelet som har några gemensamma intressen för dem som inte sammanfaller med andra gruppers intressen. Därför anses inte alla deltagare vara spelare.

Spelets regler eller villkor bestämmer möjliga beteenden, val och drag för spelare i alla skeden av spelets utveckling. Att göra ett val för spelaren innebär att stanna vid en av hans beteendemöjligheter. Spelaren gör sedan det valet med drag. Att göra ett drag innebär i ett visst skede av spelet att göra hela eller delar av valet på en gång, beroende på de möjligheter som spelreglerna ger. Varje spelare i ett visst skede av spelet gör ett drag enligt det val som gjorts. Den andra spelaren, som vet eller inte vet om den första spelarens val, gör också ett drag. Var och en av spelarna försöker ta hänsyn till information om den tidigare utvecklingen av spelet, om en sådan möjlighet tillåts av spelets regler.

En uppsättning regler som entydigt talar om för spelaren vilket val han ska göra vid varje drag, beroende på situationen som har utvecklats som ett resultat av spelet, kallas spelarens strategi. Strategi i spelteorin innebär en viss komplett handlingsplan för spelaren, som visar hur han bör agera i alla möjliga fall av spelets utveckling. Strategi betyder helheten av alla indikationer för vilken information som helst som är tillgänglig för spelaren i alla skeden av spelets utveckling. Detta visar redan att strategier kan vara bra och dåliga, framgångsrika och misslyckade osv.

Det kommer att finnas ett nollsummespel när summan av vinsterna för alla spelare i vart och ett av dess spel är noll, det vill säga i ett nollsummespel ändras inte det totala kapitalet för alla spelare utan omfördelas mellan spelarna beroende på resultatet. Således kan många ekonomiska och militära situationer ses som nollsummespel.

I synnerhet kallas ett nollsummespel med två spelare antagonistiskt, eftersom målen för spelarna i det är direkt motsatta: vinsten för en spelare sker endast på bekostnad av den andras förlust.

1.1.1 Definition, exempel och lösningar av matrisspel i rena strategier

Nollsummematrisspelet för två spelare kan ses som följande abstrakta spel för två spelare.

Den första spelaren har m strategier i =1, 2,..., m, den andra har n strategier j = 1, 2,..., n. Varje par av strategier (i, j) tilldelas ett nummer a ij , som uttrycker utbetalning av den första spelaren på grund av den andra spelaren om den första spelaren använder sin i:e strategin, och den andra - dess j-te strategi.

Var och en av spelarna gör ett drag: den första spelaren väljer sin i:te strategi (i = 1, 2, ..., m), den andra --din j-th strategi (j = 1, 2,..., n), varefter den första spelaren får utbetalningen en ij på bekostnad av den andra spelaren (om en ij< 0, то это значит, что первый игрок платит второму сумму a ij). На этом игра заканчивается.

Varje strategi för spelaren i = 1, 2,..., t; j = 1, 2,…, n kallas ofta en ren strategi.

Ett nollsummematrisspel med två spelare kommer att kallas helt enkelt ett matrisspel. Uppenbarligen tillhör matrisspelet antagonistiska spel. Det följer av dess definition att för att definiera ett matrisspel räcker det att specificera en matris A = (a ij) i storleksordningen m av den första spelarens vinster.

Med tanke på utdelningsmatrisen

sedan reduceras utförandet av varje spel i matrisspelet med matris A till valet av den första spelaren i:te raden, och av den andra spelaren i den j:te kolumnen och den första spelaren (på bekostnad av den andra) får utdelningen som ligger i matrisen A vid skärningspunkten mellan den i:te raden och den j:te kolumnen.

För att formalisera en verklig konfliktsituation i form av ett matrisspel är det nödvändigt att identifiera och numrera om de rena strategierna för varje spelare och sammanställa en utdelningsmatris.

Nästa steg är att bestämma spelarnas optimala strategier och utdelningar.

Huvudsaken i studien av spel är konceptet med optimala strategier för spelare. Detta koncept har intuitivt följande innebörd: en spelares strategi är optimal om tillämpningen av denna strategi ger honom den största garanterade utdelningen för alla möjliga strategier för den andra spelaren. Baserat på dessa positioner undersöker den första spelaren matrisen A för sina utdelningar enligt formeln (1.1) enligt följande: för varje värde i (i = 1, 2, ..., m) bestäms det lägsta utdelningsvärdet beroende på på de strategier som används av den andra spelaren

(i = 1, 2,..., m) (1,2)

d.v.s. den lägsta utdelningen för den första spelaren bestäms, förutsatt att han tillämpar sin i:te rena strategi, från dessa minimivinster hittas en sådan strategi i=i 0 för vilken denna minsta vinst kommer att vara maximal, d.v.s.

Definition. Siffran b som bestäms av formel (1.3) kallas den lägre nettokostnaden för spelet och visar vilken lägsta utdelning den första spelaren kan garantera sig själv genom att tillämpa sina rena strategier för alla möjliga handlingar av den andra spelaren.

Den andra spelaren, med sitt optimala beteende, bör sträva efter, om möjligt, att minimera utdelningen för den första spelaren på bekostnad av hans strategier. Därför, för den andra spelaren, finner vi

d.v.s. den maximala utdelningen för den första spelaren bestäms, förutsatt att den andra spelaren tillämpar sin j-th ren strategi, då hittar den andra spelaren sin egen j = j 1-strategi för vilken den första spelaren får den lägsta utdelningen, dvs.

Definition. Antalet β som bestäms av formeln (1.5) kallas den övre nettokostnaden för spelet och visar vilken maximal vinst den första spelaren kan garantera sig själv på grund av sina strategier. Med andra ord, genom att tillämpa sina rena strategier kan den första spelaren säkra en utdelning på minst b, och den andra spelaren, genom att tillämpa sina rena strategier, kan förhindra den första spelaren från att vinna mer än c.

Definition. Om i ett spel med matris A de lägre och övre nettopriserna för spelet sammanfaller, d.v.s. b = c, så sägs detta spel ha en sadelpunkt i rena strategier och ett nettospelpris:

n = b = c (1,6)

En sadelpunkt är ett par rena strategier () för den första respektive andra spelaren, under vilka jämlikhet uppnås

Konceptet med en sadelpunkt har följande innebörd: om en av spelarna följer strategin som motsvarar sadelpunkten, kan den andra spelaren inte göra bättre än att följa den strategi som motsvarar sadelpunkten. Med tanke på att spelarens bästa beteende inte bör leda till en minskning av hans utdelning, och det sämsta beteendet kan leda till en minskning av hans utdelning, kan dessa villkor skrivas matematiskt i form av följande relationer:

där i, j är alla rena strategier för den första respektive andra spelaren; (i 0 , j 0) -- strategier som bildar en sadelpunkt. Nedan kommer vi att visa att definitionen av en sadelpunkt är ekvivalent med villkor (1.8).

Baserat på (1.8) är således sadelelementet minimum i den i 0:e raden och maximum i den j 0:e kolumnen i matrisen A. Att hitta sadelpunkten för matrisen A är lätt: i matrisen A, successivt i varje rad, hitta minimumelementet och kontrollera om detta element är maximum i sin kolumn. Om det är sådant, så är det ett sadelelement, och paret av strategier som motsvarar det bildar en sadelpunkt. Ett par rena strategier (i 0 , j 0) för den första och andra spelaren, som bildar en sadelpunkt och ett sadelelement, kallas en lösning på spelet.

Rena strategier i 0 och j 0 som bildar en sadelpunkt kallas optimala rena strategier för den första respektive andra spelaren.

Sats 1. Låt f (x, y) vara en reell funktion av två variabler x A och y B och existera

då b = c.

Bevis. Av definitionen av minimum och maximum följer det

Eftersom x är godtyckligt på vänster sida av (1.11), då

På höger sida om ojämlikhet (1.12) är y godtycklig, alltså

Q.E.D.

Speciellt matrisen () är ett specialfall av funktionen f (x, y), d.v.s. om vi sätter x = i, y = j, = f (x, y), så får vi från sats 1 att ju lägre nettopriset är inte överstiger det övre nettovärdet av spelet i matrisspelet.

Definition. Låt f (x, y) vara en reell funktion av två variabler x A och y B. En punkt (x 0, y 0) kallas en sadelpunkt för funktionen f (x, y) om följande olikheter gäller:

f (x, y 0) f (x 0, y 0) f (x 0, y) (1,14)

för alla x A och y B.

1.2 Optimala blandade strategier och deras egenskaper

Studiet av ett matrisspel börjar med att hitta sin sadelpunkt i rena strategier. Om ett matrisspel har en sadelpunkt i rena strategier, avslutar studien av spelet att hitta denna punkt. Om det i matrisspelet inte finns någon sadelpunkt i rena strategier, så kan vi hitta de lägre och övre rena priserna för detta spel, vilket indikerar att den första spelaren inte bör hoppas på en utdelning som är större än spelets övre pris, och kan vara säker på att få en utdelning inte mindre än det lägre priset på spelet. Sådana rekommendationer angående spelares beteende i ett matrisspel utan sadelpunkt i rena strategier kan inte tillfredsställa forskare och utövare. En förbättring av lösningen av matrisspel bör eftersträvas i användningen av sekretessen för tillämpningen av rena strategier och möjligheten till upprepade upprepningar av spel i form av fester. Så till exempel spelas en serie partier schack, dam, fotboll, och varje gång tillämpar spelarna sina strategier på ett sådant sätt att deras motståndare inte är medvetna om deras innehåll, och längs vägen uppnår vissa utdelningar i genomsnitt genom att spelar hela serien av spel. Dessa vinster är i genomsnitt större än det lägre priset på spelet och mindre än det övre priset på spelet. Ju större detta medelvärde är bättre strategi tillämpas av spelaren. Därför uppstod idén att tillämpa rena strategier slumpmässigt, med en viss sannolikhet. Detta säkerställer fullständigt sekretessen för deras användning. Varje spelare kan ändra sannolikheten för att tillämpa sina rena strategier på ett sådant sätt att han maximerar sin genomsnittliga utdelning och får optimala strategier längs vägen. Denna idé ledde till konceptet blandad strategi.

Definition. En spelares blandade strategi är den kompletta uppsättningen av sannolikheter för att tillämpa hans rena strategier.

Således, om den första spelaren har m rena strategier 1, 2, … i, … m, så är hans blandade strategi x en uppsättning nummer x = (x 1 , x 2 , ..., x i ,…, x t ) som uppfyller relationerna

x i 0 (i = 1, 2, ... , m), = 1. (1,15)

På liknande sätt, för den andra spelaren, som har n rena strategier, är den blandade strategin y mängden siffror y = (y 1 ,…, y j , … y n) som uppfyller relationerna

y j 0 (j = 1, 2, ... , n), = 1. (1,16)

Eftersom varje gång en spelare använder en ren strategi utesluter användningen av en annan, är rena strategier inkompatibla händelser. Dessutom är de de enda möjliga händelserna.

Helt klart är en ren strategi ett specialfall av en blandad strategi. Ja, om i en blandad strategi någon i-te nätet strategi tillämpas med sannolikhet ett, då tillämpas inte alla andra rena strategier. Och denna i-te rena strategi är ett specialfall av en blandad strategi. För att upprätthålla sekretess tillämpar varje spelare sina egna strategier oavsett valet av den andra spelaren.

Definition. Den genomsnittliga utdelningen för den första spelaren i matrisspelet med matris A uttrycks som den matematiska förväntan på hans utdelning

E (A, x, y) = (1,20)

Uppenbarligen är den genomsnittliga utdelningen för den första spelaren en funktion av två uppsättningar av variabler x och y. Den första spelaren strävar efter att maximera sin genomsnittliga utdelning E (A, x, y) genom att ändra sina blandade strategier x, och den andra spelaren försöker göra E (A, x, y) minimal genom sina blandade strategier, d.v.s. för att lösa spelet är det nödvändigt att hitta sådana x, y för vilka det övre priset för spelet uppnås.

1.3 Beställ 22 spel

Ett matrisspel av ordning 22 ges av följande utdelningsmatris för den första spelaren:

Lösningen av detta spel bör börja med att hitta en sadelpunkt i rena strategier. För detta ändamål, leta reda på minimumelementet i den första raden och kontrollera om det är maximum i dess kolumn. Om ett sådant element inte hittas, kontrolleras den andra raden på samma sätt. Om ett sådant element finns i den andra raden är det ett sadelelement.

Genom att hitta ett sadelelement, om det finns ett, slutar processen att hitta dess lösning, eftersom i detta fall priset på spelet hittas - ett sadelelement och en sadelpunkt, dvs ett par rena strategier för första och andra spelare, vilket utgör optimala rena strategier. Om det inte finns någon sadelpunkt i rena strategier, så är det nödvändigt att hitta en sadelpunkt i blandade strategier, som nödvändigtvis existerar enligt matrisspelens huvudsats.

Beteckna med x=(x 1 ,x 2), y=(y 1 ,y 2) de blandade strategierna för den första respektive andra spelaren. Kom ihåg att x 1 betyder sannolikheten för att den första spelaren använder sin första strategi, och x 2 \u003d 1 - x 1 är sannolikheten att använda sin andra strategi. På samma sätt för den andra spelaren: 1 - sannolikheten att använda den första strategin, y 2 = 1 - 1 - sannolikheten att använda den andra strategin.

Enligt satsens följd är det för optimaliteten av blandade strategier x och y nödvändigt och tillräckligt att för icke-negativa x 1 , x 2 , y 1 , y 2 gäller följande relationer:

Vi visar nu att om matrisspelet inte har någon sadelpunkt i rena strategier, så måste dessa ojämlikheter förvandlas till jämlikheter:

Verkligen. Låt spelet inte ha någon sadelpunkt i rena strategier, då tillfredsställer de optimala värdena för blandade strategier ojämlikheterna

0<<1, 0<< 1,

0< <1, 01. (1.25)

Antag att båda ojämlikheterna från (1.22) är strikta

då, enligt satsen, y 1 = y 2 = 0, vilket motsäger villkor (1.25).

Det kan på liknande sätt bevisas att båda ojämlikheterna i (1.23) inte kan vara strikta ojämlikheter.

Antag nu att en av ojämlikheterna (1.22) kan vara strikt, till exempel den första

Det betyder att enligt satsen y 1 = 0, y 2 =1. Därför får vi från (1.23).

Om båda ojämlikheterna (1.24) är strikta, så av satsen x1 = x2 = 0, vilket motsäger (1.25). Men om en 12 a 22 är en av ojämlikheterna (1,27) strikt, och den andra är en jämlikhet. Dessutom kommer likheten att gälla för det större elementet från en 12 och en 22, dvs en olikhet från (1.27) måste vara strikt. Till exempel en 12< а 22 . Тогда справедливо а 12 < v, а это равносильно тому, что первое неравенство из (1.24) строгое. Тогда согласно теореме должно х 1 = 0, что противоречит условию (1.25). Если а 12 = а 22 , то оба неравенства (1.27) превращаются в равенства и тогда можно положить х 1 = 0, что противоречит (1.25). Итак, предположение о том, что первое неравенство из (1.22) может быть строгим, не справедливо. Аналогично можно показать, что второе неравенство из (1.22) также не может быть строгим.

Således visas det att om matrisspelet inte har någon sadelpunkt i rena strategier, så förvandlas ojämlikheter (1,22) till likheter för den första spelarens optimala strategier. Liknande argument om ojämlikheter (1.23) kommer att leda till att i detta fall måste ojämlikheterna (1.23) vara jämlikheter.

Så om ett matrisspel av ordning 22 inte har någon sadelpunkt, så kan spelarnas optimala blandade strategier och priset på spelet bestämmas genom att lösa ekvationssystemet (1.24). Det är också fastställt att om i ett 2x2 matrisspel en av spelarna har en optimal ren strategi, så har den andra spelaren också en optimal ren strategi.

Därför, om ett matrisspel inte har en sadelpunkt i rena strategier, så måste det ha en lösning i blandade strategier, som bestäms från ekvationer (1.24). Systemlösning (1.25)

1.4 Algebraisk metod

Det finns två fall för att lösa problem med den algebraiska metoden:

1. matrisen har en sadelpunkt;

2. matrisen har ingen sadelpunkt.

I det första fallet är lösningen ett par strategier som utgör spelets sadelpunkt. Låt oss överväga det andra fallet. Lösningar här bör sökas i blandade strategier:

Hitta strategier och När den första spelaren använder sin optimala strategi kan den andra spelaren till exempel tillämpa två sådana rena strategier

Samtidigt, på grund av egenskapen, om en av spelarna använder den optimala blandade strategin, och den andra - vilken som helst ren, inkluderad i sin optimala blandade strategi med en sannolikhet som inte är noll, då den matematiska förväntan på utdelningen alltid förblir oförändrad och lika med spelets pris, d.v.s.

Utdelningen måste i vart och ett av dessa fall vara lika med värdet på spelet V. I det här fallet är följande relationer giltiga:

Ett system av ekvationer som liknar (2.5), (2.6) kan också sammanställas för den optimala strategin för den andra spelaren:

Med hänsyn till normaliseringsvillkoret:

Låt oss lösa ekvationen (1.37) - (1.41) tillsammans med hänsyn till de okända, och inte alla på en gång, utan tre åt gången: separat (1.36), (1.38), (1.40) och (1.37), (1.39) , (1,41). Som ett resultat av lösningen får vi:

1.5 Grafisk metod

En ungefärlig lösning av spelet 22 kan ganska enkelt erhållas med den grafiska metoden. Dess kärna är följande:

Figur 1.1 - hitta en sektion av enhetslängd

Välj en sektion av enhetslängd på abskissaxeln. Den vänstra änden av den kommer att avbilda den första spelarens första strategi och den högra änden av den andra. Alla mellanliggande punkter motsvarar den första spelarens blandade strategier, och längden på segmentet till höger om punkten är lika med sannolikheten för att använda den första strategin, och längden på segmentet till vänster är sannolikheten att använda den andra strategin av den första spelaren.

Två axlar I-I och II-II utförs. På I-I kommer vi att skjuta upp utdelningen när den första spelaren använder den första strategin, på II-II när han använder den andra strategin. Låt till exempel den andra spelaren tillämpa sin första strategi, sedan ska värdet plottas på I-I-axeln och värdet på II-II-axeln

För varje blandad strategi för den första spelaren kommer hans utdelning att bestämmas av storleken på segmentet. Linje I-I motsvarar tillämpningen av den första strategin av den andra spelaren, vi kommer att kalla det den andra spelarens första strategi. Den andra strategin för den andra spelaren kan konstrueras på liknande sätt. Då, i allmänhet, kommer den grafiska visningen av spelmatrisen att ha följande form:

Figur 1.2 - hitta priset på spelet

Det bör dock noteras att denna konstruktion utfördes för den första spelaren. Här är längden på segmentet lika med värdet på spelet V.

1N2-linjen kallas den nedre payoff-linjen. Det syns tydligt här att poängen N motsvarar det maximala värdet av den garanterade utdelningen för den första spelaren.

Generellt sett kan strategin för den andra spelaren också bestämmas från denna figur, till exempel på sådana sätt. På I-I-axeln:

eller på axel II-II

Men strategin för den andra spelaren kan också definieras på samma sätt som den görs för den första spelaren, d.v.s. bygga ett sådant diagram.

Figur 1.3 - definition av den andra spelarens strategi

Här är linjen 1N2 den övre gränsen för förlusten. Punkt N motsvarar minsta möjliga förlust för den andra spelaren, och den bestämmer strategin.

Beroende på de specifika värdena för koefficienterna kan grafmatriserna också ha en annan form, till exempel enligt följande:

Figur 1.4 - bestämmer den optimala strategin för den första spelaren

I en sådan situation är den optimala strategin för den första spelaren ren:

1.6 Spel 2n eller m2

I spel av ordning 2n har den första spelaren 2 rena strategier, och den andra spelaren har n rena strategier, dvs. Utdelningsmatrisen för den första spelaren är:

Om ett sådant spel har en sadelpunkt är det lätt att hitta det och få en lösning.

Anta att spelet har sadelpoäng. Då är det nödvändigt att hitta sådana blandade strategier och, respektive, den första och andra spelaren och priset på spelet v, som uppfyller relationerna:

Eftersom spelet inte har någon sadelpunkt ersätts ojämlikheten (1,54) av ojämlikheterna

För att lösa system (1.56), (1.55), (1.53) är det lämpligt att använda den grafiska metoden. För ändamålet introducerar vi notationen för den vänstra sidan av ojämlikheten (1,53)

matrisspel matematisk modell

eller genom att ställa in från (1.55) och utföra enkla transformationer, får vi

var är den genomsnittliga utdelningen för den första spelaren, förutsatt att han använder sin blandade strategi, och den andra - hans j-te rena strategi.

Enligt uttrycket motsvarar varje värde j=1, 2, …, n en rät linje i ett rektangulärt koordinatsystem.

Målet för den andra spelaren är att minimera utdelningen för den första spelaren genom att välja hans strategier. Därför räknar vi

var är den nedre gränsen för begränsningsuppsättningen. I figur 1.6 visas grafen för funktionen med en tjock linje.

Hosted på http://www.allbest.ru/

Figur 1.6 - funktionsdiagram

Målet för den första spelaren är att maximera sin utdelning genom val, d.v.s. Beräkna

I figur 1.6 betyder punkten det maximala värdet som erhålls vid. Priset på spelet, eftersom:

Således bestäms den optimala blandade strategin för den första spelaren och ett par rena strategier för den andra spelaren grafiskt, vilka bildar en punkt vid skärningspunkten.Figur 1.6 visar den andra spelarens andra och tredje strategi. För sådana strategier förvandlas ojämlikheter (1,53) till jämlikheter. I figur 1.6 är dessa strategier j=2, j=3.

Nu kan vi lösa ekvationssystemet

och bestäm exakt värdena för och (grafiskt bestäms de ungefär). Lägg sedan alla värden vid de j för vilka de inte bildar en punkt, lös ekvationssystemet (1.56) För exemplet som visas i figur 1.6 är detta följande system:

och resten Detta system kan lösas genom att luta Om, för vissa j=j 0, strategierna för den andra spelaren bildar en punkt M 0 och då det maximala värdet för den nedre gränsen för begränsningsmängderna representeras av ett segment parallellt med axeln I det här fallet har den första spelaren oändligt många optimala värden och priset på spelet. Detta fall visas i figur 1.7, där och segmentet MN representerar den övre gränsen, de optimala värdena ligger inom gränserna. andra spelaren har en ren optimal strategi j=j 0 .

Matrisspel av storleksordningen m2 löses också med den grafiska metoden. Utdelningsmatrisen för den första spelaren i detta fall har formen

De blandade strategierna för den första respektive andra spelaren definieras på samma sätt som i fallet med spel av ordning 2n. Låt värdet från 0 till 1 plottas längs den horisontella axeln, värdet av den genomsnittliga utdelningen) för den första spelaren på den vertikala axeln under villkoren att den första spelaren tillämpar sin rena i:te strategi (i=1, 2, ..., m), den andra - hans blandade strategi (y 1 , 1- y 1) =y. Till exempel, när m=4 grafiskt) kan representeras som visas i figur 1.7.

Figur 1.7 - funktionsdiagram)

Den första spelaren försöker maximera sin genomsnittliga utdelning, så han försöker hitta

Funktionen visas som en tjock linje och representerar den övre gränsen för begränsningsuppsättningen. Den andra spelaren försöker minimera genom att välja sin strategi, d.v.s. värdet motsvarar

I figuren indikeras värdet med en punkt. Med andra ord definieras sådana två strategier för den första spelaren och sannolikheten för den andra spelaren för vilka jämlikhet uppnås

Från figuren ser vi att priset på spelet är ordinatan för punkten, sannolikheten är abskissan för punkten. För resten av de rena strategierna för den första spelaren i den optimala blandade strategin måste ().

Således, lösningssystem (1,69), vi får den optimala strategin för den andra spelaren och värdet av spelet. Vi hittar den optimala blandade strategin för den första spelaren genom att lösa följande ekvationssystem:

1.7 Matrismetod för att lösa spel

Beteckningar:

Vilken kvadratisk delmatris som helst av ordningsmatrisen

Matris (1);

Matris transponerad till;

Matris fäst till B;

- (1) en matris erhållen från X genom att ta bort de element som motsvarar raderna som raderades från när de togs emot;

- (1) en matris erhållen från radering av element som motsvarar raderna som raderades från när de togs emot.

Algoritm:

1. Välj en kvadratisk delmatris av ordningsmatrisen () och beräkna

2. Om någon eller, kassera den hittade matrisen och försök med en annan matris.

3. Om (), (), beräknar och bygger vi X och från och, adderar nollor på lämpliga platser.

Kontrollera om ojämlikheterna är uppfyllda

för varje (1,75)

och ojämlikheter

för varje (1,76)

Om ett av förhållandena inte är uppfyllt, försöker vi med ett annat. Om alla relationer är giltiga, då X, och de önskade lösningarna.

1.8 Metoden för successiv approximation av priset på spelet

I studien av spelsituationer kan det ofta hända att det inte är nödvändigt att få en exakt lösning på spelet eller att det av någon anledning är omöjligt eller mycket svårt att hitta det exakta värdet av spelkostnaden och optimala blandade strategier. Sedan kan du använda ungefärliga metoder för att lösa matrisspelet.

Låt oss beskriva en av dessa metoder - metoden för successiv approximation av spelpriset. Antalet utdelningar som beräknas med metoden ökar ungefär i proportion till antalet rader och kolumner i utdelningsmatrisen.

Kärnan i metoden är följande: mentalt spelas spelet många gånger, d.v.s. sekventiellt, i varje spelspel, väljer spelaren den strategi som ger honom den största totala (totala) utdelningen.

Efter en sådan implementering av vissa spel, beräknar den medelvärdet av den första spelarens vinst och den andra spelarens förlust, och deras aritmetiska medelvärde tas som ett ungefärligt värde på spelpriset. Metoden gör det möjligt att hitta ett ungefärligt värde för de optimala blandade strategierna för båda spelarna: det är nödvändigt att beräkna frekvensen för tillämpningen av varje ren strategi och ta det som ett ungefärligt värde i den optimala blandade strategin för motsvarande spelare.

Det kan bevisas att med en obegränsad ökning av antalet programspel, kommer den genomsnittliga vinsten för den första spelaren och den genomsnittliga förlusten för den andra spelaren på obestämd tid att närma sig spelets pris, och de ungefärliga värdena för blandade strategier i fallet när spelets lösning är unik kommer att tendera till de optimala blandade strategierna för varje spelare. Generellt sett är approximationen av värden över de angivna värdena till de sanna värdena långsam. Denna process kan dock lätt mekaniseras och på så sätt hjälpa till att få en lösning på spelet med den grad av noggrannhet som krävs även med utdelningsmatriser av en relativt stor ordning.

2. Praktisk del

Paret bestämmer vart de ska gå på promenad och spendera tid till förmån för två.

Flickan bestämmer sig för att gå en promenad i parken för att få lite frisk luft, på kvällen för att gå och se en film på närmaste biograf.

Killen erbjuder sig att gå till technoparken efter att ha sett matchen för fotbollsspelarna i den lokala klubben på centralstadion.

I enlighet med detta måste du ta reda på hur länge målet för en av spelarna kommer att uppnås. Utbetalningsmatrisen kommer att se ut så här:

Tabell 1. Payoff Matrix

Sedan 1 2 finns det uppenbarligen ingen sadelpunkt i detta spel i rena strategier. Därför använder vi följande formler, och vi får:

Hosted på http://www.allbest.ru/

2.2 Spela 2xn och mx2

Problem 1(2xn)

Två grödor odlas för torra och fuktiga klimat.

Och naturens tillstånd kan betraktas som: torr, våt, måttlig.

Hosted på http://www.allbest.ru/

Det maximala värdet på M() uppnås vid punkten M som bildas av skärningspunkten mellan linjerna som motsvarar j=1, j"=2. Därför antar vi: ,

Problem 2 (mx2)

Killen och tjejen överväger alternativ för vart de ska åka till helgen.

Valet av en viloplats kan representeras som: en park, en biograf, en restaurang.

Hosted på http://www.allbest.ru/

Det maximala värdet på M() uppnås vid punkten E som bildas av skärningspunkten mellan linjerna som motsvarar j=1, j"=2. Därför antar vi: ,

För att bestämma värdet v måste du lösa följande ekvationer:

2.5 Matrismetod

Två konkurrerande restauranger (cateringanläggningar) tillhandahåller följande uppsättningar tjänster. Den första restaurangen ligger i centrum och den andra i utkanten av staden.

Den centrala restaurangen erbjuder följande tjänster:

1) dyrare och bättre kundservice;

2) rätter är inriktade på det franska köket;

Den andra restaurangen erbjuder:

1) inte dyr och högkvalitativ service;

2) menyn kombinerar olika kända kök från världen;

3) även regelbundna kampanjer och rabatter;

4) utför leverans och tar emot beställningar för hemleverans.

I enlighet med uppdraget kommer vinsten för en dag mellan de två restaurangerna att fördelas enligt följande:

Tabell 2. Payoff Matrix

Lösa ett spel av formen på ett matrissätt:

Det finns sex submatriser och:

Tänk på matrisen:

x 1 =? 0,x2=? 0

Eftersom x 2 =< 0, то мы отбрасываем.

Betrakta nu matrisen:

x 1 =? 0,x2=? 0

Spelpris.

Detta förhållande strider mot kravet, så det är inte lämpligt.

Betrakta nu matrisen:

x 1 = , x 2 = ? 0,

y 1 =< 0, y 2 = ? 0.

Eftersom y 1 =< 0, то мы отбрасываем и.

Betrakta nu matrisen:

x 1 \u003d, x 2 \u003d 0, eftersom x 2 \u003d 0, då kasserar vi och.

Betrakta nu matrisen:

x 1 = , x 2 = ? 0. Sedan x 1 \u003d 0, då kasserar vi och.

Betrakta nu matrisen:

x 1 = , x 2 =, y 1 = , y 2 =, sedan fortsätter vi vidare:

x 1 = , x 2 =, y 1 = , y 2 = eller

Spelpris.

Nu kontrolleras huvudförhållandena:

Hosted på http://www.allbest.ru/

Svar: x 1 =, x 2 =, y 1 =, y 2 =, y 3 = 0, y 4 = 0,.

Brun metod

På begäran av arbetarna i ett visst företag förhandlar fackföreningen med sin ledning om att organisera varma måltider på företagets bekostnad. Den fackförening som företräder arbetarnas intressen ser till att måltiden är av högsta möjliga kvalitet och därför dyrare. Bolagets ledning har motstridiga intressen. I slutändan kom parterna överens om följande. Fackföreningen (spelare 1) väljer ett av tre företag (A 1 , A 2 , A 3) som tillhandahåller varma måltider, och företagsledningen (spelare 2) väljer en uppsättning rätter från tre möjliga alternativ (B 1 , B 2 , B 3) . Efter undertecknandet av avtalet bildar fackföreningen följande betalningsmatris, vars delar representerar kostnaden för en uppsättning rätter:

Låt spelet ges av följande utdelningsmatris:

Anta att den andra spelaren har valt sin andra strategi, då får den första:

2 om han använder sin första strategi,

3 om han använder sin 3:e strategi.

De erhållna värdena sammanfattas i tabell 1.

Tabell 3. Strategi för den andra spelaren

Tabell 3 visar att med den 2:a strategin för den andra spelaren, kommer den första spelaren att få den största utdelningen 3 med sin 2:a eller 3:e strategi. Eftersom den första spelaren vill få maximal utdelning, svarar han på den andra spelarens andra strategi med sin andra strategi. Med den andra strategin för den första spelaren kommer den andra att förlora:

1 om han tillämpar sin första strategi,

3 om han använder sin andra strategi,

4 om han använder sin tredje strategi.

Tabell 4. Strategi för den första spelaren

Tabell 2 visar att med den första spelarens 2:a strategi kommer den andra spelaren att ha minst förlust 1 om han tillämpar sin 1:a strategi. Eftersom den andra spelaren vill förlora mindre, kommer han som svar på den första spelarens andra strategi att tillämpa sin första strategi. De erhållna resultaten sammanfattas i tabell 5.

Tabell 5. Strategier för den första respektive andra spelaren

I tabell. 5 i kolumnen för den andra spelarens strategi i den andra raden är siffran 1, vilket indikerar att det i det andra spelet är fördelaktigt för den andra spelaren att använda sin första strategi; i kolumnen och är den största genomsnittliga utdelningen 3 för den första spelaren, som han fick i det första spelet; kolumnen w innehåller den minsta genomsnittliga förlusten 1 som den andra spelaren fick i det första spelet; kolumnen v innehåller det aritmetiska medelvärdet v = (u + w) -- det vill säga det ungefärliga värdet av spelets pris, erhållet som ett resultat av att spela ett spel i spelet. Om den andra spelaren använder sin 1:a strategi, kommer den första spelaren att få 3, 1, 2, respektive med sin 1:a, 2:a, 3:e strategi, och den totala utdelningen för den första spelaren för båda spelen blir:

2 + 3=5 med sin första strategi,

3 + 1=4 med sin andra strategi,

3 + 2=5 med sin 3:e strategi.

Dessa totala vinster registreras på den andra raden i tabellen. 3 och i kolumnerna som motsvarar den första spelarens strategier: 1, 2, 3.

Av alla totala vinster är den största 5. Den erhålls med den första och 3:e strategin för den första spelaren, sedan kan han välja vilken som helst av dem; säg, i sådana fall när det finns två (eller flera) identiska totala utdelningar, väljs strategin med det minsta antalet (i vårt fall måste vi ta den första strategin).

Med den första spelarens 1:a strategi kommer den andra spelaren att förlora 3, 2, 3 respektive till sin 1:a, 2:a, 3:e strategi, och den totala förlusten för den andra spelaren för båda spelen blir:

1 + 3=4 med sin första strategi,

3 + 2=5 med hans andra strategi,

4 + 3=7 med sin tredje strategi.

Dessa totala förluster registreras på den andra raden i tabellen. 5 och i kolumnerna som motsvarar den andra spelarens 1:a, 2:a, 3:e strategi.

Av alla de totala förlusterna för den andra spelaren är den minsta 4. Den erhålls med hans första strategi, därför måste den andra spelaren i det tredje spelet tillämpa sin första strategi. I kolumnen och lägg den största totala utdelningen för den första spelaren i två spel, dividerat med antalet spel, d.v.s.; kolumnen w innehåller den minsta totala förlusten för den andra spelaren i två spel, dividerat med antalet spel, dvs. det aritmetiska medelvärdet av dessa värden sätts i kolumn v, dvs = Detta nummer tas som ett ungefärligt värde på priset på spelet med två "spelade" spel.

Följande tabell 4 erhålls således för två uppsättningar av spelet.

Tabell 6. Totala vinster och förluster för spelare i två spelade matcher

I den tredje raden i Tabell 6, i strategikolumnen för den andra spelaren, finns siffran 1, vilket indikerar att i det tredje spelet måste den andra spelaren tillämpa sin första strategi. I det här fallet vinner den första spelaren 3, 1, 2, med hjälp av sin 1:a, 2:a, 3:e strategi, och hans totala utdelning för tre spel blir:

3 + 5 = 8 vid hans första strategi,

1 +4 = 5 med hans andra strategi,

2 + 5 = 7 för hans tredje strategi.

Dessa totala vinster för den första spelaren registreras i den tredje raden i tabell 6 och kolumner som motsvarar hans strategier 1, 2, 3. Eftersom den största totala vinsten 8 för den första spelaren erhålls med den 1:a strategin, väljer han den 1:a därefter. .

Med den första spelarens 1:a strategi kommer den andra spelaren att förlora 3, 1, 2 respektive 1:a, 2:a, 3:e strategin, och den totala förlusten för den andra spelaren för båda spelen blir:

3 + 4=7 med sin första strategi,

2 + 5=7 med sin andra strategi,

3 + 7=10 med sin tredje strategi.

Dessa totala förluster registreras på den tredje raden i tabellen. 6 och i kolumnerna som motsvarar den andra spelarens 1:a, 2:a, 3:e strategi. Av alla hans totala förluster är 7 den minsta och erhålls med hans 1:a och 2:a strategi, då måste den andra spelaren tillämpa sin 1:a strategi.

I tabell. 6 i den tredje raden i kolumnen och den största totala vinsten för den första spelaren i tre spel, dividerat med spelets nummer, dvs. kolumn w innehåller den minsta totala förlusten för den andra spelaren i tre matcher, dividerat med antalet spel, dvs. i kolumn v sätter deras aritmetiska medelvärde

Därmed får vi bordet. 7 för tre parter.

Tabell 7. Totala vinster och förluster för spelare i tre spelade matcher

Tabell 8. Finalbord med tjugo spelade matcher

Från tabell. 7 och 8, kan det ses att i 20 förlorade spel förekommer strategierna 1, 2, 3 för den första spelaren 12, 3 respektive 5 gånger, därför är deras relativa frekvenser lika; strategierna 1, 2, 3 för den andra spelaren inträffar 7 respektive 11,2 gånger, därför är deras relativa frekvenser lika; ungefärligt värde på spelets pris. Denna uppskattning är tillräckligt bra.

Sammanfattningsvis noterar vi att om spelet har mer än en lösning, kommer de ungefärliga värdena för kostnaden för spelet fortfarande att närma sig den verkliga kostnaden för spelet på obestämd tid, och de relativa frekvenserna för uppkomsten av strategierna för spelet spelare kommer inte längre nödvändigtvis att närma sig spelarnas verkliga optimala blandade strategier.

Analys av resultat

I detta kursarbete studeras materialet för att hitta en lösning på antagonistiska spel med en grafisk, matrismetod, metoden för successiv approximation av spelets pris. De optimala strategierna för den första och andra spelaren, såväl som kostnaden för spelet i 2x2, 2xn och mx2-spel, samt i spel som använder matrismetoden och Browns metod, finns.

På exemplet med ett par modellerades ett 2x2-spel, som löstes med en algebraisk och grafisk metod. Lösningen av spelet med den algebraiska metoden visar att genom att tillämpa sina optimala blandade strategier kommer den första och andra spelaren att spendera 4,6 timmar tillsammans. Den grafiska lösningen av problemet visade sig med ett litet fel och uppgick till 4,5 timmar.

Och även två uppgifter 2xn och mx2 modellerades. I 2xn-problemet övervägdes jordbrukskultur och strategin visar att det är bättre att plantera fältet 50 gånger 50, och priset på spelet var 3,75 miljoner rubel. Och i mx2-problemet övervägdes ett par, vars strategi visade att det är billigare att gå till parken och biografen, och priset och kostnaden kommer att vara 4,3 rubel.

En uppgift modellerades för matrismetoden, där två restauranger övervägdes, lösningen av problemet visade att när man tillämpar sin optimala blandade strategi kommer vinsten för den första restaurangen att vara 15,6 miljoner rubel, och när man använder sin optimala blandade strategi av den andra restaurangen tillåter inte den första att tjäna mer än 15,6 miljoner rubel. Lösningen med den grafiska metoden gav ett fel och priset på spelet var 14,9 miljoner rubel.

För Brown-metoden utarbetades en uppgift där facket och företagsledningen beaktas, deras uppgift är att ge mat åt arbetarna. När båda spelarna använder sina optimala strategier blir maten per person 2,45 tusen rubel.

Lista över använda källor

1) Vilisov V.Ya. Föreläsningsanteckningar "Spelteori och statistiska lösningar", - Branch - "Voskhod" MAI. 1979. 146 sid.

2) Krushevsky A.V. Spelteori, - Kiev: Vishcha-skolan, 1977. - 216 s.

3) Cherchmen U., Akof R., Arnof L., Introduktion till operationsforskning. - M.: Vetenskap. 1967. - 488 sid.

4) http://www.math-pr.com/exampl_gt2.htm

5) http://ru.wikipedia.org/wiki/%D0%90%D0%BD%D1% 82%D0%B0%D0 %B3%D0%BE%D0%BD%D0%B8%D1%81 %D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%B8%D0%B3%D1%80%D0%B0

Hosted på Allbest.ru

Liknande dokument

Beslutsfattande som en speciell typ av mänsklig aktivitet. Rationell representation av spelmatrisen. Exempel på matrisspel i rena och blandade strategier. Operationsforskning: sambandet mellan linjära programmeringsproblem och en spelteoretisk modell.

terminsuppsats, tillagd 2010-05-05


Spel upprepade många gånger, deras utmärkande egenskaper och stadier. Blandade strategier, förutsättningar och möjligheter för deras användning i praktiken. En analytisk metod för att lösa ett 2 x 2-spel Grundläggande satser för rektangulära spel. Algebraiska lösningar.

presentation, tillagd 2013-10-23


Grundläggande definitioner av teorin om bimatrisspel. Ett exempel på ett bimatrisspel "Student-Teacher". Blandade strategier i bimatrix-spel. Sök efter "jämviktssituation". 2x2 bimatrisspel och formler för fallet när varje spelare har två strategier.

abstrakt, tillagt 2011-02-13


Studiet av allmän information om matris- och antagonistiska spel. Begreppet positionsspel, träd, informationsuppsättning. Hänsyn till maximinprincipen och jämviktsprincipen. Pareto optimalitet. Positionellt icke-antagonistiskt spel, dess egenskaper.

terminsuppsats, tillagd 2014-10-17


Spelteori är en gren av matematiken, vars ämne är studiet av matematiska modeller för att fatta optimala beslut i en konflikt. Iterativ Brown-Robinson-metod. Monotone iterativ algoritm för att lösa matrisspel.

avhandling, tillagd 2007-08-08


Sammanställning av payoff-matrisen, sök efter de lägre och övre nettopriserna för spelet, maximin- och minimax-strategierna för spelarna. Förenkling av betalningsmatrisen. Att lösa ett matrisspel med hjälp av reduktion till ett linjärt programmeringsproblem och tillägget "Sök efter en lösning".

test, tillagt 2014-10-11


Spelteori är en matematisk teori om konfliktsituationer. Utveckling av en matematisk modell av ett tvåpersoners nollsummespel, dess implementering i form av programkoder. Problemlösningsmetod. In- och utdata. Program, användarmanual.

terminsuppsats, tillagd 2013-08-17


Grundläggande information om simplexmetoden, utvärdering av dess roll och betydelse i linjär programmering. Geometrisk tolkning och algebraisk betydelse. Hitta maximum och minimum för en linjär funktion, specialfall. Lösning av problemet med matris simplex-metoden.

avhandling, tillagd 2015-01-06


Tekniker för att konstruera matematiska modeller av datorsystem som återspeglar strukturen och processerna för deras funktion. Antalet filåtkomster under den genomsnittliga uppgiften. Fastställande av möjligheten att placera filer i externa minnesenheter.

laboratoriearbete, tillagt 2013-06-21


Designa en matematisk modell. Beskrivning av spelet tic-tac-toe. Logisk spelmodell baserad på boolesk algebra. Digitala elektroniska enheter och utveckling av deras matematiska modell. Spelkonsol, spelkontroll, spelbrädesnöre.

Spelteori är en teori om matematiska modeller för beslutsfattande under förhållanden av konflikt eller osäkerhet. Det antas att parternas agerande i spelet kännetecknas av vissa strategier - uppsättningar av handlingsregler. Om den ena sidans vinst oundvikligen leder till att den andra sidan förlorar, så talar de om antagonistiska spel. Om uppsättningen av strategier är begränsad, så kallas spelet ett matrisspel och lösningen kan erhållas mycket enkelt. Lösningarna som erhålls med hjälp av spelteorin är användbara för att göra upp planer inför eventuellt motstånd från konkurrenter eller osäkerhet i den yttre miljön.

Om bimatrisspelet är antagonistiskt, så bestäms utdelningsmatrisen för spelare 2 helt av utdelningsmatrisen för spelare 1 (motsvarande element i dessa två matriser skiljer sig endast i tecken). Därför beskrivs ett antagonistiskt bimatrisspel fullständigt av en enda matris (utbetalningsmatrisen för spelare 1) och kallas följaktligen ett matrisspel.

Det här spelet är antagonistiskt. I det j \u003d x2 - O, P och R (O, O] \u003d H (P, P) \u003d -I och R (O, P) \u003d R (P, O) \u003d 1, eller i matrisform o sid

Låt någon klass av spel Г vara "spegelstängd", d.v.s. tillsammans med vart och ett av dess spel innehåller ett spegelisomorft spel (eftersom alla spel som är spegelisomorfa till en given är isomorfa till varandra, kan vi, i enlighet med vad som just har sagts, tala om ett spegelisomorft spel). En sådan klass är till exempel klassen för alla antagonistiska spel eller klassen för alla matrisspel.

Med tanke på definitionen av acceptabla situationer i det antagonistiska spelet erhåller vi att situationen (X, Y) i den blandade förlängningen av matrisspelet är acceptabel för spelare 1 om och endast om för någon x G x ojämlikheten

Processen att konvertera spel till symmetriska kallas symmetri. Vi beskriver här en metod för symmetri. En annan, fundamentalt annorlunda version av symmetriisering kommer att ges i avsnitt 26.7. Båda dessa varianter av symmetriisering är faktiskt tillämpliga på godtyckliga antagonistiska spel, men kommer att formuleras och bevisas endast för matrisspel.

Således sammanfaller de initiala termerna och beteckningarna för teorin om allmänna antagonistiska spel med motsvarande termer och beteckningar för teorin om matrisspel.

För ändliga antagonistiska (matris) spel bevisades existensen av dessa extrema av oss i kapitel 10. 1, och hela poängen var att etablera deras jämlikhet, eller åtminstone att hitta sätt att övervinna deras ojämlikhet.

Övervägandet av matrisspel visar redan att det finns antagonistiska spel utan jämviktssituationer (och även utan e-jämviktssituationer för tillräckligt litet e > 0) i spelarnas initialt givna strategier.

Men varje ändligt (matris) spel kan utökas till ett oändligt spel, till exempel genom att förse varje spelare med valfritt antal dominerade strategier (se 22 kap. 1). Uppenbarligen kommer en sådan expansion av spelarens uppsättning strategier inte att innebära en utökning av hans möjligheter, och hans faktiska beteende i det utökade spelet bör inte skilja sig från hans beteende i originalspelet. Således fick vi omedelbart ett tillräckligt antal exempel på oändliga antagonistiska spel som inte har sadelpunkter. Det finns också exempel på det här slaget.

För att implementera maximin-principen i ett oändligt antagonistiskt spel är det alltså nödvändigt, som i fallet med ett ändligt (matris) spel, en viss utökning av spelarnas strategiska kapacitet. För 96

Liksom i fallet med matrisspel (se kap. 1, 17) spelar för generella antagonistiska spel en viktig roll av begreppet ett blandat strategispektrum, som här dock måste ges en mer allmän definition.

Slutligen, notera att uppsättningen av alla blandade strategier för spelare 1 i ett godtyckligt antagonistiskt spel är som i matrisen

Även en övervägande av antagonistiska spel visar att ett stort antal sådana spel, inklusive ändliga, matrisspel har jämviktssituationer inte i de ursprungliga, rena strategierna, utan endast i generaliserade, blandade strategier. Därför är det för allmänna, icke-antagonistiska, icke-samarbetande spel naturligt att leta efter jämviktssituationer just i blandade strategier.

Så till exempel (se fig. 3.1) har vi redan noterat att "Entreprenören" nästan aldrig behöver hantera beteendemässig osäkerhet. Men om vi tar den konceptuella nivån av typen "Administratör", så är allt precis tvärtom. I regel är den huvudsakliga typen av osäkerhet som en sådan "vår beslutsfattare" måste möta "Konflikt". Nu kan vi förtydliga att detta vanligtvis är en icke strikt rivalitet. Något mer sällan fattar "Administratören" beslut under förhållanden av "naturlig osäkerhet", och än mer sällan möter han en strikt, antagonistisk konflikt. Dessutom inträffar intressekonflikten när man fattar beslut av "Administratören" så att säga "en gång", det vill säga i vår klassificering spelar han ofta bara ett (ibland ett mycket litet antal) spel i spelet. Skalor för att utvärdera konsekvenser är oftare kvalitativa än kvantitativa. "Administratörens" strategiska oberoende är ganska begränsat. Med hänsyn till ovanstående kan man hävda att problemsituationer av denna storleksordning oftast måste analyseras med hjälp av icke-samverkande icke-antagonistiska bi-matrisspel, dessutom i rena strategier.

Principer för att lösa matrisantagonistiska spel

Som ett resultat är det rimligt att förvänta sig att motståndarna i spelet som beskrivs ovan kommer att följa sina valda strategier. Matrisantagonistiskt spel för vilket max min fiv = min max Aiy>

Men inte alla matrisantagonistiska spel är helt bestämda, och i det allmänna fallet

Således, i det allmänna fallet, för att lösa ett matrisantagonistiskt spel med dimension /uxl, är det nödvändigt att lösa ett par dubbla linjära programmeringsproblem, vilket resulterar i en uppsättning optimala strategier, / och kostnaden för spelet v.

Hur definieras det matrisantagonistiska spelet mellan två personer?

Vilka är metoderna för att förenkla och lösa matrisantagonistiska spel

När det gäller ett spel med två personer är det naturligt att betrakta deras intressen som rakt motsatta - spelet är antagonistiskt. Således är utdelningen för en spelare lika med förlusten för den andra (summan av båda spelarnas vinster är noll, därav namnet, nollsummespelet). Vi kommer att överväga spel där varje spelare har ett begränsat antal alternativ. Utdelningsfunktionen för ett sådant nollsummespel för två personer kan ges i matrisform (i form av en utdelningsmatris).

Som redan nämnts kallas det sista antagonistiska spelet matris.

MATRIX-SPEL - en klass av antagonistiska spel där två spelare deltar, och varje spelare har ett begränsat antal strategier. Om en spelare har m strategier och den andra spelaren har n strategier, då kan vi konstruera en spelmatris med dimensionen txn. Mi. kan ha en sadelpunkt eller inte. I det senare fallet

Tänk på ett ändligt nollsummeparspel. Beteckna med a spelarens utdelning A, och genom b- spelare vinner B. Därför att a = –b, då när man analyserar ett sådant spel finns det inget behov av att överväga båda dessa siffror - det räcker med att överväga utdelningen för en av spelarna. Låt det vara t.ex. A. I det följande, för att underlätta presentationen, sidan A vi kommer villkorligt att namnge " vi"och sidan B – "fiende".

Låt oss ha det m möjliga strategier A 1 , A 2 , …, A m, och fienden n möjliga strategier B 1 , B 2 , …, B n(ett sådant spel kallas ett spel m×n). Antag att varje sida har valt en viss strategi: vi har valt Ai, motståndare Bj. Om spelet endast består av personliga drag, då valet av strategier Ai och Bj bestämmer unikt resultatet av spelet - vår utdelning (positiv eller negativ). Låt oss beteckna denna vinst som aij(vinner när vi väljer strategin Ai, och fienden - strategier Bj).

Om spelet innehåller, förutom personliga slumpmässiga drag, så är utdelningen för ett par strategier Ai, Bjär en slumpvariabel som beror på resultatet av alla slumpmässiga drag. I det här fallet är den naturliga uppskattningen av den förväntade utdelningen matematiska förväntningar på en slumpmässig vinst. För enkelhetens skull kommer vi att beteckna med aij både utdelningen i sig (i ett spel utan slumpmässiga drag) och dess matematiska förväntan (i ett spel med slumpmässiga drag).

Anta att vi känner till värdena aij för varje par av strategier. Dessa värden kan skrivas som en matris vars rader motsvarar våra strategier ( Ai), och kolumnerna visar motståndarens strategier ( Bj):

En sådan matris kallas spelets utdelningsmatris eller bara spelmatris.

Observera att konstruktionen av en utdelningsmatris för spel med ett stort antal strategier kan vara en svår uppgift. Till exempel, för ett schackspel är antalet möjliga strategier så stort att konstruktionen av en utdelningsmatris är praktiskt taget omöjlig. Men i princip kan vilket ändligt spel som helst reduceras till en matrisform.

Överväga exempel 1 4×5 antagonistiskt spel. Vi har fyra strategier till vårt förfogande, fienden har fem strategier. Spelmatrisen är som följer:

Vilken strategi ska vi (dvs spelaren A) att använda? Oavsett vilken strategi vi väljer, kommer en rimlig motståndare att svara på den med den strategi för vilken vår utdelning blir minimal. Till exempel om vi väljer strategin A 3 (frestad av en vinst på 10), kommer motståndaren att välja en strategi som svar B 1 , och vår utdelning blir bara 1. Självklart måste vi, baserat på försiktighetsprincipen (och det är spelteorins huvudprincip), välja den strategi där vår minsta vinst är maximal.

Beteckna med ett i lägsta utdelningsvärde för strategin Ai:

och lägg till en kolumn som innehåller dessa värden till spelmatrisen:

När vi väljer en strategi måste vi välja den som värdet för ett i maximal. Låt oss beteckna detta maximala värde med α :

Värde α kallad lägre spelpris eller maximin(högsta minsta vinst). Spelarens strategi A motsvarande maximin α , kallas maximin strategi.

I det här exemplet är maximin α är lika med 3 (motsvarande cell i tabellen är markerad i grått), och maximin-strategin är A fyra. Efter att ha valt denna strategi kan vi vara säkra på att vi för varje beteende hos fienden kommer att vinna inte mindre än 3 (och kanske fler med fiendens "orimliga" beteende). Detta värde är vårt garanterade minimum, vilket vi kan säkerställa för oss själva och följer den mest försiktiga ("återförsäkrings") strategin.

Nu kommer vi att genomföra liknande resonemang för fienden B B A B 2 - vi kommer att svara honom A .

Beteckna med p j A B) för strategin Ai:

p j β :

7. VAD ÄR DET ÖVRE VÄRDESPELET Nu ska vi föra liknande resonemang för motståndaren B. Han är intresserad av att minimera vår vinst, det vill säga ge oss mindre, men han måste räkna med vårt beteende, vilket är det värsta för honom. Till exempel om han väljer strategin B 1 , då ska vi svara honom med en strategi A 3 , och han kommer att ge oss 10. Om han vill B 2 - vi kommer att svara honom A 2 , och han kommer att ge 8 osv. Uppenbarligen måste en försiktig motståndare välja den strategi där vår maximala vinst kommer att vara minimal.

Beteckna med p j de maximala värdena i kolumnerna i utdelningsmatrisen (spelarens maximala utdelning A, eller, vilket är detsamma, spelarens maximala förlust B) för strategin Ai:

och lägg till en rad som innehåller dessa värden till spelmatrisen:

Genom att välja en strategi, kommer fienden att föredra den som värdet för p j minimum. Låt oss beteckna det med β :

Värde β kallad högsta spelpriset eller minimax(minsta maxvinst). Motståndarens (spelarens) strategi som motsvarar minimax B), kallas minimax strategi.

Minimax är värdet av vinsten, mer än vad en rimlig motståndare säkerligen inte kommer att ge oss (med andra ord, en rimlig motståndare kommer inte att förlora mer än β ). I detta exempel, minimax β är lika med 5 (motsvarande cell i tabellen är markerad i grått) och det uppnås med motståndarens strategi B 3 .

Så, baserat på principen om försiktighet ("förvänta dig alltid det värsta!"), måste vi välja en strategi A 4, och fienden - en strategi B 3 . Försiktighetsprincipen är grundläggande i spelteorin och kallas minimax-principen.

Överväga exempel 2. Låt spelarna A och PÅ ett av tre siffror skrivs samtidigt och oberoende av varandra: antingen "1", eller "2" eller "3". Om summan av de skrivna talen är jämn, då spelaren B betalar spelaren A detta antal. Om beloppet är udda, betalar spelaren detta belopp A spelare PÅ.

Låt oss skriva ner utdelningsmatrisen för spelet och hitta de lägre och övre priserna för spelet (strateginumret motsvarar det skrivna numret):

Spelare A måste följa maximin-strategin A 1 för att vinna minst -3 (det vill säga att förlora högst 3). Minimax spelarstrategi B någon av strategierna B 1 och B 2 , vilket garanterar att han inte ger mer än 4.

Vi kommer att få samma resultat om vi skriver utdelningsmatrisen ur spelarens synvinkel PÅ. Faktum är att denna matris erhålls genom att transponera matrisen konstruerad från spelarens synvinkel A, och ändra tecknen på elementen till det motsatta (sedan spelarens utdelning Aär förlusten av spelaren PÅ):

Baserat på denna matris följer det att spelaren B måste följa någon av strategierna B 1 och B 2 (och då kommer han inte att förlora mer än 4), och spelaren A– strategier A 1 (och då förlorar han inte mer än 3). Som du kan se är resultatet exakt detsamma som det som erhölls ovan, så analysen spelar ingen roll från vilken spelare vi genomför den.

8 VAD ÄR ETT VÄRDEFÖRT SPEL.

9. VAD BESTÅR MINIMAX-PRINCIPEN AV. 2. Lägre och övre pris på spelet. Minimax-principen

Överväg ett matrisspel av typen med payoff-matris

Om spelaren MEN kommer att välja en strategi A i, då kommer alla dess möjliga vinster att vara element i-th raden i matrisen FRÅN. Värst för en spelare MEN fall när spelaren PÅ tillämpar en lämplig strategi minimum del av denna linje, spelarens utdelning MEN kommer att vara lika med antalet.

Därför, för att få maximal utdelning, spelaren MEN du måste välja en av strategierna som numret maximal.

Det enklaste fallet, utarbetat i detalj i spelteorin, är ett ändligt par med nollsumma (ett antagonistiskt spel med två personer eller två koalitioner). Betrakta ett spel G där två spelare A och B deltar, med motsatta intressen: vinsten för den ena är lika med den andras förlust. Eftersom utdelningen för spelare A är lika med utdelningen för spelare B med motsatt tecken, kan vi bara vara intresserade av utdelningen för spelare a. Naturligtvis vill A maximera och B vill minimera a.

För enkelhetens skull, låt oss identifiera oss mentalt med en av spelarna (låt det vara A) och kalla honom "vi", och spelare B - "motståndare" (naturligtvis, inga verkliga fördelar för A följer av detta). Låt oss ha möjliga strategier och motståndaren - möjliga strategier (ett sådant spel kallas ett spel). Låt oss beteckna vår utdelning om vi använder strategin och motståndaren använder strategin

Tabell 26.1

Antag att för varje par av strategier är utdelningen (eller den genomsnittliga utdelningen) a känd för oss. Då är det i princip möjligt att sammanställa en rektangulär tabell (matris), som listar spelarnas strategier och motsvarande utdelningar (se tabell 26.1).

Om en sådan tabell sammanställs, sägs spelet G vara reducerat till en matrisform (att föra spelet till en sådan form kan i sig redan vara en svår uppgift, och ibland praktiskt taget omöjlig, på grund av det stora antalet strategier ). Observera att om spelet reduceras till en matrisform, så reduceras spelet med flera drag faktiskt till ett spel med ett drag - spelaren måste bara göra ett drag: välj en strategi. Vi kommer kort att beteckna spelmatrisen

Betrakta ett exempel på ett spel G (4X5) i matrisform. Till vårt förfogande (att välja mellan) fyra strategier, har fienden fem strategier. Spelmatrisen ges i tabell 26.2

Låt oss fundera på vilken strategi vi (spelare A) använder? Matrix 26.2 har den lockande utdelningen "10"; vi lockas att välja en strategi där vi kommer att få denna "godbit".

Men vänta, fienden är inte dum heller! Om vi ​​väljer strategin, kommer han, trots oss, att välja strategin, och vi kommer att få en eländig utdelning "1". Nej, du kan inte välja en strategi! Hur man är? Uppenbarligen, med utgångspunkt från försiktighetsprincipen (och det är spelteorins huvudprincip), måste vi välja den strategi för vilken vår minsta vinst är maximal.

Tabell 26.2

Detta är den så kallade "mini-max-principen": agera på ett sådant sätt att du, med din motståndares sämsta beteende, får maximal vinst.

Låt oss skriva om tabellen 26.2 och i den högra extra kolumnen kommer vi att skriva ner minimivärdet för en förstärkning i varje rad (minst en linje); låt oss beteckna det för rad a (se tabell 26.3).

Tabell 26.3

Av alla värden (höger kolumn) väljs den största (3). Det matchar strategin. Efter att ha valt denna strategi kan vi i vilket fall som helst vara säkra på att (för alla fiendens beteende) vi kommer att få inte mindre än 3. Detta värde är vår garanterade vinst; uppträder försiktigt, vi kan inte få mindre än så här, vi kan få mer).

Denna utdelning kallas det lägre priset för spelet (eller "maximin" - det maximala av minimiutbetalningarna). Vi kommer att beteckna det som en. I vårat fall

Låt oss nu ta fiendens synvinkel och argumentera för honom. Han är inte någon slags bonde, men också rimlig! Att välja en strategi, han skulle vilja ge mindre, men han måste räkna med vårt beteende, vilket är det värsta för honom. Om han väljer en strategi kommer vi att svara honom och han ger 10; om han väljer kommer vi att svara honom och han kommer att ge tillbaka det etc. Vi lägger till ytterligare en nedre rad i tabell 26.3 och skriver maximivärdena för kolumnerna i. Uppenbarligen måste en försiktig motståndare välja den strategi för vilken detta värde är minimal (motsvarande värde 5 är markerat i tabell 26.3) . Detta värde P är värdet av vinsten, mer än vad en rimlig motståndare säkerligen inte kommer att ge oss. Det kallas det övre priset på spelet (eller "mi-nimax" - minimum av de maximala vinsterna). I vårt exempel, och uppnås med motståndarens strategi

Så, baserat på försiktighetsprincipen (återförsäkringsregeln "räkna alltid med det sämsta!"), måste vi välja strategi A och fienden - strategi. Sådana strategier kallas "minimax" (efter minimaxprincipen). Så länge som båda parter i vårt exempel håller fast vid sina minimaxstrategier kommer utdelningen att bli

Föreställ dig nu för ett ögonblick att vi har lärt oss att fienden följer strategin. Kom igen, vi straffar honom för detta och väljer en strategi, vi får 5, och det här är inte så illa. Men trots allt är fienden inte heller en miss; låt honom veta att vår strategi är , han kommer också att skynda sig att välja , minska vår utdelning till 2, etc. (partners "rusade runt strategierna"). Kort sagt, minimaxstrategierna i vårt exempel är instabila med avseende på information om den andra sidans beteende; dessa strategier har inte jämviktsegenskapen.

Är det alltid så här? Nej inte alltid. Betrakta ett exempel med matrisen i Tabell 26.4.

I det här exemplet är det lägre priset på spelet lika med det övre: . Vad följer av detta? Minimaxstrategierna för spelare A och B kommer att vara stabila. Så länge som båda spelarna håller sig till dem är utdelningen 6. Låt oss se vad som händer om vi (A) får reda på att motståndaren (B) håller fast vid strategi B?

Tabell 26.4

Och exakt ingenting kommer att förändras, eftersom varje avvikelse från strategin bara kan förvärra vår situation. På samma sätt kommer informationen som mottas av motståndaren inte att få honom att dra sig tillbaka från sin strategi. Ett tecken på närvaron av en sadelpunkt och ett balanserat par av strategier är likheten mellan de lägre och övre priserna i spelet; det totala värdet kallas spelets pris. Vi kommer att märka det

Strategier (i det här fallet ) där denna vinst uppnås kallas optimala rena strategier, och deras kombination är en lösning på spelet. I det här fallet sägs själva spelet vara löst i rena strategier. Båda parterna A och B kan ges sina optimala strategier där deras position är den bästa möjliga. Och att spelare A vinner 6 och spelare B förlorar, ja, det här är villkoren för spelet: de är fördelaktiga för A och ofördelaktiga för B.

Läsaren kan ha en fråga: varför kallas optimala strategier "rena"? Om vi ​​tittar lite framåt, låt oss svara på den här frågan: det finns "blandade" strategier, som består i att spelaren inte använder en strategi, utan flera, och växlar dem slumpmässigt. Så, om vi erkänner, förutom rena, även blandade strategier, så har vilket ändligt spel som helst en lösning - en jämviktspunkt. Men mer om detta kommer ännu.

Förekomsten av en sadelpunkt i spelet är långt ifrån regeln, det är snarare undantaget. De flesta spel har ingen sadelpunkt. Det finns dock en mängd olika spel som alltid har en sadelpunkt och därför löses i rena strategier. Det är de så kallade "spelen med fullständig information". Ett spel med fullständig information är ett spel där varje spelare känner till hela förhistorien av sin utveckling vid varje personligt drag, det vill säga resultatet av alla tidigare drag, både personliga och slumpmässiga. Exempel på spel med fullständig information är schack, schack, tic-tac-toe, etc.

I spelteorin är det bevisat att varje spel med fullständig information har en sadelpunkt, och därför kan lösas i rena strategier. I varje spel med perfekt information finns det ett par optimala strategier som ger en stabil utdelning lika med priset på spelet och. Om ett sådant spel endast består av personliga drag, då när varje spelare tillämpar sin egen optimala strategi, måste det sluta på ett ganska bestämt sätt - med en utdelning som motsvarar spelets pris. Så om spelets lösning är känd, förlorar själva spelet sin mening!

Låt oss ta ett elementärt exempel på ett spel med fullständig information: två spelare placerar växelvis nickel på ett runt bord och väljer godtyckligt positionen för myntets mitt (ömsesidig överlappning av mynt är inte tillåten). Vinnaren är den som lägger sista kronan (när det inte finns plats för andra). Det är lätt att se att resultatet av detta spel i grunden är en självklarhet. Det finns en viss strategi som säkerställer att spelaren som sätter myntet först vinner.

Han måste nämligen sätta en nickel i mitten av bordet för första gången, och sedan svara på varje drag av motståndaren med ett symmetriskt drag. Uppenbarligen, oavsett hur motståndaren beter sig kan han inte undvika att förlora. Situationen är exakt densamma med schack och spel med fullständig information i allmänhet: vilken som helst av dem, skriven i matrisform, har en sadelpunkt, och därför ligger lösningen i rena strategier, och därför är det bara vettigt så länge som denna lösning gör det. hittades inte. Låt oss säga schackspel antingen slutar det alltid med vinst för vit, eller så slutar det alltid med vinst för svart, eller så slutar det alltid oavgjort, men exakt vad - vi vet inte än (lyckligtvis för schackälskare). Låt oss lägga till en sak till: vi kommer knappast att veta inom överskådlig framtid, eftersom antalet strategier är så enormt att det är extremt svårt (om inte omöjligt) att reducera spelet till en matrisform och hitta en sadelpunkt i den.

Och låt oss nu fråga oss själva vad vi ska göra om spelet inte har en sadelpunkt: Tja, om varje spelare tvingas välja en enda ren strategi, så finns det inget att göra: vi måste vägledas av minimaxprincipen. En annan sak är om du kan "mixa" dina strategier, alternera dem slumpmässigt med vissa sannolikheter. Användningen av blandade strategier är tänkt på detta sätt: spelet upprepas många gånger; före varje spel i spelet, när spelaren får ett personligt drag, "överlåter" han sitt val åt slumpen, "kastar lotter" och tar strategin som föll ut (vi vet redan hur man organiserar lotten från föregående kapitel ).

Blandade strategier i spelteorin är en modell av föränderlig, flexibel taktik, när ingen av spelarna vet hur motståndaren kommer att bete sig i ett givet spel. Denna taktik (om än vanligtvis utan någon matematisk motivering) används ofta i kortspel. Låt oss samtidigt notera att det bästa sättet att dölja ditt beteende från fienden är att ge den en slumpmässig karaktär och därför inte veta i förväg vad du kommer att göra.

Så låt oss prata om blandade strategier. Vi kommer att beteckna de blandade strategierna för spelare A respektive B

I ett särskilt fall, när alla sannolikheter, utom en, är lika med noll, och denna är lika med en, förvandlas den blandade strategin till en ren.

Det finns ett grundläggande teorem inom spelteorin: alla ändliga nollsummespel för två spelare har minst en lösning - ett par optimala strategier, vanligtvis blandade, och ett motsvarande pris

Ett par optimala strategier som bildar en spellösning har följande egenskap: om en av spelarna följer sin optimala strategi, kan det inte vara lönsamt för den andra att avvika från sin. Det här paret av strategier bildar ett slags jämvikt i spelet: en spelare vill vända utdelningen till maximalt, den andra - till ett minimum, var och en drar åt sin egen riktning, och med rimligt beteende av båda, en jämvikt och en stabil utdelning v etableras. Om då spelet är fördelaktigt för oss, om - för fienden; när spelet är "rättvist", lika fördelaktigt för båda deltagarna.

Betrakta ett exempel på ett spel utan sadelpunkt och ge (utan bevis) dess lösning. Spelet är som följer: två spelare A och B samtidigt och utan att säga ett ord visar ett, två eller tre fingrar. Vinsten avgörs av det totala antalet fingrar: om det är jämnt vinner A och får från B ett belopp som är lika med detta antal; om det är udda, så betalar A tvärtom B ett belopp som är lika med detta antal. Vad ska spelarna göra?

Låt oss skapa en spelmatris. I ett spel har varje spelare tre strategier: visa ett, två eller tre fingrar. 3x3-matrisen ges i Tabell 26.5; den extra högra kolumnen visar radminima och den extra nedre raden visar kolumnmaxima.

Det lägre priset på spelet stämmer överens med strategin. Det betyder att med ett rimligt, försiktigt beteende garanterar vi att vi inte kommer att förlora mer än 3. Liten tröst, men ändå bättre än säg att vinna - 5, som finns i vissa celler i matrisen. Det är dåligt för oss, spelare L... Men låt oss trösta oss: motståndarens position verkar vara ännu värre: spelets lägre pris till. rimligt beteende ger han oss minst 4.