1. Доминирование

Любая матричная игра может быть решена путем решения системы линейных неравенств

и линейных уравнений

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

О п р е д е л е н и е 9. Стратегия Х₁ игрока Ι строго доминирует его стратегию Х₂, если

H (X₁, j) > H (X₂, j), j = 1, 2, …, n (18)

(стратегия X₂ называется строго доминируемой).

О п р е д е л е н и е 10. Стратегия Y₁ игрока ΙΙ строго доминирует его стратегию Y₂, если

-H (i, Y₁) > -H (i, Y₂), i = 1, 2, …, m,

или

H (i, Y₁) < H (i, Y₂), i = 1, 2, …, m, (19)

(стратегия Y₂ называется строго доминируемой).

Когда неравенства (18) и (19) для некоторых чистых стратегий игрока Ι (игрока ΙΙ) не являются строгими, стратегия X₁ (Y₁) доминирует стратегию X₂ (Y₂).

В частности, чистая стратегия i₁ игрока Ι строго доминирует его чистую стратегию i₂, если для любого j B

h > h _,

а чистая стратегия j₁ игрока ΙΙ строго доминирует его чистую стратегию j₂, если для любого i A

h < h .

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

Теорема 6. Пусть (Х^*, Y^*) – седловая точка mх n – игры Н, а (Х'^*, Y'^*) – седловая точка m' n' – игры Н' (m' < m, n' < n), полученной из Н в результате исключения доминируемых стратегий. Тогда x = x , y = y для всех недоминируемых i и j x = 0, y = 0 для всех доминируемых i и j; v(Н) = v(Н').

П р и м е р 6

Рассмотрим игру

H = .

Решение.

H = ~ H₁ = ~H₂ = = H'

Первая строка строго доминирует вторую и третью, так как все ее элементы соответственно больше элементов второй и третьей строк. Поэтому для игрока Ι стратегии {h_2j, j = 1, 2, 3, 4, 5} и {h_3j, j = 1, 2, 3, 4, 5} ((5 4 3 4 6) и (4 3 2 3 4)) менее выгодны, чем {h_1j, j = 1, 2, 3, 4, 5} ((8 6 4 7 7)), и могут быть исключены. В результате получим матрицу Н₁, в которой первый, четвертый и пятый столбцы строго доминируются вторым. Так как столбцы характеризуют стратегии игрока ΙΙ, стремящегося уменьшить выигрыш игрока Ι (и тем самым увеличить свой выигрыш), эти стратегии заведомо невыгодны для игрока ΙΙ. После их исключения получаем матрицу Н₂, в которой нет доминируемых стратегий и, следовательно, Н' = Н₂. Игра Н' эквивалентна первоначальной игре Н, т. е. оптимальные стратегии в игре Н имеют вид

X^* = (x , 0, 0, x ) = (x , 0, 0, x ) и Y^* = (0, y , y , 0, 0) = (0, y , y , 0, 0).

В результате вместо 4 5-игры Н мы можем решать 2 2-игру Н'.

Теперь приведем общую схему решения матричной игры:

1) исключить в платежной матрице доминируемые стратегии;

2) упрощенную матрицу проверить на наличие в ней седловых точек (в чистых стратегиях), что позволяет сразу же определить решение (оптимальные стратегии и значение игры) в чистых стратегиях;

3) если седловых точек нет (в чистых стратегиях), то перейти к определению решения в смешанных стратегиях.

В дальнейшем нас будет интересовать лишь третий пункт. При этом в процессе нахождения решений игр будет использоваться теорема 7.

Теорема 7. Если один из игроков применяет свою оптимальную смешанную стратегию, то его выигрыш равен значению игры v вне зависимости от того, с какими вероятностями будет применять второй игрок стратегии, вошедшие в оптимальную (в том числе и чистые стратегии).