Платёжная матрица

Вj Аi	В1	В2	…	Вn
А1	а11	а12	…	а1n
А2	а21	а22	…	а2n
…	…	…	…	…
Аm	аm1	аm2	…	аmn

 

Рассмотрим игру m × n с матрицей и определим наилучшую среди стратегий A₁, A₂, …, А_m. Выбирая стратегию А_i игрок А должен рассчитывать, что игрок В ответит на нее той из стратегий B_j, для которой выигрыш для игрока А минимален (игрок В стремится «навредить» игроку А).

Обозначим через α наименьший выигрыш игрока А при выборе им стратегии А; для всех возможных стратегий игрока В (наименьшее число в i-й строке платежной матрицы).

Назовем α нижней ценой игры, или максимальным выигрышем (максимином). Это гарантированный выигрыш игрока А при любой стратегии игрока В. Следовательно,

 

. (5.1)

 

Стратегия, соответствующая максимину, называется максиминной стратегией. Игрок В заинтересован в том, чтобы уменьшить выигрыш игрока А; выбирая стратегию B_j, он учитывает максимально возможный при этом выигрыш для А. Назовем В верхней ценой игры, или минимаксным выигрышем (минимаксом). Это гарантированный проигрыш игрока В. Следовательно,

 

. (5.2)

 

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

Принцип, диктующий игрокам выбор наиболее «осторожных» минимаксной и максиминной стратегий, называется принципом минимакса. Этот принцип следует из разумного предположения, что каждый игрок стремится достичь цели, противоположной цели противника.

Если верхняя и нижняя цены игры совпадают, то общее значение верхней и нижней цены игры α = β = ν называется чистой ценой игры, или ценой игры.

Минимаксные стратегии, соответствующие цене игры, являются оптимальными стратегиями, а их совокупность – оптимальным решением, или решением игры. В этом случае игрок А получает максимальный гарантированный (не зависящий от поведения игрока В) выигрыш ν, а игрок В добивается минимального гарантированного (вне зависимости от поведения игрока А) проигрыша ν. Говорят, что решение игры обладает устойчивостью, т. е. если один из игроков придерживается своей оптимальной стратегии, то для другого не может быть выгодным отклоняться от своей оптимальной стратегии.

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

Обозначим А* и В* – пару чистых стратегий, на которых достигается решение игры в задаче с седловой точкой. Введем функцию выигрыша первого игрока на каждой паре стратегий: P(A_i B_j) = а_ij. Тогда из условия оптимальности в седловой точке выполняется двойное неравенство: P(A_i, B*) ≤ Р(А*, В*) ≤ P(A*, B_j), которое справедливо для всех . Действительно, выбор стратегии А* первым игроком при оптимальной стратегии В* второго игрока максимизирует минимальный возможный выигрыш: Р(А*, В*) ≥ P(A_i, B*), а выбор стратегии В* вторым игроком при оптимальной стратегии первого минимизирует максимальный проигрыш: Р(А*, В*) ≤ P(A*, B_j).

 

5.3. Решение игр в смешанных стратегиях. Приведение

матричной игры к задаче линейного программирования

 

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

Смешанной стратегией игрока А называется применение чистых стратегий A₁, A₂, …, А_m с вероятностями р₁, р₂, …, р_m, причем сумма вероятностей равна: . Смешанные стратегии игрока А записываются в виде . Аналогично смешанные стратегии игрока В обозначаются как , где сумма вероятностей появления стратегий .

Чистые стратегии можно считать частным случаем смешанных и задавать строкой, в которой 1 соответствует чистой стратегии. На основании принципа минимакса определяется оптимальное решение (или решение) игры: это пара оптимальных стратегий S*_A, S*_В, в общем случае смешанных, обладающих следующим свойством: если один из игроков придерживается своей оптимальной стратегии, то другому не может быть выгодно отступать от своей. Выигрыш, соответствующий оптимальному решению, называется ценой игры ν. Цена игры удовлетворяет неравенству α ≤ v ≤ β, где α и β – нижняя и верхняя цены игры.

Пусть и – пара оптимальных стратегий.

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

 

. (5.3)

 

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

 

5.4. Примеры решения задач систем массового обслуживания

Пример 1. Предприятие может выпускать три вида продукции (А₁, A₂ и А₃), получая при этом прибыль, зависящую от спроса, который может быть в одном из трёх состояний (В₁, В₂ и В₃). Дана матрица (табл. 5.2), ее элементы а_ij характеризуют прибыль, которую получит предприятие при выпуске i-й продукции с j-м состоянием спроса.

Таблица 5.2