Antagonisztikus mátrixos játékok. Mátrixjáték megoldása Antagonisztikus mátrixjátékok

A játékelmélet alapfeltevésként azt feltételezzük, hogy minden játékos arra törekszik, hogy partnere bármely cselekedetével a lehető legnagyobb nyereményt biztosítsa magának. Tegyük fel, hogy létezik egy véges nulla összegű játék az első játékos kifizetési mátrixával és ennek megfelelően a második játékos kifizetési mátrixával. Higgye el az 1. játékos, hogy bármilyen stratégiát is választ, a 2. játékos azt a stratégiát választja, amely maximalizálja a nyereményét, és ezáltal minimalizálja az 1. játékos nyereményét.

Tehát az 1. játékos választ én

A 2. játékos arra is törekszik, hogy az ellenfél által választott stratégiától függetlenül a legnagyobb nyereményt (vagy ennek megfelelően a legkisebb veszteséget) biztosítsa. Optimális stratégiája az oszlop lenne H 0 a legalacsonyabb maximális fizetéssel. Tehát a 2. játékos választ j-th stratégia, amely megoldást jelent a problémára

Ennek eredményeként, ha az 1. játékos követi a választott stratégiát (úgynevezett maximal stratégia ), a kifizetése minden esetben kisebb lesz, mint a maximális érték (hívják "a játék alsó ára" ), azaz

Ennek megfelelően, ha a 2. játékos betartja a minimax stratégiáját, akkor vesztesége nem lesz nagyobb, mint a maximális érték (ún. "A játék legjobb ára" ), azaz

Abban az esetben, ha a játék felső ára megegyezik az alsó árral, pl. = , mindkét játékos megkapja garantált kifizetését, és az értéket h ij * hívott a játék árán .

Mátrix elem h ij a stratégiáknak megfelelő kifizetési mátrixot nevezzük a mátrix nyeregpontja N.

Ha az antagonisztikus játék költsége 0, a játék hívásra kerül becsületes .

Vegyünk egy olyan játékot, amelyben az 1. játékosnak két stratégiája van, a 2. játékosnak pedig három. Az 1. játékos kifizetési mátrixa így néz ki:

Megjegyzés . Mivel egy nulla összegű játékra gondolunk, a 2. játékos kifizetési mátrixa N2 = -H1.

Az 1. játékos kiszámítja, hogy ha az első stratégiát választja (azaz a mátrix első sorát H 1), akkor az ellenfél a második stratégiáját választja (azaz a második oszlopot), hogy a nyeremény egyenlő legyen 1 . Ha a második stratégiát választja, akkor az ellenfél választhatja az első stratégiát, így a nyeremény egyenlő lesz -1.

A kapott értékek elemzése után: Az 1. játékos beleegyezik az első stratégiájába, amely 1-gyel egyenlő maximális garantált győzelmet biztosít számára.

Hasonlóképpen, a 2. játékos a legrosszabb lehetőségeit mérlegeli, amikor az ellenfél az első vagy a második stratégiát választja, vagy amikor az ellenfél a második stratégiát választja, amikor a 2. játékos a harmadik oszlopot választja. Ezek az opciók a 2., 1. és 6. oszlop maximális értékeinek felelnek meg.

Ezeknek a maximumoknak a minimális értékeit figyelembe véve a 2. játékos a második stratégiáját választja, amelyben a vesztesége minimális és egyenlő:

Következésképpen ebben a játékban vannak közös stratégiák, azok. E

Ezért ebben a játékban ésszerű elvárni az ellenfelektől, hogy ragaszkodjanak a választott stratégiájukhoz. Egy mátrix antagonista játék, amelyhez - teljesen határozott játéknak hívják, vagy olyan játéknak, amelynek tiszta stratégiákban van megoldása.

Azonban nem minden mátrix antagonista játék jól definiált.

Azokat a játékokat, amelyekben szigorú egyenlőtlenség érvényesül, nem teljesen meghatározott játékoknak nevezzük (vagy olyan játékoknak, amelyeknek nincs megoldása tiszta stratégiákban).

Nézzünk egy példát erre a játékra:

Ehhez a játékhoz.

Ennek eredményeként, ha a játékosok betartják a fent javasolt szabályokat, akkor az 1. játékos az 1. stratégiát választja, és elvárja, hogy a 2. játékos válassza a 2. stratégiát, ahol a veszteség -2, míg a 2. játékos a 3. stratégiát választja, és azt várja, hogy az 1. válasszon 2-es stratégiát úgy, hogy a nyeremény 4 legyen.

Ha azonban a 2. játékos a harmadik stratégiáját választja, akkor az 1. játékos jobban tenné, ha a második stratégiát választaná az első stratégia helyett. Hasonlóképpen, ha az 1. játékos az első stratégiát választja, a 2. játékos jobban jár, ha a második stratégiát választja a harmadik helyett. Úgy tűnik, az alattomos típusú játékokban a tiszta stratégiákban alkalmazott megoldási elv alkalmatlannak bizonyul.

A leírt helyzetben a játékosok számára válik fontossá, hogy az ellenség ne találja ki, milyen stratégiát fog alkalmazni. A terv megvalósításához a játékosoknak az úgynevezett vegyes stratégiát kell alkalmazniuk.

Lényegében a játékos vegyes stratégiája egy tiszta stratégia véletlenszerű kiválasztására szolgáló séma. Matematikailag egy adott játékos tiszta stratégiáinak halmazán való valószínűségi eloszlásként ábrázolható. Ennek eredményeként a vektor, ahol annak a valószínűsége, hogy az 1. játékos alkalmazza a stratégiát és a , adja meg ennek a játékosnak a vegyes stratégiáját. A 2. játékos vegyes stratégiája hasonlóképpen határozható meg .

Feltételezzük, hogy a játékosok vegyes stratégiáik használata független, így annak a valószínűsége, hogy az 1. játékos ezt a stratégiát választja, és a 2. játékos választja, egyenlő . Ebben az esetben fizetés. Összegezve és -t, megkapjuk az 1. játékos nyereményének matematikai elvárását:

vagy mátrix jelöléssel

Vegyes stratégiák halmaza esetén az 1. játékos, aki a garantált nyeremény közül a legnagyobbat akarja elérni, kiválaszt egy valószínűségi vektort, hogy megkapja a várható nyeremények minimális értékeinek maximumát, pl. megoldja a problémát:

.

Hasonlóképpen a 2. játékos célja az, hogy elérje veszteségei minimális maximális értékét, pl. megoldja a problémát

.

A játékelmélet alapvető eredménye az ún. Minimax tétel, amely kimondja, hogy az 1. és 2. játékos megfogalmazott problémáinak mindig van megoldása bármilyen kifizetési mátrixra, ráadásul .

Ami a jól definiált játékokat illeti, az 1. játékos stratégiáját ún Maximin stratégia , 2. játékos stratégia - minimax stratégia, érték - a játék költségén ; abban az esetben, ha a játékot fairnek nevezik.

A Minimax-tétel nyilvánvaló következménye a következő összefüggés:

.

ami azt jelenti, hogy az 1. játékos egyetlen stratégiája sem teszi lehetővé számára, hogy a játék áránál nagyobb összeget nyerjen, ha a 2. játékos alkalmazza a minimax stratégiáját, és a 2. játékos egyetlen stratégiája sem engedi meg számára, hogy a játék áránál kisebb összeget veszítsen. ha az 1. játékos alkalmazza maximin stratégiáját.

Ez igaz a tiszta stratégiákra is, mint a vegyes stratégiák speciális esetére. (Mert a tiszta stratégia 1-es valószínűséggel használt stratégia): Bármilyen tiszta stratégia használata, ha az ellenfél az optimális stratégiáját használja, nem teszi lehetővé, hogy többet nyerjen (kevesebbet veszítsen), mint amennyi a játék költsége.

Ezt a tényt gyakran használják specifikus algoritmusok kidolgozására az antagonisztikus mátrixjátékok megoldására.

Az optimális stratégiák kiszámítása a stratégiák számának növekedésével sokkal nehezebbé válik. Többféle megközelítés is használható az optimális stratégia megtalálásához.

A játék méretének csökkentésére sor- és oszlopdominanciát használnak. Általában azt mondják, hogy a mátrix i-edik sora uralja az i-edik sort (vagyis az egyik tiszta sor uralja a másikat), ha az összes , legalább egy .

Hasonlóképpen, a th oszlop uralja a th oszlopot, ha az összes , legalább egy .

Ennek a definíciónak az a lényege, hogy a domináns stratégia soha nem rosszabb, sőt bizonyos esetekben még jobb is, mint a domináns stratégia. Ezért a fontos következtetés az, hogy a játékosnak nem kell dominált stratégiát alkalmaznia. Ez a gyakorlatban lehetővé teszi az összes dominált sor és oszlop elvetését, ami csökkenti a mátrix méretét (megjegyezzük, hogy ez a megközelítés akkor is használható, ha tiszta stratégiákban keresünk megoldást).

Példa. Tekintsünk egy játékot a következő mátrixszal:

A második sor kiiktatása mátrixot eredményez: Ebben a levágott mátrixban a harmadik oszlopot a második uralja, a második oszlop elhagyása pedig: .

Ennek eredményeként, ha az eredményül kapott játékra sikerül megoldást találni, akkor az egyszerűen használható az eredeti játék megoldására, egyszerűen nulla valószínűséget rendelve a kizárt sorokhoz és oszlopokhoz.

A mátrix egyszerűsítésének másik módja azon a tulajdonságon alapul, hogy a kifizetési mátrix affin transzformációja (azaz a mátrix összes elemének átalakítása a szabály szerint, ahol ) nem változtatja meg a játék megoldását; ráadásul az átváltott játék ára az eredeti játék árából is megkapható ugyanezen szabály szerint: . Ez azt jelenti, hogy a játék feladatához elvileg nem mindegy, hogy a nyereményt milyen egységekben mérik (rubelben vagy dollárban), hanem valamilyen fix összeg hozzáadásával (levonásával) az egyes játékosok nyereményét (veszteségét) a ugyanannyit a játék megoldásának megváltoztatása nélkül.

Ez a tulajdonság használható a kifizetési mátrix egyszerűsítésére és világosabbá tételére (a mátrixokkal végzett műveletekkel analóg módon használva - mátrix szorzása állandó számmal, sorok összeadása és kivonása, emellett ez a tulajdonság lehetővé teszi bármilyen mátrix nulla összegű játék elkészítését korrekt, ehhez ki kell számítani az árjátékokat a kifizetési mátrix összes eleméből).

Ezen kívül grafikus módszerrel is megoldható a játék (és általában a játékok).

Például a kifizetési mátrix így néz ki: .

Hagyja, hogy az 1. játékos válassza ki első stratégiáját valószínűséggel, a másodikat pedig valószínűséggel. Ha a 2. játékos az első stratégiáját választja, akkor (a mátrix első oszlopából) az 1. játékossal szembeni elvárás a következő lesz. Ha a 2. játékos a második stratégiáját választja, akkor a mátrix második oszlopának megfelelően: .

Ezen egyenletek mindegyike grafikusan ábrázolható egy egyenes szegmenssel a grafikonon a koordinátákkal és koordinátákkal.

Tesztek a végső ellenőrzéshez

1. Antagonisztikus játék állítható be:

a) stratégiakészlet mindkét játékos számára és egy nyeregpont.

b) stratégiakészlet mindkét játékos számára és az első játékos kifizetési funkciója.

2. A játék ára mindig létezik a vegyes stratégiájú mátrixos játékoknál.

a) igen.

3.Ha a kifizetési mátrix minden oszlopa azonos, és alakja (4 5 0 1), akkor milyen stratégia az optimális az 1. játékos számára?

a) először.

b) második.

c) a négy közül bármelyik.

4. Egy mátrixos játékban az 1. játékos egyik vegyes stratégiájának formája legyen (0,3, 0,7), a 2. játékos egyik vegyes stratégiájának pedig (0,4, 0, 0,6) alakja legyen. Mi ennek a mátrixnak a dimenziója?

a) 2*3.

c) egy másik dimenzió.

5. A dominancia elve lehetővé teszi, hogy egy lépésben eltávolítsa a mátrixból:

a) egész sorokat.

b) egyedi számok.

6. A 2*m-es játékok grafikus megoldásánál közvetlenül a grafikonról találjuk:

a) mindkét játékos optimális stratégiája.

b) a játék ára és a 2. játékos optimális stratégiái.

c) a játék ára és az 1. játékos optimális stratégiái.

7. A 2*m-es játékok grafikus megoldásának alsó borítékának grafikonja általános esetben:

a) törött.

b) egyenes.

c) parabola.

8. Egy 2*2-es mátrixos játékban a játékos vegyes stratégiájának két összetevője van:

a) meghatározzák egymás értékeit.

b) független.

9. Egy mátrixjátékban az aij elem:

a) az 1. játékos nyereménye, ha az i-edik stratégiát használja, a 2. játékos pedig a j-edik stratégiát.

b) az 1. játékos optimális stratégiája, ha az ellenfél az i-edik vagy a j-edik stratégiát használja.

c) az 1. játékos elvesztése, amikor a j-edik stratégiát használja, a 2. játékos pedig az i-edik stratégiát használja.

10.Az aij mátrixelem a nyeregpontnak felel meg. A következő helyzetek lehetségesek:

a) ez az elem szigorúan a legkisebb a sorban.

b) ez az elem a második sorrend a sorban.

11. A Brown-Robinson módszerben minden játékos a következő lépésben stratégiát választva a következőket vezérli:

a) az ellenség stratégiái az előző lépéseknél.

b) stratégiáit az előző lépésekben.

c) valami más.

12. A matematikai elvárás kritériuma szerint minden játékos abból indul ki, hogy:

a) a számára legrosszabb helyzet fog bekövetkezni.

c) adott valószínűséggel minden vagy néhány helyzet lehetséges.

13. Adjon meg egy mátrixjátékot egy olyan mátrix, amelyben minden elem negatív. A játék ára pozitív:

b) nem.

c) nincs egyértelmű válasz.

14. A játék ára:

egy szám.

b) vektor.

c) mátrix.

15. Maximum hány nyeregpont lehet egy 5*5 méretű játékban (a mátrix bármilyen számot tartalmazhat):

16. Egy 2*3 dimenziójú mátrixjátékban az 1. játékos egyik vegyes stratégiájának formája legyen (0.3, 0.7), a 2. játékos egyik vegyes stratégiájának pedig (0.3, x, 0.5) alakja legyen. . Mi az x szám?

c) másik szám.

17. A játékmátrix melyik dimenziójára válik a Wald-kritérium Laplace-kritériummá?

c) csak más esetekben.

18. A játék felső ára mindig alacsonyabb, mint a játék alsó ára.

b) nem.

b) a kérdés helytelen.

19. Milyen stratégiák vannak egy mátrixjátékban:

a) tiszta.

b) vegyes.

c) mindkettő.

20. Valamelyik antagonisztikus játékban mindkét játékos kifizetési függvényének értéke a változók egyes értékeire egyenlő lehet 1-gyel?

a) mindig.

b) néha.

c) soha.

21. Mátrixjátékban az 1. játékos egyik vegyes stratégiája legyen (0,3, 0,7), a 2. játékos egyik vegyes stratégiája pedig (0,4, 0,1, 0,1, 0,4) alakú. . Mi ennek a mátrixnak a dimenziója?

c) egy másik dimenzió.

22. A dominancia elve lehetővé teszi, hogy egy lépésben eltávolítsuk a mátrixból:

a) egész oszlopok,

b) egyedi számok.

c) kisebb méretű részmátrixok.

23. Egy 3*3-as mátrixos játékban a játékos vegyes stratégiájának két összetevője van:

a) határozza meg a harmadikat.

b) ne határozza meg.

24. Egy mátrixjátékban az aij elem:

a) a 2. játékos elvesztése, amikor a j-edik stratégiát használja, és a 2. - az i-edik stratégia.

b) a 2. játékos optimális stratégiája, ha az ellenfél az i-edik vagy a j-edik stratégiát alkalmazza,

c) az 1. játékos nyereményét, amikor a j-edik stratégiát alkalmazza, és a 2. - az i-edik stratégiát,

25. Az aij mátrixelem a nyeregpontnak felel meg. A következő helyzetek lehetségesek:

a) ez az elem a legnagyobb az oszlopban.

b) ez az elem szigorúan a legnagyobb sorrendben.

c) a karakterlánc ennél az elemnél nagyobb és kisebb elemeket is tartalmaz.

26. A Wald-kritérium szerint minden játékos feltételezi, hogy:

a) a számára legrosszabb helyzet fog bekövetkezni.

b) minden helyzet egyformán lehetséges.

c) adott valószínűséggel minden helyzet lehetséges.

27. Az alsó ár alacsonyabb, mint a játék felső ára:

b) nem mindig.

c) soha.

28. Egy mátrixjáték vegyes stratégia összetevőinek összege mindig:

a) egyenlő 1-gyel.

b) nem negatív.

c) pozitív.

d) nem mindig.

29. Egy 2*3-as dimenziójú mátrixjátékban az 1. játékos egyik vegyes stratégiájának formája legyen (0.3, 0.7), a 2. játékos egyik vegyes stratégiájának pedig (0.2, x, x) alakja. . Mi az x szám?

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 egy antagonisztikus játékot egy trojka képviselhet , 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) , amely 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 oldhatunk meg: 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 klub focistáinak 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

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) az étlap a világ különféle híres konyháit egyesíti;

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

4) házhozszállításra 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

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

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

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á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

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

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

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.

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ó:

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:

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.

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.

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 tegyenek a játékosok?

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.