Матричная игра

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

Рассмотрим следующий пример.

Пример . Два игрока А и В, не глядя друг на друга, кладут на стол по картонному кружку красного, зеленого или синего цветов, и расплачиваются друг с другом так, как показано в матрице игры

 

(напомним, что у этой 3 3-матрицы строки соответствуют стратегиям игрока А, а столбцы – стратегиям игрока В).

Считая, что эта 3 3 игра повторяется многократно, попробуем определить оптимальные стратегии каждого из игроков.

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

Запишем эти минимальные выигрыши в правом столбце таблицы:

 

A1	-2		-1	-2
A2
A3		-3		-3

 

 

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

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

 

	B1	B2	B3
A1	-2		-1	-2
A2
A3		-3		-3

 

 

 

Если игрок В будет придерживаться этой стратегии, то при любом поведении противника он проиграет не больше 1.

В рассматриваемой игре числа maxmin и minmax совпали:

= =1.

Выделенные стратегии A₂ и B₃ являются стратегиями игроков А и В,

в следующем смысле:

при многократном повторении игры отказ от выбранной стратегии любым из игроков уменьшает его шансы на выигрыш (увеличивает шансы на проигрыш).

Тем самым, ситуация оказывается равновесной.

Число называется нижней ценой игры.

Число называется верхней ценой игры.

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

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

Цена игры совпадает с элементом матрицы игры А, расположенным на пересечении -й строки и -го столбца – минимальным в своей строке и максимальным в своем столбце.

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

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

Замечание.Седловых точек в матричной игре может быть несколько, но все они имеют одно и то же значение.

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

.

Применение минимаксных стратегий для каждого из игроков обеспечивает выигрыш, не превышающий , и проигрыш, не меньший β. Для каждого игрока естественен вопрос увеличения выигрыша ( уменьшения проигрыша). Поиски такого решения состоят в том, что игроки 1) применяют не одну, а несколько стратегий, выбор которых осуществляется случайным образом; 2) “ смешивают ” свои стратегии, чередуя их случайным образом с какими-то вероятностями.

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

Обозначим смешанные стратегии игроков А и В через Р = { p₁, р₂, …,р_m} и Q = { q₁, q₂,…, q_n} соответственно, где p₁, р₂, …,р_m(образующие в сумме единицу) – вероятности применения игроком А стратегий А₁, А₂, …, А_m; q₁, q₂,…, q_n – вероятности применения игроком В стратегий В₁, В₂, …, В_n.

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

Применение оптимальной смешанной стратегии позволяет получить выигрыш, равный цене игры: