Равновесие Нэша (когда шизофрению невозможно победить – с ней можно справиться:)

Шизофрению невозможно победить ?

Бытует мнение, что Нобелевская премия не присуждается математикам, потому что жена Альфреда Нобеля изменила ему с математиком. Это миф. Альфред Нобель  никогда не был женат. Премия не выдаётся математикам, потому что по убеждению Нобеля отмеченные наградой открытия и изобретения должны быть непосредственно полезны для всех. То есть премия создавалась для изобретателей, и математика была исключена как абстрактная наука.

“Игры разума” – это прокатное русское название полюбившегося мне фильма. Настоящее – «A Beautiful Mind»

Фильм Рона Ховарда   2001 года  получил четыре «Оскара» (за лучший фильм, лучшие адаптированный сценарий, режиссуру и актрису второго плана), награду «Золотой глобус» и был отмечен несколькими призами BAFTA (британская премия за кинематографические достижения)  рассказывает о жизни Джона Нэша — математика, лауреата Нобелевской премии 1994 года.

В ролях:

Расселл Кроу / Russell Crowe, Эд Харрис / Ed Harris, Дженнифер Коннелли / Jennifer Connelly, Кристофер Пламмер / Christopher Plummer, Джадд Хирш / Judd Hirsch, Эдам Голдберг / Adam Goldberg
1947 год. Выдающийся студент Джон Нэш приезжает в Принстон. Мнительный, странноватый, он не находит контакта с окружающим обществом, даже занятия не посещает, всецело погрузившись в свои исследования. Однажды к нему обращается некий секретный агент Паркер, предлагающий Нэшу работать на совершенно секретный отдел ЦРУ. Его задача — анализировать информацию, опубликованную в открытых источниках на предмет поиска в ней секретной информации. Этой информацией обмениваются заговорщики — враги США. Свои отчеты Нэш оставляет в почтовом ящике в условленном месте. Во время одного из своих визитов к почтовому ящику Нэш подвергается нападению заговорщиков и чудом избегает гибели…

Фильм снят в 2001 г по бестселлеру американской журналистки (и профессора экономики Колумбийского университета) Сильвии Назар «A Beautiful Mind: The Life of Mathematical Genius and Nobel Laureate John Nash». Книга – биография Джона Форбса Нэша.

Джон Форбс Нэш-младший (англ. John Forbes Nash, Jr.; род. 13 июня 1928, Блюфилд, Западная Вирджиния) — американский математик, работающий в области теории игр и дифференциальной геометрии. Лауреат Нобелевской премии по экономике 1994 года «За анализ равновесия в теории некооперативных игр» (вместе с Райнхардом Зелтеном и Джоном Харсани).
Известен широкой публике большей частью по биографической драме Рона Ховарда «Игры разума» (англ. A Beautiful Mind) о его математическом гении и борьбе с шизофренией.

в Политехническом институте Карнеги (ныне частный Университет Карнеги-Меллона), где Нэш пробовал изучать химию, прослушал курс международной экономики, а потом окончательно утвердился в решении заняться математикой. В 1948 году, окончив институт с двумя дипломами — бакалавра и магистра, — он поступил в Принстонский университет.   Институтский преподаватель Нэша Ричард Даффин снабдил его одним из самых лаконичных рекомендательных писем. В нём была единственная строчка: «Этот человек — гений!» (англ. This man is а genius).

Учась в университете в  Принстоне, Джон Нэш услышал о теории игр, в ту пору только представленной Джоном фон Нейманом и Оскаром Моргенштерном. Теория игр поразила его воображение, да так, что в 20 лет Джон Нэш сумел создать основы научного метода, сыгравшего огромную роль в развитии мировой экономики. В 1949 году 21-летний учёный написал диссертацию о теории игр. Сорок пять лет спустя он получил за эту работу Нобелевскую премию по экономике. Вклад Нэша описали так: «За фундаментальный анализ равновесия в теории некооперативных игр».

Нейман и Моргенштерн занимались так называемыми играми с нулевой суммой, в которых выигрыш одной стороны равен проигрышу другой. В 1950—1953 годах Нэш опубликовал четыре, без преувеличения, революционные работы, в которых представил глубокий анализ игр с ненулевой суммой — класса игр, в которых сумма выигрыша выигравших участников не равна сумме проигрыша проигравших участников. Примером такой игры могут стать переговоры об увеличении зарплаты между профсоюзом и руководством компании. Эта ситуация может завершиться либо длительной забастовкой, в которой пострадают обе стороны, либо достижением взаимовыгодного соглашения. Нэш сумел разглядеть новое лицо конкуренции, смоделировав ситуацию, впоследствии получившую название «равновесие по Нэшу» или «некооперативное равновесие», при которой обе стороны используют идеальную стратегию, что и приводит к созданию устойчивого равновесия. Игрокам выгодно сохранять это равновесие, так как любое изменение только ухудшит их положение.

В 1951 году Джон Нэш стал работать в Массачусетском Технологическом институте (МТИ) в Кэмбридже. Там он написал ряд статей по вещественной алгебраической геометрии и теории римановых многообразий, высоко оценённые современниками. Но коллеги Джона избегали — его работы математически обосновывали теорию прибавочной стоимости Карла Маркса, которая тогда во время «охоты на ведьм» считалась в США еретической.

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

В теории игр равновесием Нэша (названным в честь Джона Форбса Нэша, который предложил его) называется тип решений игры двух и более игроков, в котором ни один участник не может увеличить выигрыш, изменив своё решение в одностороннем порядке, когда другие участники не меняют решения. Такая совокупность стратегий выбранных участниками и их выигрыши называются равновесием Нэша.

Концепция равновесия Нэша (РН) впервые использована не Нэшем; Антуан Огюст Курно показал, как найти то, что мы называем равновесием Нэша, в игре Курно. Соответственно, некоторые авторы называют его равновесием Нэша-Курно. Однако Нэш первым показал в своей диссертации Некооперативные игры (1950), что равновесия Нэша должны существовать для всех конечных игр с любым числом игроков. До Нэша это было доказано только для игр с 2 участниками с нулевой суммой Джоном фон Нейманом и Оскаром Моргенштерном (1947).

Игра может иметь равновесие Нэша в чистых стратегиях или в смешанных (то есть при выборе чистой стратегии стохастически с фиксированной частотой). Нэш доказал, что если разрешить смешанные стратегии, тогда в каждой игре n игроков будет хотя бы одно равновесие Нэша.

Дилемма двух бандитов

В теории игр дилемма заключённого  “ДЗ”  (реже употребляется название «дилемма бандита») — некооперативная игра, в которой игроки стремятся получить выгоду, сотрудничая друг с другом или предавая. Как во всей теории игр, предполагается, что игрок («заключённый») максимизирует свой собственный выигрыш, не заботясь о выгоде других.

В дилемме заключённого предательство строго доминирует над сотрудничеством, поэтому единственное возможное равновесие — предательство обоих участников. Проще говоря, неважно, что сделает другой игрок, каждый выиграет больше, если предаст. Поскольку в любой ситуации предать выгоднее, чем сотрудничать, все рациональные игроки выберут предательство.

Ведя себя по отдельности рационально, вместе участники приходят к нерациональному решению: если оба предадут, они получат в сумме меньший выигрыш, чем если бы сотрудничали (единственное равновесие в этой игре не ведёт к Парето-оптимальному решению). В этом и заключается дилемма.

В повторяющейся дилемме заключённого игра происходит периодически, и каждый игрок может «наказать» другого за несотрудничество ранее. В такой игре сотрудничество может стать равновесием, а стимул предать может перевешиваться угрозой наказания (с ростом числа итераций равновесие Нэша стремится к Парето-оптимуму).

Во всех судебных системах кара за бандитизм (совершение преступлений в составе организованной группы) намного тяжелее, чем за те же преступления, совершённые в одиночку (отсюда альтернативное название — «дилемма бандита»).

Классическая формулировка дилеммы заключённого такова:

Двое преступников, А и Б, попались примерно в одно и то же время на сходных преступлениях. Есть основания полагать, что они действовали по сговору, и полиция, изолировав их друг от друга, предлагает им одну и ту же сделку: если один свидетельствует против другого, а тот хранит молчание, то первый освобождается за помощь следствию, а второй получает максимальный срок (10 лет). Если оба молчат, дело проходит по другой статье, и они приговариваются к 6 месяцам. Если оба свидетельствуют против друг друга, они получают минимальный срок (по 2 года). Каждый заключённый выбирает, молчать или свидетельствовать против другого. Однако ни один из них не знает точно, что сделает другой. Что произойдёт?

Дилемма появляется, если предположить, что оба заботятся только о минимизации собственного срока заключения.

Представим рассуждения одного из заключённых. Если партнёр молчит, то лучше его предать и выйти на свободу (иначе — полгода тюрьмы). Если партнёр свидетельствует, то лучше тоже свидетельствовать против него, чтобы получить 2 года (иначе — 10 лет). Стратегия «свидетельствовать» строго доминирует над стратегией «молчать». Аналогично другой заключённый приходит к тому же выводу.

С точки зрения группы (этих двух заключённых) лучше всего сотрудничать друг с другом, хранить молчание и получить по полгода, так как это уменьшит суммарный срок заключения. Любое другое решение будет менее выгодным. Это очень наглядно демонстрирует, что в игре с ненулевой суммой Парето-оптимум может быть противоположным равновесию Нэша.

Примеры с заключёнными  могут показаться надуманными, но на самом деле есть множество примеров взаимодействия людей и животных, имеющие такую же матрицу выигрышей. Поэтому ДЗ представляет интерес социальным наукам, таким как экономика, политика и социология, а также разделам биологии — этологии и эволюционной биологии. Многие природные процессы были обобщены в модели, в которых живые существа участвуют в бесконечных играх типа дилеммы заключённого. Такая широкая применимость ДЗ придаёт этой игре значительную важность.

В фильме есть очень интересная сцена: Нэш-студент с друзьями пришли в бар и видят трёх девушек, одна из которых – красавица, и которую хочет “снять” каждый из трёх друзей. Молодой учёный  анализирует ситуацию и строит математические прогнозы развития событий при различных тактиках поведения. И объясняет друзьям, какая модель может иметь наибольшую статистическую вероятность успеха. Поставлено и снято блестяще ! Фильм стоит смотреть уже только ради этой сцены.

В политологии, к примеру, сценарий ДЗ часто используется для иллюстрации проблемы двух стран, вовлечённых в гонку вооружений. Обе будут заявлять, что у них есть две возможности: либо увеличить расходы на военные нужды, либо сокращать вооружения. Ни одна из сторон не может быть уверена, что другая будет соблюдать договорённость, следовательно, обе будут стремиться к военной экспансии. Это можно считать теоретическим объяснением политики устрашения. Похожие явления наблюдаются и в автоспорте — «Формула-1», где последние 20 лет происходит гонка бюджетов команд. Из-за этого число машин-участников сократилось с 36 в 1990 году до 20 в 2003.

В велогонках дилемма заключённого возникает, когда два сильных гонщика оторвались от общей группы. Каждый из них может либо предоставить соседу слипстрим («сотрудничать»), либо ехать сзади («предать»). Для обоих идеалом будет, когда они по очереди «висят» друг у друга на хвосте — но всегда есть желание не дать соседу слипстрима (тогда тот постепенно устаёт и «скатывается» в пелотон, а ты финишируешь с большим отрывом).

Случай дилеммы заключённого может быть найден в бизнесе. Две конкурирующие фирмы должны определиться, сколько средств тратить на рекламу. Эффективность рекламы и прибыль каждой фирмы уменьшается с ростом расходов на рекламу у конкурента. Обе фирмы принимают решение увеличить расходы на рекламу, при этом их доли рынка и, возможно, объёмы продаж остаются неизменными, а прибыль сокращается. Предел гонки рекламных бюджетов — прибыль, впрочем, они могут пытаться некоторое время работать и в убыток. Фирмы могут пойти на соглашение о сокращении расходов на рекламу, но всегда есть стимул его нарушить.

В олигополистических рынках ценовая политика — это повторяющаяся ДЗ. Обычно олигополисты сотрудничают друг с другом и не доводят ситуацию до «ценовой войны».

Уильям Паундстоун в книге о дилемме заключённого описывает ситуацию в Новой Зеландии, где газетные ящики оставляют открытыми. Газету можно взять, не заплатив за неё, но мало кто так делает, потому что большинство осознаёт вред, который был бы, если бы все воровали газеты. Поскольку ДЗ в чистом виде одновременна для всех игроков (никто не может повлиять на решения других), эта распространённая линия рассуждений называется «магическое мышление»[3].

Теоретическое заключение ДЗ — одна из причин, почему во многих странах сделка о признании вины запрещена. Часто сценарий ДЗ повторяется очень точно: в интересах обоих подозреваемых сознаться и свидетельствовать против другого подозреваемого, даже если оба невиновны. Возможно, наихудший случай — когда только один виноват, в этом случае невиновный вряд ли сознаётся в чём либо, а виновный пойдёт на это и даст показания против невиновного.

Многие дилеммы в реальной жизни включают множество игроков. Хотя и метафорическую, «трагедию общин» Ардена можно рассматривать как обобщение ДЗ для множества игроков. Каждый житель общины выбирает — пасти ли скот на общем пастбище и получить выгоду, истощая его ресурсы, либо ограничить свой доход. Коллективный результат от всеобщего (или частого) максимального использования пастбища — низкий доход (ведущий к разрушению общины). Однако такая игра не является формальной, поскольку может быть разбита на последовательность классических игр с 2 участниками.

В книге «Эволюция кооперации» (1984) Роберт Аксельрод en:Robert Axelrod исследовал расширение сценария ДЗ, которое он назвал повторяющаяся дилемма заключённого (ПДЗ). В ней участники делают выбор снова раз за разом и помнят предыдущие результаты. Аксельрод пригласил академических коллег со всего мира, чтобы разработать компьютерные стратегии, чтобы соревноваться в чемпионате по ПДЗ. Программы, вошедшие в него, различались по алгоритмической сложности, начальной враждебности, способности к прощению и так далее.
Аксельрод открыл, что если игра повторялась долго среди множества игроков, каждый с разными стратегиями, «жадные» стратегии давали плохие результаты в долгосрочном периоде, тогда как более «альтруистические» стратегии работали лучше, с точки зрения собственного интереса. Он использовал это, чтобы показать возможный механизм эволюции альтруистического поведения из механизмов, которые изначально чисто эгоистические, через естественный отбор.

Лучшей детерминистской стратегией оказалась «Око за око» (англ. Tit for Tat), которую разработал и выставил на чемпионат Анатолий Рапопорт. Она была простейшей из всех участвовавших программ, состояла всего из 4 строк кода на языке Бейсик. Стратегия проста: сотрудничать на первой итерации игры, после этого игрок делает то же самое, что делал оппонент на предыдущем шаге. Чуть лучше работает стратегия «Око за око с прощением». Когда оппонент предаёт, на следующем шаге игрок иногда в любом случае сотрудничает с небольшой вероятностью (1-5 %). Это позволяет случайным образом выйти из цикла взаимного предательства. Она лучше всего работает, когда в игру вводится недопонимание — когда решение одного игрока сообщается другому с ошибкой.

Анализируя стратегии, набравшие лучшие результаты, Аксельрод назвал несколько условий, необходимых, чтобы стратегия получила высокий результат:

Добрая
важнейшее условие — стратегия должна быть «доброй», то есть не предавать, пока этого не сделает оппонент. Почти все стратегии-лидеры были добрыми. Поэтому чисто эгоистичная стратегия по чисто эгоистическим причинам не будет первой «бить» соперника.
Мстительная
успешная стратегия не должна быть слепым оптимистом. Она должна всегда мстить. Пример немстительной стратегии — всегда сотрудничать. Это очень плохой выбор, поскольку «подлые» стратегии воспользуются этим.
Прощающая
другое важное качество успешных стратегий — уметь прощать. Отомстив, они должны вернуться к сотрудничеству, если оппонент не продолжает предавать. Это предотвращает бесконечное мщение друг другу и максимизирует выигрыш.
Не завистливая
последнее качество — не быть завистливым, то есть не пытаться набрать больше очков, чем оппонент (что в принципе невозможно для «доброй» стратегии, то есть добрая стратегия никогда не может набрать больше очков, чем оппонент).

Таким образом, Аксельрод пришёл к утопично звучащему выводу, что эгоистичные индивиды во имя их же эгоистического блага будут стремиться быть добрыми и прощающими и не завистливыми.

Рассмотрим снова модель гонки вооружений. Был дан вывод, что единственная рациональная стратегия — вооружаться, даже если обе страны хотели бы тратить ВВП на масло, а не пушки.  Интересно, что попытки продемонстрировать, что вывод ДЗ работает на практике (делая анализ «высоких» и «низких» военных расходов между периодами, на основе предположений ПДЗ), часто показывают, что такого поведения не происходит (например, греческие и турецкие военные расходы меняются не в соответствии со стратегией «око за око», а вероятнее всего следуют внутренней политике). Это может быть примером рационального поведения, отличающегося от одноразовой и многоходовой игр.

Если в одноходовой игре в любом случае доминирует стратегия предать, то в многоходовой оптимальная стратегия зависит от поведения других участников. К примеру, если среди населения все друг друга обманывают, а один ведёт себя по принципу «око за око», он оказывается в небольшом проигрыше из-за потери на первом ходе. В такой популяции оптимальная стратегия — всегда предавать. Если же число исповедующих принцип «око за око» больше, то результат уже зависит от их доли в обществе.

Определить оптимальную стратегию можно двумя путями:

* Равновесие Байеса-Нэша: если определено статистическое распределение встречаемого поведения (например, 33 % «око за око», 33 % всегда обманывают и 33 % всегда сотрудничают), то стратегию можно вычислить математически. Этим детально занимается теория эволюционной динамики.
* По методу Монте-Карло делались симуляции популяций, где индивиды с низкими результатами вымирали, а с высокими воспроизводились (использовался генетический алгоритм поиска оптимальной эволюционно стабильной стратегии). Структура поведения в конечной популяции зависит от структуры в начале.

Хотя стратегия «око за око» считалась самой удачной простой стратегией, команда Университета Саутгемптона из Англии (под руководством профессора Николаса Дженнингса ) представила новую стратегию на 20-ю годовщину Чемпионата по ПДЗ. Эта стратегия оказалась более успешной, чем «око за око». Она основывалась на взаимодействии между программами, чтобы получить максимальный счёт для одной из них. Университет выставил на чемпионат 60 программ, которые распознавали друг друга по ряду действий на первых 5-10 ходах. Узнав другую, одна программа всегда сотрудничала, а другая предавала, что давало максимум очков предателю. Если программа понимала, что оппонент — не саутгемптонский, она дальше всё время предавала его, чтобы минимизировать результат соперника. В результате эта стратегия заняла первые три места в соревновании, как и несколько мест подряд ниже.

Хотя эта эволюционно стабильная стратегия оказалась более эффективной в соревновании, это было достигнуто за счёт того, что в этом конкретном соревновании команда могла участвовать несколькими агентами. Если игрок может контролировать только одного агента, «око за око» оказывается лучшей. Она также соблюдает правило запрета на коммуникации между игроками. То, что саутгемптонские программы исполняли «ритуальный танец» в первые 10 ходов, чтобы узнать друг друга, только подтверждает, насколько важна коммуникация в сдвиге баланса игры.

Если ПДЗ играется ровно N раз (некая известная константа N), есть ещё один интересный факт. Равновесие Нэша — всегда предавать. Доказываем по индукции: если оба сотрудничают, на последнем ходу выгодно предать, тогда у соперника не будет возможности отомстить. Поэтому оба предадут друг друга на последнем ходу. Раз соперник предаст на последнем ходу в любом случае, любой игрок захочет предать на предпоследнем ходу, и так далее. Чтобы сотрудничество оставалось выгодным, необходимо, чтобы будущее было неопределённым для обоих игроков. Одно из решений — делать число N случайным и подсчитывать результаты по среднему выигрышу за ход.

Дилемма заключённого — фундаментальная для некоторых теорий о взаимодействии людей и доверии. Из предположения модели ДЗ, что транзакция между двумя людьми требует доверия, доверительное поведение в популяциях может быть смоделировано при помощи многоигроковой повторяющейся версии игры. Это годами вдохновляло многих учёных. В 1975 году Грофман и Пул оценивали число работ, посвящённых этой теме, в количестве около 2000.

 Интересная информация о фильме “Игры разума” :

* На роль режиссёра фильма был приглашён Роберт Редфорд, но его не устроило расписание съёмок.
* На роль Джона Нэша пробовался Том Круз, а на роль Алисии — Сальма Хайек. Любопытно, что она родилась в том же городке Эль-Сальвадор, что и её несостоявшаяся героиня.
* Когда Нэш впервые видит Паркера, он обращается к нему как к «большому брату» (намёк на роман Оруэлла «1984»). Ещё одна отсылка к Оруэллу происходит позднее, когда мы видим номер на двери кабинета Нэша — 101.
* В роли рукописи, которую молодой Джон Нэш показывает своему куратору, профессору Хелинджеру, выступает подлинная копия статьи, напечатанной в журнале Econometrica под заголовком «Задача совершения сделки».
* Сценарист фильма Акива Голдсман имел немалый опыт общения с душевнобольными людьми: в свою бытность врачом он лично разрабатывал методики восстановления душевного здоровья детей и взрослых.
* Куратором фильма по математической части стал профессор Барнардского колледжа Дэйв Байер — именно его рукой Расселл Кроу «выводит» на доске мудрёные формулы.
* «Мудрёные формулы» при внимательном рассмотрении представляют собой просто бессмысленный набор греческих букв, стрелок и математических знаков. Также можно заметить, что формулы, написанные на доске в кабинете Нэша, не изменяются даже спустя несколько лет по фильму.
* В отличие от своего экранного двойника, отличавшегося редкой преданностью своей «половинке», реальный Джон Нэш в своей жизни несколько раз был женат, а в двадцать с небольшим лет усыновил внебрачного ребенка.
* В части фильма, относящейся к периоду вручения Нобелевской премии (1994 г.), Нэш говорит о том, что якобы принимает антипсихотики нового типа, однако в действительности Джон Нэш отказался от них еще в 1970 году, и его ремиссия не была связана с приемом нейролептиков.
* Несколько раньше Ричард Доннер снял фильм «Теория заговора» 1997 г., который имеет очень схожий сюжет — слегка «ненормальный» герой фильма в открытых публикациях СМИ ищет (и находит) факты, свидетельствующие в пользу различных «теорий заговора» и пытается сообщить об этом «куда следует».
* В фильме Сиднея Поллака «Три дня Кондора» подобной же деятельностью (поиск секретной информации в открытых источниках) занимается целое подразделение ЦРУ.
* В ряде эпизодов можно заметить призрачность персонажей, сотворённых разумом Нэша. Например в эпизоде, когда главный герой знакомится с племянницей своего призрачного друга, она бежит по лужайке, заполненной голубями, и пытается их спугнуть. Птицы же не обращают на неё никакого внимания.

Источник: psycho.by

Комментарии: