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

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

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

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

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

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

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

В первом случае
   a_11 ... a_1m
A= a_21 ... a_2m

~p~ = (p, 1-p), o&le;p&le;1

A(p, j) = pa_1j+(1-p)a_2j

В этом случае значение игры V = max_{~p~} &isin; P_@ min_{j=1,m} A(~p~, j) = max_{p&isin;[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 &isin; (0,1)

&exist;j_0, j_1: l_1(p^0)=l_j2(p^0) = V, K_j1&ge;0, K_2&le;0

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

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

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

A(~p~, q^0) = &sum;_{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 
 &exist;j_1(0) = V 
 l_j1(p) &le; V

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

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

n &times; 2

A_{n&times;2}

A~ = -A^T

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

A~(p*, j) &ge; V, j=1,m
 -A^T(p*,j)&ge;V
 A^T(p*,j)&le;-V
 A(j,p*)&le;-V,j=1,m

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

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

Пример:
    -1  1
     0 -1
 A= -4  2, 4&times;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&times;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) &ge; min_{q&isin; Q_m} max_{i=1,n} A(i,q) = V
 V^K_2 = min_{j=1,m} A(p^K, j) &le; max_{p&isin;P_n} min_{j=1,m} A(p, j) = V

V^K_2 &le; V &le; V^K_1

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

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

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

A(p^&epsilon;, q) &ge; V-&epsilon;, &forall;q&isin;Q_m

A(p,q^&epsilon;)&le;V+&epsilon; &forall;p&isin;P_n

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

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

A(p^&epsilon;, j) &ge; V-&epsilon;, j=1,m

A(i,q^&epsilon;)&le;V+&epsilon; i=1,n

на этом основании конечный метод Брауна: начинаем с K&ge;K_0 V_1^K - V^K_2 &le; &espilon, и стратегии будут &epsilon;-оптимальными (также доказать самостоятельно)

Простое решение игры

Будем рассматривать игру с матрицей A_n&times;n

'''Определение'''. Игра с матрицей A_n&times;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|&ne;0, то он имеет. ед. пару смеш. страт.: p*=I'A^{-1}/{i'a^{01}I}, q* = A^{-1}I/{i'a^{01}I}

Теперь мы можем перейти к основному методу, дающему все решения.

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

'''Определение'''. пусть x_0&isin; X. Точка называется крайней, если не существует x_1, x_2 &isin; X, x_1&ne;x_2, &alpha;&isin;(0,1), x_0 = &alpha;x_1 + (1-&alpha;)x_2

'''Теорема''' (о крайних оптимальных смешанных стратегиях). Пусть P* и Q* — множество оптимальных смешанных стратегий 1 и 2 соотв. игрока игры со смешанной стратегией и платёжной матрицей A, и V&ne;0 — значение игры. Для того, чтобы стратегии p* &isin; P* и q* &isin; 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&gt;0}; I_2={i:A(i,q*)=V} (I_1&isin;I_2 в соответствии с одним из свойств предыдущей лекции)

Строим множество J_1={j:q*_j &gt;0}, J_2={j:A(p*,q)=V} (J_1 &isin; 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~ линейно независимы.

Докажем первую часть, вторая аналогично. Пусть это не так. Тогда найдутся &alpha;_1, &alpha;_k, не все равные нулю, такие что &sum;_{i=1}^k &alpha;_i a_ij = 0, j=1,h

Делаем следующее: обе части умножим на  q*_j и просуммируем:

0=&sum;_{j=1}^h q*_j &sum;_{i=1}^k &alpha;_i a_ij = &sum;_{i=1}^k &alpha;_i &sum;_{j=1}^h q*_j  a_ij = &sum;_{i=1}^k &alpha;_i &sum;_{j=1}^m q*_j  a_ij (почему так можно написать — потому что дальше координаты равны 0) (Посмотрим на множество I_2. Для первых d строк она равна V) = &sum;_{i=1}^k &alpha;_i V = V &sum;_{i=1}^k &alpha;_i

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

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

p^&epsilon; = p*+&epsilon;&alpha;, p^-&epsilon; = p* - &epsilon;&alpha;

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

&sum;_i=1^n p^&epsilon;_i = 1, &sum;_i=1^n p^-&epsilon;_i = 1

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

A(p^&epsilon;, j) = A(p*, j) + &epsilon;A(&lpha;, j)

j = 1, ..., h
 A(p*, j) = V
 A(&alpha;, j) = 0

j = h+1, ..., ,
 A(p*, j) > V

Можно взять &epsilon; тке, чт A(&alpha;, j) b nulf
 A(p^&epsilon;, j) > V, j=h+1, ..., m

A(p^&epsilon;, j) &ge; V, j=1..m
 A(p^-&epsilon;, )&ge;V
 p*=1/2 p^&epsilon; + 1/2 p^-&epsilon;

Получили, что p^&epsilon; и p^-&epsilon; --- оптимальные стратегии, и p* не крайняя, что противоречит условию. Противоречие возникает только из-за того, что первые строки линейно зависимы, значит, они линейно независимы.

Точно также (показать дома), что первые l столбцов линейно независимы.

Матрица A~ имеет ранг t &ge; max(k,l)

Значит, найдётся квадратная невырожденная матрица B размером t&times;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* - &alpha;p^1 + (1-&alpha;)p^2, p^1, p^2&isin;p*, &alpha;&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) &ge; 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 &le; b
 x &ge; 0

2. Двойственная задача
 min_y (b,y)
 
 yA&ge;c
 y&ge;0

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

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

A(i,x) &le; b_i, i=1...k
 A(i, x) = b_i, i=k+1...m
 x_j&ge;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 &ge; 0, i=1...k

Каждому двойственному ограничению сопоставляем переменную y_j

'''Лемма 1'''. Если x и y допустимые вектора, т (b,y)&ge;(c,x)

'''Лемма 2'''. Задачи 1 и 2 либ обе не им. решения, либо (c, x*) =(b,y*). Аналогично задачи 3 и 4.

'''Лемма 3'''. Усл. дополн. неж. или принцип оптимальности. допустимые вектора x*, y*
a) x*_j > 0 &rArr; A(y*, j) = c_j
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

@@ Строка 372: / Строка 372: @@
 a) x*_j > 0 &rArr; A(y*, j) = c_j
 b) y*_j > 0 &rArr; A(i, *x) = b_i
-Контрольная.
-Задачи
-. Найти седловую точку для игры, заданной матрицей.
-. Найти седловую точку для игры, заданной функцией F(x,y) = -x^2+y^2+y на [0,1]&times;[0,1]
 {{Тигры}}
 {{Lection-stub}}

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

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

Просмотры

Личные инструменты

Навигация

инструменты

Разделы

Спецкурсы

9 семестр

7 семестр

5 семестр

3 семестр

Поиск

Инструменты