Қорытындысыз ойындардағы Нэш тепе-теңдігі тұжырымы

Кіріспе

Кооперативті емес ойынның шешім тұжырымдамасы

Ойын теориясында Нэш тепе-теңдігі кооперативті емес ойындар үшін ең көп қолданылатын шешім тұжырымдамасы болып табылады. Нэш тепе-теңдігі – бұл егер ойыншы өзінің стратегиясын өзгертіп (басқа ойыншылардың стратегияларын өзгермей ұстап) пайда таба алмайтын жағдай. Нэш тепе-теңдігі идеясы 1838 жылы оны олигополиядағы бәсекелестік моделіне қолданған Курноға дейін жетеді. Егер әрбір ойыншы ойын барысында болған жағдайларға сүйене отырып стратегияны немесе әрекеттер жоспарын таңдаса және егер басқа ойыншылар өз стратегияларын өзгермей, өзінің күтілетін пайдасын арттыра алмаса, онда стратегиялардың қазіргі жиынтығы Нэш тепе-теңдігін құрайды. Егер екі ойыншы – Алиса мен Боб A және B стратегияларын таңдаса, (A, B) Нэш тепе-теңдігі болады, егер Алиса Бобтың B стратегиясын таңдауына жауап ретінде A-дан жақсы нәтиже беретін басқа стратегияға ие болмаса, ал Боб Алисаның A стратегиясын таңдауына жауап ретінде B-дан жақсы нәтиже беретін басқа стратегияға ие болмаса. Кэрол мен Дэн де ойыншылар болатын ойында (A, B, C, D) Нэш тепе-теңдігі болады, егер A – Алисаның (B, C, D) комбинациясына ең жақсы жауабы болса, B – Бобтың (A, C, D) комбинациясына ең жақсы жауабы болса, және т.с.с. Нэш шектеулі ойынның кез келген түрі үшін, мүмкін аралас стратегияларды қолдана отырып, Нэш тепе-теңдігінің бар екенін көрсетті.

Қолданбалар

Ойын теориясы мамандары бірнеше шешім қабылдаушылардың стратегиялық өзара әрекеттесуінің нәтижесін талдау үшін Нэш тепе-теңдігін пайдаланады. Стратегиялық өзара әрекеттесуде әрбір шешім қабылдаушының нәтижесі басқалардың шешімдеріне де, өз шешіміне де байланысты болады. Нэш идеясының негізгі түсінігі – егер шешімдер оқшауланған түрде талданса, бірнеше шешім қабылдаушының таңдауын болжау мүмкін емес. Оның орнына, әр ойыншы басқаларының не істейтінін күте отырып, өзі не істейтінін сұрауы керек. Нэш тепе-теңдігі таңдаулардың үйлесімділігін талап етеді: басқалар шешім қабылдағанда ешбір ойыншы өз шешімін өзгертуге ниеттенбейді. Бұл тұжырым соғыс және қарулану жарысы сияқты қақтығыс жағдайларды талдау үшін қолданылды (түрмешінің дилеммасын қараңыз), сондай-ақ қайталанатын өзара әрекеттесу арқылы қақтығысты қалай азайтуға болатынын зерттеу үшін («тізгінмен тізгін» әдісін қараңыз). Бұдан бөлек, әртүрлі мүдделерге ие адамдардың қаншалықты ынтымақтаса алатынын анықтау үшін (жыныстар арасындағы тартысты қараңыз) және олар ынтымақтастыққа қол жеткізу үшін тәуекелге бара ма (аң аулауды қараңыз) зерттеулер жүргізілді. Техникалық стандарттарды қабылдауды, сондай-ақ банкроттықтар мен валюталық дағдарыстардың туындауын зерттеуде де (координациялық ойынды қараңыз) қолданылды. Басқа қолданыс салалары: жол қозғалысы (Wardrop принципі), аукциондарды ұйымдастыру (аукцион теориясын қараңыз), білім беру процесіндегі бірнеше тараптың күш-жігерінің нәтижесі, қоршаған ортаны қорғау сияқты реттеуші заңнама (жалпы мүліктің трагедиясын қараңыз), табиғи ресурстарды басқару, маркетингтегі стратегияларды талдау, тіпті футболдағы пенальтилер (тең тиынды таңдауды қараңыз), энергия жүйелері, көлік жүйелері, эвакуация мәселелері және сымсыз байланыс.

Тарих

Нэш тепе-теңдігі американдық математик Джон Форбс Нэш-младшийдің есімімен аталады. Осы идея 1838 жылы Антуан Августин Курноның олигополия теориясында нақты қолданыс тапқан. Курно теориясында әр фирма өзінің пайдасын барынша арттыру үшін қанша өнім шығаратынын таңдайды. Бір фирманың ең жақсы өнімі басқа фирмалардың өнімдеріне байланысты. Курно теңгерімі, әр фирманың өнімі басқа фирмалардың өнімдерін ескере отырып, оның пайдасын барынша арттырған кезде пайда болады, бұл таза стратегиялық Нэш тепе-теңдігі. Курно теңгерімнің тұрақтылығын талдау кезінде ең жақсы жауап динамикасы ұғымы енгізілді. Алайда, Курно бұл идеяны басқа қолданыстарда қолданбады немесе оны жалпылама анықтамады. Қазіргі заманғы Нэш тепе-теңдігі түсінігі аралас стратегиялар тұрғысынан анықталады, онда ойыншылар ықтимал таза стратегияларға қарағанда ықтималдықты бөлуді таңдайды (бұл ықтималдықтың 100% -ын бір таза стратегияға қоюы мүмкін; мұндай таза стратегиялар аралас стратегиялардың кіші жиынтығы). Аралас стратегиялық тепе-теңдік ұғымын Джон фон Нейман мен Оскар Моргенштерн 1944 жылы "Ойындар теориясы және экономикалық мінез-құлық" кітабында енгізді, бірақ олардың талдауы нөлдік жиынтық ойындарының ерекше жағдайымен шектелді. Олар аралас стратегиялық Нэш тепе-теңдігінің шекті әрекеттер жиынтығымен кез келген нөлдік жиынтық ойындар үшін болатынын көрсетті. Нэштің 1951 жылғы "Кооперациялық емес ойындар" мақаласындағы үлесі – кез келген ойынның шекті әрекеттер жиынтығы үшін аралас стратегиялық Нэш тепе-теңдігін анықтау және мұндай ойында кем дегенде бір (аралас стратегиялық) Нэш тепе-теңдігінің болуы керек екенін дәлелдеу. Нэштің фон Нейманнан гөрі кеңінен өмір сүруді дәлелдеу қабілеті оның тепе-теңдік туралы анықтамасында жатыр. Нэштің айтуынша, "теңдік нүктесі – бұл әр ойыншының аралас стратегиясы, егер басқалардың стратегиясы белгіленсе, оның сыйақысын барынша арттырады. Осылайша әр ойыншының стратегиясы басқаларға қарсы оңтайлы болады". Проблеманы осы шеңберге қою Нэшке 1950 жылы теңгерімнің бар екенін дәлелдеу үшін Какутанидің тұрақты нүкте теоремасын қолдануға мүмкіндік берді. 1951 жылғы еңбегінде Браувердің қарапайым тұрақты нүкте теоремасы да осы мақсатта қолданылды. Ойын теориялары кейбір жағдайларда Нэш тепе-теңдігінің жарамсыз болжамдар жасағанын немесе бірегей болжам жасай алмайтынын анықтады. Олар Нэш тепе-теңдіктерін жойып тастау үшін көптеген шешімдер тұжырымдамаларын ("Нэш тепе-теңдіктерінің жетілдірілуі") ұсынды. Бір ерекше маңызды мәселе – кейбір Нэш тепе-теңдіктері "сенімді" емес қауіп-қатерлерге негізделуі мүмкін. 1965 жылы Рейнхард Селтен сенімді емес қауіп-қатерлерге байланысты тепе-теңдіктерді жоятын жетілдіру ретінде толық теңгерімді ұсынды. Нэш тепе-теңдігі тұжырымдамасының басқа кеңейтулері ойын қайталанса не болады немесе толық ақпарат болмаған жағдайда ойын ойналса не болады деген мәселелерді қарастырды. Алайда, Нэш тепе-теңдігінің кейінгі жетілдірілуі мен кеңейтілуі Нэш тұжырымдамасы негізделген негізгі түсінікті бөліседі: тепе-теңдік – бұл әр ойыншының стратегиясы басқалардың таңдауларын ескере отырып, оңтайлы болатын стратегиялардың жиынтығы.

Nash equilibrium is named after American mathematician John Forbes Nash Jr. The same idea was used in a particular application in 1838 by Antoine Augustin Cournot in his theory of oligopoly. In Cournot's theory, each of several firms choose how much output to produce to maximize its profit. The best output for one firm depends on the outputs of the others. A Cournot equilibrium occurs when each firm's output maximizes its profits given the output of the other firms, which is a pure strategy Nash equilibrium. Cournot also introduced the concept of best response dynamics in his analysis of the stability of equilibrium. Cournot did not use the idea in any other applications, however, or define it generally. The modern concept of Nash equilibrium is instead defined in terms of mixed strategies, where players choose a probability distribution over possible pure strategies (which might put 100% of the probability on one pure strategy; such pure strategies are a subset of mixed strategies). The concept of a mixed strategy equilibrium was introduced by John von Neumann and Oskar Morgenstern in their 1944 book The Theory of Games and Economic Behavior, but their analysis was restricted to the special case of zero sum games. They showed that a mixed strategy Nash equilibrium will exist for any zero sum game with a finite set of actions. The contribution of Nash in his 1951 article "Non Cooperative Games" was to define a mixed strategy Nash equilibrium for any game with a finite set of actions and prove that at least one (mixed strategy) Nash equilibrium must exist in such a game. The key to Nash's ability to prove existence far more generally than von Neumann lay in his definition of equilibrium. According to Nash, "an equilibrium point is an n tuple such that each player's mixed strategy maximizes his payoff if the strategies of the others are held fixed. Thus each player's strategy is optimal against those of the others." Putting the problem in this framework allowed Nash to employ the Kakutani fixed point theorem in his 1950 paper to prove existence of equilibria. His 1951 paper used the simpler Brouwer fixed point theorem for the same purpose. Game theorists have discovered that in some circumstances Nash equilibrium makes invalid predictions or fails to make a unique prediction. They have proposed many solution concepts ('refinements' of Nash equilibria) designed to rule out implausible Nash equilibria. One particularly important issue is that some Nash equilibria may be based on threats that are not 'credible'. In 1965 Reinhard Selten proposed subgame perfect equilibrium as a refinement that eliminates equilibria which depend on non credible threats. Other extensions of the Nash equilibrium concept have addressed what happens if a game is repeated, or what happens if a game is played in the absence of complete information. However, subsequent refinements and extensions of Nash equilibrium share the main insight on which Nash's concept rests: the equilibrium is a set of strategies such that each player's strategy is optimal given the choices of the others.

Нэш тепе-теңдігі

Стратегиялық профиль – әр ойыншыға арналған стратегиялар жиынтығы. Формальды емес тұрғыдан, стратегиялық профиль Нэш тепе-теңдігі болып саналады, егер ешбір ойыншы өз стратегиясын бір жақты түрде өзгерту арқылы жақсы нәтижеге қол жеткізе алмаса. Бұл нені білдіретінін түсіну үшін, әр ойыншыға басқаларының стратегиялары белгілі деп елестетейік. Содан кейін әр ойыншы өзінен: «Басқа ойыншылардың стратегияларын біліп, оларды өзгермейтіндей қарастыра отырып, өз стратегиямды өзгертуден пайда көре аламын ба?» – деп сұрайды. Егер ойыншы «Иә» деп жауап берсе, онда бұл стратегиялар жиынтығы Нэш тепе-теңдігі емес. Ал егер барлық ойыншылар стратегияларын өзгертуден бас тартса (немесе өзгерту мен өзгермеу арасында айырмашылықты сезінбесе), онда стратегиялық профиль Нэш тепе-теңдігі болып табылады. Осылайша, Нэш тепе-теңдігіндегі әр стратегия сол тепе-теңдіктегі басқа ойыншылардың стратегияларына ең жақсы жауап болып табылады. Формальды түрде, - ойыншының барлық мүмкін стратегияларының жиынтығы, мұнда - стратегиялық профиль, әр ойыншы үшін бір стратегиядан тұратын жиынтық, ал - барлық ойыншылардың стратегияларын, бірақ бойынша білдіреді. - ойыншы i-нің стратегиясының нәтижесі ретіндегі функциясы. Стратегиялық профиль Нэш тепе-теңдігі болып табылады, егер .

Ойынның бірнеше Нэш тепе-теңдігі болуы мүмкін. Тепе-теңдік бірегей болғанымен, ол әлсіз болуы мүмкін: ойыншы басқа ойыншылардың таңдауына байланысты бірнеше стратегиялардың арасында айырмашылықты сезінбеуі мүмкін. Егер теңсіздік қатаң болса, онда бұл бірегей және қатаң Нэш тепе-теңдігі деп аталады, яғни бір стратегия – ең жақсы жауап.

Стратегиялар жиынтығы әр түрлі ойыншылар үшін әртүрлі болуы мүмкін, ал оның элементтері әртүрлі математикалық объектілерден құралуы мүмкін. Ең қарапайымында, ойыншы екі стратегияның арасынан таңдау жасай алады, мысалы, . Немесе стратегиялар жиынтығы басқа ойыншыларға жауап ретінде шартты стратегиялардың шекті жиынтығы болуы мүмкін, мысалы, . Ал ол шексіз жиынтық, континуум немесе шексіз де болуы мүмкін, мысалы, , мұнда – теріс емес нақты сан. Нэштің қазіргі дәлелдемелері шекті стратегиялар жиынтығын қарастырады, бірақ Нэш тепе-теңдігінің түсінігі оны талап етпейді.

Таза/аралас тепе-теңдік

Ойын таза стратегия немесе аралас стратегия бойынша Nash тепе-теңдігіне ие болуы мүмкін. Екінші жағдайда, таза стратегия белгілі бір ықтималдықпен кездейсоқ түрде таңдалады.

Коалициялардың теңгерімдері

Нэш тепе-теңдігі тұрақтылықты тек жеке ойыншылардың ауытқулары тұрғысынан анықтайды. Кооперативтік ойындарда мұндай ұғым жеткілікті сенімді емес. Нэштің күшті тепе-теңдігі кез келген мүмкін коалицияның ауытқуына мүмкіндік береді. Формальды түрде, күшті Нэш тепе-теңдігі – бұл Нэш тепе-теңдігі, онда ешбір коалиция өз мүшелерінің әрекеттерін өзгерту арқылы, барлық қатысушыларына пайда әкелетіндей кооперативтік ауытқу жасай алмайды. Дегенмен, Нэштің күшті ұғымы кейде тым "күшті" деп есептеледі, себебі орта шексіз жеке хабарласуға жол береді. Шындығында, күшті Нэш тепе-теңдігі Парето тиімді болуы керек. Осы талаптардың нәтижесінде, күшті Нэш ойын теориясының көптеген салаларында қолдану үшін тым сирек кездеседі. Алайда, сайлау сияқты, мүмкін нәтижелер санынан ойыншылардың көп есе көп болған ойындарда, ол тұрақты тепе-теңдіктен гөрі жиі кездесуі мүмкін. Коалициялық дәлелденген Нэш тепе-теңдігі (CPNE) деп аталатын жетілдірілген Нэш тепе-теңдігі бар. Сонымен қатар, ойынның белгілі бір көлемнен кіші коалицияларға қарсы тұрақты Нэш тепе-теңдігі болуы мүмкін, яғни k көлемінен кіші коалициялардың ауытқуына төзімді. CPNE ядро теориясымен байланысты.

Нэштің өмір сүру теоремасы

Нэш аралас стратегияларға (ойыншы әртүрлі таза стратегияларды қолдану ықтималдығын таңдайтын) рұқсат етілген жағдайда, әр ойыншының шекті көп таза стратегиядан таңдай алатын, шекті санды ойыншылары бар кез келген ойынның кем дегенде бір Нэш тепе-теңдігі бар екенін дәлелдеді. Бұл тепе-теңдік әр ойыншы үшін таза стратегия немесе әр ойыншы үшін стратегиялар бойынша ықтималдық таралуы болуы мүмкін. Таңдау жиынтығы шексіз және компактты болмаса, Нэш тепе-теңдігі міндетті түрде болуы қажет емес. Мысалы: Екі ойыншы бір уақытта санды атаса, үлкен санды атаған ойыншы жеңеді. Мұндай ойынның Нэш тепе-теңдігі жоқ, себебі таңдау жиынтығы компактты емес, шексіз болғандықтан. Екі ойыншының әрқайсысы 5-тен кіші нақты санды таңдайды, ең үлкен санды атаған ойыншы жеңімпаз болады; бірақ 5-тен кіші ең үлкен сан жоқ (егер сан 5-ке тең болса, Нэш тепе-теңдігінде екі ойыншы да 5-ті таңдап, тең түсер еді). Бұл жағдайда таңдау жиынтығы жабық болмағандықтан компактты емес. Дегенмен, егер таңдау жиынтығы компактты болса және әр ойыншының төлемі барлық ойыншылардың стратегияларына қатысты үздіксіз болса, Нэш тепе-теңдігі болады.

Рационалдылық

Нэш тепе-теңдігі кейде үшінші тұлғаның көзқарасынан қарағанда иррационалды көрінуі мүмкін. Бұл себебі Нэш тепе-теңдігі міндетті түрде Парето-оптималды емес. Нэш тепе-теңдігі тізбектелген ойындарда да иррационалды салдарларға алып келуі мүмкін, себебі ойыншылар бір-бірін іс жүзінде орындамайтын қауіптермен қорқытуы мүмкін. Мұндай ойындар үшін суб ойынға толыққанды Нэш тепе-теңдігі талдау құралы ретінде маңыздырақ болуы мүмкін.

Желілік трафик

Нэш тепе-теңдігінің қолданылуы желідегі трафик ағынының күтілетін деңгейін анықтау болып табылады. Оң жақтағы графикті қарастырайық. Егер A-дан D-ге «автомобильдер» баратынын болжайтын болсақ, желідегі трафик қалай таралады? Бұл жағдайды «ойын» ретінде модельдеуге болады, онда әр саяхатшының 3 стратегияны таңдау мүмкіндігі бар, ал әр стратегия – A-дан D-ге дейінгі маршрут (ABD, ABCD немесе ACD-нің бірі). Әр стратегияның «сыйлық» мөлшері – әр маршрутты жүріп өту уақыты. Оң жақтағы графикте ABD арқылы жүретін автомобильдің жүріп өту уақыты , мұнда AB қабырғасымен жүретін автомобильдердің саны болып табылады. Осылайша, кез келген стратегияның сыйлық мөлшері басқа ойыншылардың таңдауына байланысты, бұл қалыпты жағдай. Дегенмен, бұл жағдайда мақсат – жүріп өту уақытын арттыру емес, азайту. Тепе-теңдік барлық маршруттардағы уақыт бірдей болғанда орнатылады. Ондай жағдайда ешбір жүргізуші маршрутты өзгертуге мүдделі болмайды, себебі бұл олардың жүріп өту уақытын ұзартуы мүмкін. Оң жақтағы графикте, мысалы, 100 автомобиль A-дан D-ге бара жатса, тепе-теңдік 25 жүргізуші ABD арқылы, 50-сі ABCD арқылы және 25-і ACD арқылы жүргенде орнатылады. Әрбір жүргізушінің жалпы жүріп өту уақыты 3,75-ке тең (мұны көру үшін, барлығы 75 автомобиль AB қабырғасын, ал сондай-ақ 75 автомобиль CD қабырғасын пайдаланады). Назар аударыңыз, бұл таралым әлеуметтік тұрғыдан оңтайлы емес. Егер 100 автомобиль 50-сі ABD арқылы, ал қалған 50-сі ACD арқылы жүретін болса, онда кез келген автомобиль үшін жүріп өту уақыты 3,5-ке тең болады, бұл 3,75-тен кем. Бұл сонымен қатар Нэш тепе-теңдігі болып табылады, егер B мен C арасындағы маршрут алынып тасталса, яғни қосымша маршрутты қосу жүйенің тиімділігін төмендетуі мүмкін, бұл құбылыс Бресс парадоксы деп аталады.

Пайда болуы

Егер ойынның бірегей Нэш тепе-теңдігі болса және белгілі бір жағдайларда ойыншылар арасында ойналса, онда NE стратегиясы қолданылады. Нэш тепе-теңдігінің орындалуын қамтамасыз ететін жеткілікті шарттар: Ойыншылар ойын сипаттамасында көрсетілген күтілетін пайданы барынша арттыруға бар күштерін жұмсайды. Ойыншылар орындалуда қатесіз. Ойыншылардың интеллектуалдық қабілеттері шешімді табуға жетеді. Ойыншылар басқа ойыншылардың жоспарланған тепе-теңдік стратегиясын біледі. Ойыншылар өз стратегияларынан ауытқудың басқа ойыншылардың да ауытқуына себеп болмайды деп сендіреді. Барлық ойыншылар осы шарттарды, оның ішінде осы талапты да орындайтыны – жалпыға мәлім. Демек, әр ойыншы басқа ойыншылардың шарттарды орындайтынын ғана емес, сонымен қатар олардың барлығы олардың орындайтынын білетінін, және олардың білетінін білетінін, олардың орындайтынын білетінін білетінін және т.б. білуі керек.

НЕ және сенімді емес қауіптер

Нэш тепе-теңдігі – бұл толыққанды Нэш тепе-теңдігінің кеңейтілген жиынтығы. Толыққанды тепе-теңдік, Нэш тепе-теңдігіне қосымша, стратегияның сол ойынның кез келген қосалқы ойынында да Нэш тепе-теңдігі болуын қажет етеді. Бұл сенімсіз қауіптердің барлығын жояды, яғни қарсы ойыншыны стратегиясын өзгертуге мәжбүрлеу үшін негізсіз әрекеттерді қамтитын стратегияларды. Оң жақтағы сурет қарапайым кезеңдік ойынды көрсетеді, ол қосалқы ойынның жетілмеген Нэш тепе-теңдігімен байланысты мәселені иллюстрациялайды. Ойынның бірінші ойыншысы солға (L) немесе оңға (R) таңдайды, содан кейін екінші ойыншы бірінші ойыншыға мейірімді (K) немесе мейірімсіз (U) болуға шақырылады. Дегенмен, екінші ойыншы бірінші ойыншы солға бұрған жағдайда ғана мейірімсіз болудан пайда көреді. Егер бірінші ойыншы оңға бұрса, рационалды екінші ойыншы сол қосалқы ойында оған мейірімді болар еді. Алайда, 2(2) нүктесінде мейірімсіз болудың сенімсіз қаупі әлі де көк түсті (L, (U,U)) Нэш тепе-теңдігінің құрамында. Сондықтан, егер екі тарап та рационалды мінез-құлық күте алса, онда мұндай динамикалық қайшылықтар туындаған кезде толыққанды Нэш тепе-теңдігі түсінігі мағыналы шешім болуы мүмкін.

Нэш тепе-теңдіктерін есептеу

Егер ойыншы А-ның басым стратегиясы болса, онда А ойнайтын Нэш тепе-теңдігі бар. Екі ойыншы А мен В жағдайында Нэш тепе-теңдігі бар, онда А ойнайды және В ең жақсы жауап береді. Егер қатаң басым стратегия болса, А барлық Нэш тепе-теңдіктерінде ойнайды. Егер A және B-дің екеуінің де қатаң басым стратегиясы болса, онда әрқайсысы қатаң басым стратегиясын ойнайтын бірегей Нэш тепе-теңдігі бар. Аралас стратегиялы ойындарда Нэш тепе-теңдіктері, ойыншының кез-келген нақты (яғни таза) стратегияны таңдау ықтималдығын әрбір стратегияға осы стратегияны таңдаудың тұрақты ықтималдығын білдіретін айнымалыны беру арқылы есептеуге болады. Ойыншы кездейсоқ таңдауға дайын болу үшін олардың әрбір (таза) стратегия үшін күтілетін табысы бірдей болуы керек. Сонымен қатар, әрбір ойыншының стратегиясы үшін ықтималдықтардың қосындысы 1 болуы керек. Бұл әр стратегияны таңдау ықтималдығын шығаратын теңдеулер жүйесін жасайды. Бұл "көптеген" шекті ойындарда шекті және тақ сандағы Нэш тепе-теңдіктері бар екенін айтады. 1993 жылы Харсаний бұл нәтиженің баламалы дәлелін жариялады. "Көптеген" деген сөздің мағынасы, теңдік саны шексіз немесе жұп санды кез келген ойын өте ерекше, егер оның табысы сәл ғана кездейсоқ өзгертілсе, онда бір ықтималдығымен оның тепе-теңдік саны тақ санға ие болады. Мысалы, тұтқынның дилеммасында бір тепе-теңдік бар, ал жыныстар арасындағы тартыста үш – екі таза және бір аралас, бұл тіпті егер сыйақылар сәл өзгерсе де, солай болады. Тегін ақша ойыны – тепе-теңдік саны жұп санды болатын "ерекше" ойынның мысалы. Онда екі ойыншы сыйлық алу үшін "жоқ" емес, "иә" деп дауыс беруі керек және дауыс беру бір мезгілде өтеді. Екі таза стратегиялық Нэш тепе-теңдігі бар: (иә, иә) және (жоқ, жоқ), ал аралас стратегиялық тепе-теңдік жоқ, өйткені "иә" стратегиясы "жоқ" стратегиясын әлсіз басып озады. "Иә" жауабы "жоқ" жауабына тең, бірақ егер басқа ойыншы "иә" деп жауап беру мүмкіндігі болса, онда "иә" жауабы ең жақсы жауап болады. Алайда, кез келген екі төлемнің 0-де немесе басқа санда тең болу ықтималдығы өте аз, ал ойынның бір немесе үш тепе-теңдігі болады.

If a player A has a dominant strategy then there exists a Nash equilibrium in which A plays In the case of two players A and B, there exists a Nash equilibrium in which A plays and B plays a best response to If is a strictly dominant strategy, A plays in all Nash equilibria. If both A and B have strictly dominant strategies, there exists a unique Nash equilibrium in which each plays their strictly dominant strategy. In games with mixed strategy Nash equilibria, the probability of a player choosing any particular (so pure) strategy can be computed by assigning a variable to each strategy that represents a fixed probability for choosing that strategy. In order for a player to be willing to randomize, their expected payoff for each (pure) strategy should be the same. In addition, the sum of the probabilities for each strategy of a particular player should be 1. This creates a system of equations from which the probabilities of choosing each strategy can be derived. which says that "almost all" finite games have a finite and odd number of Nash equilibria. In 1993, Harsanyi published an alternative proof of the result. "Almost all" here means that any game with an infinite or even number of equilibria is very special in the sense that if its payoffs were even slightly randomly perturbed, with probability one it would have an odd number of equilibria instead. The prisoner's dilemma, for example, has one equilibrium, while the battle of the sexes has three—two pure and one mixed, and this remains true even if the payoffs change slightly. The free money game is an example of a "special" game with an even number of equilibria. In it, two players have to both vote "yes" rather than "no" to get a reward and the votes are simultaneous. There are two pure strategy Nash equilibria, (yes, yes) and (no, no), and no mixed strategy equilibria, because the strategy "yes" weakly dominates "no". "Yes" is as good as "no" regardless of the other player's action, but if there is any chance the other player chooses "yes" then "yes" is the best reply. Under a small random perturbation of the payoffs, however, the probability that any two payoffs would remain tied, whether at 0 or some other number, is vanishingly small, and the game would have either one or three equilibria instead.

Ойын теориясы оқулықтары

Диксит, Авинаш, Сьюзан Скит және Дэвид Райли. Стратегиялық ойындар. W. W. Norton & Company компаниясы. (2009 жылы үшінші басылым). Бакалаврларға арналған оқулық. Бакалавриат және бизнес студенттеріне қолайлы. Фуденберг, Дрю және Жан Тироль (1991) Ойын теориясы MIT Press. Ойын теориясына экономикалық контекстте нақты және егжей-тегжейлі кіріспе. Моргенстерн, Оскар және Джон фон Нейман (1947) Ойындар теориясы және экономикалық мінез-құлық Принстон университетінің баспасы. Жоғары оқу орны деңгейіндегі қазіргі заманғы таныстыру. Есептеу тұрғысынан толық анықтама; 3-тарауды қараңыз. Интернеттен тегін жүктеуге болады.

Нештің түпнұсқалық құжаттары

Нэш, Джон (1950) "n ойыншысы бар ойындардағы тепе-теңдік нүктелері" Ұлттық ғылым академиясының еңбектері 36(1):48–49. Нэш, Джон (1951) "Қоспасыз ойындар" Математика анналы 54(2):286–295.

Басқа сілтемелер

Мелманн, А. (2000) Ойын басталды! Миф және парадокстардағы ойын теориясы, Америка математикалық қоғамы. Насар, Сильвия (1998), "Әдемі Ақыл", Саймон мен Шустер. Авиад Рубинштейн: "P және NP арасындағы жуықтаудың қиындығы", ACM, ISBN 978 1 947487 23 9 (2019 жылдың мамыр айы), DOI: https://doi.org/10.1145/3241304. Нэш тепе-теңдігі есептеуде шешімі қиын мәселе.