В течение жизни мы постоянно взаимодействуем с другими людьми. Маленькие дети, пытаясь добиться того, чтобы родители купили понравившуюся конфетку, часто шантажируют родителей своими слезами. Принимая решение заплакать, ребенок рискует — он не знает, как поведут себя папа с мамой. В чуть более взрослом возрасте абитуриенты, выбирающие вуз, принимают сложное решение о том, в какие университеты подать документы. Ошибка может стоить дорого: при неправильной стратегии можно оказаться в слабом университете или вообще остаться без заветного студенческого билета. Окончив вуз, юноши и девушки начинают искать работу. Перед интервью с работодателем они штудируют статьи в интернете о том, что можно и чего нельзя говорить на интервью, — они пытаются найти наилучшую стратегию своего поведения, исходя из ожиданий компании, в которую они устраиваются. Все эти ситуации объединяет то, что решения, которые принимают одни люди, оказывают влияние на других людей. Такие взаимодействия называются стратегическими. Именно их изучает теория игр. Чтобы проанализировать ту или иную реальную жизненную ситуацию стратегического взаимодействия и найти оптимальный вариант поведения в ней, необходимо сделать две вещи. Во-первых, необходимо формально записать ситуацию на языке теории игр, то есть создать модель (игру). Во-вторых, после того как модель (игра) составлена, ее необходимо решить. Этому мы будем учиться в течение курса. Мы разберем основные виды игр (одновременные и последовательные, с совершенной и несовершенной информацией, коалиционные и некоалиционные), приведем способы их решения и обсудим их на многочисленных примерах. Курс будет интересен желающим разобраться в том, как конкурируют друг с другом несколько компаний и можно ли гарантированно выиграть в шашки, есть ли смысл угрожать на переговорах и с кем стоит объединяться в коалиции в парламенте. FAQ В: Требуется ли предварительная подготовка для прохождения курса? О: Курс является базовым, поэтому он не требует специальной подготовки. Для его успешного освоения достаточно уверенных знаний курса математики в объеме школьной программы. В одном-двух примерах могут пригодиться знания начал математического анализа (дифференцирование функций одной переменной, необходимое условие экстремума) и знания начал теории вероятностей (понятие математического ожидания случайной величины). В: Что требуется для успешного окончания курса? О: Итоговая оценка за курс складывается из результатов 10 оцениваемых тестов. Для успешного окончания курса необходимо дать не менее 80 % правильных ответов на каждый из этих тестов.
Развитие теории игр в XX веке
Loading...
From the course by National Research University Higher School of Economics
Теория игр (Game Theory)
611 ratings
From the lesson
Краткая история теории игр
Дорогие слушатели! В видеолекциях одиннадцатой недели курса мы решили поговорить об истории теории игр. Помимо получения предметных знаний, важно видеть логику развития дисциплины. Надеюсь, что материалы одиннадцатой недели нам в этом помогут. Удачи и дальнейших успехов в постоянном и непрерывном обучении!
Meet the Instructors
Dmitry DagaevAssociate Professor, Deputy Vice Rector
Department of Higher Mathematics
Ответ на этот вопрос получил французский математик Эмиль Борель.
С 1921 по 1927 годы
он публикует несколько работ о стратегических играх.
В этих работах он предпринимает попытку описать
стратегическое взаимодействие и вводит понятие стратегии,
причем рассматривает не только чистые стратегии, но и смешанные.
Сначала Борель рассматривает игры двух лиц с нулевой суммой.
Он пытается найти оптимальные стратегии игроков в этих играх.
Ему удается доказать, что в любой конечной игре двух лиц
с нулевой суммой в случае, если у каждого из игроков есть три
или пять чистых стратегий, то тогда в этой игре обязательно
существует минимаксное решение в смешанных стратегиях.
Впрочем, дальше Борель высказывает предположение о том,
что для случая более пяти чистых стратегий
можно попытаться предъявить контрпример, то есть такую игру,
в которой минимаксного решения не существует.
В 1928 году Джон фон Нейман доказывает
теорему о минимаксе — он показывает, что Борель был неправ.
Фон Нейману удалось доказать, что в любой конечной игре двух лиц
с нулевой суммой существует равновесие в минимаксных смешанных стратегиях.
Эта теорема стала настолько важной для теории игр, что ее
многие рассматривают как точку отсчета в становлении этой научной дисциплины.
Результаты фон Неймана стали общепризнанными,
а про результаты Бореля знают не так хорошо.
В 1950-х годах французский математик
Морис Фреше прочитал малоизвестные на тот момент (написанные
на французском) заметки Бореля и посчитал своей обязанностью
донести до всего научного сообщества результаты Бореля.
Фреше высказал мнение о том, что именно Бореля
справедливо признать основоположником теории игр.
Цитата из Фреше звучит так: «...читая заметки Бореля, я понял,
что в этой области, как и во многих других, Борель был основоположником».
Однако фон Нейман отвечает Фреше, что на самом деле никакой
теории игр не могло бы существовать, пока не была доказана теорема о минимаксе.
Борель, доказав ее только для случая трех или пяти стратегий,
ставил под сомнение верность этой теоремы в общей формулировке, но тем самым,
с точки зрения фон Неймана, он ставил под сомнение само существование теории игр.
«...мне казалось, — говорит фон Нейман, что не было бы ничего,
что стоило бы публиковать, пока не была доказана теорема о минимаксе».
В 1944 году фон Нейман и Оскар Моргенштерн
публикуют работу «Теория игр и экономическое поведение».
В ней предпринята попытка построения системы аксиом теории игр.
В этой работе фон Нейман и Моргенштерн рассматривают игры
двух лиц с нулевой суммой, игры n лиц с нулевой суммой.
Они рассматривают в том числе и игры с ненулевой суммой,
однако на тот момент никаких систематических результатов
для игр в общем случае получено не было.
Это изменилось в 1950 году.
Именно тогда, в 50-м и 51-м годах, Джон Нэш
в своих статьях «Точки равновесия в играх n лиц» и «Некооперативные игры» вводит
понятие равновесия в смешанных стратегиях для игр n лиц, обратите внимание,
уже для игр в общем случае, не только для игр с нулевой суммой.
И вот Джон Нэш доказывает, что любая конечная игра
имеет хотя бы одно равновесие в смешанных стратегиях.
Этот результат обобщает результат фон Неймана,
который тот доказал для конечных игр двух лиц с нулевой суммой.
Далее теория игр начинает развиваться со стремительной быстротой.
В том же 1950 году американские математики Мелвин Дрешер и Мерил Флад,
которые работали в корпорации RAND, проводят эксперимент.
Они хотят посмотреть, будет ли играться равновесие Нэша в игре,
в которой это равновесие не является Парето-оптимальным.
Они приводят формальное описание этой игры и просят в нее сыграть различных игроков.
Эта модель фактически позволяет ответить, насколько склонен человек
к сотрудничеству в ситуации, когда у него есть стимулы к эгоистическому поведению.
Альберт Такер дает этой модели красивую интерпретацию.
Формулировка Такера получает название «Дилемма заключенного».
Именно в этой формулировке эта игра рассказывается всем в настоящее время.
1960 год.
Выходит книга Томаса Шеллинга «Стратегия конфликта».
В этой книге Шеллинг подробно обсуждает принципы угроз, контругроз,
сдерживания, конфликта интересов, координации и других принципов,
которые используются во время дипломатических переговоров.
Книга Шеллинга во многом становится настольной книгой для всех
дипломатов того времени.
Читая эту книгу, можно понять,
на каких основаниях базируются принципы ведения дипломатических переговоров,
и эта книга настоятельно рекомендуется к прочтению скорее как художественная
литература, потому что с содержательной точки зрения
теория игр существенно изменилась с 1960 года.
Вот один пример из этой книги:
после того как была взорвана первая атомная бомба, широко обсуждался вопрос о том,
а существует ли предел устойчивости земной атмосферы к ядерному расщеплению.
Распространялись слухи о том,
что если взорвать некоторое критическое количество атомных бомб,
то можно уничтожить атмосферу Земли, и тогда жизнь завершится.
Но тогда, если бы это утверждение действительно было бы правдой,
угрозу использования ядерного оружия можно было бы вовсе исключить.
Можно было бы открыто взорвать (n - 1) ядерную бомбу,
где n — это тот самый критический уровень, и после этого любой,
кто бы взорвал атомную бомбу, фактически полностью разрушал атмосферу,
и это бы означало запрет на использование ядерного оружия.
В книге Шеллинга
рассматриваются и другие похожие примеры, которые показывают,
как можно пытаться сдерживать те или иные угрозы.
В 1965 году Райнхард Зельтен предлагает идею
рафинирования равновесий Нэша в играх в развернутой форме.
Он вводит концепцию равновесия Нэша, совершенного на подыграх.
Зельтен замечает, что из всех равновесий Нэша
некоторые являются более хорошими,
в том смысле, что они обладают некоторыми дополнительными хорошими свойствами,
а именно на каждой подыгре каждый игрок
играет оптимально при фиксированных стратегиях всех остальных.
Если в определении равновесия Нэша требуется оптимальность
действий каждого игрока при фиксированных стратегиях остальных только во всей игре,
то почему бы не выделить подкласс всех равновесий,
в которых выполняются дополнительные свойства,
а именно игроки всегда играют оптимально, на любой подыгре, куда бы игра ни пришла.
Эта идея, идея выделения из всего множества равновесий
тех равновесий, которые обладают дополнительными хорошими свойствами,
получила название «рафинирование равновесий».
А Зельтен фактически предложил первую концепцию рафинирования равновесий Нэша.
В 1966 году Джон Харсаньи в своей работе определяет,
чем кооперативные игры отличаются от некооперативных.
Кооперативными называются игры, в которых различные
договоренности, обещания и угрозы являются связывающими,
то есть, однажды пообещав осуществить угрозу в том или ином случае,
мы гарантируем, что она будет осуществлена.
Если же эти обещания можно нарушать,
и каждый игрок сможет отклоняться от этих обещаний,
то тогда такие игры — некооперативные.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
