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

 

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

Первый игрок имеет  стратегий  = 1,2,..., , второй имеет n стратегий  = 1,2,..., n. Каждой паре стратегий (,) поставлено в соответствие число а_, выражающее выигрыш игрока 1 за счёт игрока 2, если первый игрок примет свою - ю стратегию, а 2  свою  -ю стратегию.

Каждый из игроков делает один ход: игрок 1 выбирает свою  -ю стратегию (= ), 2  свою  -ю стратегию ( = ), после чего игрок 1 получает выигрыш а_ за счёт игрока 2 (если а_ 0, то это значит, что игрок 1 платит второму сумму  а_ ). На этом игра заканчивается.

Каждая стратегия игрока = ;  = часто называется чистой стратегией.

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

 

А =

 

 

то проведение каждой партии матричной игры с матрицей А сводится к выбору игроком 1  -й строки, а игроком 2  -го столбца и получения игроком 1 (за счёт игрока 2) выигрыша а_.

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

а_ ( = )

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

а_ = = (1).

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

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

а_

т.е. определяется  выигрыш игрока 1, при условии, что игрок 2 применит свою  -ю чистую стратегию, затем игрок 2 отыскивает такую свою  = ₁ стратегию, при которой игрок 1 получит n выигрыш, т.е. находит

_ = = (2).

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

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

Определение. Если в игре с матрицей А = , то говорят, что эта игра имеет седловую точку в чистых стратегиях и чистую цену игры

u = = .

Седловая точка  это пара чистых стратегий (_о,_о) соответственно игроков 1 и 2, при которых достигается равенство = . В это понятие вложен следующий смысл: если один из игроков придерживается стратегии, соответствующей седловой точке, то другой игрок не сможет поступить лучше, чем придерживаться стратегии, соответствующей седловой точке. Математически это можно записать и иначе:

где ,   любые чистые стратегии соответственно игроков 1 и 2; (_о,_о)  стратегии, образующие седловую точку.

Таким образом, исходя из (3), седловой элемент является минимальным в _о-й строке и максимальным в _о-м столбце в матрице А. Отыскание седловой точки матрицы А происходит следующим образом: в матрице А последовательно в каждой строке находят минимальный элемент и проверяют, является ли этот элемент максимальным в своём столбце. Если да, то он и есть седловой элемент, а пара стратегий, ему соответствующая, образует седловую точку. Пара чистых стратегий (_о,_о) игроков 1 и 2, образующая седловую точку и седловой элемент , называется решением игры. При этом _о и _о называются оптимальными чистыми стратегиями соответственно игроков 1 и 2.

 

Пример 1

Седловой точкой является пара (_о = 3; _о = 1), при которой u = = = 2.

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

Пример 2

 

 

Из анализа матрицы выигрышей видно, что , т.е. данная матрица не имеет седловой точки. Если игрок 1 выбирает свою чистую максиминную стратегию  = 2, то игрок 2, выбрав свою минимаксную  = 2, проиграет только 20. В этом случае игроку 1 выгодно выбрать стратегию  = 1, т.е. отклониться от своей чистой максиминной стратегии и выиграть 30. Тогда игроку 2 будет выгодно выбрать стратегию  = 1, т.е. отклониться от своей чистой минимаксной стратегии и проиграть 10. В свою очередь игрок 1 должен выбрать свою 2-ю стратегию, чтобы выиграть 40, а игрок 2 ответит выбором 2-й стратегии и т.д.