Редактирование: Тигры, 01 лекция (от 04 сентября)
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
| Текущая версия | Ваш текст | ||
| Строка 1: | Строка 1: | ||
* '''Аудиозапись:''' http://esyr.org/lections/audio/game_theory_2008_winter/GT_08_09_04.ogg | * '''Аудиозапись:''' http://esyr.org/lections/audio/game_theory_2008_winter/GT_08_09_04.ogg | ||
| - | + | Раздел 1. Антагонистические игры (АИ) | |
| - | В АИ принимают участие 2 игрока --- первый и второй игрок. Игр определяется тремя элементами: множество стратегий первого игрока X. Его иногда называют множеством чистых стратегий. Y --- множество стратегий второго игрока. | + | В АИ принимают участие 2 игрока --- первый и второй игрок. Игр определяется тремя элементами: множество стратегий первого игрока X. Его иногда называют множеством чистых стратегий. Y --- множество стратегий второго игрока. K(x, y), X ∈ X, y ∈ Y --- платёжная функция. Почти всегда будем предполагать, что X и Y --- компактное множество в конечномерном евклидовом пространстве. |
| - | Как происходит игра: первый игрок принимает стратегию x, второй --- y и вычисляет | + | Как происходит игра: первый игрок принимает стратегию x, второй --- y и вычисляет K(x, y). И выигрыш первого игрока --- K(x, y), выигрыш второго --- -K(x, y). В этом и заключается антагонизм, поскольку один хочет максимизировать K, другой --- минимизировать. Как искать стратегию 1 игроку --- если бы он знал, какую стратегию выберет второй игрок, то задача свелась к максимизации функции. Но мы будем рассматривать случай, когда каждый игрок не знает, какую стратегию выберет второй. Получилась неопределенность. И надо понять, что в этом случае делать. В основе принятия решений в этом случае лежит метод, разработанный Г., лежит метод наилучшего гарантированного результата. В этом случае, каждый игрок выбирает стратегию, которая приносит максимальный выигрыш в худшем случае. |
| - | Рассмотрим частный случай, который позволяет понять суть метода --- когда X и Y --- конечные множества. Будем считать, что все стратегии занумерованы от 1 до n и от 1 до m соответственно. И платёжную функцию будем обозначать как | + | Рассмотрим частный случай, который позволяет понять суть метода --- когда X и Y --- конечные множества. Будем считать, что все стратегии занумерованы от 1 до n и от 1 до m соответственно. И платёжную функцию будем обозначать как K(i, j), i = 1..n, j = 1..m. Посмотрим, как работает принцип наилучшего гарантированного результата: предположим, что игрок выбрал стратегию i. Тогда его выигрыш будет в худшем случае min_j K(i, j), j=1..m. В этом случае он должен его максимизировать, то есть max_i min_j K(i, j)= min_j K(i_0, j). Эта стратегия существует, максимум есть, таких стратегий может быть несколько, и любая такая стратегия принесёт ему лучший результат. Эту стратегию будем обозначать _I_, нижней ценой игры, нижнее значение игры. |
Второй игрок. Предположим, он принял стратегию 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~. То есть, когда игрок знает действия противника, то его выигрыш будет не меньше, чем когда не он знает. | ||
| Строка 71: | Строка 71: | ||
Оценим эту разность по-другому: | Оценим эту разность по-другому: | ||
| - | _w_(x_1) - _w_(x_2) = K(x_1, y(x_1)) - K(x_2, y(x_2)) & | + | _w_(x_1) - _w_(x_2) = K(x_1, y(x_1)) - K(x_2, y(x_2)) ≤ K(x_1, y(x_2)) - K(x_1, y(x_2)) ≥ -ε |
Из этих двух сотношений получили то, что хотели: |_w_(x_1) - _w_(x_2)| ≤ ε, отсюда следует, что _w_ непрерывна по X. | Из этих двух сотношений получили то, что хотели: |_w_(x_1) - _w_(x_2)| ≤ ε, отсюда следует, что _w_ непрерывна по X. | ||
| Строка 92: | Строка 92: | ||
{| | {| | ||
|1 | |1 | ||
| - | | -3 | + | |-3 |
| - | | -2 | + | |-2 |
|- | |- | ||
|1 | |1 | ||
| Строка 238: | Строка 238: | ||
Получили седловую точку (1/2, 1/2). | Получили седловую точку (1/2, 1/2). | ||
| - | Игра с | + | Игра с ... времени. Есть два игрока --- подлодка и обороняемый объект. Игра происходит следующим образом: подлодка всплывает, а объект в момент времени y выпускает осветительную ракету освещает акваторию на отрезке y, y+d, если лодка всплывёт в этом интервале, то она будет уничтожена, иначе она уничтожит объект. Если лодка уничтожит объект, то платёж 1, иначе платеж 0 |
Здесь платёжная функция выглядит следующим образом: | Здесь платёжная функция выглядит следующим образом: | ||
| Строка 249: | Строка 249: | ||
Переходим к вопросу, связанному с существованием седловых точек. Покажем алгоритм поиска седловых точек. Сейчас более глубоко изучим этот вопрос. Для этого понадобится вспомнить некоторые утверждения из математического анализа, связанные с выпуклостью функций. | Переходим к вопросу, связанному с существованием седловых точек. Покажем алгоритм поиска седловых точек. Сейчас более глубоко изучим этот вопрос. Для этого понадобится вспомнить некоторые утверждения из математического анализа, связанные с выпуклостью функций. | ||
| - | '''Определение 1'''. Множество Y называется выпуклым, если & | + | '''Определение 1'''. Множество Y называется выпуклым, если &orall; y_1, y_2 ∈ Y, α ∈ (0,1): αy1+(1-α)y_2 ∈ Y. |
'''Определение 2.1'''. Функция f(y), y∈ Y называется выпуклой, если для ∀ y_!, y_2 ∈ Y (y_1 ≠ y_2) , α ∈ (0, 1), f(αy1+(1-α)y_2) ≤ αf(y1)+(1-α)f(y_2) | '''Определение 2.1'''. Функция f(y), y∈ Y называется выпуклой, если для ∀ y_!, y_2 ∈ Y (y_1 ≠ y_2) , α ∈ (0, 1), f(αy1+(1-α)y_2) ≤ αf(y1)+(1-α)f(y_2) | ||
| Строка 267: | Строка 267: | ||
* Строго вогнутая функция на выпуклом множестве имеет ровно одну точку максимума | * Строго вогнутая функция на выпуклом множестве имеет ровно одну точку максимума | ||
| - | Пусть дана f(x), x --- вектор (x_1, ..., x_n), если f ' '(x) --- неотрицательно определённая форма, то f(x) является выпуклой функцией. Если положительно, то строго выпуклой. Если неположительно определённая, то вогнутая, если отрицательно определённая, то строго вогнутая. | + | Пусть дана f(x), x --- вектор (x_1, ..., x_n), если f''(x) --- неотрицательно определённая форма, то f(x) является выпуклой функцией. Если положительно, то строго выпуклой. Если неположительно определённая, то вогнутая, если отрицательно определённая, то строго вогнутая. |
Рассмотрим пример. f(x_1, ..., x_n) = x_1^2 + x_2^2 + ... + x_n^2. Пкажем, что это строго выпуклая функция. Найдём f'(x) = (δf/δx_1, ..., δf/δx_n)=(2x_1, ..., 2x_n). | Рассмотрим пример. f(x_1, ..., x_n) = x_1^2 + x_2^2 + ... + x_n^2. Пкажем, что это строго выпуклая функция. Найдём f'(x) = (δf/δx_1, ..., δf/δx_n)=(2x_1, ..., 2x_n). | ||
