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

↑

▷ Содержание

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

, где – столбец, а – строка матрицы .

Доказательство. Пусть – матричная игра.

По лемме 2 имеет место либо утверждение (1):Точка (в m- мерном пространстве) содержится в выпук­лой оболочке m + n точек

………………

и

,

,

………………

либо утверждение (2): Существуют числа , удовлетворяющие условиям

, , , .

Если верно (1), то является выпуклой линейной комбинацией m+n векторов. Поэтому существуют такие , …, , что

Если бы все числа , …, были равны нулю, то` оказывался бы выпуклой линейной комбинацией m единичных векторов , ,…, , что, очевидно, невозможно, т.к. они линейно независимы. Следовательно, по крайней мере одно из чисел , …, положительно и Тогда можно положить ,

и мы получаем

Значит, и

Предположим теперь, что верно утверждение (2):

.

Тогда, так что

Следовательно, неравенство не может иметь места. Предположим теперь, что мы изменили игру А, заменив её на игру , где .

Ясно, что для любых ,

Поэтому

Так как неравенство

не может иметь места, то неравенство

также не выполняется. Но k – произвольно. Значит, неравенство невозможно. Так как , то ,

что и требовалось доказать.

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

Мы видим, что стратегия , удовлетворяющая условию

(4)

является оптимальной для игрока 1 в том смысле, что не существует стратегии, которая дала бы ему больший ожидаемый выигрыш, чем , против каждой стратегии игрока 2.

Обратно, если удовлетворяет условию

(5)

то является оптимальной для игрока 2 в том же смысле.

Далее, очевидно, что , т.к. если бы правая часть этого равенства была меньше левой, то это противоречило бы (5), а если бы она была больше левой – это противоречило бы (4). Следовательно, оптимальные стратегии и являются также оптимальными одна против другой, а также против любой иной оптимальной стратегии.

Будем называть любую пару оптимальных стратегий (, ) – решением игры.

Вычисление оптимальных стратегий (поиск решения в чистых стратегиях, доминирование стратегий, решение игр 2´2).

Теорема о минимаксе гарантирует, что каждая антагонистическая игра имеет оптимальные стратегии. Она даёт существование, но не определяет, как искать эти оптимальные стратегии.

1. Простейшим является тот случай, когда существует седловая точка, т.е. когда существует элемент , являющийся максимальным в своём столбце и минимальным в своей строке. Тогда чистые стратегии i и j (или, что равносильно, смешанные стратегии и , для которых =1, =1, а все остальные компоненты равны нулю) будут оптимальными стратегиями для игроков 1 и 2 соответственно.

2. Доминирование. Пусть дана матрица . Будем говорить, что i -ая строка доминирует k -ую строку, если и по крайней мере для одного j.

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

Короче говоря, одна чистая стратегия (представленная своей строкой или столбцом) доминирует другую чистую стратегию, если выбор первой (доминирующей) стратегии, по крайней мере, не хуже выбора второй (доминируемой) стратегии, а в некоторых случаях и лучше.

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

Теорема. (Без доказательства) Пусть – матричная игра, и пусть строки _{, ,…,} матрицы доминируются. Тогда игрок 1 имеет такую оптимальную стратегию , что = =…= =...=0; кроме того, любая оптимальная стратегия для игры, получающейся в результате удаления доминируемых строк, будет также оптимальной стратегией для первоначальной игры.

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

3. Игры (2´2). Пусть дана матричная игра 2×2 с платежной матрицей . Если есть седловая точка, то всё определено. Если нет, то оптимальные стратегии и имеют положительные компоненты , .

Если значение игры – , это для оптимальной стратегии , т.е.

.

Преобразуем

(*)

Т.к. оптимальная стратегия, то должно выполняться:

,

.

Допустим, что одно из выражений меньше :

.

Т. к. , , то левая часть (*) будет меньше правой. Отсюда следует, что должно быть

,

.

Аналогично можно показать:

,

.

Из этих уравнений, с учётом, что , легко найти стратегии обоих игроков.

4. Симметричные игры. Квадратичная матрица называется кососимметрической, если Матричная игра называется симметричной, если её матрица кососимметрическая.

Теорема. Значение симметричной игры равно нулю. Кроме того, если есть оптимальная стратегия для игрока 1, то есть также оптимальная стратегия для игрока 2.

Доказательство: Пусть - матрица игры и - произвольная стратегия. Легко видеть, что . Следовательно, Поэтому

Отсюда следует, что для любого , так что значение игры неположительно; в то же время , так что значение игры неотрицательно. Следовательно, значение игры равно нулю.

Далее, если – оптимальная стратегия игрока 1, то

(из ).

Но отсюда , так что .

Значит, стратегия оптимальна также и для игрока 2.

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



Техника прыжка в длину с разбега

Тактические действия в защите

История Олимпийских игр

История развития права интеллектуальной собственности