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

Матричная игра двух игроков с нулевой суммой может рассматриваться как следующая абстрактная игра двух игроков.

Первый игрок имеет m стратегий i = 1,2,...,m, второй имеет n стратегий

j = 1,2,...,n. Каждой паре стратегий (i,j) поставлено в соответствие число а_ij, выражающее выигрыш игрока 1 за счёт игрока 2, если первый игрок примет свою i-ю стратегию, а 2 – свою j-ю стратегию.

Каждый из игроков делает один ход: игрок 1 выбирает свою i-ю стратегию (i = 1,2,...,m,), игрок 2 – свою j-ю стратегию (j = 1,2,...,n. ), после чего игрок 1 получает выигрыш а_ij за счёт игрока 2 (если а_ij< 0, то это значит, что игрок 1 платит игроку 2 сумму | а_ij | ). На этом игра заканчивается.

Если рассмотреть матрицу

то матричная игра с матрицей А сводится к выбору игроком 1 любой из своих стратегий – (это строки матрицы А), а игроком 2 - любого столбца, и получения игроком 1 (за счёт игрока 2) выигрыша а_ij.

Матрица А называется платежной матрицей игры, элементы которой а_ij есть выигрыши игрока 1.

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

,

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

Число называется нижней ценойигры (максимином) и показывает, какой минимальный выигрыш может гарантировать себе игрок 1, применяя свои чистые стратегии при всевозможных действиях игрока 2.

Игрок 2 при оптимальном своём поведении должен стремится по возможности за счёт своих стратегий максимально уменьшить выигрыш игрока 1. Поэтому для игрока 2 отыскивается наибольшее значение а_ij в каждом столбце j и затем из этих значений определяется минимальное:

Число называется верхней ценой игры (минимаксом) и показывает, какой максимальный выигрыш за счёт своих стратегий может себе гарантировать игрок 1.

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

Если , то говорят, что матричная игра имеет седловуюточку в чистых стратегиях и чистую цену игры

Седловая точка – это пара чистых стратегий (i_о,j_о) соответственно игроков 1 и 2, при которых достигается равенство .

Пара чистых стратегий (i_о,j_о) игроков 1 и 2, образующая седловую точку и седловой элемент , называется оптимальнымрешением игры. При этом i_о и j_о называются оптимальными чистыми стратегиямисоответственно игроков 1 и 2.

Пример 5 Найти цену игры, заданной платежной матрицей

Решение:

Очевидно, что нижняя цена игры , верхняя цена игры

.

Седловой точкой является пара (i_о = 3; j_о = 1),то есть оптимальными стратегиями для игрока 1 является i = 3 – третья строка матрицы А, для игрока 2 - первый столбец, j = 1. Цена игры равна =2

Заметим, что хотя выигрыш в ситуации (3;3) также равен 2 , но она не является седловой точкой, т.к. этот выигрыш не является максимальным среди выигрышей третьего столбца.