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

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

Версия от 06:58, 13 октября 2010; Vissi (Обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

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


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

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