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

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

(Различия между версиями)
Перейти к: навигация, поиск
Строка 1: Строка 1:
 +
* '''Аудиозапись:''' http://esyr.org/lections/audio/game_theory_2008_winter/GT_08_09_18.ogg
 +
Методы решения матр. игр со смеш. стртегией
Методы решения матр. игр со смеш. стртегией

Версия 16:07, 20 сентября 2008

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

Сначала рассмотрим игры вида 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


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

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