Тигры, 01 лекция (от 04 сентября)

Материал из eSyr's wiki.

(Различия между версиями)
Перейти к: навигация, поиск
(вычитка)
Строка 5: Строка 5:
В АИ принимают участие 2 игрока --- первый и второй игрок. Игр определяется тремя элементами: множество стратегий первого игрока X. Его иногда называют множеством чистых стратегий. Y --- множество стратегий второго игрока. K(x, y), X ∈ X, y ∈ Y --- платёжная функция. Почти всегда будем предполагать, что X и Y --- компактное множество в конечномерном евклидовом пространстве.
В АИ принимают участие 2 игрока --- первый и второй игрок. Игр определяется тремя элементами: множество стратегий первого игрока X. Его иногда называют множеством чистых стратегий. Y --- множество стратегий второго игрока. K(x, y), X ∈ X, y ∈ Y --- платёжная функция. Почти всегда будем предполагать, что X и Y --- компактное множество в конечномерном евклидовом пространстве.
-
Как происходит игра: первый игрок принимает стратегию x, второй --- y и вычисляет K(x, y). И выигрыш первого игрока --- K(x, y), выигрыш второго --- -K(x, y). В этом и заключается антагонизм, поскольку один хочет максимизировать K, другой --- минимизировать. Как искать стратегию 1 игроку --- если бы он знал, какую стратегию выберет второй игрок, то задача свелась к максимизации функции. Но мы будем рассматривать случай, когда каждый игрок не знает, какую стратегию выберет второй. Получилась неопределенность. И надо понять, что в этом случае делать. В основе принятия решений в этом случае лежит метод, рзщрб. Г., лежит метод наилучшего гарантированного рез-та. В этом случае, каждый игрок выбирает стратегию, которая приносит мкс. выигрыш в худшем случае.
+
Как происходит игра: первый игрок принимает стратегию x, второй --- y и вычисляет K(x, y). И выигрыш первого игрока --- K(x, y), выигрыш второго --- -K(x, y). В этом и заключается антагонизм, поскольку один хочет максимизировать K, другой --- минимизировать. Как искать стратегию 1 игроку --- если бы он знал, какую стратегию выберет второй игрок, то задача свелась к максимизации функции. Но мы будем рассматривать случай, когда каждый игрок не знает, какую стратегию выберет второй. Получилась неопределенность. И надо понять, что в этом случае делать. В основе принятия решений в этом случае лежит метод, разработанный Г., лежит метод наилучшего гарантированного результата. В этом случае, каждый игрок выбирает стратегию, которая приносит максимальный выигрыш в худшем случае.
-
Рассмотрим частный случай, который позволяет понять суть метода --- когда 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_, нижней ценой игры, нижнее значение игры.
+
Рассмотрим частный случай, который позволяет понять суть метода --- когда 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~.
+
Теорема 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~. То есть, когда игрок знает действия противника, то его выигрыш будет не меньше, чем когда не он знает.
-
Рзность ~I~ - _I_ называется ценой инфрмции. Если верх. и ниж. цены совп., то игроку нет никакой разницы, будут его инф. или нет. А если разность больше нуля, то инфй. имеет цену.
+
Разность ~I~ - _I_ называется ценой информации. Если верхняя и нижняя цены совпадают, то игроку нет никакой разницы, будут его информацией пользоваться, или нет. А если разность больше нуля, то информация имеет цену.
-
Рассмотрим примеры. Конечные игры они здаются в иде матрицы. Рассм. ткй пример:
+
Рассмотрим примеры. Конечные игры они задаются в виде матрицы. Рассмотрим такой пример:
{|
{|
|1
|1
Строка 27: Строка 27:
|1
|1
|}
|}
-
Номер строки --- стратегия первого игрока, номер столбца --- стртегия второго. То есть, i=1..2, j=1..3. Как будет действ. первый игрок в усл. неопри.: Если первый игрок применяет первую стртегию, то он длжен рассчитывать на худший выигрыш, на 0, в втором случае получае 1. Тгда по принципу нилучш. гарант. рез-та н выбирает вторую стратегию, и нижняя граница --- 1.
+
Номер строки --- стратегия первого игрока, номер столбца --- стратегия второго. То есть, i=1..2, j=1..3. Как будет действовать первый игрок в условиях неопределённости: Если первый игрок применяет первую стратегию, то он должен рассчитывать на худший выигрыш, на 0, в втором случае получает 1. Тогда по принципу наилучшего гарантированного результата он выбирает вторую стратегию, и нижняя граница --- 1.
-
Втрой игрок. Если применит первую, то проигрыш 2 ед., если вторую --- 4 единицы, если третью --- 1 единица. В такм случае ~I~ = 1. Здесь _I_ = ~I~
+
Второй игрок. Если применит первую, то проигрыш 2 единицы, если вторую --- 4 единицы, если третью --- 1 единица. В такм случае ~I~ = 1. Здесь _I_ = ~I~
Рассмотрим ещё одни пример:
Рассмотрим ещё одни пример:
Строка 43: Строка 43:
_I_ = 1, ~I~ = 2. Здесь уже _I_ < ~I~
_I_ = 1, ~I~ = 2. Здесь уже _I_ < ~I~
-
Перейдём к случаю, кгда X, Y --- беск. множества.
+
Перейдём к случаю, кгда X, Y --- бесконечные множества.
-
В этм случае первый игрок мжет раск. на выигрыш inf_y ∈ Y K(x, y). Чт должен делать игрок --- макс. эту вел-ну, и она в итоге наз. нижней ценой _I_. Пусть супремум достигется в x_0, то есть _I_ = inf_y ∈ Y K(x_0, y). Аналогично для второго игрока inf_y ∈ Y sup_x ∈ X K(x, y) = ~I~ = sup_x ∈ X K(x, y_0)
+
В этом случае первый игрок может раск. на выигрыш inf_y ∈ Y K(x, y). Что должен делать игрок --- максимизировать эту величину, и она в итоге называется нижней ценой _I_. Пусть супремум достигается в x_0, то есть _I_ = inf_y ∈ Y K(x_0, y). Аналогично для второго игрока inf_y ∈ Y sup_x ∈ X K(x, y) = ~I~ = sup_x ∈ X K(x, y_0)
-
Терема 2. Аналогична первой, кторую мы доказали: _I_ ≤ ~I~ в случае беск. ант. игр.
+
'''Теорема 2'''. Аналогична первой, которую мы доказали: _I_ ≤ ~I~ в случае бесконечных антагонистических игр.
-
Док-во.
+
'''Доказательство.'''
* inf_y ∈ Y K(x, y) ≤ K(x, y) ≤ sup_x ∈ X K(x, y)
* inf_y ∈ Y K(x, y) ≤ K(x, y) ≤ sup_x ∈ X K(x, y)
* inf_y ∈ Y K(x, y) ≤ sup_x ∈ X K(x, y)
* inf_y ∈ Y K(x, y) ≤ sup_x ∈ X K(x, y)
Строка 55: Строка 55:
* _I_ ≤ ~I~
* _I_ ≤ ~I~
-
Терема 3. Если K(x, y) --- непр. на X×Y функция, где X, Y --- компакты, то такие функции _w_(x) = min_{y ∈ Y} K(x, y) и ~w~(x) = max_{x ∈ X} K(x, y) --- нерперывны.
+
'''Теорема 3'''. Если K(x, y) --- непрерывная на X×Y функция, где X, Y --- компакты, то такие функции _w_(x) = min_{y ∈ Y} K(x, y) и ~w~(x) = max_{x ∈ X} K(x, y) --- непрерывны.
-
Эт позволит писать min/max вместо inf/sup.
+
Это позволит писать min/max вместо inf/sup.
Докажем первую часть.
Докажем первую часть.
-
Поск ... непр, то ∀ ε > 0: ∃ δ ρ((x_1, y_1), (x_2, y_2)) ≤ δ ⇒ |K(x_1, y_1) - K(x_2, y_2)| ≤ ε
+
Поскольку K(x,y) непр, то ∀ ε > 0: ∃ δ ρ((x_1, y_1), (x_2, y_2)) ≤ δ ⇒ |K(x_1, y_1) - K(x_2, y_2)| ≤ ε
-
Зафикс. ε > 0. δ gt; 0 x_!, x_2 ∈ X,: ρ(x_!, x_2) ≤ δ
+
Зафиксируем ε > 0. δ gt; 0 x_!, x_2 ∈ X,: ρ(x_!, x_2) ≤ δ
min_{y ∈ Y} K(x, y) = K(x_1, y(x))
min_{y ∈ Y} K(x, y) = K(x_1, y(x))
Строка 69: Строка 69:
_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_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_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) = 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.
Следствие. Если _w_, ~w~ непрерывны, то нижняя цена _I_ = max_{x ∈ X} min_{y ∈ Y} K(x, y), аналогично ~I~ = min_{y ∈ Y} max_{x ∈ X} K(x, y)
Следствие. Если _w_, ~w~ непрерывны, то нижняя цена _I_ = max_{x ∈ X} min_{y ∈ Y} K(x, y), аналогично ~I~ = min_{y ∈ Y} max_{x ∈ X} K(x, y)
-
Перейдём к одному из основополгающих понятий теории АИ --- понятие седловой точки.
+
Перейдём к одному из основополагающих понятий теории АИ --- понятие седловой точки.
-
Мы рассм. АИ на мн. стратегий X×Y.
+
Мы рассмотрим АИ на множестве стратегий X×Y.
-
Пра (x, y) наз. седловой точкой игры (функции), если K(x, y_0) ≤ K(x_0, y_0) ≤ K(x_0, y) при всех ∀ x ∈ X, y ∈ Y.
+
Пара (x, y) называется седловой точкой игры (функции), если K(x, y_0) ≤ K(x_0, y_0) ≤ K(x_0, y) при всех ∀ x ∈ X, y ∈ Y.
-
Что озн. наличие седл. точки: если первый игрок будет откл. от x_0, то его выигрыш может только уменьш, а если вторй игр. будет откл., то его проигрыш будет тлько увел.
+
Что означает наличие седловой точки: если первый игрок будет отклоняться от x_0, то его выигрыш может только уменьшиться, а если второй игрок будет отклоняться, то его проигрыш будет только увеличиваться.
-
Сейчас мы докажем, что это и есть оптимальные стратегии, и цена инф. равна 0. А если силовой точки нет, т верхняя цена оказывается строго больше нижней, и цена инф. строго неотр.
+
Сейчас мы докажем, что это и есть оптимальные стратегии, и цена информации равна 0. А если седловой точки нет, то верхняя цена оказывается строго больше нижней, и цена информации строго неотрицательна.
-
Рассмотрим случайк конечнй игры и перепишем усл. седловй точки: K(i, j_0) ≤ K(i_0, j_0) ≤ K(i_0, j) при ∀ i = 1..n, j = 1..m.
+
Рассмотрим случай конечной игры и перепишем условие седловой точки: K(i, j_0) ≤ K(i_0, j_0) ≤ K(i_0, j) при ∀ i = 1..n, j = 1..m.
Рассмотрим следующую платёжную матрицу:
Рассмотрим следующую платёжную матрицу:
Строка 104: Строка 104:
|}
|}
-
Чт такое седл. элемент --- элемент, кторый максимальный в стлбце и минимальный в строке. В данной матрице элемент (i=3, j=1) минимален. Теперь в этой матрице обр. внимание на следующее: вычислим _I_ и ~I~: _I_ = 2, ~I~ = 2. Здесь верхняя цена равна нижней.
+
Что такое седловой элемент --- элемент, который максимальный в столбце и минимальный в строке. В данной матрице элемент (i=3, j=1) минимален. Теперь в этой матрице обратим внимание на следующее: вычислим _I_ и ~I~: _I_ = 2, ~I~ = 2. Здесь верхняя цена равна нижней.
-
Теперь рассм. другую матрицу:
+
Теперь рассмотрим другую матрицу:
2 3 4 1
2 3 4 1
5 2 2 3
5 2 2 3
4 1 3 2
4 1 3 2
-
Оценим здесь _I_ и ~I~: _I_ = 2, ~I~ = 3. Здесь верх. цена оказалась больше, чем нижняя.
+
Оценим здесь _I_ и ~I~: _I_ = 2, ~I~ = 3. Здесь верхняя цена оказалась больше, чем нижняя.
-
Обобщим это: если седл. тчка сущ., т цены совп, иначе верх. бльше нижней.
+
Обобщим это: если седловая точка существует, то цены совпадают, иначе верхняя больше нижней.
-
Теорема 4. В матричной ант. игре седлвая точка существует тогда и только тогда, когда _I_=~I~. Если (i_0, j_0) --- силовая точка, то K(i_0, j_0) = _I_=~I~. И i_0, j_0 --- наилучшие гарант. стратегии.
+
'''Теорема 4'''. В матричной антагонистической игре седловая точка существует тогда и только тогда, когда _I_=~I~. Если (i_0, j_0) --- седловая точка, то K(i_0, j_0) = _I_=~I~. И i_0, j_0 --- наилучшие гарантированные стратегии.
-
Доказательство. Первя часть. a) Предпложим, чт нижняя цена равна верхней. Пусть i_0 и j_0 --- оптимальные гарант. стратегии. Тогда из опр. имеем следующее: max_i min_j K(i, j) = min_j K(i_0, j). Это нижняя цена игры. В свю чередь, min_j K(i_0, j) ≤ K(i_0, j). В свю очередь, ~I~ = min_j max_i K(i, j) = max_i K(i, j_0) и поск. мы ерём максимум, то Kmax_i K(i, j_0) ≥ K(i, j_0). Но _I_ = ~I~, тогда K(i, j_0) ≤ K(i_0, j) ∀ i = 1..n, j = 1..m. Покажем, что i_0, j_0 --- седловя точка. Откуда это следует? но верн при всех i, в частнсти, при i_0: i=i_0: K(i_0, j_0) ≤ K(i_0, j), оно верно при j=j_0: K(i, j_0) ≤ K(i_0, j_0). Отсюда получаем K(i, j_0) ≤ K(i_0, j_0) ≤ K(i_0, j) ∀ i = 1..n, j = 1..m, то есть (i_0, j_0) --- седловая точка.
+
'''Доказательство'''. Первая часть. a) Предположим, что нижняя цена равна верхней. Пусть i_0 и j_0 --- оптимальные гарантированные стратегии. Тогда из определения имеем следующее: max_i min_j K(i, j) = min_j K(i_0, j). Это нижняя цена игры. В свою чередь, min_j K(i_0, j) ≤ K(i_0, j). В свою очередь, ~I~ = min_j max_i K(i, j) = max_i K(i, j_0) и поскольку мы берём максимум, то Kmax_i K(i, j_0) ≥ K(i, j_0). Но _I_ = ~I~, тогда K(i, j_0) ≤ K(i_0, j) ∀ i = 1..n, j = 1..m. Покажем, что i_0, j_0 --- седловая точка. Откуда это следует? Оно верно при всех i, в частности, при i_0: i=i_0: K(i_0, j_0) ≤ K(i_0, j), оно верно при j=j_0: K(i, j_0) ≤ K(i_0, j_0). Отсюда получаем K(i, j_0) ≤ K(i_0, j_0) ≤ K(i_0, j) ∀ i = 1..n, j = 1..m, то есть (i_0, j_0) --- седловая точка.
-
Вторая часть первой части теремы. Необх. условие. (i_0, j_0) --- седловая точка. Тогда по определению K(i, j_0) ≤ K(i_0, j_0) ≤ K(i_0, j) ∀ i = 1..n, j = 1..m
+
Вторая часть первой части теоремы. Необходимое условие. (i_0, j_0) --- седловая точка. Тогда по определению K(i, j_0) ≤ K(i_0, j_0) ≤ K(i_0, j) ∀ i = 1..n, j = 1..m
* max_i K(i, j_0) ≤ K(i_0, j_0) ≤ min_j K(i_0, j)
* max_i K(i, j_0) ≤ K(i_0, j_0) ≤ min_j K(i_0, j)
* min_j max_i K(i, j) ≤ K(i_0, j_0) ≤ max_i min_j K(i, j)
* min_j max_i K(i, j) ≤ K(i_0, j_0) ≤ max_i min_j K(i, j)
* ~I~ ≤ _I_
* ~I~ ≤ _I_
-
Но мы знаем терему 1, из которой _I_ ≤ ~I~, тсюда _I_=~I~
+
Но мы знаем теорему 1, из которой _I_ ≤ ~I~, отсюда _I_=~I~
-
Первая чсть теор. доказана полностью. Псмтрим, что мы плучили. Поск. _I_=~I~ то там везде имеет место равенство, и, таким бразом, мы доказали вторую чсть теоремы.
+
Первая часть теоремы доказана полностью. Посмотрим, что мы получили. Поскольку _I_=~I~ то там везде имеет место равенство, и, таким образом, мы доказали вторую часть теоремы.
-
Теорема 5. Если ∃ стртегии i_0, j_0 и константа ''v'' такие, что K(i, j_0) ≤ ''v'' ≤ K(i_0, j) при ∀ i=1..n, j=1..m, то пара i_0, j_0 обр. седл. точку и ''v'' = K(i_0, j_0)
+
'''Теорема 5'''. Если ∃ стратегии i_0, j_0 и константа ''v'' такие, что K(i, j_0) ≤ ''v'' ≤ K(i_0, j) при ∀ i=1..n, j=1..m, то пара i_0, j_0 образует седловую точку и ''v'' = K(i_0, j_0)
-
Доказательство. Из усл. теоремы следует, чт K(i, j_0) ≤ K(i_0, j) при ∀ i=1..n, j=1..m, а мы только что доказали, что из этого следует, что (i_0, j_0) --- седловая точка. Т.о. дказхали первую чсть.
+
'''Доказательство'''. Из условия теоремы следует, что K(i, j_0) ≤ K(i_0, j) при ∀ i=1..n, j=1..m, а мы только что доказали, что из этого следует, что (i_0, j_0) --- седловая точка. Т.о. доказали первую часть.
-
Поск. можно взять i,j любые, т мжн взять i=i_0, j=j_0, и получаем K(i_0, j_0) ≤ ''v'' ≤ K(i_0, j_0) ⇒ ''v'' = K(i_0, j_0)
+
Поскольку можно взять i,j любые, то можно взять i=i_0, j=j_0, и получаем K(i_0, j_0) ≤ ''v'' ≤ K(i_0, j_0) ⇒ ''v'' = K(i_0, j_0)
-
На этом с матр. играми пока всё. Взвр. к беск. играм.
+
На этом с матричными играми пока всё. Возвращаемся к бесконечным играм.
Рассматриваем K(x, y) на X×Y.
Рассматриваем K(x, y) на X×Y.
-
Теорем 6. Игра K(x, y) имеет седл. тчку т. и тт., когда max_{x ∈ X} inf_{y ∈ Y} K(x, y) = min_{y ∈ Y} sup_{x ∈ X} K(x, y) (то есть тчка эта дстигется). 2) (x_0, y_0) -- ct ⇒ K(x_0, y_0) = max_x inf_y K(x, y) = min_y sup_x K(x, y)
+
'''Теорема 6'''. Игра K(x, y) имеет седловую точку тогда и только тогда, когда max_{x ∈ X} inf_{y ∈ Y} K(x, y) = min_{y ∈ Y} sup_{x ∈ X} K(x, y) (то есть точка эта достигается). 2) (x_0, y_0) -- ct ⇒ K(x_0, y_0) = max_x inf_y K(x, y) = min_y sup_x K(x, y)
-
Доказательство. 1) x_0, y_0. min_x inf_y K(x, y) = inf_y K(x_0, y) ≤ K(x_0, y) ∀ y ∈ Y
+
'''Доказательство'''. 1) x_0, y_0. min_x inf_y K(x, y) = inf_y K(x_0, y) ≤ K(x_0, y) ∀ y ∈ Y
* min_y sup_x K(x, y) = sup_x K(x, y_0) ≥ K(x, y_0), ∀ x ∈ X
* min_y sup_x K(x, y) = sup_x K(x, y_0) ≥ K(x, y_0), ∀ x ∈ X
-
* Эти две вещи равны, пэтму полчуаем K(x, y_0) ≤ K(x_0, y) ∀ x ∈ X, y ∈ Y
+
* Эти две вещи равны, поэтому получаем K(x, y_0) ≤ K(x_0, y) ∀ x ∈ X, y ∈ Y
* x=x_0: K(x_0, y_0) ≤ K(x_0, y)
* x=x_0: K(x_0, y_0) ≤ K(x_0, y)
* y=y_0: K(x, y_0) ≤ K(x_0, y_0)
* y=y_0: K(x, y_0) ≤ K(x_0, y_0)
-
тсюда СТ.
+
отсюда СТ.
2) (x_0, y_0) --- СТ
2) (x_0, y_0) --- СТ
-
* (аналгично Т4)
 
- 
-
Что мы получили, на самом деле. Мы на самом деле плучили равенство. Что это означает? Это означает, что ...
 
* (аналогично Т4)
* (аналогично Т4)
-
Это озн., чт inf достигется в y=y_0, указнный supдостигается при x=x_0. Это значит, что мы мжем записать min_y sup_x K(x, y) = max_x inf_y K(x, y)
 
-
Т.. теорема ок. плностью.
+
Что мы получили, на самом деле. Мы на самом деле получили равенство. Что это означает? Это означает, что ...
 +
* (аналогично Т4)
 +
Это означает, что inf достигается в y=y_0, указанный sup достигается при x=x_0. Это значит, что мы можем записать min_y sup_x K(x, y) = max_x inf_y K(x, y)
-
<!-- перерыв -->
+
Таким образом, теорема доказана полностью.
(Про экзамен) <!-- лектор - мудак -->
(Про экзамен) <!-- лектор - мудак -->
Строка 186: Строка 184:
K(x, y) = 1 - (x-y)^2 X=Y=[0, 1]
K(x, y) = 1 - (x-y)^2 X=Y=[0, 1]
-
_w_(x) = min_{y &isin; [0, 1]} = {1-x^2, x &gt; 0.5 (y=0); 1-(1-x)^2, x&le; 0.5 (y=1)} Теперь он должен взять максимум от этой величины. Псмтрим графически, что здесь плучется. То есть, наилуч. стратиегия для первог игрока --- x_0 = 1/2. Это в случае, когд игрок не информирован.
+
_w_(x) = min_{y &isin; [0, 1]} = {1-x^2, x &gt; 0.5 (y=0); 1-(1-x)^2, x&le; 0.5 (y=1)} Теперь он должен взять максимум от этой величины. Посмотрим графически, что здесь получается. То есть, наилучшая стратегия для первого игрока --- x_0 = 1/2. Это в случае, когда игрок не информирован.
-
Заметим, что здесь же мы описали, как будет действовать второй игрок, когд он информирован.
+
Заметим, что здесь же мы описали, как будет действовать второй игрок, когда он информирован.
-
Как должен действовать, как будет дейтсввать второй, когд он не инфрмирован (как должен действовать первый, когд он информирован).
+
Как должен действовать, как будет действовать второй, когда он не информирован (как должен действовать первый, когда он информирован).
* 1-x^2=1-(1-x)^2
* 1-x^2=1-(1-x)^2
Строка 198: Строка 196:
~w~(y) = max_y
~w~(y) = max_y
-
Получили, что ~w~ &gt; _w_, значмит, седловой тчки нет.
+
Получили, что ~w~ &gt; _w_, значит, седловой точки нет.
-
Следующие дв примера более конкретны. Они имеют в литературе название "дуэльные игры".
+
Следующие два примера более конкретны. Они имеют в литературе название "дуэльные игры".
-
Первая дуэль назывется "бесшумная дуэль". Два игрока сближаются и могут произвести один выстрел. Произвести выстрелы они могут в сомент времени x,y &isin; [0, 1]. Дальше известны функции меткости: p(x), q(y). Что таке p(x) --- вероятнсть поржения первым игроком вторго игрока, если он произв. выстрел в ммент времени x. Функция меткости возрастающая.
+
Первая дуэль называется "бесшумная дуэль". Два игрока сближаются и могут произвести один выстрел. Произвести выстрелы они могут в момент времени x,y &isin; [0, 1]. Дальше известны функции меткости: p(x), q(y). Что такое p(x) --- вероятность поражения первым игроком второго игрока, если он произвёл выстрел в момент времени x. Функция меткости возрастающая.
-
Платёж следующий: 1, если 1 игрок празил второго, -1 если наоборот, 0 в двух стльных случаях. Берётся матожидание. Если x<y, т есть первый игрк стреляет первым. Вспомним, что такое матжидание --- берётся сумма произв. арг. на вер. То есть, 1*p(x) + (1-p(x))*q(y)*(-1) + 0 * (...) В итоге получается p(x) - (1-p(x))*q(y) (кгда x&lt;y). Когда x=y, то получаем p(x)(1-q(x)) - (1-p(x))q(x). Когда x>y, полоучается -q(y)+(1-q(y))p(x).
+
Платёж следующий: 1, если 1 игрок поразил второго, -1 если наоборот, 0 в двух остальных случаях. Берётся матожидание. Если x<y, то есть первый игрок стреляет первым. Вспомним, что такое матожидание --- берётся сумма произвольных аргументов на вероятность. То есть, 1*p(x) + (1-p(x))*q(y)*(-1) + 0 * (...) В итоге получается p(x) - (1-p(x))*q(y) (когда x&lt;y). Когда x=y, то получаем p(x)(1-q(x)) - (1-p(x))q(x). Когда x>y, полоучается -q(y)+(1-q(y))p(x).
-
Эти дуэли бесшумные, поск. если первый игрк произв. выстрел и промхивается, то втрй игрок это не слышал. В шумняых, если первый выстрелил и прмазал, то второй будет стрелять не в момент времени y, а в момент 1, когда верятность макс.. В случае, если p(x) = x, q(y) = y, получим
+
Эти дуэли бесшумные, поскольку если первый игрок производит выстрел и промахивается, то второй игрок это не слышал. В шумных, если первый выстрелил и промазал, то второй будет стрелять не в момент времени y, а в момент 1, когда вероятность максимальна. В случае, если p(x) = x, q(y) = y, получим
x-y+xy, x<y
x-y+xy, x<y
K(x, y) = 0, x=y
K(x, y) = 0, x=y
Строка 212: Строка 210:
Посчитаем выигрыш. стратегии.
Посчитаем выигрыш. стратегии.
-
Рассм, как выглядит функция при фикс. x.
+
Рассмотрим, как выглядит функция при фиксированном x.
_w_(x) = inf_y K(x, y) = min(-x_2, 2x-1), max_x _w_(x)
_w_(x) = inf_y K(x, y) = min(-x_2, 2x-1), max_x _w_(x)
-
x=sqrt(2)-1 --- опт. знач. джля первого игрока, и нижняя цена игрока _I_=2sqrt(2)-3, если то же саме повторить за второго игрока, т полочим, что ~I~=3-2sqrt(2) и y=sqrt(2)-1
+
x=sqrt(2)-1 --- оптимальное значение для первого игрока, и нижняя цена игрока _I_=2sqrt(2)-3, если то же самое повторить за второго игрока, то получим, что ~I~=3-2sqrt(2) и y=sqrt(2)-1
-
 
+
-
<!-- педедыв -->
+
-
Вторая модель --- шумная дуэль. Отличется от бесшумнй только тем, чт если один из игроков произв. выстрел и прмахивается, то второй игрок об этом узнаёт. Поэтому, когдо он узнаёт, то стрелять он будет в ммент, когда будет максимально, в момент 1.
+
Вторая модель --- шумная дуэль. Отличается от бесшумной только тем, что если один из игроков производит выстрел и промахивается, то второй игрок об этом узнаёт. Поэтому, когда он узнаёт, то стрелять он будет в момент, когда будет максимально, в момент 1.
Посчитаем вероятности:
Посчитаем вероятности:
Строка 240: Строка 236:
Аналогично для первого игрока _I_=0, x=1/2
Аналогично для первого игрока _I_=0, x=1/2
-
Плучили седловую точку (1/2, 1/2).
+
Получили седловую точку (1/2, 1/2).
-
Игра с ... времени. Есть два игрока --- пдлодка и обороняемый объект. Игра присх. след. обрзом: подлдка всплываем, а объект в момент времени y выпуск. осветительную ракету освещает акватриум на отрезке y, y+d, если лодка всплывёт в этом интервале, то она будет уничтжена, иначе она уничт. объект. Если лодка уничт. бъект, то платёж 1, иначе платеж 0
+
Игра с ... времени. Есть два игрока --- подлодка и обороняемый объект. Игра происходит следующим образом: подлодка всплывает, а объект в момент времени y выпускает осветительную ракету освещает акваторию на отрезке y, y+d, если лодка всплывёт в этом интервале, то она будет уничтожена, иначе она уничтожит объект. Если лодка уничтожит объект, то платёж 1, иначе платеж 0
-
Здесь плат. функция выглядит след. образом:
+
Здесь платёжная функция выглядит следующим образом:
1, x<y или y > y+d
1, x<y или y > y+d
K(x, y) = 0, x &isin; [y, y+d]
K(x, y) = 0, x &isin; [y, y+d]
-
В любй момент минимум 0, пэтому Нижняя цена равна 0, поэтму птимальным является любй момент. То же для втрого игрока --- в любом случае максимум 1, ~I~=1, тчка любая, и седловой точки здесь нет.
+
В любой момент минимум 0, поэтому нижняя цена равна 0, поэтому оптимальным является любой момент. То же для второго игрока --- в любом случае максимум 1, ~I~=1, точка любая, и седловой точки здесь нет.
-
Перехдим к вопросу, связанному с существованию седловых точек. Покжем алгоритм поиска седловых точек. Сейчас более глубок изучим этт вопрос. Для этг понадобится вспомнить нек-рые утверждения из мат. анализа, связнные с вып. функций.
+
Переходим к вопросу, связанному с существованием седловых точек. Покажем алгоритм поиска седловых точек. Сейчас более глубоко изучим этот вопрос. Для этого понадобится вспомнить некоторые утверждения из математического анализа, связанные с выпуклостью функций.
-
Определение 1. Мнжество Y называется выпуклым, если &orall; y_1, y_2 &isin; Y, &alpha; &isin; (0,1): &alpha;y1+(1-&alpha;)y_2 &isin; Y.
+
'''Определение 1'''. Множество Y называется выпуклым, если &orall; y_1, y_2 &isin; Y, &alpha; &isin; (0,1): &alpha;y1+(1-&alpha;)y_2 &isin; Y.
-
Определение 2.1 Функция f(y), y&isin; Y наз. выпуклой, если для &forall; y_!, y_2 &isin; Y (y_1 &ne; y_2) , &alpha; &isin; (0, 1), f(&alpha;y1+(1-&alpha;)y_2) &le; &alpha;f(y1)+(1-&alpha;)f(y_2)
+
'''Определение 2.1'''. Функция f(y), y&isin; Y называется выпуклой, если для &forall; y_!, y_2 &isin; Y (y_1 &ne; y_2) , &alpha; &isin; (0, 1), f(&alpha;y1+(1-&alpha;)y_2) &le; &alpha;f(y1)+(1-&alpha;)f(y_2)
-
Опр. 2.2 Функция f(y), y&isin; Y наз. строго выпуклой, если для &forall; y_!, y_2 &isin; Y (y_1 &ne; y_2) , &alpha; &isin; (0, 1), f(&alpha;y1+(1-&alpha;)y_2) &lt; &alpha;f(y1)+(1-&alpha;)f(y_2)
+
'''Определение 2.2'''. Функция f(y), y&isin; Y называется строго выпуклой, если для &forall; y_!, y_2 &isin; Y (y_1 &ne; y_2) , &alpha; &isin; (0, 1), f(&alpha;y1+(1-&alpha;)y_2) &lt; &alpha;f(y1)+(1-&alpha;)f(y_2)
-
Определение 2.3 Функция f(y), y&isin; Y наз. вогнутой, если для &forall; y_!, y_2 &isin; Y (y_1 &ne; y_2) , &alpha; &isin; (0, 1), f(&alpha;y1+(1-&alpha;)y_2) &ge; &alpha;f(y1)+(1-&alpha;)f(y_2)
+
'''Определение 2.3'''. Функция f(y), y&isin; Y называется вогнутой, если для &forall; y_!, y_2 &isin; Y (y_1 &ne; y_2) , &alpha; &isin; (0, 1), f(&alpha;y1+(1-&alpha;)y_2) &ge; &alpha;f(y1)+(1-&alpha;)f(y_2)
-
Опр. 2.4 Функция f(y), y&isin; Y наз. строго вогнутой, если для &forall; y_!, y_2 &isin; Y (y_1 &ne; y_2) , &alpha; &isin; (0, 1), f(&alpha;y1+(1-&alpha;)y_2) &gt; &alpha;f(y1)+(1-&alpha;)f(y_2)
+
'''Определение 2.4'''. Функция f(y), y&isin; Y называется строго вогнутой, если для &forall; y_!, y_2 &isin; Y (y_1 &ne; y_2) , &alpha; &isin; (0, 1), f(&alpha;y1+(1-&alpha;)y_2) &gt; &alpha;f(y1)+(1-&alpha;)f(y_2)
Утверждения.
Утверждения.
* Сумма двух выпуклых функций есть выпуклая функция
* Сумма двух выпуклых функций есть выпуклая функция
-
* Сумма вып. и строго вып. --- строго вып.
+
* Сумма выпуклой и строго выпуклой --- строго выпукла.
-
* Аналогично для вгнутых.
+
* Аналогично для вогнутых.
-
Доказать самост.
+
Доказать самостоятельно.
-
* Строго вып. функция на вып. м-ве имеет ровно дну тчку минимума
+
* Строго выпуклая функция на выпуклом множестве имеет ровно одну точку минимума
-
* Строго вогн. функция на вып. мн-ве имеет ровно одну т. максимума
+
* Строго вогнутая функция на выпуклом множестве имеет ровно одну точку максимума
-
Пусть дана 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) = (&delta;f/&delta;x_1, ..., &delta;f/&delta;x_n)=(2x_1, ..., 2x_n).
+
Рассмотрим пример. f(x_1, ..., x_n) = x_1^2 + x_2^2 + ... + x_n^2. Пкажем, что это строго выпуклая функция. Найдём f'(x) = (&delta;f/&delta;x_1, ..., &delta;f/&delta;x_n)=(2x_1, ..., 2x_n).
( &delta;^2f/&delta;x_1&delta;x_1, ..., &delta;^2f/&delta;x_1&delta;x_n ) (2 ... 0 )
( &delta;^2f/&delta;x_1&delta;x_1, ..., &delta;^2f/&delta;x_1&delta;x_n ) (2 ... 0 )
f''(x)=( ... ) = ( ... )
f''(x)=( ... ) = ( ... )
( &delta;^2f/&delta;x_n&delta;x_1, ..., &delta;^2f/&delta;x_n&delta;x_n ) (0 ... 2 )
( &delta;^2f/&delta;x_n&delta;x_1, ..., &delta;^2f/&delta;x_n&delta;x_n ) (0 ... 2 )
-
Эта фрма полож. опр. Значит, функция строго вып.
+
Эта форма положительно определённая. Значит, функция строго выпуклая.
{{Тигры}}
{{Тигры}}
-
{{Lection-stub}}
 

Версия 06:36, 13 октября 2010

Раздел 1. Антагонистические игры (АИ)

В АИ принимают участие 2 игрока --- первый и второй игрок. Игр определяется тремя элементами: множество стратегий первого игрока X. Его иногда называют множеством чистых стратегий. Y --- множество стратегий второго игрока. K(x, y), X &in; X, y &in; Y --- платёжная функция. Почти всегда будем предполагать, что X и Y --- компактное множество в конечномерном евклидовом пространстве.

Как происходит игра: первый игрок принимает стратегию x, второй --- y и вычисляет K(x, y). И выигрыш первого игрока --- K(x, y), выигрыш второго --- -K(x, y). В этом и заключается антагонизм, поскольку один хочет максимизировать K, другой --- минимизировать. Как искать стратегию 1 игроку --- если бы он знал, какую стратегию выберет второй игрок, то задача свелась к максимизации функции. Но мы будем рассматривать случай, когда каждый игрок не знает, какую стратегию выберет второй. Получилась неопределенность. И надо понять, что в этом случае делать. В основе принятия решений в этом случае лежит метод, разработанный Г., лежит метод наилучшего гарантированного результата. В этом случае, каждый игрок выбирает стратегию, которая приносит максимальный выигрыш в худшем случае.

Рассмотрим частный случай, который позволяет понять суть метода --- когда 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~.

Теорема 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~. То есть, когда игрок знает действия противника, то его выигрыш будет не меньше, чем когда не он знает.

Разность ~I~ - _I_ называется ценой информации. Если верхняя и нижняя цены совпадают, то игроку нет никакой разницы, будут его информацией пользоваться, или нет. А если разность больше нуля, то информация имеет цену.

Рассмотрим примеры. Конечные игры они задаются в виде матрицы. Рассмотрим такой пример:

1 2 0
2 4 1

Номер строки --- стратегия первого игрока, номер столбца --- стратегия второго. То есть, i=1..2, j=1..3. Как будет действовать первый игрок в условиях неопределённости: Если первый игрок применяет первую стратегию, то он должен рассчитывать на худший выигрыш, на 0, в втором случае получает 1. Тогда по принципу наилучшего гарантированного результата он выбирает вторую стратегию, и нижняя граница --- 1.

Второй игрок. Если применит первую, то проигрыш 2 единицы, если вторую --- 4 единицы, если третью --- 1 единица. В такм случае ~I~ = 1. Здесь _I_ = ~I~

Рассмотрим ещё одни пример:

1 2 3
2 4 0

_I_ = 1, ~I~ = 2. Здесь уже _I_ < ~I~

Перейдём к случаю, кгда X, Y --- бесконечные множества.

В этом случае первый игрок может раск. на выигрыш inf_y ∈ Y K(x, y). Что должен делать игрок --- максимизировать эту величину, и она в итоге называется нижней ценой _I_. Пусть супремум достигается в x_0, то есть _I_ = inf_y ∈ Y K(x_0, y). Аналогично для второго игрока inf_y ∈ Y sup_x ∈ X K(x, y) = ~I~ = sup_x ∈ X K(x, y_0)

Теорема 2. Аналогична первой, которую мы доказали: _I_ ≤ ~I~ в случае бесконечных антагонистических игр.

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

  • inf_y ∈ Y K(x, y) ≤ K(x, y) ≤ sup_x ∈ X K(x, y)
  • inf_y ∈ Y K(x, y) ≤ sup_x ∈ X K(x, y)
  • sup_x ∈ X inf_y ∈ Y K(x, y) ≤ sup_x ∈ X K(x, y)
  • _I_ ≤ ~I~

Теорема 3. Если K(x, y) --- непрерывная на X×Y функция, где X, Y --- компакты, то такие функции _w_(x) = min_{y ∈ Y} K(x, y) и ~w~(x) = max_{x ∈ X} K(x, y) --- непрерывны.

Это позволит писать min/max вместо inf/sup.

Докажем первую часть.

Поскольку K(x,y) непр, то ∀ ε > 0: ∃ δ ρ((x_1, y_1), (x_2, y_2)) ≤ δ ⇒ |K(x_1, y_1) - K(x_2, y_2)| ≤ ε

Зафиксируем ε > 0. δ gt; 0 x_!, x_2 ∈ X,: ρ(x_!, x_2) ≤ δ

min_{y ∈ Y} K(x, y) = K(x_1, y(x))

_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_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_, ~w~ непрерывны, то нижняя цена _I_ = max_{x ∈ X} min_{y ∈ Y} K(x, y), аналогично ~I~ = min_{y ∈ Y} max_{x ∈ X} K(x, y)

Перейдём к одному из основополагающих понятий теории АИ --- понятие седловой точки.

Мы рассмотрим АИ на множестве стратегий X×Y.

Пара (x, y) называется седловой точкой игры (функции), если K(x, y_0) ≤ K(x_0, y_0) ≤ K(x_0, y) при всех ∀ x ∈ X, y ∈ Y.

Что означает наличие седловой точки: если первый игрок будет отклоняться от x_0, то его выигрыш может только уменьшиться, а если второй игрок будет отклоняться, то его проигрыш будет только увеличиваться.

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

Рассмотрим случай конечной игры и перепишем условие седловой точки: K(i, j_0) ≤ K(i_0, j_0) ≤ K(i_0, j) при ∀ i = 1..n, j = 1..m.

Рассмотрим следующую платёжную матрицу:

1
1 5 4
2 3 2

Что такое седловой элемент --- элемент, который максимальный в столбце и минимальный в строке. В данной матрице элемент (i=3, j=1) минимален. Теперь в этой матрице обратим внимание на следующее: вычислим _I_ и ~I~: _I_ = 2, ~I~ = 2. Здесь верхняя цена равна нижней.

Теперь рассмотрим другую матрицу:

2 3 4 1
5 2 2 3
4 1 3 2

Оценим здесь _I_ и ~I~: _I_ = 2, ~I~ = 3. Здесь верхняя цена оказалась больше, чем нижняя.

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

Теорема 4. В матричной антагонистической игре седловая точка существует тогда и только тогда, когда _I_=~I~. Если (i_0, j_0) --- седловая точка, то K(i_0, j_0) = _I_=~I~. И i_0, j_0 --- наилучшие гарантированные стратегии.

Доказательство. Первая часть. a) Предположим, что нижняя цена равна верхней. Пусть i_0 и j_0 --- оптимальные гарантированные стратегии. Тогда из определения имеем следующее: max_i min_j K(i, j) = min_j K(i_0, j). Это нижняя цена игры. В свою чередь, min_j K(i_0, j) ≤ K(i_0, j). В свою очередь, ~I~ = min_j max_i K(i, j) = max_i K(i, j_0) и поскольку мы берём максимум, то Kmax_i K(i, j_0) ≥ K(i, j_0). Но _I_ = ~I~, тогда K(i, j_0) ≤ K(i_0, j) ∀ i = 1..n, j = 1..m. Покажем, что i_0, j_0 --- седловая точка. Откуда это следует? Оно верно при всех i, в частности, при i_0: i=i_0: K(i_0, j_0) ≤ K(i_0, j), оно верно при j=j_0: K(i, j_0) ≤ K(i_0, j_0). Отсюда получаем K(i, j_0) ≤ K(i_0, j_0) ≤ K(i_0, j) ∀ i = 1..n, j = 1..m, то есть (i_0, j_0) --- седловая точка.

Вторая часть первой части теоремы. Необходимое условие. (i_0, j_0) --- седловая точка. Тогда по определению K(i, j_0) ≤ K(i_0, j_0) ≤ K(i_0, j) ∀ i = 1..n, j = 1..m

  • max_i K(i, j_0) ≤ K(i_0, j_0) ≤ min_j K(i_0, j)
  • min_j max_i K(i, j) ≤ K(i_0, j_0) ≤ max_i min_j K(i, j)
  • ~I~ ≤ _I_

Но мы знаем теорему 1, из которой _I_ ≤ ~I~, отсюда _I_=~I~

Первая часть теоремы доказана полностью. Посмотрим, что мы получили. Поскольку _I_=~I~ то там везде имеет место равенство, и, таким образом, мы доказали вторую часть теоремы.

Теорема 5. Если ∃ стратегии i_0, j_0 и константа v такие, что K(i, j_0) ≤ v ≤ K(i_0, j) при ∀ i=1..n, j=1..m, то пара i_0, j_0 образует седловую точку и v = K(i_0, j_0)

Доказательство. Из условия теоремы следует, что K(i, j_0) ≤ K(i_0, j) при ∀ i=1..n, j=1..m, а мы только что доказали, что из этого следует, что (i_0, j_0) --- седловая точка. Т.о. доказали первую часть.

Поскольку можно взять i,j любые, то можно взять i=i_0, j=j_0, и получаем K(i_0, j_0) ≤ v ≤ K(i_0, j_0) ⇒ v = K(i_0, j_0)

На этом с матричными играми пока всё. Возвращаемся к бесконечным играм.

Рассматриваем K(x, y) на X×Y.

Теорема 6. Игра K(x, y) имеет седловую точку тогда и только тогда, когда max_{x ∈ X} inf_{y ∈ Y} K(x, y) = min_{y ∈ Y} sup_{x ∈ X} K(x, y) (то есть точка эта достигается). 2) (x_0, y_0) -- ct ⇒ K(x_0, y_0) = max_x inf_y K(x, y) = min_y sup_x K(x, y)

Доказательство. 1) x_0, y_0. min_x inf_y K(x, y) = inf_y K(x_0, y) ≤ K(x_0, y) ∀ y ∈ Y

  • min_y sup_x K(x, y) = sup_x K(x, y_0) ≥ K(x, y_0), ∀ x ∈ X
  • Эти две вещи равны, поэтому получаем K(x, y_0) ≤ K(x_0, y) ∀ x ∈ X, y ∈ Y
  • x=x_0: K(x_0, y_0) ≤ K(x_0, y)
  • y=y_0: K(x, y_0) ≤ K(x_0, y_0)

отсюда СТ.

2) (x_0, y_0) --- СТ

  • (аналогично Т4)

Что мы получили, на самом деле. Мы на самом деле получили равенство. Что это означает? Это означает, что ...

  • (аналогично Т4)

Это означает, что inf достигается в y=y_0, указанный sup достигается при x=x_0. Это значит, что мы можем записать min_y sup_x K(x, y) = max_x inf_y K(x, y)

Таким образом, теорема доказана полностью.

(Про экзамен)

Первое замечание.

Второе замечание.

0 1 0
3 2 3
0 1 2

Третье.

...

Отсюда следует, что K(x_1, y_2) ≤ K(x_1, y) ⇒ седловая точка.

Несколько примеров.

K(x, y) = 1 - (x-y)^2 X=Y=[0, 1]

_w_(x) = min_{y ∈ [0, 1]} = {1-x^2, x > 0.5 (y=0); 1-(1-x)^2, x≤ 0.5 (y=1)} Теперь он должен взять максимум от этой величины. Посмотрим графически, что здесь получается. То есть, наилучшая стратегия для первого игрока --- x_0 = 1/2. Это в случае, когда игрок не информирован.

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

Как должен действовать, как будет действовать второй, когда он не информирован (как должен действовать первый, когда он информирован).

  • 1-x^2=1-(1-x)^2
  • 1-x^2=
  • I x=1/2

~w~(y) = max_y

Получили, что ~w~ > _w_, значит, седловой точки нет.

Следующие два примера более конкретны. Они имеют в литературе название "дуэльные игры".

Первая дуэль называется "бесшумная дуэль". Два игрока сближаются и могут произвести один выстрел. Произвести выстрелы они могут в момент времени x,y ∈ [0, 1]. Дальше известны функции меткости: p(x), q(y). Что такое p(x) --- вероятность поражения первым игроком второго игрока, если он произвёл выстрел в момент времени x. Функция меткости возрастающая.

Платёж следующий: 1, если 1 игрок поразил второго, -1 если наоборот, 0 в двух остальных случаях. Берётся матожидание. Если x<y, то есть первый игрок стреляет первым. Вспомним, что такое матожидание --- берётся сумма произвольных аргументов на вероятность. То есть, 1*p(x) + (1-p(x))*q(y)*(-1) + 0 * (...) В итоге получается p(x) - (1-p(x))*q(y) (когда x<y). Когда x=y, то получаем p(x)(1-q(x)) - (1-p(x))q(x). Когда x>y, полоучается -q(y)+(1-q(y))p(x).

Эти дуэли бесшумные, поскольку если первый игрок производит выстрел и промахивается, то второй игрок это не слышал. В шумных, если первый выстрелил и промазал, то второй будет стрелять не в момент времени y, а в момент 1, когда вероятность максимальна. В случае, если p(x) = x, q(y) = y, получим

          x-y+xy, x<y
K(x, y) = 0, x=y
          x-y-xy, x>y

Посчитаем выигрыш. стратегии.

Рассмотрим, как выглядит функция при фиксированном x.

_w_(x) = inf_y K(x, y) = min(-x_2, 2x-1), max_x _w_(x)

x=sqrt(2)-1 --- оптимальное значение для первого игрока, и нижняя цена игрока _I_=2sqrt(2)-3, если то же самое повторить за второго игрока, то получим, что ~I~=3-2sqrt(2) и y=sqrt(2)-1

Вторая модель --- шумная дуэль. Отличается от бесшумной только тем, что если один из игроков производит выстрел и промахивается, то второй игрок об этом узнаёт. Поэтому, когда он узнаёт, то стрелять он будет в момент, когда будет максимально, в момент 1.

Посчитаем вероятности:

          p(x) - (1-p(x))q(1), x<y
K(x, y) = p(x)(1-q(x))-(1-p(x))q(x), x=y
          -q(y)+(1-q(y))p(1), x>y
p(x) = x,
q(y) = y
          2x-1, x<y
K(x, y) = 0, x=y
          1-2y, x>y

Рассмотрим второго игрока.

  • ~w~(y) = sup_x K(x, y) = max(2y-1, 1-2y)
  • ~I~ = min ~w~(y)=0, y=1/2

Аналогично для первого игрока _I_=0, x=1/2

Получили седловую точку (1/2, 1/2).

Игра с ... времени. Есть два игрока --- подлодка и обороняемый объект. Игра происходит следующим образом: подлодка всплывает, а объект в момент времени y выпускает осветительную ракету освещает акваторию на отрезке y, y+d, если лодка всплывёт в этом интервале, то она будет уничтожена, иначе она уничтожит объект. Если лодка уничтожит объект, то платёж 1, иначе платеж 0

Здесь платёжная функция выглядит следующим образом:

          1, x<y или y > y+d
K(x, y) = 0, x ∈ [y, y+d]

В любой момент минимум 0, поэтому нижняя цена равна 0, поэтому оптимальным является любой момент. То же для второго игрока --- в любом случае максимум 1, ~I~=1, точка любая, и седловой точки здесь нет.

Переходим к вопросу, связанному с существованием седловых точек. Покажем алгоритм поиска седловых точек. Сейчас более глубоко изучим этот вопрос. Для этого понадобится вспомнить некоторые утверждения из математического анализа, связанные с выпуклостью функций.

Определение 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.2. Функция 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.3. Функция 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.4. Функция 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)

Утверждения.

  • Сумма двух выпуклых функций есть выпуклая функция
  • Сумма выпуклой и строго выпуклой --- строго выпукла.
  • Аналогично для вогнутых.

Доказать самостоятельно.

  • Строго выпуклая функция на выпуклом множестве имеет ровно одну точку минимума
  • Строго вогнутая функция на выпуклом множестве имеет ровно одну точку максимума

Пусть дана 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).

       ( δ^2f/δx_1δx_1, ..., δ^2f/δx_1δx_n )   (2 ... 0 )
f(x)=( ...                                                                   ) = (  ...   )
       ( δ^2f/δx_nδx_1, ..., δ^2f/δx_nδx_n )   (0 ... 2 )

Эта форма положительно определённая. Значит, функция строго выпуклая.


Теория игры и исследования операций


01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16


Календарь

Сентябрь
04 11 18 25
Октябрь
02 09 16 23 30
Ноябрь
06 13 20 27
Декабрь
04 11 18



Материалы по курсу
Контрольная 1 | Контрольная 2 | Контрольная 3


Эта статья является конспектом лекции.
Личные инструменты
Разделы