Antagonisztikus mátrixos játékok. Antagonisztikus játékok folyamatos stratégiákkal Az antagonisztikus páros játékban a játékosok céljai az

Nulla összegű játék, amelyben minden játékosnak véges stratégiák állnak rendelkezésére. A mátrix játék szabályait a fizetési mátrix határozza meg, melynek elemei az első játékos nyereményei, amelyek egyben a második játékos veszteségei is.

Mátrix játék egy antagonisztikus játék. Az első játékos a játék árával megegyező maximális (a második játékos viselkedésétől függetlenül) garantált nyereményt kapja, hasonlóképpen a második játékos a minimális garantált veszteséget.

Alatt stratégia alatt olyan szabályok (elvek) összességét értjük, amelyek meghatározzák a játékos minden egyes személyes lépésénél a cselekvés kiválasztását, az aktuális helyzettől függően.

Most mindenről rendben és részletesen.

Fizetési mátrix, tiszta stratégiák, játék ára

BAN BEN mátrix játék szabályai meghatározottak fizetési mátrix .

Vegyünk egy olyan játékot, amelyben két résztvevő van: az első és a második játékos. Az első játékos álljon rendelkezésére m tiszta stratégiák, és a második játékos rendelkezésére áll - n tiszta stratégiák. Mivel a játék mérlegelés alatt áll, természetes, hogy ebben a játékban vannak győzelmek és veszteségek.

BAN BEN fizetési mátrix az elemek a játékosok győzelmeit és vereségeit kifejező számok. A nyereményeket és a veszteségeket pontokban, pénzösszegben vagy más egységekben lehet kifejezni.

Készítsünk fizetési mátrixot:

Ha az első játékos úgy dönt én-a tiszta stratégia, és a második játékos - j tiszta stratégia, akkor az első játékos nyereménye lesz aij egység, és a második játékos elvesztése is aij egységek.

Mert aij + (- a ij) = 0, akkor a leírt játék egy nulla összegű mátrixjáték.

A mátrixjáték legegyszerűbb példája az érmefeldobás. A játék szabályai a következők. Az első és a második játékos egy érmét dob, és az eredmény fej vagy farok lesz. Ha „fejek” és „fejek” vagy „farok” vagy „farok” egyszerre dobnak, akkor az első játékos egy egységet nyer, más esetekben pedig egy egységet veszít (a második játékos egy egységet nyer) . Ugyanez a két stratégia áll a második játékos rendelkezésére. A megfelelő fizetési mátrix a következő lesz:

A játékelmélet feladata, hogy meghatározza az első játékos stratégiájának megválasztását, amely garantálja számára a maximális átlagos győzelmet, valamint a második játékos stratégiájának megválasztását, amely garantálja számára a maximális átlagos veszteséget.

Hogyan válassz stratégiát egy mátrixjátékban?

Nézzük újra a fizetési mátrixot:

Először is határozzuk meg az első játékos nyereményének összegét, ha használja én tiszta stratégia. Ha az első játékos használja én th tiszta stratégiát, akkor logikus azt feltételezni, hogy a második játékos olyan tiszta stratégiát fog alkalmazni, ami miatt az első játékos kifizetése minimális lenne. Az első játékos viszont olyan tiszta stratégiát fog alkalmazni, amely a maximális győzelmet biztosítja számára. Ezen feltételek alapján az első játékos nyereménye, amelyet mi jelölünk v1 , hívott nyeremény maximalizálása vagy a játék legalacsonyabb ára .

Nál nél ezeknél az értékeknél az első játékosnak a következőképpen kell eljárnia. Minden sorból írja le a minimális elem értékét, és válassza ki közülük a maximumot. Így az első játékos nyereménye a minimum maximuma lesz. Innen a név – maximin winning. Ennek az elemnek a sorszáma az első játékos által választott tiszta stratégia száma lesz.

Most határozzuk meg a veszteség összegét a második játékos számára, ha használja j stratégia. Ebben az esetben az első játékos a saját tiszta stratégiáját használja, amelyben a második játékos vesztesége maximális lenne. A második játékosnak olyan tiszta stratégiát kell választania, amelyben minimális a vesztesége. A második játékos elvesztése, amit mi jelölünk v2 , hívott minimális veszteség vagy a játék felső ára .

Nál nél a játék árával kapcsolatos problémák megoldása és a stratégia meghatározása A második játékos értékeinek meghatározásához a következőképpen járjon el. Minden oszlopból írja le a maximális elem értékét, és válassza ki belőlük a minimumot. Így a második játékos vesztesége a maximum minimuma lesz. Innen a név - minimax win. Ennek az elemnek az oszlopszáma a második játékos által választott tiszta stratégia száma lesz. Ha a második játékos a „minimax”-ot használja, akkor az első játékos által választott stratégiától függetlenül nem veszít többet, mint v2 egységek.

1. példa

.

A sorok legkisebb elemei közül a legnagyobb a 2, ez a játék alacsonyabb ára, ennek az első sor felel meg, ezért az első játékos maximin stratégiája az első. Az oszlopok legnagyobb elemei közül a legkisebb az 5, ez a játék felső ára, a második oszlop ennek felel meg, ezért a második játékos minimax stratégiája a második.

Most, hogy megtanultuk megtalálni a játék alsó és felső árát, a maximin és minimax stratégiákat, itt az ideje megtanulni, hogyan kell formálisan meghatározni ezeket a fogalmakat.

Tehát az első játékos garantált győzelme:

Az első játékosnak olyan tiszta stratégiát kell választania, amely a minimális nyeremény maximumát biztosítja számára. Ezt az erősítést (maximum) a következőképpen jelöljük:

.

Az első játékos tiszta stratégiáját használja úgy, hogy a második játékos vesztesége maximális legyen. Ezt a veszteséget a következőképpen jelezzük:

A második játékosnak úgy kell megválasztania tiszta stratégiáját, hogy vesztesége minimális legyen. Ezt a veszteséget (minimax) a következőképpen jelezzük:

.

Egy másik példa ugyanabból a sorozatból.

2. példa Adott egy mátrix játék kifizetési mátrixszal

.

Határozza meg az első játékos maximin stratégiáját, a második játékos minimax stratégiáját, a játék alsó és felső árát.

Megoldás. A fizetési mátrix jobb oldalán kiírjuk a legkisebb elemeket a soraiba, és feljegyezzük a maximumot, a mátrix alatt pedig az oszlopok legnagyobb elemeit, és kiválasztjuk közülük a minimumot:

A sorok legkisebb elemei közül a legnagyobb a 3, ez a játék alacsonyabb ára, ennek a második sor felel meg, ezért az első játékos maximal stratégiája a második. Az oszlopok legnagyobb elemei közül a legkisebb az 5, ez a játék felső ára, az első oszlop ennek felel meg, ezért a második játékos minimax stratégiája az első.

Nyeregpont a mátrixos játékokban

Ha a játék felső és alsó ára megegyezik, akkor a mátrixjáték nyeregpontosnak minősül. Ez fordítva is igaz: ha egy mátrixjátéknak van nyeregpontja, akkor a mátrixjáték felső és alsó ára megegyezik. A megfelelő elem a legkisebb a sorban és a legnagyobb az oszlopban, és megegyezik a játék árával.

Így ha , akkor az első játékos optimális tiszta stratégiája, és a második játékos optimális tiszta stratégiája. Azaz azonos alsó és felső játékárat ugyanazzal a stratégiapárral lehet elérni.

Ebben az esetben mátrix játéknak van megoldása a tiszta stratégiákban .

3. példa Adott egy mátrix játék kifizetési mátrixszal

.

Megoldás. A fizetési mátrix jobb oldalán kiírjuk a legkisebb elemeket a soraiba, és feljegyezzük a maximumot, a mátrix alatt pedig az oszlopok legnagyobb elemeit, és kiválasztjuk közülük a minimumot:

A játék alsó ára egybeesik a játék felső árával. Így a játék ára 5. Azaz . A játék ára megegyezik a nyeregpont értékével. Az első játékos maxin stratégiája a második tiszta stratégia, a második játékos minimax stratégiája pedig a harmadik tiszta stratégia. Ez a mátrix játék tisztán stratégiákban kínál megoldást.

Oldj meg egy mátrixjáték problémát magad, majd nézd meg a megoldást

4. példa Adott egy mátrix játék kifizetési mátrixszal

.

Keresse meg a játék alsó és felső árát. Ennek a mátrixos játéknak van nyeregpontja?

Mátrix játékok optimális vegyes stratégiával

A legtöbb esetben egy mátrixjátéknak nincs nyeregpontja, így a megfelelő mátrixjátéknak nincsenek tiszta stratégiáiban megoldásai.

De van megoldása az optimális vegyes stratégiákban. Megtalálásukhoz azt kell feltételezni, hogy a játékot elegendő számú alkalommal megismétlik, hogy a tapasztalatok alapján kitalálhassa, melyik stratégia előnyösebb. Ezért a döntéshez a valószínűség és az átlag (matematikai elvárás) fogalma kapcsolódik. A végső megoldásban van a nyeregpont analógja (vagyis a játék alsó és felső árának egyenlősége), valamint a nekik megfelelő stratégiák analógja.

Tehát ahhoz, hogy az első játékos megszerezze a maximális átlagos győzelmet, a második játékos pedig minimális átlagos veszteséget, bizonyos valószínűséggel tiszta stratégiákat kell alkalmazni.

Ha az első játékos tiszta stratégiákat alkalmaz valószínűségekkel , majd a vektor vegyes első játékos stratégiának nevezik. Más szóval, ez tiszta stratégiák „keveréke”. Ebben az esetben ezeknek a valószínűségeknek az összege eggyel egyenlő:

.

Ha a második játékos tiszta stratégiákat alkalmaz valószínűségekkel , majd a vektor második játékos vegyes stratégiának nevezik. Ebben az esetben ezeknek a valószínűségeknek az összege eggyel egyenlő:

.

Ha az első játékos vegyes stratégiát alkalmaz p, és a második játékos - vegyes stratégia q, akkor van értelme várható érték az első játékos győzelme (a második játékos vesztesége). Ennek megtalálásához meg kell szorozni az első játékos vegyes stratégia vektorát (amely egysoros mátrix lesz), a kifizetési mátrixot és a második játékos vegyes stratégia vektorát (ami egy oszlopos mátrix lesz):

.

5. példa Adott egy mátrix játék kifizetési mátrixszal

.

Határozza meg az első játékos nyerésének (a második játékos veszteségének) matematikai elvárásait, ha az első játékos vegyes stratégiája , a második játékosé pedig .

Megoldás. Az első játékos nyerésének (a második játékos veszteségének) matematikai elvárásának képlete szerint ez egyenlő az első játékos vegyes stratégiai vektorának, fizetési mátrixának és a második játékos vegyes stratégiai vektorának szorzatával:

Az első játékost olyan vegyes stratégiának nevezzük, amely a játék megfelelő számú megismétlése esetén a maximális átlagos nyereményt biztosítaná számára.

Optimális vegyes stratégia a második játékost olyan vegyes stratégiának nevezik, amely minimális átlagos veszteséget biztosít számára, ha a játékot elegendő számú alkalommal megismétlik.

A tiszta stratégiák esetében a maximin és a minimummax jelölésével analóg módon az optimális vegyes stratégiákat a következőképpen jelöljük (és az első játékos nyerésének és a második játékos veszteségének matematikai elvárásaihoz, azaz átlagához kapcsolódnak):

,

.

Ebben az esetben a funkcióhoz E van egy nyeregpont , ami egyenlőséget jelent.

Az optimális vegyes stratégiák és a nyeregpont megtalálása érdekében, azaz oldjon meg egy mátrix játékot vegyes stratégiákban , le kell redukálnia a mátrixjátékot lineáris programozási problémává, azaz optimalizálási feladattá, és meg kell oldania a megfelelő lineáris programozási feladatot.

Egy mátrixjáték redukálása lineáris programozási problémává

Ahhoz, hogy egy mátrixjátékot vegyes stratégiákban oldjunk meg, egyenes vonalat kell építeni lineáris programozási problémaÉs kettős feladat. A duális feladatban a kiterjesztett mátrixot transzponáljuk, amely a korlátok rendszerében tárolja a változók együtthatóit, a szabad tagokat és a változók együtthatóit a célfüggvényben. Ebben az esetben az eredeti feladat célfüggvényének minimuma a duális feladatban a maximumhoz illeszkedik.

Célfüggvény direkt lineáris programozási feladatban:

.

Kényszerrendszer direkt lineáris programozási feladatban:

A kettős probléma célfüggvénye a következő:

.

Korlátozások rendszere a kettős problémában:

A direkt lineáris programozási probléma optimális tervét jelöljük

,

és a kettős probléma optimális tervét jelöljük

A megfelelő optimális tervek lineáris alakjait és -vel jelöljük,

és ezeket az optimális tervek megfelelő koordinátáinak összegeként kell megtalálni.

Az előző bekezdés definícióinak és az optimális tervek koordinátáinak megfelelően az első és második játékos alábbi vegyes stratégiái érvényesek:

.

Az elméleti matematikusok bebizonyították játék ára a következőképpen fejeződik ki az optimális tervek lineáris formáin keresztül:

,

vagyis az optimális tervek koordinátaösszegeinek reciproka.

Mi, gyakorlók, ezt a képletet csak vegyes stratégiájú mátrixjátékok megoldására használhatjuk. Mint képletek az optimális vegyes stratégiák megtalálásához az első és a második játékos:

amelyben a második faktorok a vektorok. Az optimális vegyes stratégiák is, amint azt az előző bekezdésben meghatároztuk, vektorok. Ezért a számot (játék árát) megszorozva egy vektorral (az optimális tervek koordinátáival) vektort is kapunk.

6. példa. Adott egy mátrix játék kifizetési mátrixszal

.

Keresse meg a játék árát Vés optimális vegyes stratégiák és .

Megoldás. Létrehozunk egy lineáris programozási feladatot ennek a mátrixjátéknak megfelelően:

Megoldást kapunk a közvetlen problémára:

.

Az optimális tervek lineáris alakját a talált koordináták összegeként találjuk meg.

A játékelméletben részletesen kidolgozott legegyszerűbb eset egy véges, nulla összegű páros játék (két személy vagy két koalíció antagonisztikus játéka). Tekintsünk egy G játékot, amelyben két A és B játékos vesz részt, ellentétes érdekekkel: az egyik nyeresége egyenlő a másik veszteségével. Mivel az A játékos nyereménye megegyezik a B játékos nyereményével ellenkező előjellel, ezért minket csak az a játékos nyereménye érdekelhet. Természetesen A maximalizálni, B pedig minimalizálni akarja a-t.

Az egyszerűség kedvéért mentálisan azonosítsuk magunkat az egyik játékossal (legyen az A), és nevezzük őt „mi”-nek, B játékost pedig „ellenfélnek” (természetesen ebből A számára nem származik valódi előny). Legyen lehetséges stratégiáink és az ellenfél - lehetséges stratégiáink (az ilyen játékot játéknak hívják). Jelöljük a nyereményünket, ha mi alkalmazzuk a stratégiát, az ellenfél pedig a stratégiát

26.1. táblázat

Tételezzük fel, hogy minden stratégiapár esetében a kifizetés (vagy átlagos kifizetés) a számunkra ismert. Ekkor elvileg meg lehet alkotni egy téglalap alakú táblázatot (mátrixot), amely felsorolja a játékosok stratégiáit és a hozzájuk tartozó kifizetéseket (lásd 26.1. táblázat).

Ha összeállítanak egy ilyen táblázatot, akkor azt mondják, hogy a G játékot mátrix formára redukálták (a játék ilyen formába hozása már önmagában is nehéz feladat, és néha szinte lehetetlen a stratégiák hatalmas változatossága miatt ). Vegye figyelembe, hogy ha a játék mátrix formájúvá redukálódik, akkor a többlépéses játék valójában egylépéses játékká redukálódik – a játékosnak csak egy lépést kell tennie: válasszon egy stratégiát. Röviden jelöljük a játékmátrixot

Nézzünk egy példát a G (4X5) játékra mátrix formában. Négy stratégia áll a rendelkezésünkre (választható), míg az ellenségnek öt stratégiája van. A játék mátrixát a 26.2 táblázat tartalmazza

Gondoljuk végig, milyen stratégiát alkalmazzunk (A játékos)? A Mátrix 26.2-ben van egy csábító "10"-es kifizetés; kísértésbe esünk, hogy olyan stratégiát válasszunk, amelyben megkapjuk ezt a „finomságot”.

De várjunk csak: az ellenség sem bolond! Ha mi választunk egy stratégiát, akkor ő, dacára, a stratégiát választja, és kapunk valami szánalmas „1”-et. Nem, nem választhat stratégiát! Hogyan legyen? Nyilvánvalóan az óvatosság elve alapján (és ez a játékelmélet alapelve) azt a stratégiát kell kiválasztanunk, amelynél a minimális nyereségünk maximális.

26.2. táblázat

Ez az úgynevezett „mini-max elv”: cselekedj úgy, hogy az ellenfél számodra legrosszabb viselkedését figyelembe véve a maximális nyereményed legyen.

Írjuk át a 26.2 táblát, és a jobb oldali kiegészítő oszlopba írjuk fel az egyes sorok minimális nyerőértékét (sor minimum); jelöljük az a sorra (lásd a 26.3 táblázatot).

26.3. táblázat

Az összes érték közül (jobb oldali oszlop) a legnagyobb (3) van kiemelve. A stratégia megfelel ennek. Ha ezt a stratégiát választjuk, akkor mindenképpen biztosak lehetünk benne, hogy (az ellenség bármilyen viselkedése esetén) nem kevesebbet nyerünk, mint 3. Ez az érték a mi garantált nyereményünk; Óvatosan viselkedve ennél kevesebbet nem kaphatunk, talán többet is kapunk).

Ezt a nyereményt a játék alacsonyabb árának nevezik (vagy „maximin” - a minimális nyeremény maximuma). Jelöljük a. A mi esetünkben

Most vegyük az ellenség nézőpontját és okát vele kapcsolatban. Nem valami gyalog, de okos is! Stratégiaválasztáskor kevesebbet szeretne adni, de a mi legrosszabb viselkedésünkkel kell számolnia. Ha stratégiát választ, válaszolunk neki, és 10-et ad; Ha úgy dönt, válaszolunk neki, és ő ad stb. A 26.3 táblázathoz egy további alsó sort adunk, és felírjuk az oszlopok maximális értékét. minimális (a megfelelő 5 értéket a 26.3. táblázat kiemeli) . Ez a P érték a nyereség értéke, amelynél többet egy ésszerű ellenfél biztosan nem ad nekünk. Ezt a játék felső árának nevezik (vagy „mi-nimax” - a maximális nyeremény minimuma). Példánkban és az ellenség stratégiájával érjük el

Tehát az óvatosság elve (a „mindig a legrosszabbra számolj!” viszontbiztosítási szabály) alapján az A stratégiát és az ellenséget - stratégia választanunk kell. Az ilyen stratégiákat „minimax”-nak nevezzük (a minimax elv alapján). Mindaddig, amíg példánkban mindkét fél ragaszkodik a minimax stratégiájához, a nyeremény az lesz

Most képzeljük el egy pillanatra, hogy megtanultuk, hogy az ellenség stratégiát követ. Gyerünk, büntessük meg ezért és válasszunk stratégiát, 5-öt kapunk, és ez nem is olyan rossz. De az ellenség sem kudarc; tudassa vele, hogy a mi stratégiánk , ő is sietni fog a választással, 2-re csökkentve nyereményünket stb. (a partnerek „stratégiákkal rohantak”). Röviden, a példánkban szereplő minimax stratégiák instabilok a másik fél viselkedésével kapcsolatos információk tekintetében; ezek a stratégiák nem rendelkeznek az egyensúlyi tulajdonsággal.

Ez mindig így van? Nem mindig. Tekintsük a példát a 26.4. táblázatban megadott mátrixszal.

Ebben a példában a játék alsó ára megegyezik a felső árral: . Mi következik ebből? Az A és B játékosok minimax stratégiája stabil lesz. Amíg mindkét játékos betartja ezeket, a nyeremény 6. Nézzük meg, mi történik, ha (A) megtudjuk, hogy az ellenfél (B) betartja a B stratégiát?

26.4. táblázat

De semmi sem fog változni, mert a stratégiától való bármilyen eltérés csak ronthat a helyzetünkön. Ugyanígy az ellenfél által kapott információ sem kényszeríti őt arra, hogy eltérjen a stratégiájától.Egy stratégiapárnak megvan az egyensúlyi tulajdonsága (egy kiegyensúlyozott stratégiapár), és a kifizetődő (esetünkben 6) ezzel a stratégiapárral „a mátrix nyeregpontjának” nevezik. A nyeregpont és a kiegyensúlyozott stratégiapár jelenlétének jele a játék alsó és felső árának egyenlősége; a teljes értéket a játék árának nevezzük. Jelölni fogjuk

Azokat a stratégiákat (ebben az esetben), amelyeknél ezt a nyereséget elérjük, optimális tiszta stratégiáknak, ezek összességét pedig a játék megoldásának nevezzük. Ilyenkor magáról a játékról azt mondják, hogy tiszta stratégiákban oldják meg. Mind A, mind B fél megkaphatja a maga optimális stratégiáját, amelyben a lehető legjobb pozíciót képviseli. És ha A játékos 6-ot nyer, B játékos pedig veszít, akkor ezek a játék feltételei: A számára előnyösek, B-nek pedig hátrányosak.

Az olvasóban felmerülhet a kérdés: miért nevezik az optimális stratégiákat „tisztának”? Kicsit előre tekintve erre a kérdésre válaszolunk: vannak „vegyes” stratégiák, amelyek abból állnak, hogy a játékos nem csak egy stratégiát alkalmaz, hanem több stratégiát is, ezeket véletlenszerűen összekeverve. Tehát, ha a tiszta stratégiák mellett megengedjük a vegyes stratégiákat, akkor minden véges játéknak van megoldása - egy egyensúlyi pont. De ezt még meg kell vitatni.

A nyeregpont jelenléte a játékban korántsem szabály, inkább kivétel. A legtöbb játéknak nincs nyeregpontja. Létezik azonban olyan játéktípus, amelynek mindig van nyeregpontja, és ezért tiszta stratégiákkal oldják meg. Ezek az úgynevezett „teljes információs játékok”. A teljes információs játék egy olyan játék, amelyben minden játékos minden személyes lépésével ismeri fejlődésének teljes hátterét, azaz minden korábbi lépésének eredményét, akár személyes, akár véletlenszerűen. Példák a teljes információt tartalmazó játékokra: dáma, sakk, tic-tac-toe stb.

A játékelméletben bebizonyosodott, hogy minden teljes információval rendelkező játéknak van nyeregpontja, ezért tiszta stratégiákban oldják meg. Minden játékban, teljes információval, van egy pár optimális stratégia, amely a játék költségével megegyező stabil kifizetést ad és. Ha egy ilyen játék csak személyes mozdulatokból áll, akkor ha minden játékos az optimális stratégiáját alkalmazza, annak nagyon határozottan kell végződnie - a játék költségének megfelelő győzelemmel. Ez azt jelenti, hogy ha ismert a játék megoldása, akkor maga a játék értelmét veszti!

Vegyünk egy elemi példát egy teljes információs játékra: két játékos felváltva helyezi el a nikkeleket egy kerek asztalon, véletlenszerűen választva az érme középpontjának helyzetét (az érmék kölcsönös átfedése nem megengedett). Az nyer, aki az utolsó nikkelt is beleteszi (amikor nem marad hely másoknak). Könnyen belátható, hogy ennek a játéknak a kimenetele lényegében előre meghatározott. Létezik egy bizonyos stratégia, amely biztosítja, hogy az a játékos nyer, aki először helyezi el az érmét.

Ugyanis először egy nikkelt kell tennie az asztal közepére, majd minden ellenfél lépésére szimmetrikus mozdulattal kell válaszolnia. Nyilvánvaló, hogy bárhogyan is viselkedik az ellenség, nem kerülheti el a veszteséget. Pontosan ugyanez a helyzet a sakkkal és általában a teljes információs játszmákkal: bármelyik mátrix formában írt nyeregponttal rendelkezik, ami azt jelenti, hogy a megoldás tiszta stratégiákban van, ezért csak addig van értelme, amíg ez a megoldás. nem találja. Mondjuk egy sakkjátszma vagy mindig fehér nyeréssel végződik, vagy mindig fekete nyeréssel, vagy mindig döntetlennel, de még nem tudjuk, hogy pontosan mi (a sakk szerelmeseinek szerencsére). Tegyük hozzá még: belátható időn belül nem valószínű, hogy megtudjuk, mert a stratégiák száma akkora, hogy rendkívül nehéz (ha nem lehetetlen) mátrix formába hozni a játékot, és nyeregpontot találni benne.

Most pedig tegyük fel magunknak a kérdést, hogy mit tegyünk, ha a játéknak nincs nyeregpontja: Nos, ha minden játékosnak egyetlen tiszta stratégiát kell választania, akkor nincs mit tenni: a minimax elvnek kell vezérelnie. Más kérdés, hogy tudod-e "keverni" a stratégiáidat, véletlenszerűen váltogatni őket bizonyos valószínűségekkel. A vegyes stratégiák alkalmazását így gondolják: a játékot sokszor megismétlik; a játék minden egyes játéka előtt, amikor a játékos személyes kört kap, választását a véletlenre „bízza”, „sorsot vet”, és a felmerült stratégiát választja (az előző fejezetből már tudjuk, hogyan kell a sorsolást megszervezni ).

A vegyes stratégiák a játékelméletben a változtatható, rugalmas taktika modelljei, amikor egyik játékos sem tudja, hogy az ellenfél hogyan fog viselkedni egy adott játékban. Ezt a taktikát (bár általában minden matematikai indoklás nélkül) gyakran használják a kártyajátékokban. Egyúttal jegyezzük meg, hogy a viselkedésed elrejtésének legjobb módja az ellenség elől, ha véletlenszerű karaktert adsz neki, és ezért nem tudod előre, mit fogsz tenni.

Tehát beszéljünk a vegyes stratégiákról. Jelöljük az A és B játékos vegyes stratégiáit, ahol (összesen egyet alkotva) - annak valószínűsége, hogy A játékos stratégiát használ - annak valószínűsége, hogy B játékos stratégiát használ.

Abban a speciális esetben, amikor egy kivételével minden valószínűség nulla, és ez az egy egyenlő eggyel, a vegyes stratégia tiszta egyessé válik.

A játékelméletnek van egy alaptétele: minden véges, kétszemélyes, nulla összegű játéknak van legalább egy megoldása – egy pár optimális stratégia, általában vegyes, és ennek megfelelő ára.

Egy játék megoldását képező optimális stratégiapárnak a következő tulajdonsága van: ha az egyik játékos ragaszkodik az optimális stratégiájához, akkor a másiknak nem lehet kifizetődő, ha eltér az övétől. Ez a stratégiapár egy bizonyos egyensúlyi helyzetet alakít ki a játékban: az egyik játékos a nyereséget maximumra, a másik minimálisra akarja fordítani, mindegyik a saját irányába húz, és mindkettő ésszerű viselkedése mellett egyensúlyt és stabil nyereséget akar elérni. v létrejönnek. Ha akkor a játék előnyös nekünk, ha - az ellenségnek; amikor a játék „tisztességes”, egyformán előnyös mindkét résztvevő számára.

Vegyünk egy példát egy nyeregpont nélküli játékra, és adjuk meg (bizonyíték nélkül) a megoldását. A játék a következő: két játékos A és B egyszerre, szó nélkül mutasson egy, két vagy három ujját. Az ujjak teljes száma dönti el a nyereményt: ha páros, akkor A nyer, és ezzel a számmal egyenlő összeget kap B-től; ha páratlan, akkor A éppen ellenkezőleg, ezzel a számmal egyenlő összeget fizet B-nek. Mit kell tenniük a játékosoknak?

Hozzunk létre egy játékmátrixot. Egy játékban minden játékosnak három stratégiája van: mutasson egy, két vagy három ujját. A 3x3-as mátrixot a 26.5. táblázat tartalmazza; a további jobb oldali oszlop a sor minimumait, a további alsó sor pedig az oszlopmaximumokat mutatja.

A játék alacsonyabb ára megfelel a stratégiának, ez azt jelenti, hogy ésszerű, körültekintő magatartással garantáljuk, hogy nem veszítünk 3-nál többet. Kis vigasz, de még mindig jobb, mint mondjuk egy 5-ös győzelem, ami bizonyos cellákban található a mátrixból. Rossz nekünk, L játékos... De vigasztaljuk magunkat: úgy tűnik, az ellenség helyzete még rosszabb: a játék alacsonyabb ára. ésszerű viselkedés szerint legalább 4-et ad nekünk.

Bevezetés

A valódi konfliktushelyzetek különböző típusú játékokhoz vezetnek. A játékok több szempontból is különböznek egymástól: a bennük résztvevő játékosok száma, a lehetséges játékosok száma, a lehetséges stratégiák száma, a játékosok közötti kapcsolatok jellege, a nyeremények jellege, a játék típusa szerint. nyerő funkciók, a lépések száma, a játékosok információszolgáltatásának jellege stb. .d. Tekintsük a játéktípusokat a felosztásuktól függően:

· A stratégiák száma szerint a játékok fel vannak osztva végső(minden játékosnak véges számú lehetséges stratégiája van) és végtelen(ahol legalább az egyik játékosnak végtelen számú lehetséges stratégiája van).

· A nyeremények jellegének megfelelően a játékok nulla összeg(a játékosok össztőkéje nem változik, hanem az eredménytől függően újraosztódik a játékosok között) és a nem nulla összeg.

· A funkciók típusának megfelelően a játék nyereményei fel vannak osztva mátrix ( egy véges, kétfős, nulla összegű játék, amelyben a játékos nyereményét megadják A mátrix formájában (a mátrix egy sora a játékos használt stratégiájának számának felel meg BAN BEN, oszlop – a játékos használt stratégiájának száma BAN BEN; a mátrix sorának és oszlopának metszéspontjában van a játékos nyereménye A, amely megfelel az alkalmazott stratégiáknak.

A mátrixos játékoknál bebizonyosodott, hogy bármelyiknek van megoldása, és ez könnyen megtalálható, ha a játékot lineáris programozási problémává redukálják), bimátrix játék (ez egy véges játék két játékosból nem nulla összeggel, amelyben minden játékos nyereményét mátrixok adják meg külön a megfelelő játékos számára (minden mátrixban egy sor felel meg a játékos stratégiájának A, oszlop – játékos stratégiák BAN BEN, az első mátrix sorának és oszlopának metszéspontjában a játékos nyereménye A, a második mátrixban – a játékos nyereményei BAN BEN.

A bimátrixos játékokhoz is kidolgozták az optimális játékos viselkedés elméletét, de az ilyen játékok megoldása nehezebb, mint a hagyományos mátrixos játékoknál. folyamatos játékok ( Folyamatos Olyan játéknak tekintik, amelyben az egyes játékosok kifizetési funkciója a stratégiáktól függően folyamatos. Bebizonyosodott, hogy az ebbe az osztályba tartozó játékoknak vannak megoldásai, de ezek megtalálására nem dolgoztak ki gyakorlatilag elfogadható módszereket) stb.

A játékok felosztásának más módjai is lehetségesek. Most térjünk vissza közvetlenül a kutatás témájához, nevezetesen a játékelmélethez. Először is határozzuk meg ezt a fogalmat.

Játékelmélet - a matematikának egy olyan ága, amely a konfliktusok körülményei között optimális döntéshozatal formális modelljeit tanulmányozza. Ebben az esetben konfliktus alatt olyan jelenséget értünk, amelyben különböző felek vesznek részt, különböző érdekekkel és lehetőségekkel rendelkeznek, hogy ezeknek az érdekeknek megfelelően válasszák meg a rendelkezésükre álló cselekvéseket. bizonytalansággá emelkedik. Éppen ellenkezőleg, a döntések bizonytalansága (például elégtelen adatok alapján) a döntési alany és a természet közötti konfliktusként értelmezhető. Ezért a játékelméletet a bizonytalanság körülményei között optimális döntések elméletének is tekintik. Lehetővé teszi a technológia, a mezőgazdaság, az orvostudomány, a szociológia és más tudományok döntéshozatalának néhány fontos szempontjának rendszerezését. A konfliktusban érintett feleket akciókoalícióknak nevezzük; a rendelkezésükre álló cselekvések – stratégiáik által; a konfliktus lehetséges kimenetelei – helyzetek.

Az elmélet célja, hogy:

1) optimális viselkedés a játékban.

2) az optimális viselkedés tulajdonságainak tanulmányozása

3) meghatározni azokat a feltételeket, amelyek mellett használata értelmes (létkérdések, egyediség, dinamikus játékoknál pedig névleges konzisztencia kérdései).

4) numerikus módszerek kidolgozása az optimális viselkedés megtalálására.

A gazdasági és társadalmi eredetű problémák matematikai megoldására megalkotott játékelmélet általában nem redukálható le a klasszikus matematikai elméletekre, amelyeket fizikai és technikai problémák megoldására hoztak létre. A klasszikus matematikai módszerek széles skáláját azonban széles körben alkalmazzák a játékelmélet különböző specifikus kérdéseiben.

Ezen túlmenően a játékelmélet számos matematikai tudományághoz belsőleg kapcsolódik. A játékelméletben a valószínűségszámítás fogalmait szisztematikusan és lényegileg használják. A játékelmélet nyelvén a matematikai statisztika legtöbb problémája megfogalmazható, és mivel a játékelmélet a döntéshozatal elméletéhez kapcsolódik, az operációkutatás matematikai apparátusának lényeges részének tekintendő.

A játék matematikai fogalma szokatlanul tág. Tartalmazza az úgynevezett társasjátékokat (beleértve a sakkot, a dámát, a GO-t, a kártyajátékokat, a dominót), de használható egy olyan gazdasági rendszer modelljei leírására is, ahol számos vevő és eladó verseng egymással. Anélkül, hogy belemennénk a részletekbe, egy játék tágabban definiálható úgy, mint egy olyan helyzet, amelyben egy vagy több egyén („játékos”) több változót közösen irányít, és minden játékosnak figyelembe kell vennie az egész csoport cselekedeteit a döntés meghozatalakor. Az egyes játékosokat megillető „fizetést” nem csak a saját, hanem a csoport többi tagjának cselekedetei is meghatározzák. Néhány „mozgás” (egyéni cselekvés) a játék során véletlenszerű lehet. Jó példa erre a híres pókerjáték: a kezdeti kártyaosztás véletlenszerű lépés. A trükkök végső összehasonlítását megelőző tétek és ellentétek sorrendjét a játék hátralévő lépései alkotják.

A matematikai JÁTÉKELMÉLET a sport-, kártya- és egyéb játékok elemzésével kezdődött. Azt mondják, hogy a játékelmélet felfedezője, a 20. század kiváló amerikai matematikusa. John von Neumann egy pókerjáték nézése közben adta elő az elméletét. Innen származik a „játékelmélet” elnevezés.

Kezdjük ezzel a témával foglalkozni a játékelmélet fejlődésének retrospektív elemzése. Tekintsük a játékelmélet kérdéskörének történetét és fejlődését. Általában a „családfát” a gráfelmélet értelmében faként ábrázolják, amelyben az elágazás egyetlen „gyökérből” történik. A játékelmélet törzskönyve J. von Neumann és O. Morgenstern könyve. Ezért a játékelmélet, mint matematikai diszciplína fejlődésének történeti menete természetesen három szakaszra oszlik:

Első fázis- J. von Neumann és O. Morgenstern monográfiájának megjelenése előtt. Nevezhetjük „pre-monografikusnak”. Ebben a szakaszban a játék még mindig sajátos versenyként működik, amelyet a szabályai értelmes kifejezésekkel írnak le. J. von Neumann csak a végén alkot egy elképzelést a játékról, mint az absztrakt konfliktus általános modelljéről. Ennek a szakasznak az eredménye számos konkrét matematikai eredmény, sőt a jövő játékelméletének egyéni alapelvei felhalmozódása volt.

Második fázis maga a monográfia J. von Neumann és

O. Morgenstern „Játékelmélet és gazdasági viselkedés” (1944), amely a korábban kapott (a modern matematikai mércével mérve azonban meglehetősen kevés) eredmény nagy részét egyesítette. Ő volt az első, aki szisztematikus elmélet formájában mutatta be a játékok matematikai megközelítését (a szó konkrét és absztrakt értelmében is).

Végül tovább harmadik szakasz a játékelmélet a vizsgált tárgyak megközelítésében alig tér el a matematika többi ágától, és nagymértékben a rájuk jellemző törvényszerűségek szerint fejlődik. Ugyanakkor természetesen gyakorlati alkalmazásának sajátosságai – mind a tényleges, mind a lehetséges – jelentősen befolyásolják a játékelméleti irányok kialakítását.

Egyes konfliktusok kimenetelét azonban még a matematikai játékelmélet sem képes teljesen megjósolni. Lehetségesnek tűnik három fő okot azonosítani a játék (konfliktus) kimenetelének bizonytalanságában.

Először is, ezek olyan játékok, amelyekben valós lehetőség nyílik a játékviselkedés összes vagy legalábbis legtöbb változatának tanulmányozására, amelyek közül az egyik a legigazabb, ami nyeréshez vezet. A bizonytalanságot az opciók jelentős száma okozza, így nem mindig lehet teljesen minden lehetőséget megvizsgálni (például a japán GO játék, orosz és nemzetközi dáma, brit reversi).

Másodszor, a tényezők véletlenszerű befolyása a játékra a játékosok által megjósolhatatlan. Ezek a tényezők döntően befolyásolják a játék kimenetelét, és a játékosok csak kis mértékben irányíthatják és határozhatják meg őket. A játék végeredményét csak kismértékben, rendkívül jelentéktelen mértékben határozzák meg maguknak a játékosoknak a cselekedetei. Azokat a játékokat, amelyek kimenetele véletlenszerű okok miatt bizonytalan, szerencsejátéknak nevezzük. A játék kimenetele mindig valószínűségi vagy sejtéses (rulett, kocka, feldobás).

Harmadszor, a bizonytalanságot az okozza, hogy nincs információ arról, hogy a játszó ellenfél milyen stratégiát követ. A játékosok tudatlansága az ellenfél viselkedését illetően alapvető, és ezt a játékszabályok határozzák meg. Az ilyen játékokat stratégiai játékoknak nevezzük.

A játékelmélet az „Operations Research” egyik fontos része, és a matematikai modellek elméleti alapjait képviseli az optimális döntések meghozatalára olyan piaci viszonyok konfliktushelyzeteiben, amelyek verseny jellegűek, amikor az egyik ellenfél nyeri meg a másikat. a másik veszteségének költsége. Ezzel a szituációval együtt a különféle döntéshozatali problémák megfogalmazásának matematikai leírását adó Operációkutatás tudomány keretein belül a kockázati és bizonytalansági helyzeteket is figyelembe veszik. Bizonytalanság esetén a feltételek valószínűsége ismeretlen, és nincs mód további statisztikai információk beszerzésére róluk. A probléma megoldását körülvevő, bizonyos körülmények között megnyilvánuló környezetet „természetnek”, a megfelelő matematikai modelleket pedig „játékoknak a természettel” vagy „statisztikai játékelméletnek” nevezzük. A játékelmélet fő célja, hogy ajánlásokat dolgozzon ki a játékosok konfliktusban való kielégítő viselkedésére, azaz mindegyikük számára meghatározza az „optimális stratégiát”.

A szolgáltatás célja. Az online szolgáltatás használatával:

• meghatározni mátrix játék ára(alsó és felső határ), nyeregpont meglétének ellenőrzése, vegyes stratégia megoldása, játékosok minimax stratégiájának megkeresése;
• írjon le egy matematikai modellt egy pár duális lineáris programozási feladatról, oldjon meg egy mátrixjátékot a következő módszerekkel: minimax, szimplex módszer , grafikus(geometriai) módszer, Brown módszere.

Utasítás. Válassza ki a mátrix dimenzióját, majd kattintson a Tovább gombra. Az új párbeszédpanelen válasszon egy módszert a mátrixjáték megoldásához. Kitöltési példa. A számítási eredményeket Word formátumú jelentésben mutatjuk be.

Játék egy valós konfliktushelyzet matematikai modellje. A két játékos közötti konfliktushelyzetet páros játéknak nevezzük. Kényelmes egy nulla összegű páros játék tanulmányozása, ha azt mátrix formájában írjuk le. Ezt a játékot az ún mátrix; egy ij számokból álló mátrixot nevezünk fizetés. A táblázat az A fizetési mátrix által meghatározott játék megoldási lehetőségeit mutatja be.

Az algoritmus leírása:

1. A fizetési mátrix elemzése alapján meg kell határozni, hogy vannak-e benne dominált stratégiák, és ezeket ki kell küszöbölni.
2. Keresse meg a játék felső és alsó árát, és határozza meg, hogy van-e nyeregpontja (a játék alsó árának meg kell egyeznie a játék felső árával).
3. Ha létezik nyeregpont, akkor a játékosok optimális stratégiái, amelyek a játék megoldását jelentik, a nyeregpontnak megfelelő tiszta stratégiáik lesznek. A játék ára megegyezik a játék felső és alsó árával, amelyek megegyeznek egymással.
4. Ha a játéknak nincs nyeregpontja, akkor a játék megoldását vegyes stratégiákban kell keresni. Az optimális vegyes stratégiák meghatározásához m × n játékokban a szimplex módszert kell használni, miután először újrafogalmaztuk a játék problémáját lineáris programozási problémává.

Mutassuk be a mátrixjáték grafikus megoldásának algoritmusát.

ábra - Mátrixjáték megoldásának sémája.

Mátrixjátékok megoldási módszerei vegyes stratégiákban

Tehát, ha nincs nyeregpont, a játékot vegyes stratégiákkal oldják meg, és a következő módszerekkel oldják meg:

1. A játék megoldása egyenletrendszeren keresztül.
   Ha adott egy nxn (n=m) négyzetmátrix, akkor a valószínűségi vektort az egyenletrendszer megoldásával találhatjuk meg. Ezt a módszert nem mindig használják, és csak bizonyos esetekben alkalmazható (ha a mátrix 2x2, akkor a játék megoldása szinte mindig megtörténik). Ha a megoldás negatív valószínűségeket produkál, akkor ezt a rendszert szimplex módszerrel oldjuk meg.
2. A játék grafikus megoldása.
   Azokban az esetekben, amikor n=2 vagy m=2, mátrix játék grafikusan is megoldható.
3. Mátrixjáték megoldása szimplex módszerrel.
   Ebben az esetben a mátrix játék lecsökken