Равновесие в смешанных стратегиях: как найти p и q

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

Что такое равновесие в смешанных стратегиях

В игре с чистыми стратегиями равновесие Нэша означает, что ни один игрок не хочет в одиночку сменить свой ход, если ходы остальных фиксированы. Но не в каждой игре такая точка есть. Классический пример, показывающий это, это игра между бьющим и вратарём: если вратарь всегда прыгает в ту же сторону, куда бьющий чаще всего бьёт, то бьющему выгодно переключиться на другую сторону, а вратарю тогда выгодно среагировать и прыгнуть за ним, и так по кругу без остановки. Значит, устойчивой пары чистых ходов нет.

Джон Нэш доказал, что если разрешить игрокам выбирать не конкретный ход, а вероятностное распределение по ходам, то есть смешанную стратегию, то равновесие найдётся всегда в любой конечной игре. В равновесии в смешанных стратегиях каждый игрок выбирает свою вероятность так, чтобы сопернику было безразлично, какую из своих чистых стратегий тот использует против этой вероятности. Именно из этого условия безразличия и выводятся конкретные числа p и q.

Игра «удар против вратаря»: матрица 2 на 2

Возьмём игру с нулевой суммой между бьющим пенальти и вратарём. У бьющего два хода: удар налево или направо. У вратаря тоже два хода: бросок налево или направо. Матрица игры задаётся четырьмя вероятностями гола, по одной на каждую комбинацию ходов: $a_{ЛЛ}$, $a_{ЛП}$, $a_{ПЛ}$, $a_{ПП}$, где первый индекс это сторона удара, а второй, сторона броска вратаря. Бьющий хочет максимизировать вероятность гола, вратарь, наоборот, минимизировать её, поэтому сумма выигрышей равна нулю.

Рассчитать для своей задачи

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

Условие безразличия и вывод формул p и q

Пусть бьющий бьёт налево с вероятностью p и направо с вероятностью 1 минус p. Пусть вратарь прыгает налево с вероятностью q и направо с вероятностью 1 минус q. Равновесие находится через условие безразличия: каждый игрок подбирает свою вероятность так, чтобы сопернику было всё равно, какую чистую стратегию использовать.

Вратарь выбирает q так, чтобы у бьющего совпал ожидаемый результат от удара налево и от удара направо:

$$q \cdot a_{ЛЛ} + (1 - q) \cdot a_{ЛП} = q \cdot a_{ПЛ} + (1 - q) \cdot a_{ПП}.$$

Раскрывая скобки и группируя q, получаем формулу равновесной вероятности вратаря:

$$q^* = \frac{a_{ПП} - a_{ЛП}}{a_{ЛЛ} - a_{ЛП} - a_{ПЛ} + a_{ПП}}.$$

Рассчитать для своей задачи

Симметрично бьющий выбирает p так, чтобы вратарю было всё равно, прыгать налево или направо:

$$p \cdot a_{ЛЛ} + (1 - p) \cdot a_{ПЛ} = p \cdot a_{ЛП} + (1 - p) \cdot a_{ПП},$$ $$p^* = \frac{a_{ПП} - a_{ПЛ}}{a_{ЛЛ} - a_{ЛП} - a_{ПЛ} + a_{ПП}}.$$

Обратите внимание на изящную логику: свою вероятность p игрок подбирает не ради собственной выгоды напрямую, а чтобы обезвредить соперника, лишить его возможности эксплуатировать предсказуемость. То же самое зеркально делает вратарь своим q. Именно поэтому равновесные вероятности каждого игрока определяются выигрышами именно ДРУГОГО игрока.

Почему смешивать выгоднее, чем играть чисто

Как только p и q найдены, легко посчитать цену игры, то есть равновесную вероятность гола:

$$v^* = p^* q^* a_{ЛЛ} + p^*(1 - q^*) a_{ЛП} + (1 - p^*) q^* a_{ПЛ} + (1 - p^*)(1 - q^*) a_{ПП}.$$

Ключевое свойство равновесия в том, что цена игры v* всегда не хуже, чем результат от любой чистой стратегии против рационального соперника. Если бьющий всегда бьёт налево, вратарь рационально выберет минимум из $a_{ЛЛ}$ и $a_{ЛП}$, и это число окажется меньше цены игры v*. То же самое с чистым ударом направо. Смешение защищает от эксплуатации: соперник не может подстроиться под вероятностный выбор так же легко, как под постоянный ход.

Пошаговый пример расчёта

Возьмём числа по умолчанию из калькулятора выше: вероятность гола при ударе налево и броске налево 58 процентов, при ударе налево и броске направо 92 процента, при ударе направо и броске налево 90 процентов, при ударе направо и броске направо 68 процентов. Такие цифры типичны для реальных данных: удар в сильную сторону чаще заходит, если вратарь прыгнул не туда, и реже, если угадал направление.

Считаем знаменатель формул:

$$a_{ЛЛ} - a_{ЛП} - a_{ПЛ} + a_{ПП} = 58 - 92 - 90 + 68 = -56.$$

Подставляем в формулу для q:

$$q^* = \frac{68 - 92}{-56} = \frac{-24}{-56} \approx 0{,}429.$$

И в формулу для p:

$$p^* = \frac{68 - 90}{-56} = \frac{-22}{-56} \approx 0{,}393.$$

То есть вратарю выгодно прыгать налево примерно в 43 процентах случаев, а бьющему бить налево примерно в 39 процентах случаев. Подставив эти значения в формулу цены игры, получаем v* примерно 77,4 процента, столько же даёт и проверка через удар направо: обе ветки сходятся к одному числу, что и подтверждает найденное равновесие. Если же посчитать результат чистого удара налево против лучшего ответа вратаря, получится только 58 процентов, а чистого удара направо, только 68 процентов: оба варианта хуже смешанной стратегии.

Частые ошибки

• Путают, чьими выигрышами определяется чья вероятность. Вероятность q вратаря находится из условия безразличия БЬЮЩЕГО, а не самого вратаря. Это частая логическая ошибка при первом знакомстве с темой.
• Забывают проверить знаменатель на ноль. Если $a_{ЛЛ} - a_{ЛП} - a_{ПЛ} + a_{ПП} = 0$, формулы не работают, нужно искать равновесие другим способом.
• Не проверяют, что p и q попали в отрезок от нуля до единицы. Если полученное значение выходит за пределы 0 и 1, значит в игре есть доминирующая чистая стратегия и смешанного внутреннего равновесия не существует.
• Считают цену игры только по одной ветке. Правильный расчёт даёт одинаковый результат и через удар налево, и через удар направо, разные числа означают ошибку в вычислениях.
• Путают вероятность гола с выигрышем вратаря. В игре с нулевой суммой выигрыш вратаря это минус вероятность гола, а не сама вероятность, знак важен при записи общей теоремы минимакса.

FAQ

Всегда ли существует равновесие в смешанных стратегиях? Да, для любой конечной игры хотя бы одно равновесие Нэша существует, если разрешить смешанные стратегии, это доказал Джон Нэш в 1950 году. Равновесие может быть в чистых стратегиях, в смешанных, или их сочетании для разных игроков.

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

Что означает цена игры v с практической точки зрения?* Это ожидаемый результат при оптимальной игре обеих сторон, то есть наилучшее, что может гарантировать себе бьющий против рационального вратаря, и наименьшее, что может гарантировать себе вратарь против рационального бьющего. Это же значение выступает решением игры в смысле теоремы минимакса фон Неймана.

Коротко

Равновесие в смешанных стратегиях возникает там, где у игры нет устойчивой пары чистых ходов, чистые стратегии по кругу проигрывают друг другу. Вероятности p и q находятся из условия безразличия: каждый игрок подбирает свою вероятность так, чтобы сопернику было всё равно, какой чистый ход выбрать. Цена игры v*, посчитанная в равновесии, всегда не хуже результата любой чистой стратегии против рационального соперника, поэтому смешивать выгоднее, чем быть предсказуемым.