Начало: Математика для чайников. Глава 1. Что такое математическая абстракция.
Кажется, что человеческую душу невозможно вычислить, и никакая математика тут не поможет. А вот и неправда! Есть такой раздел математики, как теория игр, который буквально тем и занимается, что пытается вычислить поведение человека. Кому-то может показаться странным, почему же эта наука называется «теория игр»? А все потому, что человек – существо социально, он живет в обществе, и, являясь частью общества, вынужден как-то взаимодействовать с другими членами общества. А еще человек существо эгоистичное, и, в ходе взаимодействия, пытается что-то выиграть, чаще всего за счет других людей. Именно поэтому процесс взаимодействия между людьми в данной теории получил название «игра», а сам раздел математики – «теория игр». И действительно, множество взаимодействий между людьми можно описать как игру. Но не путайте с психологией, где тоже есть понятие «игра» и тоже по ней составлен целый трактат, называемый «Игры в которые играют люди и люди, которые играют в игры». Здесь, в математике, игры описаны как алгоритмы, где люди, словно роботы, взаимодействуют по четким правилам, и в ходе так называемых игр просчитывают свои ходы, четко математически оценивают их. Вы спросите, а какая польза от теории игр, если люди в реальной жизни так не делают? Но на самом деле, люди ведут себя достаточно рационально в очень многих ситуациях. И, как раз в таких ситуациях, теория игр и может предсказать человеческое поведение.
Естественно, как и любая другая наука, теория игр имеет ряд ограничений. Ограничения теории игр как раз вытекает из принятого в ней допущения, что люди делают рациональный выбор. В тех ситуациях, когда это не так, теория игр не работает. Но, как я уже сказал, человек ведет себя рационально довольно часто. Перечислю несколько таких ситуаций:
- Принятие решение в бизнесе. Владелец бизнеса, как правило, стремиться просчитать потенциальные риски и выгоды и сделать наиболее рациональный выбор.
- Когда играет в шахматы или другие интеллектуальные игры.
- Когда принимает инженерные решения
- Когда принимает политические решения.
И много других случаев.
Говоря о теории игр, нельзя не упомянуть знаменитую «дилемму заключенных», которая очень хорошо иллюстрирует, чем, собственно говоря, занимается теория игр.
Двое преступников, А и Б, попались примерно в одно и то же время на сходных преступлениях. Есть основания полагать, что они действовали по сговору, и полиция, изолировав их друг от друга, предлагает им одну и ту же сделку: если один свидетельствует против другого, а тот хранит молчание, то первый освобождается за помощь следствию, а второй получает максимальный срок лишения свободы (10 лет). Если оба молчат, их деяние проходит по более лёгкой статье, и они приговариваются к 6 месяцам. Если оба свидетельствуют против друг друга, они получают минимальный срок (по 2 года). Каждый заключённый выбирает, молчать или свидетельствовать против другого. Однако ни один из них не знает точно, что сделает другой. Что произойдёт?
Часто игры записываются и анализируются в виде матриц. Об этом речь пойдет чуть ниже. А пока составим матрицу для дилеммы заключенных:
А теперь представим развитие ситуации, поставив себя на место заключенного А: «Если мой подельник молчит, лучше его сдать и выйти на свободу. Если он говорит, то так же лучше все рассказать, и получить всего два года, вместо десяти». Таким образом, если каждый игрок выбирает, что лучше для него, оба сдадут друг друга, и получат два года, что не является идеальной ситуацией для обоих. Если бы каждый думал об общем благе, они бы получили всего по пол года.
Ну а теперь перейдем непосредственно к самой теории игр.
Начнем с того, что игры бывают разных типов. Их можно классифицировать по количеству игроков: игры из двух игроков (парные игры) и игры из множества игроков. Наиболее изучен, конечно, первый вариант – игры из двух игроков. По количеству стратегий игры делятся на конечные и бесконечные. По информированности игроков игры можно классифицировать на игры с полной или неполной информацией. По способу взаимодействия игры делятся на антагонистические и кооперативные. В первом случае игроки играют друг против друга, во втором случае они скооперировались для достижения общей цели. Антагонистические игры часто называют играми с нулевой суммой, потом что если выигрывает один, то проигрывает другой, и сумма их выигрышей равна нулю (проигрыш считается отрицательным выигрышем).
Под стратегией в игре понимается способ действия. Как я уже говорил выше, часто антагонистические игры рассматривают в матричной форме (про матрицы см. Математика для чайников. Глава 10. Линейная алгебра), где матрица – это совокупность выигрышей:
Строки соответствуют чистым стратегиям игрока 1, столбцы – чистым стратегиям игрока 2. На пересечении строки и столбца строится выигрыш игрока в соответствующей ситуации. Например, в ситуации s=(i,j) выигрыш игрока 1 равен:
А вот выигрыш игрока 2 равен
Для всех
Иными словами, сколько игрок 1 выигрывает, столько же и проигрывает игрок 2. Ну и наоборот. Замечу, что в данном описании у игрока 1 имеется m стратегий, а у игрока 2 n. То есть, в общем случае, эти стратегии не одинаковы. Матрица имеет размерность m на nи называется платежной матрицей.
Цель игрока 1 – максимизировать свой выигрыш, но он также понимает, что цель игрока 2 – минимизировать его выигрыш, ибо только так игрок 2 может максимизировать свой. Значит, при, стратегии i игрока 1 игрок 2 выберет стратегию j максимизирующую его выигрыш, но тем самым минимизируя выигрыш игрока 1:
Тогда оптимальной стратегией для игрока 1 будет та стратегия, при которой он получит максимальный минимум:
Надо сказать, что аналогичными соображениями буде руководствоваться и игрок 2: предполагать, что игрок 1 будет «вредничать», и выбирая те стратегии, где у игрока 1 будет минимальный выигрыш. Таким образом, игроку 2 точно так же придется максимизировать минимальные выигрыши.
Для второго игрока выигрыш равен –h, то есть:
Здесь
Таким образом, оптимальная стратегия для него будет
Отсюда
А теперь, чтобы было более понятно, рассмотрим пример. Пусть игра описана платежной матрицей
Определим максимальную стратегию первого игрока, минимаксную стратегию второго игрока, нижнюю и верхнюю цену игры.
Решение. Справа от платежной матрицы выпишем наименьшие элементы в ее строках и выберем максимальный из них, а внизу – наибольшие элементы в ее столбцах, и выберем минимальный из них:
Наибольший из наименьших элементов строк - 2. Это значит, что нижняя цена игры равна 2. Ей соответствует первая строка. То есть, максимальная строка первого игрока – первая. А вот в случае второго игрока мы ищем наименьший из наибольших элементов столбцов. Это число 5 и оно соответствует второму столбцу, то есть минимальная стратегия второго игрока – вторая.
В данном случае, у нас верхняя и нижняя цена игры – разные. А вот если бы были одинаковые, то это бы означало, что у игры есть седловая точка. Верно и обратное, что если у матричной игры есть седловая точка, то значит верхняя и нижняя цена игры одинаковы.
Рассмотрим еще пример. Пусть у нас дана платежная матрица:
Найдем верхнюю и нижнюю цену игры. Точно так же справа выпишем в строках, а снизу наибольшие элементы в столбцах.
Здесь мы видим, что нижняя и верхняя цена игры совпадает. Цена игры равна значению седловой точки
Таким образом, максимальная чистая стратегия первого игрока: вторая, а второго – третья. Под чистой стратегией поднимается стратегия, которую игрок выберет с вероятностью единица (100%).
Следует заметить, что игра не всегда имеет седловую точку. В таком случае она не имеет решения в чистых стратегиях, но может иметь в смешанных стратегиях. Это значит, что игрок выбирает стратегию случайно. Это и есть смешанная стратегия. А оценивается смешная стратегия по среднему выигрышу. Строгим определением смешанной стратегии является вектор вероятностей выбрать ту или иную стратегию.
Для первого игрока она, как правило, обозначается буквой p:
Причем, сумма всех этих вероятностей равна единице:
Смешанная стратегия второго игрока обозначается буквой q и задается вектором вероятностей
Если первый игрок использует стратегию p, а второй q, то возможно вычислить математического ожидание выигрыша первого игрока E(p,q). Оно же является математическим ожиданием проигрыша второго игрока. Чтобы вычислить это математическое ожидание, нужно перемножить вектор смешанной стратегии первого игрока на платежную матрицу и на вектор смешанной стратегии второго игрока:
По сути, нахождение математического ожидания выигрыша сводиться к простому перемножению матриц (см. Математика для чайников. Глава 10. Линейная алгебра).
Если необходимо найти оптимальную (наилучшую) смешанную стратегию, то это делается путем сведения данной задачи к задаче линейного программирования, а именно: у нас есть некоторая линейная функция, которую необходимо максимизировать или минимизировать и некоторые ограничения, заданный системой линейных неравенств и уравнений. Для решения подобных задач существует специальный метод, который мы рассмотрим в будущих уроках.
Следующая глава: Математика для чайников. Глава 14. Производная