2. Матричный метод определения оптимальных смешанных стратегий и цены игры для игр 2х2.
3. Графический метод решения игр 2хm и 3хm.
1. Итак, на прошлой лекции мы выяснили, что большинство игр с нулевой суммой не поддается простому и красивому решению в чистых стратегиях. Конечно, путем исключения доминируемых и дублирующих стратегий иногда удается существенно уменьшить матрицу игры. И если удалось ее свести к одной строке или одному столбцу - игра решена в чистых стратегиях даже без принципа минимакса и нахождения седловой точки. Но чаще приходится признать, что ни одна из чистых стратегий не является оптимальной. Выход из этой казалось бы тупиковой ситуации тем не менее существует - надо чередовать стратегии в определенной пропорции. Поэтому решением игры в этом случае является как раз такая пропорция. Например, если у игрока 3 чистых стратегии и мы после определенных расчетов говорим – ему надо использовать эти стратегии в пропорции 5:1:4. В принципе, здесь могут стоять любые натуральные числа или даже ноль. В последнем случае говорят, что соответствующая стратегия не используется в смеси стратегий и является неактивной. Те же, которые используются, называют активными стратегиями. А само поведение игрока, связанное с чередованием его стратегий, называют смешанной стратегией. Основная теорема теории игр (она же теорема Неймана или теорема о минимаксе) гласит: любая парная игра с нулевой суммой имеет решение в чистых или смешанных стратегиях. Это решение определяет оптимальные минимаксные стратегии игроков и цену игры. Использование любой другой стратегии в среднем менее выгодно каждому из игроков. Цена игры всегда находится между нижней и верхней ценой матрицы игры. Решение в чистых стратегиях – это просто частный случай решения в смешанных стратегиях (когда в смеси активна лишь одна стратегия).
Если смешанная стратегия выражена в виде пропорции, то стоящие в ней числа называют относительными частотами применения стратегий. Существует и другой способ задания смешанной стратегии - через вероятности реализации чистых стратегий. Их легко рассчитать по известным относительным частотам. Пусть например задана смесь четырех стратегий в виде пропорции N1: N2: N3: N4. Тогда вероятность реализации первой стратегии равна:
р1 = N1/( N1+ N2+ N3+ N4)
Аналогично рассчитываются и остальные 3 вероятности р2, р3, р4. Естественно, что сумма всех вероятностей в этом случае равна 1. На самом деле мы довольно часто сталкиваемся с такого рода понятиями. Например, при игре в русскую рулетку, когда в 6-зарядный барабан револьвера вставляется один патрон и выстрел производится после вращения барабана - реализуется смесь двух стратегий (убить – не убить) с относительными частотами 1:5, а вероятность рокового выстрела – 1/6. Или когда в годы репрессий давали разнарядку типа «каждого десятого» - это тоже смешанная стратегия с частотами 1:9.
Если действия по реализации стратегий производятся многократно, то вполне достаточно буквального использования относительных частот. Например, если работнику консульского отдела рекомендована смесь 2-х стратегий (выдать – не выдать визу) с частотами 2:3, то он может первым двум посетителям оформить визу, следующим 3-м – отказать и т.д. Но при этом он рискует тем, что посетители его «просчитают» и будут заранее знать кому он не откажет. Поэтому в теории игр обычно используется другой способ, который в принципе исключает возможность знать следующий ход. Он основан на вероятностном подходе и связан с использованием датчика случайных чисел. Такие датчики есть во многих компьютерных программах, хотя на практике чаще используют подручные средства типа бросания монетки или игральной кости. Например, при частотах 1:2 надо при каждом ходе бросать кубик и применять первую стратегию, когда выпадет 1 или 2, а в остальных случаях – использовать вторую стратегию. Любые вычислительные методы, использующие датчик случайных чисел, принято называть методами Монте-Карло. Заметим, что по методу Монте-Карло можно реализовать смешанную стратегию даже в одноходовой игре, которыми обычно и являются игры, представленные в нормальной форме. Осталось понять, как найти оптимальную смесь стратегий.
2.Итак, допустим, что проверка на наличие седловой точки в игровой матрице дала отрицательный результат. Тогда выполняется процедура выбраковки доминируемых и дублирующих стратегий. Если при этом получилась матрица 2х2, то можно вздохнуть спокойно - решение в смешанных стратегиях удастся найти сравнительно просто. В противном случае элементарного решения нет, придется потрудится. Причем объем вычислений резко увеличивается для матриц большой размерности и в этом случае используют приближенные методы решения игр. Отчасти поэтому в литературе обычно рассматриваются именно игры 2х2.