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

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

• Аудиозапись: http://esyr.org/lections/audio/game_theory_2008_winter/GT_08_09_18.ogg

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

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