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

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

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

Определение. В антогонистической игре пара стратегий (А_i, В_j) называется равновесной или устойчивой, если ни одному из игроков не выгодно отходить от своей стратегии.

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

В рассмотренном §2.2 примере 1 минимаксные чистые стратегии А₄ и В₅ неустойчивы по отношению к информации о поведении противника; они не обладают свойством равновесия.

Действительно, предположим, что мы узнали, что противник придерживается стратегии В₃. Используя эту информацию, выберем стратегию А₁ и получим больший выигрыш, равный 7. Но если противник узнал, что наша стратегия А₁, он выберет стратегию В₄, сведя наш выигрыш к 4.

Таким образом, в  рассмотренном примере минимаксные  чистые стратегии оказались неустойчивы  по отношению к информации о поведении  другой стороны. Но это не всегда так.

Рассмотрим матричную  игру G (3х4), платежная матрица которой приведена на рис 2.3. 

 

Рис. 2.3. 

В этом примере нижняя цена игры равна верхней: a=b=9, т.е. игра имеет седловую точку.

Оказывается, что  в этом случае минимаксные стратегии  А₂ и В₂ будут устойчивыми по отношению к информации о поведении противника.

Действительно, пусть  игрок А узнал, что противник применяет стратегию В₂. Но и в этом случае игрок А будет по-прежнему придерживаться стратегии А₂. Потому что любое отступление от стратегии А₂ только уменьшит выигрыш. Равным образом, информация, полученная игроком, не заставит его отступить от своей стратегии В₂.

Пара стратегий  А₂ и В₂ обладает свойством устойчивости, а выигрыш (в рассматриваемом примере 9), достигаемый при этой паре стратегий, оказывается седловой точкой платежной матрицы.

Признак устойчивости пары стратегии - это равенство нижней и верхней цены игры.

Стратегии А_i и В_j (в рассматриваемом примере А₂, В₂), при котором выполняется равенство нижней и верхней цены игры, называются оптимальными чистыми стратегиями, а их совокупность - решением игры. Про саму игру в этом случае говорят, что она решается в чистых стратегиях.

Величина 

                                             (2.5.) 

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

Если n>0, то игра выгодна для игрока А, если n<0 - для игрока В; при n=0 игра справедлива, одинаково выгодная для обоих участников.

Однако наличие  седловой точки в игре - єто далеко не правило, скорее - исключение. Большинство матричных игр, не имеет седловой точки, а следовательно, не имеет оптимальных чистых стратегий. Впрочем, есть разновидность игр, которые всегда имеют седловую точку и, значит, решаются в чистых стратегиях. Это - игры с полной информацией.

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

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

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

Возникает вопрос: как  найти решение игры, платежная  матрица которой не имеет седловой точки? Применение минимаксного приципа каждым из игроков обеспечивает игроку А выигрыш не менее a, игроку - проигрыш не больше b. Учитывая что a<b, естественно для игрока А желание увеличить выигрыш, а для игрока В - уменьшить проигрыш. Поиск такого решения производит к необходимости применять смешанные стратегии: чередовать чистые стратегии с какими-то частотами.

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

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

Будем обозначать смешанные  стратегии игроков А и В соответственно

S_A=||p₁, p₂, ..., p_m||,

S_B=||q₁, q₂, ..., q_n||,

где p_i - вероятность применения игроком А чистой стратегии А_і;

q_j - вероятность применения игроком В чистой стратегии B_j;

В часном случае, когда все вероятности, кроме одной, равны нулю, а эта одна - единице, смешанная стратегия превращается в чистую.

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

Смешанные стратегии  в теории игр представляют собой  модель изменчивой, гибкой тактики, когда  ни один из игроков не знает, какую  чистую стратегию выберет противник  в данной партии. Если игрок А применяет смешанную стратегию S_A=||p₁, p₂, ..., p_m||, а игрок В смешанную стратегию S_B=||q₁, q₂, ..., q_n||, то средний выигрыш (математическое ожидание) игрока А определяется соотношением

                                                (2.6.)

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

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

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

2.4. Основные теоремы  матричных игр

Если игрок А выбирает смешанную стратегию S_A=||p₁, p₂, ..., p_m||, а игрок В смешанную стратегию S_B=||q₁, q₂, ..., q_n||,то средний выигрыш математическое ожидание выигрыша игрока А (проигрыша игрока В) опредится суммой

,

которая может рассматриваться в качестве характеристики выбранных S_А и S_B.

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

                               (2.7.)

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

                               (2.8.)

Весьма важным для  теории и практики является вопрос о том, связаны ли между собой  v_А и v_B. Ответ на него дает теорема о минимаксе.

Теорема о минимаксе. В конечной игре двух игроков (коалиций) с нулевой суммой (матричной игре) имеет место равенство

v_А=v_B, при a¹b.                                                           (2.9.)

Теорема о минимаксе  указывает на существование равновесия для случая v_А=v_B, при a¹b и, следовательно, существования оптимальных смешаных стратегий.

Поэтому другая формулировка теоремы о минимаксе, называемая основной теоремой матричных игр  определяется следующим образом.

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

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

a£n£b,                                                               (2.10.)

т.е. лежит между  нижней a и верхней b ценой игры.

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

Эта пара стратегий  образует в игре положение равновесия: один игрок хочет обратить выигрыш  в максимум, другой - в минимум, каждый “тянет” в свою сторону и, при  оптимальном поведение обоих, устанавливается равновесие и устойчивый выигрыш n.

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

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

Теорема об активных стратегиях. Если один из участников матричной игры G (mxn), придерживается своей оптимальной смешанной стратегии, то это обеспечивает ему максимальный средний выигрыш, равный цене игры n, независимо от того, какие действия предпринимает другой игрок, если только он не выходит за пределы своих активных стратегий (т.е. пользуется любой из них в чистом виде или смешивает их в любых пропорциях), причем число активных стратегий каждого игрока, входящих в их оптимальные смешанные стратегии, не превосходит , где =min(m, n).

Использование данной теоремы позволяет в частности, упрощать решение матричных игр  2xn и mx2. 
 
 

ТЕСТЫ 

1. В антогонистической игре пара стратегий (A_i, B_j) называется равновесной или устойчивой, если ни одному из игроков не выгодно отходить от своей стратегии.

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

3. Игра решается  в чистых стратегиях если платежная матрица имеет седловую точку.

4. Игра решается в чистых стратегиях, если нижняя цена платежной матрицы равна верхней.