5. Решение матричных игр в смешанных стратегиях.

Пример (игра поиск): Имеются 2 игрока и 2 комнаты. Игрок А может спрятаться в одной из этих двух комнат, а игрок В ищет его в одной из двух комнат. Если игрок В находит игрока А, то игрок А выплачивает ему одну денежную единицу. В противном случае игрок В выплачивает игроку А одну денежную единицу.

Так как , значит . Данная игра не имеет седловой точки и не имеет решения в чистых стратегиях.

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

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

Смешанную стратегию для игрока A обозначим ( ). Для игрока В смешанную стратегию обозначим ( ).

Здесь – вероятности применения игроками A и В стратегий и соответственно. Обозначим через P и Q множества стратегий для игроков A и В соответственно.

Величина выигрыша при использовании смешанных стратегий p и q случайна и равна (С – платежная матрица игры).

Основная теорема теории игр

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

(1)

Выигрыш , соответствующий паре оптимальных стратегий наз-ся ценой игры.

Теорема: Любая конечная матричная игра имеет решение в области смешанных стратегий.

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

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

(2)

Обозначим через - оптимальную смешанную стратегию игрока В. Пусть игрок А использует некоторую i-ую стратегию p. При этом выигрыш удовлетв. след. нер-ву. Вводя обозначения получим следующую задачу линейного программирования, относительно интереса игрока В.

(3)

Заметим, что (2) и (3) являются парой взаимнодвойственных задач линейного программирования. Согласно теоремы двойственности, задачи (2) и (3) имеют решения одновременно. Отметим, что целевая функция задачи (2) ограничена снизу нулем и решение , . Это решение является планом задачи (2), следовательно, задача (3) имеет решение. Если - решение задачи (2), то координаты вектора находятся следующим образом . Аналогично, если - решение задачи (3), то , а . Значит, что если на первом шаге производилось преобразование платежной матрицы, то из полученной цены игры следует вычесть положительную величину, которая прибавлялась для получения положительно матрицы.

Активные стратегии. Теорема об активных стратегиях.

Опр. Будем говорить, что чистая стратегия i активна, если она входит в оптимальную смешанную стратегию с ненулевой вероятностью.

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

Док-во. Пусть первые к стратегий для игрока А – активны, т.е. и соответственно первые стратегий игрока В также активны, т.е. . Пусть игрок А применяет свою стратегию , а игрок В- некоторую чистую активную стратегию j, при этом полученный выигрыш обозначим через . Выразим через цену игры , т.е. . Если мы предположим, что , следовательно противоречие.