Разработанный МФТИ курс отличается тем, что все основные конструкции и принципы теории вводятся непосредственно на основе разбираемых "с нуля" конкретных этюдов. Каждый этюд начинается с понятной непрофессионалу проблемы. В одних случаях это просто "детская игра", в других - формализованное жизненное наблюдение, в третьих - обобщённая социальная закономерность. Сюжет затем разворачивается, исходя из логики содержащегося в нём конфликта, и сам порождает тот или иной принцип разрешения конфликта, который окончательно строго формализуется в виде решения игры. Этюдов всего рассмотрено чуть более десяти, и они в совокупности покрывают основные формальные конструкции базовой теории игр. В нескольких отступлениях приведены формулировки теорем существования игровых решений с набросками доказательств.
Субъективные веры в информационных множествах
Loading...
來自 Moscow Institute of Physics and Technology 的課程
Теория игр
33 個評分
從本節課中
Секвенциальные равновесия и равновесия Байеса-Нэша
Мы изучим концепцию равновесия Байеса-Нэша и секвенциального равновесия.
與講師見面
Дмитрий Ильинскийпреподаватель
кафедра дискретной математики МФТИ
Ну вот. Значит, я расскажу о том методе,
который сейчас общепризнан, общепринятый для разрешения таких вот ситуаций.
А именно введём понятие «веры».
Веры.
Вера, или вероятностное, так сказать, распределение
своих собственных априорных суждений о том, в какой точке ты находишься.
То есть первый игрок вот в этом и вот в этом информационном множестве
должен для себя сформулировать, какие шансы нахождения здесь и здесь.
То есть чему равна вероятность μ,
давайте обозначим вот эту, как бы эту вероятность...
Вера, или вероятность с его как бы априорной такой вот субъективной позиции,
называется словом «вера».
Назовём, значит, это числом μ, а здесь будет (1 − μ).
То есть это его собственная уверенность в том, что вот с такой вероятностью он
имеет дело с честным, а с такой вероятностью — с шулером.
Тонкость в том, что μ ≠ β.
Необязательно равно β.
И вообще, тонкость понятия веры в том, что это не просто так взятое с неба число,
оно должно определяться действиями игроков на предыдущих шагах,
то есть историей взаимодействия, историей конфликта.
Ну давайте посмотрим.
Я уже, вводя вот это вот число μ, я намекаю на то,
что здесь не получится найти чистого равновесия, чистого, то есть с ходами...
Ну например, вот в этой позиции шулер иногда будет брать деньги себе,
а иногда отправлять ход направо.
И это мы строго докажем, чуть позже мы строго докажем, что здесь нет ни
одного равновесия, в котором шулер вот в этой точке действует либо всегда вот так,
либо всегда вот так, таких равновесий не существует, мы это покажем.
Но в этом случае вот это μ будет уже отличаться от β, да?
Ну вот смотрите.
Допустим, шулер всегда ходит сюда, чему тогда равно μ?
Тогда μ, ну понятно, по интуитивным соображениям ясно,
что тогда μ = β просто, потому что, смотрите, какая ситуация.
Если шулер в этой точке всегда ходит направо,
то у первого к этому моменту нету никакого вероятностного, так сказать,
никакого уточнения вероятности по сравнению с тем, что он просто знает,
что в обществе, из которого взят второй игрок, процент β честных.
Но например, если шулер здесь ходил бы сюда, а первый обнаружил
себя действующим вот в этом информационном множестве, то что это означает?
Это означает с вероятностью 1, что он действует здесь.
То есть, если ход шулера здесь всегда забрать,
то то, что до первого игрока второй раз дошёл ход,
должно означать не что иное, как то, что он обязательно имеет дело с честным.
То есть если вот в равновесии, которое мы ищем,
мы ищем равновесный набор стратегии людей.
Что такое стратегия?
Это тоже отдельный вопрос — что такое стратегия.
Ну второго игрока, это понятно, что такое: это ход вот в этой ситуации и всё.
Тот или иной или смешанная стратегия на этих ходах.
А что такое для первого стратегия?
Для первого стратегия — это два вероятностных хода: ход здесь и ход здесь.
То есть это, так сказать, это два плана действий.
Первый план действий состоит в том, брать ли в первый момент сразу же или в первый
момент передать ход, а значит, вторая компонента плана
действий состоит в том, что делать вот в этом информационном множестве,
в этом информационном множестве, то есть когда он второй раз получил ход.
Будет ли он себе хапать, или он будет передавать.
И вот нам интересно исследовать эту ситуацию, но её на самом деле,
исследовать интересно только при β, которое меньше 1/7.
Ну давайте напишем β = 1/10, например.
Но, на самом деле, интересно, когда β < 1/7.
Если β > 1/7, то оказывается так, что...
Тут оказывается,
что этого хватает, чтобы он всегда передавал ход.
То есть процент честных настолько велик,
что ему просто всегда имеет смысл полагаться, уповать на то,
что вдруг он играет с честным, лучше он будет передавать ход направо.
Вот интересно, что даже в случае очень малого процента честных, меньшего,
чем 1/7 (мы потом увидим, откуда эта 1/7 взялась, когда начнём эту игру решать),
но в данном случае, когда эта β < 1/7, всё ещё в достаточно большом
диапазоне β равновесия, в которых в начале он передаёт ход, существуют.
То есть достаточно чрезвычайно низкого процента альтруистов в обществе, чтобы
в этой игре присутствовали равновесия альтруистичного поведения первого,
квазиальтруистичного поведения первого, то есть передачи хода, на первом шаге.
Ну вот.
А теперь смотрите, давайте я, давайте вместе с вами введём
обозначение для смешанного равновесия и попробуем написать формулу для μ.
Вот что это за вера?
Я уже сказал, что вера, она не должна быть взята с потолка,
она должна быть чем‐то продиктована.
Вот. Продиктована она предыдущими ходами.
В свою очередь, она сама, она определяет, влияет на последующие ходы,
то есть вера — это то самое не хватающее нам звено, чтобы
разрешить все такие игры относительно, ну, так сказать, принципа Цермело.
То есть принцип Цермело, если нам даны веры, мы можем посчитать,
какой из ходов что нам даёт, и выбрать наилучшее.
Но сами веры должны быть определены по принципу, ну, там, пересчёта по Байесу,
грубо говоря, да?
Единственный способ, которым мы умеем вычитывать информацию,
это пересчёт по Байесу.
Из того, что планирует на предыдущем этапе.
Но что планирует на предыдущем этапе,
завязано и на будущие действия тоже через понятие равновесия.
И вот этот весь клубок мы с вами будем раскручивать, его мы будем развязывать.
Значит, начнём с того, что просто введём все обозначения.
Давайте обозначим
за σ вероятность хода сюда и сюда.
Напоминаю, это одна и та же вероятность, он не отличает эти две точки,
он не может здесь выбрать одну, а здесь другую.
И соответственно, (1 − σ) — это то,
что пасует и забирает деньги себе, вот эти вот 16, и оставляет 4.
Дальше, μ у нас уже есть, здесь будет τ.
τ — это вероятность смешанной стратегии
второго игрока, который на самом деле нечестный, но притворяется честным.
Вот вероятность того, что он притворяется честным, равна τ.
И тогда здесь будет 1 − τ.
Ну и обозначим вот эту вот вероятность вот здесь за α, это вероятность того,
что на первом ходу первый игрок передаёт ход.
Мы хотим понять,
в каком диапазоне всё ещё возможно рассчитывать в равновесие на α = 1.
Но это забегая вперёд,
а пока я хочу завершить этот маленький сюжет выписыванием формулы для μ.
Смотрите, с какой вероятностью мы попадаем сюда?
Вероятность эта равна...
Ну, так сказать, для всех игр на графах она абсолютно одинаково высчитывается.
Это вероятность того, что природа пошла сюда, умножить на вероятность того,
что я сам отправил, если я первый игрок, отправил игру дальше,
и на вероятность того, что второй отправил игру дальше.
Это вероятность прихода в эту клетку.
То есть она равна (1 − β) * α * τ.
А чему равна вероятность попадания вот в эту точку?
β * α, правильно?
То есть вероятность, что природа пошла сюда, и вероятность того,
что мы отправили дальше.
Всё, здесь уже нет никакого дополнительного.
Так вот, чтобы узнать μ, нужно написать очевидное соотношение, что...
Пересчёт по Байесу — это что такое?
Это значит, что мы берём отношение этих двух вероятностей и пишем,
что оно же равно (1 − μ) / μ.
[БЕЗ СЛОВ] Ну а то,
к чему это приводит, мы поговорим на следующем сюжете.
