• POP
• Windows
• Antivirus
• Antivirus
• Grafisk konst

antagonistiskt spel. Lösa matrisantagonistiska spel Principer för att lösa matrisantagonistiska spel

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änsad. 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

Moscow Power Engineering Institute

(Tekniskt universitet)

Labb rapport

i spelteori

"Ett sökprogram för optimala strategier för ett parat antagonistiskt spel givet i matrisform"

Kompletteras av studenter

grupp A5-01

Ashrapov Daler

Ashrapova Olga

Grundläggande begrepp inom spelteori

Spelteori designad för att lösa konfliktsituationer , dvs. situationer där två eller flera parters intressen som strävar efter olika mål kolliderar.

Om partiernas mål är rakt motsatta, då talar de om antagonistisk konflikt .

spel kallas en förenklad formaliserad modell av en konfliktsituation.

Att spela ett spel en gång från början till slut kallas fest . Resultatet av festen är betalning (eller vinna ).

Partiet består av rör sig , dvs. att välja spelare från en uppsättning möjliga alternativ.

Rörelser kan vara personlig och slumpmässig.personligt drag , Till skillnad från slumpmässig , innebär ett medvetet val av spelaren av något alternativ.

Spel där det finns minst ett personligt drag kallas strategisk .

Spel där alla drag är slumpmässiga kallas spelande .

När man gör ett personligt drag talar man också om strategier spelare, dvs. om regeln eller uppsättningen regler som avgör spelarens val. Samtidigt bör strategin vara heltäckande, d.v.s. valet måste bestämmas för varje möjlig situation under spelets gång.

Spelteoretisk utmaning– hitta spelarnas optimala strategier, dvs. strategier som ger dem maximal vinst eller minsta förlust.

Klassificering av spelteoretiska modeller

spel n personer brukar kallas, var
är uppsättningen av strategier för den i:e spelaren,
- spelbetalning.

I enlighet med denna beteckning kan följande klassificering av spelteoretiska modeller föreslås:

Diskret (uppsättningar av strategier diskret)

Slutlig

Ändlös

Kontinuerlig (uppsättningar av strategier kontinuerlig)

Ändlös

n personer (
)

Koalition (kooperativ)

Icke-samarbetsvillig (icke-samarbetsvillig)

2 personer (parade)

Antagonistiska (nollsummespel)

(parternas intressen är motsatta, dvs. en spelares förlust är lika med den andras vinst)

Icke-antagonistisk

Med fullständig information (om spelaren som gör ett personligt drag känner till hela spelets historia, d.v.s. motståndarens alla drag)

Med ofullständig information

Med noll belopp (total betalning är noll)

Med en summa som inte är noll

Enkelriktad (lotterier)

flervägs

Matrisrepresentation av ett parat antagonistiskt spel

I den här handledningen kommer vi att överväga antagonistiska spel av två personer ges i matrisform. Detta betyder att vi känner till uppsättningen av strategier för den första spelaren (spelare A){ A i }, i = 1,…, m och uppsättningen av strategier för den andra spelaren (spelare B){ B j }, j = 1,..., n och matrisen A = || a I j || den första spelarens utdelning. Eftersom vi talar om ett antagonistiskt spel, antas det att vinsten för den första spelaren är lika med förlusten för den andra. Vi anser att matriselementet a I jär utdelningen för den första spelaren när han väljer en strategi A i och svaret från den andra spelaren med strategin B j. Vi kommer att hänvisa till ett sådant spel som
, var m - antal spelarstrategier MEN,n - antal spelarstrategier PÅ. I allmänhet kan det representeras av följande tabell:

Exempel 1

Som ett enkelt exempel, betrakta ett spel där spelet består av två drag.

1:a draget: Spelare MEN väljer ett av siffrorna (1 eller 2) utan att berätta för motståndaren om sitt val.

2:a draget: Spelare PÅ väljer ett av siffrorna (3 eller 4).

Resultat: Spelarval MEN och PÅ Lägg till. Om summan är jämn, då PÅ betalar sitt värde till spelaren MEN, om udda - vice versa, MEN betalar spelaren PÅ.

Detta spel kan representeras som
på följande sätt:

Det är lätt att se det detta spelär antagonistisk, dessutom är det ett spel med ofullständig information, eftersom spelare PÅ, gör ett personligt drag är det inte känt vilket val spelaren gjorde MEN.

Som noterats ovan är spelteorins uppgift att hitta spelarnas optimala strategier, d.v.s. strategier som ger dem maximal vinst eller minsta förlust. Denna process kallas spelets beslut .

När man löser ett spel i matrisform bör man kontrollera spelets närvaro sadelpunkt . För detta introduceras två värden:

är den nedre gränsen för spelets pris, och

är den övre uppskattningen av priset på spelet.

Den första spelaren kommer med största sannolikhet att välja strategin där han kommer att få maximal vinst bland alla möjliga svar från den andra spelaren, och den andra kommer tvärtom att välja den som minimerar hans egen förlust, dvs. möjlig vinst av den första.

Det kan bevisas α ≤ V ≤ β , var V–spelpris , d.v.s. den troliga utdelningen för den första spelaren.

Om förhållandet α = β = V, då säger de det spelet har en sadelpunkt
, och lösas i rena strategier . Det finns med andra ord ett par strategier
, ger spelaren MENV.

Exempel 2

Låt oss återgå till spelet som vi betraktade i exempel 1 och kontrollera att det finns en sadelpunkt.

För det här spelet
= -5,
= 4,
, därför har den ingen sadelpunkt.

Återigen, observera att det här spelet är ett ofullständigt informationsspel. I det här fallet kan du bara ge spelaren råd MEN välja en strategi , därför att i detta fall kan han få den största utdelningen, dock förutsatt att spelaren väljer PÅ strategier .

Exempel 3

Låt oss göra några ändringar i spelets regler från exempel 1. Låt oss ge spelaren PÅ information om spelarval MEN. Sedan PÅ Det finns ytterligare två strategier:

- en strategi som är fördelaktig för MEN. Om val A - 1, sedan PÅ väljer 3 om val A - 2, sedan PÅ väljer 4;

- en strategi som inte är fördelaktig för MEN. Om val A - 1, sedan PÅ väljer 4 om val A - 2, sedan PÅ väljer 3.

Det här spelet är fullt av information.

I detta fall
= -5,
= -5,
, därför har spelet en sadelpunkt
. Denna sadelpunkt motsvarar två par optimala strategier:
och
. Spelpris V= -5. Det är uppenbart att för MEN det här spelet är värdelöst.

Exempel 2 och 3 är en bra illustration av följande teorem, bevisat i spelteorin:

Sats 1

Varje parat antagonistiskt spel med perfekt information löses i rena strategier.

Den där. Sats 1 säger att alla två-personers spel med perfekt information har en sadelpunkt och det finns ett par rena strategier
, ger spelaren MEN hållbar vinst lika med priset på spelet V.

Vid avsaknad av sadelpunkt, den sk blandade strategier :, var sid i ochq jär sannolikheterna för att välja strategier A i och B j den första respektive andra spelaren. Lösningen i spelet i det här fallet är ett par blandade strategier
maximera de matematiska förväntningarna på spelets pris.

En generalisering av sats 1 till fallet med ett spel med ofullständig information är följande sats:

Sats 2

Alla parade antagonistiska spel har åtminstone en optimal lösning, dvs ett par blandade strategier i det allmänna fallet
, ger spelaren MEN hållbar vinst lika med priset på spelet V, dessutom α ≤ V ≤ β .

I ett speciellt fall, för ett spel med en sadelpunkt, ser lösningen i blandade strategier ut som ett par vektorer där ett element är lika med ett och resten är lika med noll.

Det enklaste fallet, utarbetat i detalj i spelteorin, är ett ändligt par med nollsumma (ett antagonistiskt spel med två personer eller två koalitioner). Tänk på det här spelet G, där två spelare MEN och PÅ, ha motsatta intressen: vinsten för den ena är lika med den andras förlust. Sedan spelarens utdelning MENär lika med spelarens utdelning In med motsatt tecken, vi kan bara vara intresserade av utdelningen a spelare MEN. Naturligtvis, MEN vill maximera och AT - minimera a. För enkelhetens skull, låt oss identifiera oss mentalt med en av spelarna (låt det vara MEN) och vi kommer att kalla honom "vi", och spelaren AT -"motståndare" (naturligtvis inga verkliga fördelar för MEN följer inte av detta). Låt oss ha det t möjliga strategier MEN 1 , A 2 , ..., MEN m, och fienden n möjliga strategier PÅ 1 , AT 2 , ..; PÅ n(ett sådant spel kallas ett spel t × n). Beteckna a I j vår utdelning om vi använder strategin A i , och fienden är en strategi B j .

Tabell 26.1

Antag att för varje par av strategier A<, PÅ, vinst (eller genomsnittlig vinst) a, j vi vet. 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, då säger vi att spelet G reducerad till en matrisform (i sig själv kan det redan vara en svår uppgift att föra spelet till en sådan form, och ibland nästan omöjligt, 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 ( a I j).

Tänk på ett exempelspel G(4×5) 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 (spelaren MEN) utnyttja? Matrix 26.2 har den lockande utdelningen "10"; vi lockas att välja en strategi MEN 3 , där vi kommer att få denna "godis". Men vänta, fienden är inte dum heller! Om vi ​​väljer en strategi MEN 3 , han, trots oss, kommer att välja en strategi PÅ 3 , och vi får en eländig utdelning "1". Nej, välj en strategi MEN 3 det är förbjudet! Hur man är? Uppenbarligen, baserat på försiktighetsprincipen (och det är spelteorins huvudprincip), måste vi välja

Tabell 26.2

strategin som vår minsta vinst är maximal. Detta är den så kallade "minimaxprincipen": agera på ett sådant sätt att du, med fiendens sämsta beteende för dig, får maximal vinst.

Vi skriver om tabell 26.2 och i den högra extra kolumnen skriver vi ner det lägsta värdet av vinsten på varje rad, (linjeminimum); låt oss utse det för i-te raden α i(se tabell 26.3).

Tabell 26.3

Av alla värden α i(höger kolumn) den största (3) är markerad. Det matchar strategin A fyra. Efter att ha valt den här strategin kan vi i alla fall vara säkra på att (för alla fiendens beteende) vi kommer att vinna inte mindre än 3. Detta värde är vår garanterade vinst; var försiktig, vi kan inte få mindre än så här (jag kan få mer). Denna utdelning kallas det lägre priset för spelet (eller "maximin" - det maximala av minimiutbetalningarna). Vi kommer att beteckna det a. I vårat fall α = 3.

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 PÅ 1 , vi kommer att svara honom MEN 3 , och han kommer att ge 10; om han väljer B 2 - vi ska svara honom MEN 2 , och han kommer att ge 8, etc. Vi lägger till ytterligare en lägre rad till tabell 26.3 och skriver i den maximivärdena för kolumnerna β j. Självklart bör en försiktig motståndare välja den strategi som minimerar detta värde (motsvarande värde på 5 är markerat i Tabell 26.3). Detta värde på β är värdet på vinsten, mer än vad en rimlig motståndare säkerligen inte kommer att ge oss. Det kallas det övre priset på spelet (eller "minimax" - minimum av de maximala vinsterna). I vårt exempel är β = 5 och uppnås med motståndarens strategi B 3 .

Så, baserat på försiktighetsprincipen (återförsäkringsregeln "räkna alltid med det värsta!"), måste vi välja en strategi MEN 4 , och fienden - strategi PÅ 3 . 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 a 43 = 3.

Föreställ dig nu för ett ögonblick att vi har lärt oss att fienden följer en strategi PÅ 3 . Kom igen, låt oss straffa honom för detta och välja en strategi MEN 1 - vi får 5, vilket inte är så illa. Men trots allt är fienden inte heller en miss; låt honom veta att vår strategi MEN 1 ; han är också snabb att välja PÅ 4 , minska vår utdelning till 2, etc. (partners "bråttom om strategier"). Med ett ord, minimaxstrategier i vårt exempel instabil i förhållande till till information om den andra partens 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: α = β = 6. Vad följer av detta? Minimax spelarstrategier MEN och PÅ kommer att vara hållbart. 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 (MEN) vet att fienden (PÅ)

Tabell 26.4

håller fast vid strategin B 2 ? Och exakt ingenting kommer att förändras. Eftersom varje avvikelse från strategin MEN 2 kan bara göra vår situation värre. På samma sätt kommer information som mottas av fienden inte att få honom att dra sig tillbaka från sin strategi. PÅ 2 . Ett par strategier MEN 2 , B 2 besitter egenskapen jämvikt (ett balanserat par av strategier), och utdelningen (i vårt fall 6) som uppnås med detta par av strategier kallas "matrisens sadelpunkt" 1). 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 gemensamma värdet av α och β kallas spelets pris. Vi kommer att märka det v:

α = β = v

Strategier A i , B j(I detta fall MEN 2 , AT 2 ), för vilka denna utdelning uppnås kallas optimala rena strategier, och deras helhet kallas en lösning på spelet. I det här fallet sägs själva spelet vara löst i rena strategier. Båda sidor MEN och PÅ man kan ange deras optimala strategier där deras position är den bästa möjliga. Vad är en spelare MEN i detta fall 6 vinster och spelaren AT - förlorar 6, - ja, Dessa är spelets villkor: de är fördelaktiga för MEN och ofördelaktigt för PÅ

1) Termen "sadelpunkt" är hämtad från geometri - detta är namnet på punkten på ytan, där minimum längs en koordinat och maximum längs den andra uppnås samtidigt.

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 tillåter, förutom rena sådana, även blandade strategier, ev slutspel har en lösning - en jämviktspunkt. Men vi pratar fortfarande om atomen.

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 en hylla med information är ett spel där varje spelare känner till hela historien om dess utveckling, det vill säga resultatet av alla tidigare drag, både personliga och slumpmässiga, vid varje personligt drag. 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 kan därför lösas i rena strategier. I varje spel med perfekt information finns det ett par optimala strategier som ger en stabil utdelning som motsvarar spelets kedja v. 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 först placera en nickel i mitten av bordet, 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: någon 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 detta lösningen hittades inte. Låt oss säga att ett schackspel är antingen det alltid slutar med att vit vinner, eller alltid - svart vinner, eller alltid - oavgjort, bara med vad exakt - vi vet inte ännu (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.

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 - den enda rena strategin, så finns det inget att göra: man måste vägledas av minimaxprincipen. En annan sak är om det är möjligt att "mixa" en uppsättning strategier, alternera 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, "anförtror" 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 spelarnas blandade strategier MEN och PÅ respektive S A = ( sid 1 , R 2 , ..., sid m), S B = (q 1 , q 2 , …, q n), var sid 1 , sid 2 , …, sid m(bildar totalt en) - sannolikheterna för spelaren som använder MEN strategier MEN 1 , A 2 ,… , A m ; q 1 , q 2 , …, q n- sannolikheter för användning av spelaren PÅ strategier PÅ 1 , PÅ 2 , ..., PÅ n . 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 för spelteori: alla tvåpersoners nollsummespel har minst en lösning - ett par optimala strategier, vanligtvis blandade
och motsvarande pris v.

Ett par optimala strategier
att bilda lösningen av spelet har följande egenskap: om en av spelarna följer sin optimala strategi så kan det inte vara lönsamt för den andra att avvika från sin egen. Detta par strategier bildar ett slags jämvikt i spelet: en spelare vill vända vinsten till ett maximum, den andra till ett minimum, var och en drar åt sin egen riktning och, med rimligt beteende hos båda, en jämvikt och en stabil vinst etableras. v. Om en v > 0, då är spelet lönsamt för oss om v< 0 - för fienden; på v= 0 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 MEN och PÅ samtidigt och utan att säga ett ord visa ett, två eller tre fingrar. Vinst avgörs av det totala antalet fingrar: om det är jämnt, vinner MEN och tar emot från PÅ ett belopp lika med detta antal; om det är udda, så tvärtom MEN betalar PÅ ett belopp som är lika med det antalet. 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. 3×3-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 α = - 3 och motsvarar strategin A 1 . Det betyder att vi med rimligt, försiktigt beteende garanterar att vi inte kommer att förlora mer än 3. Liten tröst, men ändå bättre än, säg, en vinst på 5, som inträffar i vissa celler i matrisen. Dåligt för oss, spelaren MEN... Men låt oss trösta oss:

motståndarens position verkar vara ännu sämre: den lägre kostnaden för spelet är β = 4, d.v.s. med rimligt beteende kommer han att ge oss minst 4. I allmänhet är positionen inte särskilt bra - varken för en eller för andra sidan. Men låt oss se om det kan förbättras? Det visar sig att du kan. Om varje sida inte använder en ren strategi, utan en blandad, där

Tabell 26.5

den första och tredje går in med sannolikhet 1/4, och den andra - med sannolikhet 1/2, dvs.

då kommer den genomsnittliga utdelningen att vara konstant lika med noll (vilket betyder att spelet är "rättvist" och lika fördelaktigt för båda sidor). Strategier
bilda en lösning på spelet och dess pris v= 0. Hur hittade vi denna lösning? Det här är en annan fråga. I nästa avsnitt visar vi hur finita spel generellt löses.

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 B j. Om spelet endast består av personliga drag, då valet av strategier Ai och B j 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 B j).

Om spelet innehåller, förutom personliga slumpmässiga drag, så är utdelningen för ett par strategier Ai, B jä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 ( B j):

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 schackspel antalet möjliga strategier är så stort att konstruktionen av payoff-matrisen ä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 βj A B) för strategin Ai:

β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 β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 β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.

Beslutsproblemet, betraktat inom ramen för systemansatsen, innehåller tre huvudkomponenter: systemet, styrdelsystemet och miljön identifieras i det. Nu övergår vi till studiet av beslutsfattande problem, där systemet påverkas av inte ett, utan flera kontrolldelsystem, som vart och ett har sina egna mål och handlingsmöjligheter. Detta förhållningssätt till beslutsfattande kallas spelteoretisk, och de matematiska modellerna för motsvarande interaktioner kallas spel. På grund av skillnaden i målen för styrdelsystemen, samt vissa begränsningar av möjligheten att utbyta information mellan dem, är dessa interaktioner av konfliktkaraktär. Därför är alla spel en matematisk modell av konflikter. Vi begränsar oss till fallet när det finns två styrsystem. Om systemens mål är motsatta kallas konflikten antagonistisk, och den matematiska modellen för en sådan konflikt kallas antagonistiskt spel..

I spelteoretisk terminologi kallas det 1:a kontrollundersystemet spelare 1, 2:a styrdelsystemet - spelare 2, set

deras alternativa handlingar kallas uppsättningar av strategier dessa spelare. Låta X- uppsättning spelare 1-strategier, Y- många strategier

spelare 2. Systemets tillstånd bestäms unikt av valet av kontrollåtgärder av delsystem 1 och 2, det vill säga valet av strategier

x∈X och y∈Y. Låta F(x,y) - nyttouppskattning för spelare 1 i den staten

systemet som det passerar till när spelare 1 väljer en strategi X och

spelare 2 strategi på. siffra F(x,y) kallas vinnande spelare 1 i situationen ( x,y), och funktionen F- spelare 1 payoff funktion. Spelaren vinner

1 är också förlusten av spelare 2, det vill säga värdet som den första spelaren försöker öka, och den andra - att minska. Det är vad det är

manifestation av konfliktens antagonistiska karaktär: spelarnas intressen är helt motsatta (vad den ena vinner, den andra förlorar).

Ett antagonistiskt spel sätts naturligtvis av systemet G=(X, Y, F).

Observera att formellt sett är det antagonistiska spelet faktiskt satt på samma sätt som problemet med att fatta ett beslut under förhållanden av osäkerhet - om

identifiera styrdelsystemet 2 med miljön. Den materiella skillnaden mellan kontrolldelsystemet och miljön är att

beteendet hos den första är målmedvetet. Om vi, när vi sammanställer en matematisk modell av en verklig konflikt, har en anledning (eller avsikt) att betrakta miljön som en motståndare, vars syfte är att

oss maximal skada, då kan en sådan situation representeras som ett antagonistiskt spel. Med andra ord kan det antagonistiska spelet tolkas som ett extremfall av ZPR under förhållanden av osäkerhet,

kännetecknas av att omgivningen ses som en motståndare med ett mål. Samtidigt måste vi begränsa typerna av hypoteser om miljöns beteende.

Den mest underbyggda här är hypotesen om extrem försiktighet, när vi, när vi fattar ett beslut, förlitar oss på det värsta möjliga scenariot för att vi ska agera i miljön.

Definition. Om en X och Yär ändliga, då kallas det antagonistiska spelet matris. I matrisspelet kan vi anta det X={1,…,n},

Y={1,…,m) och sätt aij=F(I j). Alltså bestäms matrisspelet helt av matrisen A=(aij), jag=1,…,n, j=1,…,m.

Exempel 3.1. Spel med två fingrar.

Två personer samtidigt visar ett eller två fingrar och ringer numret 1 eller 2, vilket enligt talaren betyder numret

fingrar visas för andra. Efter att fingrarna har visats och numren har namngivits fördelas vinsterna enligt följande regler:

om båda gissade eller båda inte gissade hur många fingrar deras motståndare visade, är utdelningen för var och en lika med noll; om bara en har gissat rätt, så betalar motståndaren gissaren summan pengar som är proportionell mot det totala antalet visade

Detta är ett antagonistiskt matrisspel. Varje spelare har fyra strategier: 1- visa 1 finger och säg 1, 2- visa 1 finger och säg 2, 3-

visa 2 fingrar och säg 1, 4 - visa 2 fingrar och säg 2. Sedan payoff matrisen A=(aij), i= 1,…, 4, j= 1,…, 4 definieras enligt följande:

a12= 2, a21 = – 2, a13=a42=–3, a24=a31= 3, a34 = – 4, a43= 4,aij= 0 annars.

Exempel 3.2. Diskret spel av duelltyp.

Duellliknande uppgifter beskriver till exempel två spelares kamp,

som var och en vill utföra någon engångsåtgärd (släppande av en sändning av varor på marknaden, en ansökan om köp på en auktion) och väljer en tidpunkt för detta. Låt spelarna gå mot varandra vidare n steg. Efter varje steg som tas kan spelaren skjuta på motståndaren eller inte. Varje person kan bara ha ett skott. Man tror att sannolikheten för att träffa fienden om du avancerar förbi k n =5 har formen