Принцип доминирования. Теорема о доминирующих стратегиях и следствия из нее

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

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

строк ( матрицы А, представляющими собой строки выигрышей , j=1,2,…,n, игрока А в ситуациях , j=1,2,…,n, устанавливается взаимно-однозначное соответствие

из которого ясно, что, в частности, каждой чистой стратегии игрока А ставится во взаимно-однозначное соответствие k-я строка матрицы А.

Если для двух выпуклых комбинаций строк матрицы А

и

выполняются неравенства

то говорят, что строка (2) доминирует строку (1), а строка (1) доминирует строкой (2). Если каждое неравенство (3) является равенством, то строки (1) и (2) называют дублирующими. Если же каждое неравенство (3) является строгим, то говорят, что строка (2) строго доминирует строку (1), а строка (1) строго доминируется строкой (2).

Аналогичная терминология используется и для соответствующих стратегий игрока А. А именно, если строка (2) доминирует, соответственно дублирует, соответственно строго доминирует строку (1), то говорят, что стратегия доминирует, соответственно дублирует, соответственно строго доминирует стратегию .

 

Между смешанными (в том числе и чистыми) стратегиями игрока В и выпуклыми комбинациями

^T,

столбцов ^T , j=1,2,…,n, матрицы А (Т- значок транспонирования), представляющими собой столбцы ^T

проигрышей Н(, i=1,2,…,m, игрока В в ситуациях (, i=1,2,…,m, устанавливается взаимно-однозначное соответствие

^T ,

из которого видно, что, в частности, каждой чистой стратегии , l =1,2,…,n, игрока В ставится во взаимно-однозначное соответствие l -й столбец ^T матрицы А.

Если для двух выпуклых комбинаций столбцов матрицы А

^T

и

^T

выполняются неравенства

то говорят, что столбец (4) (стратегия доминирует столбец (5) (стратегию , а столбец (5) (стратегия ) доминируется столбцом (4) (стратегией ). Если каждое неравенство (6) является равенством, то столбцы (4) и (5) (стратегии и ) называют дублирующими друг друга. Если же каждое неравенство (6) является строгим, то говорят, что столбец (4) (стратегия ) строго доминирует столбец (5) (стратегию ), а столбец (5) (стратегия ) строго доминируется столбцом (4) (стратегией ).

Теорема. Справедливы следующие предложения:

1. Если k-ая строка (k ϵ {1, 2, …, m}) матрицы А игры доминируется некоторой выпуклой комбинацией остальных ее строк, то существует оптимальная смешанная стратегия Р^k = ( игрока А, относительно которой k-я чистая стратегия А_k является пассивной, т.е. входит в смешанную стратегию Р^k с нулевой вероятностью: =0

2. Если k-ая строка (k ϵ {1, 2, …, m}) матрицы А игры строго доминируется некоторой выпуклой комбинацией остальных ее строк, то относительно любой оптимальной смешанной стратегии Р^О = игрока А, чистая k-я стратегия является пассивной, т.е. входит в стратегию Р^О с нулевой вероятностью: =0

3. Если l-ый столбец (l ϵ {1, 2, …, n}) матрицы А игры доминируется некоторой выпуклой комбинацией остальных ее столбцов, то существует оптимальная смешанная стратегия Q^l = игрока В, относительно которой l-я чистая стратегия B_l является пассивной, т.е. входит в стратегию Q^l с нулевой вероятностью: =0

4. Если l-ый столбец (l ϵ {1, 2, …, n}) матрицы А игры строго доминируется некоторой выпуклой комбинацией остальных ее столбцов, относительно любой оптимальной смешанной стратегии Q^О = игрока В чистая l-я стратегия B_l является пассивной, т.е. входит в стратегию Q⁰ с нулевой вероятностью: =0

Следствие 1:

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

2. Если k-я строка матрицы игры строго доминируется некоторой другой строкой, то относительно любой оптимальной смешанной стратегии игрока А чистая стратегия А_k является пассивной, т.е. входит в любую оптимальную смешанную стратегию с нулевой вероятностью.

3. Если l-ый столбец матрицы игры доминируется некоторым другим столбцом, то существует оптимальная смешанная стратегия игрока В, относительно которой чистая стратегия В_l является пассивной, т.е. входит в эту смешанную стратегию с нулевой вероятностью.

4. Если l-ый столбец матрицы игры строго доминируется некоторым другим столбцом, то относительно любой оптимальной смешанной стратегии игрока В чистая стратегия В_l является пассивной, т.е. входит в любую оптимальную смешанную стратегию с нулевой вероятностью.

Следствие 2:

Одну из двух дублирующих чистых стратегий можно удалить.

 

 

41. Критерий седловой точки платежной матрицы игры размера , в терминах доминирования

Теорема:

Пусть i, k – номера строк, а j, l – номера столбцов. И пусть матрица А размером 2х2. Для того, чтобы элемент a_ij был седловой точкой матрицы, необходимо и достаточно выполнение хотя бы одного из следующих условий:

1. Либо можно удалить k-ю строку, как доминируемую i-й строкой, и уже в i-й строке удалить l-й столбец, потому что им доминирует j-й.

2. Либо можно начать со столбцов, удалить там один из доминируемых (например j-й), а потом в оставшемся l-м столбце удалить одну из строк.

Если в матрице нет доминируемых строк и столбцов – значит, нет седловых точек. (можно не писать: Другими словами, для того, чтобы у матрицы А размером 2*2 не существовало седловой точки, необходимо и достаточно, чтобы среди строк и среди столбцов не было доминируемых (в частности, дублируемых).)

42. Критерий существования седловой точки в игре размера в терминах пассивных стратегий

Теорема: Для того чтобы в игре с матрицей А размером 2*2 существовала седловая точка, необходимо и достаточно существование смешанной стратегии, относительно которой одна из чистых стратегий является пассивной.

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

Док-во:

1) Необходимость. Пусть , - номера чистых стратегий игрока А, а , номера чистых стратегий игрока В. Пусть - седловая точка. Тогда - оптимальная стратегия игрока А. Так как чистую оптимальную стратегию можно рассматривать как смешанную оптимальную стратегию, в которую чистая стратегия входит с вероятностью 1, а чистая стратегия - с нулевой вероятностью, то стратегия является пассивной, и необходимость доказана.

2) Достаточность. Пусть стратегия игрока А является пассивной. Тогда найдется оптимальная смешанная стратегия , в которую чистая стратегия входит с нулевой вероятностью и, следовательно, чистая стратегия входит с вероятностью, равной 1. Это означает, что , т.е. - оптимальная стратегия.

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

Если , то чистая стратегия является активной и тогда, по теореме об активных стратегиях . В то же время стратегия является оптимальной, тк в случае , имеет место , а - оптимальная стратегия. С учетом этого и из равенства следует, что - седловая точка.

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

Наконец, рассмотрим случай и . В этом случае стратегии и активны и по теореме об активных стратегиях имеют место оба равенства: и . Могут представиться 2 возможности: и .

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

Рассмотрим возможность . Если , то это неравенство вместе с будет означать, что i-я строка матрицы А строго доминируется k-й строкой и потому i-ю строку нужно отбросить как заведомо невыгодную, что противоречит оптимальности стратегии . Значит, . Но так как по и , то элемент - наименьший в i-й строке и наибольший в -м столбеце, т.е. - седловая точка матрицы А.

 

 

43. Признак (достаточное условие) существования седловой точки платежной матрицы размерности 2*2

Теорема: Для того чтобы у матрицы А размером 2*2 существовала седловая точка, достаточно, чтобы сумма элементов главной диагонали матрицы А равнялась сумме элементов ее побочной диагонали:

Доказательство: из неравенства: возможны случаи:

Тогда из неравенства: получим: , которое вместе с означает, что второй столбец матрицы А доминируется ее первым столбцом. Тогда на основании следствия из теоремы (Если l-й столбец матрицы игры доминируется некоторым другим столбцом, то существует оптимальная смешанная стратегия игрока В) существует оптимальная смешанная стратегия игрока в, в которую чистая стратегия В2 входит с нулевой вероятностью, то есть В1 является оптимальной. Следовательно стратегия В2 пассивна и по теореме о существовании седловой точки в игре размера 2*2 в терминах пассивных стратегий: ( для того чтобы в игре с матрицей А размером 2*2 существовала седловая точка, необходимо и достаточно существование смешанной стратегии, относительно которой одна из чистых стратегий явл пассивной)у матрицы А существует седловая т.

2.

Тогда из нер-ва: получим: , которое вместе с означает строгую доминируемость первого столбца матрицы А ее вторым столбцом. А потому на основании следствия 2 теоремы 11.1 стратегия В1 является пассивной и, => по теореме (той же, что и в 1-м пункте) у матрицы А существует седловая точка.

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

Теорема. Пусть матрица А размером 2*2 не имеет седловой точки. Тогда каждый из игроков А и В обладает единственной оптимальной смешанной стратегией соответственно , где:

Цена игры в смешанных стратегиях

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

Теорема. Пусть матрица А размером 2*2 не имеет седловой точки. Тогда каждый из игроков А и В обладает единственной оптимальной смешанной стратегией соответственно , где:

Цена игры в смешанных стратегиях