Редактирование: Тигры, 03 лекция (от 18 сентября)
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 1: | Строка 1: | ||
- | + | Методы решения матр. игр со смеш. стртегией | |
- | + | ||
- | Методы решения | + | |
Сначала рассмотрим игры вида 2×m или n×2 | Сначала рассмотрим игры вида 2×m или n×2 | ||
Строка 13: | Строка 11: | ||
A(p, j) = pa_1j+(1-p)a_2j | A(p, j) = pa_1j+(1-p)a_2j | ||
- | В этом случае | + | В этом случае знчение игры V = max_{~p~} ∈ P_@ min_{j=1,m} A(~p~, j) = max_{p∈[0,1]} min_{=1,m} (pa_1j+(1-p)a_2j) = min_{j=1,m} (p^0 a_1j+(1-p^0)a_2j) |
y=l_j(p), j=1,m | y=l_j(p), j=1,m | ||
Строка 44: | Строка 42: | ||
A(~p~^0, ~q~^0) = V | A(~p~^0, ~q~^0) = V | ||
- | + | Покжем, что l_j1, l_2 не зависят от p | |
A(~p~^0, ~q~^0) = a_{1 j_1}q^0 + a_a_{2 j_1}(1-q^0) + p(K_1 q^0 + K_j2(1-q^0)) = a_{1 j_1}q^0 + a_a_{2 j_1}(1-q^0) | A(~p~^0, ~q~^0) = a_{1 j_1}q^0 + a_a_{2 j_1}(1-q^0) + p(K_1 q^0 + K_j2(1-q^0)) = a_{1 j_1}q^0 + a_a_{2 j_1}(1-q^0) | ||
Строка 56: | Строка 54: | ||
Получаем чистую стратегию, ~q~^0 = (0, ..., 1 (пхиция j_1), ..., 0) | Получаем чистую стратегию, ~q~^0 = (0, ..., 1 (пхиция j_1), ..., 0) | ||
- | 3) p^0 = 1 | + | 3) p^0 = 1 рассм. аналогично |
Строка 65: | Строка 63: | ||
A~ = -A^T | A~ = -A^T | ||
- | + | Предп, мы решили A^T (p*, q*, V) | |
A~(p*, j) ≥ V, j=1,m | A~(p*, j) ≥ V, j=1,m | ||
Строка 72: | Строка 70: | ||
A(j,p*)≤-V,j=1,m | A(j,p*)≤-V,j=1,m | ||
- | Точно | + | Точно ткже покзывается (сделть дома) A(q*, i) ≥ -V, i=1,2 |
- | В таком случае (q*, p*, -V) обр. решение | + | В таком случае (q*, p*, -V) обр. решение исх. игры с плат. мтрицей A. |
Пример: | Пример: | ||
Строка 82: | Строка 80: | ||
1 -5 | 1 -5 | ||
- | + | Ндо трансп. матрицу: | |
1 0 4 -1 | 1 0 4 -1 | ||
Строка 94: | Строка 92: | ||
l_4(p) = 5-6p | l_4(p) = 5-6p | ||
- | Теперь надо | + | Теперь надо постр. эти прямые, найти минимум. и максимальную точку. |
l_1(p)=l_2(p) | l_1(p)=l_2(p) | ||
Строка 101: | Строка 99: | ||
~p~^0 = (2/3, 1/3) | ~p~^0 = (2/3, 1/3) | ||
- | Теперь | + | Теперь считем опт. стртегию второго игрока: |
K_1=2, K_2=-1 | K_1=2, K_2=-1 | ||
Составляем уравнение: | Составляем уравнение: | ||
Строка 113: | Строка 111: | ||
Второе: итеративный метод Брауна. | Второе: итеративный метод Брауна. | ||
- | Проводится имитация | + | Проводится имитация мнгокртного розыгрыш игры. И каждый раз игроки пытаются нхдить чистые стртегии. Потом изо всего множества выбр. чисты стратегий будут выбраны смеш., кторые будут явл. прибл. знач. решения игры. |
Игра A_n×m | Игра A_n×m | ||
- | 1) | + | 1)Игрки выбир. произв. чистые стратегии: i_1, j_1 |
- | + | Предпложим, что в игре проведено k шагов, предп., что первый игрок первую свою стратегию выбрал r_1 раз, вторую r_2 и ... n-ю r_n раз. Аналогично второй игрок l_1, ..., l_m раз. | |
Тогда p^k = (r_1/K, ..., r_n/K), q^K = (l_1/K, ..., l_m/K) | Тогда p^k = (r_1/K, ..., r_n/K), q^K = (l_1/K, ..., l_m/K) | ||
- | Легко | + | Легко пказать, что p^K, q^K явл смеш. страт. (покзть дома) |
- | Теперь K+1 шаг. На k+1 шаге. | + | Теперь K+1 шаг. На k+1 шаге. выбир какую-т чистую стртегия, предп., что у втргго игрок q^K --- оптимльная смеш. стртегия, и тогда, чтбы выбр. свю чистую стртегию, он макс. по i величину max_{i=1,n} A(i,q^k) = A(i_k+1,q^) = V^K_1. |
- | Мы показали, как игрок | + | Мы показали, как игрок выбир. стратегию н каждом очреднм шаге. Аналгичн второй игрок, он ищет min_{j=1,m} A(p^K, j) = A(p^K, j_k+1) = V^K_2. |
Теперь увидим, что | Теперь увидим, что | ||
Строка 136: | Строка 134: | ||
V^K_2 ≤ V ≤ V^K_1 | V^K_2 ≤ V ≤ V^K_1 | ||
- | Теорема. 1) В | + | Теорема. 1) В метде Бруна предел при K ← ∞ V^K_1 равен пределу V^K_2 и равны они V. |
- | 2) Пусть p^0 | + | 2) Пусть p^0 произв. пред. тчк посл. {p^k}, q^0 — {q^K}. Тогда p^0, q^0 — птим. смеш.ю стртегии для 1, 2 игроков. |
- | ε-оптимальные смешанные стратегии. | ||
- | p^ε, q^ε | + | ε-оптимальные смеш. стратегии. |
+ | |||
+ | p^ε, q^ε наз. ε-оптимальными смешг. стртегиями, если | ||
A(p^ε, q) ≥ V-ε, ∀q∈Q_m | A(p^ε, q) ≥ V-ε, ∀q∈Q_m | ||
Строка 147: | Строка 146: | ||
A(p,q^ε)≤V+ε ∀p∈P_n | A(p,q^ε)≤V+ε ∀p∈P_n | ||
- | Можно показать | + | Можно показать ткое утверждение (дк. сам) |
- | p^ε, q^ε явл. ε-оптимальными, если | + | p^ε, q^ε явл. ε-оптимальными, если вып. след. нер-ва |
A(p^ε, j) ≥ V-ε, j=1,m | A(p^ε, j) ≥ V-ε, j=1,m | ||
Строка 155: | Строка 154: | ||
A(i,q^ε)≤V+ε i=1,n | A(i,q^ε)≤V+ε i=1,n | ||
- | на этом | + | на этом осн. конеч. метод Брауна: нч. с K≥K_0 V_1^K - V^K_2 ≤ &espilonб и стратегии будут ε-оптимльными (также дказать самостятельно) |
- | + | Просте решение игры | |
- | Будем | + | Будем рассм. игру с матр. A_n×n |
- | + | Определение. Игра с матр. A_n×n дпускет прстое решение (p*, q*, V), если A(p*, )=V, j=1,n, A(i, q*)=V, i=1,n | |
1 | 1 | ||
Строка 170: | Строка 169: | ||
I'=(1, .., 1) (n элементов) | I'=(1, .., 1) (n элементов) | ||
- | + | Терема 1. Если игра с матр A дп. прстое решение, и опр. A невырожден, то решение нахд. по ким фрмулам: | |
p* = VI'A^{-1}; q*=VA^{-1}I, V = 1/{i'a^{01}I} | p* = VI'A^{-1}; q*=VA^{-1}I, V = 1/{i'a^{01}I} | ||
Строка 176: | Строка 175: | ||
причём других решений нет. | причём других решений нет. | ||
- | + | Доказательство. | |
- | + | Рассм. систему, предп., чт V --- какое-т число. | |
p*=VI'A^{-1} | p*=VI'A^{-1} | ||
p*=VA^{-1}I | p*=VA^{-1}I | ||
Строка 186: | Строка 185: | ||
V = V^2 I' A^{-1}I | V = V^2 I' A^{-1}I | ||
- | 1) V=0. Но | + | 1) V=0. Но этг быть не мжет, птому что тогда p* плучится нул. вектором, а этог быть немжет, ибо смешанная стратегия |
2) V = 1/{i'a^{01}I} | 2) V = 1/{i'a^{01}I} | ||
- | И | + | И реш. единственно след. из ед. реш. системы. |
чтд | чтд | ||
- | + | Опред. Игра наз. вполне смеш, если у каждй пары оптим. смеш. страт, все координаты положительны. | |
- | + | Теорема 2. Если игра вплне смеш и |A|≠0, то он имеет. ед. пару смеш. страт.: p*=I'A^{-1}/{i'a^{01}I}, q* = A^{-1}I/{i'a^{01}I} | |
- | Теперь мы можем перейти к | + | Теперь мы можем перейти к сн. методу, дающему все реш. |
- | Крайние | + | Крайние птимальные смеш. стратегии. |
- | + | Определение. пусть x_0∈ X. Тчк наз. крайней, если не сущ. x_1, x_2 ∈ X, x_1≠x_2, α∈(0,1), x_0 = αx_1 + (1-α)x_2 | |
- | + | Теорема (о крайних оптимльных смеш. стратегиях). Пусть P* и Q* — мнжество оптим. смеш. страт. 1 и 2 соотв. игрока игры со смеш. стртегией и плат. мтр. A, и V≠0 — знчение игры. Для того, чтбы статегии p* ∈ P* и q* ∈ Q* были крйними точками, небх. и дост, чтбы матр. A содержала кв. невыр. матрицу B, для игры которй p*^B и q*^B были бы простыми реш. и V(B)=V. | |
- | * V(B) — значение игры с | + | * V(B) — значение игры с матр. B |
- | * p*^B — | + | * p*^B — вектр, плученный из p* вычёркиванием тех координат, кторые соотв. нмерам строк матр. A, не вшедших в B |
- | * | + | * анлоигчно пр. q*^B |
- | + | Рассм. ещё раз форм. этй теоремы. Тут два. утв. Перве тке: если мы берём крайние пт. смеш. стратегии игроков, то тогда в мтр. A найдётся подматр. B, такя, что p*^B и q*^B были бы простыми реш. и V(B)=V. Второе утв. — достаточность. Если мы берём ккие-т оптим. смеш. стртегии игроков и сущ. подматр. B, такя, что p*^B и q*^B были бы простыми реш. и V(B)=V, то тогда p* и q* будут смеш. страт. | |
- | + | Доказательство. Необхдимсть. Что у нас есть? Есть p* и q*, кторые явл. крайними. Ндо показать, что найдётся подматр. B, такя, что p*^B и q*^B были бы простыми реш. и V(B)=V | |
- | Что мы делаем: | + | Что мы делаем: стрим множеств индексов I_1={i:p*_i>0}; I_2={i:A(i,q*)=V} (I_1∈I_2 в соотв. с доним из свойств пред. лекции) |
- | + | Стрим мнжество J_1={j:q*_j >0}, J_2={j:A(p*,q)=V} (J_1 ∈ J_2) | |
- | Занумеруем элементы, при | + | Занумеруем элементы, при этм, не гр. бщнсти, будпем считать, что туда вхдят первые стрки и столбцы исх. матрицы. |
I_1={1,..,k}, I_2={1,...,k,...d} | I_1={1,..,k}, I_2={1,...,k,...d} | ||
J_1={1,..,l}, J_2={1,...,l,...h} | J_1={1,..,l}, J_2={1,...,l,...h} | ||
- | Матрицу A | + | Матрицу A предствляем таким образом: |
A_1 A_2 A_3 | A_1 A_2 A_3 | ||
A_4 A_5 A_6 | A_4 A_5 A_6 | ||
Строка 230: | Строка 229: | ||
A~ = A_4 A_5 | A~ = A_4 A_5 | ||
- | Лемма. Первые k строк A~ линейно независимы. Первые l | + | Лемма. Первые k строк A~ линейно независимы. Первые l стлбцов A~ линейн независимы. |
- | + | Дкажем первую часть, втрая аналгично. Пусть это не так. Тгда найдутся α_1, α_k, не все равные нулю, такие что ∑_{i=1}^k α_i a_ij = 0, j=1,h | |
- | Делаем следующее: | + | Делаем следующее: бе части имнжим на q*_j и просуммируем: |
- | 0=∑_{j=1}^h q*_j ∑_{i=1}^k α_i a_ij = ∑_{i=1}^k α_i ∑_{j=1}^h q*_j a_ij = ∑_{i=1}^k α_i ∑_{j=1}^m q*_j a_ij (почему | + | 0=∑_{j=1}^h q*_j ∑_{i=1}^k α_i a_ij = ∑_{i=1}^k α_i ∑_{j=1}^h q*_j a_ij = ∑_{i=1}^k α_i ∑_{j=1}^m q*_j a_ij (почему тк мжно написать — потому что дальше коорд. равны 0) (Посмотрим на мн-во I_2. Для первых d строк она равна V) = ∑_{i=1}^k α_i V = V ∑_{i=1}^k α_i |
- | И | + | И поск. V неравн 0 (это несильное огр., поск. мжн прибавить дно и то же ко всем эл-там матр, тогда птим. стартегия не изм.) |
- | Теперь | + | Теперь рассм. α = (α_1, .., α_k, 0, ..., 0) |
p^ε = p*+εα, p^-ε = p* - εα | p^ε = p*+εα, p^-ε = p* - εα | ||
- | При этом первые k p*_i | + | При этом первые k p*_i бльше 0. Тгда мжно взять ε > 0 таке, что p^ε, p^-ε больше 0. Крме того |
∑_i=1^n p^ε_i = 1, ∑_i=1^n p^-ε_i = 1 | ∑_i=1^n p^ε_i = 1, ∑_i=1^n p^-ε_i = 1 | ||
Строка 266: | Строка 265: | ||
p*=1/2 p^ε + 1/2 p^-ε | p*=1/2 p^ε + 1/2 p^-ε | ||
- | + | Плучили, что p^ε и p^-ε --- оптимльные стратегии, и p* не крйняя, чт противоречит условию. Пртиворечие возн. только из того, что первые стрки линейн зависимы, знчит, ни линейн независимы. | |
- | Точно также (показать дома), | + | Точно также (показать дома), чт первые l стлбцв лин. независимы. |
- | + | <!-- педедыв --> | |
- | + | Матр. A~ имеет ранг t ≥ max(k,l) | |
- | + | Значит, найдётся квадр. невырожд. матрица B размером t×t, которая расп. в верхнем левом угу (не огр. общности) | |
+ | |||
+ | Пкажем, что это та самая матрица B. Надо показать, что (p*^B, q*^B, V) простое решение. | ||
... | ... | ||
Строка 280: | Строка 281: | ||
A(p*, j) = B(p*^B, j) = V, j=1,t | A(p*, j) = B(p*^B, j) = V, j=1,t | ||
B(i, q8^b) = V | B(i, q8^b) = V | ||
- | Отсюда эта тройка и есть прстое решение. | + | Отсюда эта тройка и есть прстое решение. Небхдимость доказана. |
- | + | Дстаточность. p* q* --- ОСС. Существует B, p*^B, q*^B, V(B)=V. Небх. дказать, что p*, q* --- кр. | |
- | + | Дказтельство от братного | |
p* - αp^1 + (1-α)p^2, p^1, p^2∈p*, α&isin(0,1) | p* - αp^1 + (1-α)p^2, p^1, p^2∈p*, α&isin(0,1) | ||
Строка 298: | Строка 299: | ||
... | ... | ||
- | 3. Это | + | 3. Это мнжество --- мнгогранник. И, находя все его крайние точки, мы ег предедлим. Т. . мы сможем описать множество всех смеш. стртегий. |
Пример: | Пример: | ||
Строка 305: | Строка 306: | ||
A= 1 0 4 | A= 1 0 4 | ||
- | У этой игры нет | + | У этой игры нет седл. точки в чистой стратегии. |
2 4 2 0 4 0 | 2 4 2 0 4 0 | ||
Строка 329: | Строка 330: | ||
V(D)=2 --- уже не кр. | V(D)=2 --- уже не кр. | ||
- | Нужн перебирать все | + | Нужн перебирать все кв. пдм, и если ... |
Связь теории игр с линейным программированием | Связь теории игр с линейным программированием | ||
- | Вспомним | + | Вспомним прост. методы лин. программирования. |
A_m*n: x=(x_1, ..., x_n), y=(y_1, ..., y_m) | A_m*n: x=(x_1, ..., x_n), y=(y_1, ..., y_m) | ||
Строка 350: | Строка 351: | ||
y≥0 | y≥0 | ||
- | Вводятся | + | Вводятся перем. огр., таких переменных m штук. |
3. Общая задача линейного программирования: min_x (C,x) | 3. Общая задача линейного программирования: min_x (C,x) | ||
Строка 363: | Строка 364: | ||
y_i ≥ 0, i=1...k | y_i ≥ 0, i=1...k | ||
- | Каждому | + | Каждому двойств. гр. сопост. перем. y_j |
- | + | Лемма 1. Если x и y допустимые вектора, т (b,y)≥(c,x) | |
- | + | Лемма 2. Задачи 1 и 2 либ обе не им. решения, либо (c, x*) =(b,y*). Аналогично задачи 3 и 4. | |
- | + | Лемма 3. Усл. дополн. неж. или принцип оптимальности. допустимые вектра x*, y* | |
a) x*_j > 0 ⇒ A(y*, j) = c_j | a) x*_j > 0 ⇒ A(y*, j) = c_j | ||
b) y*_j > 0 ⇒ A(i, *x) = b_i | b) y*_j > 0 ⇒ A(i, *x) = b_i | ||
- | |||
- | Контрольная. | ||
- | |||
- | Задачи | ||
- | |||
- | 1. Найти седловую точку для игры, заданной матрицей. | ||
- | |||
- | 2. Найти седловую точку для игры, заданной функцией F(x,y) = -x^2+y^2+y на [0,1]×[0,1] | ||
{{Тигры}} | {{Тигры}} | ||
{{Lection-stub}} | {{Lection-stub}} |