Разработанный МФТИ курс отличается тем, что все основные конструкции и принципы теории вводятся непосредственно на основе разбираемых "с нуля" конкретных этюдов. Каждый этюд начинается с понятной непрофессионалу проблемы. В одних случаях это просто "детская игра", в других - формализованное жизненное наблюдение, в третьих - обобщённая социальная закономерность. Сюжет затем разворачивается, исходя из логики содержащегося в нём конфликта, и сам порождает тот или иной принцип разрешения конфликта, который окончательно строго формализуется в виде решения игры. Этюдов всего рассмотрено чуть более десяти, и они в совокупности покрывают основные формальные конструкции базовой теории игр. В нескольких отступлениях приведены формулировки теорем существования игровых решений с набросками доказательств.
Игра "Русская рулетка" - решение
Loading...
Del curso dictado por Moscow Institute of Physics and Technology
Теория игр
33 calificaciones
De la lección
Случайность и неполная информация
На этой неделе мы узнаем, как моделировать и искать равновесия в играх с неполной информацией.
Conoce a los instructores
Дмитрий Ильинскийпреподаватель
кафедра дискретной математики МФТИ
Так, ну что, будем сейчас анализировать русскую рулетку.
Есть, кстати, русская рулетка и еще есть петербургский парадокс — две вещи,
которые сразу припоминаются из теории игр,
но про петербургский парадокс может быть в самом конце мы,
в самом конце, наших лекций-сюжетов, мы на нем остановимся.
Так, ну вот… Он, кстати, связан с оценкой лотерей.
Он связан с оценкой лотерей,
мы здесь сейчас будем оценивать лотереи из двух исходов — вот такого и такого.
Но в данном случае мы просто будем брать матожидание,
а вот проблемы с этим матожиданием, как раз вскрываются тем самым
петербургским парадоксом, о котором когда-нибудь пойдет речь.
Пока не буду ваше внимание к нему привлекать,
поэтому лотерею вот такую, которая на 1/2
дает исходы α и 0, а еще на 1/2 дает исходы −1 и β,
я просто заменяю с помощью тряпочки на то, что в этом случае,
если он вистанет, будет исход (α − 1) / 2, β / 2.
То есть я начинаю работать с конца,
а пока просто приводил лотерею к числам, (α − 1) / 2, β / 2.
А вот теперь уже можно поговорить, с точки зрения принципа Цермело.
Давайте будем рисовать сейчас на одной из этих досок.
Ну, например, на вот этой доске будем рисовать соотношение
параметров α и β, [БЕЗ
СЛОВ] при котором будут приняты те или иные решения.
Ну вот здесь у нас решения В и решения П отличаются тем,
что здесь человек получает 0, а здесь (α − 1) / 2.
Ну понятно, что переломный момент наступает вот на этой прямой.
Саму эту прямую мы не рассматриваем, мы ее выбрасываем из рассмотрения.
Значит.
Здесь будет ход вист на последнем шаге,
то есть эти два шага мы пока не знаем, а на последнем шаге будет ход вист.
И, соответственно, здесь будет
вот это дерево редуцированно к дереву вот такому.
Я сотру вот это и оставлю вот это.
А, соответственно, если α < 1, то здесь будет ход пас на последнем шаге.
Вот. Здесь соответственно будет промежуточный
выигрыш в последний момент (α − 1) / 2, β / 2, а здесь будет выигрыш 0, β.
Эти выигрыши будут учитывать B, второй игрок на предыдущем шаге.
Соответственно, нам придется уже иметь дело с двумя разными деревьями и
исследовать каждое из них по отдельности в зависимости от значения α — α > 1, α < 1.
Значит.
α > 1, сейчас нарисуем дерево, и α < 1, тоже нарисуем дерево.
[БЕЗ СЛОВ] Оба
дерева будут заканчиваться после двух уже сегментов,
то есть они будут уже укорочены, согласно принципу Цермело мы постепенно будем
их редуцировать до конца.
П, В.
(0, β), (−1, β).
И это, соответственно, ход природы.
Тут вероятность 1/4, тут 3/4 и это ход второго игрока,
В, П, в случае паса, (α, 0).
В случае виста с вероятностью 1/3 возникает ход (α,
−1), а с вероятностью 2/3… Внимание,
с вероятностью 2/3 при α > 1 мы выписываем вот те выигрыши — (α
− 1) / 2 и β / 2.
Второе дерево отличается от первого существенным образом выигрышами в конце.
Больше пока никак не отличается, но как мы догадываемся,
это отличие окажется весьма существенным для всего хода игры.
Второй, вист, пас, (α, 0),
(α, −1) и (0, β).
Посмотрите.
В каком случае с большей охотой β будет нажимать, второе будет нажимать, на курок?
Он будет нажимать на курок там,
где ожидает от первого пас при прочих равных на последней ситуации,
то есть если второй знает, что в случае успешного нажатия на курок,
дальше он получить принцессу точно — это одно, одна история.
А если он после курка еще должен, вынужден будет ждать, не застрелится ли первый, а
если он не застрелиться, второму придется пасовать, то это совсем другая история.
Ну сравнение, соответственно, β / 2 и β, вот, оно и дает разницу.
Поэтому и сворачивать эту игру придется по-разному.
А именно, здесь в результате,
вот здесь в этой точке будет стоять выигрыш,
который равен 1/3 (α,
− 1) + 2/3 ((α − 1) / 2, β / 2).
А вот здесь будет стоять выигрыш,
который равен… Я тут немножко не дорисовал, да?
2/3, 1/3… Будет 1/3 тоже от (α,
−1), а вот 2/3 от (0, β).
Вот.
Соответственно, мы редуцируем,
в первом случае это будет (α, −1)… Значит, что это такое?
Это (2α − 1) /
3, запятая,
(β − 1) / 3.
Видно, что в этом случае нажимать или не нажимать курок зависит тоже от того,
β больше или меньше 1, то есть от того же самого порога,
что и у α на последнем шаге.
А вот в этом случае немножко иначе,
а именно здесь будет α / 3,
а здесь будет (2β − 1) / 3.
И, соответственно, нажимать или не нажимать курок, уже зависит от того,
β больше или меньше 1/2, а вовсе не 1.
Поэтому вот в этой зоне [БЕЗ
СЛОВ] разное поведение — нажимать/ не нажимать курок
— происходит по вот этой вот границе, а в той зоне — по вот этой.
И вот получается уже четыре разных зоны с разным поведением.
Вот.
Дальше я не буду полностью это разбирать.
Я просто оставлю на дом в качестве упражнения, но я скажу, что будет,
а именно вот в этой точке возникнет еще… Вот в этой зоне возникнет
еще дополнительная α, равная 1/3,
и кажется в самом конце еще здесь надо будет отметь β = 1/4.
В случае с полноценной русской рулеткой, здесь дойдет до 1/5, 1/6.
Какие вопросы нам интересны?
Ну давайте подумаем, какие вопросы интересны.
Ну прежде всего интересно,как в зависимости от α и β
будут распределены решения стрелять или не стрелять, то есть заканчивать
игру пасуя или отдавать ход второму, на каждом возможном шаге этой игры.
Ну и понятно, в общем-то, понятно более-менее, да, что,
если α и β очень большие, то будет просто… Ну все очень просто будет — они все время
будут говорить «вист»… Они… вист, вист, вист, вист,
вист… В какой-то момент кто-то кого-то… Кто-то себя застрелит,
либо игра дойдет до самого последнего момента и второй спасует.
Но при α и β уже не слишком больших, а где-то там в районе, где-то может,
допустим, от 1/3 до половины, возникает существенная разница в
зависимости от того, какое α в пороге на β начинает меняться.
И все это очень красиво на этой картинке видно становится, после анализа этой игры.
В частности, можно ставить вопрос и отвечать на такие вопросы,
как: при каких параметрах α и β у них нет конфликта относительно того,
кто должен первый ходить?
Понятно, да?
Что в этой игре, кое что не доопределено.
В русской рулетке не доопределено кто начинает.
Вот что это за первый?
Кто такой первый?
Кто первый с невестой познакомился или кто?
Или может быть первый по старшинству?
Скажем это… Лейтенант и капитан.
Кто это первый?
Если это два совершенно одинаковых офицера, кому нужно первому давать ружье?
Так вот, при некоторых α и β возникает парадоксальная ситуация,
что конфликта нет.
То есть первый говорит: «Я хочу стрелять первым», а второй говорит: «Да, да, да,
я тоже хочу, чтобы ты стрелял первым».
А в других ситуациях, конфликт возникает.
Ну вот эти вопросы я предлагаю в качестве упражнения на дом, полностью разобрать.
Причем не эту вот игрушечную, а настоящую русскую рулетку.
Упражнение: разобрать русскую рулетку… По косточкам.
Но, пожалуйста,
учтите, если вы не хотите ошибаться,
то вам потребуется 2—3 часа времени минимум на это.
И очень, очень, очень скрупулезное вот это вот вычисление всех этих операций,
вычисление усредненных исходов лотерей.
Вот.
Ну что же, так сказать, в качестве заключения к этому сюжету.
Надо понимать, что конечно верить в то,
что наши прогнозы имеют какое-то отношение к реальной русской рулетке,
было бы абсолютно абсурдным, то есть это чисто учебный пример.
Ну начнем с того что никто не знает своих α и β, даже своих, не говоря уже о чужих.
То есть никто в общем-то на самом деле этого не понимает.
Никто не понимает, как себя будет вести перед лицом непосредственной смерти,
то есть когда берет пистолет и вот он должен решить, там, стрелять, не стрелять?
То есть эти все… Все построения абсолютно сухие,
это чисто для тренировки динамического программирования и принципа Цермело.
Вот это я хочу совершенно четко говорить, если в каких-то книгах написано,
что вот полная формализация старинной русской забавы… Как и все,
вся теория игр требует некоторого дисклеймера,
что все-таки это игрушки, это тренировка только математического ума.
Ну в некоторых случаях мы немного лучше понимаем то,
какие решения… С какими решениями сталкиваются на практике.
Но то, какие решения будут приняты, мы еще об этом поговорим дальше,
когда сопоставим результаты анализа теоретико-игрового с даже самыми
незыблемыми концепциями, сопоставим это,
прогнозы, с тем, что мы видим на экспериментальных данных.
Explora nuestro catálogo
Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.
Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.
© 2018 Coursera Inc. Todos los derechos reservados.
