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

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

Игроки Л и В одновременно независимо друг от друга записывают число. ИгрокА записывает 1 или 2, а игрок В записывает 0 или 3. Если сумма записанных чисел нечетна, то столько денежных единиц игрок В платит игроку А, а если сумма четна, то столько игрокА платит игроку В.

Найти решение игры.

Решение. Обозначим стратегии игроков:

Aj — игрокА записал 1;

А₂ — игрокА записал 2;

Bj — игрок В записал 0;

В₂ — игрок В записал 3.

Матрица игры имеет вид.

Найдем, а и Р, для чего заполним таблицу.

Так как, а Ф р, то ясно, что седловая точка в этой игре отсутствует.

Из таблицы очевидно, что при максиминной стратегии А₂ игрокА может гарантировать себе выигрыш не меньше-2, а игрок В при минимаксной стратегии В] может гарантировать себе проигрыш не больше 1.

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

Отметим, что если каждый игрок будет придерживаться принципа минимакса (стратегии А₂ и В j), то каждый раз выигрыш игрока, А будет составлять -2. Это невыгодно игроку А, так как проигрыш игрока В, равный -2 (т.е. выигрыш 2), меньше того проигрыша, равного 1, который игрок В обеспечивает себе по принципу минимакса.

Игроку, А выгодно отказаться от своей максиминной стратегии, если В придерживается минимаксной, и применить стратегию А]. Тогда игрокА вместо выигрыша -2 получит выигрыш 1. Правда, тогда игроку В будет выгодно отказаться от стратегии B_v чтобы игрокА получил выигрыш -4, и т. д.

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

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

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

Секретность можно сохранить, если каждый раз выбирать стратегию случайным образом. Такое поведение тоже является стратегией и называется смешанной стратегией в отличие от рассмотренных ранее чистых стратегий А_ь А₂, …, А_т, B_v В₂, …, В_п. При этом противник лишен возможности узнать наперед о действиях другой стороны.

Итак, смешанная стратегия S_A игрока А — это применение чистых стратегий А_ь А₂, … А_т случайным образом с вероятностями соответственно р_ь р₂, … р_т, причем.

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

Аналогично смешанная стратегия игрока В имеет вид.

П.

где qj — вероятность применения игроком В стратегии В-, а? q, = 1.

j=i.

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

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

Эту функцию часто называют функцией потерь или платежной функцией.

Решением игры в этом случае является пара оптимальных смешанных стратегий S_A* = (р/,р₂ ,… р_т*) и S_B* = (q_a q₂,… q_n*), обладающих тем же свойством, что и для чистых стратегий: каждому игроку невыгодно отступать от своей оптимальной смешанной стратегии, если другой игрок придерживается своей оптимальной смешанной стратегии.

Ценой игры с в такой игре называется средний выигрыш игрока А при оптимальных смешанных стратегиях

Цена игры с удовлетворяет неравенству.

где а. и (3 — соответственно нижняя и верхняя цена игры.

Основной теоремой теории игр является теорема Неймана: каждая конечная игра имеет, по крайней мере, одно решение среди смешанных стратегий.

Рассмотрим игру с матрицей (a, j)₂x2 являющуюся простейшим случаем матричной игры.

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

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

Здесь вероятности р, р₂ соответствуют стратегиям А_ь А₂, вероятности q, q₂ стратегиям В_ь В₂.

Пусть матрица игры имеет вид.

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

Найти решение и цену игры для описанной ранее игры с записью чисел. Решение. Полученная выше матрица игры имеет вид Пример 9.5.

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

Таким образом, можно записать.

Полученный результат означает, что оптимальная смешанная стратегия игрока, А состоит в том, чтобы применять чистые стратегии А_г и Д₂ случайным образом с вероятностями соответственно 0,58 и 0,42, а игрока В — чистые стратегии В₁иВ₂ — с вероятностями 0,75 и 0,25.

Таким образом, ясно, что при правильной игре обоих игроков наиболее часто будет выбираться пара стратегий (А_1; Bj), т. е. чаще игрокА будет записывать единицу, чем 2, а игрок В — 0, чем 3.

Найдем цену игры с, т. е. средний выигрыш игрока, А при оптимальных смешанных стратегиях.

Это средний выигрыш игрока, А в одной игре. Он отрицателен, следовательно, эта игра для игрока, А невыгодна, а выгодна для игрока В. ?