Nashi tasakaal

Nashi tasakaal on mänguteoorias kasutatav lahenduse leidmise kontseptsioon, mis on saanud nimetuse USA matemaatiku John Forbes Nashi järgi. Mittekooperatiivses mängus, kus osaleb vähemalt kaks mängijat ning iga mängija teab teiste mängijate strateegiaid, esineb Nashi tasakaal juhul, kui ükski mängija ei soovi muuta oma strateegiat, arvestades teiste osalejate strateegiavalikuid.

Juhul kui kõik mängijad on valinud strateegia ja keegi neist ei saaks mõne muu strateegia kasutamisel paremat tulemust, eeldusel et teised mängijad oma strateegiat ei muuda, moodustavadki selline strateegiate hulk ning neile vastavad tasud Nashi tasakaalu.

Kahe mängija kohta lihtsustatult väljendudes on Mari ja Jüri saavutanud Nashi tasakaalu siis, kui Mari teeb enda jaoks parima võimaliku otsuse, võttes arvesse ka Jüri otsust ja eeldades, et see parajasti ei muutu, ning kui Jüri teeb endale parima võimaliku otsuse, võttes arvesse Mari otsust ja eeldades, et see parajasti ei muutu.

Rakendusi

Mänguteoreetikud kasutavad Nashi tasakaalu mõistet, et ennustada tulemust olukorras, kus mitu inimest või institutsiooni teevad samal ajal strateegilisi valikuid ning iga osaleja tulemus sõltub nii tema enda kui ka teiste valikutest. John Nashi idee seisneb lihtsas põhimõttes, et mitme otsustaja valikute tulemust ei saa ennustada, kui võimalikke otsuseid analüüsitakse isoleeritult.

Nashi tasakaalu on kasutatud vaenulike situatsioonide analüüsiks, nt sõda ja võidurelvastumine. Samuti on seda kasutatud eesmärgiga uurida eri eelistustega inimeste koostöövalmidust, valuutakriise, mitme osalise hariduslike püüdluste tulemusi, õigusakte, nt keskkonnamäärusi, loodusressursside haldamist, turundusstrateegiaid ja isegi penaltite löömist jalgpallis.

Ajalugu

Nashi tasakaalu erijuhtumit on teadaolevalt esimesena käsitlenud 1838. aastal Antoine Augustin Cournot, kes rakendas seda oligopolide puhul. Cournot' teoorias valivad ettevõtted oma tootmismahu kasumi maksimeerimise järgi. Samal ajal sõltub optimaalne tootmismaht ka sellest, kui palju teised turuosalised toodavad. Cournot' tasakaal ilmneb juhul, kui iga ettevõte maksimeerib oma kasumi, arvestades ka teiste ettevõtete tootmismahtusid. Sel juhul on tegemist Nashi tasakaalu puhta strateegiaga. Seevastu Nashi tasakaal on laiem mõiste kui Cournot' tasakaal või Pareto-efektiivne tasakaal, sest Nashi definitsioon ei sisalda hinnangut tekkinud tasakaalu optimaalsusele.

Tänapäevases mänguteoorias kasutatav Nashi tasakaalu kontseptsioon on defineeritud segastrateegiate kaudu, kus mängijad valivad tõenäosusjaotuse, arvestades võimalikke valikuid. Segastrateegilise Nashi tasakaalu ideed tutvustasid John von Neumann ja Oskar Morgenstern oma 1944. aastal ilmunud raamatus "Mänguteooria ja majanduslik käitumine" ("The Theory of Games and Economic Behavior"). Siiski oli nende analüüs piiratud nullsummamängudega. Nad näitasid, et igas lõpliku valikute hulgaga nullsummamängus on segastrateegiaga Nashi tasakaal.

Nashi 1951. aastal avaldatud artikli "Mittekooperatiivsed mängud" ("Non-Cooperative Games") tähtsus seisnes selles, et segastrateegiaga Nashi tasakaal defineeriti iga mängu jaoks, milles on lõplik arv valikuid, ning tõestati, et sellises mängus peab olema vähemalt üks (segastrateegiaga) Nashi tasakaal. Von Neumanniga võrreldes esitab Nash oluliselt üldisema tõestuse tasakaalu olemasolu kohta. Nashi definitsiooni kohaselt on "tasakaalupunkt n osalejaga mängus n elementi nii, et iga mängija segastrateegia maksimeerib tema tasu, kui teiste strateegiad hoida püsivana. Seega on iga mängija strateegia teiste suhtes optimaalne". Sellise raamistiku andmine probleemile võimaldas Nashil oma 1950. aasta artiklis kasutada Kakutani püsipunkti teoreemi. 1951. aastal avaldatud lisaartiklis tõestas Nash Brouweri püsipunkti teoreemi abil väite, et igas lõpliku mängijate arvuga mängus (mitte üksnes nullsummamängus) peab olema vähemalt üks segastrateegiaprofiil, mis seab mängija vastavusse iseendaga, st strateegiaprofiil, mis ei tingi strateegia muutmist suurema tasu nimel.

Alates Nashi tasakaalu kontseptsiooni kasutuselevõtust on mänguteoreetikud tuvastanud mõningaid tingimusi, mille korral viib Nashi tasakaal valede ennustusteni. Selliste tingimuste kõrvaldamiseks on välja pakutud mitmeid lahenduste kontseptsioone või täiendusi. Näiteks võib Nashi tasakaal tekkida olukorras, kus strateegia põhineb ebausutaval ähvardusel. 1965. aastal pakkus Reinhard Selten välja tasakaalu alamhulga, mille ta nimetas ideaalseks tasakaaluks. Tema täiendus seisneski ebausutavatel ähvardustel põhinevate strateegiate välistamises. Teised Nashi tasakaalu täiendused on seotud olukordadega, kus mängu korratakse või kus kõigil mängijatel ei ole kogu asjakohast informatsiooni teiste osalejate kohta. Mistahes täiendusi ja laiendusi iseloomustab aga lähtumine Nashi tasakaalu aluspõhimõttest, et kõik tasakaalukontseptsioonid analüüsivad, mis valikuid tehakse, kui võetakse arvesse teiste mängijate valikuid.

Definitsioonid

Mitteametlik definitsioon

Mittematemaatiliselt väljendudes on strateegiaprofiil Nashi tasakaal, kui ükski mängija ei saa oma strateegiat muutes suuremat tasu. Et mõista, mida see tähendab, tuleb kujutleda olukorda, kus igale mängijale tehakse teatavaks teiste strateegia. Järgmiseks küsib iga mängija endalt: "Teades teiste mängijate strateegiaid ja oletades, et need ei muutu, kas ma saaksin enda strateegia muutmisest kasu?" Kui vähemalt üks mängija saab vastata sellele küsimusele jaatavalt, siis selline strateegiate hulk ei ole Nashi tasakaal. Kui iga mängija eelistab jätta oma strateegia samaks või ei huvitu strateegia muutmisest, sest tema tasu jääks strateegia muutmisel samaks, siis selline strateegiaprofiil on Nashi tasakaal. Seega, iga strateegia Nashi tasakaalus on parimal viisil vastavuses kõigi teiste mängijate strateegiatega.

Nashi tasakaal võib vahel paista ebaratsionaalne, kui jälgida süsteemi väljastpoolt, sest Nashi tasakaal ei pruugi olla Pareto-efektiivne. Samuti võib Nashi tasakaal tekitada mitteratsionaalseid tulemusi järjestikustes mängudes, sest mängijad võivad teineteist n-ö ähvardada ebaratsionaalsete otsustega. Selliste mängude analüüsimiseks võib sobida paremini ideaalne Nashi tasakaal kui Nashi tasakaalu alamhulk.

Ametlik definitsioon

Olgu $(S,f)$ mäng, milles on $n$ mängijat, ning $S_{i}$ on strateegiate hulk mängija $i$ jaoks. $S=S_{1}\times S_{2}\times \dotsb \times S_{n}$ on kogu strateegiaprofiilide hulk ja $f(x)=(f_{1}(x),\dotsc ,f_{n}(x))$ on selle tasufunktsioon punktis $x\in S$. Olgu $x_{i}$ mängija $i$ strateegiaprofiil ning olgu $x_{-i}$ kõigi teiste mängijate strateegiaprofiil, välja arvatud $i$oma. Kui iga mängija $i\in \{1,\dotsc ,n\}$ valib strateegia $x_{i}$ ning tulemuseks on strateegiaprofiil $x=(x_{1},\dotsc ,x_{n})$, siis mängija $i$ tasu on $f_{i}(x)$. Tasu sõltub valitud strateegiaprofiilist, st mängija $i$ valitud strateegiast ning ka kõigi teiste valitud strateegiatest. Strateegiaprofiil $x^{*}\in S$ on Nashi tasakaal, kui ükskõik mis mängija ükski ühepoolne strateegiamuudatus ei ole sellele mängijale kasumlik, st

$\forall i,x_{i}\in S_{i}:f_{i}(x_{i}^{*},x_{-i}^{*})\geq f_{i}(x_{i},x_{-i}^{*}).$

Kui ülemine võrratus kehtib rangelt (≥ asemel on >) kõigi mängijate jaoks ning kõigi võimalike alternatiivsete strateegiate jaoks, siis nimetatakse tasakaalu rangeks Nashi tasakaaluks. Kui mõne mängija jaoks kehtib täpne võrdus $x_{i}^{*}$ ja mõne muu strateegia vahel hulgas $S$, siis nimetatakse tasakaalu nõrgaks Nashi tasakaaluks.

Mängul võib olla puhta strateegia või segastrateegiaga Nashi tasakaal. Viimases valitakse puhas strateegia juhuslikult kindla tõenäosusega.

Nashi olemasoluteoreem

Nash tõestab, et kui lubada segastrateegiaid, siis igal lõpliku mängijate arvuga mängul, kus valida on lõpliku arvu puhaste strateegiate vahel, on olemas vähemalt üks Nashi tasakaal.

Nashi tasakaalu ei pruugi olemas olla, kui valikute hulk on lõpmatu ja mittekompaktne. Siia alla kuulub olukord, kus kaks mängijat nimetavad samal ajal naturaalarvu ning suurema arvu nimetaja võidab. Nashi tasakaal on aga olemas siis, kui valikute hulk on kompaktne ning pideva tasufunktsiooniga. See esineb olukorras, kus tasakaal on pidev segu puhastest strateegiatest, ehk mängus, kus kaks mängijat valivad reaalarvude 0 ja 1 vahel ning ühe mängija tasu (mille maksab teine mängija) võrdub ruutjuurega kahe valitud arvu vahest.

Näiteid

Koordinatsioonimäng

Koordinatsioonimängu näide on sõitmine teel vastutuleva auto suunas ning kohustus valida, kas sõita tee parem- või vasakpoolses servas. Esitatud näites on tasu 10 olukord, kus kokkupõrget autode vahel ei toimu, ning tasu 0 olukord, kus kokkupõrge toimub. Sel juhul saame mängu kirjeldada järgmise tasumaatriksiga.

Sõitmismäng

Autojuht 1; autojuht 2	Sõitmine vasakul	Sõitmine paremal
Sõitmine vasakul	10, 10	0, 0
Sõitmine paremal	0, 0	10, 10

Praegusel juhul eksisteerib kaks puhta strateegiaga Nashi tasakaalu: mõlemad valivad sõitmiseks enda poolt vaadatuna vasaku või parema poole. Kui lubada ka segastrateegiaid (kus puhas strateegia valitakse juhuslikult, kuid mingi kindla tõenäosusega), siis eksisteerib sama juhtumi korral kolm Nashi tasakaalu: esimesed kaks on eeltoodud puhtad strateegiad, kus tõenäosused on esimese mängija jaoks 0% ja 100% ning teise jaoks 0% ja 100% ning vastupidi; kolmas on lisanduv segastrateegia, kus tõenäosused kummalegi mängijale on 50% ja 50%.

Vangi dilemma

 Pikemalt artiklis Vangi dilemma

Vangi dilemma tasumaatriksi näide

Vang 1; vang 2	Koostöö (vaikimine)	Reetmine (rääkimine)
Koostöö (vaikimine)	2, 2	0, 3
Reetmine (rääkimine)	3, 0	1, 1

Kujutlege kahte vangi, keda hoitakse eraldi kongides ning keda kuulatakse samal ajal üle. Mõlemale pakutakse võimalust saada kaaskurjategija reetmise korral lühem vanglakaristus. Vang võib teise vangiga teha koostööd, st mitte midagi välja rääkida, või reeta kaaskurjategija, rääkides teise sisse. Juhul kui mõlemad annavad teineteise kohta infot, saavad nad suurema karistuse kui vaikimise korral. Tasumaatriksis kujutatud arvud on seda suuremad, mida lühem on karistus, st suurem arv tähendab suuremat tasu (väiksemat karistust).

Vangi dilemma korral sarnaneb maatriks koordinatsioonimänguga, kuid mõlemad mängijad saavad maksimaalse tasu (vt näide 3) vaid juhul, kui nende otsused on erinevad. Mõlemal mängijal on võimalik oma olukorda parandada, kui ta vahetab koostöö reetmise vastu, teades, et teise vangi parim otsus on reeta. Vangi dilemmal on seega üks Nashi tasakaal – mõlema vangi otsus teine reeta. Arutelu, mis näitab, et reetmine on parim valik, võiks olla näiteks järgmine: "Kui teine vang mu reedab, peaksin ka mina tema reetma (tasu = 1), sest tema reetmise ja minu vaikimise korral on minu karistus karmim (tasu = 0). Kui teine vang vaikib, siis peaksin ta ikkagi reetma, sest sel juhul on minu tasu maksimaalne (tasu = 3). Kui mõlemad vaikiksime, oleks minu tasu vaid 2."

Selle juhtumi on teinud läbi aegade üheks huvitavaimaks õppenäiteks asjaolu, et Nashi tasakaalu saavutamine on vangidele vähem kasulik kui koostöö tegemine, st vaikimine. Mõlemad saaksid kergema karistuse, kui kumbki ei räägiks midagi. Siiski saab vang parandada oma olukorda, murdes vastastikuse koostöö lepet. Sõltumata teise mängija valikust, on vangil alati kasulikum reeta.

Kirjeldatud juhtum on põhjustanud ka vääritimõistmist, sest Nashi tasakaalu puhul rõhutatakse sageli vajadust arvestada teiste mängijate strateegiatega ning seda tõlgendatakse sageli kui koostööd, kuid siin toodud näites ei ole koostöö Nashi tasakaal. Lisaks põhjustab eksiarvamusi asjaolu, et Nashi tasakaal ei ole mõlemale vangile kõige kasulikum olukord. Näiteks on Marek Strandberg 2012. aastal avaldanud Sirbis artikli, kus ta kirjeldab, et vangi dilemma juures on Nashi tasakaaluks mõlema vaikimine, mis ei ole õige. Teine võimalus tõlgendada ja õigustada Strandbergi arutluskäiku oleks see, kui reetmine tooks kaasa kõige kehvema tulemuse (isegi kehvema kui vaikimine, eeldusel et teine räägib). See aga ei ole mäng "Vangi dilemma", mis on defineeritud ülaltoodud viisil.

Stabiilsus

Stabiilsuse kontseptsiooni, mis on kasulik mitut tüüpi tasakaalu analüüsimisel, saab rakendada ka Nashi tasakaalu korral. Nashi tasakaal segastrateegiatega mängus on stabiilne, kui väike tõenäosuste muutus ühe mängija jaoks viib situatsioonini, kus on täidetud järgmised tingimused:

1. mängija, kelle jaoks midagi ei muutunud, ei saavutanud uues situatsioonis paremat strateegiat;
2. mängija, kelle jaoks toimus muutus, mängib nüüd varasemast kehvema strateegiaga.

Kui mõlemad tingimused on täidetud, siis mängija, kelle segastrateegias toimus väike muutus, naaseb kohe Nashi tasakaalu. Sel juhul nimetatakse tasakaalu stabiilseks. Kui esimene tingimus ei pea paika, on tasakaal ebastabiilne. Kui aga ainult esimene tingimus peab paika, siis on tõenäoliselt selle mängija jaoks, kellel toimus muutus, kasutada lõpmatu hulk optimaalseid strateegiaid.

Eespool toodud "Sõitmismängu" näites esinevad nii stabiilne kui ka ebastabiilne tasakaal. Stabiilne on selline tasakaal, mis põhineb segastrateegiatel, mille valikud toimuvad 100% tõenäosusega. Kui emb-kumb mängija muudab seda tõenäosust veidi, on mõlemad seejärel kehvemas olukorras ning vastasel ei ole selle peale põhjust enda strateegiat muuta. Seevastu 50% ja 50% tasakaal on ebastabiilne. Kui emb-kumb mängija muudab valiku tõenäosust, siis on teisel mängijal mõttekam liikuda kohe 0% ja 100% strateegia või 100% ja 0% strateegia juurde.

Stabiilsus on Nashi tasakaalu rakendamisel oluline, sest mängijate segastrateegiad ei ole üldjuhul detailselt teada, vaid neid tuleb tuletada mängus tehtud valikute statistilisest jaotusfunktsioonist. Sel juhul on väga ebatõenäoline, et praktikas esineb ebastabiilne tasakaal, sest iga vähimgi muutus kellegi strateegias viib tasakaalu kaotamiseni.

Esinemine

Kui mängus on olemas unikaalne Nashi tasakaal ning mäng vastab teatud tingimustele, siis jõutakse Nashi tasakaaluks vajalike strateegiate hulgani. Nashi tasakaalu tekkeks peavad olema täidetud järgmised tingimused.

1. Mängijad annavad endast parima, et maksimeerida enda oodatavat tasu.
2. Mängijad on oma tegevuste täideviimises veatud.
3. Mängijatel on piisavad teadmised mängu lahenduse tuletamiseks.
4. Mängijad teavad kõigi teiste mängijate planeeritud tasakaalustrateegiat.
5. Mängijad usuvad, et kui nad kalduvad oma strateegiast kõrvale, ei mõjuta see teiste mängijate valikut.
6. Valitseb üldine teadlikkus selle kohta, et kõik mängijad vastavad eeltoodud tingimustele: peale selle, et iga mängija peab teadma, et teised vastavad konkreetsele tingimusele, peab ta ka teadma, et kõik teised seda teavad jne.

Tingimused ei ole täidetud

Näiteid mänguteooria probleemide kohta, kus eeltoodud tingimused ei ole kas osaliselt või täielikult täidetud

1. Esimene tingimus ei ole täidetud, kui mängust ei ilmne piisavalt selgelt, mis suurust soovib mängija maksimeerida. Sel juhul ei ole mängijal otsest põhjust valida tasakaaluni viivat strateegiat. Näiteks vangi dilemma ei ole dilemma, kui vähemalt üks mängijatest on rahul määramata ajaks vangi minemisega.
2. Paljudel juhtudel ei ole kolmas tingimus täidetud, sest kuigi tasakaalupunkt peab mängus eksisteerima, ei ole see mängu keerukuse tõttu teada, nt Hiina male korral. Sama kehtib ka siis, kui tasakaalupunkt on teada, kuid mitte kõigile mängijatele, nt väikese lapsega trips-traps-trulli mängides.
3. Üldise teadlikkuse kriteerium ei pruugi olla täidetud isegi siis, kui kõik mängijad vastavad kõigile ülejäänud tingimustele. Mängijad, kes seavad kahtluse alla teineteise ratsionaalsuse, võivad teiste irratsionaalse käitumise tarbeks võtta kasutusele hoopis vastustrateegiad. Seda tuleb kindlasti arvestada näiteks võidurelvastumist analüüsides.

Tingimused on täidetud

Doktoriväitekirjas pakkus John Nash välja kaks tõlgendust oma tasakaalukontseptsioonile, et näidata, kuidas saab tema tasakaalupunktid viia vaadeldavate nähtustega vastavusse. Üks tõlgendus on ratsionalistlik: "Kui eeldada, et mängijad on ratsionaalsed, teavad mängu struktuuri, mängitakse vaid ühe korra ning mängus on vaid üks Nashi tasakaal, siis mängijad mängivad sellesse tasakaalupunkti jõudmiseni." Selle idee formaliseerisid 1995. aastal R. Aumann ja A. Brandenburger artiklis "Epistemic conditions for Nash equilibrium" (Econometrica, 63, 1161–1180). Nad tõlgendasid iga mängija segastrateegiat kui hüpoteesi teiste mängijate käitumise kohta ning näitasid, et kui mäng ja mängijate ratsionaalsus on vastastikku teada, siis selline hüpotees peab olema Nashi tasakaal.

Teine tõlgendus on mängijate jaoks väiksemate piirangutega: "Ei ole tarvilik eeldada, et mängijatel on täielik teadmine mängu struktuuri kohta ning mängijatel ei pea olema võimekust ja vajadust läbida keerulist loogilist arutlusprotsessi. Eeldatakse, et on olemas mängijate kogum igale positsioonile mängus, mida mängivad kogumist juhuslikult valitud mängijad ajas pidevalt. Kui on olemas stabiilne keskmine sagedus, millega kogumi "keskmine mängija" kasutab mõnda puhast strateegiat, siis see stabiilne keskmine sagedus ongi segastrateegia Nashi tasakaal." (Vt H. Kuhn jt 1996, "The work of John Nash in game theory", Journal of Economic Theory, 69, 153–185.)

Kuivõrd tingimused, millal saab Nashi tasakaalu reaalselt mingis olukorras jälgida, on võrdlemisi piiratud, on see kontseptsioon üsna harva teejuhiks igapäevaste olukordade lahendamisel. Siiski on Nashi tasakaalul kui majandusteaduse ja evolutsioonibioloogia teoreetilisel kontseptsioonil selgitav jõud. Majandusteaduses on mängu tasuks üldjuhul varad (raha) vm, evolutsioonibioloogias geenide edasikandumine – mõlemad on tarvilikud tingimused elamiseks ja elu edasikandumiseks vastavates distsipliinides. Uurijad, kes neis valdkondades mänguteooriat rakendavad, väidavad, et strateegiad, mis ei tule toime eeltoodud hüvede maksimeerimisega mistahes põhjustel, surutakse turult või keskkonnast välja. Sellistes situatsioonides kasvab eeldus, et jälgitav strateegia on Nashi tasakaal, enamasti välja uurimusest.

Olemasolu tõestus

Tõestus Kakutani püsipunktiteoreemi abil

Nashi algses, väitekirjas esitatud tõestuses kasutati Brouweri püsipunktiteoreemi. Lihtsam on näidata tõestust Kakutani püsipunktiteoreemi kaudu, nagu ta ise tegi seda oma 1950. aasta artiklis.

Et tõestada Nashi tasakaalu olemasolu, olgu $r_{i}(\sigma _{-i})$ mängija i parim vastus kõigi teiste mängijate strateegiatele.

$r_{i}(\sigma _{-i})=\arg \max _{\sigma _{i}}u_{i}(\sigma _{i},\sigma _{-i})$

Siin $\sigma \in \Sigma$, kus $\Sigma =\Sigma _{i}\times \Sigma _{-i}$ on segastrateegia profiil kõigi segastrateegiate hulgas ja $u_{i}$ on mängija i tasufunktsioon. Vastavuse $r\colon \Sigma \rightarrow 2^{\Sigma }$ defineerimisel $r=(r_{i}(\sigma _{-i}),r_{-i}(\sigma _{i}))$. Nashi tasakaalu olemasolu on ekvivalentne sellega, kui $r$-il on püsipunkt.

Kakutani püsipunktiteoreem tagab püsipunkti olemasolu, kui järgmised neli nõuet on rahuldatud.

1. $\Sigma$ on kompaktne, kumer ja mittetühi.
2. $r(\sigma )$ on mittetühi.
3. $r(\sigma )$ on kumer.
4. $r(\sigma )$ on ülespoole poolpidev.

Tingimus 1 on rahuldatud sellega, et $\Sigma$ on simpleksne ja seega kompaktne. Kumerus tuleneb mängijate võimalusest strateegiaid segada. $\Sigma$ on mittetühi, kui mängijatel on strateegiaid.

Tingimus 2 on rahuldatud, sest mängijad proovivad maksimeerida oma tasu, mis on pidev funktsioon üle kompaktse hulga. Weierstrassi ekstreemumite teoreem tagab, et maksimum on alati olemas.

Tingimus 3 on rahuldatud tänu segastrateegiatele. Kui $\sigma _{i},\sigma '_{i}\in r(\sigma _{-i})$, siis $\lambda \sigma _{i}+(1-\lambda )\sigma '_{i}\in r(\sigma _{-i})$. Seega, kui kaks strateegiat maksimeerivad tasu, siis nende kahe strateegia kombinatsioon tagab sama tasu.

Tingimus 4 on rahuldatud Berge maksimumi teoreemi kaudu. Kuna $u_{i}$ on pidev ja kompaktne, siis $r(\sigma _{i})$ on ülespoole poolpidev.

Seega eksisteerib $r$ püsipunkt ja Nashi tasakaal.

Kui Nash tegi eelneva teatavaks John von Neumannile, siis von Neumann vastas: "See on ju triviaalne. See on lihtsalt püsipunktiteoreem." (Vt Nasar, 1998, p. 94.)

Nashi tasakaalu arvutamine

Kui mängijal A on domineeriv strateegia $s_{A}$, siis eksisteerib Nashi tasakaal, milles A mängib välja $s_{A}$. Mängijate A ja B puhul eksisteerib Nashi tasakaal, kus A mängib välja $s_{A}$ ja B mängib parima vastuse $s_{A}$-le. Kui $s_{A}$ on rangelt domineeriv strateegia, siis A mängib $s_{A}$ kõigis võimalikes Nashi tasakaalu punktides. Kui nii A-l kui ka B-l on rangelt domineerivad strateegiad, siis eksisteerib unikaalne Nashi tasakaal, milles mõlemad mängivad oma rangelt domineerivat strateegiat.

Segastrateegia Nashi tasakaalu punktidega mängus arvutatakse konkreetse strateegia valik nii, et iga strateegiaga viiakse vastavusse muutuja, mis kirjeldab selle strateegia valimise fikseeritud tõenäosust. Et mängija nõustuks juhuvalikuga, peaks eeldatav tasu iga strateegia jaoks olema sama. Lisaks peab kõigi strateegiate valikute tõenäosuste summa olema 1. See tekitab võrrandisüsteemi, millest saab tuletada iga strateegia valimise tõenäosuse.

Näited

Sendimäng

Mängija A; mängija B	Mängija B mängib kulli	Mängija B mängib kirja
Mängija A mängib kulli	−1, +1	+1, −1
Mängija A mängib kirja	+1, −1	−1, +1

Kulli ja kirja mängus kaotab mängija A punkti B-le, kui A ja B mängivad sama strateegiaga, ning võidab punkti B-lt, kui nad mängivad eri strateegiatega. Segastrateegia Nashi tasakaalu arvutamiseks tähistagu p seda, et A mängib kulli, ning (1-p) seda, et ta mängib kirja. q olla tõenäosus, et B mängib kulli, ja (1−q) tõenäosus, et ta mängib kirja.

E[Tasu, et A mängib kulli] = (−1)q + (+1)(1−q) = 1−2q

E[Tasu, et A mängib kirja] = (+1)q + (−1)(1−q) = 2q−1

E[Tasu, et A mängib kulli] = E[Tasu, et A mängib kirja] ⇒ 1−2q = 2q−1 ⇒ q = 1/2

E[Tasu, et B mängib kulli] = (+1)p + (−1)(1−p) = 2p−1

E[Tasu, et B mängib kirja] = (−1)p + (+1)(1−p) = 1−2p

E[Tasu, et B mängib kulli] = E[Tasu, et B mängib kirja] ⇒ 2p−1 = 1−2p ⇒ p = 1/2

Seega, segastrateegiaga Nashi tasakaal oleks selles mängus see, et kumbki mängija valib juhuslikult kulli või kirja tõenäosustega p = 1/2 ja q = 1/2.

Vaata ka

• Mänguteooria
• Vangi dilemma

Kirjandus

Mänguteooria õpikuid

• Dixit, A.; Skeath, S.; Reiley, D. (2009). Games of Strategy. W.W. Norton & Company.
• Dutta, Prajit K. (1999), Strategies and Games: Theory and Practice, MIT Press, ISBN 978-0-262-04169-0.
• Fudenberg, D.; Tirole, J. (1991). Game Theory. MIT Press.
• Leyton-Brown, Kevin; Shoham, Yoav (2008), Essentials of Game Theory: A Concise, Multidisciplinary Introduction, San Rafael, CA: Morgan & Claypool Publishers, ISBN 978-1-59829-593-1.
• Morgenstern, O.; von Neumann, J. (1947). The Theory of Games and Economic Behavior. Princeton University Press.
• Myerson, Roger B. (1997), Game Theory: Analysis of Conflict, Harvard University Press, ISBN 978-0-674-34116-6.
• Papayoanou, Paul (2010), Game Theory for Business: A Primer in Strategic Gaming, Probabilistic Publishing, ISBN 978-0964793873.
• Rubinstein, Ariel; Osborne, Martin J. (1994), A Course in Game Theory, MIT Press, ISBN 978-0-262-65040-3.
• Shoham, Yoav; Leyton-Brown, Kevin (2009), Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations, New York: Cambridge University Press, ISBN 978-0-521-89943-7. Downloadable free online.
• Gibbons, Robert (1992), Game Theory for Applied Economists, Princeton University Press (July 13, 1992), ISBN 978-0-691-00395-5.
• Osborne, Martin (2004), An introduction to game theory, Oxford University, ISBN 978-0-19-512895-6.

Algsed Nashi artiklid

• Nash, J. (1950). "Equilibrium Points in n-Person Games". Proceedings of the National Academy of Sciences, 36 (1): 48–49.
• Nash, J. (1951). "Non-Cooperative Games". The Annals of Mathematics, 54 (2): 286–295.

Muud viited

• Mehlmann, A. (2000). The Game's Afoot! Game Theory in Myth and Paradox. American Mathematical Society.
• Nasar, S. (1998). A Beautiful Mind. Simon & Schuster.

Välislingid

• Complete Proof of Existence of Nash Equilibria