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

Платежная матрица, нижняя и верхняя цена игры.

Опр. Рассмотрим парную конечную игру.

Пусть у игрок располагает личными стратегиями, которые обозначим .

Пусть у игрока имеется личных стратегий, обозначим их .

Говорят, что игра имеет размерность .

Опр. Матрица элементами которой являются выигрыши, соответствующие стратегиям и , называется платежной матрицей или матрицей игры.

Общий вид такой матрицы представлен в таблице 1.

Таблица 1 B1 B2 … Bn A1 a11 a12 … a1n A2 a21 a22 … a1n … … … … … An am1 am2 … amn

(1) (2) (3) (4)

Опр. Назовем нижней ценой игры (максимином). Это максимальный гарантированный выигрыш игрока.

Опр. Назовем верхней ценой игры (минимаксом). Это минимальный гарантированный проигрыш игрока .

Опр. Стратегия, соответствующая максимину, называется максиминной стратегией.

Опр. Стратегия, соответствующая минимаксу, называется минимаксной стратегией.

Опр. Если , то называется чистой ценой игры, или ценой игры.

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

Опр. Минимаксные стратегии, соответствующие цене игры, являются оптимальными стратегиями, а их совокупность — оптимальным решением, или решением игры.

Опр. Говорят, что решение игры обладает устойчивостью, т.е. если один из игроков придерживается своей оптимальной стратегии, то для другого не может быть выгодным отклоняться от своей оптимальной стратегии (решение при этом является равновесием Нэша).

Опр. Пара чистых стратегий A_i и B_j дает оптимальное решение игры когда соответствующий ей элемент a_ij, является одновременно наибольшим в своем столбце и наименьшим в своей строке (седловая точка)

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

, .

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

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

или или .

Опр. Выигрыш, соответствующий оптимальному решению, называется ценой игры . Цена игры верно: ,где и — нижняя и верхняя цены игры. Справедлива следующая основная теорема теории игр — теорема Неймана.

Теор. Каждая конечная игра имеет по крайней мере одно оптимальное решение, возможно, среди смешанных стратегий. Пусть и — пара оптимальных стратегий.

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

Если игрок применяет смешанную стратегию против любой чистой стратегии игрока , то он получает средний выигрыш, или математическое ожидание выигрыша ,

Задача игрока — максимизировать свой гарантированный выигрыш, т.е. цену игры .

Это задача линейного программирования. Решая задачу , получаем оптимальную стратегию

, где .

. Задача игрока :

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

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