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

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

Перейти к: навигация, поиск

Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.

Текущая версия Ваш текст
Строка 74: Строка 74:
Точно так же показывается (сделать дома) A(q*, i) ≥ -V, i=1,2
Точно так же показывается (сделать дома) A(q*, i) ≥ -V, i=1,2
-
В таком случае (q*, p*, -V) обр. решение исходной игры с платёжной матрицей A.
+
В таком случае (q*, p*, -V) обр. решение исходной игры с платёжной мтрицей A.
Пример:
Пример:
Строка 117: Строка 117:
Игра 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)
Строка 155: Строка 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
Строка 170: Строка 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}
Строка 176: Строка 176:
причём других решений нет.
причём других решений нет.
-
'''Доказательство'''.
+
Доказательство.
-
Рассмотрим систему, предположим, что V --- какое-то число.
+
Рассм. систему, предп., чт V --- какое-т число.
p*=VI'A^{-1}
p*=VI'A^{-1}
p*=VA^{-1}I
p*=VA^{-1}I
Строка 186: Строка 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
Строка 230: Строка 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
Строка 266: Строка 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 ≥ max(k,l)
+
<!-- педедыв -->
-
Значит, найдётся квадратная невырожденная матрица B размером t&times;t, которая расположена в верхнем левом углу (не ограничивая общности)
+
Матр. A~ имеет ранг t &ge; max(k,l)
-
Покажем, что это та самая матрица B. Надо показать, что (p*^B, q*^B, V) простое решение.
+
Значит, найдётся квадр. невырожд. матрица B размером t&times;t, которая расп. в верхнем левом угу (не огр. общности)
 +
 
 +
Пкажем, что это та самая матрица B. Надо показать, что (p*^B, q*^B, V) простое решение.
...
...
Строка 280: Строка 282:
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)
Строка 298: Строка 300:
...
...
-
3. Это множество --- многогранник. И, находя все его крайние точки, мы его определим. Таким образом мы сможем описать множество всех смешанных стратегий.
+
3. Это мнжество --- мнгогранник. И, находя все его крайние точки, мы ег предедлим. Т. . мы сможем описать множество всех смеш. стртегий.
Пример:
Пример:
Строка 305: Строка 307:
A= 1 0 4
A= 1 0 4
-
У этой игры нет седловой точки в чистой стратегии.
+
У этой игры нет седл. точки в чистой стратегии.
2 4 2 0 4 0
2 4 2 0 4 0
Строка 329: Строка 331:
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: Строка 352:
y&ge;0
y&ge;0
-
Вводятся переменные ограничения, таких переменных m штук.
+
Вводятся перем. огр., таких переменных m штук.
3. Общая задача линейного программирования: min_x (C,x)
3. Общая задача линейного программирования: min_x (C,x)
Строка 363: Строка 365:
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

Пожалуйста, обратите внимание, что все ваши добавления могут быть отредактированы или удалены другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. eSyr's_wiki:Авторское право).
НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!


Отменить | Справка по редактированию (в новом окне)

Шаблоны, использованные на этой странице:

Получено с http://esyr.org/wiki/%D0%A2%D0%B8%D0%B3%D1%80%D1%8B%2C_03_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%28%D0%BE%D1%82_18_%D1%81%D0%B5%D0%BD%D1%82%D1%8F%D0%B1%D1%80%D1%8F%29
Личные инструменты
Разделы