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

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

(Различия между версиями)

ESyr01 (Обсуждение | вклад)
(Новая: Остлось доказть, что ... 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) --- э...)
К следующему изменению →

Версия 18:19, 15 сентября 2008

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

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). Дальше над, вобще говоря, проверить все плоуч. седл. точки.

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

Смешанные стратегии в ант. играх.

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

Игра обычно разыг. много раз. При этом возн. понятие p=(p_1, ..., p_n), p_i > 0, &suum;_{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 — противоречие.

Пример