Решение игры 2×2

Покажем на примере платёжной матрицы размерностью 2 × 2 реализацию алгоритма построения оптимального решения игровой задачи в смешанных стратегиях.

Пример 1. Найдем решение матричной игры

.

V_* = -1, V* = 1, V_* ≠V* - решения в чистых стратегиях не существует.

Припишем строкам платёжной матрицы неизвестные вероятности p₁ и p₂ (вероятности выбора стратегий A₁ и A₂) соответственно:

.

Поскольку p₁ + p₂ =1 → p₂ = 1 - p₁. Обозначим p₁ = p, тогда p₂ =1 - p. В результате получим:

Умножим столбец поэлементно на 1-й столбец и, сложив произведения, получим - математическое ожидание (среднее значение) выигрыша первого игрока A, при условии, что второй игрок B следует первой стратегии.

M₁(p) = 1∙p + (-1)(1-p) = 2p-1

Умножим столбец поэлементно на 2-й столбец и, сложив произведения, получим линейную зависимость - математическое ожидание (средний выигрыш) игрока A при применении игроком B второй стратегии

M₂(p) = (-1)∙p + 1(1-p) = -2p+1

Поскольку мы разыскиваем оптимальное решение первого игрока A, которое не должно зависеть от выбора стратегий вторым игроком B, приравняем полученные зависимости средних выигрышей:

2p-1 = -2p+1

Отсюда, p= ½, 1-p = ½, то есть оптимальная смешанная стратегия игрока A - это P = (½, ½) (каждую из стратегий надо применять с относительной частотой 1/2). Подставив в любую из зависимостей , i =1,2 найдем цену игры:

V=M_i(1/2) = 0.

Теперь припишем столбцам вероятности q₁ и q₂ соответственно, а поскольку:

q₁ + q₂ =1 →q₂ = 1 - q₁. Обозначим q₁ = q, тогда q₂ =1 - q. В результате получим:

.

Умножив строку (q, 1 -q) на 1-ю строку и сложив произведения, получим линейную зависимость - математическое ожидание:

W₁(q) = 1· q + (-1) ·(1-q) = 2q - 1

Это средний выигрыш игрока A (равный проигрышу игрока B) при применении игроком A 1-й стратегии.

Умножив строку (q, 1 -q) на 2-ю строку и сложив произведения, получим линейную зависимость - математическое ожидание:

W₂ = (-1) · q + 1· (1-q) = -2q + 1

Это средний выигрыш игрока A (равный проигрышу игрока B) при применении игроком A 2-й стратегии.

Приравняем полученные зависимости:

2q -1 = -2q + 1

Отсюда, q = ½, 1 - q = ½, то есть оптимальная смешанная стратегия игрока B - это Q = (1/2, 1/2) (каждую из стратегий надо применять с относительной частотой 1/2).

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

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

Не нашли, что искали? Воспользуйтесь поиском: