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 formula_1 mäng, milles on formula_2 mängijat, ning formula_3 on strateegiate hulk mängija formula_4 jaoks. formula_5 on kogu strateegiaprofiilide hulk ja formula_6 on selle tasufunktsioon punktis formula_7. Olgu formula_8 mängija formula_4 strateegiaprofiil ning olgu formula_10 kõigi teiste mängijate strateegiaprofiil, välja arvatud formula_4oma. Kui iga mängija formula_12 valib strateegia formula_8 ning tulemuseks on strateegiaprofiil formula_14, siis mängija formula_4 tasu on formula_16. Tasu sõltub valitud strateegiaprofiilist, st mängija formula_4 valitud strateegiast ning ka kõigi teiste valitud strateegiatest. Strateegiaprofiil formula_18 on Nashi tasakaal, kui ükskõik mis mängija ükski ühepoolne strateegiamuudatus ei ole sellele mängijale kasumlik, st
formula_19
Kui ülemine võrratus kehtib rangelt (≥ asemel on &gt;) 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 formula_20 ja mõne muu strateegia vahel hulgas formula_21, 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.
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.
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:
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.
Tingimused ei ole täidetud.
Näiteid mänguteooria probleemide kohta, kus eeltoodud tingimused ei ole kas osaliselt või täielikult täidetud
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 formula_22 mängija "i" parim vastus kõigi teiste mängijate strateegiatele.
formula_23
Siin formula_24, kus formula_25 on segastrateegia profiil kõigi segastrateegiate hulgas ja formula_26 on mängija "i" tasufunktsioon. Vastavuse formula_27 defineerimisel formula_28. Nashi tasakaalu olemasolu on ekvivalentne sellega, kui formula_29-il on püsipunkt.
Kakutani püsipunktiteoreem tagab püsipunkti olemasolu, kui järgmised neli nõuet on rahuldatud.
Tingimus 1 on rahuldatud sellega, et formula_34 on simpleksne ja seega kompaktne. Kumerus tuleneb mängijate võimalusest strateegiaid segada. formula_34 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 formula_36, siis formula_37. Seega, kui kaks strateegiat maksimeerivad tasu, siis nende kahe strateegia kombinatsioon tagab sama tasu.
Tingimus 4 on rahuldatud Berge maksimumi teoreemi kaudu. Kuna formula_26 on pidev ja kompaktne, siis formula_39 on ülespoole poolpidev.
Seega eksisteerib formula_40 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 formula_41, siis eksisteerib Nashi tasakaal, milles A mängib välja formula_41. Mängijate A ja B puhul eksisteerib Nashi tasakaal, kus A mängib välja formula_41 ja B mängib parima vastuse formula_41-le. Kui formula_41 on rangelt domineeriv strateegia, siis A mängib formula_41 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.
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−2"q"
E[Tasu, et A mängib kirja] = (+1)"q" + (−1)(1−"q") = 2"q"−1
E[Tasu, et A mängib kulli] = E[Tasu, et A mängib kirja] ⇒ 1−2"q" = 2"q"−1 ⇒ "q" = 1/2
E[Tasu, et B mängib kulli] = (+1)"p" + (−1)(1−"p") = 2"p"−1
E[Tasu, et B mängib kirja] = (−1)"p" + (+1)(1−"p") = 1−2"p"
E[Tasu, et B mängib kulli] = E[Tasu, et B mängib kirja] ⇒ 2"p"−1 = 1−2"p" ⇒ "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.