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

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

• Аудиозапись: http://esyr.org/lections/audio/game_theory_2008_winter/GT_08_09_04.ogg

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

В АИ принимают участие 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 --- конечные множества. Будем считать, что все стратегии занумерованы от 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_ называется ценой инфрмции. Если верх. и ниж. цены совп., то игроку нет никакой разницы, будут его инф. или нет. А если разность больше нуля, то инфй. имеет цену.

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

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

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

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

_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.

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

Поск ... непр, то ∀ ε > 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.

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

Чт такое седл. элемент --- элемент, кторый максимальный в стлбце и минимальный в строке. В данной матрице элемент (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)

Т.. теорема ок. плностью.

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

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

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

Третье.

...

Отсюда следует, что 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 )

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