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

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

Чистая стратегия А_i первого игрока доминирует его чистую стратегию А_k, если выполнены неравенства:

a_ij ≥ a_kj для всех , причем для некоторого индекса j₀,

т.е. все элементы i-й строки платежной матрицы игры А не меньше соответствующих элементов ее k-й строки и хотя бы один элемент строго больше. В этом случае стратегия А_k называется доминируемой.

Соответственно, чистая стратегия B_j второго игрока доминирует его чистую стратегию B_l, если выполнены неравенства:

a_il ≥ a_ij для всех ; причем для некоторого индекса i₀,

т.е. все элементы j-го столбца платежной матрицы А не больше соответствующих элементов ее l-го столбца и хотя бы один элемент строго меньше. В этом случае стратегия B_l также называется доминируемой.

Чистые стратегии игроков А_i и А_k первого игрока называются дублирующими, если a_ij = a_kj для всех , т.е. i-я и k-я строки платежной матрицы совпадают.

Соответственно, чистые стратегии игроков B_j и B_l второго игрока называются дублирующими, если a_il = a_ij для всех ; т.е. j-й и l-й столбцы платежной матрицы совпадают.

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

Пример 3.4. Рассмотрим игру 3х4 с платежной матрицей

	В1	В2	В3	В4
А1	34	24	28	18	х1
А2	34	25	28	25	х2
А3	24	26	24	26	х3
	y1	y2	y3	y4

Стратегия А₂ первого игрока доминирует стратегию А₁, поэтому первую строку можно вычеркнуть. Сокращенная матрица имеет такой вид:

	В1	В2	В3	В4
А2	34	25	28	25	х2
А3	24	26	24	26	х3
	y1	y2	y3	y4

В этой игре стратегия В₃ второго игрока доминирует стратегию В₁; следовательно, первый столбец можно вычеркнуть. Стратегии В₂ и В₄ являются дублирующими, так как соответствующие столбцы содержат одинаковые элементы. Значит любой из них также можно вычеркнуть. Пусть это будет четвертый столбец. Итак, после отбрасывания доминируемых и дублирующих стратегий получаем игру 2х2 с платежной матрицей

	В2	В3
А2	25	28	х2
А3	26	24	х3
	y2	y3

Ее решение: Следовательно, решение исходной игры таково:

В следующем примере использование принципа доминирования также позволяет существенно сократить размерность платежной матрицы.

Пример 3.5. На аукционе продаются контрольные пакеты акций двух предприятий. За них борются два банка, один из которых располагает капиталом $4 млн., а другой — $3 млн. Можно предлагать лишь цену, кратную $1 млн. Выигрывает банк, предложивший большую сумму. Если оба банка предложили одинаковую сумму, то никто не выигрывает.

Платежная матрица формируется таким образом: если банк выиграл пакет акций, то ему начисляется очко, а в матрицу записывается разность между выигрышами первого и второго банка. Нужно найти решение этой игры.

Первый банк имеет пять чистых стратегий: (4, 0), (3, 1), (2, 2), (1, 3), (0, 4), а второй — четыре чистые стратегии: (3, 0), (2, 1), (1, 2), (0, 3). Здесь первая цифра означает сумму, предложенную банком за первое предприятие, а вторая цифра — сумму, предложенную за второе предприятие. Сформируем платежную матрицу игры:

	В1 (3, 0)	В2 (2, 1)	В3 (1, 2)	В4 (0, 3)
А1 (4, 0)	1	0	0	0	х1
А2 (3, 1)	1	1	0	0	х2
А3 (2, 2)	0	1	1	0	х3
А4 (1, 3)	0	0	1	1	х4
А5 (0, 4)	0	0	0	1	х5
	y1	y2	y3	y4

Стратегия А₂ доминирует стратегию А₁, а стратегия А₄ доминирует стратегию А₅. Следовательно, первую и пятую строку можно вычеркнуть. Получаем новую матрицу:

	В1	В2	В3	В4
А2	1	1	0	0	х2
А3	0	1	1	0	х3
А4	0	0	1	1	х4
	y1	y2	y3	y4

В этой игре стратегия В₁ доминирует стратегию В₂, а стратегия В₄ доминирует стратегию В₃. Значит, второй и третий столбцы можно вычеркнуть. Получаем следующую матрицу игры:

	В1	В4
А2	1	0	х2
А3	0	0	х3
А4	0	1	х4
	y1	y4

Вторую строку в ней можно вычеркнуть. Окончательно имеем такую платежную матрицу:

	В1	В4
А2	1	0	х2
А4	0	1	х4
	y1	y4

Эта матрица не имеет седловой точки. Поэтому для нахождения ее решения нужно использовать смешанные стратегии. Ее решение:

Значит, оптимальная стратегия первого банка = (0, 0.5, 0, 0.5, 0), оптимальная стратегия второго банка = (0.5, 0, 0, 0.5), а цена игры Таким образом, первый банк должен применять свою вторую и четвертую чистую стратегию с вероятностью, равной 0.5, а второй банк — первую и четвертую чистую стратегию с такой же вероятностью. В этом случае выигрыш первого банка будет равен 0.5.