Eriright

Всем привет! Я продолжаю свою серию постов по популяризации науки :) Пока я выкладываю материалы по теории игр.

Прошлые посты тут:

Игра с природой, или что такое математическое ожидание? : Часть 1, Часть 2

Сегодня, мы перейдём непосредственно к играм рациональных игроков.

Дилемма заключенного

Наверное, самая известная из модельных задач − так называемая «Дилемма заключённого». Она была формализована в 1950 году Альбертом Такером в Принстоне, но сформулирована ещё до него Мерриллом Фладом и Мелвином Дрешером.

Одна из её формулировок звучит следующим образом:

Дилемма заключённого. Окружной прокурор в городе Чикаго знает, что Франкенштейн и Дракула − гангстеры, которые являются виновными в совершении тяжкого преступления, но он не может уличить их в этом, если ни один из них не сознается. Он приказывает арестовать их и по отдельности (да они и так не смогли бы договориться) предлагает каждому следующий контракт:

Если Вы признаете вину, а ваш соучастник не захочет признаться, тогда вы идете домой и вообще свободны, ибо мы сможем забыть, что вы соучастник за ваше признание. Если вы не готовы признать вину, но ваш соучастник признает, то вы будете осуждены и приговорены к максимальному сроку в тюрьме. Если вы оба признаетесь, то вы оба будете осуждены, но не на максимальный срок. Если ни один не признается, то я ненадолго посажу обоих, а за что, уж будьте уверены --- найду.

Здесь речь идет о не очень честном прокуроре, который может сфабриковать дело, чтобы посадить этих персонажей в тюрьму.

При данном условии, Дракула и Франкенштейн играют в некую игру. Для каждого из них есть две стратегии: «Признать вину» и «Молчать».

Условимся записывать каждую возможную ситуацию, как пару выбранных стратегий, где на первом месте стоит выбор Франкенштейна, а на втором − Дракулы. Например, пара («Признать вину», «Молчать») означает, что Франкенштейн заложил Дракулу, который решил, что он добренький.

Так как сидеть в тюрьме, а, особенно, сидеть в тюрьме долго, никому не хочется, будем считать, что цель каждого игрока − минимизировать свой срок заключения. Срок будем записывать в виде чисел, обозначающих потерю очков.

Рассмотрим все возможные ситуации для того, чтобы составить так называемую платёжную матрицу данной игры. В каждой ячейке данной матрицы указана пара чисел, показывающая выигрыши игроков при выборе данной пары стратегий.

Допустим, Франкенштейн выбирает молчание, а Дракула признаётся, тогда Франкенштейна выставляют единственным виновным, и он получает максимальный срок в 10 лет. Мы записываем этот исход как −10 очков для Франкенштейна по стратегии («Молчать», «Признать вину»), и 0 очков для Дракулы по данной стратегии.

Если Франкенштейн признаётся, а Дракула молчит, то Франкенштейна отпускают − записываем Франкенштейну 0 очков по стратегии («Признать вину», «Молчать»), а Дракуле --- −10 очков.

Если же оба решат скрыть все свои тайны, получаем стратегию («Молчать», «Молчать»). По правилам, в таком случае окружной прокурор фабрикует какое-нибудь мелкое дело, и оба идут в тюрьму на 1 год. Записываем −1 очко каждому при данной стратегии.

Наконец, если оба признают вину, то и Франкенштейн и Дракула должны были бы сесть на 10 лет, но так как признание есть смягчающее обстоятельство, то оба в итоге получают по 9 лет. Запишем обоим −9 по стратегии («Признать вину», «Признать вину»).

Мы только что составили матрицу платежей. Сразу введём следующее определение.

Нормальная, или стратегическая форма игры − есть спецификация пространства стратегий и функций выигрышей каждого игрока на всех возможных стадиях игры. Таким образом, игра описывается её платёжной матрицей. Обе стороны матрицы − игроки. Стратегии первого игрока определяются строками, стратегии второго − столбцами, пересечение строк --- выигрыши игроков.

Заметим, что у нас есть проблема: ни Дракула не знает, какую стратегию изберёт Франкенштейн, ни Франкенштейн не знает, какую стратегию изберёт Дракула. Иначе они бы только глянули на соответствующую стратегии другого игрока строку или столбец и выбрали бы лучший исход из предлагаемых им.

В данной игре, на самом деле, всё просто − какую бы стратегию не выбрал соперник, признание всегда ведёт к максимизации очков. Но в таком случае, оба игрока признаются и оба попадут на нары на 9 лет, хотя могли бы оба смолчать и получить всего по 1 году заключения.

Как же так? Почему рациональные действия двух человек привели к настолько нерациональному исходу? А вот это и является дилеммой...

На самом деле, критикам теории игр вообще не нравится дилемма заключенного, потому что они видят, что и Дракуле, и Франкенштейну было бы лучше, если бы они оба молчали. Если бы вместо Франкенштейна поймали подругу Дракулу, Мину Харкер, возможно, они бы так и поступили, но, на самом деле, если люди не связаны до игры, поступки большинства из нас будут достаточно эгоистичными. Если вы посидите на ютубе, вы обнаружите, например, примеры телешоу, основанные на дилемме заключенного, например, шоу «Golden Balls ».

Одна из многочисленных попыток решить парадокс рациональности в дилемме заключенных − это использовать симметрию игры, рассматривая Дракулу и Франкенштейна как близнецов.

Это выглядит следующим образом:

Две рациональных человека, перед которыми стоит одна и та же проблема, придут к такому же выводу. Поэтому Дракула должен исходить из того, что Франкенштейн сделает такой же выбор, как и он. Поэтому либо оба идут в тюрьму на девять лет, или они оба идут в тюрьму на один год. Поскольку последний вариант является предпочтительным, Дракула должен молчать. Так как Франкенштейн его близнец, он будет рассуждать таким же образом и тоже будет молчать.

Но есть одна проблема: это, по сути, превращает данную игру в игру с одним игроком, то есть, дилемма перестаёт быть дилеммой как таковой. Дилемма как раз и заключается в независимости принимаемых игроками решений.

Всем привет ! Я решила немного повыкладывать научпоп, надеюсь, кому-нибудь зайдёт. Вначале будет немного математики, это самая скучная часть, но нужна будет, чтобы по-настоящему насладиться тем, что будет дальше. Это курс по теории игр для начинающих, который я в своё время вела на олимпиадных школах при физтехе (был жутко популярным), а потом сильно переработанный (и изданный в виде книги) читала и читаю во Франции на научпоп-лекциях. Итак, поехали !

Что такое случайность?

Все мы знакомы (ну или думаем, что знакомы) с таким понятием, как «случайность». Какое представление вы имеете о значении этого термина?

Самый распространенный ответ на этот вопрос: «Случайность случается, когда случаются неожиданные вещи». Что это за неожиданные вещи? Я думаю, вы и сами понимаете, что такое определение не имеет особого смысла. Вот определение, которое Аристотель дает термину «случайность»: «Когда этот случайный характер проявляется в фактах, произведенных с определенной целью, тогда мы говорим о действиях фортуны и случайности», но он утверждает, что «... является определенной причиной всего, что, как мы говорим, происходит случайно или по счастливой случайности».

Введём более формальное определение. «Случайность − это фактор, который определяет исход эксперимента из множества возможных исходов, известных заранее».

Но можем ли мы говорить о случайности, если мы не знаем заранее множество возможных исходов? Например, приходите вы на контрольную и получаете задачи. Являются ли они для вас случайными? А являются ли они случайными для вашего преподавателя? Подумайте об этом.

Случайность можно разделить на два различных типа:

Онтологическая случайность − случайность является частью бытия. Например, подбрасывание монетки можно отнести к данному типу случайности.

Эпистемологическая случайность −это случайность, которая возникает из-за незнания, невежества или невозможности понимания каких-то процессов, но на самом деле тут вполне всё предопределено.

Например, приходите вы в школу и выясняете, что сегодня у вас будет контрольная. Вам кажется, что это случайно, а на самом деле это было давно запланировано на педагогическом совете. Но вы об этом просто не знали.... Фраза «Случайности не случайны» − как раз об эпистемологической случайности.

Очень многие люди и по сей день, не говоря уже о более ранней поре, считали и считают, что онтологической случайности не существует, что вся случайность носит только эпистемологический тип. Большинство учёных от эпохи Просвещения до начала двадцатого века считали, что, возможно, мы просто не знаем, как именно что-то работает, но всё предопределено заранее. Течение, в котором утверждается, что всё предопределено, называется детерминизмом. На принципе детерминизма построена классическая физика, а вот в квантовой физике всё достаточно сложно, и философы, и физики пока сами не до конца определились. Например, Поль Тири д'Гольбах, ученый-материалист и философ немецкого происхождения и французского выражения (1723-1789), писал: «В пылевом вихре, поднятом стремительным ветром, каким бы беспорядочным он ни казался нашим глазам, в самой страшной буре, возбуждаемой встречными ветрами, возмущающими волны, нет ни одной молекулы пыли или пылинки, у которой нет достаточной причины, чтобы занять то место, где она находится, и которое не действует строго так, как должно действовать. Геометр, точно знавший различные силы, действующие в этих случаях, и свойства движущихся молекул, показал бы, что, согласно данным причинам, каждая молекула действует именно так, как должна действовать, и не может действовать иначе, чем она действует.».

Гольбах связывает причинности разной природы, в частности механическую модель, основанную на всеобщей связи движения, и химическую модель, основанную на сродствах и включающую в себя человеческие страсти и желания. Он утверждает основной принцип всеобщей необходимой причинности: каждое следствие имеет естественную причину. Таким образом, он настаивает на «простых и общих законах», потому что они предлагают постоянный, обнадеживающий и достаточный критерий против сверхъестественного. Особенно сильно данное мнение у дуалистов, утверждающих, что помимо материи существуют элементы метафизики, в том числе божественное начало. Очевидно, что случайность онтологическая абсолютно несовместима с принятием чего-то всемогущего и всезнающего.

Изучение философии, надеюсь, не пройдёт мимо вас − в большинстве высших учебных заведений она включена в программу, а в аспирантуре по любой специальности она вообще является основным предметом. Но добавлять в наш курс помимо математики, экономики и психологии ещё и философию было бы жестоко с моей стороны.

Что такое вероятность?

Никто не умеет предсказывать, упадёт монета, если её бросить, орлом, решкой или вообще ребром. Поэтому подбрасывание монеты так часто и используют для определения своего действия в спорной ситуации − например, идти ли на первый урок или остаться в постели.

Первое использование этой игры в такой форме датируется созданием металлических денег. Однако до этого существовали другие формы подобных «запросов к мирозданию», в которых использовались предметы с двумя выделенными сторонами, например, раковина. Тогда выбор был оставлен на волю случая. Даже сегодня, мы загадываем «орёл или решка, когда мы хотим оставить решение на волю случая, в зависимости от того, какая сторона монеты выпадет после подбрасывания.

В каких ситуациях мы бросаем монету? Когда хотим, чтобы за нас решила «судьба», то есть, чтобы одинаково вероятно нам попался любой из двух исходов (падение на ребро обычно исходом не считают и просто перебрасывают монетку). В таких случаях вероятность выпадения орла оценивают как один к двум, ещё зачастую говорят о процентном соотношении орлов и решек «50 на 50».

Сколько примерно орлов выпадет, если мы подбросим монетку 1000 раз? Вероятность выпадения одного орла необходимо умножить на количество действий, так как, можно сказать, что в каждом броске в среднем у нас выпадает «пол-орла». Тогда получим, что в среднем выпадет 1000/2=500 орлов.

Так что такое вероятность? Обычно в рамках школьной программы дают следующее определение:

Вероятностью называют отношение числа благоприятных исходов к общему количеству равновероятных исходов.

Что такое благоприятный исход? Например, выпадение орла при подбрасывании монетки. Общее количество исходов − это всё множество исходов − в данном случае «орёл и решка», то есть их два.

Зачем же в определении вероятности есть слово «равновероятных»? Может, стоит просто делить устраивающие нас исходы на их общее количество?

Данное определение можно проиллюстрировать следующим анекдотом:

Спрашивают блондинку: Какова вероятность того, что, выйдя на улицу, вы встретите динозавра.

Б: 50 процентов.

- Это как?????

Б: Ну, или я его встречу, или нет..

Тут каноническая блондинка как раз и поделила один благоприятный исход «встречи с динозавром» на возможные два исхода.

Ну вы уже поняли, что оно так не работает. Мало того, если монетку подпилить, то она перестанет быть идеально симметричной и вероятности выпадения орла и решки теперь могут перестать быть равными. Так, например, поступают мошенники.

Игры с природой

Одна из главных причин популярности, да и вообще возникновения и развития теории вероятностей --- это желание получить много денег сразу и без труда. Например, выиграть их в лотерею или в рулетку. Попытка найти закономерности и «обмануть систему» − это мощный стимул к развитию соответствующего математического аппарата.

Кажется, что если мы знаем законы вероятности и правила, управляющие случайностью, то можем выиграть в любой игре, то есть найдём некую выигрышную стратегию (называемую специальным термином «мартингейл»). На самом деле это несбыточная мечта, и мы собираемся это доказать.

Главное, что мы должны понимать --- игра является случайной, если игрок не может иметь вообще никакого влияния на исход игры. Например, шахматы неслучайны, преферанс не совсем случаен, а вот подбрасывание монеты, рулетка и даже русская рулетка --- игры случайные. Будем называть те игры, в которых важную роль играет случай, пусть и подчинённый неким математическим зависимостям, «играми с природой». Можно играть только с природой, подбрасывая монетку. Можно сыграть с кем-то и природой − например, в «дурака». Тогда, с одной стороны, карты вам раздала природа (или шулер, но мы верим в доброту и честность людей, и вообще, колода у нас своя), но действия второго игрока уже неслучайны.

Есть ряд игр, в которых игроку суждено только приобрести билет и после этого никакого участия он не принимает. Так обстоит дело, например, с простой лотереей. Игра в рулетку − пример другого класса игр, в которых игроку дают возможность выбрать ставку и тип игры. С математической точки зрения игра в рулетку не является справедливой, так как при любом типе игры в выигрыше всегда оказывается казино. А как мы определяем, справедливая ли игра? Для этого потребуется понятие математического ожидания, впервые введённого в 1670 году голландским математиком Яном де Виттом. Он опубликовал первый современный трактат об оценке пожизненной ренты с помощью математического ожидания (приведенной стоимости будущих платежей).

Математическое ожидание

Что же такое, это математическое ожидание? Представим, что мы играем в какую-либо игру. Пока нам не важно, игра это с природой или с другим соперником. Пусть это будет игра в кости с игральным кубиком. За право сделать бросок мы платим 10 рублей. Если в сумме брошенных двух костей выпадет 7 очков, то нам дают 50 рублей, если выпадет другая сумма − ничего не дают. Выгодна ли эта игра? Стоит ли принимать в ней участие?

В этой игре нужно посчитать вероятность выпадения ровно 7 очков в сумме на двух костях. Всего существует ровно 36 равновероятных событий (мы полагаем, что в этой игре организаторы не являются такими явными шулерами, что предлагают плохие кубики). Какие же это исходы ? 1 + 1, 1 + 2, 1 + 3, итд. Из них ровно 6 событий (1+6, 2+5, 3+4, 4+3, 5+2, 6+1) благоприятны. То есть, вероятность выигрыша равна 6/36 = 1/6 . Вероятность проигрыша, соответственно, равна 1 − 1/6 = 5/6.

Исход броска − случайная величина.

Случайная величина может принимать в результате эксперимента неизвестные заранее значения из заданного множества.

В нашем случае множество возможных значений броска каждой из костей нам известно --- это числа от 1 до 6. Нам неизвестно, какое же число выпадет после очередного броска, это − онтологическая случайность (если организаторы игры − шулеры, то для нас это было бы эпистемологической случайностью). Нас интересует средний выигрыш для одной игры.

Введём определение среднего выигрыша на более формальном языке:

Математическое ожидание случайной величины есть сумма произведения вероятностей появления всех возможных значений на величину этих значений.

В нашем случае при успехе мы выигрываем 50 рублей, сумма выигрыша равна 40 рублям, (не забываем, что мы уже 10 рублей отдали!), а при неуспехе − проигрываем 0 рублей, сумма выигрыша равна минус десяти рублям. Итого: E=1/6∙40+5/6∙-10=-10/6.

Математическое ожидание выигрыша в данной игре отрицательное, то есть, игра для нас невыгодна. Чем больше партий мы в неё сыграем, тем большим будет математическое ожидание выигрыша (по модулю), а, значит, тем больше мы проиграем.

Христиан Гюйгенс, со своей стороны, в «Du calcul dans les jeux de hasard» 1657 года интересовался суммой ставок, чтобы игра была честной. Он установил, что если в игре у нас есть вероятность p выиграть сумму a, и вероятность q выиграть сумму b, мы должны поставить сумму S = (ap+bq)/(p+q), чтобы игра была честной. Другими словами,

Если математическое ожидание выигрыша за одну игру равно нулю, игра считается справедливой.

Понятие математического ожидания − достаточно базовая вещь, которая используется далеко не только в теории игр, но об этом попозже.

Всем привет ! Меня зовут Софи и я кот-гермафродит :)