Реализация смешанной стратегии

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

Пусть, например, игрок 1 имеет две чистых стратегии, и смешанная стратегия задается вектором (1/2, 1/2), т.е. он выбирает свои чистые стратегии А₁ и А₂ с одинаковыми вероятностями. В этом случае перед началом каждой партии он может подбрасывать монету и при выпадении «решки» выбирать стратегию А₁, а при выпадении «орла» — стратегию А₂.

Если игрок 1 имеет три чистых стратегии и смешанная стратегия задается вектором (1/2, 1/3, 1/6), то в качестве механизма случайного выбора можно использовать урну, в которой находятся три белых, два красных и один черный шар. Перед началом партии игрок должен вынуть из урны шар, а затем положить его снова в урну. Если вынут белый шар, то он должен использовать стратегию А₁, если красный, то стратегию А₂, а если черный, то стратегию А₃.

В некоторых случаях возможно «смешивание» чистых стратегий. Тогда смешанную стратегию х = (х₁,…, х_m) можно реализовать в виде физической смеси чистых стратегий. Она задает доли чистых стратегий в этой смеси, т.е. x_i — доля стратегии А_i. в смеси стратегий. Пусть, например, инвестор располагает некоторой суммой и собирается вложить ее в акции различных компаний. В этом случае его чистой стратегией можно считать покупку акций данной компании, и число чистых стратегий равно числу компаний. Смешанная стратегия допускает такую реализацию: ее компонента x_i — доля общей суммы, на которую покупаются акции i-й компании.

3. Оптимальные стратегии, решение игры

Предположим, что в игре в орлянку игрок 1 использует смешанную стратегию = (1/2, 1/2), т.е. с равной частотой выбирает свои чистые стратегии. Тогда, какова бы ни была смешанная стратегия у = (р, 1 – р) игрока 2, где 0 ≤ р ≤ 1, выигрыш игрока 1 всегда будет равен нулю.

Действительно,

Н(х, y) = 1∙1/2∙ р + -1∙1/2∙(1 – р) + 1∙1/2∙ р + -1∙1/2∙(1 – р) = 0.

Если игрок 1 будет использовать стратегию х = (q, 1 – q), отличную от , то при правильной игре игрок 2 может выиграть. Чтобы убедиться в этом, подсчитаем значение выигрыша первого игрока:

Н(х, y) = 1∙qр + -1∙q(1 – р) + 1∙ (1 – q)р + -1∙ (1 – q)(1 – р) = (1 – 2q)(2р – 1).

Если взять , то .

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

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

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

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

Х = {х│ }, Y = {у│ }

и функцией выигрыша на множестве .

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

.

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

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

.

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

Пара смешанных стратегий ( , ) называется седловой точкой функции выигрыша Н : → R, если для всех , выполняется условие:

Н(х, ) ≤ Н( , ) ≤ Н( , y) (3.4)

В этом случае и называются оптимальными стратегиями, число ν = Н( , ) — ценой игры, а совокупность { , , ν} — решением игры.

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

.

Это соотношение — не что иное, как другая форма записи соотношения (2.3) с учетом того, что а_ij = Н(A_i, B_j).

Легко показать, что , т.е. нижняя цена игры не превосходит ее верхней цены. Если , то максиминная стратегия игрока 1 и минимаксная стратегия игрока 2 образуют седловую точку ( , ) и, следовательно, являются их оптимальными смешанными стратегиями. Оказывается, что верно и обратное: это неравенство становится равенством, если функция Н имеет седловую точку. Ранее этот факт (теорема 2.1) был установлен для игр с чистыми стратегиями.

Теорема 3.1. Равенство имеет место тогда и только тогда, когда функция Н имеет седловую точку ( , ). В этом случае

= Н( , ) = ν.

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

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

Таким образом, справедлива теорема, называемая основной теоремой матричных игр,·которая была доказана фон Нейманом в 1928 г.

Теорема 3.2. Всякая матричная игра с нулевой суммой имеет решение в смешанных стратегиях.

Итак, если матричная игра не имеет решения в чистых стратегиях (платежная матрица не имеет седловой точки), то следует рассмотреть ее расширение — игру в смешанных стратегиях. Решение этой игры всегда существует. Его образуют оптимальные смешанные стратегии игроков, которые соответствуют принципу гарантированного результата (максимина). Отклонение от этих стратегий не выгодно ни одному из игроков: они образуют ситуацию равновесия. Множество ситуаций равновесия состоит из всевозможных пар ( , ), где — максиминная стратегия игрока 1, а — минимаксная стратегия игрока 2. Выигрыши во всех ситуациях равновесия совпадают и равны значению игры.