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

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

Для этой игры max min a_ij = -22000 < 44000 = min max a_ij. По всей видимости, в играх такого типа принцип решения в чистых стратегиях оказывается непригодным.

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

Мы будем предполагать использование игроками их смешанных стратегий независимым, так что вероятность, с которой Игрок 1 выбирает i -тую стратегию, а Игрок 2 - j -тую, равна x_i y_j. В этом случае платеж равен a_ij.

Для случая игры со смешанными стратегиями платежная матрица принимает следующий вид (табл. 7.4).

Таблица 7.4 – Матрица игры

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

,

где переменные х и у удовлетворяют соотношениям

x_i ³ 0, i =1, …, m, , (7.3)

y_j ³ 0, j =1, …, n, , (7.4)

а второй игрок выбирает стратегию, обеспечивающую

Эти величины определяются соответственно как среднеожидаемые максиминные и среднеожидаемые минимаксные платежи.

Если х^* _i, и у^* _j — оптимальные решения для обоих игроков, каждому элементу платежной матрицы a_ij соответствует вероятность . Следовательно, оптимальное ожидаемое значение игры .

Как и в случае чистых стратегий, выполняется соотношение:

минимаксный ожидаемый проигрыш ³ максиминный ожидаемый выигрыш.

Когда х_i и y_j соответствуют оптимальным решениям, выполняется строгое равенство, и результирующее значение равно ожидаемому (оп­тимальному) значению игры. Это утверждение следует из теоремы о минимаксе и приведено здесь без доказательства.

Справедлива следующая основная теорема теории матричных игр с нулевой суммой (теорема фон Неймана).

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

Теорема о минимаксе утверждает, что сформулированные задачи для Игрока 1 и Игрока 2 всегда имеют решение для любой матрицы выигрышей.

Также как и для вполне определенных игр, стратегия х^* Игрока 1 называется максиминной, стратегия y^* Игрока 2 – минимаксной, значение v –ценой игры.

В случае, когда v =0, игра называется справедливой.