Тигры, 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 — противоречие.

Пример

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.



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


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


Эта статья является конспектом лекции.

Эта статья ещё не вычитана. Пожалуйста, вычитайте её и исправьте ошибки, если они есть.
Личные инструменты
Разделы