WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 2 | 3 || 5 |

Определение 5.3. Рассмотрим систему линейных неравенств xA b Лемма 5.1. Пусть i(x) – выпуклые на М функции. Тогда да i = 1,n или j верхняя огибающая этого семейства функций (x) xa, j N = {1, n}, (5.1) j j (x) = max i(x) (5.3) где.

(m n)-матрица, A = [a, j N] – x Rm, b = (1,…,n ) Rn i =1,n 38 является выпуклой на М, а нижняя огибающая (в (5.3) берется минимум Для каждого имеем:, E(x,1) = - + 2, E(x,2) = 2 +j = 1,по i) является вогнутой.

, Нижняя огибающая семейства а E(x,3) = -3 + 4 E(x,4) = 4. H() Теорема 5.1. В МИ множества оптимальных смешанных GA прямых и сами прямые, {E(x, j)} E(x, j) j = 1,4, изображены на рис. 5.1.

стратегий * и * игроков являются выпуклыми многогранниками.

I II Вернемся к теореме 3.7. В качестве примера использования теоремы приведем геометрическое решение игр с двумя стратегиями у одного из игроков ( (2 n)- и (m 2)-игры). Такой подход называется графоаналитическим методом решения е (2 n)- либо (m 2)-МИ. В основе графоаналитических методов лежит свойство оптимальных стратегий x* и y* доставлять экстремумы в критических точках ах vA = max min E(x, j)= min max E(i, y).

x j y i Пример 5.1. ( (2 n)-игра). Рассмотрим игру, в которой игрок 1 имеет две стратегии, а игрок 2 – п стратегий. Матрица имеет вид 11 12... 1n A = 22... 2n.

Рис. 5.1. Геометрическая интерпретация выигрыша первого игрока Пусть игрок 1 выбрал смешанную стратегию, а игрок x = (, 1- ) 2 чистую – j N. Тогда выигрыш игрока 1 в ситуации равен ен (x, j) Максимум функции находится на пересечении первой ой H(*) H() E(x, j) = 1 j + (1- )2 j. (5.4) и четвертой прямых. Таким образом, – решение уравнения * Геометрически он представляет собой прямую в координатах.

(, E) 4* = -* + 2 = vA.

Таким образом, каждой чистой стратегии j соответствует своя прямая.

Откуда получаем оптимальную стратегию игрока x* = (2 5,3 5) Графиком функции является нижняя огибающая H() = min E(x, j) j и значение игры. Оптимальную стратегию игрока 2 найдем из vA = 8 семейства прямых (5.4). Эта функция вогнута как нижняя огибающая следующих соображений. Заметим, что в рассматриваемом случае семейства вогнутых (в данном случае линейных) функций (лемма 5.1).

E(x*,1)= E(x*,4)= vA = 8 5.

Точка, в которой достигается максимум функции по, * H() [0,1] * Для оптимальной стратегии должно y* = (1, *, *, *) 2 3 дает требуемый оптимальный набор стратегий и значение x* = (*, 1- *) выполняться равенство игры.

vA = H(*) * vA = E(x*, y*)= 1E(x*,1)+ * E(x*, 2)+ *E(x*,3)+ * E(x*, 4).

2 3 Для определенности рассмотрим игру с матрицей При этом, следовательно,, E(x*,2)> 8 5, E(x*,3)> 8 5 * = * = 2 1 3 1 A =. * 2 1 4 а 1, * можно найти из условия (5.3):

40 ЗАНЯТИЕ № * * 1 + 4* = 8 5, 21= 8 5.

6.1. Доминирование стратегий в биматричной игре * Таким образом, 1 = 4 5 и * = 1 5 и оптимальная стратегия игрока а 2 равна.

y* = (4 5, 0, 0, 1 5) Покажем на примере, что существуют стратегии, которые заведомо выбирать не нужно, и вероятность выбора которых, согласно теореПример 5.2. ( (m 2)-игра). В этом примере две стратегии имеет мам 3.3–3.4, должна быть нулевой. Эта идея позволяет осуществлять игрок 2, а игрок 1 – т стратегий. Тогда матрица А имеет вид замену первоначальной матрицы на матрицу выигрышей меньшей размерности.

11 Пример 6.1. Рассмотрим следующую игру:

21 22.

A = Iy IIy IIIy … … m Ix (4,3) (5,1) (6,2) m IIx (2,1) (8,4) (3,6).

Анализ этой игры проводится аналогично. Действительно, пусть IIIx (3,0) (9,6) (2,8) y = (, 1- ) – произвольная смешанная стратегия игрока 2. Тогда выигрыш игрока 1 в ситуации равен (i, y) IIIy Независимо от того, как играет игрок 1, дает игроку 2 строго о IIy IIy больший выигрыш, нежели. В этом смысле стратегия строго E(i, y) = i1 + i2(1- ) = (i1 - i2) + i2.

IIy доминируема, поэтому рациональный игрок 2 не должен играть.

График функции – прямая. Рассмотрим верхнюю огибающую E(i, y) Далее, если игрок 1 знает (так как он сам рационален и знает, что другой этих прямых, т. е. функцию IIy рационален), что игрок 2 не будет играть, то для него Ix будет лучше, H() = max[(i1 - i2) + i2].

i чем IIx или IIIx. Наконец, если игрок 2 знает, что игрок 1 знает, что о Функция выпуклая (как верхняя огибающая семейства а H() IIy игрок 2 не будет играть, то игрок 2 знает, что игрок 1 будет играть Ix, выпуклых функций).

Iy а тогда игрок 2 должен играть. Естественно, что строго доминируемые Точка минимума функции дает оптимальную стратегию * H() стратегии надо удалять и в результате последовательного удаления строго = H(*)= min H().

и значение игры vA y* = (*, 1- *) (Ix, Iy) [0,1] доминируемых стратегий остается пара стратегий.

Пример 6.2. Посмотрим теперь на следующую игру:

Самостоятельная работа № Iy IIy Найти ситуацию равновесия и значение игры в смешанных страIx (4,0) (-1,0) тегиях графоаналитическим методом.

IIx (0,0) (0,0).

IIIx (-1,0) (2,0) 42 Смешанная стратегия может быть строго доминируемой, если она Здесь IIx не доминируется строго ни стратегией Ix, ни стратегией использует с положительной вероятностью чистые стратегии, которые IIIx. Однако, если игрок 1 играет Ix с вероятностью и IIIx – 1 даже не слабо доминируемы.

с вероятностью, он обеспечивает себе выигрыш независимо от т 1 2 1 2 Пример 6.3. Действительно, рассмотрим следующую игру:

того, как играет игрок 2. Следовательно, чистая стратегия может строго I IIy y доминироваться смешанной стратегией, даже если она не доминиIx (1,3) (- 2,0) руется строго никакой чистой стратегией.

IIx (- 2,0) (1,3).

Определение 6.1. Чистая стратегия xi игрока i в игре G строго IIIx (0,1) (0,1) доминируема, если существует другая чистая стратегия xi, такая, что о Стратегия игрока дает ожидаемый выигрыш -1 вне (1 2, 1 2, 0) Ki(x || xi ) Ki(x) x X, j =1, n, j i. (6.1) j зависимости от того, что играет игрок 2, а следовательно, строго доминируется стратегией IIIx.

В этом случае говорят, что стратегия xi доминирует страПример 6.4. Рассмотрим игру, где выигрыши могут принимать знатегию xi.

чения Определение 6.2. Стратегия xi слабо доминируется, если Iy IIy существует такая xi, что (6.1) выполняется как нестрогое неравенство, (20,10) (15,20) Ix.

Ix (–100,20) (40,30) {x j = 1, n, j i} но хотя бы для одного набора – неравенство строгое.

j Аналогично определение и для смешанных стратегий:

Iy IIy Очевидно, что здесь стратегия доминируется стратегией, но Определение 6.3. Смешанная стратегия i строго доминируется (IIx, Iy) проигрыш игрока 1 в ситуации слишком велик, поэтому вполне в игре, если существует другая стратегия i :

G можно допустить, что игрок 1 может не рискнуть сыграть стратегию IIx, Ei( ||i ) Ei(), j =1, n, j i. (6.2) допуская возможность случайной ошибки игрока 2.

j Стратегия i называется строго доминирующей стратегией для 6.2. Доминирование стратегий в антагонистической игре игрока i в игре, если она строго доминирует любую другую стратегию G Определение 6.4. Говорят, что стратегия игрока 1 доминирует т x из i.

стратегию в x (m n)-игре, если для всех чистых стратегий GA j = 1,n Заметим, что для проверки строгой доминируемости i стратегией i нам нужно знать «поведение» этих двух стратегий против чистых игрока 2 выполняются неравенства стратегий оппонентов игрока i, т. е.

j j x a x a. (6.3) Ei( ||i ) Ei(), j = 1, n, j i j 2 тогда и только тогда, когда Например, в матрице 3 4 3-я строка доминируется 2-й, т. е.

3 Ei(x ||i ) > Ei(x ||i ) x X, j =1, n, j i.

j 44 существуют, такие, что:

о:

x = (0, 1, 0) x = (0, 0, 1) Теорема 6.1. Если в игре стратегия x одного из игроков домиG A нирует оптимальную стратегию этого игрока, то стратегия также x* x е 0 2 +1 3 + 0 3 0 2 + 0 3 +1 3;

оптимальна.

0 5 +1 4 + 0 2 0 5 + 0 4 +1 2.

Отсюда вывод, что оптимальная стратегия может быть доминируеАналогично, стратегия игрока 2 доминирует ма лишь оптимальной стратегией. С другой стороны, никакая оптимальy т его стратегию ная стратегия не является строго доминируемой, поэтому строго доми, если для всех чистых стратегий i = 1, m игрока y нируемые стратегии не могут быть оптимальными.

ai y ai y. (6.4) Теорема 6.2. Если в игре стратегия одного из игроков ов x* G A Если неравенства (6.3), (6.4) выполняются как строгие, то говорят оптимальна, то x* – недоминируема строго.

о строгом доминировании. Частным случаем доминирования стратегий Обратное утверждение неверно.

является их эквивалентность.

1 Пример 6.5. Так, в игре с матрицей 0 2 1-я и 2-я чистые Определение 6.5. Будем называть стратегии x и x игрока эквивалентными в игре, если для всех стратегии игрока 1 недоминируемы строго, но они неоптимальны.

GA j = 1,n С другой стороны, если i-я строка (j-й столбец) матрицы А j j (6.3) x a = x a доминируемы, то нет необходимости приписывать ей (ему) положительную вероятность в ситуации равновесия. Таким образом, для и обозначать ~. Для двух эквивалентных стратегий и x x x x нахождения оптимальных стратегий вместо игры достаточно решить GA выполняется (для каждого ) равенство о y II подыгру, где A – матрица, получаемая из матрицы A вычеркиванием GA.

E(x, y) = E(x, y) доминируемых строк и столбцов.

Аналогично, стратегии и игрока 2 эквивалентны ( ~ ) y y y y Определение 6.6. Если x = (1,...,m )I и о 1 i m +1, то в игре, если для всех i = 1, m GA расширением стратегии на i-м месте будем называть вектор x y ai = y ai. (6.4).

xi = (1,..., i-1, 0, i,..., m ) Rm+Пример 6.6. Так, расширением вектора на 2-м месте Отсюда имеем, что для любой смешанной стратегии игрока (1 3,2 3, 1 3) а x I 1 выполняется равенство является вектор ; расширением на 4-м месте – вектор (1 3,0, 2 3, 1 3) E(x, y ) = E(x, y ).

; расширением на 1-м месте – вектор.

(1 3, 2 3, 1 3, 0) (0, 1 3, 2 3, 1 3) Для чистых стратегий введенные определения трансформируются Теорема 6.3. Пусть дана – о GA (m n)-МИ. Предположим, что i-я следующим образом. Если чистая стратегия игрока 1 доминирует i т строка матрицы А доминируема (т. е. доминируема чистая стратегия i чистую стратегию, а чистая стратегия игрока 2 – чистую i j ую первого игрока) и пусть дана – игра с матрицей A, получаемой из GA стратегию того же игрока, то для всех выполняются j ся i = 1, m, j = 1, n матрицы А вычеркиванием i-й строки. Тогда справедливы следующие неравенства утверждения:

1..

vA = vA ij ij, ij ij.

2. Всякая оптимальная стратегия игрока 2 в игре является ся Покажем, что игроки могут не использовать доминируемые стра- y* GA тегии. Этот факт устанавливает следующую теорему.

оптимальной и в игре.

GA 46 Пример 6.7. Рассматривается игра с матрицей 3. Если x* – произвольная оптимальная стратегия игрока 1 в игре и – расширение стратегии на i-м месте, то – оптимальная 2 1 1 о GA xi* x* xi* стратегия этого игрока в игре.

GA 2 3 1 3.

A = 3 1 2 4. Если i-я строка матрицы А строго доминируема, то оптимальная 0 3 0 стратегия x* игрока 1 в игре может быть получена из оптимальной GA стратегии x* в игре расширением на i-м месте.

GA Так как каждое значение 3-й строки a3 превосходит соотСформулируем теорему о доминировании для второго игрока.

ветствующее значение первой (a3 a1), то, вычеркивая первую строку,, Теорема 6.4. Пусть дана – о GA (m n)-МИ. Предположим, что j-й получаем столбец матрицы А доминируем и пусть дана – игра с матрицей A, G A 2 3 1 получаемой из матрицы А вычеркиванием j-го столбца. Тогда A1 = 1 2 0.

справедливы следующие утверждения:

0 3 0 1..

vA = vA В этой матрице каждое значение 3-го столбца a3 не превосходит 2. Всякая оптимальная стратегия x* игрока 1 в игре является ся GA соответствующее значение 1-го столбца a1. Поэтому получаем оптимальной и в игре.

GA 3 1 3. Если y* – произвольная оптимальная стратегия игрока 2 в игре A2 = 2 0.

и y* – расширение стратегии о y* – оптимальная GA j y* на j-м месте, то j 3 0 стратегия этого игрока в игре.

GA В последней матрице никакая строка (столбец) не доминируется 4. Далее, если j-й столбец матрицы А строго доминируем, то другой строкой (столбцом). Вместе с тем 1-й столбец a1 превосходит оптимальная стратегия GA y* игрока 2 в игре может быть получена из выпуклую линейную комбинацию столбцов a2 и, так как ак aоптимальной стратегии GA y* в игре расширением на j-м месте.

, поскольку a1 1 2a2 +1 2a3 3 > 1 2 +1 2 3, 1 = 1 2 2 +1 2 0, Обобщим полученные результаты. Теоремы 5.3–5.4 дают алгоритм. Исключая 1-й столбец, получаем понижения размерности матрицы игры. Так, если строка (столбец) мат- 3 = 0 1 2 +1 2 рицы не больше (не меньше) некоторой выпуклой линейной комбина1 ции остальных строк (столбцов) этой матрицы, то для нахождения ре2 0.

шения игры можно эту строку (столбец) вычеркнуть. При этом соответ0 ствующее расширение оптимальных стратегий в игре с усеченной мат- В этой матрице 1-я строка эквивалентна смешанной стратегии рицей даст оптимальное решение исходной игры. Если неравенства выполнялись как строгие, то множество оптимальных стратегий в перво, поскольку. Таким x = (0,1 2, 1 2) 1 = 1 2 2 + 0 1 2, 3 = 0 1 2 + 6 1 начальной игре можно получить расширением множества оптимальных образом, исключая 1-ю строку, получаем матрицу стратегий усеченной игры, в противном случае при такой процедуре 2 оптимальные стратегии можно потерять.

.

0 48 k Оптимальные стратегии x* и y* игроков в игре с этой матрицей k k v = max k = k и vk = min i = ij j ik +1 j j i.

ij ijk +i j j j i i равны x* = y* = (3 4, 1 4) 3, при этом значение v игры равно.

Пусть – значение МИ. Рассмотрим отношения Последняя матрица получена вычеркиванием первых двух строк v GA и столбцов, поэтому оптимальными стратегиями игроков в исходной игре k v k = max kj k = k k, (7.1) ij ik +1 j j являются расширения указанных стратегий на 1-м и 2-м местах, т. е.

i j j * *.

x12 = y12 = (0, 0, 3 4, 1 4) k k vk k = min i k = i k. (7.2) Заметим, что поскольку в решении использовалось нестрогое доij ijk +j i i минирование, то могут быть потеряны другие оптимальные стратегии.

k k Векторы и являются ся xk = (1 k,..., k k) yk = (1 k,..., k k) m n Самостоятельная работа № смешанными стратегиями игроков 1 и 2 соответственно, поэтому по определению значения игры имеем Рассмотреть игру на доминирование и найти ситуацию равновесия.

k max vk k v min v k.

k k Таким образом, получен некоторый итеративный процесс, ЗАНЯТИЕ № позволяющий находить приближенное решение МИ, при этом степень близости приближения к истинному значению игры определяется длиной Итеративные методы решения матричных игр k интервала [max vk k, min v k]. Сходимость алгоритма гарантируется k k 7.1. Итеративный метод Брауна – Робинсона (метод фиктивного следующей теоремой.

разыгрывания) Теорема 7.1.

Идея метода – многократное фиктивное разыгрывание игры с k min max lim v k = lim vk k = v.

заданной матрицей выигрыша. Одно повторение игры будем называть k k k k A = {ij} партией. Пусть разыгрывается игра с. В 1-й (m n)-матрицей Пример 7.1. Найти приближенное решение игры с матрицей партии оба игрока выбирают совершенно произвольные чистые a b c стратегии. В k-й партии каждый игрок выбирает ту чистую стратегию, 2 1 которая максимизирует его ожидаемый выигрыш против наблюдаемого A = 0 1.

эмпирического вероятностного распределения противника за -1) (k 2 партий.

Итак, предположим, что за первые k разыгрываний игрок a,b,c Обозначим,, – стратегии игрока 1 и – стратегии игрока 2.

k использовал i-ю стратегию раз, а игрок 2 – j-ю стратегию i (i = 1, m) Пусть сначала игроки выбрали стратегии и соответственно. Если a игрок 1 выбрал стратегию, то игрок 2 может потерять один из k раз. Тогда в ать ( j = 1, n) (k +1)-й партии игрок 1 будет использовать j выигрышей -1, - 3) a. Если игрок 2 выбрал стратегию, то игрок (- 2, де ik +1-ю стратегию, а игрок 2 – свою jk +1-ю стратегию, где может получить один из выигрышей. Во 2-й и 3-й партиях игрок (2, 3, 1) 50 В таблице приведены результаты разыгрываний, указаны страте1 выбирает стратегию, а игрок 2 –, поскольку эти стратегии обеспеb гия игрока, накопленный и средний выигрыши.

чивают наилучший результат и т. д.

Таким образом, за 12 партий мы получили приближение решения Вычислим средний выигрыш за первые три шага:

,, а точность может быть оценена x12 = (1 4,1 6,7 12) y12 = (1 12,1 2,5 12) числом. Основным недостатком рассмотренного метода является его о 1 v1 1 = max (1j 1)= ij i j малая скорость сходимости, которая уменьшается с ростом размерности матрицы. Это является также следствием немонотонности последова= max{(2 1+1 0 + 3 0); (31+ 0 0 +1 0); (11+ 2 0 +1 0)}= i k тельностей и vk k.

v k = max{2; 3; 1}= 3;

Pages:     | 1 |   ...   | 2 | 3 || 5 |






















© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.