Тема 1.1. Матричные игры и линейное программирование

Глава 1. Основные понятия теории игр.

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

Как утверждал Г.Лейбниц, "...и игры заслуживают изучения; и если какой-нибудь проницательный математик посвятит себя их изучению, то получит много важных результатов, ибо нигде человек не показывает столько изобретательности, как в игре ".

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

Остановимся на классификации игр.

Интересы участников игры (игроков) могут оказаться несовпадающими и даже противоположными. В последнем случае игра называетсяантагонистической.

В игре могут участвовать два или более игроков. Случай игры с одним участником (пасьянс, управление физическим объектом и т.д.) в сущности является игрой двух лиц, где вторым участником выступает природа (судьба, рок, провидение).

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

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

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

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

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

Простейшими являются игры 2 лиц с нулевой суммой.

Пусть в такой игре игрок 1 имеет m выборов и игрок 2 - n выборов. Если игрок 1 делает свой i-й выбор, а игрок 2 - свой j-й выбор, то выигрыш игрока 1 (проигрыш игрока 2) равен Rij. Такая игра называется матричной и матрица R = [ R_ij / i=1..m , j=1..n ] называетсяматрицей выигрышей (пла-тежной матрицей).

При ведении игры игрок должен ориентироваться на оптимальную политику партнера и наказывать его за отступления от таковой.

Проведем рассуждения за игрока 1. Если Я воспользуюсь i-м выбором, мой противник для минимизации моего выигрыша сделает тот из своих выборов, который даст min R_ij. Соответственно, Я должен использовать тот выбор, который гарантирует мне выигрыш, не меньший. (1)

(1)

Противник, рассуждая аналогично, приходит к выводу о гарантированном проигрыше, не превышающем. (1.2)

(1.2)

Если в матрице выигрышей существует элемент R_kl = V₁ = V₂, то говорят о наличии оптимальной политики "в пространстве чистых стратегий" и оптимальными выборами для игроков соответственно являются выборы k и l. Пару (k, l) называют седловой точкой.

Пример 1. Пусть игра определяется матрицей (1.3)

(1.3)

Седловые точки - (4, 1) и (4, 2). Цена игры = 6; оптимальный выбор для игрока 1 - четвертый, для игрока 2 равнозначны первый и второй (под ценой игры понимают гарантированный выигрыш-проигрыш при оптимальной политике обоих игроков).

Пример 2. Пусть игра определяется матрицей (1.4)

(1.4)

Здесь равенство V₁ = V₂ не выполняется; оптимальной чистой стратегии для игроков нет.

При анализе игр часто прибегают к попыткам обнаружить доминирование между строками и столбцами. Так в примере 1 элементы четвертой строки больше элементов других строк: использование выбора 4 выгоднее других выборов при любой политике противника. Противник видит, что в такой ситуации использовать выборы 3 и 4 неразумно.

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

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

Если игрок 1 прибегает к своему выбору i с вероятностью P_i, а игрок 2 - к своему j-му выбору с вероятностью Q_j, то ожидаемый выигрыш игрока 1 (проигрыш игрока 2) равен (1.5)

(1.5)

Основная теорема теории игр (теорема Джона фон Неймана) утверждает, что любая матричная игра с нулевой суммой всегда имеет седловую точку, т.е. существуют векторы P и Q такие, что (1.6)

(1.6)

(V - цена игры).

Тема 1.1. Матричные игры и линейное программирование.

Очевидно, что если игрок 1 отступит от оптимальной политики, а игрок 2 будет действовать оптимально, то выигрыш игрока 1 будет меньше цены игры, и если игрок 2 отступит от оптимальной политики при сохранении оптимального поведения игроком 1, то его проигрыш превысит цену игры (1.7):

(1.7)

Рассуждения игрока 1: мне хотелось бы максимизировать цену игры, т.е. мой гарантированный выигрыш, и я должен подобрать систему значений P_i так, чтобы при любом выборе противника мой ожидаемый выигрыш был больше цены игры.

Рассуждения игрока 2: мне хочется уменьшить мой гарантированный проигрыш, т.е. цену игры, и мне надо подобрать значения Q_j так, чтобы при любом выборе противника мой проигрыш был меньше цены игры.

Отсюда возникают две задачи (1.8), (1.9):

(1.8)

(1.9)

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

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

Обратим внимание на то, что при увеличении элементов матрицы R на любую константу С цена игры увеличится на С и это изменение не окажет влияния на искомые вероятности выборов. Таким образом, можно добиться, например, положительности элементов матрицы и, следовательно, цены игры. Поэтому можно допустить, что цена игры V положительна.

В предположении V > 0 проведем замену переменных

Х_i = P_i / V, Y_j = Q_j / V.

Отсюда видно, что

Соответственно, поставленные задачи можно преобразовать к задачам с меньшим числом переменных:

Например, для игры с матрицей

возникают задачи:

максимизировать минимизировать

Y₁ + Y₂ + Y₃ X₁ + X₂ + X₃

при при

Y₁ + 2 Y₂ + 3 Y₃ £ 1 X₁ + 4 X₂ + 2 X₃ ³ 1

4 Y₁ + Y₃ £ 1 2 X₁ + 3 X₃ ³ 1

2 Y₁ + 3 Y₂ £ 1 3 X₁ + X₂ ³ 1

Y₁, Y₂, Y₃ ³ 0 X₁, X₂, X₃ ³ 0

Решение этих задач симплексным методом дает оптимальные значения

X = {11/37, 4/37, 5/37}, Y = {8/37, 7/37, 5/37}

и экстремумы целевых функций, равные 20/37.

Отсюда V = 37/20, P = {11/20, 4/20, 5/20}, Q = {8/20, 7/20, 5/20}.