Начинаем разбирать теорию игр — это набор инструментов, которые помогают принимать взвешенные, рациональные и точные решения, а также понимать данные. Чем больше данных об игроках и ситуациях — тем точнее анализ и прогноз.
Сегодня будет простое введение — что это, для чего и что внутри. Дальше будем постепенно применять знания на практике.
Что такое теория игр
Представим ситуацию: в городе утро, всё в снегу, вам нужно попасть на работу. Варианта два — на машине и на общественном транспорте. Вы знаете, что на общественном транспорте вы гарантированно доберётесь до работы за час: автобусы ходят точно, расписание вы знаете и сто раз так уже ездили. На машине вы доберётесь в два раза быстрее, поэтому можно попозже выйти из дома. Но это если не будет пробок — если будут, то можно застрять в них и на час, и на два.
Допустим, выбрали машину. Вы примерно помните, где обычно зимой возникают пробки, и решаете их объехать, чтобы точно успеть приехать вовремя.
Но, подъехав к нужной улице, вы обнаруживаете, что там тоже собралась пробка. Оказывается, половина района подумала так же, как и вы, и решила объехать возможные пробки этим маршрутом.
В этой ситуации вы не могли повлиять на решения других водителей поехать тем же маршрутом или узнать про это. Но их действия напрямую повлияли на вас — вы попали в пробку. Они тоже не знали, что вы поедете этим маршрутом, и рассчитывали всё так же, как и вы.
При этом кто-то просто поехал старым маршрутом и успел — на том пути не было пробок, потому что они все переместились в другие места. Кто-то поехал на общественном транспорте и снизил нагрузку на дорогу — из-за этого на старом маршруте тоже не было пробок. Кто-то вообще не поехал на работу и остался дома.
Ключевая мысль такая: разные решения разных людей в разных ситуациях по-разному влияют на нас. Обратно тоже работает — наши действия тоже влияют на других. Иногда можно заранее отследить, понять или спрогнозировать, какие действия на что повлияют. Этим и занимается теория игр.
Что такое игра
Автор теории игр — физик, математик и инженер Джон фон Нейман (в некоторых источниках — Нойман). Под игрой он понимал любую ситуацию, в которой выполняются такие условия:
- В ней не меньше двух участников.
- У каждого участника свой интерес.
- У каждого участника есть несколько вариантов действий.
- Каждый принимает решения на основании информации о действиях других.
- Есть какие-то общие правила, которые известны всем. Они могут меняться, сокращаться или расширяться, но они быстро становятся известны всем.
С этой точки зрения большинство наших бытовых ситуаций попадает под действие теории игр. Даже обычные переговоры о зарплате или о том, где провести отпуск, — в них тоже действует теория игр.
Изначально фон Нейман рассматривал игру в покер и пытался вывести универсальные стратегии, которые приводили бы к выигрышу (отсюда и название теории). Но потом он расширил применение своей теории на все подобные ситуации, где поведение одного участника влияет как на его собственные позиции, так и на поведение остальных.
Стратегия
Смысл теории игр — найти максимально выигрышную стратегию для конкретного игрока. Стратегия — это его последовательность действий: что он делает и какие сообщения отправляет тем самым другим игрокам.
В некоторых играх невозможно выиграть, и в этом случае лучшей стратегией будет проиграть как можно меньше или находиться в игре как можно дольше. Все онлайн-шутеры, где игровое поле постоянно сжимается — это как раз про такую стратегию.
Мы тоже будем говорить в основном о стратегиях выигрыша, но параллельно будем рассматривать и другие результаты. Задача дата-аналитика в этом случае — собрать информацию обо всех игроках и их стратегиях и понять, какая стратегия для нас сработает лучше всего.
Виды игр
В зависимости от поведения участников и правил, игры можно поделить на несколько категорий. Они могут пересекаться между собой.
С нулевой и ненулевой суммой. В игре с нулевой суммой выигрыш одного означает проигрыш другого и наоборот. В играх с ненулевой суммой выигрыш одного необязательно приводит к проигрышу другого. В таких играх бывает так, что выгоду получает каждый участник.
Кооперативные и некооперативные. В кооперативных играх игроки могут объединяться друг с другом, чтобы получить лучшие результаты и координировать свои действия. При этом это не постоянный союз — игрок в любой момент может выйти из коалиции и играть дальше сам.
Симметричные и нет. В симметричных играх у каждого игрока всегда один и тот же набор стратегий, а в несимметричных стратегии могут быть разные.
С полной или неполной информацией. В играх с полной информацией каждый знает все доступные другим игрокам стратегии и может делать выводы на их основе. В играх с неполной информацией никто не знает, какую стратегию выбрал другой участник. Наш пример с пробками как раз из разряда игр с неполной информацией.
Параллельные и последовательные. В последовательных играх все ходят по очереди (необязательно по порядку, но за один ход действует только один игрок). В параллельных все действуют одновременно и не знают, что сделали другие, пока не сделали свой ход. Пример с пробками — это параллельная игра.
Игры и математика
В теории игр используется мощный математический аппарат. Это значит, что можно написать или придумать симуляцию для каждой игры и посмотреть на возможные результаты при разных стратегиях игры. Часть стратегий получает строгое математическое доказательство, другая — процентную вероятность успеха при выборе той или иной стратегии.
В нашем случае это полезно тем, что для простых игр мы можем написать алгоритм и сразу проверить игру на практике — смоделировать поведение разных игроков и посмотреть, к какому результату что приведёт. Этим мы будем заниматься в следующих статьях. Для этого нам пригодится Python — универсальный язык для построения разных моделей.
Где используется теория игр
Теория игр работает почти в каждой области жизни:
- в экономике — как и с кем торговать;
- в переговорах — как договариваться и на каких условиях;
- в математике — там есть целый раздел, посвящённый комбинаторным играм;
- в политике — какое принять решение на основании информации о действиях других стран;
- в быту — когда нужно принять решение на основании неполной информации;
- в играх — когда нужно найти выигрышную стратегию.
Что дальше
В следующий раз разберём дилемму заключённого — этот пример чаще всего приводят, когда хотят показать действие теории игр в жизни. Он не единственный, но самый известный. Мы посмотрим, как он работает в теории, и попробуем смоделировать его работу на практике — напишем код и выясним лучшую стратегию.
