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

↑

▷ Содержание

⇐ ПредыдущаяСтр 10 из 11Следующая ⇒

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

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

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

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

a_ij≤ a_il(1)

a_ij≥ a_kj(2)

При сравнении элементов a_il и a_kl возможны случаи:

a_il≥ a_kl(3)

и

a_il≤ a_kl (4)

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

Таким образом, в случае (3) выполняется условие 1.

Рассмотрим случай (4). Из неравенств (4), (1) и (2) следует неравенство а_kl> a_kj, которое вместе с неравенством (1) означает, что l-й столбец доминируется j-м столбцом, и потому l-й столбец можно удалить. Неравенство (2) означает, что в оставшемся j-м столбце i-я строка доминирует k-ю строку в, следовательно, k-ю строку можно удалить.

Итак, в случае выполнения неравенства (4) справедливо условие 2.

Наконец, отметим, что если верны неравенства (3) и (4), т. е. если:

a_il= a_kl(5)

то, как следует из доказанного, имеют место условия 1 и 2. Однако совместное выполнение условий 1 и 2 может быть и при невыполнении равенства (5). Итак, необходимость доказана.

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

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

3. Доказательство критерия седловой точки матрицы игры размерности в терминах пассивных стратегий.

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

Доказательство.

Необходимость. Пусть i, k Î{1, 2}, i k, – номера чистых стратегий игрока А, а j, l Î{1, 2} ,j l, – номера чистых стратегий игрока В. Пусть – седловая точка. Тогда A_i – оптимальная стратегия игрока А.

Так как чистую оп­тимальную стратегию A_i можно рассматривать как смешанную оптимальную стратегию, в которую чистая стратегия A_i входит достоверно, т. е. с вероятностью, равной 1, а чистая стратегия A_k – cнулевой вероятностью, то стратегия А_k является пассивной, и необходимость доказана.

Отметим, что из того, что – седловая точка, аналогичным образом следует, что B_l — пассивная стратегия игрока В.

Достаточность. Пусть одна из чистых стратегий, напри­мер, стратегия А_k игрока А является пассивной. Тогда найдется оптимальная смешанная стратегия Р⁰ игрока А, в которую чистая стратегия А_k входит с нулевой вероятностью и, следовательно, чистая стратегия А_k входит с вероятностью, равной единице. Это означает, что Р⁰ = A_i, т. е. A_i – оптимальная стратегия.

Пусть Q⁰ – некоторая оптимальная стратегия игрока В, в кото­рую чистые стратегии В_j и В_l входят соответственно с вероятностями q⁰ и 1 – q⁰. Так как q⁰+( 1 – q⁰) = 1, то хотя бы одно из чисел q⁰ и 1 – q⁰ положительно.

Если q⁰ = 1и, следовательно, 1 – q⁰ = 0, то чистая стратегия В_j является активной и тогда, по теореме об активных страте­гиях

(1)

где V- цена игры.

В то же время стратегия B_j является оптималь­ной, так как в случае q⁰ = 1, имеет место равенство B_j = Q⁰, a Q⁰ – оптимальная стратегия. Из равенства с учетом оптималь­ности стратегий А_i и B_j следует, что – седловая точка.

Если q⁰ = 0 и, следовательно, 1 – q⁰ = 1, то чистая стратегия В_j является активной оптимальной стратегией и тогда из равенства

(2)

которое имеет место в силу теоремы об активных стратеги­ях, следует, что — седловая точка.

Наконец, рассмотрим случай q⁰ > 0 и 1 – q⁰ > 0. В этом случае стратегии B_j и B_l активны и тогда по теореме об активных стратегиях имеют место оба равенства .

Могут представиться две возможности:

(3)

и

(4)

1) Рассмотрим возможность .

В силу (1) и (2) для показателя эффективности стратегии А_i будем иметь

Из неравенства (3) и равенства (1) следует, что

Из (5) и (6) получаем двойное равенство

которое означает, что A_i и B_j - оптимальные стратегии. Следовательно, – седловая точка матрицы А.

2) Рассмотрим возможность .

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

4. Доказательство теоремы о признаке (достаточном условии) существования седловой точки матрицы игры размерности .

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

Доказательство.

Из равенства

Возможны случаи:

или

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

Если же имеет место случай (2), то из вытекает неравенство , которое вместе с (2) означает строгую юминируемость первого столбца матрицы А ее вторым столб­цом. А потому В ₁является пассивной и, следовательно, у матрицы А существует седловая точка.

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

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

В этом случае в соответствии со следствием выполняется условие

.

Пусть — оптимальная смешанная стратегия игрока A (которая всегда существует по основной теореме матричных игр фон Неймана) и V – цена игры.

Так как матрица А не имеет седловых точек, то пассивных стратегий в игре не существует. Поэтому стратегии В ₁и В ₂активны. Тогда Записывая ле­вые части этих равенств по формуле и присоединяя к ним нормировочное условие получим систему трех ли­нейных алгебраических уравнений

с тремя неизвестными Определитель этой системы

в силу выполнимости условия . Поэтому система имеет единственное решение, которое можно найти по формулам Крамера. Для этого вычислим определители

Тогда по формулам Крамера

получаем требуемые формулы

и

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

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

В этом случае в соответствии со следствием выполняется условие

.

Пусть — оптимальная смешанная стратегия игрока В (которая всегда существует по основной теореме матричных игр фон Неймана) и V – цена игры.

Так как матрица А не имеет седловых точек, то пассивных стратегий в игре не существует.

Поэтому стратегии А₁и А ₂активны. Следовательно, . Записывая ле­вые части этих равенств по формуле и присоединяя к ним нормировочное условие

получим систему

.

Определитель этой системы

в силу выполнимости условия . Поэтому система

имеет единственное решение, которое можно найти по формулам Крамера. Для этого вычислим определители

По формулам Крамера

мы получаем формулы и

Познавательные статьи:



Психологические особенности спортивного соревнования

Приготовление дезинфицирующих растворов различной концентрации

Занятость населения и рынок труда

Социальный статус семьи и её типология