Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Департамент образования города Москвы

Государственное образовательное учреждение среднего профессионального образования колледжа предпринимательства № 15

Джон Форбс Нэш младший

математический моделирование теория игра

Выпонила:

Студентка группы 203

Емельянова Анастасия

Москва 2012



Содержание

Введение

1. Джон Форбс Нэш младший

2. Биография

3. Теория игр

4. Равновесие Нэша

5. Теорема Нэша--Кейпера

6. Теорема Нэша о регулярных вложениях

7. Задача о сделках

8. Письмо Джона Нэша в АНБ от 1955 года

Заключение



Введение

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

Фильм, построенный на реальных событиях, фильм-биография, у которого, казалось бы, нет недостатков. «Игры разума» - трогательный, эмоционально заряженный фильм с подробным изложением жизни блестящего академика, который страдает шизофренией. Пронзительная история о том, как сложно найти тонкую грань между гениальностью и безумием, и о том, могут ли эти два фактора существовать друг без друга, не оставит равнодушным ни одного из тех, кто собрался посмотреть этот фильм.

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

На этой фотографии идет сравнение между настоящим Джон Нэшом и киношным (Рассел Айра Кроу).

«Я начал интеллектуально преодолевать некоторые элементы иллюзорного образа мыслей, которые характеризовали мою жизненную ориентацию». В своей автобиографии профессор Джон Нэш математически краток, и единой фразой описал содержание будущего фильма.



1. Джон Форбс Нэш младший

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

Теория игр -- это раздел прикладной математики, точнее -- исследования операций. Чаще всего методы теории игр находят применение в экономике, чуть реже в других общественных науках -- социологии, политологии, психологии, этике и других. Начиная с 1970-х годов её взяли на вооружение биологи для исследования поведения животных и теории эволюции. Очень важное значение она имеет для искусственного интеллекта и кибернетики, особенно с проявлением интереса к интеллектуальным агентам. и дифференциальной геометрии. Лауреат Нобелевской премии по экономике 1994 года «За анализ равновесия в теории некооперативных игр Некооперативная игра -- термин теории игр. Некооперативной игрой называется математическая модель взаимодействия нескольких сторон (игроков), в процессе которого они не могут формировать коалиции и координировать свои действия.» (вместе с Райнхардом Зельтеном и Джоном Харсани). Известен широкой публике большей частью по биографической драме Рона Ховарда «Игры разума» (англ. A Beautiful Mind) о его математическом гении и борьбе с шизофренией.

Участник IV, V Астанинского экономического форума, принимал участие в обсуждениях по Казахстанскому и зарубежному опыту развития малого и среднего бизнеса. В марте 2011г. присвоено звание Почетный Профессор Евразийского экономического клуба ученных.

Джон Нэш в 2007 году

Дата рождения: 13 июня 1928 (84 года)

Место рождения: Блюфилд, Западная Виргиния, США

Страна: США

Научная сфера: Математика, экономика

Место работы: Массачусетский технологический институт

Альма-матер: Технологический институт Карнеги Принстонский университет

Известен как: Равновесие Нэша

Теорема Нэша -- Кейпера

Алгебраическая геометрия

Награды и премии: Нобелевская премия -- 1994 Нобелевская премия по экономике (1994)

2. Биография

Джон Нэш родился 13 июня 1928 года в Блюфилде, штат Западная Виргиния, в строгой протестантской семье. Отец работал инженером в компании Appalachian Electric Power, мать до замужества успела 10 лет проработать школьной учительницей. В школе учился средне, а математику вообще не любил -- в школе её преподавали скучно. Когда Нэшу было 14 лет, к нему в руки попала книга Эрика Т. Белла «Творцы математики». «Прочитав эту книгу, я сумел сам, без посторонней помощи, доказать малую теорему Ферма» -- пишет Нэш в автобиографии. Так его математический гений заявил о себе. Но это было только начало.

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

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

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

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

Нэшу приходится оставить МТИ, хотя он числился там профессором до 1959, и он уезжает в Калифорнию в корпорацию RAND, занимающуюся аналитическими и стратегическими разработками для правительства США, в которой работали ведущие американские учёные. Там, опять-таки благодаря своим исследованиям в области теории игр, Нэш стал одним из ведущих специалистов в области ведения холодной войны. Хотя корпорация RAND известна как приют диссидентов, находящихся в оппозиции Вашингтону, но даже там Джон не ужился. В 1954 он был уволен после того, как полиция его арестовала за непристойное поведение -- переодевание в мужской комнате на пляже в Санта-Монике.

Вскоре Джон Нэш встретил студентку, колумбийскую красавицу Алисию Лард, и в 1957 году они поженились. В июле 1958 года журнал Fortune назвал Нэша восходящей звездой Америки в «новой математике». Вскоре жена Нэша забеременела, но это совпало с болезнью Нэша -- у него появились симптомы шизофрении. В это время Джону было 30 лет, а Алисии -- 26. Алисия пыталась скрыть всё происходящее от друзей и коллег, желая спасти карьеру Нэша. Ухудшение состояния мужа все сильнее угнетало Алисию. В 1959 году он лишился работы. Через некоторое время Нэш был принудительно помещён в частную психиатрическую клинику в пригороде Бостона, McLean Hospital, где ему поставили диагноз «параноидальная шизофрения» и подвергли психофармакологическому лечению. Адвокату Нэша удалось добиться его освобождения из госпиталя через 50 дней. После выписки Нэш решил уехать в Европу. Алисия оставила новорождённого сына у своей матери и последовала за мужем. Нэш пытался получить статус политического беженца во Франции, Швейцарии и ГДР и отказаться от американского гражданства. Однако под давлением со стороны Государственного департамента США эти страны отказали Нэшу в убежище. Кроме того, за действиями Нэша следил американский военно-морской атташе, который блокировал его обращения в посольства разных стран. Наконец властям США удалось добиться возвращения Нэша -- он был арестован французской полицией и депортирован в США. По возвращении они обосновались в Принстоне, где Алисия нашла работу. Но болезнь Нэша прогрессировала: он постоянно чего-то боялся, говорил о себе в третьем лице, писал бессмысленные почтовые карточки, звонил бывшим коллегам. Они терпеливо выслушивали его бесконечные рассуждения о нумерологии и состоянии политических дел в мире.

В январе 1961 года полностью подавленная Алисия, мать Джона и его сестра Марта приняли трудное решение: поместить Джона в Trenton State Hospital в Нью-Джерси, где Джон прошёл курс инсулиновой терапии -- жёсткое и рискованное лечение, 5 дней в неделю в течение двух с половиной месяцев. После выписки коллеги Нэша из Принстона решили ему помочь, предложив ему работу в качестве исследователя, однако Джон опять отправился в Европу, но на этот раз один. Домой он отправлял только загадочные письма. В 1962 году, после трёх лет смятения, Алисия развелась с Джоном. При поддержке матери она вырастила сына сама. Впоследствии у него также развилась шизофрения.

Несмотря на развод Нэша с Алисией, коллеги-математики продолжали помогать Нэшу -- они дали ему работу в университете и устроили встречу с психиатром, который выписал антипсихотические лекарства. Состояние Нэша улучшилось, и он стал проводить время с Алисией и своим первым сыном Джоном Дэвидом. «Это было очень обнадёживающее время, -- вспоминает сестра Джона Марта. -- Это был достаточно долгий период. Но затем все стало меняться». Джон перестал принимать лекарства, опасаясь, что они могут вредить мыслительной активности и симптомы шизофрении опять проявились.

В 1970 году Алисия Нэш, будучи уверенной, что, предав мужа, совершила ошибку, приняла его вновь, теперь уже как пенсионера, и это, возможно, спасло учёного от состояния бездомности. В последующие годы Нэш продолжал ходить в Принстон, записывая на досках странные формулы. Студенты Принстона прозвали его «Фантомом». Затем в 1980-х годах Нэшу стало заметно лучше -- симптомы отступили и он стал более вовлечённым в окружающую жизнь. Болезнь, к удивлению врачей, стала отступать. На самом деле, Нэш стал учиться не обращать на неё внимания и вновь занялся математикой. «Сейчас я мыслю вполне здраво, как всякий учёный, -- пишет Нэш в автобиографии. -- Не скажу, что это вызывает у меня радость, какую испытывает всякий выздоравливающий от физического недуга. Здравое мышление ограничивает представления человека о его связи с космосом».

11 октября 1994 года, в возрасте 66 лет, Джон Нэш получил Нобелевскую Премию за свою работу по теории игр. Однако он был лишён возможности прочитать традиционную Нобелевскую лекцию в Стокгольмском университете, так как организаторы опасались за его состояние. Вместо этого был организован семинар (с участием лауреата), на котором обсуждался его вклад в теорию игр. После этого Джон Нэш всё же был приглашён прочитать лекцию в другом университете -- Уппсалы. По словам приглашавшего его профессора Математического института университета Уппсалы Кристера Кисельмана, лекция была посвящена космологии.

В 2001 году, через 38 лет после развода, Джон и Алисия вновь поженились. Нэш вернулся в свой офис в Принстоне, где продолжает заниматься математикой. В 2008 году Джон Нэш выступил с докладом на тему «Ideal Money and Asymptotically Ideal Money» на международной конференции Game Theory and Management в Высшей Школе Менеджмента Санкт-Петербургского Государственного Университета.

3. Теория игр

Дж. Нэш в 1949 году пишет диссертацию по теории игр, через 45 лет он получает Нобелевскую премию по экономике. Дж. Нэш после окончания Политехнического института Карнеги с двумя дипломами -- бакалавра и магистра -- поступил в Принстонский университет, где посещал лекции Джона фон Неймана. В своих трудах Дж. Нэш разработал принципы «управленческой динамики». Первые концепции теории игр анализировали антагонистические игры, когда есть проигравшие и выигравшие за их счет игроки. Нэш разрабатывает методы анализа, в которых все участники или выигрывают, или терпят поражение. Эти ситуации получили названия «равновесие по Нэшу», или «некооперативное равновесие», в ситуации стороны используют оптимальную стратегию, что и приводит к созданию устойчивого равновесия. Игрокам выгодно сохранять это равновесие, так как любое изменение ухудшит их положение. Эти работы Дж. Нэша сделали серьёзный вклад в развитие теории игр, были пересмотрены математические инструменты экономического моделирования. Дж. Нэш показывает, что классический подход к конкуренции А. Смита, когда каждый сам за себя, неоптимален. Более оптимальны стратегии, когда каждый старается сделать лучше для себя, делая лучше для других.

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

В 1960--1970 гг. интерес к теории игр угасает, несмотря на значительные математические результаты, полученные к тому времени. С середины 1980-х гг. начинается активное практическое использование теории игр, особенно в экономике и менеджменте. За последние 20 -- 30 лет значение теории игр и интерес значительно растет, некоторые направления современной экономической теории невозможно изложить без применения теории игр.

Большим вкладом в применение теории игр стала работа Томаса Шеллинга, нобелевского лауреата по экономике 2005 г. «Стратегия конфликта». Т. Шеллинг рассматривает различные «стратегии» поведения участников конфликта. Эти стратегии совпадают с тактиками управления конфликтами и принципами анализа конфликтов в конфликтологии (это психологическая дисциплина) и в управлении конфликтами в организации (теория менеджмента). В психологии и других науках используют слово «игра» в других смыслах, нежели чем в математике. Некоторые психологи и математики скептически относятся к использованию этого термина в других смыслах, сложившихся ранее. Культурологическое понятие игры было дано в работе Йохана Хёйзинга «Homo Ludens» (статьи по истории культуры), автор говорит об использовании игр в правосудии, культуре, этике.. говорит о том, что игра старше самого человека, так как животные тоже играют. Понятие игры встречается в концепции Эрика Бёрна «Игры, в которые играют люди, люди, которые играют в игры». Это сугубо психологические игры, основанные на трансакционном анализе. Понятие игры у Й. Хёзинга отличается от интерпретации игры в теории конфликтов и математической теории игр. Игры также используются для обучения в бизнес-кейсах, семинарах Г.П. Щедровицкого, основоположника организационно-деятельностного подхода. Во время Перестройки в СССР Г. П. Щедровицкий провел множество игр с советскими управленцами. По психологическому накалу ОДИ (организационно-деятельностные игры) были так сильны, что служили мощным катализатором изменений в СССР. Сейчас в России сложилось целое движение ОДИ. Критики отмечают искусственную уникальность ОДИ. Основой ОДИ стал Московский методологический кружок (ММК).

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

Нобелевскими лауреатами по экономике за достижения в области теории игр и экономической теории стали: Роберт Ауманн, Райнхард Зелтен, Джон Нэш, Джон Харсаньи, Уильям Викри, Джеймс Миррлис, Томас Шеллинг, Джордж Акерлоф, Майкл Спенс, Джозеф Стиглиц, Леонид Гурвиц, Эрик Мэскин, Роджер Майерсон, Ллойд Шепли, Элвин Рот.

Представление игр

Игры представляют собой строго определённые математические объекты. Игра образуется игроками, набором стратегий для каждого игрока и указания выигрышей, или платежей, игроков для каждой комбинации стратегий. Большинство кооперативных игр описываются характеристической функцией, в то время как для остальных видов чаще используют нормальную или экстенсивную форму. Характеризующие признаки игры как математической модели ситуации:

- наличие нескольких участников;

- неопределенность поведения участников, связанная с наличием у каждого из них нескольких вариантов действий;

- различие (несовпадение) интересов участников;

- взаимосвязанность поведения участников, поскольку результат, получаемый каждым из них, зависит от поведения всех участников;

- наличие правил поведения, известных всем участникам.

Экстенсивная форма

Игра «Ультиматум» в экстенсивной форме

Игры в экстенсивной, или расширенной, форме представляются в виде ориентированного дерева, где каждая вершина соответствует ситуации выбора игроком своей стратегии. Каждому игроку сопоставлен целый уровень вершин. Платежи записываются внизу дерева, под каждой листовой вершиной.

На рисунке -- игра для двух игроков. Игрок 1 ходит первым и выбирает стратегию F или U. Игрок 2 анализирует свою позицию и решает -- выбрать стратегию A или R. Скорее всего первый игрок выберет U, а второй -- A (для каждого из них это оптимальные стратегии); тогда они получат соответственно 8 и 2 очка.

Экстенсивная форма очень наглядна, с её помощью особенно удобно представлять игры с более чем двумя игроками и игры с последовательными ходами. Если же участники делают одновременные ходы, то соответствующие вершины либо соединяются пунктиром, либо обводятся сплошной линией.

Нормальная форма

	Игрок 2 стратегия 1	Игрок 2 стратегия 2
Игрок 1 Стратегия 1	4,3	-1, -1
Игрок 2 Стратегия 2	0,0	3,4
Нормальная форма для игры с 2 игроками, у каждого из которых по 2 стратегии.

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

Игроки выбирали стратегии с максимальным для себя результатом, но проиграли, из-за незнания хода другого игрока. Обычно в нормальной форме представляются игры, в которых ходы делаются одновременно, или хотя бы полагается, что все игроки не знают о том, что делают другие участники. Такие игры с неполной информацией будут рассмотрены ниже.

Характеристическая функция

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

Основания такого подхода можно найти ещё в книге фон Неймана и Моргенштерна. Изучая нормальную форму для коалиционных игр, они рассудили, что если в игре с двумя сторонами образуется коалиция C, то против неё выступает коалиция N \ C. Образуется как бы игра для двух игроков. Но так как вариантов возможных коалиций много (а именно 2N, где N -- количество игроков), то выигрыш для C будет некоторой характеристической величиной, зависящей от состава коалиции. Формально игра в такой форме (также называемая TU-игрой) представляется парой (N, v), где N -- множество всех игроков, а v : 2N > R -- это характеристическая функция.

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

Применение теории игр

Теория игр, как один из подходов в прикладной математике, применяется для изучения поведения человека и животных в различных ситуациях. Первоначально теория игр начала развиваться в рамках экономической науки, позволив понять и объяснить поведение экономических агентов в различных ситуациях. Позднее область применения теории игр была расширена на другие социальные науки; в настоящее время теория игр используется для объяснения поведения людей в политологии, социологии и психологии. Теоретико-игровой анализ был впервые использован для описания поведения животных Рональдом Фишером в 30-х годах XX века (хотя даже Чарльз Дарвин использовал идеи теории игр без формального обоснования). В работе Рональда Фишера не появляется термин «теория игр». Тем не менее, работа по существу выполнена в русле теоретико-игрового анализа. Разработки, сделанные в экономике, были применены Джоном Майнардом Смитом в книге «Эволюция и теория игр». Теория игр используется не только для предсказания и объяснения поведения; были предприняты попытки использовать теорию игр для разработки теорий этичного или эталонного поведения. Экономисты и философы применяли теорию игр для лучшего понимания хорошего (достойного) поведения. Вообще говоря, первые теоретико-игровые аргументы, объясняющие правильное поведения, высказывались ещё Платоном.

Описание и моделирование

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

Нормативный анализ (выявление наилучшего поведения)

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

Типы игр

Кооперативные и некооперативные

Игра называется кооперативной, или коалиционной, если игроки могут объединяться в группы, взяв на себя некоторые обязательства перед другими игроками и координируя свои действия. Этим она отличается от некооперативных игр, в которых каждый обязан играть за себя. Развлекательные игры редко являются кооперативными, однако такие механизмы нередки в повседневной жизни.

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

Из двух типов игр, некооперативные описывают ситуации в мельчайших деталях и выдают более точные результаты. Кооперативные рассматривают процесс игры в целом. Попытки объединить два подхода дали немалые результаты. Так называемая программа Нэша уже нашла решения некоторых кооперативных игр как ситуации равновесия некооперативных игр.

Гибридные игры включают в себя элементы кооперативных и некооперативных игр. Например, игроки могут образовывать группы, но игра будет вестись в некооперативном стиле. Это значит, что каждый игрок будет преследовать интересы своей группы, вместе с тем стараясь достичь личной выгоды.

Симметричные и несимметричные

	А	Б
А	1, 2	0, 0
Б	0, 0	1, 2
Несимметричная игра

Игра будет симметричной тогда, когда соответствующие стратегии у игроков будут равны, то есть иметь одинаковые платежи. Иначе говоря, если игроки могут поменяться местами и при этом их выигрыши за одни и те же ходы не изменятся. Многие изучаемые игры для двух игроков -- симметричные. В частности, таковыми являются: «Дилемма заключённого», «Охота на оленя», «Ястребы и голуби». В качестве несимметричных игр можно привести «Ультиматум» или «Диктатор».

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

С нулевой суммой и с ненулевой суммой

	А	Б
А	?1, 1	3, ?3
Б	0, 0	?2, 2
Игра с нулевой суммой

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

Многие изучаемые математиками игры, в том числе уже упоминавшаяся «Дилемма заключённого», иного рода: в играх с ненулевой суммой выигрыш какого-то игрока не обязательно означает проигрыш другого, и наоборот. Исход такой игры может быть меньше или больше нуля. Такие игры могут быть преобразованы к нулевой сумме -- это делается введением фиктивного игрока, который «присваивает себе» излишек или восполняет недостаток средств.

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

Параллельные и последовательные

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

Различия в представлении параллельных и последовательных игр рассматривались выше. Первые обычно представляют в нормальной форме, а вторые -- в экстенсивной.

С полной или неполной информацией

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

В то же время есть интересные примеры игр с полной информацией: «Ультиматум», «Многоножка». Сюда же относятся шахматы, шашки, го, манкала и другие.

Часто понятие полной информации путают с похожим -- совершенной информации. Для последнего достаточно лишь знание всех доступных противникам стратегий, знание всех их ходов необязательно.

Игры с бесконечным числом шагов

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

Задача, которая обычно ставится в этом случае, состоит не в поиске оптимального решения, а в поиске хотя бы выигрышной стратегии. Используя аксиому выбора, можно доказать, что иногда даже для игр с полной информацией и двумя исходами -- «выиграл» или «проиграл» -- ни один из игроков не имеет такой стратегии. Существование выигрышных стратегий для некоторых особенным образом сконструированных игр имеет важную роль в дескриптивной теории множеств.

Письмо Джона Нэша в АНБ Агентство национальной безопасности от 1955 года

Большинство изучаемых игр дискретны: в них конечное число игроков, ходов, событий, исходов и т. п. Однако эти составляющие могут быть расширены на множество вещественных чисел. Игры, включающие такие элементы, часто называются дифференциальными. Они связаны с какой-то вещественной шкалой (обычно -- шкалой времени), хотя происходящие в них события могут быть дискретными по природе. Дифференциальные игры также рассматриваются в теории оптимизации, находят своё применение в технике и технологиях, физике.

Метаигры

Это такие игры, результатом которых является набор правил для другой игры (называемой целевой или игрой-объектом). Цель метаигр -- увеличить полезность выдаваемого набора правил. Теория метаигр связана с теорией оптимальных механизмов.



4. Равновесие Нэша

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

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

Формальное определение

Допустим, -- игра n лиц в нормальной форме, где -- набор чистых стратегий, а -- набор выигрышей. Когда каждый игрок выбирает стратегию в профиле стратегий , игрок получает выигрыш . Заметьте, что выигрыш зависит от всего профиля стратегий: не только от стратегии, выбранной самим игроком , но и от чужих стратегий. Профиль стратегий является равновесием по Нэшу, если изменение своей стратегии с на не выгодно ни одному игроку , то есть для любого

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

5. Теорема Нэша--Кейпера

Теорема Нэша--Кейпера утверждает, что любое гладкое короткое вложение (или погружение) -мерного Риманова многообразия в Евклидово пространство при , можно аппроксимировать -гладким изометрическим вложением (или соответственно погружением).

Термин «изометрическое вложение/погружение» здесь означает соответственно вложение/погружение, которое сохраняет длины кривых.

Более точно:

Пусть есть Риманово многообразие и есть короткое -гладкое вложение (или погружение) в Евклидово пространство и . Тогда для любого существует вложение (или соответственно погружение) такое, что

является -гладким, (изометричность) для любых двух касательных векторов в касательном пространстве точки мы имеем:

(-близость) для всех .

Этот результат является весьма контринтуитивным. В частности из него следует что любая замкнутая ориентированная поверхность может быть изометрично -вложена в произвольно малый трёхмерный шар. Из формулы Гаусса следует, что такое вложение невозможно в классе -вложений.

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

6. Теорема Нэша о регулярных вложениях

Теорема Нэша о регулярных вложениях:

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

Нэш также доказал аналогичный результат для аналитических вложений.

О доказательстве

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

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

,

7. Задача о сделках

Задача о сделках (или задача о переговорах) -- игра двух лиц, в которой моделируется ситуация двусторонних переговоров. В ней участвуют два игрока, принимающие решение о распределении некоторого блага (часто в денежной форме). Если игроки договариваются о распределении, они получают требуемую часть. В противном случае никто ничего не получает.

Игра была впервые предложена в 1950 г. Дж. Ф. Нэшем в работе «The Bargaining Problem». Там же был сформулирован один из подходов к решению этой задачи, получивший впоследствии название «решения Нэша».

Формально задача о сделках может быть записана в виде четверки , где X -- множество альтернатив, из которых выбирают участники; -- функция полезности i-го участника, определенная на множестве X; -- точка разногласия (исход, который получат участники, если переговоры не дадут результата).

Решение Нэша

Решение Нэша (в литературе часто используется аббревиатура NBS, от англ. Nash bargaining solution) задачи о сделках представляет собой аксиоматический принцип оптимальности, удовлетворяющий следующим аксиомам:

1) Инвариантность к аффинным преобразованиям функций полезности участников;

2) Эффективность по Парето;

3) Независимость от посторонних альтернатив: если из множества X убрать заведомо неоптимальные альтернативы, то решение задачи не изменится;

4) Симметричность: если игроки одинаковы, то есть , при разногласии получают одинаковую полезность и множество Х -- симметрично, то есть для любой альтернативы найдется альтернатива , такая, что , то .

Теорема. Решением задачи о переговорах , удовлетворяющим аксиомам (1) -- (4) является точка максимума на множестве X функции

.

8. Письмо Джона Нэша в АНБ Агентство национальной безопасности от 1955 года

Джон Нэш предложил для тех времён совершенно революционную идею: использовать в криптографии теорию сложности вычислений. Если прочитать письмо от 18 января 1955 года, то вызывает восхищение, насколько пророческим оказался анализ Нэша о вычислительной сложности и криптостойкости. Именно на этих принципах основана современная криптография. Первая работа в этой области была опубликована только в 1975 году. В своё время власти так и не проявили интереса к работе чудаковатого профессора математики. Или, что тоже возможно, использовали идеи Нэша втайне от него.

В своём письме Джон Нэш развивает идеи теории связи в секретных системах Клода Шэннона (1949), не упоминая её, но идёт значительно дальше. Он предлагает основать безопасность криптосистем на вычислительной сложности -- в точности на том принципе, который в 1975 году спустя два десятилетия лёг в основы современной криптографии. Далее Нэш чётко описывает различие между полиномиальным временем и экспоненциальным временем, что является базисом теории вычислительной сложности. Этот принцип первые описан в 1965 году, хотя о нем речь идёт в знаменитом письме Гёделя к фон Нейману от 1956 года, но не применительно к криптографии.

Джон Нэш:

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

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

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

Собственно, так оно и произошло. Интересно также, что Джон Нэш открыто говорит об использовании методов, теоретический базис которых он не может доказать (P = NP). Более того, он прямо говорит в письме, что «не ожидает его доказательства», что необычно для математика.



Заключение

Как мы уже заметили - сама история Джона Нэша завораживает. Его труды очень важны, они сильно повлияли на развитие экономики и менеджмента, а так же ряд других социальных наук. В том числе на социологию и психологию.

Труды Джона Нэша стали основой в конфликтологии и конкуренции в менеджменте. Так же его труды стали использовать военные для составления тактик во время холодной войны.

И не стоит оставлять без внимания и болезнь Нэша, и способы борьбы с ней. Со временем он перестал принимать лекарства, и симптомы вновь проявились. Со временем болезнь стала отступать, но на самом деле это не так. Он научился жить с ней, и не обращать на нее внимание, «Сейчас я мыслю вполне здраво, как всякий учёный, -- пишет Нэш в автобиографии. -- Не скажу, что это вызывает у меня радость, какую испытывает всякий выздоравливающий от физического недуга».

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

«Кошмар шизофрении заключается в том, что человек не понимает, что именно реально. Представляете, что вдруг узнаете, что люди и места, и самые важные моменты в вашей жизни не ушли в прошлое, не умерли. А хуже того, их просто никогда не было. Представьте себе этот кошмар».

Размещено на Allbest.ru