Принцип доминирования стр-ий. Т и следствие о доминируемых стр-ях.

Пусть имеем игру с матрицей . Обычная мат-ца А

Каждой смеш.стр-ии иг-ка А поставим в соответствие строку (1)

(размера ), элементами которой являются выигрыши иг-ка А в ситуациях В силу формулы строку (1) можно представить так:

откуда видно, что она является выпуклой комбинацией строк мат-цы А

Обратно, каждой выпуклой комбинации (2) строк мат-цы А с коэффициентами поставим в соответствие смешанную стр-ию иг-ка А.

Т.о., между смешанными (в том числе и чистыми) стр.ми иг-ка А и выпуклыми комбинациями , , строк мат-цы устанавливается взаимно-однозначное соответствие .(3)Из (1) и (3) ясно, что каждой чистой стр-ии A_kk =1,2,…mиг-ка А ставится во взаимно-однозначное соответствие k-я строка мат-цыА. Если для двух выпуклых комбинаций строк мат-цы А (4) И , (5)

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

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

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

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

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

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

 

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

 

Следствие 1

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

2. Если l-й столбец матрицы игры доминируется (строго доминируется) некоторым другим столбцом, то существует (любая) оптимальная смешанная стратегия игрока B, в которую чистая стратегия Bl входит с нулевой вероятностью.

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

 

Принцип редуцирования матриц игры, основанный на разбиение ее на подматрицы с определнным свойством.

Редуцирование матриц путем разбития ее на подматрицы, основывется на следующей теореме:

Пусть подматрица обладает равными суммами элементов по строкам и столбцам. Тогда справедливы следующие неравентсва, при которых матрица может делится на подматрицы:

1. Если данная подматрица состоит из единственной строки, то все элементы этой единственной строки равны между собой.

2. Если данная подматрица состоит из единственного столбца, то все элементы этого единственного столбца равны между собой.

3. Если данная подматрица квадратная, то есть число ее строк равно числу столбцов, то сумма элементов каждой строки равна сумме элементов каждого столбца.

 

31. Изоморфное преобразование игры

Изоморфным преобразованием игры называется перенумеравание чистых стратегий игрока А и, или игрока В.

Теорема. При изоморфном преобразовании справедливы следующие утверждения:

 

Зеркальный изоморфизм игры.

33. Аффиное преобразование игры.

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

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

1. Можно удалить k-ю строку как доминируемую 1-й строкой, а затем в оставшейся i-й строке можно удалить 1-й столбец как доминируемый j-м столбцом,

2. Можно удалить 1-й столбец как доминируемый j-м столбцом, а затем в оставшемся j-м столбце удалить k-ю строку как доминируемую i-й строкой.

Док-во. Необх-ть: Пусть a_ij — седл. точка. Тогда элемент а_ij — наименьший в i-й строке и наибольший в j-м столбце: . При сравнении элементов а_ij и a_kl возможные случаи .

Рассмотрим (3): Нерав-ва (2) и (3) означают, что i-я строка доминирует k-ю строку и потому k-ю строку можно удалить. Нерав-во (1) показывает, что в оставшейся i-й строке 1-й столбец доминируется j-м столбцом, а потому 1-й столбец можно удалить. Т.о, в случае (3) выполняется условие 1. Рассмотрим (4): Из нерав-тв (4), (1) и (2) следует нерав-во , которое вместе с нерав-вом (1) означает, что 1-й столбец доминируется j-м столбцом, и потому 1-й столбец можно удалить. Нерав-во (2) означает, что в оставшемся j-м столбце i-я строка доминирует k-ю строку и, следовательно, k-ю строку можно удалить. Итак, в случае выполнения нерав-ва (4) справедливо условие 2.Если верны нерав-ва (3) и (4), т. е. если , то, как следует из доказанного, имеют место условия 1 и 2. Однако совместное выполнение условий 1 и 2 может быть и при невыполнении рав-ва (5). Итак, необходимость доказана.

Дост-ть. Пусть выполняется условие 1. Тогда i-я строка доминирует k-ю строку, откуда, в частности, следует, что верно (2). Так как в i-й строке l-й столбец доминируется j-м, то имеет место (1). Нерав-ва (1) и (2) означают, что a_ij- седл. точка игры.

Пусть выполняется условие 2. Из того, что l-й столбец доминируется j-м столбцом, следует (1), а из того, что в j-м столбце i-я строка доминирует k-ю строку, вытекает нерав-во (2). Поэтому a_ij - седл. точка игры.