Тигры, 02 лекция (от 11 сентября)
Материал из eSyr's wiki.
(Новая: Остлось доказть, что ... 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) --- э...) |
м |
||
| Строка 1: | Строка 1: | ||
| + | * '''Аудиозапись:''' http://esyr.org/lections/audio/game_theory_2008_winter/GT_08_09_11.ogg | ||
| + | |||
Остлось доказть, что ... | Остлось доказть, что ... | ||
Версия 18:58, 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
