Удаление стратегий

Количество строк и ¤ или столбцов платёжной матрицей может быть уменьшено за счёт удаления доминируемых и дублирующих стратегий. Стратегия s игрока A называется домини-руемой его стратегией t, если все элементы s -ой строки платёжной матрицы не больше, чем со-ответствующие элементы её t -ой строки. Игроку A нет смысла выбирать доминируемую страте-гию s, поскольку при выборе доминирующей стратегии t он выигрывает не меньше, независимо от стратегии игрока B. Стратегия s игрока B называется доминируемой его стратегией t, если все элементы s -го столбца платёжной матрицы не меньше, чем соответствующие элементы её t -го столбца. Игроку B нет смысла выбирать доминируемую стратегию s, поскольку при выборе доминирующей стратегии t он проигрывает не больше, независимо от стратегии игрока A. Стратегия s (любого игрока) называется дублирующей его стратегию t, если соответствующие этим стратегиям строки (или столбцы) совпадают. Очевидно, что из нескольких совпадающих стратегий достаточно оставить только одну, удалив все другие.

Пример 3. Рассмотрим матричную игру двух лиц со следующей платёжной матрицей

В данном случае для игрока A стратегия 1 является доминируемой стратегией 2, для игрока B стратегия 6 является доминируемой стратегиями 3, 4 и 5, а стратегии 4 и 5 являются дублирую-щими друг друга. После удаления указанных доминируемых стратегий и одной из дублирую-щих стратегий останется следующая матрица, в которой доминируемых и дублирующих страте-гий уже нет:

■

Утверждение 3. Удаление доминируемых и дублирующих стратегий из платёжной мат-рицы не влияет на значение нижней и верхней цены игры, заданной данной матрицей. Множес-тва оптимальных стратегий также не меняются (за исключением удаления дублирующих) ■

Таким образом, при удалении из платёжной матрицы «лишних» строк и столбцов суть иг-ры не меняется, в то время как размерность матрицы может значительно уменьшиться. В при-мере 3 вместо матрицы размера 4´6 получена матрица размера 3´4.

Пример 4. Рассмотрим матричную игру двух лиц со следующей платёжной матрицей:

В данной матрице 1-ая строка доминируема 2-ой строкой, поскольку все её элементы больше. После удаления 1-ой строки получаем следующую матрицу:

В новой матрице 1-ый и 4-ый столбцы доминируемы 3-им столбцом. После их удаления оста-нется матрица

в которой 1-ая строка доминирует 2-ую строку. После удаления 2-ой строки останется единст-венная строка á28, 18, 33ñ, откуда следует, что игроку B надо выбрать 2-ой столбец, содержа-щий минимальный проигрыш 18, т.е. исходная матрица сведена к матрице размера 1´1, или од-ному числу 18. Возвращаясь к исходной матрице, видим, что пара стратегий á2, 3ñ является решением данной игры, а её цена равна 18.

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

Далее, удаляя доминируемые 1-ую и 3-ью строку, получаем единственную строку á28, 18, 38, 33ñ, и выбирая в ней минимальный проигрыш 18, получаем тот же ответ - матрицу размером 1´1, т.е. число 18 ■

Результат примера 4 не случаен. Имеет место

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

Задание 2. Удалить доминируемые стратегии в следующих матрицах (см. примеры 3 и 4)

				-99

				-23

-19
				-90

	-15
			-13

	-19
		-18
			-29

		-30

		-19

	-13
		-27

■

Дата добавления: 2015-10-16