Если из платежной матрицы исключить строки и столбцы: Доминирование и дублирование стратегий

Содержание

Доминирование и дублирование стратегий

Рассмотрим несколько методов упрощения платёжных матриц.

Первый метод, используемый для уменьшения размерности матрицы, основан на одном из важнейших понятий в теории игр — понятии доминирования стратегий (мажорирование стратегий).

Если i-я строка поэлементно не меньше (≥) j-й строки, то говорят, что i-я строка доминирует над j-й строкой. Поэтому игрок A не использует j-ю стратегию, так как его выигрыш при i-й стратегии не меньше, чем при j-й стратегии, вне зависимости от того, как играет игрок B.

Аналогично, если i-й столбец поэлементно не меньше (≥) j-го столбца, то говорят, что j-й столбец доминирует над i-м столбцом. Поэтому игрок B не использует i-ю стратегию, так как его проигрыш (равный выигрышу игрока A) при j-й стратегии не больше (≤), чем при i-й стратегии, вне зависимости от того, как играет игрок A. Стратегии, над которыми доминируют другие стратегии, надо отбросить и приписать им нулевые вероятности.

На цене игры это никак не скажется. Зато размер матрицы игры понизится. С этого и нужно начинать решение игры.

Частный случай доминирования является дублирование стратегий.

Если платёжная матрица игры содержит несколько одинаковых строк (столбцов), то из них оставляем только одну строку, а остальные строки (столбцы) отбрасываем. Отброшенным стратегиям припишем нулевые вероятности.

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

Пусть I — игра, в матрице которой i -я стратегия первого игрока доминирует над i +1, а G — игра, матрица которой получена из матрицы I исключением i + 1 стратегии (строки). Тогда:

цена игры I равна цене игры G;
оптимальная смешенная стратегия Q^*= (q₁^*,q₂^*,…,q_n^*) второго игрока в игре G является также его оптимальной смешанной стратегией в игре I;
если P^*= (p₁^*,p₂^*,…,p_i^*, p*_i+2,…, p_m^*) оптимальная смешенная стратегия первого игрока в игре G, то его смешенная стратегия P^*= (p₁^*,p₂^*,…,p_i^*, p*_i+2,…, p_m^*) является оптимальной в игре I.

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

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

Пример 1. Платёжная матрица игры задана в виде: .

Решение
Видео решение

Упростим игру (упростим платёжную матрицу).

1-я и 4-я строки равны. Поэтому отбросим 4-ю строку. Вероятность p₄= 0. Получим матрицу:

2-я строка доминирует над 3-й строкой (6 > 3, 5 > 4, 8 = 8, 7 > 6). Поэтому отбросим 3-ю строку. Вероятность p₃= 0. Получим матрицу:

2-й столбец доминирует над 3-м столбцом (9 = 9, 5 < 8). Поэтому отбросим 3-й столбец. Вероятность q₃= 0. Получим матрицу:

Строки между собой не сравнимы (8 > 6, 4 < 7), столбцы тоже (8 < 9, 6 > 5; 8 > 4, 6 < 7; 9 > 4, 5 < 7). Дальнейшее упрощение невозможно. Мы свели игру 4×4 к игре 2×3.

Пример 2. Матрица игры

Упростить игру.

Введём вероятностные векторы: P = (p₁, p₂, p₃, p₄), Q = (q_1,q_2,q₃, q₄).

1 — ый шаг: A₁доминирует A₂: вычёркиваем 2- ю строку, в результате получаем р₂= 0 и платёжную матрицу:

2-ой шаг: A₃доминирует A₁: вычёркиваем 1- ю строку, в результате получаем р₁= 0 и платёжную матрицу:

3-ий шаг: B₂ доминирует B₁ вычёркиваем 1- ый столбец, в результате получаем q₁= 0 и платёжную матрицу:

4-ый шаг: B₄

доминирует B₃ вычёркиваем 2 — ый столбец, в результате получаем q₃= 0 и платёжную матрицу:

5 -ый шаг: A₃доминирует A₄: вычёркиваем 4 — ю строку, в результате получаем p₄= 0 и платёжную матрицу:

6 — ой шаг: B₂ доминирует B₄ вычёркиваем 4 — ый столбец, в результате получаем q₄= 0 и платёжную матрицу:

В результате упрощения платёжной матрицы выяснилось, что игра имеете единственное оптимальное решение в чистых стратегиях, о чём говорят векторы вероятностей P и Q:

P = (0, 0, p₃, 0), Q = (0_,q_2,0, 0).

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

3, а игрок B выбирает стратегию B₂.

Тот же результат получается, если использовать максиминную стратегию.

V_* = max min a_ij = max{4,3,6,3}= 6
V^* = min max a_ij= min{8,6,10,8}= 6
V_* = V* = 6, элемент матрицы а₃₂ является седловой точкой.
Замечание. Если игра m×n имеет седловую точку, то после упрощений платёжной матрицы мы всегда получим игру 1×1.

Продолжим рассмотрение методов упрощения платёжной матрицы.
Другой метод преобразования матрицы выигрышей (платёжной матрицы) основывается на доказываемой в теории игр теореме об аффинных преобразованиях.

Теорема об аффинных преобразованиях. Аффинное преобразование (преобразование подобия и сдвига) платежной матрицы, т.е. преобразование всех элементов матрицы

A вида: a’_ij = k*a_ij+b, где k ≠ 0 и b — любая константа, не изменяет решение игры. Кроме того, цена преобразованной игры V’ может быть получена из цены первоначальной игры V по тому же правилу: V' = kV + b
Это означает, в частности, что для задания игры в принципе безразлично, в каких единицах измеряется выигрыш, например, в рублях или другой валюте.
Прибавление (вычитание) некоторой фиксированной суммы bк каждому из элементов a_ij платёжной матрицы A изменит на такую же сумму выигрыш (проигрыш) каждого из игроков, не меняя при этом решения игры. Это свойство может быть использовано для преобразования исходной матрицы игры к более удобному виду. Так, например, если элементы платежной матрицы представляют собой дроби с общим знаменателем, то каждый элемент матрицы a_ij можно умножить на некоторую константу, в результате чего элементы преобразованной матрицы будут представлять собой целые числа; если же большинство клеток матрицы заполнены одинаковыми элементами, то их можно вычесть из каждого элемента матрицы для получения нулей, которым будут равны соответствующие элементы матрицы.

Кроме того, цену игры V’ всегда можно сделать положительной, т.е. V’ > 0, чем мы воспользуемся при сведении игровой задачи к задаче линейного программирования.

В завершении данного параграфа приведём формулу пересчёта от преобразованной цены игры V’ к исходной V:

Пример 3. Задана платёжная матрица игры:

A =

Необходимо упростить матрицу игры.

1 — ый шаг: умножим каждый из элементов матрицы A на k = 0.01, получим:

2 — ой шаг: к каждому элементу матрицы A’ прибавим b = 4, получим матрицу:

Таким образом, мы получили платёжную матрицу с положительными элементами и небольшими по абсолютной величине. Работа с такой матрицей проще, чем с исходной матрицей. Элементы матрицы A» получены преобразованием:

Перейти к онлайн решению своей задачи

Пример 4. Платёжная матрица игры задана в виде. Упростить игру (упростить платёжную матрицу) найти оптимальное решение.

Упрощение платёжной матрицы

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

Дублирующими называются стратегии, которым соответствуют одинаковые значения элементов в матрице, т.е. матрица содержит одинаковые строки (столбцы). Если все элементы i-й строки матрицы меньше соответствующих элементов k-й строки, то i-я стратегия для игрока А называется доминирующей. Если же элемент r-го столбца матрицы больше соответствующих элементов j-го столбца, то для игрока В стратегия В_r – доминирующая. Например, в матрице платежей C= для игрока В заведомо невыгодна четвёртая стратегия, так как все значения элементов 4-го столбца c_i₄ превышают соответствующие значения первого и второго столбца. Четвёртый столбец матрицы можно исключить (игрок В никогда не воспользуется этой стратегией).

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

Рассмотрим матрицу С, разбитую на четыре подматрицы, для которых выполняется условие равенства сумм элементов по строкам и столбцам:

C=.

Объединяя стратегии А₁, А₂, и А₃, А₄ и А₅, В₁ и В₂, В₃ и В₄, приводим матрицу к виду:

Полученная матрица содержит седловую точку. Поэтому решение первоначальной игры, заданной матрицей С, таково: Р*=(1/3; 1/3; 1/3; 0; 0), Q*=(1/2; 1/2; 0; 0). Цена игры равна единице. В результате упрощения игры решение её стало очевидным: оптимальной для игрока А является комбинация стратегий А₁, А₂ и А₃, а для игрока В комбинация стратегий В₁ и В₂. Вероятности применения стратегий А₁, А₂ и А₃ равны между собой, сумма их равна 1, поэтому Р*=(1/3; 1/3; 1/3; 0; 0). Аналогично, оптимальная стратегия игрока В имеет вид Q*=(1/2; 1/2; 0; 0).

Таким образом, при решении игры mxn следует:

а) проверить, содержит ли матрица седловую точку;

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

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

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

Эти условия зависят не от сознательных действий другого игрока, а от объективной действительности, которую принято называть природой. Такие игры называются играми с природой. Решения в этих играх получают с помощью теории стратегических решений. Человек А в играх с природой старается действовать осмотрительно, используя например, минимаксную стратегию, позволяющую получить наименьший проигрыш. Второй игрок В (природа) действует совершенно случайно, возможные стратегии определяются как её состояния (например, условия погоды в данном районе, спрос на определённую продукцию, объём перевозок, некоторое сочетание производственных факторов и т.д.). В некоторых задачах для состояний природы может быть задано распределение вероятностей, в других – и оно неизвестно.

Условия игры, как и в рассмотренных выше задачах теории игр, задаются в виде матрицы:

C=.

Элемент с_ij равен выигрышу игрока А, если он использует стратегию А_i, а состояние природы – В_j.

В ряде случаев при решении игр рассматривают матрицу рисков R. Элемент матрицы r_ij представляет собой разность между выигрышем, который получил бы игрок А, если бы он знал состояние природы B_j, и выигрышем, который он получит в тех же условиях, применяя стратегию A_i, т.е. r_ij=_j— с_ij, где _.

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

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

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

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

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

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

, где 0 1.

Значение  выбирают на основании субъективных соображений. Чем больше желание подстраховаться в данной ситуации, тем ближе к нулю следует брать значение . Применим принцип Гурвица к решению примера:

Таблица 9.4

Применение принципа Гурвица к игре из примера 9. 1

A_i	B_j				min выигрыш	max выигрыш	Расчётный выигрыш при
	B₁	B₂	B₃	B₄	А	А	=0,4	=0,2
	35	35	3	10	3	35	15,8	9,4
	24	1	6	90	10	90	36,6	18,2
	40	60	10	15	1	60	42	20

По принципу обобщённого максимина необходимо стороне А использовать стратегию А₃.

Кроме перечисленных принципов (минимакса, обобщённого максимина и минимальных потерь), используют принцип Байеса-Лапласа, который отступает от условий полной неопределённости. При этом предполагается, что возможным состояниям природы В₁, В₂, …, B_n можно приписать определённую вероятность, соответственно равную q₁, q₂,…, q_n. Этот принцип используется, если есть возможность определить вероятность возникновения отдельных состояний природы (например, статистическая обработка метеосводок), если нет – применяют принцип равновероятности (принцип недостаточного основания Лапласа). Он заключается в том, что всем возможным состояниям природы приписывается одинаковая вероятность, и решение игры ищется при таких условиях. Однако во всех случаях нельзя утверждать, что принятое решение оптимальное, оптимальным оно является только относительно принятого распределения вероятностей состояний природы.

В заключение можно отметить, что если мы имеем дело с многократно повторяющимися состояниями и многократно повторяющимися решениями, то наиболее целесообразно применять принцип Байеса- Лапласа или Гурвица. В случае разового решения применяют обычный принцип минимакса или минимальных потерь (Сэвиджа).

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

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

Вопросы для самопроверки

Предмет изучения теории игр.

Виды причин неопределённости результата игры.

Основные понятия теории игр: игра, правила, ход, стратегия, оптимальная стратегия.

Виды игр.

Общая постановка игры двух лиц с нулевой суммой.

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

Общая постановка задачи теории игр, её математическая модель, формулы для получения оптимальных вероятностей использования стратегий.

Основная теорема теории игр.

Геометрический способ решения задач теории игр.

Метод Брауна приближённого решения задач теории игр.

Сведение игры к задаче линейного программирования.

Способы упрощения платёжной матрицы игры.

Понятие игр с природой.

Виды критериев, используемых при решении игр с природой.

Применение теории игр в экономических исследованиях.

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

11.3: Сокращение по доминированию — Mathematics LibreTexts

Последнее обновление
Сохранить как PDF

Идентификатор страницы: 37941

Рупиндер Сехон и Роберта Блум
Колледж Де Анза

Иногда игровую матрицу \(m \times n\) можно уменьшить до матрицы \(2 \times 2\), удалив определенные строки и столбцы. Строка может быть удалена, если существует другая строка, которая даст такой же или больший выигрыш. Точно так же столбец может быть удален, если есть другой столбец, который даст выигрыш равного или лучшего значения для игрока столбца. Говорят, что строка или столбец, которые обеспечивают лучший выигрыш для соответствующего игрока, доминируют строка или столбец с меньшим выигрышем.

Пример \(\PageIndex{1}\)

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

\[G=\left[\begin{array}{ccc}
-2 & 6 & 4 \\
-1 & -2 & -3 \\
1 & 2 & -2
\end{массив} \right] \nonumber \]

Решение

Сначала мы ищем седловую точку и определяем, что ее нет. Затем мы пытаемся уменьшить матрицу до матрицы \(2 \times 2\), удалив доминирующую строку.

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

\[\left [\begin{array}{ccc}
-2 & 6 & 4 \\
1 & 2 & -2
\end{array}\right] \nonumber \]

Теперь попробуем удалить столбец. Помните, что игровая матрица представляет выигрыши для игрока строки, а не игрока столбца; следовательно, чем больше число в столбце, тем меньше выигрыш для игрока столбца.

Игрок столбца никогда не будет воспроизводить столбец 2, потому что он доминирует как столбец 1, так и столбец 3. Поэтому мы исключаем столбец 2 и получаем модифицированную матрицу M, приведенную ниже.

\[\mathrm{M}=\left[\begin{array}{cc}
-2 & 4 \\
1 & -2
\end{array}\right] \nonumber \]

Найти оптимальную стратегию как для игрока-строки, так и для игрока-столбца, мы используем метод, изученный в разделе 11.2.

Пусть стратегия игрока строки будет \(\mathrm{R}=\left[\begin{array}{ll}
\mathrm{r} & 1-\mathrm{r}
\end{array}\right]\), а стратегия игрока в столбце будет \(C=\left[\begin{array}{c}
c \\
1-c
\end{массив}\right]\)

Чтобы найти оптимальную стратегию для игрока-строки, мы сначала найдем произведение RM, как показано ниже.

\[\left[\begin{array}{lll}
\mathrm{r} & 1-\mathrm{r}
\end{массив}\right]\left[\begin{array}{cc}
-2 и 4 \\
1 и -2
\end{массив}\right]=\left[\begin{массив}{ll}
-3 r+1 & 6 r-2
\end{array}\right] \nonumber \]

Приравняв записи, получим

\[-3r + 1 = 6r — 2 \nonumber \]

или

\[r = 1/ 3 \номер. \nonumber \]

Следовательно, оптимальная стратегия для игрока-строки: \(\left[\begin{array}{ll}
1/ 3 & 2 / 3
\end{array}\right]\), но относительно исходной игровой матрицы это \(\left[\begin{array}{lll}
1 / 3 & 0 & 2/3
\end{array}\right]\).

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

\[\left[\begin{array}{cc}
-2 и 4 \\
1 & -2
\end{массив}\right]\left[\begin{array}{c}
c \ \
1-c
\end{массив}\right]=\left[\begin{array}{c}
-6 c+4 \\
3 c-2
\end{массив}\right] \nonumber \]

Приравниваем элементы матрицы произведения друг к другу и получаем,

\[-6c + 4 = 3c — 2 \nonnumber \]

или

\[c = 2/3 \ не число. \nonumber \]

Следовательно, оптимальной стратегией для игрока в столбце является \(\left[\begin{array}{l}
2 / 3 \\
1 / 3
\end{array}\right]\), но по отношению к исходной игровой матрице стратегия для игрока столбца будет \(\left[\begin{array}{c}
2 / 3 \\
0 \\
1 / 3
\end{массив}\right]\).

Чтобы найти математическое ожидание V в игре, у нас есть два варианта: либо найти произведение матриц R, M и C, либо умножить оптимальные стратегии относительно исходной матрицы на исходную матрицу. Выбираем первое и получаем

\[\begin{array}{l}
\mathrm{V}=\left[\begin{array}{lll}
1 / 3 & 2 / 3
\end{массив}\right]\left[\begin{array}{cc}
-2 & 4 \\
1 & -2
\end{массив}\right]\left[\begin{array}{l}
2 / 3 \\
1 / 3
\end{массив}\right] \\
\mathrm{V}=\left[\begin{array}{l}
0
\end{array}\right]
\end{array} \nonumber \]

Следовательно, если оба игрока используют свою оптимальную стратегию, ценность игры равна нулю.

Резюмируем следующим образом:

Сокращение доминированием

Иногда игровую матрицу \(m \times n\) можно свести к матрице \(2 \times 2\), удалив доминирующих строк и столбцов.
Строка называется доминируемой строкой , если существует другая строка, которая даст такой же или больший выигрыш. Это происходит, когда существует строка, каждая запись которой больше, чем соответствующая запись доминирующей строки.
Столбец называется столбцом с преобладанием , если существует другой столбец, который даст выплату равного или лучшего значения. Это происходит, когда существует столбец, каждая запись которого меньше, чем соответствующая запись доминирующей строки.

Эта страница под названием 11.3: Reduction by Dominance распространяется под лицензией CC BY 4.0 и была создана, изменена и/или курирована Рупиндером Секоном и Робертой Блум с использованием исходного контента, который был отредактирован в соответствии со стилем и стандартами платформы LibreTexts; подробная история редактирования доступна по запросу.

Наверх

Была ли эта статья полезной?

Тип изделия
Раздел или Страница
Автор
Рупиндер Сехон и Роберта Блум
Лицензия
СС BY
Версия лицензии
4,0
Показать страницу TOC
нет
Теги
1. доминирующая колонка
2. доминирующая строка
3. уменьшение доминирования
4. источник@https://www. deanza.edu/faculty/bloomroberta/math21/afm3files.html.html

Теория игр (игра в нормальной форме) | Набор 4 (Преобладание свойства — чистая стратегия)

В некоторых играх можно уменьшить размер матрицы выплат, исключив строки (или столбцы), над которыми доминируют другие строки (или столбцы) соответственно.

Свойство доминирования для строк: X ≤ Y, т. е. если все элементы конкретной строки X меньше или равны соответствующим элементам другой строки Y , затем удалите строку X (в строке X преобладает строка Y ). Элементы определенной строки X также можно сравнить со средним значением двух или более других строк, и если элементы строки X меньше или равны соответствующим элементам после взятия среднего значения, удалите строку X. .

Свойство доминирования для столбцов: X ≥ Y, т. е. если все элементы определенного столбца X больше или равны соответствующим элементам другого столбца Y , затем удалите столбец X (столбец X доминирует над столбцом Y ). Элементы столбца X также можно сравнить со средним значением двух или более столбцов, и если элементы столбца X больше, чем соответствующие элементы после взятия среднего значения, удалите столбец X .

Рассмотрим следующую игру:

Решение:
Чистая стратегия: Решение вышеописанной игры с помощью Pure Strategy будет следующим:
– стоимость игры (V) = 8
– A[P1, P2, P3, P4] = A[0, 0, 1, 0]
– B[Q1, Q2, Q3, Q4, Q5] = B[1, 0, 0, 0, 0]
Где
P1, P2, P3 и P4 — вероятности стратегии 1, 2, 3 и 4 соответственно для игрока. A.
Q1, Q2, Q3, Q4 и Q5 — вероятности стратегий 1, 2, 3, 4 и 5 соответственно для игрока B.
Для обоих игроков общая вероятность равна 1.

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

– при использовании свойства доминирования для строки элементы строки 4 меньше элементов строки 3, т. е. в строке 4 доминирует строка 3. Удалить строку 4.

– выбрать наименьшее значение из оставшихся «Итого по строке» и примените свойство доминирования.

. Используя свойство доминирования, в строке 1 доминирует строка 3. Удалить строку 1.

— выбрать наименьшее значение среди оставшихся значений, т. е. 39 — наименьшее, при применении свойства доминирования видно, что условие доминирования строки не выполняется. Теперь примените свойство доминирования для столбца.

— Возьмите сумму каждого столбца (только из оставшихся строк) и выберите среди них наибольшую.

— при использовании свойства доминирования для столбца в столбце 4 доминирует столбец 1. Удалите столбец 4.

— выберите наибольшее из оставшихся значений столбца.

— при использовании свойства доминирования для столбцов в столбце 5 доминирует столбец 1. Удалите столбец 5.

– выберите наибольшее из оставшихся значений столбца.

— при использовании свойства доминирования для столбцов столбец 2 доминирует над столбцом 1. Удалите столбец.

— Снова выберите наибольшее значение (например, 16). Теперь при применении свойства доминирования доминирование не будет найдено. Теперь снова перейдите к сокращению ряда.

— Найдите сумму строки и выберите наименьшую из них.

— при использовании свойства доминирования для строк в строке 2 доминирует строка 3. Удалите строку 2.

— теперь есть только одна строка (нет необходимости находить общее количество столбцов), и остается два столбца.