Разработанный МФТИ курс отличается тем, что все основные конструкции и принципы теории вводятся непосредственно на основе разбираемых "с нуля" конкретных этюдов. Каждый этюд начинается с понятной непрофессионалу проблемы. В одних случаях это просто "детская игра", в других - формализованное жизненное наблюдение, в третьих - обобщённая социальная закономерность. Сюжет затем разворачивается, исходя из логики содержащегося в нём конфликта, и сам порождает тот или иной принцип разрешения конфликта, который окончательно строго формализуется в виде решения игры. Этюдов всего рассмотрено чуть более десяти, и они в совокупности покрывают основные формальные конструкции базовой теории игр. В нескольких отступлениях приведены формулировки теорем существования игровых решений с набросками доказательств.
Игра "Встреча в метро": равновесие Байеса-Нэша
Loading...
From the course by Moscow Institute of Physics and Technology
Теория игр
38 ratings
From the lesson
Секвенциальные равновесия и равновесия Байеса-Нэша
Мы изучим концепцию равновесия Байеса-Нэша и секвенциального равновесия.
Meet the Instructors
Дмитрий Ильинскийпреподаватель
кафедра дискретной математики МФТИ
Ну что же, давайте попробуем эту задачу решить.
Решить ее можно геометрически.
Надо посмотреть, что на самом деле здесь минимизируется.
Интеграл — это площадь, площадь под кривой, которая здесь нарисована.
Давайте посмотрим, что за кривая здесь на самом деле нарисована.
Для этого умножим на два это, как обычно.
На минимизации это никак не скажется.
Значит, мы ищем значение b, при котором
минимизируется вот этот интеграл.
Модуль v, 2v теперь уже.
2v − b − vB по dvB — по,
так сказать, нашему этому самому,
по неизвестному нам адресу проживания второго человека,
который, известно, что ведет себя честно.
Значит, итак.
Мы ищем b, при котором этот интеграл достигает минимума.
Что это за интеграл, как он выглядит вот как функция?
Как функция от переменной vB, по которой идет интегрирование.
Вот vB.
Она меняется от −1 к 1,
и в некоторой точке, равной 2v − b,
в точке 2v − b
значение vB зануляет вот этот модуль.
А справа и слева растет, естественно, так сказать,
так и положено модулю расти — «птичкой».
Теперь что такое интеграл?
Интеграл — это вот эта площадь.
Вот эта плюс вот эта.
Вопрос: что мы минимизируем и по какому параметру?
Ответ: наш параметр — это вот эта точка, потому что,
меняя b, мы меняем 2v − b, но, правда, в определенных пределах.
Иногда может быть так, что наш адрес проживания таков,
что ни при каком значении b мы не можем эту точку загнать в
какие-то зоны вот этого отрезка, например, вот в эту точку 0 загнать ее не можем.
Но давайте посмотрим в пределах минимизации, что мы хотим сделать.
Вот мы двигаем эту точку.
Двигая b, мы двигаем эту точку внутри каких-то пределов.
Вот если я в эту сторону ее двигаю, то я что делаю с интегралом?
Понятно, я его увеличиваю, правда?
Потому что вот эта площадь сокращается меньше, чем увеличивается вот эта.
Наоборот, приближая вот сюда, я его уменьшаю.
И если бы мне была доступна вот такая опция,
то я бы достиг абсолютного минимума этого интеграла среди всех вообще возможных.
То есть если можно положить 2v − b = 0, то надо это сделать.
То есть ответ такой: если можно, надо это сделать.
Если нет, надо приблизиться к этой точке максимальным образом.
Поэтому ответ на честное поведение выглядит так:
[БЕЗ СЛОВ]
b = 2v, покуда это возможно.
b = 2v, если 2v принадлежит отрезку [−1,
1], то есть если ваш адрес проживания находится,
грубо говоря, между Тимирязевской и Нагатинской,
в отрезке от −1 / 2 до 1 / 2.
Если же ваш настоящий адрес выпадает из этого отрезка,
то надо постараться это выражение сделать как можно ближе к 0,
то есть выбрать край отрезка, нужно b назначить краем отрезка,
поэтому в противном
случае надо положить b = ±1, соответственно,
так сказать, соответственно тому, к какому краю это ближе.
Давайте я нарисую просто график, график функции такой.
Вот он.
То есть график оптимального ответа выглядит так.
Это 2v,
b = 2v в пределах от −1 / 2 до 1 / 2.
И константно равен 1 вот на этом отрезочке, константно равен −1 — на этом.
Вот вам ответ, как надо врать, грубо говоря, оптимально.
Если против вас играет честный человек, то вам нужно в СМС-е записать
двойной свой адрес, то есть удвоенный адрес,
удвоенное расстояние от Боровицкой в ту же сторону по ветке,
если этот двойной адрес не выходит за пределы линии метро,
и конечную станцию линии метро — если выходит.
То есть вот в этих пределах получится написать двойной адрес, в этой надо,
вот здесь и здесь надо все время писать конечные, то есть в половине случаев ответ
оптимальный будет указывать конечную станцию, одну из двух.
Вот.
Ну, понятно следующее:
что еще нет уверенности в том, что это, собственно говоря,
и есть равновесное поведение, потому что смотрите, что мы нашли.
Мы нашли функцию,
которая является оптимальным ответом на честное поведение,
то есть на функцию b тождественное = v, на вот эту функцию.
Что такое равновесие?
Ну наверное, после всего, что я сказал, понятно, что такое равновесие.
Равновесие — это такая функция, которая является оптимальным ответом на себя саму.
То есть если есть некоторая функция,
мы говорим, что она равновесная в том случае, если вот я подставил
эту функцию в соответствующий интеграл, вон туда подставил ее,
вот туда вместо v написал вот эту вот функцию s(v).
Взял, проминимизировал это выражение по b в любой точке v и обнаружил,
что для любого адреса v вот этот вот минимум
тождественно равен той самой s(v), которую здесь использовали в интеграле.
Еще раз: это настолько важно, что я это повторю.
Это самое основное утверждение теории игр с неполной информацией.
Значит, как искать симметричное равновесие в такой игре и, вообще, что это такое?
Что такое симметричное равновесие?
Это функция отклика.
Подставляется ваш истинный тип, в данном случае адрес, а вы реагируете,
посылая в СМС-е какой-то, значит, измененный, искаженный адрес.
Функция искажения проверяется на то, является ли она равновесной или нет.
Функция, не одно какое-то конкретное значение — вот это никогда, это очень
сложно обычно бывает понять, особенно людям с экономическим образованием,
потому что здесь речь идет о функциональном анализе,
который в подавляющем большинстве случаев им просто абсолютно неизвестен.
Итак, функция.
Поведение — это функция.
Ну понятно: вот сколько типов, столько и ответов, поэтому это функция.
Равновесное поведение означает следующее: пусть я верю,
что партнер ведет себя в соответствии с вот этой функцией.
Это означает, что при вычислении своего оптимального ответа,
если мой адрес равен v, я должен минимизировать вот этот интеграл,
куда вместо честной реакции подставлена именно вот эта функция s.
И эта функция s является равновесием в том случае,
если при любом моем истинном адресе v моя оптимальная реакция,
записанная в СМС-е, в точности совпадает с s(v).
Такое равновесие носит название специальное —
равновесие Байеса-Нэша.
На самом деле можно формализовать игру так,
чтобы она оказалась равновесием Нэша в некоторой новой игре,
но это уже формалистика, которой мы заниматься не будем.
Итак, равновесие Байеса-Нэша — это функция такая,
что в любой точке ее значение является оптимальным откликом на поведение
оппонента в точности в соответствии с этой функцией на всем интервале,
усредненная по его неизвестному мне параметру.
Вот.
Осталось дорешать эту задачу.
Но я не буду дорешивать, я просто объявлю ответ.
Оказывается, что если мы подставим вот такое поведение
вот в этот интеграл, то ответом будет в точности такое же поведение.
То есть чудесным образом ответная оптимальная
реакция на оптимальную реакцию на честное поведение совпадает с вот этой функцией.
То есть здесь как бы итеративно в два приема мы приходим к равновесию.
Берется честное поведение, ответом на честное поведение
будет вот такая функция, а вот ответом на такую функцию будет она же сама.
Поэтому мы уже нашли равновесие, но это чудесным образом так получилось здесь.
Здесь на самом деле на любую нечетную функцию будет один и тот же ответ,
вот такой — вы можете это проверить в качестве упражнения.
И конечно, в других играх это не так.
И вообще, вопросы сходимости вот таких вот оптимальных реакций в играх с неполной
информацией пока находятся в книге за семью печатями,
это просто неизвестные вопросы.
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.
