Küldje el a jó munkát a tudásbázis egyszerű. Használja az alábbi űrlapot

Diákok, végzős hallgatók, fiatal tudósok, akik a tudásbázist tanulmányaikban és munkájukban használják, nagyon hálásak lesznek Önnek.

Bevezetés

1. Elméleti rész

1.3 Játékrendelés 2x2

1.4 Algebrai módszer

1.5 Grafikus módszer

1.6 Játékok 2xn vagy mx2

1.7 Játékok megoldása mátrix módszerrel

2. Gyakorlati rész

2.2 Játékok 2xn és mx2

2.3 Mátrix módszer

2.4 Barna módszer

Az eredmények elemzése

Bevezetés

A nulla összegű játék egy nulla összegű játék. A nulla összegű játék egy nem kooperatív játék, amelyben két olyan játékos vesz részt, akiknek ellentétes a nyereménye.

Formálisan az antagonisztikus játékot egy trojka képviselheti , ahol X és Y az első és a második játékos stratégiáinak halmaza, F az első játékos kifizetési függvénye, hozzárendelve minden egyes stratégiapárt (x,y), ahol egy valós szám, amely megfelel a játék hasznosságának. az első játékos egy adott helyzet megvalósításában.

Mivel a játékosok érdekei ellentétesek, az F függvény egyben a második játékos vesztét is jelenti.

Történelmileg a nulla összegű játékok a matematikai játékelméleti modellek első osztálya, amellyel a szerencsejátékot leírták. Úgy gondolják, hogy ez a tanulmányi téma az, ahonnan a játékelmélet kapta a nevét. Manapság az antagonisztikus játékokat a nem kooperatív játékok szélesebb osztályának tekintik.

1. Elméleti rész

1.1 A játék alapvető definíciói és rendelkezései

A játékot egy olyan szabályrendszer jellemzi, amely meghatározza a játékban résztvevők számát, lehetséges akcióikat és a nyeremény elosztását viselkedésüktől és kimenetelüktől függően. A játékos egy résztvevőnek vagy a játékban résztvevők csoportjának minősül, akiknek olyan közös érdekei vannak, amelyek nem esnek egybe más csoportok érdekeivel. Ezért nem minden résztvevő számít játékosnak.

A játék szabályai vagy feltételei meghatározzák a játékosok lehetséges viselkedését, választásait és lépéseit a játék fejlődésének bármely szakaszában. A játékos választása azt jelenti, hogy kiválasztja valamelyik viselkedési lehetőséget. A játékos ezután mozdulatokkal választja meg ezeket. A lépés végrehajtása azt jelenti, hogy a játék egy bizonyos szakaszában a játékszabályok által biztosított lehetőségektől függően a választás egy részét vagy egészét egyszerre kell végrehajtani. A játék egy bizonyos szakaszában minden játékos megtesz egy lépést a választott választásnak megfelelően. A másik játékos, tudva vagy nem tudva az első játékos választásáról, szintén megtesz egy lépést. Minden játékos igyekszik figyelembe venni a játék múltbeli fejlődésére vonatkozó információkat, ha ezt a játékszabályok megengedik.

A játékos stratégiájának nevezzük azt a szabályrendszert, amely egyértelműen jelzi a játékos számára, hogy minden lépésnél milyen döntést kell hoznia, a játék eredményeként felmerülő helyzettől függően. A stratégia a játékelméletben egy bizonyos teljes cselekvési tervet jelent a játékos számára, amely megmutatja, hogyan kell cselekednie a játékfejlesztés minden lehetséges esetben. A stratégia a játék fejlesztésének bármely szakaszában a játékos rendelkezésére álló információk bármely állapotára vonatkozó utasítások összességét jelenti. Ebből már látszik, hogy a stratégiák lehetnek jók és rosszak, sikeresek és sikertelenek stb.

Nulla összegű játékról akkor beszélünk, ha az összes játékban az összes játékos nyereményének összege nullával egyenlő, azaz egy nulla összegű játékban az összes játékos össztőkéje nem változik, hanem újraosztódik a játékosok között. az eredménytől függően. Így sok gazdasági és katonai helyzet nulla összegű játéknak tekinthető.

Különösen a két játékos közötti zéró összegű játékot nevezik antagonisztikusnak, mivel a benne szereplő játékosok céljai közvetlenül ellentétesek: az egyik játékos nyeresége csak a másik veszteségének rovására történik.

1.1.1 Mátrixjátékok definíciója, példái és megoldásai tiszta stratégiákban

Egy kétjátékos nulla összegű mátrixjáték a következő absztrakt kétjátékos játékként fogható fel.

Az első játékosnak t stratégiája van i =1, 2,…, t, a másodiknak n stratégiája van j = 1, 2,…, p. Minden stratégiapár (i, j) egy a ij számhoz van társítva, amely kifejezi az az első játékos nyereménye a második játékosnak, ha az első játékos az i-edik stratégiáját használja, a második játékos pedig a j-edik stratégiáját.

Minden játékos egy lépést tesz: az első játékos kiválasztja az i-edik stratégiáját (i = 1, 2,..., m), a második a j-edik stratégiáját (j = 1, 2,..., n) , ami után az első játékos kap egy ij nyereményt a második játékos rovására (ha egy ij< 0, то это значит, что первый игрок платит второму сумму a ij). На этом игра заканчивается.

Az i játékos minden stratégiája = 1, 2,…, t; j = 1, 2,…, n-t gyakran tiszta stratégiának nevezik.

A kétjátékos nulla összegű mátrixjátékot ezentúl egyszerűen mátrixjátéknak nevezik. Nyilvánvalóan a mátrixjáték az antagonisztikus játékok közé tartozik. Definíciójából az következik, hogy egy mátrixjáték definiálásához elegendő egy A = (a ij) mátrixot megadni az első játékos nyereményeinek sorrendjében.

Ha figyelembe vesszük a kifizetési mátrixot

akkor az A mátrixú mátrixjáték minden játékát az i-edik sor első játékosának, a j-edik oszlop második játékosának a választására redukálják, és az első játékos kap (a második rovására). ) az A mátrixban az i-edik sor és a j-edik oszlop metszéspontjában található nyeremény.

Ahhoz, hogy egy valós konfliktushelyzetet mátrixjáték formájában formalizáljunk, meg kell határozni és újra kell számozni minden játékos tiszta stratégiáját, és létre kell hozni egy kifizetési mátrixot.

A következő lépés a játékosok optimális stratégiáinak és nyereményeinek meghatározása.

A játékok tanulmányozásában a legfontosabb a játékosok optimális stratégiáinak koncepciója. Ennek a fogalomnak intuitív jelentése a következő: egy játékos stratégiája akkor optimális, ha ennek a stratégiának a használata biztosítja számára a legnagyobb garantált nyereményt a másik játékos összes lehetséges stratégiája tekintetében. Ezen pozíciók alapján az első játékos az (1.1) képlet segítségével megvizsgálja a nyereményei A mátrixát a következőképpen: i minden egyes értékéhez (i = 1, 2,..., t) a minimális nyereményértéket a a második játékos által használt stratégiák

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

azaz meghatározzák az első játékos minimális nyereményét, feltéve, hogy az i-edik tiszta stratégiáját alkalmazza, majd ezekből a minimális nyereményekből egy olyan i = i 0 stratégiát találunk, amelynél ez a minimális nyeremény maximális lesz, azaz.

Meghatározás. Az (1.3) képlettel meghatározott b számot a játék alacsonyabb nettó árának nevezzük, és megmutatja, hogy az első játékos mekkora minimális nyereményt tud garantálni magának, ha tiszta stratégiáit alkalmazza a második játékos minden lehetséges akciójára.

A második játékosnak optimális viselkedésével törekednie kell, ha lehetséges, stratégiái révén az első játékos nyereményének minimalizálására. Ezért a második játékos számára találjuk

azaz meghatározásra kerül az első játékos maximális kifizetése, feltéve, hogy a második játékos a j-edik tiszta stratégiáját alkalmazza, majd a második játékos megtalálja a j = j 1 stratégiáját, amely szerint az első játékos megkapja a minimális kifizetést, azaz megtalálja

Meghatározás. Az (1.5) képlettel meghatározott b számot a játék nettó felső árának nevezzük, és megmutatja, hogy az első játékos mekkora maximális nyereményt tud garantálni magának stratégiáival. Más szóval, tiszta stratégiáinak alkalmazásával az első játékos nem kevesebb, mint b nyereményt biztosíthat, a második játékos pedig a tiszta stratégiáinak alkalmazásával megakadályozhatja, hogy az első játékos b-nél többet nyerjen.

Meghatározás. Ha egy A mátrixú játékban a játék alsó és felső nettó ára egybeesik, azaz b = c, akkor ennek a játéknak állítólag van nyeregpontja a tiszta stratégiákban és a játék nettó ára:

n = b = v (1,6)

A nyeregpont az első és a második játékos tiszta stratégiáinak () párja, amelyeknél az egyenlőség megvalósul.

A nyeregpont fogalmának jelentése a következő: ha az egyik játékos ragaszkodik egy nyeregpontnak megfelelő stratégiához, akkor a másik játékos nem tehet jobban, mint egy nyeregpontnak megfelelő stratégiát. Figyelembe véve, hogy a játékos legjobb viselkedése nem vezethet a nyeremény csökkenéséhez, a legrosszabb viselkedés pedig a nyeremény csökkenéséhez vezethet, ezek a feltételek matematikailag a következő összefüggések formájában írhatók fel:

ahol i, j az első és a második játékos bármely tiszta stratégiája; (i 0 , j 0) nyeregpontot képező stratégiák. Az alábbiakban megmutatjuk, hogy a nyeregpont definíciója egyenértékű az (1.8) feltételekkel.

Így az (1.8) alapján az A mátrixban a nyeregelem minimális az i 0. sorban és maximum a j 0. oszlopban. Az A mátrix nyeregpontjának megtalálása egyszerű: az A mátrixban a minimális elem egymás után megtalálható minden sort, és ellenőrizze, hogy ez az elem a legnagyobb az oszlopában. Ha ilyen, akkor nyeregelem, és a neki megfelelő stratégiapár nyeregpontot képez. Az első és a második játékos tiszta stratégiáinak (i ​​0 , j 0) párját, amelyek nyeregpontot és nyeregelemet alkotnak, a játék megoldásának nevezzük.

Az i 0 és j 0 nyeregpontot képező tiszta stratégiákat az első és a második játékos optimális tiszta stratégiájának nevezzük.

1. Tétel. Legyen f (x, y) két x A és y B változó valós függvénye és létezik

akkor b = c.

Bizonyíték. A minimum és maximum definíciójából az következik

Mivel (1.11) bal oldalán x tetszőleges, akkor

Az (1.12) egyenlőtlenség jobb oldalán y tehát tetszőleges

Q.E.D.

Konkrétan a () mátrix az f (x, y) függvény speciális esete, azaz ha x = i, y = j, = f (x, y) -t tesszük, akkor az 1. Tételből azt kapjuk, hogy az alsó net Az ár nem haladja meg a mátrixjáték felső nettó játékárát.

Meghatározás. Legyen f (x, y) két x A és y B változó valós függvénye. Az (x 0, y 0) pontot az f (x, y) függvény nyeregpontjának nevezzük, ha a következő egyenlőtlenségek teljesülnek

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

bármely x A és y B esetén.

1.2 Optimális vegyes stratégiák és tulajdonságaik

A mátrixjáték tanulmányozása azzal kezdődik, hogy a tiszta stratégiákban megtaláljuk a nyeregpontját. Ha egy mátrixjátéknak van nyeregpontja a tiszta stratégiákban, akkor a játék tanulmányozása ennek a pontnak a megtalálásával ér véget. Ha egy mátrixos játékban nincs nyeregpont a tiszta stratégiákban, akkor meg lehet találni ennek a játéknak az alsó és felső nettó árait, amelyek azt jelzik, hogy az első játékos ne reménykedjen a játék felső áránál többet nyerni. győződjön meg arról, hogy nyerni nem kevésbé alacsonyabb áron a játék. Az ilyen ajánlások a mátrixjátékban a játékosok viselkedésére vonatkozóan, tiszta stratégiák nyeregpontja nélkül, nem elégíthetik ki a kutatókat és a gyakorlati szakembereket. A mátrixjátékok megoldásainak tökéletesítését a tiszta stratégiák alkalmazásának titkának és a játékok többszöri megismétlésének lehetőségében kell keresni. Így például sakk-, dáma- és focijátékok sorozatát játsszák, és minden alkalommal a játékosok úgy alkalmazzák a stratégiájukat, hogy ellenfelüknek fogalmuk sincs a tartalmáról, és ezen az úton átlagosan bizonyos nyereményeket elérni a teljes játéksorozat megjátszásával. Ezek a nyeremények átlagosan nagyobbak, mint a játék alsó ára és kisebbek, mint a játék felső ára. Minél magasabb ez az átlagérték, annál jobb stratégiát használ a játékos. Ezért felmerült az ötlet, hogy a tiszta stratégiákat véletlenszerűen, bizonyos valószínűséggel alkalmazzuk. Ez teljes mértékben biztosítja használatuk titkosságát. Minden játékos megváltoztathatja a tiszta stratégiáinak használatának valószínűségét oly módon, hogy maximalizálja átlagos nyereményét, és optimális stratégiákat érjen el az út során. Ez az ötlet vezetett a vegyes stratégia koncepciójához.

Meghatározás. Egy játékos vegyes stratégiája a tiszta stratégiák használatának valószínűségeinek teljes halmaza.

Így, ha az első játékosnak m tiszta stratégiája van 1, 2, … i, … m, akkor az x vegyes stratégiája x = (x 1, x 2, ..., x i,…, x m ) számok halmaza kielégítő. a kapcsolatokat

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

Hasonlóképpen, a második játékos számára, akinek n tiszta stratégiája van, az y vegyes stratégia az y = (y 1, ..., y j, ... y n) számok halmaza, amely kielégíti az összefüggéseket.

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

Mivel minden alkalommal, amikor egy játékos egy tiszta stratégiát használ, kizárja egy másik használatát, a tiszta stratégiák összeegyeztethetetlen események. Ráadásul ezek az egyetlen lehetséges események.

Nyilvánvaló, hogy a tiszta stratégia a vegyes stratégia speciális esete. Valójában, ha egy vegyes stratégiában bármelyik i-edik tiszta stratégiát egy valószínűséggel alkalmazzák, akkor az összes többi tiszta stratégiát nem alkalmazzák. Ez az i-edik tiszta stratégia pedig a vegyes stratégia speciális esete. A titoktartás érdekében minden játékos a saját stratégiáját alkalmazza, függetlenül a másik játékos döntéseitől.

Meghatározás. Az A mátrixú mátrixjátékban az első játékos átlagos nyereményét a nyereményei matematikai elvárásaként fejezzük ki.

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

Nyilvánvaló, hogy az első játékos átlagos nyeresége két x és y változókészlet függvénye. Az első játékos a vegyes stratégiáinak x megváltoztatásával maximalizálja átlagos nyereményét E (A, x, y), a második játékos pedig vegyes stratégiáival arra törekszik, hogy E (A, x, y) minimális legyen, azaz. A játék megoldásához meg kell találni egy olyan x, y értéket, amelynél a játék felső ára elérhető.

1.3 Rendezési játék 22

A 22-es sorrendű mátrixjátékot a következő kifizetési mátrix adja az első játékos számára:

Ennek a játéknak a megoldását azzal kell kezdeni, hogy megtaláljuk a nyeregpontot a tiszta stratégiákban. Ehhez keresse meg az első sorban a minimális elemet, és ellenőrizze, hogy az oszlopában a maximum-e. Ha ilyen elem nem található, akkor a második sort is ugyanúgy ellenőrzi. Ha ilyen elem található a második sorban, akkor ez egy nyereg.

A nyeregelem megtalálása, ha van, lezárja a megoldás megtalálásának folyamatát, hiszen ebben az esetben a játék ára – a nyeregelem és a nyeregpont – meg lett találva, azaz tiszta stratégiapár az első és a nyeregpont. második játékos, optimális tiszta stratégiát alkotva. Ha a tiszta stratégiákban nincs nyeregpont, akkor vegyes stratégiákban kell nyeregpontot találni, ami a mátrixjátékok főtétele szerint szükségszerűen létezik.

Jelöljük x = (x 1, x 2), y = (y 1, y 2) az első és a második játékos vegyes stratégiáját. Emlékezzünk vissza, hogy x 1 azt a valószínűséget jelenti, hogy az első játékos alkalmazza az első stratégiáját, és x 2 = 1 - x 1 annak a valószínűsége, hogy a második stratégiáját használja. Hasonlóképpen a második játékos esetében: 1 annak a valószínűsége, hogy az első stratégiát alkalmazza, 2 = 1 - 1 annak a valószínűsége, hogy a második stratégiát használja.

A tétel következménye szerint ahhoz, hogy x és y vegyes stratégiák optimálisak legyenek, szükséges és elégséges, hogy nem negatív x 1, x 2, y 1, y 2 esetén a következő összefüggések teljesüljenek:

Mutassuk meg most, hogy ha egy mátrixjátéknak nincs nyeregpontja a tiszta stratégiákban, akkor ezeknek az egyenlőtlenségeknek egyenlőségekké kell alakulniuk:

Valóban. Hagyja, hogy tiszta stratégiákban ne legyen nyeregpontja a játéknak, akkor a vegyes stratégiák optimális értékei kielégítik az egyenlőtlenségeket

0<<1, 0<< 1,

0< <1, 01. (1.25)

Tegyük fel, hogy (1.22) mindkét egyenlőtlensége szigorú

akkor a tétel szerint y 1 = y 2 = 0, ami ellentmond az (1.25) feltételeknek.

Hasonlóképpen bebizonyosodott, hogy az (1.23)-ból származó mindkét egyenlőtlenség nem lehet szigorú egyenlőtlenség.

Tegyük fel most, hogy az (1.22) egyenlőtlenségek egyike lehet szigorú, például az első

Ez azt jelenti, hogy a tétel szerint y 1 = 0, y 2 = 1. Következésképpen az (1.23)-ból megkapjuk

Ha mindkét (1.24) egyenlőtlenség szigorú, akkor a tétel szerint x 1 = x 2 = 0, ami ellentmond (1.25). Ha egy 12 a 22, akkor az (1.27) egyenlőtlenségek egyike szigorú, a másik egyenlőség. Sőt, az egyenlőség a 12 és a 22 nagyobb elemére érvényes, azaz az (1.27)-ből származó egy egyenlőtlenségnek szigorúnak kell lennie. Például egy 12< а 22 . Тогда справедливо а 12 < v, а это равносильно тому, что первое неравенство из (1.24) строгое. Тогда согласно теореме должно х 1 = 0, что противоречит условию (1.25). Если а 12 = а 22 , то оба неравенства (1.27) превращаются в равенства и тогда можно положить х 1 = 0, что противоречит (1.25). Итак, предположение о том, что первое неравенство из (1.22) может быть строгим, не справедливо. Аналогично можно показать, что второе неравенство из (1.22) также не может быть строгим.

Így látható, hogy ha egy mátrixjátéknak nincs nyeregpontja a tiszta stratégiákban, akkor az első játékos optimális stratégiáinál az egyenlőtlenségek (1.22) egyenlőségekké alakulnak. Az (1.23) egyenlőtlenségekkel kapcsolatos hasonló érvelés ahhoz vezet, hogy ebben az esetben az (1.23) egyenlőtlenségeknek egyenlőségnek kell lenniük.

Tehát, ha egy 22-es sorrendű mátrixjátéknak nincs nyeregpontja, akkor az (1.24) egyenletrendszer megoldásával meghatározható a játékosok optimális vegyes stratégiája és a játék ára. Azt is megállapították, hogy ha egy 2x2-es sorrendű mátrixjátékban az egyik játékosnak van optimális tiszta stratégiája, akkor a másik játékosnak is van optimális tiszta stratégiája.

Következésképpen, ha egy mátrixjátéknak nincs nyeregpontja tiszta stratégiákban, akkor vegyes stratégiákban kell megoldást találnia, melyeket az (1.24) egyenletek határoznak meg. Az (1.25) rendszer megoldása

1.4 Algebrai módszer

A problémák algebrai módszerrel történő megoldására két eset lehetséges:

1. a mátrixnak van nyeregpontja;

2. a mátrixnak nincs nyeregpontja.

Az első esetben a megoldás a játék nyeregpontját képező stratégiapár. Nézzük a második esetet. A megoldásokat itt vegyes stratégiákban kell keresni:

Keressünk stratégiákat és... Amikor az első játékos az optimális stratégiáját használja, a második játékos például két ilyen tiszta stratégiát alkalmazhat

Sőt, a tulajdonságból adódóan, ha az egyik játékos optimális vegyes stratégiát használ, a másik pedig az optimális vegyes stratégiájában szereplő tiszta stratégiát nullától eltérő valószínűséggel, akkor a nyerési matematikai elvárás mindig változatlan és egyenlő marad. a játék árához, i.e.

A nyereménynek minden esetben meg kell egyeznie a V játék árával. Ebben az esetben a következő összefüggések érvényesek:

A (2.5), (2.6)-hoz hasonló egyenletrendszert szerkeszthetünk a második játékos optimális stratégiájához:

Figyelembe véve a normalizálási feltételt:

Oldjuk meg az (1.37) - (1.41) egyenletet az ismeretlenekre együtt, nem egyszerre, hanem egyszerre hármat: külön-külön (1.36), (1.38), (1.40) és (1.37), ( 1,39), (1,41). A megoldás eredményeként a következőket kapjuk:

1.5 Grafikus módszer

A 22. játék hozzávetőleges megoldása meglehetősen egyszerűen elérhető grafikus módszerrel. A lényege a következő:

1.1 ábra - egységnyi hosszúságú szakasz megtalálása

Válasszon ki egy egységnyi hosszúságú szakaszt az x tengelyen. A bal vége az első játékos első stratégiáját, a jobb oldala pedig a másodikat ábrázolja. Minden közbenső pont megfelel az első játékos vegyes stratégiáinak, és a ponttól jobbra lévő szakasz hossza megegyezik az első stratégia használatának valószínűségével, a bal oldali szakasz hossza pedig a felhasználás valószínűsége. a második stratégia az első játékos által.

Két I-I és II-II tengely van megrajzolva. A nyereményt az I-I-re helyezzük, amikor az első játékos az első stratégiát használja, a II-II-re, ha a második stratégiát használja. Például a második játékos alkalmazza az első stratégiáját, majd az értéket az I-I tengelyen, az értéket pedig a II-II tengelyen kell ábrázolni.

Az első játékos bármilyen vegyes stratégiája esetén a nyereményét a szegmens értéke határozza meg. Az I-I sor az első stratégia második játékos általi alkalmazásának felel meg, ezt a második játékos első stratégiájának nevezzük. Hasonlóképpen megszerkesztheti a második játékos második stratégiáját. Ekkor általában a játékmátrix grafikus megjelenítése a következő formában jelenik meg:

1.2 ábra - a játék árának megállapítása

Meg kell azonban jegyezni, hogy ezt az építkezést az első játékos számára hajtották végre. Itt a szegmens hossza megegyezik a V játékárral.

Az 1N2 vonalat alsó nyerési határnak nevezzük. Itt jól látható, hogy az N pont az első játékos garantált nyereményének maximális összegének felel meg.

Általánosságban elmondható, hogy ebből az ábrából a második játékos stratégiája is meghatározható, például a következő módokon. Az I-I tengelyen:

vagy a II-II tengelyen

A második játékos stratégiája azonban hasonlóan határozható meg, mint az első játékosnál, azaz. készítsünk egy ilyen grafikont.

1.3. ábra - a második játékos stratégiájának meghatározása

Itt az 1N2 sor a veszteség felső határa. Az N pont a második játékos minimális lehetséges veszteségének felel meg, és ez határozza meg a stratégiát.

A mátrix-együttható értékektől függően a grafikonok eltérő formájúak lehetnek, például ez:

1.4 ábra - meghatározza az első játékos optimális stratégiáját

Ilyen helyzetben az első játékos optimális stratégiája tiszta:

1.6 Játékok 2n vagy m2

A 2n sorrendű játékokban az első játékosnak 2 tiszta stratégiája van, a másodiknak pedig n tiszta stratégiája van, azaz. Az első játékos kifizetési mátrixa a következő:

Ha egy ilyen játéknak van nyeregpontja, akkor azt könnyű megtalálni és megoldást találni.

Tegyük fel, hogy a játéknak vannak nyeregpontjai. Ezután olyan vegyes stratégiákat kell találni, és ennek megfelelően az első és második játékost, valamint a játék árat v, amelyek kielégítik az összefüggéseket:

Mivel a játéknak nincs nyeregpontja, az egyenlőtlenség (1,54) helyére az egyenlőtlenségek lépnek.

Az (1.56), (1.55), (1.53) rendszerek megoldásához a grafikus módszert célszerű alkalmazni. Ebből a célból bevezetjük az egyenlőtlenség bal oldalának jelölését (1.53)

mátrix játék matematikai modellje

vagy (1.55)-ből kirakva és egyszerű transzformációkat végrehajtva megkapjuk

hol van az első játékos átlagos kifizetése, feltéve, hogy vegyes stratégiáját használja, a második pedig a j-edik tiszta stratégiáját.

A kifejezés szerint minden j=1, 2, …, n érték egy téglalap alakú koordinátarendszerben egy egyenesnek felel meg.

A második játékos célja, hogy stratégiáinak megválasztásával minimalizálja az első játékos nyereményét. Ezért számolunk

hol van a korlátozások halmazának alsó határa. Az 1.6. ábrán a függvény grafikonja vastag vonallal látható.

Közzétéve: http://www.allbest.ru/

1.6. ábra - függvénygrafikon

Az első játékos célja, hogy választás útján maximalizálja nyereményét, pl. kiszámítja

Az 1.6. ábrán a pont azt a maximális értéket jelenti, amelynél kapott. A játék ára azért van, mert:

Ily módon grafikusan meghatározásra kerül az első játékos optimális vegyes stratégiája és a második játékos tiszta stratégiapárja, amelyek a metszéspontban alkotnak egy pontot Az 1.6. ábra a második játékos 2. és 3. stratégiáját mutatja. Az ilyen stratégiák esetében az egyenlőtlenségek (1,53) egyenlőségekké alakulnak. Az 1.6. ábrán ezek a j=2, j=3 stratégiák.

Most meg tudjuk oldani az egyenletrendszert

és pontosan meghatározza a és értékeit (grafikusan hozzávetőlegesen határozzák meg). Ezután az összes olyan j értéket feltéve, amelyre nem alkotnak pontot, megoldjuk az (1.56) egyenletrendszert. Az 1.6. ábrán látható példánál ez a következő rendszer:

és a többi Ez a rendszer megoldható lejtős Ha valamilyen j=j 0 esetén a második játékos stratégiái egy M 0 pontot alkotnak, majd a korlátozáshalmazok alsó határának maximális értékét egy, a tengely Ebben az esetben az első játékosnak végtelen sok optimális értéke és a játék ára van Ezt az esetet az 1.7. ábra mutatja, ahol az MN szegmens a felső határokat ábrázolja, az optimális értékek a határokon belül vannak. tiszta optimális stratégiája van j=j 0 .

Grafikus módszerrel is megoldhatók m2-es mátrixjátékok. Az első játékos kifizetési mátrixának ebben az esetben a formája

Az első és a második játékos vegyes stratégiáját hasonlóan definiáljuk, mint a 2n sorrendű játékok esetében. A vízszintes tengely mentén ábrázoljuk a 0-tól 1-ig terjedő értéket, a függőleges tengely mentén az első játékos átlagos nyereményének értékét, azzal a feltétellel, hogy az első játékos a tiszta i-edik stratégiáját alkalmazza (i=1, 2, ..., m), a második - vegyes stratégiája (y 1, 1- y 1) =y. Például ha m=4 grafikusan) az 1.7. ábra szerint ábrázolható.

1.7. ábra - függvénygrafikon)

Az első játékos megpróbálja maximalizálni átlagos nyereményét, ezért igyekszik megtalálni

A függvényt vastag vonal jelöli, és a megszorítások halmazának felső korlátját jelenti. A második játékos stratégiája megválasztásával próbál minimalizálni, pl. érték megfelel

Az ábrán az értéket pont jelzi. Más szavakkal, az első játékos két stratégiája és a második játékos valószínűsége határozza meg, hogy mikor érhető el az egyenlőség

Az ábráról azt látjuk, hogy a játék ára a pont ordinátája, a valószínűség a pont abszcisszája. A fennmaradó tiszta stratégiák az első játékos az optimális vegyes stratégia kell ().

Így az (1.69) rendszer megoldásával megkapjuk a második játékos optimális stratégiáját és a játék árát. Az első játékos számára optimális vegyes stratégiát a következő egyenletrendszer megoldásával találjuk meg:

1.7 Mátrix módszer a játékok megoldására

Megnevezések:

A sorrendi mátrix bármely négyzetes részmátrixa

Mátrix(1);

Mátrix transzponált;

Mátrix adjungált B-hez;

- (1) az X-ből az átvételkor törölt soroknak megfelelő elemek törlésével kapott mátrix;

- (1) az átvételkor törölt soroknak megfelelő elemek törlésével kapott mátrix.

Algoritmus:

1. Válassza ki a () sorrendű mátrix négyzetes részmátrixát és számítsa ki

2. Ha néhány vagy, akkor dobja el a talált mátrixot, és próbáljon ki egy másik mátrixot.

3. Ha (), (), akkor kiszámítjuk és megszerkesztjük X-et és -ból és -ből, a megfelelő helyeken nullákat adva.

Annak ellenőrzése, hogy az egyenlőtlenségek teljesülnek-e

mindenkinek (1,75)

és egyenlőtlenségek

mindenkinek (1,76)

Ha az egyik kapcsolat nem elégedett, akkor megpróbálunk egy másikat. Ha minden összefüggés érvényes, akkor X, és a szükséges megoldások.

1.8 A játék árának egymás utáni közelítésének módszere

A játékhelyzetek tanulmányozása során gyakran előfordulhat, hogy nem kell pontos megoldást találni a játékra, vagy valamilyen oknál fogva lehetetlen vagy nagyon nehéz megtalálni a játék árának és az optimális vegyes stratégiáknak a pontos értékét. Ezután közelítő módszereket használhat egy mátrixjáték megoldására.

Leírjuk ezen módszerek egyikét – a játék árának egymás utáni közelítésének módszerét. A módszer alkalmazásával számított szám megközelítőleg a kifizetési mátrix sorainak és oszlopainak számával arányosan növekszik.

A módszer lényege a következő: a játékot sokszor mentálisan játsszák, i.e. szekvenciálisan minden játékban a játékos kiválasztja azt a stratégiát, amely a legnagyobb összesített (teljes) nyereményt adja.

Egyes játékok ilyen végrehajtása után kiszámítják az első játékos nyereményének és a második játékos veszteségének átlagértékét, és ezek számtani átlagát a játék költségének hozzávetőleges értékének tekintik. A módszer lehetővé teszi mindkét játékos optimális vegyes stratégiájának közelítő értékének meghatározását: ki kell számítani az egyes tiszta stratégiák alkalmazási gyakoriságát, és hozzávetőleges értéknek kell tekinteni a megfelelő játékos optimális vegyes stratégiájában.

Bizonyítható, hogy a programjátékok számának korlátlan növekedésével az első játékos átlagos nyeresége és a második játékos átlagos vesztesége korlátlanul megközelíti a játék árát, illetve a vegyes stratégiák hozzávetőleges értékeit. Az az eset, amikor a játék egyedi megoldással rendelkezik, az egyes játékosok optimális vegyes stratégiáira hajlamos. Általánosságban elmondható, hogy az ezen értékek feletti közelítő értékek lassan közelítik meg a valódi értékeket. Ez a folyamat azonban könnyen gépesíthető, és ezáltal még viszonylag nagy rendű kifizetési mátrixok esetén is segít a játék megfelelő pontosságú megoldásában.

2. Gyakorlati rész

A pár eldönti, hova menjen sétálni, és mindkettőjük számára hasznosan eltölteni az időt.

A lány elhatározza, hogy elmegy sétálni a parkba, hogy friss levegőt szívjon, este pedig filmet néz a legközelebbi moziban.

A srác azt javasolja, menjünk el a technológiai parkba, majd nézzük meg a helyi klubfocisták meccsét a központi stadionban.

Ennek megfelelően meg kell találnia, hogy mennyi időbe telik az egyik játékos céljának elérése. A nyertes mátrix így fog kinézni:

1. táblázat Kifizetési mátrix

Stratégiák

1 2 óta nyilvánvalóan ennek a játéknak nincs nyeregpontja a tiszta stratégiákban. Ezért a következő képleteket használjuk, és megkapjuk:

Közzétéve: http://www.allbest.ru/

2.2 Játék 2xn és mx2

1. feladat (2xn)

Két gabonanövényt termesztenek száraz és nedves éghajlatra.

A természet állapota pedig a következőnek tekinthető: száraz, nedves, mérsékelt.

Közzétéve: http://www.allbest.ru/

Az M() maximális értékét az M pontban érjük el, amelyet a j=1, j"=2 egyenesek metszéspontja képez. Eszerint feltételezzük:

2. feladat (mx2)

Egy srác és egy lány fontolgatja a lehetőségeket, hogy hova menjenek hétvégére.

A nyaralóhely választása a következőképpen fogható fel: park, mozi, étterem.

Közzétéve: http://www.allbest.ru/

Az M() maximális értékét az E pontban érjük el, amelyet a j=1, j"=2 egyenesek metszéspontja képez. Eszerint feltételezzük:

A v értékének meghatározásához a következő egyenleteket kell megoldani:

2.5 Mátrix módszer

Két egymással versengő étterem (vendéglátó egység) az alábbi szolgáltatáscsomagokat nyújtja. Az első étterem a központban, a másik a város szélén található.

A központi étterem az alábbi szolgáltatásokat nyújtja:

1) drágább és minőségibb ügyfélszolgálat;

2) az ételek középpontjában a francia konyha áll;

A második étterem a következőket kínálja:

1) olcsó és jó minőségű szolgáltatás;

2) a menü ötvözi a világ különböző híres konyháit;

3) állandó akciók és kedvezmények;

4) házhoz szállítással szállítja és fogadja a megrendeléseket.

A feladatnak megfelelően az egy nap nyereségét két étterem között a következőképpen osztjuk fel:

2. táblázat: Kifizetési mátrix

Stratégiák

Egy ilyen alakú játék megoldása mátrix módszerrel:

Hat részmátrix van és:

Tekintsük a mátrixot:

x 1 = ? 0, x 2 = ? 0

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

Nézzük most a mátrixot:

x 1 = ? 0, x 2 = ? 0

A játék ára.

Ez az arány ellentmond a követelménynek, ezért nem megfelelő.

Nézzük most a mátrixot:

x 1 = , x 2 = ? 0,

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

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

Nézzük most a mátrixot:

x 1 = , x 2 = 0, mivel x 2 = 0, akkor eldobjuk és.

Nézzük most a mátrixot:

x 1 = , x 2 = ? 0. Mivel x 1 = 0, eldobjuk és.

Nézzük most a mátrixot:

x 1 = , x 2 =, y 1 = , y 2 =, akkor folytatjuk tovább:

x 1 = , x 2 = , y 1 = , y 2 = vagy

A játék ára.

Most az alapvető kapcsolatokat ellenőrizzük:

Közzétéve: http://www.allbest.ru/

Válasz: x 1 = , x 2 =, y 1 = , y 2 = , y 3 =0, y 4 =0,.

Barna módszer

Egy adott cég dolgozóinak kérésére a szakszervezet tárgyal a vezetőségével a meleg ebéd megszervezéséről a cég költségére. A dolgozókat képviselő szakszervezet azt szeretné elérni, hogy az ebéd minél minőségibb legyen, és ezáltal drágább legyen. A cégvezetésnek ellentétes érdekei vannak. A felek végül a következőkben állapodtak meg. A szakszervezet (1. játékos) három meleg ételt szállító cég (A 1, A 2, A 3) közül választ egyet, a cégvezetés (2. játékos) pedig három lehetséges ételkészlet közül (B 1, B 2) választ. , B 3) . A szerződés aláírása után a szakszervezet az alábbi fizetési mátrixot állítja elő, melynek elemei egy étkészlet költségét jelentik:

Határozzuk meg a játékot a következő kifizetési mátrix segítségével:

Tegyük fel, hogy a második játékos a 2. stratégiáját választotta, akkor az első a következőket kapja:

2, ha az első stratégiáját használja,

3, ha a 3. stratégiáját használja.

A kapott értékeket az 1. táblázat foglalja össze.

3. táblázat. A második játékos stratégiája

Tétel száma	2. játékos stratégia	1. játékos nyer

A 3. táblázatból látható, hogy a második játékos 2. stratégiájával az első kapja a legnagyobb nyereményt 3 a 2. vagy 3. stratégiájával. Mivel az első játékos a maximális győzelmet akarja elérni, a második játékos 2. stratégiájára a 2. stratégiájával válaszol. Az első játékos 2. stratégiájával a második elveszíti:

1, ha az 1. stratégiáját használja,

3, ha a 2. stratégiáját használja,

4, ha a 3. stratégiáját használja.

4. táblázat: Első játékos stratégia

Tétel száma	1. játékos stratégia	A 2. játékos veszít

A 2. táblázatból látható, hogy az első játékos 2. stratégiájával a második játékosnak lesz a legkisebb vesztesége 1, ha az 1. stratégiáját alkalmazza. Mivel a második játékos kevesebbet akar veszíteni, az első játékos 2. stratégiájára válaszul az 1. stratégiáját fogja használni. A kapott eredményeket az 5. táblázat foglalja össze.

5. táblázat. Az első és a második játékos stratégiája

Tétel száma

2. játékos stratégia

Az 1. játékos teljes nyereménye

1. játékos stratégia

táblázatban 5 a második sorban lévő második játékos stratégia oszlopában egy 1-es szám található, ami azt jelzi, hogy a második játékban előnyös, ha a második játékos az 1. stratégiáját használja; az oszlopban az első játékos legnagyobb átlagos nyerő 3-a látható, amelyet az első játékban kapott; A w oszlop tartalmazza a második játékos által az első játszmában elszenvedett legkisebb átlagos 1-es veszteséget; az v oszlop a v = (u + w) számtani átlagot tartalmazza - azaz a játék egy játékának elvesztése következtében kapott játékár hozzávetőleges értékét. Ha a második játékos az 1. stratégiáját alkalmazza, akkor az első játékos 3, 1, 2-t kap az 1., 2. és 3. stratégiájával, és az első játékos össznyeresége mindkét játékban:

2 + 3=5 az első stratégiájával,

3 + 1=4 a 2. stratégiájával,

3 + 2=5 a 3. stratégiájával.

Ezek a teljes nyeremények a táblázat második sorában vannak rögzítve. 3 és az első játékos stratégiáinak megfelelő oszlopokban: 1, 2, 3.

Az összes nyeremény közül a legnagyobb az 5. Ezt az első játékos 1. és 3. stratégiájával szerzi meg, majd bármelyiket választhatja; Mondjuk ilyen esetekben, amikor két (vagy több) egyforma össznyeremény van, a legalacsonyabb számmal rendelkező stratégiát válasszuk (esetünkben az 1. stratégiát kell választanunk).

Az első játékos 1. stratégiájával a második 3-at, 2-t, 3-at veszít az 1., 2. és 3. stratégiájával szemben, és a második játékos teljes vesztesége mindkét játékban:

1 + 3=4 az első stratégiájával,

3 + 2=5 a 2. stratégiájával,

4 + 3=7 a 3. stratégiájával.

Ezeket a teljes veszteségeket a táblázat második sorában rögzítjük. 5. és a második játékos 1., 2., 3. stratégiájának megfelelő oszlopokban.

A második játékos összes vesztesége közül a legkisebb a 4. Ezt az 1. stratégiájával kapja, ezért a harmadik játékban a második játékosnak kell alkalmaznia az 1. stratégiáját. Az oszlopba kerül az első játékos két játék során elért legnagyobb össznyeresége, osztva a játékok számával, azaz; A w oszlop tartalmazza a második játékos legkisebb teljes veszteségét két játszma alatt, osztva a játszmák számával, azaz ; az v oszlopba ezeknek az értékeknek a számtani középértéke kerül, azaz = Ez a szám a két „lejátszott” játék árának hozzávetőleges értéke.

Így a következő 4. táblázatot kapjuk két játékra.

6. táblázat: A játékosok összesített nyereményei és veszteségei két lejátszott játék után

2. játékos stratégia

Az 1. játékos teljes nyereménye

1. játékos stratégia

A 2. játékos teljes elvesztése

A 6. táblázat harmadik sorában a második játékos stratégia oszlopában egy 1-es szám található, ami azt jelzi, hogy a harmadik játékban a második játékosnak az 1. stratégiáját kell alkalmaznia. Ebben az esetben az első játékos nyer 3-at, 1-et, 2-t, az 1., 2. és 3. stratégiáját alkalmazva, és a három játék során elért össznyeresége:

3 + 5 = 8 az első stratégiájával,

1 +4 = 5 a második stratégiájával,

2 + 5 = 7 a 3. stratégiájával.

Az első játékos összesített nyereményét a 6. táblázat harmadik sorában és az 1., 2., 3. stratégiájának megfelelő oszlopokban rögzítjük. Mivel az első játékos 8. legnagyobb nyereményét az 1. stratégiával kapjuk, az 1. kerül kiválasztásra. Eszerint.

Az első játékos 1. stratégiájával a második 3-at, 1-et, 2-t veszít az 1., 2. és 3. stratégiájával szemben, és a második játékos teljes vesztesége mindkét játékban:

3 + 4=7 az első stratégiájával,

2 + 5=7 a 2. stratégiájával,

3 + 7 = 10 a 3. stratégiájával.

Ezeket a teljes veszteségeket a táblázat harmadik sorában rögzítjük. 6. és a második játékos 1., 2., 3. stratégiájának megfelelő oszlopokban. Az összes vesztesége közül 7 a legkisebb, és az 1. és 2. stratégiájával éri el, majd a második játékosnak kell alkalmaznia az 1. stratégiáját.

táblázatban 6 az oszlop harmadik sorában, és rögzíti az első játékos három játék során elért legnagyobb össznyereményét, osztva a játék számával, azaz; a w oszlopban a második játékos legkisebb összesített vesztesége kerül elhelyezésre három játszmán keresztül, osztva a játszmák számával, azaz; A v oszlop a számtani középértéküket tartalmazza

Így kapunk asztalt. 7 három meccsre.

7. táblázat: A játékosok összesített nyereményei és veszteségei három lejátszott meccs után

Tétel száma

2. játékos stratégia

Az 1. játékos teljes nyereménye

1. játékos stratégia

A 2. játékos teljes elvesztése

8. táblázat: Döntő asztal húsz lejátszott meccs után

Tétel száma

2. játékos stratégia

Az 1. játékos teljes nyereménye

1. játékos stratégia

A 2. játékos teljes elvesztése

Az asztalról A 7. és 8. ábrán látható, hogy 20 elvesztett játszmában az 1., 2., 3. stratégia az első játékosnál rendre 12, 3, 5 alkalommal fordul elő, így ezek relatív gyakorisága rendre egyenlő; az 1., 2., 3. stratégiák a második játékosnál rendre 7, 11,2 alkalommal fordulnak elő, ezért relatív gyakoriságuk rendre egyenlő; a játék hozzávetőleges ára. Ez a közelítés elég jó.

Végül vegye figyelembe, hogy ha egy játéknak több megoldása van, akkor a játék költségének becslései továbbra is meghatározhatatlanul megközelítik a játék valódi költségét, és a játékosok stratégiáinak relatív gyakorisága már nem feltétlenül közelíti meg a játékosok valódi optimális értékét. vegyes stratégiák.

Az eredmények elemzése

Ebben a kurzusmunkában a nulla összegű játékok megoldásának anyagát tanulmányoztuk grafikus, mátrixos módszerrel, valamint a játék árának egymás utáni közelítésének módszerével. Megtalálták az első és második játékos optimális stratégiáját, valamint a 2x2, 2xn és mx2 játékokban, valamint a mátrix módszert és Brown módszert alkalmazó játékokban a játék költségeit.

Egy pár példájával szimuláltam egy 2x2-es játékot, amelyet algebrai és grafikus módszerekkel oldottak meg. A játék algebrai megoldásával a megoldás azt mutatja, hogy optimális vegyes stratégiájukat alkalmazva az első és a második játékos 4,6 órát tölt együtt. A probléma grafikus megoldását kis hibával kaptuk meg, és 4,5 órát tett ki.

És két 2xn és mx2 problémát is szimuláltak. A 2xn. feladatban egy mezőgazdasági növényt vettek figyelembe, és a stratégia azt mutatja, hogy jobb 50-50 táblát ültetni, és a játék ára 3,75 millió rubel volt. Az mx2 problémában pedig egy párat vettek figyelembe, akiknek stratégiája azt mutatta, hogy olcsóbb a parkba és moziba menni, és a költség 4,3 rubel lesz.

A mátrix módszerre modelleztem egy problémát, amelyben két éttermet vettek figyelembe, a probléma megoldása azt mutatta, hogy optimális vegyes stratégiáját alkalmazva az első étterem profitja 15,6 millió rubel lesz, az optimális vegyes stratégiát alkalmazva pedig kb. a második étterem nem teszi lehetővé, hogy az első 15,6 millió rubelnél többet keressen. A grafikus megoldás hibát eredményezett és a játék ára 14,9 millió rubel lett.

Brown módszeréhez egy feladatot fogalmaztak meg, amelyben a szakszervezetet és a cégvezetést veszik figyelembe, az ő feladatuk a dolgozók élelmezése. Ha mindkét játékos az optimális stratégiáját használja, az egy főre jutó étel 2,45 ezer rubel lesz.

A felhasznált források listája

1) Vilisov V.Ya. Előadásjegyzet „Játékelmélet és statisztikai döntések”, - Ágazat - „Voskhod” MAI. 1979. 146 p.

2) Krushevsky A.V. Játékelmélet, - Kijev: Vishcha School, 1977. - 216 p.

3) Churchmen U., Akof R., Arnof L., Bevezetés a műveletek kutatásába. - M.: Tudomány. 1967. - 488 p.

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

Közzétéve az Allbest.ru oldalon

Hasonló dokumentumok

A döntéshozatal, mint az emberi tevékenység sajátos fajtája. A játékmátrix racionális ábrázolása. Példák mátrixjátékokra tiszta és vegyes stratégiákban. Operációkutatás: lineáris programozási problémák kapcsolata játékelméleti modellel.

tanfolyami munka, hozzáadva 2010.05.05


Sokszor ismétlődő játékok, jellegzetes tulajdonságaik és szakaszaik. Vegyes stratégiák, gyakorlati felhasználásuk feltételei és lehetőségei. Analitikai módszer 2 x 2 típusú játék megoldására. Alaptételek téglalap alakú játékokhoz. Algebrai megoldások.

bemutató, hozzáadva 2013.10.23


A bimátrix játékok elméletének alapdefiníciói. Példa a „Diák-Tanár” bimátrix játékra. Vegyes stratégiák bimátrixos játékokban. Keressen egy „egyensúlyi helyzetet”. 2x2 bimátrixos játékok és képletek arra az esetre, amikor minden játékosnak két stratégiája van.

absztrakt, hozzáadva: 2011.02.13


Tanuljon meg általános információkat a mátrixos és nulla összegű játékokról. A helyzeti játék fogalma, fa, információs halmaz. A maximin elv és az egyensúlyi elv figyelembevétele. Pareto optimalitás. Pozicionális nem antagonisztikus játék, tulajdonságai.

tanfolyami munka, hozzáadva 2014.10.17


A játékelmélet a matematikának egy olyan ága, amelynek tárgya a konfliktushelyzetekben optimális döntések meghozatalára szolgáló matematikai modellek tanulmányozása. Iteratív Brown-Robinson módszer. Egy monoton iteratív algoritmus mátrixjátékok megoldására.

szakdolgozat, hozzáadva: 2007.08.08


Fizetési mátrix készítése, a játék alsó és felső nettó árának, a játékosok maximin és minimax stratégiáinak felkutatása. A fizetési mátrix egyszerűsítése. Mátrixjáték megoldása lineáris programozási feladatra való redukcióval és a „Megoldás keresése” kiegészítővel.

teszt, hozzáadva: 2014.11.10


A játékelmélet a konfliktushelyzetek matematikai elmélete. Kétszemélyes nulla összegű játék matematikai modelljének kidolgozása, megvalósítása programkódok formájában. A probléma megoldásának módja. Bemeneti és kimeneti adatok. Program, használati útmutató.

tanfolyami munka, hozzáadva 2013.08.17


Alapvető tudnivalók a szimplex módszerről, szerepének és jelentőségének felmérése a lineáris programozásban. Geometriai értelmezés és algebrai jelentés. Lineáris függvény maximumának és minimumának megtalálása, speciális esetek. A feladat megoldása mátrix szimplex módszerrel.

szakdolgozat, hozzáadva: 2015.06.01


Számítógépes rendszerek matematikai modelljeinek felépítésének technikái, amelyek tükrözik működésük szerkezetét és folyamatait. A fájlhozzáférések száma egy átlagos probléma megoldása során. Fájlok külső memóriameghajtókba helyezésének lehetőségének meghatározása.

labormunka, hozzáadva 2013.06.21


Matematikai modell tervezése. A tic-tac-toe játék leírása. Logikai játék modellje Boole-algebrán. Digitális elektronikai eszközök és matematikai modelljük fejlesztése. Játékkonzol, játékvezérlő, játék mezővonal.

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 jelöljü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.

Moszkvai Energiaintézet

(Technikai Egyetem)

Laborjelentés

játékelméletben

„Program optimális stratégiák megtalálására egy páros, nulla összegű játékhoz, mátrix formában”

Diákok végezték el

csoport A5-01

Ashrapov Daler

Ashrapova Olga

Játékelméleti alapfogalmak

A játékelméletet a megoldásra tervezték konfliktushelyzetek , azaz olyan helyzetek, amikor két vagy több, különböző célokat követő fél érdekei ütköznek.

Ha a felek céljai közvetlenül ellentétesek, akkor arról beszélnek antagonisztikus konfliktus .

Játszma, meccs a konfliktushelyzet egyszerűsített formalizált modelljének nevezzük.

A játék egyetlen játékát az elejétől a végéig hívják buli . A játék eredménye az fizetés (vagy nyeremények ).

A buli a következőkből áll mozog , azaz a játékosok választása a lehetséges alternatívák bizonyos halmazából.

A mozdulatok lehetnek személyesÉs véletlen.Személyes lépés , Nem úgy mint véletlen , magában foglalja a játékos tudatos választását valamilyen lehetőség közül.

Azokat a játékokat hívják, amelyekben legalább egy személyes lépés van stratégiai .

Olyan játékokat hívnak, amelyekben minden lépés véletlenszerű szerencsejáték .

Személyes lépések megtételekor arról is beszélnek stratégiákat játékos, azaz egy szabályról vagy szabályrendszerről, amely meghatározza a játékos választását. A stratégiának ugyanakkor átfogónak kell lennie, pl. a választást a játék során esetlegesen előforduló helyzetekre kell meghatározni.

Játékelméleti probléma– optimális stratégiák megtalálása a játékosok számára, pl. olyan stratégiákat, amelyek maximális nyereséget vagy minimális veszteséget biztosítanak számukra.

A játékelméleti modellek osztályozása

Játszma, meccs n a személyeket általában hol, hol jelölik
- az i-edik játékos stratégiáinak összessége,
- fizetés a játékért.

Ezzel a megjelöléssel összhangban a játékelméleti modellek következő osztályozása javasolható:

Diszkrét (több stratégia diszkrét)

Végső

Végtelen

Folyamatos (több stratégia folyamatos)

Végtelen

n személyek (
)

koalíció (szövetkezet)

Nem koalíció (nem együttműködő)

2 fő (pár)

Antagonisztikus (nulla összegű játékok)

(a felek érdekei ellentétesek, azaz az egyik játékos vesztesége egyenlő a másik nyereségével)

Nem antagonisztikus

Teljes információval (ha a személyes lépést végrehajtó játékos ismeri a játék teljes hátterét, azaz az ellenfél összes lépését)

Hiányos információkkal

Nulla összeggel (a teljes kifizetés nulla)

Nem nulla összeg

Egy mozdulat (lottók)

Több passz

Egy páros nulla összegű játék mátrixábrázolása

Ebben az oktatóanyagban megnézzük kétszemélyes antagonisztikus játékok , mátrix formában megadva. Ez azt jelenti, hogy ismerjük az első játékos (játékos A){ A én }, én = 1,…, més különféle stratégiák a második játékos számára (játékos B){ B j }, j = 1,..., n, és adott a mátrix is A = || a ij || az első játékos nyereménye. Mivel antagonista játékról beszélünk, feltételezzük, hogy az első játékos nyeresége megegyezik a második veszteségével. Feltételezzük, hogy a mátrix elem a ij– az első játékos nyereménye, amikor stratégiát választ A énés a második játékos válasza rá egy stratégiával B j. Az ilyen játékot így fogjuk jelölni
, Ahol m - játékos stratégiák száma A,n - játékos stratégiák száma BAN BEN.Általában a következő táblázattal ábrázolható:

	B 1		B j		B n
A 1
A én
A m

1. példa

Egyszerű példaként vegyünk egy játékot, amelyben egy játék két lépésből áll.

1. lépés: Játékos A kiválaszt egyet a számok közül (1 vagy 2), anélkül, hogy tájékoztatná az ellenfelét a választásáról.

2. lépés: Játékos BAN BEN kiválaszt egyet a számok közül (3 vagy 4).

A lényeg: A játékosok választása AÉs BAN BEN hajtsa fel. Ha az összeg páros, akkor BAN BEN kifizeti értékét a játékosnak A, ha páratlan - fordítva, A kifizeti az összeget a játékosnak BAN BEN.

Ezt a játékot formában lehet bemutatni
a következő módon:

	(3. választás)	(4-es választás)
(1. választás)
(2. választás)

Könnyen belátható, hogy ez a játék antagonisztikus, ráadásul hiányos információkat tartalmazó játék, mert a játékosnak BAN BEN, személyes lépést végrehajtva nem ismert, hogy a játékos milyen döntést hozott A.

Ahogy fentebb is jeleztük, a játékelmélet feladata a játékosok optimális stratégiáinak megtalálása, pl. olyan stratégiákat, amelyek maximális nyereséget vagy minimális veszteséget biztosítanak számukra. Ezt a folyamatot ún játék megoldás .

Amikor egy játékot mátrix formában old meg, ellenőrizze a játék jelenlétét nyeregpont . Ehhez két értéket kell megadni:

– alacsonyabb becslés a játék árára és

– a játék árának felső becslése.

Az első játékos nagy valószínűséggel azt a stratégiát választja, amelyben a második játékos összes lehetséges válasza közül a legnagyobb győzelmet kapja, a második játékos pedig éppen ellenkezőleg, azt a stratégiát választja, amely minimalizálja saját veszteségét, azaz. az első lehetséges megnyerése.

Ez bizonyítható α ≤ V ≤ β , Ahol V–játék ára , azaz az első játékos valószínű győzelme.

Ha az összefüggés fennáll α = β = V, akkor azt mondják a játéknak van nyeregpontja
, És tiszta stratégiákkal megoldható . Más szóval, van néhány stratégia
, így a játékos AV.

2. példa

Térjünk vissza az 1. példában vizsgált játékhoz, és ellenőrizzük, hogy van-e nyeregpont.

	(3. választás)	(4-es választás)
(1. választás)
(2. választás)

Ehhez a játékhoz
= -5,
= 4,
, ezért nincs nyereghegye.

Ismételten felhívjuk a figyelmet arra, hogy ez a játék egy játék hiányos információkkal. Ebben az esetben csak tanácsot tudunk adni a játékosnak A válassz egy stratégiát , mert ebben az esetben azonban ő szerezheti meg a legnagyobb győzelmet, a játékos választásától függően BAN BEN stratégiákat .

3. példa

Végezzünk néhány változtatást a játékszabályokon az 1. példából. Mi biztosítjuk a játékost BAN BEN játékos kiválasztási információk A. Akkor legyen BAN BEN két további stratégia jelenik meg:

- a számára előnyös stratégia A. Ha a választás A-1, Hogy BAN BEN 3-at választ, ha választ A-2, Hogy BAN BEN választja a 4-et;

- olyan stratégia, amely számára nem előnyös A. Ha a választás A-1, Hogy BAN BEN 4-et választ, ha választ A-2, Hogy BAN BEN választja a 3.

	(3. választás)	(4-es választás)
(1. választás)
(2. választás)

Ez a játék teljes körű információval rendelkezik.

Ebben az esetben
= -5,
= -5,
, ezért a játéknak van nyeregpontja
. Ez a nyeregpont két optimális stratégiának felel meg:
És
. A játék ára V= -5. Nyilvánvaló, hogy azért A egy ilyen játék veszteséges.

A 2. és 3. példa jól illusztrálja a következő, a játékelméletben bizonyított tételt:

1. tétel

Minden párosított antagonisztikus játék teljes információval megoldható tiszta stratégiákkal.

Hogy. Az 1. tétel azt mondja, hogy minden teljes információval rendelkező kétjátékos játéknak van nyeregpontja, és van egy pár tiszta stratégia.
, így a játékos A fenntartható nyeremény, amely megegyezik a játék árával V.

Nyeregpont hiánya esetén az ún vegyes stratégiák :, Ahol p én Ésq j– a stratégiák kiválasztásának valószínűsége A én És B j az első és a második játékos. A játék megoldása ebben az esetben egy pár vegyes stratégia
, maximalizálva a játék árának matematikai elvárását.

A következő tétel általánosítja az 1. tételt egy hiányos információt tartalmazó játék esetére:

2. tétel

Bármely páros antagonisztikus játéknak van legalább egy optimális megoldása, azaz általános esetben egy pár vegyes stratégia
, így a játékos A fenntartható nyeremény, amely megegyezik a játék árával V, és α ≤ V ≤ β .

Speciális esetben egy nyeregpontos játéknál a vegyes stratégiák megoldása olyan vektorpárnak tűnik, amelyben az egyik elem egyenlő eggyel, a többi pedig nullával.

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.