Тигры, 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 )

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