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

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

(Различия между версиями)
Перейти к: навигация, поиск
Текущая версия (06:58, 13 октября 2010) (править) (отменить)
(вычитка)
 
(2 промежуточные версии не показаны)
Строка 1: Строка 1:
* '''Аудиозапись:''' http://esyr.org/lections/audio/game_theory_2008_winter/GT_08_09_18.ogg
* '''Аудиозапись:''' http://esyr.org/lections/audio/game_theory_2008_winter/GT_08_09_18.ogg
-
Методы решения матр. игр со смеш. стртегией
+
Методы решения матричных игр со смешанной стратегией
Сначала рассмотрим игры вида 2×m или n×2
Сначала рассмотрим игры вида 2×m или n×2
Строка 13: Строка 13:
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)
+
В этом случае значение игры 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: Строка 44:
A(~p~^0, ~q~^0) = V
A(~p~^0, ~q~^0) = V
-
Покжем, что l_j1, l_2 не зависят от p
+
Покажем, что 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: Строка 56:
Получаем чистую стратегию, ~q~^0 = (0, ..., 1 (пхиция j_1), ..., 0)
Получаем чистую стратегию, ~q~^0 = (0, ..., 1 (пхиция j_1), ..., 0)
-
3) p^0 = 1 рассм. аналогично
+
3) p^0 = 1 рассмотрим аналогично
Строка 65: Строка 65:
A~ = -A^T
A~ = -A^T
-
Предп, мы решили A^T (p*, q*, V)
+
Предположим, мы решили A^T (p*, q*, V)
A~(p*, j) ≥ V, j=1,m
A~(p*, j) ≥ V, j=1,m
Строка 72: Строка 72:
A(j,p*)≤-V,j=1,m
A(j,p*)≤-V,j=1,m
-
Точно ткже покзывается (сделть дома) A(q*, i) ≥ -V, i=1,2
+
Точно так же показывается (сделать дома) A(q*, i) ≥ -V, i=1,2
-
В таком случае (q*, p*, -V) обр. решение исх. игры с плат. мтрицей A.
+
В таком случае (q*, p*, -V) обр. решение исходной игры с платёжной матрицей A.
Пример:
Пример:
Строка 82: Строка 82:
1 -5
1 -5
-
Ндо трансп. матрицу:
+
Надо транспонировать матрицу:
1 0 4 -1
1 0 4 -1
Строка 94: Строка 94:
l_4(p) = 5-6p
l_4(p) = 5-6p
-
Теперь надо постр. эти прямые, найти минимум. и максимальную точку.
+
Теперь надо построить эти прямые, найти минимум и максимальную точку.
l_1(p)=l_2(p)
l_1(p)=l_2(p)
Строка 101: Строка 101:
~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: Строка 113:
Второе: итеративный метод Брауна.
Второе: итеративный метод Брауна.
-
Проводится имитация мнгокртного розыгрыш игры. И каждый раз игроки пытаются нхдить чистые стртегии. Потом изо всего множества выбр. чисты стратегий будут выбраны смеш., кторые будут явл. прибл. знач. решения игры.
+
Проводится имитация мнгократного розыгрыша игры. И каждый раз игроки пытаются находить чистые стратегии. Потом изо всего множества выбранных чистых стратегий будут выбраны смешанные, которые будут являться приближенным значением решения игры.
Игра A_n×m
Игра A_n×m
-
1)Игрки выбир. произв. чистые стратегии: i_1, j_1
+
1)Игроки выбирают произвольные чистые стратегии: i_1, j_1
-
Предпложим, что в игре проведено k шагов, предп., что первый игрок первую свою стратегию выбрал r_1 раз, вторую r_2 и ... n-ю r_n раз. Аналогично второй игрок l_1, ..., l_m раз.
+
Предположим, что в игре проведено 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 явл смеш. страт. (покзть дома)
+
Легко показать, что p^K, q^K является смешанной стратегией (показать дома)
-
Теперь K+1 шаг. На k+1 шаге. выбир какую-т чистую стртегия, предп., что у втргго игрок q^K --- оптимльная смеш. стртегия, и тогда, чтбы выбр. свю чистую стртегию, он макс. по i величину max_{i=1,n} A(i,q^k) = A(i_k+1,q^) = V^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.
+
Мы показали, как игрок выбирает стратегию на каждом очередном шаге. Аналогично второй игрок, он ищет min_{j=1,m} A(p^K, j) = A(p^K, j_k+1) = V^K_2.
Теперь увидим, что
Теперь увидим, что
Строка 136: Строка 136:
V^K_2 ≤ V ≤ V^K_1
V^K_2 ≤ V ≤ V^K_1
-
Теорема. 1) В метде Бруна предел при K ← ∞ V^K_1 равен пределу V^K_2 и равны они V.
+
Теорема. 1) В методе Брауна предел при K ← ∞ V^K_1 равен пределу V^K_2 и равны они V.
-
2) Пусть p^0 произв. пред. тчк посл. {p^k}, q^0 — {q^K}. Тогда p^0, q^0 — птим. смеш.ю стртегии для 1, 2 игроков.
+
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
Строка 148: Строка 147:
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
Строка 156: Строка 155:
A(i,q^ε)≤V+ε i=1,n
A(i,q^ε)≤V+ε i=1,n
-
на этом осн. конеч. метод Брауна: нч. с K≥K_0 V_1^K - V^K_2 ≤ &espilonб и стратегии будут ε-оптимльными (также дказать самостятельно)
+
на этом основании конечный метод Брауна: начинаем с K≥K_0 V_1^K - V^K_2 ≤ &espilon, и стратегии будут ε-оптимальными (также доказать самостоятельно)
-
Просте решение игры
+
Простое решение игры
-
Будем рассм. игру с матр. A_n×n
+
Будем рассматривать игру с матрицей A_n×n
-
Определение. Игра с матр. A_n×n дпускет прстое решение (p*, q*, V), если A(p*, )=V, j=1,n, A(i, q*)=V, i=1,n
+
'''Определение'''. Игра с матрицей A_n×n допускает простое решение (p*, q*, V), если A(p*, )=V, j=1,n, A(i, q*)=V, i=1,n
1
1
Строка 171: Строка 170:
I'=(1, .., 1) (n элементов)
I'=(1, .., 1) (n элементов)
-
Терема 1. Если игра с матр A дп. прстое решение, и опр. A невырожден, то решение нахд. по ким фрмулам:
+
'''Теорема 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}
Строка 177: Строка 176:
причём других решений нет.
причём других решений нет.
-
Доказательство.
+
'''Доказательство'''.
-
Рассм. систему, предп., чт V --- какое-т число.
+
Рассмотрим систему, предположим, что V --- какое-то число.
p*=VI'A^{-1}
p*=VI'A^{-1}
p*=VA^{-1}I
p*=VA^{-1}I
Строка 187: Строка 186:
V = V^2 I' A^{-1}I
V = V^2 I' A^{-1}I
-
1) V=0. Но этг быть не мжет, птому что тогда p* плучится нул. вектором, а этог быть немжет, ибо смешанная стратегия
+
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}
+
'''Теорема 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
+
'''Определение'''. пусть 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.
+
'''Теорема''' (о крайних оптимальных смешанных стратегиях). Пусть P* и Q* — множество оптимальных смешанных стратегий 1 и 2 соотв. игрока игры со смешанной стратегией и платёжной матрицей A, и V≠0 — значение игры. Для того, чтобы стратегии p* ∈ P* и q* ∈ Q* были крайними точками, необходимо и достаточно, чтобы матрица. A содержала квадратную невырожденную матрицу B, для игры которой p*^B и q*^B были бы простыми решениями и V(B)=V.
-
* V(B) — значение игры с матр. B
+
* V(B) — значение игры с матрицей B
-
* p*^B — вектр, плученный из p* вычёркиванием тех координат, кторые соотв. нмерам строк матр. A, не вшедших в B
+
* p*^B — вектор, полученный из p* вычёркиванием тех координат, которые соответствуют номерам строк матрицы A, не вошедшим в B
-
* анлоигчно пр. q*^B
+
* аналогично пр. q*^B
-
Рассм. ещё раз форм. этй теоремы. Тут два. утв. Перве тке: если мы берём крайние пт. смеш. стратегии игроков, то тогда в мтр. A найдётся подматр. B, такя, что p*^B и q*^B были бы простыми реш. и V(B)=V. Второе утв. — достаточность. Если мы берём ккие-т оптим. смеш. стртегии игроков и сущ. подматр. B, такя, что p*^B и q*^B были бы простыми реш. и V(B)=V, то тогда p* и q* будут смеш. страт.
+
Рассмотрим ещё раз формулировку этой теоремы. Тут два утверждения. Первое такое: если мы берём крайние оптимальные смешанные стратегии игроков, то тогда в матрице 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
+
'''Доказательство'''. Необходимость. Что у нас есть? Есть 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 в соотв. с доним из свойств пред. лекции)
+
Что мы делаем: строим множество индексов 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)
+
Строим множество 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
Строка 231: Строка 230:
A~ = A_4 A_5
A~ = A_4 A_5
-
Лемма. Первые k строк A~ линейно независимы. Первые l стлбцов A~ линейн независимы.
+
Лемма. Первые k строк A~ линейно независимы. Первые l столбцов A~ линейно независимы.
-
Дкажем первую часть, втрая аналгично. Пусть это не так. Тгда найдутся α_1, α_k, не все равные нулю, такие что ∑_{i=1}^k α_i a_ij = 0, j=1,h
+
Докажем первую часть, вторая аналогично. Пусть это не так. Тогда найдутся α_1, α_k, не все равные нулю, такие что ∑_{i=1}^k α_i a_ij = 0, j=1,h
-
Делаем следующее: бе части имнжим на q*_j и просуммируем:
+
Делаем следующее: обе части умножим на 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) (Посмотрим на мн-во I_2. Для первых d строк она равна V) = ∑_{i=1}^k α_i V = V ∑_{i=1}^k α_i
+
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 (это несильное огр., поск. мжн прибавить дно и то же ко всем эл-там матр, тогда птим. стартегия не изм.)
+
И поскольку V неравно 0 (это несильное ограничение, поскольку можно прибавить одно и то же ко всем элементам матрицы, тогда оптимальная стратегия не изменится)
-
Теперь рассм. α = (α_1, .., α_k, 0, ..., 0)
+
Теперь рассмотрим α = (α_1, .., α_k, 0, ..., 0)
p^ε = p*+εα, p^-ε = p* - εα
p^ε = p*+εα, p^-ε = p* - εα
-
При этом первые k p*_i бльше 0. Тгда мжно взять ε > 0 таке, что p^ε, p^-ε больше 0. Крме того
+
При этом первые 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
Строка 267: Строка 266:
p*=1/2 p^ε + 1/2 p^-ε
p*=1/2 p^ε + 1/2 p^-ε
-
Плучили, что p^ε и p^-ε --- оптимльные стратегии, и p* не крйняя, чт противоречит условию. Пртиворечие возн. только из того, что первые стрки линейн зависимы, знчит, ни линейн независимы.
+
Получили, что p^ε и p^-ε --- оптимальные стратегии, и p* не крайняя, что противоречит условию. Противоречие возникает только из-за того, что первые строки линейно зависимы, значит, они линейно независимы.
-
 
+
-
Точно также (показать дома), чт первые l стлбцв лин. независимы.
+
-
<!-- педедыв -->
+
Точно также (показать дома), что первые l столбцов линейно независимы.
-
Матр. A~ имеет ранг t &ge; max(k,l)
+
Матрица A~ имеет ранг t &ge; max(k,l)
-
Значит, найдётся квадр. невырожд. матрица B размером t&times;t, которая расп. в верхнем левом угу (не огр. общности)
+
Значит, найдётся квадратная невырожденная матрица B размером t&times;t, которая расположена в верхнем левом углу (не ограничивая общности)
-
Пкажем, что это та самая матрица B. Надо показать, что (p*^B, q*^B, V) простое решение.
+
Покажем, что это та самая матрица B. Надо показать, что (p*^B, q*^B, V) простое решение.
...
...
Строка 283: Строка 280:
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* q* --- ОСС. Существует B, p*^B, q*^B, V(B)=V. Небходимо дказать, что p*, q* --- кр.
-
Дказтельство от братного
+
Доказательство от обратного
p* - &alpha;p^1 + (1-&alpha;)p^2, p^1, p^2&isin;p*, &alpha;&isin(0,1)
p* - &alpha;p^1 + (1-&alpha;)p^2, p^1, p^2&isin;p*, &alpha;&isin(0,1)
Строка 301: Строка 298:
...
...
-
3. Это мнжество --- мнгогранник. И, находя все его крайние точки, мы ег предедлим. Т. . мы сможем описать множество всех смеш. стртегий.
+
3. Это множество --- многогранник. И, находя все его крайние точки, мы его определим. Таким образом мы сможем описать множество всех смешанных стратегий.
Пример:
Пример:
Строка 308: Строка 305:
A= 1 0 4
A= 1 0 4
-
У этой игры нет седл. точки в чистой стратегии.
+
У этой игры нет седловой точки в чистой стратегии.
2 4 2 0 4 0
2 4 2 0 4 0
Строка 332: Строка 329:
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)
Строка 353: Строка 350:
y&ge;0
y&ge;0
-
Вводятся перем. огр., таких переменных m штук.
+
Вводятся переменные ограничения, таких переменных m штук.
3. Общая задача линейного программирования: min_x (C,x)
3. Общая задача линейного программирования: min_x (C,x)
Строка 366: Строка 363:
y_i &ge; 0, i=1...k
y_i &ge; 0, i=1...k
-
Каждому двойств. гр. сопост. перем. y_j
+
Каждому двойственному ограничению сопоставляем переменную y_j
-
Лемма 1. Если x и y допустимые вектора, т (b,y)&ge;(c,x)
+
'''Лемма 1'''. Если x и y допустимые вектора, т (b,y)&ge;(c,x)
-
Лемма 2. Задачи 1 и 2 либ обе не им. решения, либо (c, x*) =(b,y*). Аналогично задачи 3 и 4.
+
'''Лемма 2'''. Задачи 1 и 2 либ обе не им. решения, либо (c, x*) =(b,y*). Аналогично задачи 3 и 4.
-
Лемма 3. Усл. дополн. неж. или принцип оптимальности. допустимые вектра x*, y*
+
'''Лемма 3'''. Усл. дополн. неж. или принцип оптимальности. допустимые вектора x*, y*
a) x*_j > 0 &rArr; A(y*, j) = c_j
a) x*_j > 0 &rArr; A(y*, j) = c_j
b) y*_j > 0 &rArr; A(i, *x) = b_i
b) y*_j > 0 &rArr; A(i, *x) = b_i

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

Методы решения матричных игр со смешанной стратегией

Сначала рассмотрим игры вида 2×m или n×2

В первом случае

  a_11 ... a_1m

A= a_21 ... a_2m

~p~ = (p, 1-p), o≤p≤1

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

l_j(p)=pa_ij+(1-p)a_ij

~p~^0 = (p^0, 1-p^0)


K_j=a_1j-a_2j

l_j(p)(a_1-a_2)p+a_1j

1) p^0 ∈ (0,1)

∃j_0, j_1: l_1(p^0)=l_j2(p^0) = V, K_j1≥0, K_2≤0

q^0 = (-K_j2/(K_j1-K_j2)) (это решение для K_1 q + K_j2(1-q)=0)

q^0 ∈[0,1] #доказать дома

~q~^0 = (0, ..., 0, q^0_1, 0, ..., 1-q^0, 0, ..., 0)

A(~p~, q^0) = ∑_{j=1}^m(a_1j p + a_2j(1-p))q^0_ = (a_{1 j_1}p + a_a_{2 j_1}(1-p))q^0+((a_{1 j_2}p + a_a_{2 j_2}(1-p)))(1-q^0) = l_j1(p)q^0+l_j2(p)(1-q^0)

~p~^0 = (p^0, 1-p^0)

l_j1(p^0) = V = l_j2(p^0)

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)

Таким образом, оптимальной стратегией второго игрока является (~p~^0, ~q~^0).

2) p^0=0

∃j_1(0) = V 
l_j1(p) ≤ V

Получаем чистую стратегию, ~q~^0 = (0, ..., 1 (пхиция j_1), ..., 0)

3) p^0 = 1 рассмотрим аналогично


n × 2

A_{n×2}

A~ = -A^T

Предположим, мы решили A^T (p*, q*, V)

A~(p*, j) ≥ V, j=1,m
-A^T(p*,j)≥V
A^T(p*,j)≤-V
A(j,p*)≤-V,j=1,m

Точно так же показывается (сделать дома) A(q*, i) ≥ -V, i=1,2

В таком случае (q*, p*, -V) обр. решение исходной игры с платёжной матрицей A.

Пример:

   -1  1
    0 -1
A= -4  2, 4×2
    1 -5

Надо транспонировать матрицу:

     1 0  4 -1
A = -1 1 -2  5

y=l_j(p), =1,4

l_1(p) = p-(1-p) = 2p-1
l_2(p) = 1-p
l_3(p) = 6p-2
l_4(p) = 5-6p

Теперь надо построить эти прямые, найти минимум и максимальную точку.

l_1(p)=l_2(p)
2p-1=1-p
p^0 = 2/
~p~^0 = (2/3, 1/3)

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

K_1=2, K_2=-1

Составляем уравнение:

k_1q+k_2(1-q)=0
2q-1+q=0
q^0 = 1/3
~q~^0 = (1/3, 2/3, 0, 0)

Окончательный ответ: ((1/3, 2/3, 0, 0), (2/3, 1/3), V=-1/3)

Второе: итеративный метод Брауна.

Проводится имитация мнгократного розыгрыша игры. И каждый раз игроки пытаются находить чистые стратегии. Потом изо всего множества выбранных чистых стратегий будут выбраны смешанные, которые будут являться приближенным значением решения игры.

Игра A_n×m

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, q^K является смешанной стратегией (показать дома)

Теперь 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.

Теперь увидим, что

V^K_1 = max_{i=1,n} A(i,q^k) ≥ min_{q∈ Q_m} max_{i=1,n} A(i,q) = V
V^K_2 = min_{j=1,m} A(p^K, j) ≤ max_{p∈P_n} min_{j=1,m} A(p, j) = V
V^K_2 ≤ V ≤ V^K_1

Теорема. 1) В методе Брауна предел при K ← ∞ V^K_1 равен пределу V^K_2 и равны они V. 2) Пусть p^0 произведение пред. точек посл. {p^k}, q^0 — {q^K}. Тогда p^0, q^0 — оптимальные смешанные стратегии для 1, 2 игроков.

ε-оптимальные смешанные стратегии.

p^ε, q^ε называются ε-оптимальными смешанными стратегиями, если

A(p^ε, q) ≥ V-ε, ∀q∈Q_m

A(p,q^ε)≤V+ε ∀p∈P_n

Можно показать такое утверждение (доказать самостоятельно)

p^ε, q^ε явл. ε-оптимальными, если выполняются следующие неравенства

A(p^ε, j) ≥ V-ε, j=1,m

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
I = ... (n элементов)
     1
I'=(1, .., 1) (n элементов)

Теорема 1. Если игра с матрицей A допускает простое решение, и определитель A невырожден, то решение находится по таким формулам:

p* = VI'A^{-1}; q*=VA^{-1}I, V = 1/{i'a^{01}I}

причём других решений нет.

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

Рассмотрим систему, предположим, что V --- какое-то число.

p*=VI'A^{-1}
p*=VA^{-1}I
V=A(p*, q*) = p*Aq*
V = VI'A^{-1} A VA^{-1}I = V^2 I' A^{-1}I
V = V^2 I' A^{-1}I

1) V=0. Но этого быть не может, потому что тогда p* получится нулевой вектор, а этого быть не может, ибо смешанная стратегия

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) — значение игры с матрицей 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}
J_1={1,..,l}, J_2={1,...,l,...h}

Матрицу A представляем таким образом:

A_1 A_2 A_3
A_4 A_5 A_6
A_7 A_8 A_9
     A_1 A_2
A~ = A_4 A_5

Лемма. Первые 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) (Посмотрим на множество I_2. Для первых d строк она равна V) = ∑_{i=1}^k α_i V = V ∑_{i=1}^k α_i

И поскольку V неравно 0 (это несильное ограничение, поскольку можно прибавить одно и то же ко всем элементам матрицы, тогда оптимальная стратегия не изменится)

Теперь рассмотрим α = (α_1, .., α_k, 0, ..., 0)

p^ε = p*+εα, p^-ε = p* - εα

При этом первые k p*_i больше 0. Тогда можно взять ε > 0 таке, что p^ε, p^-ε больше 0. Кроме того

∑_i=1^n p^ε_i = 1, ∑_i=1^n p^-ε_i = 1

Рассмотрим матрицу

A(p^ε, j) = A(p*, j) + εA(&lpha;, j)
j = 1, ..., h
A(p*, j) = V
A(α, j) = 0
j = h+1, ..., ,
A(p*, j) > V

Можно взять ε тке, чт A(α, j) b nulf

A(p^ε, j) > V, j=h+1, ..., m
A(p^ε, j) ≥ V, j=1..m
A(p^-ε, )≥V
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) простое решение.

...

A(p*, j) = B(p*^B, j) = V, j=1,t
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)

B без гр. общности нах. в левм верхнем углу.

A(p*,j)=B(p8^B, j), A(p*, j) = B(p*^B, j), A(p*, j) = B(p*^B, j), j=1,t

...

Свойства:

...

3. Это множество --- многогранник. И, находя все его крайние точки, мы его определим. Таким образом мы сможем описать множество всех смешанных стратегий.

Пример:

   2 4 0
A= 1 0 4

У этой игры нет седловой точки в чистой стратегии.

   2 4     2 0     4 0

B = 1 0 C = 1 4 D = 0 4

       0    1

B^-1 = 1/4 -1/3

V(B) = [(1,1)B^-1 (1,1)^T]^-1 = 4/3

p*^B = 4/3 (1,1)B^-1 = (1/3, 2/3)
q8^B = 4/ B^- (1 1)^T = (4/3, -1/3)
V(C) = 8/5
p*^C = (3/5, 2/5), q*^C = (4/5, 1/5)
p*^C=(-3/5, 2/5), q*^C = (4/5, 0, 1/5)
V=8/5
A(p*, j) ≥ 8/5, j=1,2,3
A(i,q*) = 8/5, i=1,2

D p8^D=(1/2,1/2)

q*^D=()1/2, 1/
V(D)=2 --- уже не кр.

Нужн перебирать все квадратные подматрицы, и если ...


Связь теории игр с линейным программированием

Вспомним простые методы линейного программирования.

A_m*n: x=(x_1, ..., x_n), y=(y_1, ..., y_m)

B=(b_1, .., b_m), C=(c_1, ..., c_n)

1. Первая задачаа: max_x (c,x)

Ax ≤ b
x ≥ 0

2. Двойственная задача

min_y (b,y)

yA≥c
y≥0

Вводятся переменные ограничения, таких переменных m штук.

3. Общая задача линейного программирования: min_x (C,x)

A(i,x) ≤ b_i, i=1...k
A(i, x) = b_i, i=k+1...m
x_j≥0, j=1...n

4. min_y (b,y)

A(y,j)=c_j, j=1...r
A(y, j) = c_j, j=r+1...n
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 b) y*_j > 0 ⇒ A(i, *x) = b_i

Контрольная.

Задачи

1. Найти седловую точку для игры, заданной матрицей.

2. Найти седловую точку для игры, заданной функцией F(x,y) = -x^2+y^2+y на [0,1]×[0,1]


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


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


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

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