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

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

Для этой игры max min a_ij = -2 < 4 = min max a_ij. В результате, если иг-

i j j i

роки будут следовать предложенным выше правилам, то Игрок 1 выберет стратегию 1 и будет ожидать, что Игрок 2 выберет стра­тегию 2, при которой проигрыш равен -2, в то время как Игрок 2 изберет стратегию 3 и будет ожидать, что Игрок 1 выберет страте­гию 2 с выигрышем, равным 4. Однако если Игрок 2 выберет свою третью стратегию, то Игрок 1 поступит правильнее, выбирая вто­рую, а не первую стратегию. Аналогично, если Игрок 1 выберет первую стратегию, то Игроку 2 выгоднее выбрать вторую страте­гию, а не третью. По всей видимости, в играх такого типа принцип решения в чистых стратегиях оказывается непригодным.

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

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

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

Таблица 5.4

Платежная матрица

	y1	y2	.....	yn
x1	a11	a12	.....	a1n
x2	a21	a22	.....	a2n
.....	.....	.....	.....	.....
xn	am1	am2	.....	amn

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

,

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

x_i0, i=1, …, m, , (5.3)

y_j0, j=1, …, n, , (5.4)

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

^.

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

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

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

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

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

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

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

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

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

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