Aug 4, 2005, 12:09 AM

Теория на игрите и Равновесието на Наш 

  Podcasts
29659 0 7
28 мин reading

   Тази статия е за живота и работата на американския математик Джон Форбс Наш, който се занимавал в областта на диференциалната геометрия и теорията на игрите. Тъй като неговите трудове обхващат различни сфери на човешкия живот и имат приложения в много и най-разнообразни ситуации, тук ще се опитам да наблегна на по-интересните и лесноразбираеми( доколкото могат да бъдат лесни за разбиране) негови разсъждения/теореми/закони.

 

   И така, кой е Наш? Джон Форбс Наш - Младши е роден на 13 юни 1928 г. в Блуфийлд, Западна Вирджиния в семейството на електроинженер и учителка по английски и латински.Още от малък проявява интерес към науката. Едва дванадесет-годишен  той започва да прави “научни” експерименти в собствената си стая.За него винаги е било ясно ,че вкъщи може да научи повече отколкото ,ако ходи на училище.

След завършване на средното си образование, той се насочва към следване в две направления: индустриална химия и математика в Техническия Институт Карнеги в Питсбърг (от 1945 до 1948 г.), възнамерявайки първо да стане инженер като баща си, но именно тук се заражда дълбоката му обич към математиката. През това време подготвя научно съчинение на тема за търговските сделки. То е публикувано през 1950 г. Впрочем, първата му публикация, съвместна с неговия баща, е на електротехническа тема и е публикувана през 1945 г.

Когато младият Наш кандидатства за университета в Принстън, неговият бивш учител от Карнеги проф. Р. Дж. Дафин в препоръчителното му писмо написва само един ред за Джон:”Това момче е гений”. През 1948 г. постъпва докторант в Принстънския университет. Тук под ръководството на проф. Олбърт Тъкер в продължение на 14 месеца пише дисертация на тема: "Некооперативни игри" и я защитава през май 1950 г. През същата 1950 г Наш публикува и кратка статия на тема: “Равновесни точки в игрите с n (ен) лица” През следващата година излиза от печат в сп. “Annals of mathematics” в преработен вид дисертацията на Наш .В същото списание през 1952 г. Наш публикува статия на съвсем друга тема - "Реални алгебрични многообразия". В нея той доказва важна теорема, разбираема за тесен кръг специалисти. Тази статия има две продължения в същото списание – от 1954г. и от 1956г. Но предложение за награда с Филдсов медал не е последвало. Наш има публикации върху частни диференциални уравнения, описващи движението на флуиди. Последната му научна статия – “Arc structure of singularities”, е от 1966 г. и е публикувана след 10 години в “Duke Mathematical Journal”.

През 1951 г. постъпва на техническа работа в Мичиганския технологически институт. Именно тук той написва статията по алгебрични многообразия. За нея е избран за асистент през 1953 г. Наш е привлечен на работа и от Пентагона. Тук изпълнява задачи по разшифроване на кодове, увличайки се в теорията на кодирането. Междувременно се оженва и има син.През целия му живот Алисиа(жена му) му оказва голяма подкрепа и помощ във всеки труден момент.През 1958 г. Наш за първи път започва да показва болестни симптоми . Напрегнатата и отговорна работа по времето на "студената война" с главни "воюващи" САЩ и СССР, довеждат до психическо заболяване с диагноза: параноидна шизофрения. Наш е въведен принудително в психиатрична клиника и лекуван около 25 години с прекъсвания, когато отново се заема с математическа работа.След проблематичен престой в Париж и Женева ,Наш се завръща в Принстън през 1960г.Честите престои в болници бележат живота му до 1970г.Лекуват го по различни начини, но най-често с инсулинова терапия(insulin coma therapy) .Най-успешното “лекарство” се оказва административното решение на Пристънския математически отдел и компютърния център да разрешат на Наш да използва университетските съоръжения за неговите проучвания. Научни публикации след 1966 г. обаче няма.

 

По-долу са разгледани “правилата”/разсъжденията/законите( дори наричани и теореми) на Джон Наш.Като се вземе в предвид,че неговите разработки като цяло са свързани и се допълват по между си ( тези ,които ще разгледам и тези ,на които няма да мога да се спра),а и се препокриват с тези на много други учени,оттук надолу статията е малко трудно да изглежда подредена. ;)

 

 

          Теория на игрите( Game Theory) и Равновесието на Наш (Nash `s Equilibrium)

 

През 50-те години теорията на игрите е дисциплина, към която проявяват интерес не само математици и икономисти, но и военните. Основите на теорията на игрите са положени в издадената през 1944 г. в Принстън монография "Теория на игрите и икономическото поведение" на американските математици Джон фон Нойман и Оскар Маргенщерн (първият има унгарски произход, а вторият - австрийски). И двамата са работили в Принстънския университтет. Затова е разбираемо и увлечението на Наш още от студентските му години. Теорията на игрите е математическа дисциплина, която изучава математическите модели за вземане на оптимални решения в условията на конфликти. Наличието на конфликти означава, че имаме множество М1 от участници, наречени коалиции на действието, множество М2 от техни стратегии, множество М3 от ситуации, множество М4 от коалиции на интересите и множество М5 от отношения. Системата { М1 , М2 , М3 , М4 , М5 } се нарича игра, а елементите на М1 и М4 - играчи. В теорията на игрите се изяснява понятието решение и съществуването на оптимално решение.

Дисертацията на Наш - "Некооперативни игри" не е голяма по обем - всичко 27 машинописни страници. Но тя съдържа няколко важни постижения, две от които са:
   1. Въвеждане на понятието некооперативии игри. В теорията на игрите преди Наш такова понятие няма - играчите могат да извършват принудителни съглашения, изцяло да се обвързват с определени стратегии. Това липсва при некооперативните игри.
   2. Въвеждане на понятието равновесна точка или равновесие, наричано днес равновесие на Наш. Нека в играта всеки играч има множество от стратегии и множество от съответни функции на възнагражденията. Стратегиите са в равновесие (играта има равновесна точка на Наш), когато стратегиите на кой да е играч максимизират неговата платежна функция, ако стратегиите на останалите играчи са фиксирани.
   Наш извежда редица свойства на равновесието и доказва, че всяка игра с краен брой играчи и непрекъсната платежна функция, притежава поне една равновесна точка. За да стане по-ясно ще приведем съдържанието на една от работите на Наш: "Проста игра на покер с три лица", съвместна с друг математик, публикувана в Годишника на Принстънския университет по математика 1950 г. Разглежда се постановка, при която на всеки играч се раздава по една карта от колода, съдържаща карти от два вида - високи и ниски, и всичките 8 случая са равно възможни. Предварително е направен облог а и е фиксиран размерът b на залаганията. При допълнителни ограничения авторите доказват, че при а<b играта има единствена равновесна точка.

 

   Нека обаче да поясним малко… Теорията на игрите изучава взаимосвързаното взимане на решения, където изходът/резултатът за един участник или “играч” зависи от действията на всички. Ако вие сте играч в такава игра, когато избирате вашия ход на действие или “стратегия” , трябва да вземете под внимание и изборът на другите.Но докато мислите върху решенията на другите играчи, вие ще разберете ,че и те мислят върху вашите такива. На свой ред вие се опитвате да вземете под внимание техните мисли за вашия ход и т.н. Може да ви се стори ,че този вид “мислене за мислите” е трудно и ловко нещо. Всъщност ,някои аспекти, като например изчисляването (разбирането) на мотивите на противниците ,имат наистина сложни модели. Но пък и много стратегически аспекти могат да бъдат изучени и систематизирани в наука-> game theory. За разлика от физиката и химията ,които имат ясно разграничени области за проучване ,теорията на игрите е добре приложима на много места. От всекидневните социални взаимоотношения и спорта до бизнеса и икономиката,политиката ,правото, дипломацията и войната.Някои биолози дори намират връзка между теорията на игрите и теорията за еволюцията на Дарвин в борбата за оцеляване. Теорията на игрите започва с работата на Джон фон Нойман през 20-те години и кулминира в съвместната му книга с Оскар Маргенщерн издадена през 1944г. Те обаче изучават тъй наречените “игри, чиято сума е нула”, където участват само двама играчи с напълно противоположни интереси(например спортни игри или игри подобни на шах).Този вид игри е важен за икономиката, особено ,ако двама души се опитват доброволно да сключат сделка. Наш обаче се занимава с по нормалния и вероятен случай т.е. когато имаме смесица от интереси и различен брой играчи.

“Равновесието на Наш”  в една от горе описаните игри се достига, когато действията на един играч пораждат реакцията на всички други играчи, а техните реакции пък водят отново до неговите встъпителни действия.

Теорията на игрите може грубо да се раздели на две области: “не-кооперативни” (или стратегически) игри и “кооперативни” (или коалиционни) игри (,които впрочем ще разгледаме накрая с примера за затворниците).

В Теорията на игрите , Равновесието на Наш е един вид оптимална стратегия за игра, включваща двама или повече играчи, чрез изходът на която(игра) играчите постигат взаимна полза. Ако за една игра има определена серия/група от стратегии и печалба, която никой играч не може да спечели, ако си промени собствената стратегия ,а другите играчи не си променят своите стратегии, тогава дадената серия/група от стратегии и съответната печалба образуват/съставят равновесието на Наш.Една игра може да има (или да достига) много или нито едно равновесие на Наш. Наш доказва това->Ако в игра позволим смесени стратегии (играчите си избират произволно стратегии в съответствие с определените вероятности), тогава  всяка игра с n на брой играчи, в която всеки играч може да избира от много ,но ограничен брой стратегии, достига поне едно равновесие на Наш(на смесени стратегии). Ако игра има уникално равновесие на Наш и е изиграна между напълно рационални и разумни играчи ,то играчите ще подберат (несъзнателно) такива стратегии , че да се достигне това равновесие. Общо взето Джон Наш открива начин ,по който може да се предвиди изходът на почти всеки вид стратегическо взаимодействие.

Равновесието на Наш е хубава теория, но дали работи в действителност? И да, и не.Предпоставката за “напълно рационални” играчи е не винаги изпълнена,а и много пъти има липсваща информация. В други случаи пък просто ситуацията е твърде сложна за анализиране.

 

Нека да дообясним с примери.

     (Важно е да се отбележи и фактът ,че при неочаквано вдигане на залозите ,при играчите настъпва голяма промяна в поведението.)

        

               Пр.1:  Мария и Ана трябва да си изберат сума между 180 и 300 стотинки. И на двете ще бъде платена по-малката избрана сума(т.е. и двете ще получат стотинки). Едната от двете, която е  избрала по-голямата сума, отделно пък ще трябва да плати наказание в размер на Х стотинки на другата. При равенство в избраните суми няма наказание! Така, ако Мария избере 280 ,а Ана избере 300, печалбата на Мария е 280+Х стотинки, а печалбата на Ана е 280-Х стотинки.(Ако Х>280, то Ана няма да получи нищо, а само ще плати.) Ако Ана мисли ,че Мария ще каже 280, тогава Ана ще иска да обяви 279. Но ,ако Мария мисли ,че Ана ще обяви 279, тогава Мария ще иска да каже 278.И т.н. Единствената съвместима двойка от мисли(,така да се каже,) е ,когато и двете вярват, че другата ще каже 180.

       Опитите с хора са забележителни. Ако Х=180(или дори по-голямо число), почти 80% от хората избират числото/сумата 180, което пък е предвидено от Наш. Ако Х=5, тогава пък почти 80% избират числото 300.

       (Опитите с хора са довели до създаването на поведенческа теория на игрите. В нея се работи с реални хора, а не с онези митични “напълно разумни/рационални”  хора ;) )

 

            Пр.2: (по-известен като “Затворническата дилема”)

 

·         За двама бъдещи-затворници се знае ,че са виновни.Но полицията няма достатъчно доказателства ,за да осъди и двамата без самопризнание.

·         Полицията ги разделя двамата в различни стаи, без каквато и да била връзка помежду им. И двамата трябва да решат какво да правят едновременно .

·         Между затворниците няма никакво (или поне дълго) приятелство, никакво доверие и никакви предварителни уговорки.

·         Как да се сдобият полицаите със самопризнанията на двамата?(това е въпросът ;) )

·         ……

·         Следните възможности са предоставени на затворниците да избират(поотделно разбира се) ->   Ако и двамата се признаят за виновни , то и двамата получават присъди от по 5 години затвор. Ако единият се признае за виновен,а другия –не;тогава този,който си е признал излиза свободен, а другият,който си е замълчал остава в затвора за 20 години. Ако обаче и двамата не си признаят и си замълчат, то тогава и двамата получават само по 1 година затвор.

·         Анализът на това, какво може да се случи, ако двамата затворници се държат “рационално”, следвайки своите лични интереси, е прост пример на Теорията на игрите (Game Theory).

 

 

   

          През 1994г. Джон Ф. Наш, Джон К. Харсанай и Реинхард Селтън получават заедно нобеловата награда за икономика за техните постижения в теорията на игрите. Теорията на игрите, както отбелязва кралската академия на науките в Швеция, “произхожда от изучаването на игри като покера и шаха”, в които “играчите трябва да мислят стъпки напред и да развиват стратегия, основаваща се на очакванията от контра-действията на другите играчи. Подобни стратегически взаимоотношения се наблюдават и в много икономически ситуации, затова теорията на игрите показва ,че е полезна и в икономическия анализ.”

Джон К. Харсанай и Реинхард Селтън доразвиват модела за теорията на игрите на Наш през 60-те години и издават съвместна книга през 1988г.- “Главна теория на равновесния подбор в игрите.” Селтън пък е първият германец ,който получава наградата за икономика.

 

      Според Аристотел ,най-добрите трагедии стават при конфликт между героя и неговата съдба. Те съдържат обрати, моменти на признание, и, накрая, катарзис. Животът на Д-р Джон Наш—ранният му блясък, борбата между болестта му и неговото бавно оздравяване—определено става за гръцка трагедия. Именно той вдъхновява филма “Красив ум”, който има 4 награди Оскар, също и 4 награди златен глобус за 2001г.

 

 

*За по-любознателните и тези ,които са по-наясно с материала искам да спомена теоремата, която Наш доказва в статията си “Реални алгебрични многообразия”, а тя е ->

    “Ако М е дадено гладко компактно k - мерно многообразие, то съществува реално алгебрично многообразие V С R2K+1 и свързана компонента V0 от V такава, че V0 е гладко многообразие, дифеоморфно на М.” 

 

      Също и ,че ->

В рецензията на Д. Гейл в Mathematical Reviews, относно дисертацията на Наш се казва: "Общата крайна n-лична игра е предварително анализирана с разглеждане на две-лична игра, получена с разбиване на множеството на играчите на две множества от коалиции. Тази работа дава едно изцяло ново разглеждане на такива игри, в които кооперацията (коалициите) са изключени. Главният резултат е обобщение на фундаменталната теорема за две-лична игра с нулева сума (съществуване на стойност) в общи n-лични игри, и може да се опише както следва: Нека s1 , s2 ,..., sn означават смесени стратегии на играчите 1,2, ..., n, и нека pi(s1 , s2 ,..., sn) е платежната функция на i-тия играч, където, както обикновено, всяко рi е една n-линейна функция на si-тите. Една n-торка от стратегии (s1 , s2 ,..., sn ) се нарича "равновесна точка", ако за всяко i, pi(s1 , s2 ,..., sn)> pi(s1 , s2 ,.,si',.., sn) където si' е коя да е стратегия на i-тия играч. Теорема: Всяка крайна n-лична игра има равновесна точка. Използвайки тази концепция, авторът дефинира понятието решение на игра (което, впрочем, може и да не съществува).

 

© Ицо All rights reserved.

Comments
Please sign in with your account so you can comment and vote.
  • Наистина поздравления! Съвсем случайно преди 2 дена гледах филма "Красив ум", но нямах и най-малка предства,че всъщност точно за този човек уча в момента. Открих сайта току що случайно и статията много ще ми помогне за лекциите,които посещавам. Браво на автора!
  • БРАВООООООО!!!!!!! Възхитен съм от написаното.
    Jantex (Ицо ) продължавай в същия дух.
  • Статията много ми помогна ! Благодаря
  • е, нищо не разбрах от последната част, но... но ми беше ужасно интересно, страхотна статия и много добре и достъпно написана.
  • Добре подредена информативна статия за един от най-актуалните икономически предмети на изследване и неговия откривател. Нямах идея, че Наш от Наш екуилибриъм е използван за филма с австралийския гладиатор. Браво на Янтекс.
  • Поздравления
    Имаш ли и нещо за друг математик логик Jon Barwise
    Много от колегите на Наш обаче не го обичат -арогантен и често неетичен...
    Има незконороденно дете което не признава за свое
    множество скандали....
    Е то до колкото познавам математици...( живеят почти на границата на изкрейзването - понякога24 часово натоварване) подобно поведение е разбираемо
    По един от Дискавърите имаше документален филм за него...и думата "красиво" отсъстваше...освен в очите на жена му - до себеотричане обичаща го негова бивша студентка
    А Неш по мое му в по-голяма част от живота си е бил луд ( пациент е по-меко)
    г
  • Беше ми страшно интересно да прочета за Наш - гледала съм "Красив ум" и тази статия ми дойде като по поръчка - да разбера всъщност за кого става дума!Поздравления!
Random works
: ??:??