Antagonistiniai matriciniai žaidimai. Matriciniai žaidimai Nulinės sumos žaidimai Nulinės sumos žaidimų sprendimas internete
Sprendimų priėmimo problema, nagrinėjama sisteminio požiūrio rėmuose, susideda iš trijų pagrindinių komponentų: ji išskiria sistemą, valdymo posistemį ir aplinką. Dabar pereiname prie sprendimų priėmimo problemų tyrimo, kai sistemą veikia ne viena, o keletas valdymo posistemių, kurių kiekviena turi savo tikslus ir veikimo galimybes. Toks sprendimų priėmimo metodas vadinamas žaidimo teoretiniu, o atitinkamų sąveikų matematiniais modeliais žaidimai. Dėl valdymo posistemių tikslų skirtumų, taip pat tam tikrų apribojimų, susijusių su galimybe keistis informacija tarp jų, šios sąveikos yra prieštaringo pobūdžio. Todėl kiekvienas žaidimas yra matematinis konflikto modelis. Apsiribokime tuo atveju, kai yra dvi valdymo posistemės. Jei sistemų tikslai yra priešingi, konfliktas vadinamas antagonistiniu, o matematinis tokio konflikto modelis. antagonistinis žaidimas..
Žaidimų teorinėje terminologijoje 1-asis valdymo posistemis vadinamas žaidėjas 1, 2-asis valdymo posistemis - žaidėjas 2, rinkiniai
jų alternatyvūs veiksmai vadinami strategijų rinkiniusšie žaidėjai. Leisti X- daug strategijų 1 žaidėjui, Y- daug strategijų
2 žaidėjas. Sistemos būseną vienareikšmiškai lemia 1 ir 2 posistemių valdymo veiksmų pasirinkimas, tai yra strategijų pasirinkimas
x∈X Ir y∈Y. Leisti F(x,y) – naudingumo įvertinimas tos valstybės 1 žaidėjui
sistema, į kurią patenka, kai žaidėjas pasirenka 1 strategiją X Ir
2 žaidėjo strategija adresu. Skaičius F(x,y) vadinamas laimėti 1 žaidėjas situacijoje ( x,y), ir funkcija F- 1 žaidėjo išmokėjimo funkcija. Žaidėjo laimėjimai
1 tuo pačiu yra 2 žaidėjo praradimas, tai yra vertė, kurią pirmasis žaidėjas siekia padidinti, o antrasis - sumažinti. Štai kas yra
konflikto antagonistinio pobūdžio apraiška: žaidėjų interesai visiškai priešingi (ką laimi vienas, tą pralaimi).
Antagonistinį žaidimą natūraliai apibrėžia sistema G=(X, Y, F).
Atkreipkite dėmesį, kad formaliai nulinės sumos žaidimas nustatomas beveik taip pat, kaip ir sprendimo priėmimo užduotis neapibrėžtumo sąlygomis – jei
2 valdymo posistemį tapatinti su aplinka. Esminis skirtumas tarp valdymo posistemio ir aplinkos yra tas
pirmojo elgesys yra tikslingas. Jei, sudarydami realaus konflikto matematinį modelį, turime pagrindo (ar ketinimų) laikyti aplinką priešu, kurio tikslas yra
didžiausią žalą mums, tada tokia situacija gali būti pateikta antagonistinio žaidimo forma. Kitaip tariant, nulinės sumos žaidimas gali būti interpretuojamas kaip kraštutinis ZPR atvejis neapibrėžtumo sąlygomis,
būdingas aplinkos traktavimas kaip priešininkas, turintis tikslą. Kartu turime apriboti hipotezių tipus apie aplinkos elgesį.
Labiausiai pateisinama čia yra ypatingo atsargumo hipotezė, kai priimdami sprendimą atsižvelgiame į blogiausią įmanomą aplinkos veiksmą.
Apibrėžimas. Jeigu X Ir Y yra baigtiniai, tada antagonistinis žaidimas vadinamas matriciniu žaidimu. Matriciniame žaidime galime tai manyti X={1,…,n},
Y={1,…,m) ir įdėti aij=F(aš, j). Taigi, matricos žaidimas yra visiškai nulemtas matricos A=(aij), i=1,…,n, j=1,…,m.
3.1 pavyzdys. Žaidimas dviem pirštais.
Du žmonės vienu metu rodo vieną ar du pirštus ir skambina numeriu 1 arba 2, kuris, kalbėtojo nuomone, reiškia skaičių
kitiems rodomi pirštai. Parodžius pirštus ir įvardijus skaičius, laimėjimai paskirstomi pagal šias taisykles:
jei abu atspėjo arba abu neatspėjo, kiek pirštų parodė priešininkas, visų laimėjimai lygūs nuliui; jei tik vienas atspėjo, tada priešininkas sumoka spėliotojui pinigų sumą, proporcingą bendram parodytam skaičiui
Tai nulinės sumos matricos žaidimas. Kiekvienas žaidėjas turi keturias strategijas: 1 – parodyk 1 pirštą ir skambink 1, 2 – parodyk 1 pirštą ir skambink 2, 3 –
parodyk 2 pirštus ir skambink 1, 4 – parodyk 2 pirštus ir skambink 2. Tada išmokėjimo matrica A=(aij), i= 1,…, 4, j= 1,…, 4 apibrėžiamas taip:
a12= 2, a21 = – 2, a13=a42=–3, a24=a31= 3, a34 = – 4, a43= 4,aij= 0 kitais atvejais.
3.2 pavyzdys. Diskretiškas dvikovos tipo žaidimas.
Dvikovos tipo problemos apibūdina, pavyzdžiui, dviejų žaidėjų kovą,
kurių kiekvienas nori atlikti kokį nors vienkartinį veiksmą (išleisti prekių partiją į rinką, pateikti paraišką pirkti aukcione) ir pasirenka tam laiką. Leiskite žaidėjams judėti vienas kito link nžingsniai. Po kiekvieno žingsnio žaidėjas gali pasirinkti šaudyti ar nešaudyti į priešą. Kiekvienas žmogus gali šaudyti tik vieną kartą. Manoma, kad tikimybė nukentėti priešą, jei žengsite į priekį k n =5 turi formą
Žaidimo teorija yra matematinių sprendimų priėmimo modelių teorija konflikto ar neapibrėžtumo sąlygomis. Daroma prielaida, kad žaidimo šalių veiksmams būdingos tam tikros strategijos – veiksmų taisyklių rinkiniai. Jei vienos pusės pelnas neišvengiamai veda prie kitos pusės praradimo, tada jie kalba apie antagonistinius žaidimus. Jei strategijų rinkinys yra ribotas, tada žaidimas vadinamas matriciniu ir sprendimą galima gauti labai paprastai. Sprendimai, gauti naudojant žaidimo teoriją, yra naudingi kuriant planus esant galimam konkurentų pasipriešinimui ar neapibrėžtumui išorinėje aplinkoje.
Jei bimatricinis žaidimas yra antagonistinis, tai 2 žaidėjo išmokėjimo matricą visiškai lemia 1 žaidėjo išmokėjimo matrica (atitinkami šių dviejų matricų elementai skiriasi tik ženklais). Todėl bimatricinis nulinės sumos žaidimas yra visiškai aprašytas viena matrica (1 žaidėjo išmokėjimo matrica) ir atitinkamai vadinamas matricos žaidimu.
Šis žaidimas yra antagonistinis. Jame j = x2 - O, P ir I (O, O] = H(P, P) = -I ir I (O, P) = I (P, O) = 1, arba matricos pavidalu apie p
Tegul kuri nors žaidimų klasė Ж būna „veidrodinė“, t.y. kartu su kiekvienu žaidimu jame yra veidrodinis izomorfinis žaidimas (kadangi visi žaidimai, kurie yra veidrodiniai izomorfiniai tam tikram žaidimui, yra izomorfiniai vienas kitam, mes, pagal ką tik pasakytą, galime kalbėti apie vieną veidrodinį izomorfinį žaidimą) . Tokia klasė yra, pavyzdžiui, visų nulinės sumos žaidimų klasė arba visų matricinių žaidimų klasė.
Prisimindami priimtinų situacijų apibrėžimą nulinės sumos žaidime, matome, kad situacija (X, Y) mišriame matricos žaidimo išplėtime yra priimtina 1 žaidėjui tada ir tik tada, jei nelygybė galioja bet kuriam x G x.
Žaidimų pavertimo simetriniais procesas vadinamas simetrija. Čia apibūdinsime vieną simetrijos techniką. Kitas, iš esmės kitoks simetrijos variantas bus pateiktas 26.7 skyriuje. Abi šios simetrijos parinktys iš tikrųjų taikomos savavališkiems nulinės sumos žaidimams, tačiau bus suformuluotos ir patikrintos tik matriciniams žaidimams.
Taigi bendrųjų antagonistinių žaidimų teorijos pradiniai terminai ir žymėjimai sutampa su atitinkamais matricinių žaidimų teorijos terminais ir žymėjimais.
Baigtinės nulinės sumos (matricos) žaidimams mes įrodėme šių ekstremalių egzistavimą 10 skyriuje. 1, o esmė buvo nustatyti jų lygybę arba bent jau rasti būdų, kaip įveikti jų nelygybę.
Jau išnagrinėjus matricinius žaidimus matyti, kad iš pradžių pateiktose žaidėjų strategijose yra antagonistinių žaidimų be pusiausvyros situacijų (ir net be e-pusiausvyros situacijų esant pakankamai mažam e > 0).
Bet kiekvienas baigtinis (matricinis) žaidimas gali būti išplėstas iki begalinio žaidimo, pavyzdžiui, kiekvienam žaidėjui suteikiant bet kokį dominuojančių strategijų skaičių (žr. 22 skyrių, 1 skyrių). Akivaizdu, kad toks žaidėjo strategijų rinkinio išplėtimas tikrai nereikš jo galimybių išplėtimo, o realus jo elgesys išplėstiniame žaidime neturės skirtis nuo elgesio pradiniame žaidime. Taigi iš karto gavome pakankamai daug begalinių antagonistinių žaidimų, neturinčių balno taškų, pavyzdžių. Yra ir tokių pavyzdžių.
Taigi, norint įgyvendinti maksimino principą begaliniame antagonistiniame žaidime, reikia, kaip ir baigtinio (matricinio) žaidimo atveju, kiek praplėsti žaidėjų strategines galimybes. Už 96
Kaip ir matricinių žaidimų atveju (žr. 17 skyrių, 1 skyrių), bendriesiems nulinės sumos žaidimams svarbų vaidmenį atlieka mišraus strategijos spektro samprata, kuriai čia vis dėlto reikia suteikti bendresnį apibrėžimą.
Galiausiai atkreipkite dėmesį, kad visų 1 žaidėjo mišrių strategijų rinkinys savavališkame nulinės sumos žaidime yra kaip matriciniame žaidime.
Jau ištyrus nulinės sumos žaidimus, matyti, kad daug tokių žaidimų, įskaitant baigtinių matricų žaidimus, turi pusiausvyros situacijas ne originaliose, grynosiose strategijose, o tik apibendrintose, mišriose strategijose. Todėl bendriems, neantagonistiniams nebendradarbiaujantiems žaidimams natūralu pusiausvyros situacijų ieškoti būtent mišriose strategijose.
Taigi, pavyzdžiui (žr. 3.1 pav.), mes jau pažymėjome, kad „Vykdytojas“ beveik niekada neturi susidurti su elgesio neapibrėžtumu. Bet jei paimtume konceptualų „Administratoriaus“ tipo lygmenį, tada viskas yra priešingai. Paprastai pagrindinis neapibrėžtumo tipas, su kuriuo turi susidurti toks „mūsų sprendimų priėmėjas“, yra „konfliktas“. Dabar galime paaiškinti, kad tai paprastai nėra griežta konkurencija. Kiek rečiau „Administratorius“ sprendimus priima „natūralaus neapibrėžtumo“ sąlygomis, dar rečiau susiduria su griežtu, antagonistiniu konfliktu. Be to, interesų konfliktas „Administratoriui“ priimant sprendimus atsiranda, taip sakant, „vieną kartą“, t.y., mūsų klasifikacijoje, jis dažnai žaidžia tik vieną (kartais labai nedidelį skaičių) žaidimų. Pasekmių vertinimo skalės dažnai yra kokybinės, o ne kiekybinės. Administratoriaus strateginis nepriklausomumas yra gana ribotas. Atsižvelgiant į tai, kas išdėstyta, galima teigti, kad tokio masto problemines situacijas dažniausiai tenka analizuoti naudojant nebendradarbiaujančius neantagonistinius dvimatricinius žaidimus, be to, grynosios strategijos.
Matricinių nulinių sumų žaidimų sprendimo principai
Dėl to pagrįstai galima tikėtis, kad aukščiau aprašytame žaidime varžovai laikysis savo pasirinktų strategijų. Matricos nulinės sumos žaidimas, kuriame max min fiv = min max Aiy>
Tačiau ne visi matriciniai antagonistiniai žaidimai yra gerai apibrėžti ir apskritai
Taigi, bendru atveju, norint išspręsti /xl matmenų matricinį nulinės sumos žaidimą, reikia išspręsti porą dvigubo linijinio programavimo uždavinių, dėl kurių randamas optimalių strategijų rinkinys, / ir kaina. žaidimo v.
Kaip apibrėžiamas dviejų asmenų matricos antagonistinis žaidimas?
Kokie yra matricinių nulinės sumos žaidimų supaprastinimo ir sprendimo metodai?
Žaidimo tarp dviejų žmonių atveju natūralu, kad jų interesai yra tiesiogiai priešingi – žaidimas yra antagonistinis. Taigi vieno žaidėjo laimėjimas lygus kito pralaimėjimui (abiejų žaidėjų laimėjimų suma lygi nuliui, iš čia ir pavadinimas – nulinės sumos žaidimas). Mes apsvarstysime žaidimus, kuriuose kiekvienas žaidėjas turi ribotą skaičių alternatyvų. Tokio dviejų asmenų nulinės sumos žaidimo išmokėjimo funkcija gali būti pateikta matricos forma (kaip išmokėjimo matrica).
Kaip jau minėta, baigtinis antagonistinis žaidimas vadinamas matriciniu žaidimu.
MATRIX GAMES – antagonistinių žaidimų klasė, kurioje dalyvauja du žaidėjai, kurių kiekvienas turi ribotą skaičių strategijų. Jei vienas žaidėjas turi m strategijų, o antrasis turi n, tada galima sudaryti žaidimo matricą, kurios matmenys yra thn. M.i. gali turėti arba neturėti balno taško. Pastaruoju atveju
Matricinių žaidimų sprendimą galima apibendrinti nulinės sumos žaidimų atveju, kai žaidėjų atsipirkimas nurodomas kaip nuolatinė funkcija (begalinis nulinės sumos žaidimas).
Šis žaidimas vaizduojamas kaip dviejų žaidėjų žaidimas, kuriame 1 žaidėjas pasirenka skaičių X iš daugelio X, 2 žaidėjas pasirenka skaičių y iš rinkinio 7, o po to 1 ir 2 žaidėjai atitinkamai gauna laimėjimus U(x, y) ir -U(x, y).Žaidėjo pasirinktas tam tikras skaičius reiškia jo grynosios strategijos, atitinkančios šį skaičių, taikymą.
Analogiškai su matriciniais žaidimais galima pavadinti mažesnę grynąją žaidimo kainą v (= max min U(x, y), ir grynoji aukščiausia žaidimo kaina -v 2 =
min maks U(x, y). Tada pagal analogiją galime manyti, kad jei kai kuriems
adresu *
arba nesibaigiantis antagonistinis dydžio žaidimas V Ir v 2 egzistuoja ir yra lygūs vienas kitam („t =v 2 =v), tada toks žaidimas turi sprendimą grynosiose strategijose, t.y. 1 žaidėjo optimali strategija yra pasirinkti skaičių x° e X, o žaidėjas 2 – skaičiai y 0 e 7, už kurį Shchh ( y 0) -v.
Tokiu atveju v vadinama grynąja žaidimo kaina, o (x°, y 0) yra begalinio nulinės sumos žaidimo balno taškas.
Matricos žaidimams v x Ir v 2 visada egzistuoja, bet begaliniuose antagonistiniuose žaidimuose jų gali ir nebūti, t.y. nesibaigiantis nulinės sumos žaidimas ne visada išsprendžiamas.
Įforminant realią situaciją nesibaigiančio antagonistinio žaidimo forma, dažniausiai pasirenkamas vienas strateginis intervalas – vienas intervalas, iš kurio žaidėjai gali pasirinkti (X - 1 žaidėjo pasirinktas skaičius (strategija); -
2 žaidėjo pasirinktas skaičius (strategija). Techniškai tai supaprastina sprendimą, nes paprasta transformacija bet kurį intervalą galima paversti vienetiniu intervalu ir atvirkščiai. Šis žaidimas vadinamas antagonistinis žaidimas vieneto kvadrate.
Pavyzdžiui, tarkime, kad 1 žaidėjas pasirenka skaičių X iš daugelio X=, 2 žaidėjas pasirenka skaičių y iš rinkinio Y=. Po to 2 žaidėjas sumoka žaidėjui 1 sumą Shx, y) -2x 2 -y 2. Kadangi 2 žaidėjas siekia sumažinti 1 žaidėjo mokėjimą, jis nustato min ( 2x 2 - y 2) = 2x 2– 1, t.y. šiuo atveju = 1. 1 žaidėjas stengiasi padaryti mtagą
Imituokite savo mokėjimą, todėl nustato maksimalų min Shchh, y)1 =
xGX y pvz
- maks (2x 2 - 1) = 2- 1 = 1, kuris pasiekiamas, kai X = 1.
Taigi mažesnė grynoji žaidimo kaina v x - 1. Išvalykite viršų
žaidimo kainav 2 =min - min (2 - y 2) = 2 - 1 = 1, t.y. šiame
> pvzheh ey
žaidimas v l =v 2 =l. Taigi grynoji žaidimo kaina v= 1, o balno taškas (x° = 1; y° = 1).
Dabar manykime, kad tai Chi Y- atviri intervalai, t.y. 1 žaidėjas pasirenka xeA"=(0; 1), 2 žaidėjas pasirenka ue 7= (0; 1). Šiuo atveju pasirenkant X, pakankamai arti 1, 1 žaidėjas bus įsitikinęs, kad gaus ne mažesnį atlygį nei skaičius, artimas "=1; pasirinkdamas y arti 1, 2 žaidėjas neleis, kad 1 žaidėjo išmokėjimas gerokai viršytų grynąją žaidimo kainą v= 1.
Artumo žaidimo kainai laipsnį galima apibūdinti skaičiumi?>0. Todėl aprašytame žaidime galime kalbėti apie grynųjų strategijų optimalumą x°= 1, 0 = 1 atitinkamai žaidėjai 1 ir 2 iki savavališko skaičiaus?>0. Taškas (X", y E), kur x e e X, y (. eY, begaliniame nulinės sumos žaidime vadinamas z pusiausvyros taškas (s.-balno taškas), jei bet kuriai strategijai xTiger 1, ue Tiger 2 galioja nelygybė Shchh, u.) - ? Ш x r , у (.) U(x t ., у) + ?. Šiuo atveju strategijos x k. ir tu. yra vadinami su,-optimaliomis strategijomis. Ar šios strategijos yra optimalios? ta prasme, kad jei nukrypimas nuo optimalios strategijos negali atnešti jokios naudos žaidėjui, tai jo nukrypimas nuo c-optimalios strategijos gali padidinti jo pelną ne daugiau kaip e.
Jei žaidimas neturi balno taško (c-saddle point), t.y. sprendimus grynosiose strategijose, tada optimalių strategijų galima ieškoti tarp mišrių strategijų, kurios naudojamos kaip grynąsias strategijas naudojančių žaidėjų tikimybių pasiskirstymo funkcijos.
Leisti F(x) yra 1 žaidėjo grynųjų strategijų naudojimo tikimybių pasiskirstymo funkcija. Jei skaičius E yra grynoji 1 žaidėjo strategija, tada F(x) = P(q kur P(q -X)- tikimybė, kad atsitiktinai pasirinkta grynoji strategija E neviršys X. Panašiai nagrinėjama tikimybių pasiskirstymo funkcija naudojant grynąsias strategijas r|. 2 žaidėjas: Q(y) = P(g .
Funkcijos F(x) Ir Q(y) yra vadinami mišrios strategijos atitinkamai 1 ir 2 žaidėjai. Jei Fx) Ir Q(y) yra diferencijuojami, tada egzistuoja jų išvestinės, atitinkamai žymimos f(x) Ir q(y)(paskirstymo tankio funkcijos).
Apskritai skirstymo funkcijos skirtumas dF(x) išreiškia tikimybę, kad strategija Su, yra tarp x E, Panašiai ir 2 žaidėjui: dQ(y) reiškia tikimybę, kad jo strategija p yra intervale y g| y+dy. Tada 1 žaidėjo mokėjimas bus Shx, y) dF(x), o žaidėjo 2 mokėjimas yra Shx, y) dQ(y).
Vidutinė 1 žaidėjo išmoka, atsižvelgiant į tai, kad 2 žaidėjas naudoja savo gryną strategiją y, galima gauti integruojant mokėjimus per visas įmanomas vertes X, tie. vieneto intervalu:
Vidutinis 1 žaidėjo atlyginimas, darant prielaidą, kad abu žaidėjai naudoja savo mišrias strategijas F(x) Ir Q(y), bus lygus
Analogiškai su matriciniais žaidimais nustatomos optimalios žaidėjų mišrios strategijos ir žaidimo kaina: jei mišrių strategijų pora F*(x) Ir Q*(y) atitinkamai 1 ir 2 žaidėjams yra optimalūs, tada bet kuriai mišriai strategijai F(x) Ir Q(y) galioja šie santykiai:
Jei 1 žaidėjas nukrypsta nuo savo strategijos F*(x), tada jo vidutinė išmoka negali padidėti, bet gali sumažėti dėl racionalių 2 žaidėjo veiksmų. Jei 2 žaidėjas pasitraukia nuo savo mišrios strategijos Q*(y), tada 1 žaidėjo vidutinė išmoka gali padidėti, bet nesumažėti dėl protingesnių 1 žaidėjo veiksmų. E(F*, Q*), 1 žaidėjas gauna, kai žaidėjai taiko optimalias mišrias strategijas, atitinka žaidimo kainą.
Tada begalinės nulinės sumos žaidimo, išspręsto mišriomis strategijomis, minimalią kainą galima apibrėžti kaip v x= patikrinkite
min E(FQ), ir aukščiausia žaidimo kaina yra tokia v 2 = min maks E(F, Q).
Q Q f
Jei tokios mišrios strategijos egzistuoja F* (x) Ir Q*(y) atitinkamai 1 ir 2 žaidėjams, kurių apatinė ir viršutinė žaidimo kainos sutampa, tada F*(x) Ir Q*(y) Natūralu, kad atitinkamų žaidėjų optimalias mišrias strategijas galima vadinti a v = v x = v 2- žaidimo kaina.
Skirtingai nuo matricos žaidimų, begalinio nulinės sumos žaidimo sprendimas neegzistuoja kiekvienai funkcijai Ššš, ai). Tačiau teorema buvo įrodyta, kad kiekvienas begalinis nulinės sumos žaidimas su nuolatine išmokėjimo funkcija Ššš, ai) vieneto kvadratas turi sprendimą (žaidėjai turi optimalias mišrias strategijas), nors nėra bendrų metodų, kaip išspręsti begalinius nulinės sumos žaidimus, įskaitant nuolatinius žaidimus. Tačiau antagonistiniai begaliniai žaidimai su išgaubtomis ir įgaubtomis nuolatinėmis išmokėjimo funkcijomis (jie vadinami atitinkamai išgaubtas Ir įgaubti žaidimai).
Panagrinėkime žaidimų su išgaubta išmokėjimo funkcija sprendimą. Žaidimų su įgaubta išmokėjimo funkcija sprendimas yra simetriškas.
Išgaubtas funkcija/kintamasis X per intervalą ( A; b) yra funkcija, kuriai galioja nelygybė
Kur Xx Ir x 2 - bet kurie du taškai iš intervalo (a; b);
X.1, A.2 > 0 ir +X.2 = 1.
Jei / h * 0 D 2 * 0, griežta nelygybė galioja visada
tada funkcija/ iškviečiama griežtai išgaubtas ant; b).
Geometriškai išgaubta funkcija vaizduoja lanką, kurio grafikas yra žemiau jį sutraukiančios stygos. Analitiškai dvigubai diferencijuojamos funkcijos išgaubtumas atitinka jos antrosios išvestinės neneigiamumą (o griežto išgaubimo atveju – pozityvumą).
Įgaubtų funkcijų savybės yra priešingos; joms nelygybė /(/4X1 +A.2X2) > Kf(xi) +)-jei(x 2) (> su griežta įduba), o antroji išvestinė / "(x)
Įrodyta, kad ištisinė ir griežtai išgaubta funkcija uždarame intervale įgauna minimalią reikšmę tik viename intervalo taške. Jeigu Shchh, y) yra nuolatinė 1 žaidėjo išmokėjimų vieneto kvadrate ir funkcija griežtai išgaubtas išilgai adresu bet kuriam x yra unikali optimali grynoji strategija y=y° e 2 žaidėjui žaidimo kaina nustatoma pagal formulę
ir prasmė y 0 apibrėžiamas kaip šios lygties sprendimas:
Jei funkcija Shchh, y) nėra griežtai išgaubtas y, tada 2 žaidėjas neturės vienintelės optimalios grynosios strategijos.
Simetrinė savybė taip pat taikoma griežtai įgaubtoms funkcijoms. Jei funkcija Shchh, y) yra tęstinis abiejuose argumentuose ir griežtai įgaubtas x bet kuriame y, tada 1 žaidėjas turi unikalią optimalią strategiją.
Žaidimo kaina nustatoma pagal formulę
o 1 žaidėjo grynoji optimali strategija x 0 nustatoma pagal lygtį
Remiantis šiomis begalinės nulinės sumos žaidimų su išgaubtomis arba įgaubtomis išmokėjimo funkcijomis savybėmis, sukonstruota bendra tokių žaidimų sprendimo vienetiniame kvadrate (хе, уе) schema. Šią schemą pateikiame tik išgaubtiems žaidimams, nes įgaubtiems žaidimams ji yra simetriška.
1. Patikrinkite funkciją Shchh, y) išgaubtumui y (antroji dalinė išvestinė turi būti didesnė arba lygi 0).
2. Iš santykio nustatykite y 0 v- min maks Ššš, ai) kaip prasmė
y, prie kurio pasiekiamas minimumas.
3. Raskite lygties sprendinį v = U(x, y 0) ir sudaryti jo sprendinių poras X Ir x 2, kuriam
4. Rasti parametrą A iš Eq.
Parametras A nustato optimalią 1 žaidėjo strategiją ir turi jo grynosios strategijos pasirinkimo tikimybę reikšmę x x. Reikšmė 1 – a reiškia tikimybę, kad žaidėjas 1 pasirinks savo grynąją strategiją x 2.
Panaudokime pavyzdį, kad parodytume šios schemos naudojimą sprendžiant tokio tipo žaidimą. Tegul išmokėjimo funkcija begaliniame nulinės sumos žaidime yra nurodyta vieneto kvadrate ir lygi Shchh, y) = =(x - y) 2 =x 2 - 2 xy ch-y 2.
1. Ši funkcija yra nuolatinė X Ir y, ir todėl šis žaidimas turi sprendimą. Funkcija Ššš, ai) griežtai išgaubtas išilgai y, nes 
Todėl 2 žaidėjas turi vienintelę grynai optimalią strategiją 0.
2. Turime v= min max (x - y) 2. Norėdami nustatyti maks. (x 2 - 2xy Ch-y 2)
Iš eilės suraskime pirmąją ir antrąją mokėjimo funkcijos dalines išvestines x atžvilgiu:
Taigi funkcija U turi bet kurio y minimumą, kai x=y. Tai reiškia, kad xy - didėjant, o jo maksimumas turėtų būti pasiektas viename iš kraštutinių taškų x = 0 arba x = 1. Nustatykime funkcijos reikšmes Ušiuose taškuose:
Tada patikrinkite (x - y) 2 = max (y 2; 1 - 2y + y 2). „vidaus“ palyginimas
maxima garbanotuose skliaustuose, tai nesunku pastebėti 2 val > 1 - - 2y+y 2, Jeigu y >*/ 2 ir y 2 1–2 y+y 2, Jeigu y "/ 2. Tai aiškiau pavaizduoja grafikas (2.5 pav.).
Ryžiai. 2.5. Vidiniai mokėjimo funkcijos maksimumai U(x, y) = (x- adresu) 2
Todėl išraiška (x - y) 2 pasiekia maksimumą ties x=0, jei y > 7 2 ir pas x= 1 jei U 2:
Vadinasi, v= min (min y 2; min (1 - y) 2). Kiekvienas iš
ryto minimumai pasiekiami val y=*/ 2 ir įgauna reikšmę Y 4. Taigi žaidimo kaina r = Y 4 ir optimali 2 žaidėjo strategija:
3. Iš lygties nustatykite optimalią 1 žaidėjo strategiją U(x, y 0)= v, tie. šiam žaidimui (x - Y 2) 2 = Y 4. Šios lygties sprendimas YRA X| =0, x 2 = 1.
Sąlygos jiems įvykdytos
4. Nustatykime parametrą a, t.y. tikimybė, kad žaidėjas 1 pasinaudos savo grynąja strategija X] = 0. Sukurkime lygtį a-1 + (1 - a) (-1) = 0, iš kurios a = Y 2. Taigi optimali 1 žaidėjo strategija yra pasirinkti grynąsias 0 ir 1 strategijas su tikimybe 1 / 2 kiekviena. Problema išspręsta.
Galutinės kontrolės testai
1. Antagonistinis žaidimas gali būti nustatytas:
a) strategijų rinkinys tiek žaidėjams, tiek balno taškas.
b) abiejų žaidėjų strategijų rinkinys ir pirmojo žaidėjo išmokėjimo funkcija.
2. Žaidimo kaina visada egzistuoja matriciniams žaidimams mišriomis strategijomis.
a) taip.
3.Jei visi išmokėjimo matricos stulpeliai yra vienodi ir turi formą (4 5 0 1), tai kokia strategija yra optimali 1 žaidėjui?
a) pirmiausia.
b) antrasis.
c) bet kuris iš keturių.
4. Tegul matriciniame žaidime viena iš 1-ojo žaidėjo mišrių strategijų turi formą (0,3, 0,7), o viena iš mišrių antrojo žaidėjo strategijų turi formą (0,4, 0, 0,6). Koks yra šios matricos matmuo?
a) 2*3.
c) kitas matmuo.
5. Dominavimo principas leidžia pašalinti iš matricos vienu žingsniu:
a) ištisos eilutės.
b) atskiri numeriai.
6. Taikant grafinį 2*m žaidimų sprendimo būdą, tiesiai iš grafiko randama:
a) optimalios abiejų žaidėjų strategijos.
b) žaidimo kaina ir optimalios 2 žaidėjo strategijos.
c) žaidimo kaina ir optimalios 1 žaidėjo strategijos.
7. Apatinio voko grafikas grafiniam 2*m žaidimų sprendimo būdui yra bendruoju atveju:
a) sulaužytas.
b) tiesus.
c) parabolė.
8. 2*2 matricos žaidime yra du žaidėjo mišrios strategijos komponentai:
a) nustato vienas kito vertybes.
b) nepriklausomas.
9. Matricos žaidime elementas aij yra:
a) 1-ojo žaidėjo laimėjimai, kai jis naudoja i-ąją strategiją, o 2-ojo - j-ąją strategiją.
b) optimali 1-ojo žaidėjo strategija, kai varžovas naudoja i-tą arba j-ą strategiją.
c) 1-ojo žaidėjo praradimas, kai jis naudoja j-ąją strategiją, o 2-ojo - i-ąją strategiją.
10.Matricos elementas aij atitinka balno tašką. Galimos šios situacijos:
a) šis elementas yra griežtai mažiausias iš visų eilutėje.
b) šis elementas yra antras eilės eilėje.
11. Brown-Robinson metodu kiekvienas žaidėjas, pasirinkdamas strategiją kitame žingsnyje, vadovaujasi:
a) priešo strategijos ankstesniuose žingsniuose.
b) savo strategijas ankstesniuose žingsniuose.
c) kažkas kita.
12. Pagal matematinio lūkesčio kriterijų, kiekvienas žaidėjas remiasi tuo, kad:
a) jam atsitiks pati blogiausia situacija.
c) su tam tikromis tikimybėmis galimos visos arba kai kurios situacijos.
13. Tegu matricinį žaidimą pateikia matrica, kurioje visi elementai yra neigiami. Žaidimo kaina teigiama:
b) ne.
c) nėra aiškaus atsakymo.
14. Žaidimo kaina:
skaičius.
b) vektorius.
c) matrica.
15. Koks didžiausias balno taškų skaičius gali būti 5*5 matmenų žaidime (matricoje gali būti bet kokie skaičiai):
16. Tegul 2*3 matmenų matricos žaidime viena iš 1-ojo žaidėjo mišrių strategijų turi formą (0,3, 0,7), o viena iš mišrių antrojo žaidėjo strategijų turi formą (0,3, x, 0,5). . Kas yra skaičius x?
c) kitas skaičius.
17. Kokiam žaidimo matricos matmeniui Wald kriterijus virsta Laplaso kriterijumi?
c) tik kitais atvejais.
18. Viršutinė žaidimo kaina visada yra mažesnė už apatinę žaidimo kainą.
b) ne.
b) klausimas neteisingas.
19. Kokios strategijos yra matricos žaidime:
a) švarus.
b) mišrus.
c) abu.
20. Ar tam tikrame antagonistiniame žaidime abiejų žaidėjų išmokėjimo funkcijos reikšmės kai kurioms kintamųjų reikšmėms gali būti lygios 1?
a) visada.
b) kartais.
c) niekada.
21. Matriciniame žaidime viena iš 1-ojo žaidėjo mišrių strategijų turi būti formos (0,3, 0,7), o viena iš 2-ojo žaidėjo mišrių strategijų formos (0,4, 0,1, 0,1, 0,4). . Koks yra šios matricos matmuo?
c) kitas matmuo.
22. Dominavimo principas leidžia vienu žingsniu pašalinti iš matricos:
a) ištisus stulpelius,
b) atskiri numeriai.
c) mažesnio dydžio submatricos.
23. 3*3 matricos žaidime yra du žaidėjo mišrios strategijos komponentai:
a) nustatyti trečią.
b) neapibrėžti.
24. Matricos žaidime elementas aij yra:
a) 2-ojo žaidėjo praradimas, kai jis naudoja j-ąją strategiją, o 2-ojo - i-ąją strategiją.
b) optimali 2-ojo žaidėjo strategija, kai priešininkas naudoja i-tąją arba j-ąją strategiją,
c) 1-ojo žaidėjo laimėjimai, kai jis naudoja j-ąją strategiją, o antrojo - i-ąją strategiją,
25. Matricos elementas aij atitinka balno tašką. Galimos šios situacijos:
a) šis elementas yra didžiausias stulpelyje.
b) šis elementas yra griežtai didžiausias eilės tvarka.
c) eilutėje yra elementų, didesnių ir mažesnių už šį elementą.
26. Pagal Wald kriterijų kiekvienas žaidėjas daro prielaidą, kad:
a) jam atsitiks pati blogiausia situacija.
b) visos situacijos galimos vienodai.
c) visos situacijos galimos su tam tikromis duotomis tikimybėmis.
27. Mažesnė kaina yra mažesnė už viršutinę žaidimo kainą:
b) ne visada.
c) niekada.
28. Matricinio žaidimo mišrios strategijos komponentų suma visada yra:
a) lygus 1.
b) neneigiamas.
c) teigiamas.
d) ne visada.
29. Tegul 2*3 matmenų matricos žaidime viena iš 1-ojo žaidėjo mišrių strategijų turi formą (0,3, 0,7), o viena iš mišrių antrojo žaidėjo strategijų turi formą (0,2, x, x). . Kas yra skaičius x?
Siųsti savo gerą darbą žinių bazėje yra paprasta. Naudokite žemiau esančią formą
Studentai, magistrantai, jaunieji mokslininkai, kurie naudojasi žinių baze savo studijose ir darbe, bus jums labai dėkingi.
Įvadas
1. Teorinė dalis
1.3 Žaidimo tvarka 2x2
1.4 Algebrinis metodas
1.5 Grafinis metodas
1.6 Žaidimai 2xn arba mx2
1.7 Žaidimų sprendimas matricos metodu
2. Praktinė dalis
2.2 Žaidimai 2xn ir mx2
2.3 Matricos metodas
2.4 Rudas metodas
Rezultatų analizė
Įvadas
Nulinės sumos žaidimas yra nulinės sumos žaidimas. Nulinės sumos žaidimas yra nebendradarbiaujantis žaidimas, kuriame dalyvauja du žaidėjai, kurių išmokos yra priešingos.
Formaliai antagonistinį žaidimą gali atstovauti trejetas
Kadangi žaidėjų interesai yra priešingi, funkcija F kartu reiškia antrojo žaidėjo praradimą.
Istoriškai nulinės sumos žaidimai yra pirmoji matematinių žaidimų teorijos modelių klasė, kuria buvo aprašytas lošimas. Manoma, kad šis studijų dalykas yra žaidimų teorijos pavadinimas. Šiais laikais antagonistiniai žaidimai yra laikomi platesnės nebendradarbiaujančių žaidimų klasės dalimi.
1. Teorinė dalis
1.1 Pagrindiniai žaidimo apibrėžimai ir nuostatos
Žaidimui būdinga taisyklių sistema, kuri lemia žaidimo dalyvių skaičių, galimus jų veiksmus bei laimėjimų paskirstymą priklausomai nuo jų elgesio ir rezultatų. Žaidėju laikomas vienas dalyvis arba žaidimo dalyvių grupė, kuri turi bendrų interesų, kurie nesutampa su kitų grupių interesais. Todėl ne kiekvienas dalyvis laikomas žaidėju.
Žaidimo taisyklės ar sąlygos nustato galimą žaidėjų elgesį, pasirinkimus ir judesius bet kuriame žaidimo vystymosi etape. Pasirinkimas žaidėjui reiškia pasirinkti vieną iš jo elgesio variantų. Tada žaidėjas daro šiuos pasirinkimus naudodamas judesius. Judėjimas reiškia, kad tam tikrame žaidimo etape iš karto pasirenkamas visas arba jo dalis, atsižvelgiant į žaidimo taisyklėse numatytas galimybes. Kiekvienas žaidėjas tam tikrame žaidimo etape atlieka ėjimą pagal pasirinktą pasirinkimą. Kitas žaidėjas, žinodamas ar nežinodamas apie pirmojo žaidėjo pasirinkimą, taip pat atlieka ėjimą. Kiekvienas žaidėjas stengiasi atsižvelgti į informaciją apie ankstesnį žaidimo vystymąsi, jei tokią galimybę leidžia žaidimo taisyklės.
Taisyklių rinkinys, aiškiai nurodantis žaidėjui, kokį pasirinkimą jis turi padaryti atlikdamas kiekvieną ėjimą, priklausomai nuo situacijos, susidariusios dėl žaidimo, vadinamas žaidėjo strategija. Strategija žaidimo teorijoje reiškia tam tikrą pilną žaidėjo veiksmų planą, parodantį, kaip jis turėtų elgtis visais įmanomais žaidimo kūrimo atvejais. Strategija reiškia visų instrukcijų, skirtų bet kokiai informacijos būsenai, prieinamą žaidėjui bet kuriame žaidimo kūrimo etape, visuma. Iš to jau aišku, kad strategijos gali būti geros ir blogos, sėkmingos ir nesėkmingos ir pan.
Nulinės sumos lošimas bus tada, kai visų žaidėjų laimėjimų suma kiekviename jo žaidime yra lygi nuliui, t.y. nulinės sumos žaidime bendras visų žaidėjų kapitalas nesikeičia, o perskirstomas tarp žaidėjų. priklausomai nuo gautų rezultatų. Taigi į daugelį ekonominių ir karinių situacijų galima žiūrėti kaip į nulinės sumos žaidimus.
Visų pirma, nulinės sumos žaidimas tarp dviejų žaidėjų vadinamas antagonistiniu, nes jame esančių žaidėjų tikslai yra tiesiogiai priešingi: vieno žaidėjo pelnas atsiranda tik kito pralaimėjimo sąskaita.
1.1.1 Matricinių žaidimų apibrėžimas, pavyzdžiai ir sprendimai grynosiose strategijose
Dviejų žaidėjų nulinės sumos matricos žaidimas gali būti įsivaizduojamas kaip toks abstraktus dviejų žaidėjų žaidimas.
Pirmasis žaidėjas turi t strategiją i =1, 2,…, t, antrasis turi n strategijų j = 1, 2,…, p. Kiekviena strategijų pora (i, j) yra susieta su skaičiumi a ij , išreiškiančiu pirmojo žaidėjo laimėjimai dėl antrojo žaidėjo, jei pirmasis žaidėjas naudoja savo i-ąją strategiją, o antrasis žaidėjas naudoja savo j-ąją strategiją.
Kiekvienas žaidėjas atlieka vieną ėjimą: pirmasis žaidėjas pasirenka savo i-ąją strategiją (i = 1, 2,..., m), antrasis pasirenka savo j-ąją strategiją (j = 1, 2,..., n). , po kurio pirmasis žaidėjas gauna laimėjimą ij antrojo žaidėjo sąskaita (jei ij< 0, то это значит, что первый игрок платит второму сумму a ij). На этом игра заканчивается.
Kiekviena žaidėjo strategija i = 1, 2,…, t; j = 1, 2,…, n dažnai vadinama grynąja strategija.
Dviejų žaidėjų nulinės sumos matricos žaidimas nuo šiol bus vadinamas tiesiog matricos žaidimu. Akivaizdu, kad matricos žaidimas priklauso antagonistiniams žaidimams. Iš jo apibrėžimo matyti, kad norint apibrėžti matricinį žaidimą, pakanka nurodyti pirmojo žaidėjo išmokų eilės matricą A = (a ij).
Jei atsižvelgsime į atsipirkimo matricą
tada kiekvienas matricos žaidimo žaidimas su matrica A sumažinamas iki pirmojo i-osios eilės žaidėjo ir antrojo j-osios stulpelio žaidėjo pasirinkimo, o pirmasis gaunantis žaidėjas (antrojo sąskaita) ) laimėjimus, esančius A matricoje i-osios eilutės ir j-osios stulpelio sankirtoje.
Norint įforminti realią konfliktinę situaciją matricinio žaidimo forma, būtina nustatyti ir pernumeruoti grynąsias kiekvieno žaidėjo strategijas ir sukurti išmokėjimo matricą.
Kitas etapas – nustatyti optimalias žaidėjų strategijas ir laimėjimus.
Pagrindinis dalykas tiriant žaidimus yra optimalių žaidėjų strategijų samprata. Ši sąvoka intuityviai turi tokią reikšmę: žaidėjo strategija yra optimali, jei šios strategijos naudojimas suteikia jam didžiausią garantuotą laimėjimą pagal visas įmanomas kito žaidėjo strategijas. Remdamasis šiomis pozicijomis, pirmasis žaidėjas tiria savo išmokėjimų matricą A naudodamas (1.1) formulę taip: kiekvienai i reikšmei (i = 1, 2,..., t) nustatoma minimali išmokėjimo vertė, priklausomai nuo antrojo žaidėjo naudojamos strategijos
(i = 1, 2,..., m) (1,2)
y., nustatomas minimalus pirmojo žaidėjo laimėjimas, su sąlyga, kad jis taiko savo i-ąją grynąją strategiją, tada iš šių minimalių išmokėjimų randama strategija i = i 0, kuriai ši minimali išmoka bus didžiausia, t.y.
Apibrėžimas. Skaičius b, nustatomas pagal (1.3) formulę, vadinamas mažesne grynąja žaidimo kaina ir parodo, kokį minimalų laimėjimą gali garantuoti pirmasis žaidėjas, taikydamas savo grynąsias strategijas visiems galimiems antrojo žaidėjo veiksmams.
Antrasis žaidėjas, elgdamasis optimaliai, turėtų stengtis, jei įmanoma, savo strategijomis sumažinti pirmojo žaidėjo laimėjimus. Todėl antram žaidėjui randame
y., nustatomas maksimalus pirmojo žaidėjo laimėjimas, su sąlyga, kad antrasis žaidėjas taiko savo j-ąją grynąją strategiją, tada antrasis žaidėjas suranda savo j = j 1 strategiją, pagal kurią pirmasis žaidėjas gaus minimalų atlyginimą, t.y.
Apibrėžimas. Skaičius b, nustatomas pagal formulę (1.5), vadinamas grynąja viršutine žaidimo kaina ir parodo, kokius maksimalius laimėjimus pirmasis žaidėjas gali garantuoti sau naudodamas savo strategijas. Kitaip tariant, taikydamas savo grynąsias strategijas, pirmasis žaidėjas gali užtikrinti ne mažesnį nei b laimėjimą, o antrasis žaidėjas, taikydamas savo grynąsias strategijas, gali užkirsti kelią pirmajam žaidėjui laimėti daugiau nei b.
Apibrėžimas. Jei žaidime su matrica A apatinė ir viršutinė žaidimo grynoji kaina sutampa, t. y. b = c, tada sakoma, kad šis žaidimas turi balno tašką grynosiose strategijose ir grynąją žaidimo kainą:
n = b = v (1,6)
Balno taškas yra grynų pirmojo ir antrojo žaidėjų strategijų () pora, kurioje pasiekiama lygybė.
Balno taško sąvoka turi tokią reikšmę: jei vienas iš žaidėjų laikosi strategijos, atitinkančios balno tašką, tai kitas žaidėjas negali padaryti geriau, nei laikytis strategijos, atitinkančios balno tašką. Turint omenyje, kad geriausias žaidėjo elgesys neturėtų lemti jo laimėjimo sumažėjimo, o blogiausias jo laimėjimo sumažėjimas, šias sąlygas galima matematiškai parašyti tokiais ryšiais:
kur i, j yra bet kokios grynos pirmojo ir antrojo žaidėjų strategijos atitinkamai; (i 0 , j 0) yra strategijos, kurios sudaro balno tašką. Žemiau parodysime, kad balno taško apibrėžimas yra lygiavertis sąlygoms (1.8).
Taigi, remiantis (1.8), matricos A balno elementas yra minimalus i 0 eilutėje, o didžiausias - j 0 stulpelyje. Matricos A balno tašką rasti paprasta: matricoje A minimalus elementas iš eilės randamas matricoje A. kiekvieną eilutę ir patikrinkite, ar šis elementas yra didžiausias jos stulpelyje. Jei jis yra toks, tai yra balno elementas, o jį atitinkanti strategijų pora sudaro balno tašką. Pirmojo ir antrojo žaidėjų grynųjų strategijų pora (i 0 , j 0), sudaranti balno tašką ir balno elementą, vadinama žaidimo sprendimu.
Grynosios strategijos i 0 ir j 0, sudarančios balno tašką, vadinamos atitinkamai optimaliomis grynosiomis pirmojo ir antrojo žaidėjų strategijomis.
1 teorema. Tegu f (x, y) yra realioji dviejų kintamųjų x A ir y B funkcija ir egzistuoja
tada b = c.
Įrodymas. Iš minimumo ir maksimumo apibrėžimų išplaukia, kad
Kadangi kairėje (1.11) x yra savavališkas, tada
Dešinėje nelygybės (1.12) pusėje y yra savavališkas, todėl
Q.E.D.
Konkrečiai, matrica () yra specialus funkcijos f (x, y) atvejis, t. y. jei įdėsime x = i, y = j, = f (x, y), tada iš 1 teoremos gauname, kad apatinis tinklas kaina neviršija viršutinės grynosios žaidimo kainos matricos žaidime.
Apibrėžimas. Tegul f (x, y) yra tikroji dviejų kintamųjų x A ir y B funkcija. Taškas (x 0, y 0) vadinamas funkcijos f (x, y) balno tašku, jei tenkinamos šios nelygybės
f (x, y 0) f (x 0, y 0) f (x 0, y) (1,14)
bet kuriam x A ir y B.
1.2 Optimalios mišrios strategijos ir jų savybės
Matricinio žaidimo tyrimas prasideda nuo jo balno taško suradimo grynosiose strategijose. Jei matricos žaidimas turi balno tašką grynosiose strategijose, tada žaidimo tyrimas baigiasi šio taško suradimu. Jei matriciniame žaidime grynosios strategijos nėra balno taško, tada galima rasti šio žaidimo apatinę ir viršutinę grynąsias kainas, kurios rodo, kad pirmasis žaidėjas neturėtų tikėtis laimėti daugiau nei viršutinė žaidimo kaina, ir gali įsitikinkite, kad gausite ne mažiau mažesnę žaidimo kainą. Tokios rekomendacijos dėl žaidėjų elgesio matriciniame žaidime be balno taško grynosiose strategijose negali patenkinti tyrėjų ir praktikų. Tobulinti matricinių žaidimų sprendimus reikėtų pasitelkiant grynųjų strategijų naudojimo slaptumą ir galimybę daug kartų kartoti žaidimus žaidimų forma. Taigi, pavyzdžiui, žaidžiama šachmatų, šaškių ir futbolo partijų serija, ir kiekvieną kartą žaidėjai taiko savo strategijas taip, kad priešininkai net neįsivaizduotų jų turinio, ir tokiu būdu jie vidutiniškai pasiekti tam tikrų laimėjimų žaisdami visą žaidimų seriją. Šie laimėjimai yra vidutiniškai didesni už mažesnę žaidimo kainą ir mažesni už viršutinę žaidimo kainą. Kuo didesnė ši vidutinė vertė, tuo geresnę strategiją žaidėjas naudoja. Todėl ir kilo mintis grynąsias strategijas taikyti atsitiktinai, su tam tikra tikimybe. Tai visiškai užtikrina jų naudojimo slaptumą. Kiekvienas žaidėjas gali pakeisti savo grynųjų strategijų naudojimo tikimybę taip, kad maksimaliai padidintų savo vidutinį pelną ir gautų optimalias strategijas. Ši idėja paskatino mišrios strategijos koncepciją.
Apibrėžimas. Žaidėjo mišri strategija yra visas tikimybių rinkinys, kad jis pasinaudos grynosiomis strategijomis.
Taigi, jei pirmasis žaidėjas turi m grynųjų strategijų 1, 2, … i, … m, tai jo mišri strategija x yra skaičių x = (x 1, x 2, ..., x i,…, x m ) aibė. santykius
x i 0 (i = 1, 2, ... , t), = 1. (1,15)
Panašiai antrajam žaidėjui, turinčiam n grynųjų strategijų, mišri strategija y yra skaičių y = (y 1, ..., y j, ... y n) rinkinys, tenkinantis santykius
y j 0 (j = 1, 2, ... , n), = 1. (1,16)
Kadangi kiekvieną kartą, kai žaidėjas naudoja vieną gryną strategiją, nenaudojama kita, grynos strategijos yra nesuderinami įvykiai. Be to, tai vieninteliai galimi įvykiai.
Akivaizdu, kad gryna strategija yra ypatingas mišrios strategijos atvejis. Iš tiesų, jei mišrioje strategijoje kuri nors i-oji grynoji strategija taikoma su viena tikimybe, tada visos kitos grynosios strategijos netaikomos. Ir ši i-oji grynoji strategija yra ypatingas mišrios strategijos atvejis. Kad išlaikytų paslaptį, kiekvienas žaidėjas taiko savo strategijas, nepaisydamas kito žaidėjo pasirinkimo.
Apibrėžimas. Vidutinis pirmojo žaidėjo atlyginimas matricos žaidime su matrica A išreiškiamas kaip matematinis jo išmokų lūkestis
E (A, x, y) = (1,20)
Akivaizdu, kad vidutinis pirmojo žaidėjo pelnas yra dviejų kintamųjų x ir y rinkinių funkcija. Pirmasis žaidėjas, keisdamas savo mišrias strategijas x, siekia maksimaliai padidinti savo vidutinį pelną E (A, x, y), o antrasis žaidėjas savo mišriomis strategijomis siekia, kad E (A, x, y) būtų minimalus, t.y. Norint išspręsti žaidimą, reikia rasti tokius x, y, kuriems esant pasiekiama aukščiausia žaidimo kaina.
1.3 Tvarkos žaidimas 22
22 eilės matricos žaidimas pateikiamas pagal šią pirmojo žaidėjo išmokėjimo matricą:
Šio žaidimo sprendimas turėtų prasidėti ieškant balno taško grynosiose strategijose. Norėdami tai padaryti, suraskite mažiausią elementą pirmoje eilutėje ir patikrinkite, ar jis yra didžiausias jo stulpelyje. Jei tokio elemento nerasta, tada antroji eilutė tikrinama taip pat. Jei toks elementas randamas antroje eilutėje, tai yra balnas.
Balno elemento radimas, jei toks yra, baigia sprendimo paieškos procesą, nes šiuo atveju buvo rasta žaidimo kaina – balno elementas ir balno taškas, t. y. grynų strategijų pora pirmajam ir antrasis žaidėjas, sudarantis optimalias grynąsias strategijas. Jei grynosiose strategijose balno taško nėra, tai mišriose strategijose reikia rasti balno tašką, kuris būtinai egzistuoja pagal pagrindinę matricinių žaidimų teoremą.
Pažymime x = (x 1 , x 2), y = (y 1 , y 2) atitinkamai pirmojo ir antrojo žaidėjų mišrias strategijas. Prisiminkite, kad x 1 reiškia tikimybę, kad pirmasis žaidėjas pasinaudos savo pirmąja strategija, o x 2 = 1 – x 1 yra tikimybė, kad jis pasinaudos savo antrąja strategija. Panašiai ir antrajam žaidėjui: 1 yra tikimybė, kad jis pasinaudos pirmąja strategija, 2 = 1 – 1 yra tikimybė, kad jis naudos antrąją strategiją.
Remiantis teoremos išvadomis, kad mišrios strategijos x ir y būtų optimalios, būtina ir pakanka, kad neneigiamiems x 1, x 2, y 1, y 2 galiotų šie ryšiai:
Dabar parodykime, kad jei matricos žaidimas neturi balno taško grynosiose strategijose, tada šios nelygybės turi virsti lygybėmis:
Iš tikrųjų. Tegul žaidimas neturi balno taško grynose strategijose, tada optimalios mišrių strategijų vertės patenkina nelygybes
0<<1, 0<< 1,
0< <1, 01. (1.25)
Tarkime, kad abi nelygybės iš (1.22) yra griežtos
tada pagal teoremą y 1 = y 2 = 0, o tai prieštarauja sąlygoms (1.25).
Panašiai įrodyta, kad abi nelygybės iš (1.23) negali būti griežtos nelygybės.
Tarkime, kad viena iš nelygybių (1.22) gali būti griežta, pavyzdžiui, pirmoji
Tai reiškia, kad pagal teoremą y 1 = 0, y 2 = 1. Vadinasi, iš (1.23) gauname
Jei abi nelygybės (1.24) yra griežtos, tai pagal teoremą x 1 = x 2 = 0, o tai prieštarauja (1.25). Jei 12 a 22, tai viena iš nelygybių (1,27) yra griežta, o kita yra lygybė. Be to, lygybė galios didesniam 12 ir 22 elementui, ty viena nelygybė iš (1.27) turi būti griežta. Pavyzdžiui, 12< а 22 . Тогда справедливо а 12 < v, а это равносильно тому, что первое неравенство из (1.24) строгое. Тогда согласно теореме должно х 1 = 0, что противоречит условию (1.25). Если а 12 = а 22 , то оба неравенства (1.27) превращаются в равенства и тогда можно положить х 1 = 0, что противоречит (1.25). Итак, предположение о том, что первое неравенство из (1.22) может быть строгим, не справедливо. Аналогично можно показать, что второе неравенство из (1.22) также не может быть строгим.
Taigi parodoma, kad jei matricinis žaidimas neturi balno taško grynosiose strategijose, tai optimalioms pirmojo žaidėjo strategijoms nelygybės (1.22) virsta lygybėmis. Panašūs samprotavimai dėl nelygybių (1.23) lems, kad šiuo atveju nelygybės (1.23) turi būti lygybės.
Taigi, jei 22 eilės matricinis žaidimas neturi balno taško, tai optimalias žaidėjų mišrias strategijas ir žaidimo kainą galima nustatyti sprendžiant lygčių sistemą (1.24). Taip pat nustatyta, kad jei matriciniame žaidime eilės 2x2 vienas iš žaidėjų turi optimalią grynąją strategiją, tai kitas žaidėjas taip pat turi optimalią grynąją strategiją.
Vadinasi, jei matricos žaidimas neturi balno taško grynosiose strategijose, tai jis turi turėti sprendimą mišriose strategijose, kurios nustatomos iš (1.24) lygčių. Sistemos (1.25) sprendimas
1.4 Algebrinis metodas
Yra du galimi problemų sprendimo atvejai naudojant algebrinį metodą:
1. matrica turi balno tašką;
2. matrica neturi balno taško.
Pirmuoju atveju sprendimas yra strategijų pora, kuri sudaro žaidimo balno tašką. Panagrinėkime antrąjį atvejį. Čia reikia ieškoti mišrių strategijų sprendimų:
Raskime strategijas ir... Kai pirmasis žaidėjas naudoja savo optimalią strategiją, antrasis žaidėjas gali, pavyzdžiui, taikyti dvi tokias grynas strategijas
Be to, dėl savybės, jei vienas iš žaidėjų naudoja optimalią mišrią strategiją, o kitas naudoja bet kokią gryną strategiją, įtrauktą į jo optimalią mišrią strategiją, kurios tikimybė nėra lygi nuliui, tada matematinis laimėjimo lūkestis visada išlieka nepakitęs ir lygus. prie žaidimo kainos, t.y.
Laimėjimas kiekvienu iš šių atvejų turi būti lygus žaidimo V kainai. Šiuo atveju galioja šie santykiai:
Antrojo žaidėjo optimaliai strategijai galima sukurti lygčių sistemą, panašią į (2.5), (2.6):
Atsižvelgiant į normalizavimo sąlygą:
Išspręskime lygtį (1.37) - (1.41) kartu nežinomųjų atžvilgiu, galime išspręsti ne visus iš karto, o po tris: atskirai (1.36), (1.38), (1.40) ir (1.37), ( 1,39), (1,41). Dėl sprendimo gauname:
1.5 Grafinis metodas
Apytikslį 22 žaidimo sprendimą galima gauti gana paprastai naudojant grafinį metodą. Jo esmė yra tokia:
1.1 pav. – vienetinio ilgio atkarpos radimas
Pasirinkite vieneto ilgio atkarpą x ašyje. Kairysis jo galas pavaizduos pirmąją pirmojo žaidėjo strategiją, o dešinysis – antrojo žaidėjo strategiją. Visi tarpiniai taškai atitinka mišrias pirmojo žaidėjo strategijas, o segmento ilgis į dešinę nuo taško yra lygus tikimybei panaudoti pirmąją strategiją, o segmento ilgis kairėje yra tikimybė panaudoti antroji pirmojo žaidėjo strategija.
Nubrėžtos dvi ašys I-I ir II-II. Laimėjimą skirsime I-I, kai pirmasis žaidėjas naudoja pirmąją strategiją, II-II, kai naudoja antrąją strategiją. Pavyzdžiui, tegul antrasis žaidėjas taiko savo pirmąją strategiją, tada vertė turi būti pavaizduota I-I ašyje, o vertė turi būti pavaizduota II-II ašyje
Taikant bet kokią mišrią pirmojo žaidėjo strategiją, jo atlyginimas bus nustatomas pagal segmento vertę. I-I eilutė atitinka antrojo žaidėjo pirmosios strategijos taikymą; mes ją vadinsime pirmąja antrojo žaidėjo strategija. Panašiai galite sukurti antrąją antrojo žaidėjo strategiją. Tada apskritai žaidimo matricos grafinis vaizdas bus tokia forma:
1.2 pav. – žaidimo kainos radimas
Tačiau reikia pažymėti, kad ši konstrukcija buvo atlikta pirmajam žaidėjui. Čia segmento ilgis yra lygus žaidimo kainai V.
1N2 linija vadinama apatine laimėjimo riba. Čia aiškiai matosi, kad taškas N atitinka didžiausią garantuoto pirmojo žaidėjo laimėjimo sumą.
Paprastai tariant, antrojo žaidėjo strategiją taip pat galima nustatyti pagal šią figūrą, pavyzdžiui, tokiais būdais. Aš-I ašyje:
arba ant II-II ašies
Tačiau antrojo žaidėjo strategija gali būti nustatoma panašiai, kaip tai daroma pirmajam žaidėjui, t.y. sukurti tokį grafiką.
1.3 pav. – antrojo žaidėjo strategijos nustatymas
Čia 1N2 eilutė yra viršutinė nuostolių riba. Taškas N atitinka minimalų galimą antrojo žaidėjo pralaimėjimą ir lemia strategiją.
Atsižvelgiant į konkrečias matricos koeficientų vertes, grafikai gali turėti skirtingą formą, pavyzdžiui:
1.4 pav. – nustato optimalią pirmojo žaidėjo strategiją
Esant tokiai situacijai, optimali pirmojo žaidėjo strategija yra gryna:
1.6 Žaidimai 2n arba m2
2n eilės žaidimuose pirmasis žaidėjas turi 2 grynąsias strategijas, o antrasis – n grynųjų strategijų, t.y. Pirmojo žaidėjo išmokėjimo matrica yra tokia:
Jei toks žaidimas turi balno tašką, jį lengva rasti ir rasti sprendimą.
Tarkime, kad žaidimas turi balno taškų. Tada reikia rasti tokias mišrias strategijas ir atitinkamai pirmąjį ir antrąjį žaidėjus bei žaidimo kainą v, kurios tenkintų santykius:
Kadangi žaidimas neturi balno taško, nelygybė (1,54) pakeičiama nelygybėmis
Sistemoms (1.56), (1.55), (1.53) spręsti patartina naudoti grafinį metodą. Šiuo tikslu pateikiame kairiosios nelygybės pusės žymėjimą (1.53)
matricos žaidimo matematinis modelis
arba, sudėję iš (1.55) ir atlikę paprastas transformacijas, gauname
kur yra pirmojo žaidėjo vidutinė išmoka, jei jis naudoja mišrią strategiją, o antrojo žaidėjo j-oji grynoji strategija.
Pagal išraišką kiekviena reikšmė j=1, 2, …, n atitinka tiesę stačiakampėje koordinačių sistemoje.
Antrojo žaidėjo tikslas yra sumažinti pirmojo žaidėjo laimėjimą, pasirenkant jo strategijas. Todėl skaičiuojame
kur yra apatinė apribojimų aibės riba. 1.6 paveiksle funkcijos grafikas pavaizduotas stora linija.
Paskelbta http://www.allbest.ru/
1.6 pav. – funkcijų grafikas
Pirmojo žaidėjo tikslas yra maksimaliai padidinti savo laimėjimą pasirinkus, t.y. apskaičiuoti
1.6 paveiksle taškas reiškia didžiausią gautą vertę. Žaidimo kaina yra todėl, kad:
Tokiu būdu grafiškai nustatoma pirmojo žaidėjo optimali mišri strategija ir antrojo žaidėjo grynųjų strategijų pora, kurios susikirtimo vietoje sudaro tašką.1.6 paveiksle pavaizduotos antrojo žaidėjo 2 ir 3 strategijos. Tokioms strategijoms nelygybės (1,53) virsta lygybėmis. 1.6 paveiksle tai strategijos j=2, j=3.
Dabar galime išspręsti lygčių sistemą
ir tiksliai nustatyti ir reikšmes (grafiškai jos nustatomos apytiksliai). Tada sudėjus visas tų j reikšmes, kurioms jos nesudaro taško, išsprendžiant lygčių sistemą (1.56) 1.6 paveiksle parodytame pavyzdyje yra tokia sistema:
o likusią Šią sistemą galima išspręsti pasvirusiu Jei tam tikram j=j 0 antrojo žaidėjo strategijos sudaro tašką M 0 ir tada maksimali apribojimų aibių apatinės ribos reikšmė pavaizduota atkarpa, lygiagrečia ašis Šiuo atveju pirmasis žaidėjas turi be galo daug optimalių verčių ir žaidimo kainos Šis atvejis pavaizduotas 1.7 paveiksle, kur segmentas MN vaizduoja viršutines ribas, optimalios vertės yra ribose. Antrasis žaidėjas turi gryną optimalią strategiją j=j 0 .
M2 eilės matriciniai žaidimai gali būti sprendžiami ir grafiniu metodu. Pirmojo žaidėjo išmokėjimo matrica šiuo atveju turi formą
Mišrios pirmojo ir antrojo žaidėjų strategijos apibrėžiamos panašiai kaip ir 2n eilės žaidimų atveju. Tegul reikšmė nuo 0 iki 1 yra pavaizduota išilgai horizontalios ašies, o vidutinio laimėjimo vertė – išilgai vertikalios ašies, esant sąlygoms, kai pirmasis žaidėjas taiko savo grynąją i-ąją strategiją (i=1, 2, ..., m), antrasis - jo mišri strategija (y 1, 1- y 1) =y. Pavyzdžiui, kai m=4 grafiškai) gali būti pavaizduotas taip, kaip parodyta 1.7 pav.
1.7 pav. – funkcijų grafikas)
Pirmasis žaidėjas stengiasi maksimaliai padidinti savo vidutinį pelną, todėl stengiasi rasti
Funkcija pavaizduota stora linija ir nurodo viršutinę apribojimų rinkinio ribą. Antrasis žaidėjas stengiasi minimalizuoti pasirinkdamas savo strategiją, t.y. vertė atitinka
Paveiksle reikšmė pažymėta tašku. Kitaip tariant, nustatomos dvi pirmojo žaidėjo strategijos ir antrojo žaidėjo tikimybė, kai pasiekiama lygybė.
Iš paveikslo matome, kad žaidimo kaina yra taško ordinatė, tikimybė – taško abscisė. Dėl likusių grynųjų strategijų pirmojo žaidėjo optimalioje mišrioje strategijoje turi būti ().
Taigi, išsprendę sistemą (1.69), gauname optimalią antrojo žaidėjo strategiją ir žaidimo kainą. Mes randame optimalią mišrią strategiją pirmajam žaidėjui išspręsdami šią lygčių sistemą:
1.7 Matricos metodas žaidimams spręsti
Pavadinimai:
Bet kuri kvadratinė eilės matricos submatrica
Matrica(1);
Matrica perkelta į;
Matricos jungtis prie B;
- (1) matrica, gauta iš X išbraukus elementus, atitinkančius eilutes, ištrintas gavus;
- (1) matrica, gauta išbraukus elementus, atitinkančius eilutes, ištrintas gavus.
Algoritmas:
1. Pasirinkite () eilės matricos kvadratinę submatricą ir apskaičiuokite
2. Jei yra arba, tada išmeskite rastą matricą ir pabandykite kitą matricą.
3. Jei (), (), apskaičiuojame ir sudarome X ir iš ir, atitinkamose vietose pridėdami nulius.
Tikrinama, ar tenkinamos nelygybės
visiems (1,75)
ir nelygybės
visiems (1,76)
Jei vienas iš santykių nepatenkintas, tada bandome kitus. Jei visi ryšiai galioja, tai X ir reikalingi sprendiniai.
1.8 Žaidimo kainos nuoseklaus aproksimavimo metodas
Nagrinėjant žaidimo situacijas dažnai gali atsitikti taip, kad nėra poreikio gauti tikslaus žaidimo sprendimo arba dėl kokių nors priežasčių neįmanoma arba labai sunku rasti tikslią žaidimo kainos vertę ir optimalias mišrias strategijas. Tada galite naudoti apytikslius matricos žaidimo sprendimo būdus.
Apibūdinkime vieną iš šių metodų – nuoseklaus žaidimo kainos apskaičiavimo metodą. Taikant metodą apskaičiuotas skaičius didėja maždaug proporcingai išmokėjimo matricos eilučių ir stulpelių skaičiui.
Metodo esmė tokia: žaidimas daug kartų žaidžiamas mintyse, t.y. paeiliui kiekviename žaidime žaidėjas pasirenka strategiją, kuri jam suteikia didžiausią bendrą (bendrą) laimėjimą.
Po tokio kai kurių žaidimų įgyvendinimo apskaičiuojama pirmojo žaidėjo laimėjimų ir antrojo žaidėjo nuostolių vidutinė vertė, o jų aritmetinis vidurkis imamas kaip apytikslis žaidimo kainos dydis. Metodas leidžia rasti apytikslę abiejų žaidėjų optimalių mišrių strategijų reikšmę: reikia apskaičiuoti kiekvienos grynosios strategijos taikymo dažnumą ir priimti jį kaip apytikslę reikšmę atitinkamo žaidėjo optimalioje mišrioje strategijoje.
Galima įrodyti, kad neribotai padidėjus programinių žaidimų skaičiui, pirmojo žaidėjo vidutinis pelnas ir antrojo žaidėjo vidutinis praradimas neribotą laiką priartės prie žaidimo kainos, o apytikslės mišrių strategijų vertės. tuo atveju, kai žaidimas turi unikalų sprendimą, bus linkęs į optimalias mišrias kiekvieno žaidėjo strategijas. Apskritai, apytikslių verčių, viršijančių šias reikšmes, tendencija artėti prie tikrųjų verčių yra lėta. Tačiau šį procesą lengva mechanizuoti ir taip padėti gauti reikiamo tikslumo žaidimo sprendimą net ir naudojant santykinai didelės išmokos matricas.
2. Praktinė dalis
Pora nusprendžia, kur eiti pasivaikščioti ir abiem naudingai praleisti laiką.
Mergina nusprendžia eiti pasivaikščioti į parką pakvėpuoti grynu oru, o vakare pažiūrėti filmą artimiausiame kino teatre.
Vaikinas siūlo nueiti į technologijų parką, o tada centriniame stadione pažiūrėti vietinių klubų futbolininkų rungtynes.
Atsižvelgdami į tai, turite sužinoti, kiek laiko užtruks, kad pasiektumėte vieno iš žaidėjų tikslą. Laimėjusi matrica atrodys taip:
1 lentelė. Išmokėjimo matrica
|
Strategijos |
||||
Kadangi 1 2 , Akivaizdu, kad grynosios strategijos šis žaidimas neturi balno taško. Todėl naudojame šias formules ir gauname:
Paskelbta http://www.allbest.ru/
2.2 Žaidimas 2xn ir mx2
1 problema (2xn)
Dvi grūdinės kultūros auginamos sausam ir drėgnam klimatui.
O gamtos būklę galima laikyti: sausa, šlapia, vidutinė.
Paskelbta http://www.allbest.ru/
Didžiausia M() reikšmė pasiekiama taške M, kurį sudaro tiesių, atitinkančių j=1, j"=2, sankirta. Pagal tai darome prielaidą:
2 problema (mx2)
Vaikinas ir mergina svarsto variantus, kur vykti savaitgalį.
Atostogų vietos pasirinkimą galima įsivaizduoti taip: parkas, kino teatras, restoranas.
Paskelbta http://www.allbest.ru/
Didžiausia M() reikšmė pasiekiama taške E, kurį sudaro tiesių, atitinkančių j=1, j"=2, sankirta. Pagal tai darome prielaidą:
Norint nustatyti v reikšmę, reikia išspręsti šias lygtis:
2.5 Matricos metodas
Du tarpusavyje konkuruojantys restoranai (maitinimo įstaigos) teikia šiuos paslaugų kompleksus. Pirmasis restoranas yra centre, o kitas – miesto pakraštyje.
Centriniame restorane teikiamos šios paslaugos:
1) brangesnis ir kokybiškesnis klientų aptarnavimas;
2) patiekalai orientuoti į prancūzų virtuvę;
Antrasis restoranas siūlo:
1) nebrangi ir kokybiška paslauga;
2) meniu sujungiamos įvairios žinomos pasaulio virtuvės;
3) taip pat nuolatinės akcijos ir nuolaidos;
4) pristato ir priima užsakymus pristatymui į namus.
Pagal užduotį vienos dienos pelnas tarp dviejų restoranų bus paskirstytas taip:
2 lentelė. Išmokėjimo matrica
|
Strategijos |
||||||
Formos žaidimo sprendimas matricos metodu:
Yra šešios submatricos ir:
Apsvarstykite matricą:
x 1 = ? 0, x 2 = ? 0
Kadangi x 2 =< 0, то мы отбрасываем.
Dabar panagrinėkime matricą:
x 1 = ? 0, x 2 = ? 0
Žaidimo kaina.
Šis santykis prieštarauja reikalavimui, todėl nėra tinkamas.
Dabar panagrinėkime matricą:
x 1 = , x 2 = ? 0,
y 1 =< 0, y 2 = ? 0.
Kadangi y 1 =< 0, то мы отбрасываем и.
Dabar panagrinėkime matricą:
x 1 = , x 2 = 0, nes x 2 = 0, tada atmetame ir.
Dabar panagrinėkime matricą:
x 1 = , x 2 = ? 0. Kadangi x 1 = 0, atmetame ir.
Dabar panagrinėkime matricą:
x 1 = , x 2 =, y 1 = , y 2 =, tada tęsiame toliau:
x 1 = , x 2 = , y 1 = , y 2 = arba
Žaidimo kaina.
Dabar tikrinami pagrindiniai santykiai:
Paskelbta http://www.allbest.ru/
Atsakymas: x 1 = , x 2 =, y 1 = , y 2 = , y 3 =0, y 4 =0,.
Rudas metodas
Tam tikros įmonės darbuotojų prašymu profesinė sąjunga derasi su savo vadovybe dėl karštų pietų organizavimo įmonės lėšomis. Darbuotojams atstovaujanti profesinė sąjunga nori užtikrinti, kad pietūs būtų kuo kokybiškesni ir dėl to brangesni. Įmonės vadovybė turi priešingų interesų. Galiausiai šalys susitarė dėl to. Profesinė sąjunga (žaidėjas 1) pasirenka vieną iš trijų įmonių (A 1, A 2, A 3), tiekiančių karštą maistą, o įmonės vadovybė (2 žaidėjas) pasirenka patiekalų komplektą iš trijų galimų variantų (B 1, B 2). , B 3) . Pasirašiusi sutartį, sąjunga sugeneruoja tokią mokėjimo matricą, kurios elementai atspindi patiekalų komplekto kainą:
Tegul žaidimą apibrėžia tokia išmokėjimo matrica:
Tarkime, kad antrasis žaidėjas pasirinko savo 2-ąją strategiją, tada pirmasis gaus:
2, jei jis naudoja savo 1-ąją strategiją,
3, jei jis naudoja savo 3 strategiją.
Gautos reikšmės apibendrintos 1 lentelėje.
3 lentelė. Antrojo žaidėjo strategija
|
Partijos numeris |
2 žaidėjo strategija |
1 žaidėjo pergalė |
|||
Iš 3 lentelės matyti, kad naudojant 2-ąją antrojo žaidėjo strategiją pirmasis gaus didžiausią laimėjimą 3, naudodamas savo 2 arba 3 strategiją. Kadangi pirmasis žaidėjas nori gauti didžiausią laimėjimą, jis į antrojo žaidėjo 2-ąją strategiją atsako savo 2-ąja strategija. Taikant 2-ąją pirmojo žaidėjo strategiją, antrasis pralaimės:
1, jei jis naudoja savo 1-ąją strategiją,
3, jei jis naudoja savo antrąją strategiją,
4, jei jis naudoja savo 3 strategiją.
4 lentelė. Pirmojo žaidėjo strategija
|
Partijos numeris |
1-ojo žaidėjo strategija |
2 žaidėjas pralaimi |
|||
Iš 2 lentelės matyti, kad taikant 2-ąją pirmojo žaidėjo strategiją, antrasis žaidėjas turės mažiausią nuostolį 1, jei taikys savo 1-ąją strategiją. Kadangi antrasis žaidėjas nori prarasti mažiau, reaguodamas į pirmojo žaidėjo 2-ąją strategiją, jis naudos savo 1-ąją strategiją. Gauti rezultatai apibendrinti 5 lentelėje.
5 lentelė. Pirmojo ir antrojo žaidėjų strategijos atitinkamai
|
Partijos numeris |
2 žaidėjo strategija |
Bendras 1-ojo žaidėjo laimėjimas |
1-ojo žaidėjo strategija |
|||||||||
Lentelėje 5 antrojo žaidėjo strategijos stulpelyje antroje eilutėje yra skaičius 1, kuris rodo, kad antrame žaidime antrajam žaidėjui naudinga naudoti savo 1-ąją strategiją; stulpelyje yra didžiausias pirmojo žaidėjo laimėjimo vidurkis, kurį jis gavo per pirmąjį žaidimą; w stulpelyje pateikiamas mažiausias vidutinis pralaimėjimas 1, kurį gavo antrasis žaidėjas pirmame žaidime; v stulpelyje yra aritmetinis vidurkis v = (u + w) – t.y. apytikslė žaidimo kainos, gautos pralaimėjus vieną žaidimo partiją, vertė. Jei antrasis žaidėjas taiko savo 1-ąją strategiją, tada pirmasis gaus atitinkamai 3, 1, 2 pagal savo 1-ą, 2-ą, 3-ią strategiją, o bendras pirmojo žaidėjo abiejų žaidimų laimėjimas bus:
2 + 3 = 5 su savo pirmąja strategija,
3 + 1 = 4 su savo 2 strategija,
3 + 2=5 su savo 3 strategija.
Šie bendri laimėjimai įrašomi antroje lentelės eilutėje. 3 ir stulpeliuose, atitinkančiuose pirmojo žaidėjo strategijas: 1, 2, 3.
Iš visų bendrų laimėjimų didžiausias yra 5. Jis gaunamas naudojant 1 ir 3 pirmojo žaidėjo strategijas, tada jis gali pasirinkti bet kurią iš jų; Tarkime, tokiais atvejais, kai yra du (ar keli) vienodi bendri laimėjimai, rinkitės strategiją su mažiausiu skaičiumi (mūsų atveju reikia imtis 1-osios strategijos).
Taikant 1-ąją pirmojo žaidėjo strategiją, antrasis atitinkamai pralaimi 3, 2, 3 savo 1-ajai, 2-ajai, 3-iajai strategijoms, o bendras antrojo žaidėjo pralaimėjimas abiem žaidimams bus:
1 + 3 = 4 su savo pirmąja strategija,
3 + 2 = 5 su savo 2 strategija,
4 + 3=7 su savo 3 strategija.
Šie bendri nuostoliai įrašyti antroje lentelės eilutėje. 5 ir stulpeliuose, atitinkančiuose antrojo žaidėjo 1, 2, 3 strategijas.
Iš visų antrojo žaidėjo pralaimėjimų mažiausias yra 4. Jis gaunamas naudojant jo 1-ąją strategiją, todėl trečiajame žaidime antrasis žaidėjas turi taikyti savo 1-ąją strategiją. Stulpelyje įrašomas didžiausias pirmojo žaidėjo bendrasis laimėjimas per du žaidimus, padalintas iš lošimų skaičiaus, t.y.; Stulpelyje w pateikiamas mažiausias bendras antrojo žaidėjo pralaimėjimas per du žaidimus, padalytas iš žaidimų skaičiaus, t.y.; v stulpelyje pateikiamas šių reikšmių aritmetinis vidurkis, t.y. = Šis skaičius yra apytikslė žaidimo su dviem „žaistus“ žaidimais kainos vertė.
Taigi gaunama tokia 4 lentelė dviem žaidimams.
6 lentelė. Žaidėjų bendri laimėjimai ir pralaimėjimai po dviejų sužaistų partijų
|
2 žaidėjo strategija |
Bendras 1-ojo žaidėjo laimėjimas |
1-ojo žaidėjo strategija |
Visiškas antrojo žaidėjo praradimas |
|||||||||
Trečioje 6 lentelės eilutėje antrojo žaidėjo strategijos stulpelyje yra skaičius 1, kuris rodo, kad trečiajame žaidime antrasis žaidėjas turi taikyti savo 1-ąją strategiją. Tokiu atveju pirmasis žaidėjas laimi 3, 1, 2, naudodamas atitinkamai 1, 2 ir 3 strategijas, o jo bendri laimėjimai per tris žaidimus bus:
3 + 5 = 8 su savo pirmąja strategija,
1 + 4 = 5 su jo 2 strategija,
2 + 5 = 7 su savo 3 strategija.
Šie bendri pirmojo žaidėjo laimėjimai įrašomi į trečią 6 lentelės eilutę ir jo strategijas atitinkančius stulpelius 1, 2, 3. Kadangi taikant 1 strategiją gaunamas didžiausias bendras pirmojo žaidėjo laimėjimas 8, pasirenkamas 1-asis. atitinkamai.
Taikant 1-ąją pirmojo žaidėjo strategiją, antrasis pralaimės atitinkamai 3, 1, 2 savo 1, 2, 3 strategijoms, o bendras antrojo žaidėjo pralaimėjimas abiem žaidimams bus:
3 + 4 = 7 su savo pirmąja strategija,
2 + 5 = 7 su savo 2 strategija,
3 + 7 = 10 su jo 3 strategija.
Šie bendri nuostoliai fiksuojami trečioje lentelės eilutėje. 6 ir stulpeliuose, atitinkančiuose antrojo žaidėjo 1, 2, 3 strategijas. Iš visų jo pralaimėjimų 7 yra mažiausi ir gaunami taikant 1 ir 2 strategijas, tada antrasis žaidėjas turi taikyti savo 1 strategiją.
Lentelėje 6 trečioje stulpelio eilutėje ir įrašo didžiausią bendro pirmojo žaidėjo laimėjimą per tris žaidimus, padalijus iš lošimo skaičiaus, t.y.; w stulpelyje įrašomas mažiausias antrojo žaidėjo bendras pralaimėjimas per tris partijas, padalytas iš partijų skaičiaus, t.y.; v stulpelyje yra jų aritmetinis vidurkis
Taip gauname stalą. 7 už tris rungtynes.
7 lentelė. Žaidėjų bendri laimėjimai ir pralaimėjimai po trijų sužaistų partijų
|
Partijos numeris |
2 žaidėjo strategija |
Bendras 1-ojo žaidėjo laimėjimas |
1-ojo žaidėjo strategija |
Visiškas antrojo žaidėjo praradimas |
||||||||
8 lentelė. Galutinis stalas po dvidešimties sužaistų partijų
|
Partijos numeris |
2 žaidėjo strategija |
Bendras 1-ojo žaidėjo laimėjimas |
1-ojo žaidėjo strategija |
Visiškas antrojo žaidėjo praradimas |
||||||||
Nuo stalo 7 ir 8 matyti, kad 20 pralaimėtų žaidimų 1, 2, 3 strategijos pirmajam žaidėjui pasitaiko atitinkamai 12, 3, 5 kartus, todėl jų santykinis dažnis yra atitinkamai vienodas; 1, 2, 3 strategijos antrajam žaidėjui pasitaiko atitinkamai 7, 11,2 kartus, todėl jų santykiniai dažniai yra atitinkamai vienodi; apytikslė žaidimo kaina. Ši aproksimacija yra gana gera.
Galiausiai atkreipkite dėmesį, kad jei žaidime yra daugiau nei vienas sprendimas, žaidimo kainos apytikslės apytikslės vis tiek neribotą laiką apytiksliai atitiks tikrąją žaidimo kainą, o žaidėjų strategijų santykiniai dažniai nebūtinai atitiks žaidėjų tikrąjį optimalų mišinį. strategijos.
Rezultatų analizė
Šiame kursiniame darbe nagrinėjome nulinės sumos žaidimų sprendimų paieškos grafiniu, matriciniu metodu ir žaidimo kainos nuoseklaus aproksimavimo metodu medžiagą. Rastos optimalios pirmojo ir antrojo žaidėjų strategijos bei žaidimo kaštai žaidimuose 2x2, 2xn ir mx2, taip pat žaidimuose naudojant matricos metodą ir Browno metodą.
Naudojant poros pavyzdį, buvo imituojamas 2x2 žaidimas, kuris buvo sprendžiamas algebriniais ir grafiniais metodais. Išsprendus žaidimą algebriškai, sprendimas rodo, kad naudojant optimalias mišrias strategijas, pirmasis ir antrasis žaidėjai kartu praleis 4,6 valandos. Grafinis problemos sprendimas gautas su nedidele klaida ir siekė 4,5 val.
Taip pat buvo imituojamos dvi problemos 2xn ir mx2. 2xn užduotyje buvo svarstoma žemės ūkio kultūra ir strategija rodo, kad geriau sodinti lauką nuo 50 iki 50, o žaidimo kaina buvo 3,75 mln. O problemoje mx2 buvo svarstoma pora, kurios strategija parodė, kad pigiau nueiti į parką ir kiną, o kaina būtų 4,3 rublio.
Matricos metodui buvo sumodeliuota problema, kurioje buvo nagrinėjami du restoranai, problemos sprendimas parodė, kad naudojant optimalią mišrią strategiją pirmojo restorano pelnas bus 15,6 mln. rublių, o naudojant optimalią mišrią strategiją antrasis restoranas, jis neleis pirmajam uždirbti daugiau nei 15,6 mln. Dėl grafinio sprendimo įvyko klaida ir žaidimo kaina siekė 14,9 mln.
Browno metodui buvo sudaryta užduotis, kurioje svarstoma profesinė sąjunga ir įmonės vadovybė, jų užduotis – aprūpinti darbuotojus maistu. Jei abu žaidėjai naudos savo optimalias strategijas, maistas vienam asmeniui bus 2,45 tūkst.
Naudotų šaltinių sąrašas
1) Vilisovas V.Ya. Paskaitų konspektas „Žaidimų teorija ir statistiniai sprendimai“, - Filialas - „Voskhod“ MAI. 1979. 146 p.
2) Kruševskis A.V. Žaidimo teorija, - Kijevas: Vishcha mokykla, 1977. - 216 p.
3) Churchmen U., Akof R., Arnof L., Operacijų tyrimo įvadas. - M.: Mokslas. 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
Paskelbta Allbest.ru
Panašūs dokumentai
Sprendimų priėmimas kaip ypatinga žmogaus veiklos rūšis. Racionalus žaidimo matricos vaizdavimas. Matricinių žaidimų pavyzdžiai grynomis ir mišriomis strategijomis. Operacijų tyrimas: tiesinio programavimo problemų ryšys su žaidimo teoriniu modeliu.
kursinis darbas, pridėtas 2010-05-05
Daug kartų kartojami žaidimai, jų išskirtinės savybės ir etapai. Mišrios strategijos, sąlygos ir jų panaudojimo praktikoje galimybės. Analitinis 2 x 2 tipo žaidimo sprendimo metodas. Stačiakampių žaidimų pagrindinės teoremos. Algebriniai sprendimai.
pristatymas, pridėtas 2013-10-23
Pagrindiniai bimatricinių žaidimų teorijos apibrėžimai. Bimatricinio žaidimo „Mokinys – mokytojas“ pavyzdys. Mišrios strategijos bimatrix žaidimuose. Ieškokite „pusiausvyros situacijos“. 2x2 bimatriciniai žaidimai ir formulės tuo atveju, kai kiekvienas žaidėjas turi dvi strategijas.
santrauka, pridėta 2011-02-13
Sužinokite bendrąją informaciją apie matricinius ir nulinės sumos žaidimus. Pozicinio žaidimo samprata, medis, informacijos rinkinys. Maksimino principo ir pusiausvyros principo svarstymas. Pareto optimalumas. Pozicinis neantagonistinis žaidimas, jo savybės.
kursinis darbas, pridėtas 2014-10-17
Žaidimų teorija yra matematikos šaka, kurios dalykas yra matematinių modelių, leidžiančių priimti optimalius sprendimus konflikto sąlygomis, tyrimas. Iteracinis Brown-Robinson metodas. Monotoninis iteracinis algoritmas, skirtas matriciniams žaidimams spręsti.
baigiamasis darbas, pridėtas 2007-08-08
Mokėjimo matricos sudarymas, apatinės ir viršutinės žaidimo neto kainos, žaidėjų maximin ir minimax strategijų paieška. Mokėjimo matricos supaprastinimas. Matricinio žaidimo sprendimas naudojant linijinio programavimo problemos redukciją ir priedą „Ieškoti sprendimo“.
testas, pridėtas 2014-11-10
Žaidimo teorija yra matematinė konfliktinių situacijų teorija. Dviejų asmenų nulinės sumos žaidimo matematinio modelio sukūrimas, jo įgyvendinimas programų kodų pavidalu. Problemos sprendimo būdas. Įvesties ir išvesties duomenys. Programa, vartotojo vadovas.
kursinis darbas, pridėtas 2013-08-17
Pagrindinė informacija apie simplekso metodą, jo vaidmens ir reikšmės linijiniame programavime įvertinimas. Geometrinė interpretacija ir algebrinė reikšmė. Tiesinės funkcijos maksimumo ir minimumo radimas, ypatingi atvejai. Problemos sprendimas naudojant matricos simplekso metodą.
baigiamasis darbas, pridėtas 2015-06-01
Kompiuterinių sistemų matematinių modelių, atspindinčių jų veikimo struktūrą ir procesus, konstravimo būdai. Prieigų prie failų skaičius sprendžiant vidutinę problemą. Galimybės įdėti failus į išorinius atminties įrenginius nustatymas.
laboratorinis darbas, pridėtas 2013-06-21
Matematinio modelio projektavimas. „Tic-tac-toe“ žaidimo aprašymas. Loginio žaidimo modelis, pagrįstas Būlio algebra. Skaitmeniniai elektroniniai prietaisai ir jų matematinio modelio kūrimas. Žaidimų konsolė, žaidimų valdiklis, žaidimo lauko linija.