Редактирование: Тигры, 01 лекция (от 04 сентября)
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 11: | Строка 11: | ||
Второй игрок. Предположим, он принял стратегию j. Худший для него вариант --- max_j K(i, j), j=1..m. Выбирать н будет стратегию, которая минимизирует этот максимум --- min_i max_j K(i, j)= max_j K(i, j_0). Эта стратегия существует, минимум есть, Эту стратегию будем обозначать верхней ценой игры ~I~. | Второй игрок. Предположим, он принял стратегию j. Худший для него вариант --- max_j K(i, j), j=1..m. Выбирать н будет стратегию, которая минимизирует этот максимум --- min_i max_j K(i, j)= max_j K(i, j_0). Эта стратегия существует, минимум есть, Эту стратегию будем обозначать верхней ценой игры ~I~. | ||
- | + | Теорема 1. _I_ ≤ ~I~. Математически это доказывается просто. Зафиксируем произвольную пару i, j. min_j K(i, j) ≤ K(i, j) ≤ max_i K(i, j). Отсюда следует, что min_j K(i, j) ≤ max_i K(i, j) при всех i, j. Если это верно при всех i, то можно взять максимум, и он будет верен при любой правой части: max_i min_j K(i, j) ≤ max_i K(i, j). Вспомним также, что это соотношение верно при любых j, тогда можно взят минимум по j, и получаем _I_ ≤ ~I~. | |
Посмотрим смысловую часть теоремы. Нижняя цена --- тот выигрыш, который гарантирован первому игроку, когда он не знает, как действует второй. Теперь посмотрим на верхнюю цену, это лучшая цена для второго игрока, но можно интерпретировать иначе: пусть первый игрок всегда знает, как действует второй, то есть, он знает j. Тогда он будет искать max_i K(i, j), и тогда в худшем случае он получит min_j max_i K(i, j), то есть, ~I~. То есть, когда игрок знает действия противника, то его выигрыш будет не меньше, чем когда не он знает. | Посмотрим смысловую часть теоремы. Нижняя цена --- тот выигрыш, который гарантирован первому игроку, когда он не знает, как действует второй. Теперь посмотрим на верхнюю цену, это лучшая цена для второго игрока, но можно интерпретировать иначе: пусть первый игрок всегда знает, как действует второй, то есть, он знает j. Тогда он будет искать max_i K(i, j), и тогда в худшем случае он получит min_j max_i K(i, j), то есть, ~I~. То есть, когда игрок знает действия противника, то его выигрыш будет не меньше, чем когда не он знает. |