Смешанные стратегии

Большинство матричных игр не имеет седловых точек. В такой ситуации игроку важно, чтобы противник не угадал, какую стратегию он будет использо­вать. Для осуществления этого плана следует пользовать­ся смешанной страте­гией. Смешанная стратегия представляет собой схе­му случайного выбора чис­той стратегии. Математически ее можно пред­ставить как вероятностное рас­пре­деление на множестве чистых стра­тегий игрока.

Def. Пусть R – платежная матрица игры размера m×n.Тогда смешанная стратегия игрока А представляет собой вектор,удовлетворяющий условиям

,

а смешанная стратегия для игрока Б есть вектор,такой, что

.

Данное определение имеет следующий смысл: когда игрок Аис­пользует смешанную стратегиюp, он применяет случайный способ вы­бо­ра стратегии, при котором чистая стратегиявыбирается с вероят­нос­тью, где. Аналогично игрокБ, используя смешанную стра­тегиюqприменяет случайный способ выбора стратегии, при кото­ром чистая стратегиявыбирается с ве­роятностью, гдеЭти две схемы рандомизации будем предпола­гать независимыми, так что вероятность того, что в партии игрокАвыберет стратегию, а игрокБ -, равна. Так как платеж в этом случае равен, мате­ма­ти­чес­кое ожидание результата игры (средний платеж игрокаА при розыг­ры­ше большого числа партий) выражается формулой

,

или в матричных обозначениях

,

где значок tозначает транспонирование.

Для смешанных стратегий седловая точка определяется как пара стратегий удовлетворяющих условию

для любых стратегий , гдеPиQ- мно­жества допустимых сме­шан­ных стратегий игроковАиБ, соответственно.

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

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

Величина Vобычно называетсяценойилизначением игры.

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

Таким образом, стратегия оптимальна для игрокаА,если

,

и стратегия оптимальна для игрока Б, если

.

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

Методы определения оптимальных стратегий

1. Простейший метод состоит в нахождении седловой точки для чис­тых стратегий. Если такая седловая точка существует, то две чистые стратегии, которые к ней приводят, являются оптимальными.

2. Для уменьшения размерности игры используется доми­ни­ро­ва­ние строк и столбцов.

Говорят, что k-я строка матрицыRдоминируетi-ю строку (т.е. од­на чистая стратегия доминирует другую), если

при всех j.

Аналогично l-й столбец доминируетj-й столбец, если

при всех i.

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

Пример

Рассмотрим игру с матрицей

.

Вторая строка доминирует третью. Исключение третьей строки приводит к матрице

.

Первый столбец в этой урезанной матрице доминирует второй. Исключе­ние второго столбца приводит к матрице

.

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

3. Существуют простые процедуры получения решения игр ма­лой раз­мер­­ности. Рассмотрим один из них на примере игры 22.

Пример

Рассмотрим игру с платежной матрицей

.

Эта игра не имеет решения в чистых стратегиях, так как

.

Будем искать решение этой игры в смешанных стратегиях.

Пусть pиq– вероятности выбора игрокамиАиБ, соответст­вен­но, первой чистой стратегии. Тогдаи(1-q)– вероятности выбора ими вто­рой чистой стратегии.

Математическое ожидание результата .

Для определения оптимальной стратегии игрока Анужно найти

.

Сначала при фиксированном значении pнеобходимо найти макси­мум поq, а для этого разобьем область измененияpна два интервала[0,0.4]и[0.4,1]знакопостоянства выражения(5p-2)и решим эту задачу на каждом из этих интервалов.

;

Итак, мы определили, что оптимальной для игрока Абудет сме­шан­ная стратегия, при которой первая чистая стратегия выбирается им с вероятностью (или частотой) 0,4, а вторая - с вероятностью 0,6. Цена игры - 3,2 .

Аналогично задача решается и для игрока Б.

С ростом размерности матрицы платежей сложность задачи замет­но воз­растает.

4. Для решения больших игр предложено несколько методов. Наи­бо­лее распространенным является определение опти­маль­ной стра­те­гии мето­да­ми линейного программирования.

Теорема.Каждой матричной игре mn с платежной матрицей R эквивалентна следующая пара двойственных задач линейного програм­мирования:

минимизировать целевую функцию при условиях

(1)

максимизировать целевую функцию при условиях

(2)

Составляющие оптимальных смешанных стратегий игры и цена игры V связаны с компонентами оптимальных планов задачи ЛП со­от­но­шениями

(3)