Matriciniai žaidimai: problemų sprendimo pavyzdžiai. Antagonistiniai žaidimai su nuolatinėmis strategijomis b) ne visada

Įvadas

Tikros konfliktinės situacijos veda į įvairius žaidimus. Žaidimai skiriasi įvairiais būdais: pagal juose dalyvaujančių žaidėjų skaičių, galimų žaidėjų skaičių, galimų strategijų skaičių, žaidėjų tarpusavio santykių pobūdį, laimėjimų pobūdį, žaidimo tipą. laimėjimo funkcijos, pagal ėjimų skaičių, žaidėjų informavimo pobūdį ir pan. .d. Panagrinėkime žaidimų tipus, atsižvelgiant į jų skirstymą:

· Pagal strategijų skaičių žaidimai skirstomi į galutinis(kiekvienas žaidėjas turi ribotą skaičių galimų strategijų) ir begalinis(kai bent vienas iš žaidėjų turi begalinį galimų strategijų skaičių).

· Pagal laimėjimų pobūdį žaidimai su nulinė suma(bendras žaidėjų kapitalas nesikeičia, o perskirstomas tarp žaidėjų priklausomai nuo rezultatų) ir žaidimai su ne nulinė suma.

· Pagal funkcijų tipą žaidimo laimėjimai skirstomi į matrica ( yra baigtinis dviejų žaidėjų nulinės sumos žaidimas, kuriame suteikiamas žaidėjo atlyginimas A matricos pavidalu (matricos eilutė atitinka žaidėjo naudojamos strategijos skaičių IN, stulpelis – žaidėjo naudojamos strategijos numeris IN; matricos eilutės ir stulpelio sankirtoje yra žaidėjo laimėjimas A, atitinkančias taikomas strategijas.

Matriciniams žaidimams įrodyta, kad bet kuris iš jų turi sprendimą, ir jį galima lengvai rasti sumažinus žaidimą iki linijinio programavimo problemos). bimatricažaidimas (tai baigtinis dviejų žaidėjų žaidimas su ne nuline suma, kuriame kiekvieno žaidėjo laimėjimai pateikiami matricomis atskirai atitinkamam žaidėjui (kiekvienoje matricoje eilutė atitinka žaidėjo strategiją A, stulpelis – žaidėjų strategijos IN, pirmosios matricos eilutės ir stulpelio sankirtoje yra žaidėjo išmokėjimas A, antroje matricoje – žaidėjo laimėjimai IN.

Bimatriciniams žaidimams taip pat sukurta optimalaus žaidėjo elgesio teorija, tačiau tokius žaidimus išspręsti yra sunkiau nei įprastus matricinius žaidimus. tęstinisžaidimai ( Nuolatinis Tai laikomas žaidimu, kuriame kiekvieno žaidėjo išmokėjimo funkcija yra nuolatinė, priklausomai nuo strategijų. Įrodyta, kad šios klasės žaidimai turi sprendimus, tačiau nėra sukurta praktiškai priimtinų metodų jiems surasti) ir kt.

Galimi ir kiti žaidimo padalijimo būdai. Dabar grįžkime tiesiai prie tyrimo temos, būtent prie žaidimų teorijos. Pirmiausia apibrėžkime šią sąvoką.

Žaidimo teorija - matematikos šaka, tirianti formalius optimalių sprendimų priėmimo konflikto sąlygomis modelius. Šiuo atveju konfliktas suprantamas kaip reiškinys, kuriame dalyvauja įvairios šalys, apdovanotos skirtingais interesais ir galimybėmis pagal šiuos interesus pasirinkti joms prieinamus veiksmus kilti iki netikrumo. Priešingai, neapibrėžtumas priimant sprendimus (pavyzdžiui, remiantis nepakankamais duomenimis) gali būti interpretuojamas kaip konfliktas tarp sprendimą priimančio subjekto ir prigimties. Todėl žaidimų teorija taip pat laikoma optimalių sprendimų priėmimo neapibrėžtumo sąlygomis teorija. Tai leidžia susisteminti kai kuriuos svarbius technologijų, žemės ūkio, medicinos ir sociologijos bei kitų mokslų sprendimų priėmimo aspektus. Konflikto šalys vadinamos veiksmų koalicija; jiems prieinamus veiksmus – pagal savo strategijas; galimos konflikto baigtys – situacijos.

Teorijos tikslas yra toks:

1) optimalus elgesys žaidime.

2) optimalaus elgesio savybių tyrimas

3) nustatant sąlygas, kuriomis jo naudojimas yra prasmingas (egzistencijos, unikalumo, o dinamiškiems žaidimams – vardinio nuoseklumo klausimai).

4) skaitmeninių metodų optimaliam elgesiui rasti konstravimas.

Žaidimų teorija, sukurta ekonominės ir socialinės kilmės problemų matematiniam sprendimui, apskritai negali būti redukuojama į klasikines matematines teorijas, sukurtas fizinėms ir techninėms problemoms spręsti. Tačiau sprendžiant įvairius specifinius žaidimų teorijos klausimus plačiai naudojami įvairūs klasikiniai matematiniai metodai.

Be to, žaidimų teorija yra iš vidaus susijusi su daugybe matematinių disciplinų. Žaidimų teorijoje tikimybių teorijos sąvokos vartojamos sistemingai ir iš esmės. Žaidimų teorijos kalba galima suformuluoti daugumą matematinės statistikos problemų, o kadangi žaidimų teorija yra susijusi su sprendimų priėmimo teorija, ji laikoma esminiu operacijų tyrimo matematinio aparato komponentu.

Matematinė žaidimo samprata yra neįprastai plati. Tai apima vadinamuosius saloninius žaidimus (įskaitant šachmatus, šaškes, GO, kortų žaidimus, domino), bet taip pat gali būti naudojamas apibūdinti ekonominės sistemos modelius, kuriuose daug pirkėjų ir pardavėjų konkuruoja tarpusavyje. Nesileidžiant į smulkmenas, žaidimą galima plačiai apibrėžti kaip situaciją, kai vienas ar keli asmenys („žaidėjai“) kartu valdo daugybę kintamųjų ir kiekvienas žaidėjas, priimdamas sprendimą, turi atsižvelgti į visos grupės veiksmus. Kiekvienam žaidėjui tenkantį „mokėjimą“ lemia ne tik jo paties, bet ir kitų grupės narių veiksmai. Kai kurie „judesiai“ (individualūs veiksmai) žaidimo metu gali būti atsitiktiniai. Aiški iliustracija yra garsusis pokerio žaidimas: pradinis kortų dalijimas yra atsitiktinis ėjimas. Lažybų ir priešinių statymų seka prieš galutinį triukų palyginimą susidaro iš likusių žaidimo ėjimų.

Matematinė ŽAIDIMŲ TEORIJA prasidėjo nuo sportinių, kortų ir kitų žaidimų analizės. Jie sako, kad žaidimų teorijos atradėjas, puikus XX amžiaus amerikiečių matematikas. Johnas von Neumannas savo teorijos idėjas sugalvojo žiūrėdamas pokerio žaidimą. Iš čia kilęs pavadinimas „žaidimų teorija“.

Pradėkime tyrinėti šią temą nuo retrospektyvinė žaidimų teorijos raidos analizė. Panagrinėkime žaidimų teorijos klausimo istoriją ir raidą. Paprastai „šeimos medis“ grafų teorijos prasme vaizduojamas kaip medis, kuriame šaka atsiranda iš vienos „šaknies“. Žaidimų teorijos kilmė yra J. von Neumann ir O. Morgensterno knyga. Todėl istorinė žaidimų teorijos, kaip matematinės disciplinos, raidos eiga natūraliai skirstoma į tris etapus:

Pirmas lygmuo– iki J. von Neumanno ir O. Morgensterno monografijos išleidimo. Jis gali būti vadinamas „iki monografiniu“. Šiame etape žaidimas vis dar veikia kaip specifinis konkursas, prasmingai apibūdinamas jo taisyklėmis. Tik jo pabaigoje J. von Neumannas išplėtoja žaidimo, kaip bendro abstraktaus konflikto modelio, idėją. Šio etapo rezultatas buvo daugybė specifinių matematinių rezultatų ir net atskirų ateities žaidimų teorijos principų.

Antrasis etapas yra pati J. von Neumann monografija ir

O. Morgensterno „Žaidimų teorija ir ekonominis elgesys“ (1944), apjungęs daugumą anksčiau gautų (tačiau šiuolaikiniais matematiniais standartais gana nedaug) rezultatų. Ji pirmoji sisteminės teorijos forma pristatė matematinį požiūrį į žaidimus (tiek konkrečia, tiek abstrakčia šio žodžio prasme).

Galiausiai, toliau trečiasis etapasžaidimų teorija savo požiūriu į tiriamus objektus mažai skiriasi nuo kitų matematikos šakų ir didžiąja dalimi vystosi pagal joms bendrus dėsnius. Žinoma, tuo pačiu metu žaidimo teorijos krypčių formavimuisi didelę įtaką turi ir jo praktinio pritaikymo specifika, tiek aktuali, tiek galima.

Tačiau net ir matematinė žaidimų teorija negali iki galo numatyti kai kurių konfliktų baigties. Atrodo, kad galima išskirti tris pagrindines žaidimo (konflikto) baigties neapibrėžtumo priežastis.

Pirma, tai yra žaidimai, kuriuose yra reali galimybė ištirti visus arba bent jau daugumą žaidimo elgesio variantų, iš kurių vienas yra teisingiausias, vedantis į laimėjimą. Neapibrėžtumą sukelia nemažai pasirinkimų, todėl ne visada pavyksta ištirti absoliučiai visus variantus (pavyzdžiui, japoniškas žaidimas GO, rusiškos ir tarptautinės šaškės, britų reversi).

Antra, žaidėjai nenuspėja atsitiktinės veiksnių įtakos žaidimui. Šie veiksniai turi lemiamos įtakos žaidimo rezultatui ir žaidėjų gali būti kontroliuojami ir nulemti tik nedidele dalimi. Galutinį žaidimo rezultatą tik nedidele, itin nereikšminga dalimi lemia pačių žaidėjų veiksmai. Žaidimai, kurių baigtis neaiški dėl atsitiktinių priežasčių, vadinami azartiniais lošimais. Žaidimo baigtis visada yra tikimybinė arba spėlionė (ruletė, kauliukas, metimas).

Trečia, neapibrėžtumą sukelia informacijos apie tai, kokios strategijos laikosi žaidžiantis varžovas, trūkumas. Žaidėjų nežinojimas apie varžovo elgesį yra esminis ir nulemtas pačių žaidimo taisyklių. Tokie žaidimai vadinami strateginiais žaidimais.

Žaidimo teorija yra viena iš svarbių „Operacijų tyrimo“ skyrių ir atspindi matematinių modelių teorinius pagrindus, leidžiančius priimti optimalius sprendimus rinkos santykių konfliktinėse situacijose, kurios yra konkurencinio pobūdžio, kai viena priešinga šalis laimi kitą. kito nuostolių sąskaita. Kartu su šia situacija Operacijų tyrimo mokslo rėmuose, kuriame matematiškai aprašomas įvairių sprendimų priėmimo problemų formulavimas, nagrinėjamos rizikos ir neapibrėžtumo situacijos. Neapibrėžtumo situacijoje sąlygų tikimybės nežinomos ir nėra galimybės apie jas gauti papildomos statistinės informacijos. Problemos sprendimą supanti aplinka, kuri pasireiškia tam tikromis sąlygomis, vadinama „gamta“, o atitinkami matematiniai modeliai – „žaidimai su gamta“ arba „statistine žaidimų teorija“. Pagrindinis žaidimo teorijos tikslas – parengti rekomendacijas, kaip patenkinti žaidėjų elgesį konflikte, tai yra nustatyti kiekvienam iš jų „optimalią strategiją“.

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 , kur X ir Y yra atitinkamai pirmojo ir antrojo žaidėjo strategijų rinkiniai, F yra pirmojo žaidėjo išmokėjimo funkcija, kuri susieja kiekvieną strategijų porą (x, y), kur yra realusis skaičius, atitinkantis naudingumą pirmojo žaidėjo, įgyvendinančio tam tikrą situaciją.

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 žaidime yra lygi nuliui, t. y. nulinės sumos žaidime bendras visų žaidėjų kapitalas nesikeičia, o perskirstomas tarp žaidėjų, priklausomai nuo gauto dydžio. rezultatus. 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 laikomas tokiu abstrakčiu dviejų žaidėjų žaidimu.

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 išmokėjimas antrojo žaidėjo naudai, 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ėjimai, esantys 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 nuosekliai randamas matricoje A. kiekvieną eilutę ir patikrinkite, ar šis elementas yra didžiausias jos stulpelyje. Jei jis 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 tikrus laimėjimus ž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, galite 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ą, vadinsime ją antrojo žaidėjo pirmąja 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ę nesudėtingas 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 antrojo žaidėjo 2-ą ir 3-ią strategiją. 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, 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) galima pateikti 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ą. Skaičiavimų skaičius naudojant metodą 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ų nurodytas 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

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ė. Atsipirkimo matrica

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

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

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

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š žaidimų 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ų

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ų

8 lentelė. Galutinis stalas po dvidešimties sužaistų partijų

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 nebebū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: ryšys tarp tiesinio programavimo problemų ir žaidimo teorinio modelio.

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.

Apsvarstykite baigtinės nulinės sumos porų žaidimą. Pažymėkime pagal ažaidėjo laimėjimai A, ir per b– žaidėjo laimėjimai B. Nes a = –b, tuomet analizuojant tokį žaidimą nereikia svarstyti abiejų šių skaičių – pakanka atsižvelgti į vieno iš žaidėjų laimėjimą. Tegul tai būna pvz. A. Pateikimo patogumui toliau A mes tradiciškai vadinsime " Mes“ ir pusė B – "priešas".

Leiskite mums m galimos strategijos A 1 , A 2 , …, Esu, ir priešas n galimos strategijos B 1 , B 2 , …, Bn(toks žaidimas vadinamas žaidimu m×n). Tarkime, kad kiekviena pusė pasirinko tam tikrą strategiją: mes pasirinkome A i, priešininkas B j. Jei žaidimas susideda tik iš asmeninių ėjimų, tada pasirenkamos strategijos A i Ir B j unikaliai lemia žaidimo baigtį – mūsų laimėjimą (teigiamą ar neigiamą). Pažymime šį pelną a ij(nauda, ​​kai pasirenkame strategiją A i, o priešas – strategijos B j).

Jei žaidime, be asmeninių, atsitiktinių ėjimų, tada laimėjimai su strategijų pora A i, B j yra atsitiktinė reikšmė, priklausanti nuo visų atsitiktinių judesių rezultatų. Šiuo atveju natūralus numatomo atsipirkimo įvertinimas yra matematinis atsitiktinio laimėjimo lūkestis. Patogumui pažymėsime a ij tiek pats laimėjimas (žaidime be atsitiktinių ėjimų), tiek jo matematinis lūkestis (žaidime su atsitiktiniais ėjimais).

Tarkime, kad mes žinome vertybes a ij kiekvienai strategijų porai. Šios reikšmės gali būti parašytos kaip matrica, kurios eilutės atitinka mūsų strategijas ( A i), o stulpeliai – priešo strategijos ( B j):

Tokia matrica vadinama žaidimo mokėjimo matrica arba tiesiog žaidimo matrica.

Atminkite, kad žaidimų su daugybe strategijų išmokėjimo matricos kūrimas gali būti sudėtinga užduotis. Pavyzdžiui, šachmatų žaidime galimų strategijų skaičius yra toks didelis, kad sukonstruoti išmokų matricą praktiškai neįmanoma. Tačiau iš esmės bet koks baigtinis žaidimas gali būti redukuotas į matricos formą.

Pasvarstykime 1 pavyzdys antagonistinis žaidimas 4x5. Mes turime keturias strategijas, o priešas turi penkias strategijas. Žaidimo matrica yra tokia:

Kokią strategiją turėtume (t. y. žaidėjas A) naudoti? Kad ir kokią strategiją pasirinktume, protingas priešininkas atsakys strategija, kurią taikant mūsų atlygis bus minimalus. Pavyzdžiui, jei pasirenkame strategiją A 3 (gundomas laimėti 10), varžovas atsakys pasirinkdamas strategiją B 1, o mūsų atlygis bus tik 1. Akivaizdu, kad remiantis atsargumo principu (ir tai yra pagrindinis žaidimo teorijos principas), turime pasirinkti strategiją, kurioje mūsų minimalūs laimėjimai yra didžiausi.

Pažymėkime pagal α i minimali strategijos laimėjimo vertė A i:

ir pridėkite stulpelį su šiomis reikšmėmis prie žaidimo matricos:

Renkantis strategiją turėtume teikti pirmenybę ta, kurios vertė α i maksimalus. Pažymime šią didžiausią reikšmę α :

Didumas α paskambino mažesnė žaidimo kaina arba maksimalus(maksimalus minimalus laimėjimas). Žaidėjo strategija A, atitinkantis maksimalų α , paskambino maksimalios strategijos.

Šiame pavyzdyje maksim α yra lygus 3 (atitinkamas langelis lentelėje paryškintas pilkai), o maksimali strategija yra A 4 . Pasirinkę šią strategiją galime būti tikri, kad už bet kokį priešo elgesį laimėsime ne mažiau nei 3 (o gal ir daugiau, jei priešo elgesys bus „neprotingas“) Ši vertė yra mūsų garantuotas minimumas, kurį galime užtikrinti patys laikantis atsargiausios („perdraudimo“) strategijos.

Dabar atlikime panašius samprotavimus priešui B B A B 2 – mes jam atsakysime A .

Pažymėkime pagal β j A B) strategijai A i:

β j β :

7. KAS VADINAMAS AUKŠČIAUSIAI VERTYBINIU ŽAIDIMU Dabar atlikime panašius argumentus prieš varžovą B. Jis suinteresuotas sumažinti mūsų laimėjimus, tai yra, duoti mums mažiau, tačiau jis turi pasikliauti mūsų blogiausiu jo elgesiu. Pavyzdžiui, jei jis pasirenka strategiją B 1, tada mes jam atsakysime su strategija A 3 ir jis duos mums 10. Jei pasirinks B 2 – mes jam atsakysime A 2, o jis duos 8 ir tt Akivaizdu, kad atsargus varžovas turėtų pasirinkti strategiją, kurioje mūsų maksimalus laimėjimas bus minimalus.

Pažymėkime pagal β j maksimalios vertės išmokėjimo matricos stulpeliuose (maksimalus žaidėjo laimėjimas A arba, kas yra tas pats, maksimalus žaidėjo pralaimėjimas B) strategijai A i:

ir pridėkite eilutę su šiomis reikšmėmis prie žaidimo matricos:

Renkantis strategiją, priešas pirmenybę teiks tajai, kurios vertė β j minimalus. Pažymėkime tai β :

Didumas β paskambino aukščiausia žaidimo kaina arba minimalus maks(minimalus didžiausias laimėjimas). Minimax atitinkanti priešo (žaidėjo) strategija B), skambino Minimax strategija.

Minimax yra laimėjimo vertė, kurios daugiau protingas varžovas mums tikrai neduos (kitaip tariant, protingas varžovas pralaimės ne daugiau kaip β ). Šiame pavyzdyje minimax β yra lygus 5 (atitinkamas langelis lentelėje paryškintas pilkai) ir pasiekiamas naudojant priešo strategiją B 3 .

Taigi, vadovaudamiesi atsargumo principu („visada prisiimk blogiausią!“), turime pasirinkti strategiją A 4, o priešas – strategija B 3. Atsargumo principas yra esminis žaidimų teorijoje ir vadinamas Minimax principas.

Pasvarstykime 2 pavyzdys. Tegul žaidėjai A Ir IN vienu metu ir nepriklausomai vienas nuo kito užrašykite vieną iš trijų skaičių: „1“, „2“, arba „3“. Jei parašytų skaičių suma lygi, tai žaidėjas B moka žaidėjui Aši suma. Jei suma yra nelyginė, žaidėjas sumoka šią sumą Ažaidėjui IN.

Užsirašykime žaidimo mokėjimų matricą ir suraskime apatinę ir viršutinę žaidimo kainas (strategijos numeris atitinka užrašytą skaičių):

Žaidėjas A turi laikytis maximin strategijos A 1 laimėti ne mažiau kaip –3 (tai yra, pralaimėti ne daugiau kaip 3). Minimax žaidėjo strategija B– bet kuri iš strategijų B 1 ir B 2, garantuojant, kad jis duos ne daugiau kaip 4.

Tą patį rezultatą gauname, jei išmokėjimo matricą įrašome žaidėjo požiūriu IN. Tiesą sakant, ši matrica gaunama perkeliant matricą, sukurtą žaidėjo požiūriu A, o elementų ženklus keičiant į priešingą (nuo žaidėjo laimėjimo A– tai žaidėjo pralaimėjimas IN):

Remiantis šia matrica darytina išvada, kad žaidėjas B turi laikytis bet kurios iš strategijų B 1 ir B 2 (ir tada jis praras ne daugiau kaip 4), o žaidėjas A– strategijos A 1 (ir tada jis praras ne daugiau kaip 3). Kaip matote, rezultatas tiksliai sutampa su aukščiau gautu, todėl analizuojant nesvarbu, kuriam žaidėjui mes tai atliekame.

8 KAS VADINAMAS VERTYBĖS ŽAIDIMU.

9. KAS YRA MINIMAX PRINCIPAS. 2. Žemutinė ir viršutinė žaidimo kaina. Minimax principas

Apsvarstykite tokio tipo matricinį žaidimą su išmokėjimo matrica

Jei žaidėjas A pasirinks strategiją A i, tada visi galimi jo laimėjimai bus elementai i matricos eilutė SU. Blogiausia žaidėjui A atvejis, kai žaidėjas IN taiko tinkamą strategiją minimumasšios linijos elementas, žaidėjo laimėjimas A bus lygus skaičiui .

Todėl, norėdamas gauti didžiausią laimėjimą, žaidėjas A reikia pasirinkti strategiją, kuriai numeris maksimalus.

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 už matricinius žaidimus 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 pirmajam žaidėjui?

a) pirmiausia.

b) antra.

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 matricos žaidime viena iš 1-ojo žaidėjo mišrių strategijų yra formos (0,3, 0,7), o viena iš mišrių antrojo žaidėjo strategijų yra formos (0,2, x, x). . Kas yra skaičius x?

Maskvos energetikos institutas

(Technikos universitetas)

Laboratorijos ataskaita

žaidimų teorijoje

"Programa, skirta rasti optimalias strategijas suporuotam nulinės sumos žaidimui, pateiktam matricos forma"

Baigė studentai

grupė A5-01

Ašrapovas Daleris

Ašrapova Olga

Pagrindinės žaidimų teorijos sąvokos

Žaidimo teorija skirta išspręsti konfliktines situacijas , t.y. situacijos, kai susiduria dviejų ar daugiau šalių, siekiančių skirtingų tikslų, interesai.

Jei šalių tikslai yra tiesiogiai priešingi, jie kalba apie antagonistinis konfliktas .

Žaidimas vadinamas supaprastintu formalizuotu konfliktinės situacijos modeliu.

Vadinamas vienas žaidimo žaidimas nuo pradžios iki pabaigos vakarėlis . Žaidimo rezultatas yra mokėjimas (arba laimėjimai ).

Vakarėlis susideda iš juda , t.y. žaidėjų pasirinkimas iš tam tikro galimų alternatyvų rinkinio.

Judėjimai gali būti Asmeninis Ir atsitiktinis.Asmeninis judėjimas , Skirtingai nei atsitiktinis , reiškia, kad žaidėjas sąmoningai pasirenka kokį nors variantą.

Vadinami žaidimai, kuriuose yra bent vienas asmeninis ėjimas strateginis .

Vadinami žaidimai, kuriuose visi judesiai yra atsitiktiniai azartinių lošimų .

Darydami asmeninį žingsnį jie taip pat kalba apie strategijos žaidėjas, t.y. apie taisyklę ar taisyklių rinkinį, lemiantį žaidėjo pasirinkimą. Kartu strategija turi būti visapusiška, t.y. pasirinkimas turi būti nustatytas bet kuriai galimai situacijai žaidimo metu.

Žaidimo teorijos problema– ieškant optimalių strategijų žaidėjams, t.y. strategijas, kurios suteikia jiems didžiausią pelną arba minimalų nuostolį.

Žaidimų teorinių modelių klasifikacija

Žaidimas n asmenys paprastai žymimi kaip, kur
- i-ojo žaidėjo strategijų rinkinys,
- apmokėjimas už žaidimą.

Remiantis šiuo pavadinimu, galima pasiūlyti tokią žaidimų teorinių modelių klasifikaciją:

Diskretus (kelios strategijos diskretus)

Galutinis

Begalinis

Nuolatinis (kelios strategijos nuolatinis)

Begalinis

n asmenys (
)

Koalicija (kooperatyvas)

Ne koalicija (nebendradarbiaujanti)

2 asmenys (poros)

Antagonistiniai (nulinės sumos žaidimai)

(šalių interesai yra priešingi, t. y. vieno žaidėjo praradimas yra lygus kito laimėjimui)

Neantagonistinis

Su visa informacija (jei žaidėjas, atliekantis asmeninį ėjimą, žino visą žaidimo foną, t. y. visus priešininko ėjimus)

Su nepilna informacija

Su nuline suma (bendras mokėjimas lygus nuliui)

Ne nulinė suma

Vienas judesys (loterijos)

Daugkartinis praėjimas

Suporuoto nulinės sumos žaidimo matrica

Šioje pamokoje apžvelgsime dviejų asmenų antagonistiniai žaidimai , pateikta matricos forma. Tai reiškia, kad mes žinome daug pirmojo žaidėjo (žaidėjo A){ A i }, i = 1,…, m ir įvairių strategijų antrajam žaidėjui (žaidėjui B){ B j }, j = 1,..., n, taip pat pateikta matrica A = || a ij || pirmojo žaidėjo laimėjimai. Kadangi kalbame apie antagonistinį žaidimą, daroma prielaida, kad pirmojo žaidėjo pelnas yra lygus antrojo praradimui. Darome prielaidą, kad matricos elementas a ij– pirmojo žaidėjo laimėjimai, kai jis pasirenka strategiją A i o antrojo žaidėjo atsakas jam su strategija B j. Tokį žaidimą pažymėsime kaip
, Kur m - žaidėjų strategijų skaičius A,n - žaidėjų strategijų skaičius IN. Apskritai jį galima pavaizduoti šioje lentelėje:

1 pavyzdys

Kaip paprastą pavyzdį apsvarstykite žaidimą, kuriame žaidimas susideda iš dviejų ėjimų.

1 ėjimas: Žaidėjas A pasirenka vieną iš skaičių (1 arba 2), nepranešęs priešininkui apie savo pasirinkimą.

2-as ėjimas: Žaidėjas IN pasirenka vieną iš skaičių (3 arba 4).

Apatinė eilutė: Žaidėjų pasirinkimas A Ir IN sulankstyti. Jei suma lygi, tada IN sumoka savo vertę žaidėjui A, jei nelyginis - atvirkščiai, A sumoka žaidėjui sumą IN.

Šis žaidimas gali būti pateiktas formoje
tokiu būdu:

Nesunku pastebėti, kad šis žaidimas yra priešiškas, be to, tai žaidimas su nepilna informacija, nes žaidėjui IN, darydamas asmeninį ėjimą, nežinoma, kokį žaidėjo pasirinkimą padarė A.

Kaip minėta aukščiau, žaidimo teorijos uždavinys yra surasti optimalias žaidėjų strategijas, t.y. strategijas, kurios suteikia jiems didžiausią pelną arba minimalų nuostolį. Šis procesas vadinamas žaidimo sprendimas .

Spręsdami žaidimą matricos forma, turėtumėte patikrinti, ar žaidimas yra balno taškas . Norėdami tai padaryti, įvedamos dvi reikšmės:

– mažesnis žaidimo kainos įvertinimas ir

– viršutinė žaidimo kainos sąmata.

Pirmasis žaidėjas greičiausiai pasirinks strategiją, kurioje gaus maksimalų laimėjimą tarp visų galimų antrojo žaidėjo atsakymų, o antrasis žaidėjas, priešingai, pasirinks tokią, kuri sumažins jo paties nuostolius, t.y. galimas pirmojo laimėjimas.

Tai galima įrodyti α ≤ V ≤ β , Kur V–žaidimo kaina , t.y., tikėtinas pirmojo žaidėjo laimėjimas.

Jei santykis galioja α = β = V, tada jie taip sako žaidimas turi balno tašką
, Ir gali būti išspręstos grynomis strategijomis . Kitaip tariant, yra keletas strategijų
, suteikiant žaidėjui AV.

2 pavyzdys

Grįžkime prie žaidimo, kurį nagrinėjome 1 pavyzdyje, ir patikrinkime, ar jame nėra balno taško.

Šiam žaidimui
= -5,
= 4,
, todėl jis neturi balno taško.

Dar kartą atkreipkime dėmesį, kad šis žaidimas yra žaidimas su nepilna informacija. Tokiu atveju žaidėjui galime tik patarti A pasirinkti strategiją , nes tokiu atveju jis gali gauti didžiausią laimėjimą, tačiau žaidėjo pasirinkimu IN strategijos .

3 pavyzdys

Pakeiskime žaidimo taisykles iš 1 pavyzdžio. Mes suteiksime žaidėją INžaidėjų pasirinkimo informacija A. Tada turi IN atsiras dvi papildomos strategijos:

- naudinga strategija A. Jei pasirinkimas A-1, Tai IN pasirenka 3, jei pasirenkama A-2, Tai IN pasirenka 4;

- strategija, kuri nėra naudinga A. Jei pasirinkimas A-1, Tai IN pasirenka 4, jei pasirenkama A-2, Tai IN pasirenka 3.

Šis žaidimas yra su visa informacija.

Tokiu atveju
= -5,
= -5,
, todėl žaidimas turi balno tašką
. Šis balno taškas atitinka dvi optimalių strategijų poras:
Ir
. Žaidimo kaina V= -5. Akivaizdu, kad už A toks žaidimas nepelningas.

2 ir 3 pavyzdžiai puikiai iliustruoja šią teoremą, įrodytą žaidimų teorijoje:

1 teorema

Kiekvienas suporuotas antagonistinis žaidimas su visa informacija gali būti išspręstas naudojant grynas strategijas.

Tai. 1 teorema sako, kad bet kuris dviejų žaidėjų žaidimas su visa informacija turi balno tašką ir yra pora grynų strategijų.
, suteikiant žaidėjui A tvarūs laimėjimai, lygūs žaidimo kainai V.

Tuo atveju, kai nėra balno taško, vadinamasis mišrios strategijos :, Kur p i Irq j– strategijų pasirinkimo tikimybės A i Ir B j atitinkamai pirmasis ir antrasis žaidėjai. Žaidimo sprendimas šiuo atveju yra mišrių strategijų pora
, maksimaliai padidindami matematinius lūkesčius dėl žaidimo kainos.

Ši teorema apibendrina 1 teoremą žaidimo su nepilna informacija atveju:

2 teorema

Bet kuris suporuotas antagonistinis žaidimas turi bent vieną optimalų sprendimą, t. y. porą mišrių strategijų bendruoju atveju
, suteikiant žaidėjui A tvarūs laimėjimai, lygūs žaidimo kainai V, ir α ≤ V ≤ β .

Ypatingu atveju žaidimo su balno tašku sprendimas mišriose strategijose atrodo kaip vektorių pora, kurioje vienas elementas yra lygus vienetui, o likusieji yra lygūs nuliui.