♟️ Теория игр

Доминирование стратегий

англ. Strategy dominance

Сравнение строк и столбцов платёжной матрицы: стратегия, не лучшая ни при одном ответе соперника, вычёркивается до решения игры.

Строка $i$ доминирует строку $k$ , если $a_{ij} \geq a_{k j}$ при всех столбцах $j$ и хотя бы одно неравенство строгое: что бы ни сыграл B, строка $i$ не хуже. Строку $k$ тогда называют доминируемой и вычёркивают — она не входит ни в один разумный план. Для игрока B, который минимизирует, доминирование столбцов устроено наоборот: столбец $j^{'}$ лучше $j^{''}$ , если его элементы не больше. Процедуру повторяют, сжимая матрицу до маленького ядра.

Пример: в $A = 423232312$ первая строка покомпонентно не хуже третьей: $4 \geq 3$ , $2 \geq 2$ , $3 \geq 2$ — вычёркиваем третью. Дальше сжимаем столбцы с позиции B: третий столбец $(3, 1)$ покомпонентно не больше первого $(4, 2)$ , поэтому для B первый доминируем — вычёркиваем его. Остаётся ядро $2 \times 2$ , которое решается смешиванием. Доминирование — первый шаг ручного решения: определение и примеры — в уроке игры с чистыми стратегиями, откуда берутся матрицы — во введении в теорию игр.

a_{ij} \geq a_{k j} \forall j \Rightarrow строка k доминируема и удаляется

критерий доминирования по строкам; для столбцов неравенство разворачивается, так как игрок B минимизирует выплату

Частые вопросы

Можно ли вычёркивать стратегии при слабом доминировании?

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

Как доминирование связано с дилеммой заключённого?

Напрямую: там стратегия «сознаться» строго доминирует «молчать» — она даёт больше и при молчании партнёра ( $0 > - 1$ ), и при его признании ( $- 8 > - 10$ ). Доминирующие стратегии выбирают оба игрока, поэтому исход «сознаются оба» получается без всяких равновесных вычислений. Дилемма и показывает опасность попарного доминирования: устойчивый исход оказывается хуже для всех.