Хабрахабр

Алексей Савватеев и теория игр: «Какова вероятность, что в ближайшие пять лет будет скинута атомная бомба?»

image

Расшифровка видеозаписи лекции.

Одним канатом к математике, другим канатом — к социальным наукам, прочно прикреплена. Теория игр — дисциплина, которая прочно зависла между математикой и социальными науками.

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

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

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

  • Теория игр в Талмуде.
  • Теория иг в русской классике.
  • Телеигра или задача о парковочных местах.
  • Люксембург в Евросоюзе.
  • Синдзо Абэ и Северная Корея
  • Парадокс Брайеса в Метрогородке (Москва)
  • Два парадокса Дональда Трампа
  • Рациональное безумие (снова Северная Корея)

(В конце поста — опрос про бомбу.)

image

Талмуд: задача о наследстве

Когда было разрешено многоженство(3-4 тыс лет назад). Еврей, когда женился, подписывал брачный договор, сколько выплатят жене, когда он умрет. Ситуация: умирает еврей у которого три жены. Первой завещалось 100 монет, второй — 200, третей — 300. Но когда открыли наследство, там было меньше 600 монет. Что делать?

Офтоп про подход евреев к решению вопросов:

А за полярным кругом?
Шаббат начинается с первой звездой.

  1. «Спуститься» по меридиану и ориентироваться по той местности где всё нормально. (не работает с Северным полюсом)
  2. Начинать в 00-00 и не париться. (тоже не работает с Северным полюсом), поэтому:
  3. Еврею нечего делать за полярным кругом и ездить туда не надо.
  1. В Талмуде написано, если наследство меньше 100 монет, то делить поровну.
  2. Если до 300 монет, то делим 50-100-150
  3. Если 200 монет, делим 50-75-75

Как эти три условия можно склеить в одну формулу?

Получаем список претензий, не только единичных, но и «компаний». Принцип, как решать кооперативные игры.
Выписываем претензии каждой жены, претензии пар жен, при условии, что третья всё «погасила». В теории игр это изучали, назвали "нуклеолус". Берется такое решение, такое разделение наследства, чтобы самая тяжелая претензия была минимально возможной (максимин). Роберт Алман доказал, что все три сценария из Талмуда — строго по нуклеолусу!

3000 лет назад? Как это может быть? (Господь диктовал? Ни я, никто другой не понимает, как это может быть. Или их математика была намного сложнее, чем мы думаем?)

Николай Васильевич Гоголь

image

Подкупать слуг ведь не всегда можно. Ихарев. Позвольте вам сделать один вопрос: как поступали вы доселе, чтобы пустить в ход колоды?

да и опасно. Утешительный. Сохрани Бог! Мы делаем это иначе. Это значит иногда самого себя продать. Лавки еще не успели нанять; сундуки и вьюки пока в комнате. Один раз мы поступили вот как: приезжает на ярмонку наш агент, останавливается под именем купца в городском трактире. Хозяин шарит в комнате. Живет он в трактире, издерживается, ест, пьет — и вдруг пропадает неизвестно куда, не заплативши. Карты, натурально, сей же час проданы с публичного торга. Видит, остался один вьюк; распаковывает — сто дюжин карт. А в четыре дни проигрался весь город! Пустили рублем дешевле, купцы миг расхватали в свои лавки.

У меня тоже была недавно в жизни двухходовка, в Тюмени. Это чисто теоретико-числовая двухходовка. Я изучаю ситуацию и прошу взять мне верхнее место в купе. Еду в поездом. Я говорю: «Верхнее».
Почему я просил верхнее место? Мне говорят: «Не надо экономить, берите нижнее, деньги не вопрос». (Подсказка: задачу я выполнил на 3/4)

ответ

Дорогие места не берут. У меня в результате было два места — верхнее и нижнее.
Нижнее в полтора раза дороже. Поэтому взял наугад верхнее. Я посмотрел, что почти все верхние куплены, а нижние почти все пустые. Только на участке Екатеринбург-Тюмень был сосед.

Пришло время поиграть

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

11 смсов: Минута прошла.

  • Шоколадка!
  • Шоколадка
  • Изи
  • Шшшш
  • 123
  • Здравствуйте Алексей Владимирович
  • Здравствуйте Алексей
  • Шоколадка:)
  • +
  • Combo-breacker
  • А

В Майкопе у меня на лекции был глава республики Адыгея и задал содержательный вопрос.

138 смсов. В Красноярске в зале сидели 300 мотивированных школьников. Я начал их зачитывать, пятый оказался матерным.

Конечно это лохотрон. Давайте разберем эту игру. Ни разу за историю розыгрышей (ближе к 100 раундов) не было, чтобы шоколадка кому-то досталась.

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

Равновесие — это такой розыгрыш, когда можно объявить стратегии вслух, и от этого они не поменяются.

Количество людей в зале не играет почти никакой роли. Пускай шоколадка в 100 раз дороже смса (если в 1000, то результат будет немножко другой).

Каждый из вас сомневается и не знает как играть. Смешанные равновесия. Например, рулетке 1/6. И он отдает свой ход случаю. Человек решает, что в 1/6 случаев (при многократной игре) он будет посылать смс.

Вопрос: какая «рулетка» будет равновесной?

Раздаем всем рулетку 1/р. Мы хотим найти симметричное равновесие. Надо удостовериться, что люди хотят в такую рулетку сыграть.

Если вы её поймете, считай что с теорией игр вы уже познакомились. Существенная деталь. Я утверждаю, что с равновесием совместимо только одно «р».

Например 1/1000. Предположим что «р» очень маленькое. Тогда получив такую рулетку ты быстро догадаешься, что шоколадки не видать и выкинешь такую рулетку и будешь слать смс.

Тогда правильным решением будет не посылать смс и сэкономить рубль. Если «р» слишком большое, например 1/2. Точно ты не будешь вторым, а скорее всего сорок вторым.

Но сейчас не о них речь. Есть расчет равновесии с одновременным глубоким продумыванием.

Значения «р» должны быть такие, что ваш выигрыш от того, что вы пошлете смс, в среднем будет равен выигрышу от того, что не пошлете.

Посчитаем эту вероятность.

N+2 — количество людей в аудитории.

image

На видео разбор формул на 33й минуте.

(1+pn)(1+p)^n = 1/100 (вероятность шоколадки=цене смс)

Если рулетка такова, что её независимый запуск всеми остальными участниками приводит к вероятности получения шоколадки в случае вашего отправления смса (равной 0,01).

При цене соотношении цен шоколадка/смс = 100, количество смс будет 7, при 1000 — 10.

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

Если пустили на самотёк — будет хуже, чем если бы договорились. Один из результатов теории игр — идея свободного рынка, что он сам всё наладит — совершенно не верна.

Люксембург в Евросоюзе

Приготовились смеяться.

Люксембург входил в Евросоюз.

Совет министров Европейского союза состоял из 6 представителей по одному из каждой страны ЕС (с 1958 по 1973).

Страны были разные и поэтому:

  • Франция Германия Италия — по 4 голоса,
  • Бельгия, Нидерланды — 2 голоса,
  • Люксембург — 1 голос.

Решение принято, если квота превзойдена. Шесть человек принимали решения по всем вопросам 15 лет подряд. Квота = 12…

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

Они ответили:
— Ты не сравнивай Люксембург с вашим советским лагерем, где математику хорошо знают. Я когда это узнал, попросил своих знакомых немцев (не было знакомых из Люксембурга) прокомментировать. Они никакого представления о четности/нечетности не имеют.
— Как, вся страна?!??!?
— Ну да, кроме, может, парочки учителей.

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

Синдзо Абэ

Я ехал на лекцию по теории игр и увидел новость:

image

Что этого не может быть. У меня заиграл тревожный звоночек. КНДР способны сделать атомную бомбу, но доставить её — вряд ли. Никак.

Зачем вводить в намеренную дезинформацию?

Это страшно для японцев. Правда в том, что ракеты могут долететь до Японии. Но если это сообщить НАТО, это ни к чему не приведет, а пугая «Европой» — приведет.

Я не настаиваю на правоте, может есть и другие анализы этой новости.

Метрогородок

Когда-то дано шутники назвали улицу «Открытое шоссе», потому что она тупиковая и упирается в лес. Те же шутники назвали район «Метрогородок», потому что там никогда не будет метро."

В начале 90х пробок еще не было и разыгрался следующий сюжет.

image

Метрогородок обозначен буквой «М».

700 000 человек, согласно последней переписи. Щелковское шоссе соединяет гигантский кластер городов.

По шоссе ехать час, по дорожке — 20 минут. Из Метрогородка к ВДНХ ведет маленькая извилистая дорожка, без единого светофора. Часть народа с шоссе начинает «срезать» — результат — 30 мин пробка.

Если сильно меньше 30 минут пробка — это известно, и тогда еще больше машин сворачивают, чтоб «срезать». Это точно из теории игр. Если сильно больше, народ перестает «срезать».

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

Без «соединялки» 1 час и 20 минут, с «соединялкой» — 1 час и 50 минут. Для водителей как был час, так и остался, а для жителей Метрогородка 20 минут превратились в 50. Чистый парадокс Браеса.

Юрий Евгениевич Нестеров получил высочайшую награду в области математического программирования. А вот пример который стоил премии Данцига.

Если появление новой дороги может привести к ухудшению дорожной ситуации, то, наверное, какой-то запрет может привести к улучшению. Идея такая. И Он изобразил конкретику, когда это происходит.

Есть пункт «А» и пункт «Б» и посередине точка, которой нельзя избежать.

image

Нестеров предложил поставить знак «смены дороги».
В итоге машины поделились на две категории, кто ехал прямо, а потом в объезд (4000) и тех, кто ехал в объезд, а потом прямо (4000) и при этом пробок на узкой прямой дороге не возникало. В итоге все едут 1 час и 20 минут. И в итоге все участники дорожного движения едут 1 час.

Трамп

За Трампа проголосовало меньше, чем против него.

Выборщики.

image

2 выборщика.
Во втором штате 12 млн чел, 8 — «за», 4 — «против». В первом штате 8 млн чел, все «против» Трампа. 3 выборщика и все обязаны голосовать за Трампа.
В итоге 2:3 по выборщикам в пользу Трампа, хотя за него проголосовало 8 а против него 12 млн.

Скандальный кандидат

Бывает, что какой-то кандидат по опросам не проходит. Или про «Брекзит» по опросам не должен был произойти. Есть недоброкачественные опросы (когда выпиливают неугодные мнения из выборки), но профессиональные социологи так делают редко.

В кафтане удобно жить, у него есть некое социальное окружение: работодатель, семья, родители. Человек живет как будто в кафтане, говорит одно, а перед урной сбрасывает кафтан и голосует по-другому.

Все эти люди, так или иначе, на него влияют. Вот модель моего знакомого, потому что у меня нет фейсбука.

image

И если мы с ним обсуждаем политику и сильно расходимся, это представляет некоторую небольшую дискомфортную составляющую. Мнения 500 человек важны.

Модель социального раскола.

Примеры:

  • Брекзит
  • Русско-украинский раскол
  • Выборы США

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

Можно написать функцию выигрыша:

image

В каждой клеточке написано, как каждый человек на каждого влияет и с каким знаком. Есть матрица взаимодействий aij (много миллионов на много миллионов). Один может влиять на очень многих, но на одного влияют человек 200. Сильно несимметричная матрица.

Мы умножаем внутреннее состояние vi человека на то, что он сказал вслух σi

Равновесие — это когда каждый принял решение, какое σ транслировать вслух.

Оба врут, но солидаризируются. Могут даже думать одновременно про одно, а вслух говорить одновременно другое.

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

image

С пассионарных и фанатиков надо начинать просчитывать равновесие.

image

Телевизор — это магнитное поле, которое смещает внутреннее мнение.

image

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

При формуле моделирования белого шума:

image

Очень много. Получается по два уравнения на каждого человека, 100 млн человек — 200 млн уравнений.

Возможно, настанет момент, когда можно будет взять данные соцопросов, исследовать количественные показатели социальной сети знакомств и сказать: «В этой системе соцопрос на 7% снизит количество голосов за данного кандидата.»

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

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

Модель рационального безумия

Многие люди поражаются «бесстрашию» руководства Северной Кореи, проводящей испытания своего ядерного оружия «под носом» у США. Особенно, учитывая судьбу Каддафи, Саддама Хусейна и др. Неужели Ким Чен Ын сошёл с ума? Однако в его «безумном» поведении вполне может быть рациональное зерно.

Это модель Цезаря, сжигающего мосты.

image

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

image

Дерево игры и прогноз.

P.S.

Поднимите руку, кто считает что в ближайшие пять лет будет скинута атомная бомба?
Я считаю 50%. Пол руки бы я поднял.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть