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

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

Текущая версия

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

Осталось доказать, что ...

x ∈ X, y ∈ Y, t ∈ (0,1)

K((1-t)x*+tx+y) > (1-t)k(x*,y) + tK(x, y) ≥ (1-t)_w_(x*) + tK(x,y)

ỹ = y((1-t)x* + tx) --- это верно при фиксированном ...

_w_(x*) ≥ _w_((1-t)x* + tx) > (1-t)_w_(x*) + tk(x, ỹ) --- мы расписали это соотношение при y=ỹ

t_w_(x*) &gy; tK(x,ỹ)

_w_(x*) > K(x, y((1-t)x* + tx))

Это соотношение справедливо ∀t ∈ (0,1). Устремим t к 0. Что получится:

_w_(x*) ≥ K(x,y(x*)) (здесь мы используем доказанную в начале непрерывность)

Левая величина _w_(x*) = K(x*, y(x*))

То есть показано, что это — седловая точка.

Теперь откажется от строгости выпуклости/вогнутости.

Введём функцию K_ε(x,y) = K(x,y) - ε &sum_{i=1}^n x_i^2 + ε &sum_{j=1}^m y_j^2, ε > 0

Так как каждое из слагаемых строго выпукло по x/y, то и сумма тоже строго выпукла по x и y. Следовательно, для неё верно только что доказанное утверждение: (x_ε, y_ε) — седловая точка. K_ε(x,y)

K_ε(x,y_ε) ≤ K_ε(x_ε,y_ε) < K_ε(x_ε,y), ∀ x ∈ X, y ∈ Y

K(x, y_ε) — ε &sum_{i=1}^n x_i^2 ≤ K_ε(x,y_ε) ≤ K_ε(x_ε,y_ε) ≤ K(x_ε,y) + ε &sum_{j=1}^m y_j^2

Итог следующий:

K(x, y_ε) — ε &sum_{i=1}^n x_i^2 ≤ K_ε(x_ε,y_ε) ≤ K(x_ε,y) + ε &sum_{j=1}^m y_j^2, ∀ x ∈ X, y ∈ Y

Теперь ε_n → 0, n → ∞, ε_n > 0. Тогда эти слагаемые устремляются к нулю, из ограниченной последовательности можно выделить сходящуюся, соответственно, без ограничения общности y_{ε_n} → y*, x_{ε_n} → x*, и получаем

K(x, y*) ≤ K(x*, y), из этого условия мы доказывали ранее, что K(x*, y*) — седловая точка.

Важно отметить, что эти условия являются достаточными, но не необходимыми.

Пример (условие не является необходимым):

K(x,y) = x^e + 0×y, x, y ∈ [0,1]. (1,1) — седловая точка. (доказать дома)

Пример:

K(x,y) = y ln(x+3) + xy^2, x, y ∈ [0,1]

Условия теоремы фон Неймана выполняются:

K_{x}' = y/(x+3) + y^2

K_{xx} = –y/(x+3)^2 ≤ 0 — вогнута по x

K_{y}' = ln(x+3) + 2xy

K_{yy} = 2x ≥ 0 — выпукла по y.

Условие теоремы фон Неймана выполнено, и есть седловая точка (показать дома, что это (1,0))

Теорема конструктивная и вообще говоря, ей можно пользоваться для нахождения седловой точки.

Сейчас рассмотрим частный случай платёжной функции, для которой есть простой алгоритм. Он позволяет свести поиск седловой точки к решению системы уравнений и решению матричной игры.

Раздел: необходимое условие для седловой точки

Рассмотрим следующий случай: множество стратегий X имеет следующий вид: X={x=(x_1, ..., x_n), 0 ≤ a_i ≤ x_i ≤ b_i, i = 1..n}, Y={y=(y_1, ..., y_m), 0 ≤ c_i ≤ y_j ≤ d_j, j = 1..m}

Предполагаем, что K(x, y) непрерывно на X× Y и имеет частную производную K_{x_i}', K_{y_j}', i=1..n, j=1..m.

Прежде, чем вып. след. деёств, рассмотрим систему:

K_{x_i}'(x, y)(x_i - a_i)(x_i - b_i) = 0, i=1..n
K_{y_j}'(x, y)(y_j - c_j)(y_j - d_j) = 0, j=1..m (*)

Предположим, что эта система имеет решение и множество решений конечно. Тогда пр. следующие множества: те x из X, что:

X^c = {x ∈ X: ∃y ∈ Y, (x,y) ∈ X}

....

Теорема. Если (x_0, y^0) — седловая точка K(x,y) на X×Y, то (x_0, y^0) ∈ C, (x_0, y^0) — c.т. K на X^c×Y^c

Эта теорема даёт нам алгоритм поиска седловой точки. Пусть есть такая функция и выполнены все условия мы выписываем систему уравнений (*), решаем её, получаем, что множество решений конечно. Выписываем множество X^c×Y^c, и получаем матричную игру, и тут уже искать просто.

Еcли с.т. у K есть, то она обязательно войдёт в число точек матричной игры. То есть решаем матричную игру и проверяем, будет ли каждая из седловых точек для исходной игры.

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

K(x,y^0) ≤ K(x^0, y^0) ≤ K(x^0, y), ∀ x ∈ X, y ∈ Y

max_{x_i ∈ [a_i, b_i]} K(x^0_1_j, ..., x^0_i, ..., x&0_n, y^0_1, y^0_m) = K(x^0, y^0)

K'_{x_i}(x^0, y^0) = 0 либ x_i^n=a_i, либ x^0_i=b_i

Таким образом мы доказали первую часть.

Вторая часть: если мы берём первое соотношение, и оно верно при ∀ x ∈ X, y ∈ Y, то оно верно и при ∀ x ∈ X^c, y ∈ Y^c

Таким образом мы получили алгоритм.

Пример.

K(x,y)=8(4xy^2-2x^2-y), x,y∈[0,1]

Сначала проверим, выполнены ли условия теоремы фон Неймана. По x она вогнута и по y она выпукла. Отсюда по теореме фон Неймана существует седловая точка.

Теперь будем строить систему уравнений (*):

K'_x=8(4y^2-4x), K'_y=8(8xy-1)

(y^2-x)(x-0)(x-1) = 0
(8xy-1)(y-0)(y-1) = 0

решаем эту систему: (0,0), (0,1), (1,0), (1,1), (1, 1/8), (1/4, 1/2) --- построили множество C

X^c = {0, 1/4, 1}, Y^c = {0, 1/8, 1/2, 1}

Теперь строим матричную игру:

x^c \ y^c  0   1/8  1/2   1
 0         0    -1   -4  -8
1/4       -1 -15/8   -3   1
 1       -16 -33/2  -12   8

седловая точка --- (1/4, 1/2). Дальше надо, вообще говоря, проверить все полученные седловые точки.

Но поскольку мы установили, что по теореме фон Неймана есть одна седловая точка, а получили мы их максимум одну, то их ровно одна.

[править] Смешанные стратегии в антагонистических играх

Когда рассматривается игра с платёжной матрицей A = ||a_ij||, i=1..n, j=1..m. Каждый выбирает i/j соответственно, и один получает a_ij, другой -a_ij

Игра обычно разыгрывается много раз. При этом возникает понятие p=(p_1, ..., p_n), p_i > 0, ∑_{i=1}^n p_i=1 --- вектор вероятности выбора стратегии i --- смешанная стратегия первого игрока. Множество этих стратегий P_n = {p=(p_1, ..., p_n), p_i > 0, ∑_{i=1}^n p_i=1}. Аналогично для второго игрока: Q_m = {q=(q_1, ..., q_m), q_j > 0, ∑_{j=1}^m q_j=1}.

Пусть p∈ P_n, q ∈ Q_n. Как считается результат? считается матожидание платежа. Платёж a_ij первый игрок получает при выборе стратегии i и выборе стратегии j вторым игроком. Но первый игрок выбирает с вероятностью p_i, а второй — q_j. Вероятность данного выбора --- p_i×q_j. Тогда выигрыш равен A(p,q) = &sum_{i=1}^n ∑_{j=1}^m a_ij p_i q_j. Это показывает, какой выигрыш получат игроки, если выбрали стратегии p, q.

От игры с платёжной матрицей A мы перешли к игре с платёжной функцией A(p,q).

A(p,j) = &sum_{i=1}^n a_ij p_i, A(i, q) = ∑_{j=1}^m a_ij q_j

A(p,q) = ∑_{j=1}^m A(p,j) q_j = &sum_{i=1}^n A(i, q) p_i

Каждый игрок по прежнему действует по принципу максимальной выгоды, тогда получим:

max_{p∈P_n} min_{q∈Q_m} A(p,q) = min_{q∈Q_m} A(p^0,q)

min_{q∈Q_m} max_{p∈P_n} A(p,q) = max_{p∈P_n} A(p,q^0)

В такой игре всегда существует седловая точка.

Л1. P_n, Q_m — выпуклые компакты.

1) p^1, p^2 ∈ P_n, α ∈ (0,1) Рассмотрим αp^1 + (1-α)p^2 Тогда

αp^1 + (1-α)p^2 ≥ 0
∑_{i=1}^n(αp_i^1 + (1-α)p_i^2) = α ∑_{i=1}^n p_i^1 + (1-α) ∑_{i=1}^n p_i^2 = 1

2) p^k ←_{k ← ∞} p^0, p^k ∈ P_n

p_i^k ≥ 0 ⇒ p_i^0 ≥ 0
∑_i=1^n p_i^k = 1
lim_{k &rasrr; ∞} ∑_i=1^n p_i^k = 1
∑_i=1^n lim_{k &rasrr; ∞} p_i^k = ∑_i=1^n p_i^0

Из определений P и Q. Мы делаем вывод, что A(p,q) непрерывна, и является линейной. Значит, она и выпукла, и вогнута по любой переменной. То есть, она вогнута по p и выпукла по q. По теореме фон Неймана существует седловая точка. Т.о., мы доказали теорему "в матричной игре всегда существует смешанная стратегия". Ну и поскольку мы отметили, что функция A(p,q) — непрерывна, а множества смешанных стратегий являются компактными, то это позволяло писать max/min.

Ну и вообще, мы делаем какой вывод: max min и min max равны. Это следствие из теоремы.

Как решать матричные игры в смешанных стратегиях: нужно найти любую седловую точку.

Отметим ещё раз, что если p*, q* --- оптимальные стратегии, то (p*, q*) — седловая точка.

Отметим свойства оптимальных смешанных стратегий. Тройкой (p*, q*, V) будем называть решение игры. V = max_p nim_q A(p,q) = min_q max_p A(p,q) = A(p*, q*) Когда нам будет дана со смешанной стратегией, то целью будет являться решение игры. Таких троек может быть много. Для поиска таких троек небходимо знать свойства оптимальных смешанных стратегий.

1. Если (p*, q*, V) — решение игры с матрицей A, то (p*, q*, V+c) — решение игры с матрицей Ã = ||a_ij + c||, c=const. Мы прибавили константу ко всем элементам матрицы. Что меняется? Множество решений не меняется, меняется только значение игры. Докажем:

A(p,q) + c = A(p,q) + c(∑_i=1^n p_i)(∑_i=j^m q_j) = &sum_{i=1}^n ∑_{j=1}^m (a_ij + c) p_i q_j = Ã(p,q)

Пусть выполнено условие, и A(p*, q*) — седловая точка. Тогда

A(p,q*) ≤ A(p*, q*) ≤ A(p*, q)
Прибавим константу c:
A(p,q*) + c ≤ A(p*, q*) + c ≤ A(p*, q) + c
Ã(p,q*) ≤ A(p*, q*) + с ≤ Ã(p*, q)

Теперь из утверждения, доказанного на прошлой лекции, следует, что (p*, q*) обращает седловую точку и (p*, q*, V+с) — решение игры

2. Тройка (p*, q*, V) является решением игры тогда и только тогда, когда A(i, q*) ≤ V ≤ A(p*,j), ∀ i=1..n, j=1..m

Доказательство. 1)Пусть (p*, q*, V) — решение. Тогда:

A(p,q*) ≤ A(p*, q*) = V ≤ A(p*, q), ∀ p ∈ P_n, q ∈ Q_m

Т.к. оно верно для всех p, q, то можно взять p=(0...0, 1 (i-е место), ..., 0) ∈ P_n, q=(0...0, 1 (j-е место), ..., 0) ∈ Q_m, и сразу получаем эти соотношения.

2)Пусть выполнены соотношения: A(p,q*) ≤ A(p*, q*) = V ≤ A(p*, q), ∀ p ∈ P_n, q ∈ Q_m

Возьмём произвольным p, q. Возьмём соотношение A(i, q*) ≤ V, i=1..n

∑_{i=1}^n p_i A(i, q*) ≤ ∑_{i=1}^n V p_i
A(p, q*) ≤ V

В итоге получится, что A(p,q*) ≤ V ≤ A(p*, q). Это означает, что (p*, q*, V) — решение.

Пример.

1 0
0 1

Решение: ((1/2, 1/2), (1/2, 1/2), 1/2)

Можно доказать, что _I_ ≤ V ≤ ~I~ (доказать дома)

3. Справедливы следующие равенства:

1) ∀ p ∈ P_n min_q A(p,q)=min_j A(p,j)
2) ∀ q ∈ Q_m max_p A(p,q)=max_i A(i,q)

Докажем первую часть, вторая доказывается аналогично. Покажем сначала, что лч≤ пч, потом что лч≥пч.

a) min_{j=1..m} A(p, j) = min_j A(p, q^j), q^j = (0..., 1(j-е место), ..., 0)

min_j A(p, q^j) ≥ min_q A(p, q)

b) min_q A(p,q) = min_q ∑_{j=1}^n ≤ min_q &sum_j q_j (min_j ∑ a_ij p_j) = min_j ∑ a_ij p_j (min_q &sum_j q_j (=1)) = min_j ∑ a_ij p_j = A(p, j)

min_j A(p, q^j) ≤ min_q A(p, q)

Отсюда равенство.

Следствия.

Сл1. V = max_p min_q A(p,q) = max_p min_j A(p,j)

    V = min_q max_p A(p,q) = min_q max_i A(i,q)

Cл2. (доказать самостоятельно) (p*, q*, V) — решение тогда и только тогда, когда min_ A(p*, j) = max_i A(i, q*) = V

В этом свойстве тоже заложен некий алгоритм поиска решения.

Св4. (p*, q*, V) — решение

1) p*_{i_0} > 0 ← A(i_0, q*) = V
1) q*_{j_0} > 0 ← A(p*, j_0) = V

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

пусть p*_{i_0} > 0, A(i_0, q*) ≤ V

V=A(p*, q*) = ∑_i A(i,q*) (≤ V) p_i* + A(i_0, q*) {<V} p*_i (>0) < V(1-p*_{i_0}) + Vp*_i_0 = V — противречие

Св5. P*, Q* — компакты.

Доказательство. Выпуклость: p_1, p62 ∈ P*, α ∈ (0,1) ~p = αp^1 + (1-α)p^2 ∈ P_n Осталось доказать, что это оптимальная стратегия. Все линейности можно записать следующим образом: A(~p, j) = αA(p^1, j) + (1-α)A(p^2,j) ≥ αV + (1-α)V=V

A(~p, j) ≥ V, ∀ j=1..m

P* — огр, p* ←_{k ← ∞} p^0

p_k ∈ P*, p^0 ∈ P_n

A(p^k, ) ≥ V, &orall; j=1..m

lim_{k ← ∞} A(p^k+) ≥ V

A(lim_{k ← ∞} p*, ) ≥ V

A(p^0, j) ≥ V, J=1..m

p^0 ∈ P*

В следующий раз мы покажем, что крайних точек конечное число, и тогда это многогранник. Тогда же будет указан способ нахождения крайних точек.

Раздел: доминирование матричных строк и столбцов

Предположим, что одна из строк оказалась меньше других, то первому игроку выгоднее её вычеркнуть и не рассматривать. Аналогично для второго игрока.

Теорема. Если некоторая строка матрицы A = ||A_ij|| доминируется (строго доминируется) выпуклой линейной комбинацией остальных строк, то эта строка входит с нулевой вероятностью в некоторую (любую) оптимальную смешанную стратегию первого игрока (и её можно вычеркнуть).

Теорема. Если некоторый столбец матрицы A = ||A_ij|| доминирует (строго доминирует) выпуклую линейную комбинацию остальных столбцов, то этот столбец входит с нулевой вероятностью в некоторую (любую) оптимальную смешанную стратегию второго игрока (и его можно вычеркнуть).

Нестрогое доминирование. Пусть некоторая строка матрицы нестрого доминируется. Что это значит:

Возьмём α+i ≥ 0, &sum_{i≠i_0} α_i = 1, ∑ α_i a_i — выпуклая линейная комбинация

Доминируется: a_ij ≤ ∑_{i≠i_0} αa_ij, j=1..m --- нестрогое доминирование

a_ij < ∑_{i≠i_0} αa_ij, j=1..m --- строгое доминирование

p* ∈ P*

~p_i = 0, i=i_0
       p*_i + α_i p*_{i_0}, i ≠ i_0i ≠ i_0

~p_i ≥ 0

∑_i ~p_i = ∑_{} (p*_i+α_i p*_{i_0}) = ∑_{i ≠ i_0}p*_i + p*_{i_0} &sum_{i ≠ i_0} &slphs;_i = ∑_i p*_i = 1

~p ∈ P_n

Осталось показать, что это оптимальная смешанная стратегия

A(~p, ) = ∑_{i ≠ i_0} (p*_i + α_i p*_{i_0}) a_ij = ∑_{i ≠ i_0} p*_i a_ij + p*_{i_0} ∑_{i ≠ i_0} ....

A(~p, ) ≥ V

Случай строгого доминирования:

Надо доказать, что p*_{i_0} = 0. Пусть p*_{i_0} ≥ 0. Тогда V=A(i_0, q*) = ∑_j a_{{i_0}j} q*_j < ∑_j (∑_{i≠i_0} α_i a_ij) q*_i = ∑_j α_i ∑_j a_ij q*_i = ... V < V — противоречие.

Пример

3 2 4 0
3 4 2 4
4 2 4 0
0 4 0 8

Первая строка меньше третьей, следовательно, она доминируется, но нестрого. Но если мы ищем хотя бы одно решение, то мы её можем вычеркнуть.

3 4 2 4
4 2 4 0
0 4 0 8

Сравним 1 и 3 столбцы. 1 ≥ 3. Имеет место доминирование столбцов, и его можно вычеркнуть.

4 2 4
2 4 0
4 0 8

Первый столбец доминирует линейную комбинацию 2 и 3 столбцов с коэффициентом 0.5. Опять первый столбец вычёркиваем.

2 4
4 0
0 8

Здесь доминирование строк. доминируется 1 строчка линейной комбинацией 2 и 3 с коэффициентом 0.5

4 0
0 8

Не объясняя, как мы ищем решение, то для последней игры решение такое: p*' = (2/3, 1/3), q*' = (2/, 1/3), w=8/3.