Разработанный МФТИ курс отличается тем, что все основные конструкции и принципы теории вводятся непосредственно на основе разбираемых "с нуля" конкретных этюдов. Каждый этюд начинается с понятной непрофессионалу проблемы. В одних случаях это просто "детская игра", в других - формализованное жизненное наблюдение, в третьих - обобщённая социальная закономерность. Сюжет затем разворачивается, исходя из логики содержащегося в нём конфликта, и сам порождает тот или иной принцип разрешения конфликта, который окончательно строго формализуется в виде решения игры. Этюдов всего рассмотрено чуть более десяти, и они в совокупности покрывают основные формальные конструкции базовой теории игр. В нескольких отступлениях приведены формулировки теорем существования игровых решений с набросками доказательств.
Симметричные игры и симметричные равновесия: "Белый Аист"
Loading...
Del curso dictado por Moscow Institute of Physics and Technology
Теория игр
31 calificaciones
De la lección
Смешанные равновесия
Conoce a los instructores
Дмитрий Ильинскийпреподаватель
кафедра дискретной математики МФТИ
Симметричные равновесия.
Симметричные игры и
симметричные равновесия.
[БЕЗ СЛОВ] Это
тема этого и следующих нескольких сюжетов.
Пример.
Игра, которая называется «Белый аист»,
тоже по неким каким-то историческим причинам.
Это телеигра.
Слушатели некоторой программы телевизионной,
коих n,
ну для удобства я буду считать, что их (n + 2),
почему это важно, станет ясно из формулы, которую мы потом будем выписывать.
Итак, игроки — это слушатели некоторой телевизионной программы,
вот множество игроков, и телеведущий объявил,
что разыгрывается две бутылки коньяка «Белый аист».
И чтобы стать призером,
нужно отослать СМС на некоторый короткий номер.
Стоимость СМС — 1 условный рубль, ну может быть, тысяча рублей, я не знаю.
В общем, некая единица измерения, вот единица.
Значит, каждый, кто посылает СМС, он тратит эту единицу.
Правила игры таковы,
что если СМС будет послано 1 или 2,
то каждый, приславший СМС, получает бутылку.
Если СМС будет послано 3 или более, бутылку не получит никто,
они останутся в редакции, то есть на телевидении.
Вот.
Нужно найти равновесие в этой игре.
Ну, давайте подумаем.
Итак, вот вы посылаете или не посылаете СМС.
От чего это зависит?
Как ищется равновесие?
В равновесии нужно посмотреть,
какой ваш наилучший ответ на стратегии остальных игроков.
Ну и давайте его выпишем.
Ответ на любую последовательность решений
«посылать»/ «не посылать», в которой
не более чем 1 положительное решение, то есть на...
во-первых, на последовательность, где все нули,
а также на любую последовательность вида [0...
010...
0] вот если вы увидели,
подглядели чужие решения и увидели, что никто не послал или что ровно 1 человек
послал, то ответ на такое — это «послать».
Ответ на все остальное,
то есть когда пославших ≥ 2,
равно «отказаться».
И нужно придумать какую-нибудь общую формулу состояний,
«послать»/ «не послать», да, давайте это формализуем в виде игры,
в которой все множества стратегий просто содержат
2 элемента: «послать» или «не послать».
Бинарная игра.
На самом деле, очень много, в теории игр довольно большой процент
времени посвящается изучению различных бинарных игр, в котором решение — это ±.
И вот типичный пример бинарной игры, к тому же симметричной.
Что значит симметричная игра?
Это значит, прежде всего, что все стратегические множества совершенно
одинаковы, то есть нельзя различить людей по стратегическим множествам.
А кроме того, людей нельзя различить и по функциям выигрыша.
Ну в каком смысле?
В том смысле, что ui (si,
s−i), если мы рассматриваем
вот такой вот выигрыш, и теперь берем и меняем местами i-того и j-того,
но вместе с ними меняем местами i-тую и j-тую стратегию.
Поэтому давайте я напишу более подробно.
Выигрыш i-того игрока от применения им i-той стратегии,
j-тым — j-той, и всеми остальными — какого-то набора,
должен быть такой же, как выигрыш j-того от применения им j-той,
i-тым — i-той и всеми остальными — того же самого набора.
То есть нельзя различить игроков ни по их стратегическим множествам,
ни по тому, как выглядит функция.
Если я поменяю местами имена, назову i-того j-тым, а j-того i-тым,
то у меня ничего не изменится.
Вот. Такие игры называются симметричными, и,
конечно, хотелось бы верить,
что в симметричной игре есть симметричное равновесие.
Но что мы видим здесь?
Здесь мы видим, что ничего подобного.
Я думаю, что любой из слушателей очень быстро поймет,
что все чистые равновесия выглядят следующим образом.
Это последовательности из нулей и единиц,
в которых ровно 2 единицы и все остальные — нули.
Ничего общего с симметрией эта ситуация не имеет.
Действительно, рассмотрим любую такую последовательность.
Ясно, что в ней вот есть 2.
Грубо говоря, что это такое?
Это 2 неких таких, некоторых очень больших «везунчика»,
про которых известно, что они будут посылать СМС.
Если всем известно, что СМС обязательно посылают эти два везунчика,
то тогда никто не будет посылать СМС, потому что в этом случае ни им не
достанется коньяк, ни тому, кто попытался послать третьим.
Ну и ясно, что эти двое тоже не будут отказываться от коньяка, то есть, грубо
говоря, это такая ситуация, в которой есть какая-то внутренняя асимметрия уже в
равновесии, что про каких-то двух людей считают, что именно они — те самые.
Если есть в какой-нибудь компании два человека,
какие-нибудь выделенные каким-то свойствами, может, семейная пара,
у которой всегда все собираются на всех пьянках-гулянках, например.
Ну тогда вполне можно понять,
что если вот вот эти все посетители этих пьянок-гулянок играют в такую игру,
они подумают: «Ну ладно, пусть Ваня с Машей и пошлют эти СМС, а мы не будем».
И Ваня с Машей думают: «Ну кто те двое?
Наверное, мы и есть те двое.
Раз мы всегда у себя собираем всех, наверное, мы и есть те двое,
мы пошлем СМС».
Это равновесие Нэша, но это равновесие Нэша с симметрией не имеет ничего общего.
То есть здесь вот симметричная игра по выигрышам, но она,
как бы, в ней внутренняя вот эта вот проявляется несимметрия,
которая не записана ни в какие условия.
То есть в условиях игры не формализована эта несимметрия,
и больше равновесий никаких нет.
Равновесий, соответственно, C из (n + 2) по 2, в зависимости от того,
кого двух назвать этими везунчиками.
Но ведь так же не бывает,
ведь в симметричной игре должно быть симметричное равновесие, правда?
Должно быть.
Ответ: теорема.
Если игра конечная,
ну то есть списки вот эти вот
игроков и все вот эти множества конечны,
то существует симметричное смешанное равновесие,
симметричное смешанное равновесие,
то есть одна смешанная
стратегия — σ обозначим ее со *,
вот это, кстати, все вот эти вот, если игра конечная и вот эти все Si-тые,
они все совпадают с некоторым стратегическим множеством S,
то существует симметричное смешанное равновесие, и все,
и функции выигрыша тоже все симметричны, тогда существует стратегия,
такая, что вот эта вот ситуация, то есть ситуация,
в которой все игроки применяют одну и ту же вот эту вот стратегию,
является равновесием по Нэшу.
Значит, в конечной симметричной игре обязательно существует симметричное
смешанное равновесие, но в некоторых случаях оно может вырождаться в чистое.
И вот в такой ситуации разумно говорить, что есть,
есть равновесная стратегия именно, потому что
если речь идет о симметричном равновесии, то это именно повторенная стратегия,
которую все одинаково используют, вот эта комбинация составляет равновесие,
поэтому в симметричных играх можно говорить о равновесной стратегии,
это единственный случай, когда это оправданно, если игра симметрична.
Вот. Ну что же, надо попробовать найти здесь
такое равновесие, то есть стратегию поведения,
смешанную, которая, если я верю,
что все остальные ведут себя ровно так, для меня приемлема.
Я могу ее использовать, и она оптимальна среди всех моих стратегий.
Давайте поищем такую стратегию поведения σ*.
σ*, так как у нас чистые стратегии всего 2 — «посылать»/ «не посылать»,
— то σ*, это просто вероятность некоторая, которую мы будем искать, того,
что вы посылаете СМС, и с вероятностью (1 − p) вы его не посылаете.
То есть, что же мы тогда ищем?
Мы ищем такую вероятность послать СМС, что если я верю в то,
что все остальные (n + 1) игроков разыгрывают то же самое
вероятностное распределение, то есть с вероятностью p посылают СМС,
то мне тоже годится вот эта стратегия в качестве моего ответа.
А что это значит?
Это значит, что вот эти две стратегии мне должны давать одинаковый выигрыш.
Как всегда, если смешанная стратегия ищется в качестве равновесия,
то чистые стратегии, входящие в нее, должны давать одинаковый выигрыш.
То есть надо найти такую вероятность p, что при условии,
что все остальные разыгрывают именно ее, мой выигрыш от стратегии «послать
СМС» равен моему выигрышу от стратегии «не послать СМС».
Продолжение в следующем сюжете.
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.
