Разработанный МФТИ курс отличается тем, что все основные конструкции и принципы теории вводятся непосредственно на основе разбираемых "с нуля" конкретных этюдов. Каждый этюд начинается с понятной непрофессионалу проблемы. В одних случаях это просто "детская игра", в других - формализованное жизненное наблюдение, в третьих - обобщённая социальная закономерность. Сюжет затем разворачивается, исходя из логики содержащегося в нём конфликта, и сам порождает тот или иной принцип разрешения конфликта, который окончательно строго формализуется в виде решения игры. Этюдов всего рассмотрено чуть более десяти, и они в совокупности покрывают основные формальные конструкции базовой теории игр. В нескольких отступлениях приведены формулировки теорем существования игровых решений с набросками доказательств.
Игра "Встреча в метро": постановка задачи
Loading...
En provenance du cours de Moscow Institute of Physics and Technology
Теория игр
32 notes
À partir de la leçon
Секвенциальные равновесия и равновесия Байеса-Нэша
Мы изучим концепцию равновесия Байеса-Нэша и секвенциального равновесия.
Rencontrer les enseignants
Дмитрий Ильинскийпреподаватель
кафедра дискретной математики МФТИ
Игры с неполной информацией, продолжение.
Сюжет «Встреча в метро».
[БЕЗ_ЗВУКА]
[БЕЗ_ЗВУКА] Два очень занятых бизнесмена,
давайте назовем их Александр и Виктор,
должны встретиться, чтобы передать друг другу какую-то важную бумагу.
Ситуация такова, что весь город в пробках,
поэтому встречу лучше всего, быстрее всего осуществить в метро.
Известно следующее, что оба бизнесмена проживают на одной и той же линии метро,
ну например, самой длинной линии метро в городе Москва, которая,
если ее немножко продлить, дойдет до Долгопрудного.
Вот станция «Алтуфьево», вот станция «Бульвар Дмитрия Донского».
На этой линии, как известно, очень много станций,
и можно без сильного ограничения
общности считать, что это просто непрерывный спектр станций,
то есть адресов проживания на этой линии столько же, сколько точек этого отрезка.
И можно ввести на ней координаты от −1 до 1, где 0 будет в центре,
на станции «Боровицкая».
Вот.
Известно, что эти два бизнесмена живут на этой линии метро,
и каждый бизнесмен, конечно, знает свой адрес точный проживания,
однако про второго бизнесмена это неизвестно.
То есть бизнесмен Александр знает, что Виктор проживает где-то на этой линии с
совершенно равными шансами, то бишь его адрес проживания выуживается,
так сказать, как на рыбалке рыбу ловят, так же вот выуживается из отрезка [−1,
1] из равномерного распределения с плотностью 1/2.
То же самое про Виктора: он знает свой адрес,
но адрес Александра ему точно не известен,
эта информация для него является полностью размытой, и мы считаем, что то же самое,
что его априорное представление об адресе проживания Александра состоит в том,
что он может проживать в любой точке с равными шансами.
Теперь правила игры.
Игра состоит в том, что каждый из них хочет ехать,
ехать до места встречи как можно меньше станций.
И они договариваются, они условились о следующем: каждый посылает сигнал по SMS,
в один и тот же момент времени они посылают два сигнала.
Значит, давайте за VA и VB обозначим их адреса,
то есть истинные места проживания этих бизнесменов,
а за bA и bB мы обозначим сигналы,
которые тоже могут быть, соответственно, любыми станциями.
Они могут послать: «Мой адрес такой-то», «Мой адрес такой-то», «А, ну хорошо».
В этом случае место встречи произойдет
в середине между теми сигналами, которые посланы.
Ну понятно, значит, люди являются рациональными игроками,
то есть априори они не обязаны говорить честно свой адрес,
поэтому bA может отличаться от VA, и bB тоже может отличаться от VB.
После того как посланы сигналы, они встречаются якобы в середине,
то есть в точке вот с таким адресом.
Вот это вот будет место встречи.
Ну в самом деле, они же не знают настоящих V, и они сами их тщательно скрывают,
поэтому единственная информация, которая может быть использована для того,
чтобы понять, где они встречаются — это посланные сигналы.
Ну вот они посылают друг другу сигналы, сигналы приходят,
это происходит одновременно, и вычисляется таким образом место встречи.
Вопрос: [БЕЗ_ЗВУКА] как
выглядит равновесное поведение?
И что это такое?
Давайте еще раз проговорим, что это такое,
потому что вчера, когда мы обсуждали сюжет,
связанный с реформой, мы только начинали наше погружение в
теорию игр с неполной информацией и даже не сформулировали концепцию решения.
Мы сказали просто, что люди с разными типами, а вчера типы были — это издержки,
с разными издержками получения информации, будут вести себя по-разному,
и предположили какие-то разумные вещи и нашли то,
что вроде бы называется равновесием или должно считаться равновесием,
но никаких формальных определений мы вчера не давали.
Ну хорошо, вот сегодня пришла пора дать формальное определение того,
что такое равновесие в такой игре.
Значит, давайте подумаем, что вообще означает описать это взаимодействие.
Что я должен предсказать?
Я должен предсказать поведение этих двух бизнесменов.
Но дело в том, что поведение этих двух бизнесменов зависит от адреса,
где они на самом деле проживают.
Поэтому, вообще говоря, решить задачу, — я хочу, в общем-то,
всем слушателям навязать вот этот принцип решения задач с неполной информацией,
— решить задачу означает предсказать поведение
любого типа A или любого типа B.
В нашем случае эта ситуация упрощается, потому что игра априори симметрична,
они оба априори могут жить в любой точке отрезка [0, 1], и все функции
выигрыша будут симметричными, не зависят от имени Александр или Виктор.
И поэтому что такое поведение, которое мы предсказываем?
Поведение — это правило, согласно которому он посылает сигнал b в зависимости от
того, где он проживает, то есть это функция.
И вот в этом месте надо остановиться.
То, что мы ищем, то, что мы ищем — это функция.
И так всегда происходит в играх с неполной информацией,
в частности, в аукционах.
То, что является объектом поиска — это некоторая функция,
то есть нужно найти одну функцию среди всех функций, среди пространства функций.
Функция, давайте так напишем, b из отрезка [−1,
1] в отрезок [−1, 1].
Это — сигнал, это — отклик.
Сигнал означает, что бизнесмен проживает в конкретной точке, отклик — это значит, что
если он проживает в точке VA, то bA — это то, что он запишет в эсэмэску и пошлет.
То есть мы ищем вот такие вот функции, давайте нарисуем их график.
Вот (−1, 1), вот (−1, 1), вот всевозможные вот такие вот функции,
которые тут вообще могут быть, все пространство функций, в принципе.
И в этом пространстве функций нужно найти поведение, то есть функцию,
которую мы считаем равновесной, то есть мы назовем ее равновесной.
Вот что означает равновесность, этому сейчас будет посвящено некоторое время.
Explorer notre catalogue
Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.
Coursera propose un accès universel à la meilleure formation au monde,
en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.
© 2018 Coursera Inc. Tous droits réservés.
