WWW.DISSERS.RU

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

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


Pages:     | 1 | 2 || 4 | 5 |

числа. Нужно пользоваться многими комбинациями. Если всюду ставить равенства, то задача не решается. Можно поставить строгие неравен а, i ={ij} – j -я смешанная стратегия i-го игрока, ства. Не везде. Распишем эти неравенства.

;

i N, i i, j = 1, ki 31 - 22 + 43 v 31 - 2 + 23;

– вероятность выбора i-м игроком j -й чистой стратегии, т. е.

ij - 1 + 42 + 23 v -21 + 42 + 23;

элемент вектора i, ;

i N, i i, j = 1,ki 21 + 22 + 63 v 41 + 22 + 63.

Ei() = Ei(1,…, n ) – функция выигрыша i-го игрока;

31 - 22 + 43 < v; 31 - 2 + 23 = v;

набор стратегий = (1,…,n), i i i N, называется - 1 + 42 + 23 = v; - 21 + 42 + 23 = v;

ситуацией игры.

21 + 22 + 63 = v; 41 + 22 + 63 > v.

Определение 3.11. Если X – конечное множество чистых стратегий i Составим квадратную матрицу, учитывая равенства. Следовательно, игрока i, то смешанная стратегия i : Xi [0,1] ставит в соответствие = если, то i = 0, если, то. Примем о E(i, y) < v E(x, j) > v j каждой чистой стратегии вероятность того, что она будет xij Xi ij 1 = 0; 3 = 0. Тогда 24 Введем следующие обозначения для чистых и смешанных стратеj играться, причем.

=i гий:

j=1,ki x =(x1jk,…, xijk1, xijk, xijk1,…, xnjk );

Определение 3.12. Выигрыш игрока i, соответствующий ситуации - +, есть (x || xi ) =(x1jk,…, xijk1, xijk, xijk1,…, xnjk );

- + n j Ei() = Ei(x). (3.11) = (1,…, i-1, i, i+1,…, n);

k xX k =( ||i ) = (1,…, i-1,i, i+1,…, n);

k = 1, ki, i = 1,n;

В случае биматричной игры формула (3.11) имеет вид ( || xij)=(1,…, i-1, xij, i+1,…, n);

2Ei(x)= 2Ei(x), i = 1,2.

1 …x x1 xn j j (x ||i)=(x1jk,…, xi-k1,ijk, xi+k1,…, xnjk ).

Пример 3.4. Рассмотрим игру Определение 3.14. Ситуация (набор смешанных стратегий) I II III = (1,...,n) является равновесием по Нэшу в игре, G = {N, {i}, {Ei}} I (4,3) (5,1) (6,2) если для любого i N II (2,1) (8,4) (3,6).

Ei() Ei( || i ) i i.

III (3,0) (9,6) (2,8) Теорема 3.8. Пусть Xi+ Xi – множество чистых стратегий, Пусть (это означает, что смешанная стратегия 1 = (1/ 3,1/ 3,1/ 3) которые игрок i играет с положительной вероятностью в ситуации игрока 1 предписывает ему играть стратегии I, II и III с вероятностями = (1,...,n). Ситуация является NE в смешанном расширении G каждую), (0, 1/2, 1/2) (эта смешанная стратегия игрока 1 3 2 = игры G тогда и только тогда, когда для всех i N предписывает играть стратегии II и III с равными вероятностями и не играть стратегию I вовсе).

Ei( || xij)= Ei( || xij) xij, xij Xi+;

В данном случае мы получаем в ситуации :

= (1, 2) (3.12) Ei( || xij) Ei( || xij) xij Xi+, xij Xi+.

1 1 E1() = 2E1(x) = 4 + 5 + 6 + Таким образом, необходимые и достаточные условия того, что си3 2 x туация – NE, состоят в том, что: 1) каждый игрок при данном распределении стратегий, которые играют его противники, безразличен между 1 1 1 1 1 1 0 + 2 + 8 + 3 + 3 + 9 + 2 =, чистыми стратегиями, которые он играет с положительной вероятнос3 2 2 3 2 2 тью; 2) эти чистые стратегии не хуже тех, которые он играет с нулевой вероятностью.

E2() = 2E2(x) =.

Это свойство можно использовать для нахождения NE в смешанных x стратегиях.

Определение 3.13. Смешанным расширением игры Пример 3.5. Рассмотрим следующую игру:

называется игра.

G = {N, X, K(x)} G = {N,, E()} 26 за A, то игрок 2 не изменит исход, как бы он ни голосовал, и игроку A B безразлично, как он голосует. Таким образом, и – NE, (A, A, A) (A, B, A) A (100,1000) (0,0).

но – не NE, так как игроку 2 лучше голосовать за B.

(A, A, B) B (0,0) (1000,100) Очевидно, что ситуации (А, А) и (В, В) являются NE (в чистых стратегиях). Найдем равновесия по Нэшу в смешанных стратегиях.

ЗАНЯТИЕ № Предположим, что в таком равновесии игрок 1 играет смешанную стратегию, а второй –, причем.

(p,1- p) (q,1- q) p, q (0,1) Нахождение значения игры при помощи линейного Тогда получаем, что ожидаемый выигрыш игрока 2 от игры при программирования (ЛП) использовании стратегии А есть, а от игры при 1000 p + 0(1 - p) Напомним, что существует три формы задачи ЛП (ЗЛП) использовании стратегии В есть, а значит 100 (1- p)+ 0 p m 1000 p + (1 - p) 0 = 100 (1- p)+ 0 p.

xi max : (4.1) ci i=Отсюда 1100 p = 100 и, следовательно,. Аналогично p =1 • общая задача (ограничения трех типов):

.

q =1 n Пример 3.6. «Семейный спор». Как в предыдущем примере, Она, xi bj, j =1, p;

aij выбирая Ф, получает, а выбирая Т, получает.

1 p + 0(1 - p) 0 p + 2(1- p) i=Следовательно,. Отсюда 3p = 2, а следовательно,.

2(1- p) = p p = 2 n xi bj, j = p +1, s; (4.2) Аналогично получаем, а значит, 3q = 2q + (1- q) 0 = 0 q +1(1- q) aij i=и. Таким образом, в смешанном равновесии Он играет Ф q = 1 n с вероятностью, а Она играет Ф с вероятностью.

2 3 1 xi = bj, j = s +1, m;

aij Пример 3.7. «Голосование». Рассмотрим следующую ситуацию – i=три игрока 1, 2, 3 и три альтернативы – A, B, C.

xi 0, i =1, n;

Игроки голосуют одновременно за одну из альтернатив, • основная задача (все ограничения – уравнения):

воздержаться невозможно. Таким образом, пространство стратегий n Xi = {A, B,C}. Альтернатива, получившая большинство, побеждает. Если xi = bj, j = 1, m; (4.3) aij ни одна из альтернатив не получает большинства, то выбирается i=альтернатива A. Функции выигрышей таковы:

xi 0, i = 1, n;

E1(A)= E2(B)= E3(C)= 2;

• каноническая задача:

E1(B) = E2(C) = E3(A) = 1;

n xi bj, j = 1, m; (4.4) aij E1(C) = E2(A) = E3(B) = 0.

i=В этой игре три равновесных исхода (в чистых стратегиях): A, B xi 0, i =1,n.

и C. Посмотрим на равновесия (их больше 3): если игроки 1 и 3 голосуют 28 Лемма 4.1 (о масштабе). Пусть и – две антагонистические GA GA Задача нахождения min cx при ограничениях x игры, причем (4.5) xA b, x 0, (4.7) A = A + B, > 0, = const, где А –, называется прямой (m n)-матрица, c, x Rm, b Rn B = {ij = = const i, j} а. Тогда max by стандартной ЗЛП, а задача, заключающаяся в определении при y Z(GA) = Z(GA), vG A = vGA +.

(4.8) ограничениях Иными словами, оптимальность поведения игроков не изменится, Ay c, y 0, (4.6) если в игре множества стратегий остаются прежними, а функция выиггде называется двойственной ЗЛП.

y Rn рыша умножается на положительную константу или (и) к ней прибавляется постоянное число.

Прямая задача (ПЗ) Двойственная задача (ДЗ) Содержательно данная лемма говорит о стратегической эквиваленn тности двух игр, отличающихся лишь началом отсчета выигрышей, m y min ;

xi max ; а также масштабом их измерения.

bj j ci j=i=Замечание 4.1. Если две МИ и находятся в условиях этой ой GA GA n m леммы, то смешанные расширения также стратегически эквивалентны.

y ci,i = 1, k ;

xi bj, j = 1, s;

aij j aij Лемма 4.2. Пусть и – две матричные GA GA (m n)-игры, причем j=i= A = A + B, > 0, = const, n m y = ci,i = k +1,m;

xi = bj, j = s +1, n;

aij j aij B = {ij = = const i, j} а. Тогда, vA +, Z(G )= Z(G ) vA = A A j=i=где G и – смешанные расширения игр и соответственно, G A A GA GA y 0, j =1, s.

xi 0, i =1,k ;

j a vA, vA– значения игр и.

GA GA x Rm Вектор, удовлетворяющий системе (4.5), называется Пример 4.1. Проверим, что стратегии y = (1 2,1 4,1 4), допустимым решением задачи (4.5). Аналогично вводится понятие оптимальны, а – значение игры с матрицей x = (1 2,1 4,1 4) vA = 0 G A y Rn допустимого решения задачи (4.6). Допустимое решение x(y) -1 - называется оптимальным решением задачи (4.5) ((4.6)), если на нем A = -1 -1.

достигается минимум (максимум) функции на множестве всех х cx(by) -1 3 -допустимых решений.

Справедливо следующее утверждение.

Упростим матрицу А (в целях получения максимального числа нуТеорема 4.1 (двойственности). Если задачи (4.5), (4.6) имеют лей). Прибавляя ко всем элементам матрицы А единицу, получим матрицу x y допустимые решения, то они имеют оптимальные решения и 2 0 соответственно, при этом.

cx = by A = 0 4.

Напомним, что множество всех ситуаций равновесия в МИ мы 0 4 обозначили как Z(GA).

30 Каждый элемент матрицы А разделим на 2. Новая матрица x*u = y*w = > 0. (4.11) принимает вид Пусть теперь – произвольная ом GA (m n)-МИ. Покажем, что в этом 1 0 случае теорема справедлива.

A = 0 2.

Рассмотрим векторы x = x* и y = y* и покажем, что они 0 2 являются оптимальными стратегиями игроков 1 и 2 соответственно По лемме 4.2 значение игр связано равенством vA = 1/ 2vA = в игре G, при этом значение игры равно.

A.

= 1/ 2(vA +1) Действительно, из (4.11) имеем Таким образом, требуется проверить, что значение игры равно GA xu =(x*u) =(y*w) = yw = 1,. Действительно, E(x, y) = xA, y = 1 2. С другой стороны, для 1 y* а из допустимости и для задач (4.9), (4.10) следует, что x = x* x* о каждой стратегии, y = (1,2,3) имеем E(x, y) = 1/ 21 +y II и y = y* 0, т. е. x и y – смешанные стратегии игроков 1 и +1/ 22 +1/ 23 = 1/ 2 1 = 1/ 2, а для всех x = (1,2,3),, x X в игре.

GA E(x, y) = 1/ 21 +1/ 22 +1/ 23 = 1/ 2. Следовательно, указанные стратеВычислим выигрыш игрока 1 в ситуации :

(x, y) гии являются оптимальными, а.

(x, y) vA = Докажем теорему 3.1.

E(x, y) = xA, y = x*A, y* 2.

(4.12) Теорема 3.1. Всякая МИ имеет ситуацию равновесия в смешанных стратегиях.

С другой стороны, из допустимости векторов и y* для задач ч x* Доказательство. ЗЛП в определенном смысле эквивалентна (4.9), (4.10) и равенства (4.11) имеем МИ.

GA = wy* x* A, y* = x*, Ay* x*u =.

Рассмотрим ПЗ и ДЗ ЛП:

max yw, min xu, x*A, y* = о Таким образом, ; из (4.12) получаем, что AyT u, (4.10) xA wT (4.9) (4.13) E(x, y) = 1.

y 0, x 0;

Пусть x, y – произвольные смешанные стратегии игроков T T где A = {ij > u = (1,...,1) Rm, w = (1,...,1) Rn, а матрица и 2. Тогда выполняются неравенства, т. е. строго положительная, откуда следует, что i = 1,m, j = 1,n} о E(x, y) = xA, y = x*A, y (wy) = 1 ;

(4.14) существует такой вектор, для которого xA wT, т. е. задача (4.9) x > E(x, y) = x, Ay = x, Ay* (xu) = 1.

(4.15) имеет допустимое решение. С другой стороны, вектор y = 0 является допустимым решением задачи (4.10), поэтому по теореме 4.Сравнивая (4.14) и (4.15), получаем, что – ситуация равновесия, (x, y) двойственности ЛП обе задачи (4.9) и (4.10) имеют оптимальные решения а – значение игры со строго положительной матрицей А.

1 GA м x*, y* соответственно, при этом 32 Теперь рассмотрим Введем 3,4 – базисные переменные, – свободные перемен(m n)-МИ с произвольной матрицей GA 1,ные. Заметим, что эти задачи в эквивалентной форме могут быть записаны A = { }. Тогда существует такая константа > 0, что матрица ij для ограничений типа равенств:

B = {ij}- (m n)-матрица, A = A + B – строго положительна, где min 1 + 2, max 1 + 2,. В игре существует ситуация равновесия ij =, i = 1,m, j = 1,n GA (x, y) 41 + 22 - 3 =1, 41 + 3 = 1, в смешанных стратегиях, а значение игры равно vA = 1, где 32 - 4 = 1, 21 + 32 + 4 = 1, определяется как в (4.11).

1 0,2 0,3 0,4 0; 1 0,2 0,3 0,4 0.

Из леммы 4.2 следует, что (x, y) Z(G ) – ситуация равновесия A Таким образом, методы решения ЗЛП могут быть приспособлены в игре в смешанных стратегиях, а значение игры равно GA vA = vA - = для решения МИ.

. Теорема доказана.

= 1 - Перепишем задачу Следует отметить, что не всегда в антагонистических играх сущеF = 1 + 2 min;

ствует решение в смешанных стратегиях.

Доказательство теоремы сводит решение МИ к ЗЛП.

41 + 22 - 3 = 1;

Алгоритм решения игры GA следующий.

32 - 4 = 1;

1. По матрице А’ строится строго положительная матрица, A = A + B 1,…,4 ij = > где B = {ij},.

в эквивалентном виде = R1 + R2 = 1- 41 - 22 + 3 +1- 32 + 4 = x*, y* 2. Решаются ЗЛП (4.9), (4.10). Находятся векторы и число [см. (4.11)].

= 2 - 41 - 52 + 3 + 4 min ;

3. Строятся оптимальные стратегии игроков 1 и 2:

41 + 22 - 3 + R1 = 1;

x = x* и y = y* соответственно.

- 4 + R2 = 1.

1. Вычисляется значение игры.

GA vA =1 - Составим симплекс-таблицу:

Пример 4.2. Рассмотрим МИ, определенную матрицей GA 4 1 2 3 4 R1 RA =. Соответствующие ей ЗЛП имеют следующий вид:

2 R1 4 2 –1 0 1 0 R2 0 3* 0 –1 0 1 min 1 + 2, max 1 + 2, 4 5 –1 –1 0 0 41 + 22 1, 41 1, и решим симплекс-методом (см. пример 1, стр. 59).

32 1, 21 + 32 1, 1 0,2 0; 1 0,2 0.

34 ~u ~u x = y = = 5 /12;

1 2 3 4 R1 RR1 4* 0 –1 2/3 1 –2/3 1/3 ~ 1 12 1 x x = =, = (1/ 5,4 / 5);

5 2 0 1 0 –1/3 0 1/3 1/5 12 5 4 0 –1 2/3 0 –5/3 2–5/~ 1 4 1 y y = =, = (3/ 5, 2 / 5).

1 1 0 –1/4 1/6 1/4 –1/6 1/ 5 5 12 5 2 0 1 0 –1/3 0 1/3 1/ 0 0 0 0 –1 –1 Пусть X и Y – множества оптимальных решений задач (4.9) и (4.10) соответственно. Обозначим 1 2 3 1 x 1 y X = x X Y = y Y > 0.

,, 1 1 0 –1/4 1/6 1/ 2 0 1 0 –1/3 1/Напомним, что множество оптимальных смешанных стратегий –1/4 –1/6 5/F обозначается, а проекции множества оптимальных стратегий – Z(GA). е.

1 =1/12; 2 =1/ 3; F = 5 /12. на и – * и * соответственно, т. е.

Z(GA) I II I II Решим теперь задачу * ={x* x* I, y* II, (x*, y*) Z(GA)};

I F = 1 + 2 max;

41 + 3 =1; * ={y* y* II, x* I, (x*, y*) Z(GA)}.

II 21 + 32 + 4 = 1;

Теорема 4.2. Пусть – GA (m n)-игра с положительной матрицей А 1,...,4 0.

и даны две двойственные задачи ЛП (4.9) и (4.10). Тогда возможны следующие варианты:

Составим симплекс-таблицу:

1. Обе ЗЛП имеют решение ( и ), при этом ом X 0 Y / / 1 2 3 = min xu = max yw.

2 4* 0 1 0 x y 4 2 3 0 1 x y 1 1 0 0 2. Значение игры равно, а стратегии x* =, y* = F vA GA vA = и решим симплекс-методом.

являются оптимальными, где – оптимальное решение прямой x X 1 2 3 4 1 2 3 задачи (4.9), а – двойственной задачи (4.10).

y Y 1 1 0 1/4 0 1/4 1 1 0 1/4 0 1/3. Любые оптимальные стратегии x* * и y* * игроков могут I II 4 0 3* –1/2 1 1/2 2 0 1 –1/6 1/3 1/1 0 1 –1/4 0 –1/4 0 0 –1/12 –1/3 –5/F F быть построены указанным способом, т. е.

* = X, * = Y.

I II 36 ~ Самостоятельная работа № Обозначим X = {x xA b} множество решений системы (5.1).

~ X Непосредственно из определения следует, что – выпуклое множество.

Найти ситуацию равновесия и значение игры в смешанных страте~ гиях при помощи ЛП. Сделать проверку.

Множество называется выпуклым многогранным множеством X м, заданным системой ограничений (5.1).

x M о, Определение 5.4. Точка, где – выпуклое множество, M ЗАНЯТИЕ № называется крайней точкой, если из условия x = x1 + (1- )x2,. Содержательно определение следует, что x1, x2 M, (0,1) x1 = x2 = x Графоаналитический метод решения (2 n)- либо (m 2)- матричных означает, что x M – крайняя точка, если не существует отрезка, игр (МИ) содержащего две точки из M, для которого x является внутренней.

Заметим, что крайняя точка выпуклого множества всегда является Распространенный способ решения МИ путем сведения ее к ЗЛП граничной; обратное неверно.

обладает тем недостатком, что процесс решения ЗЛП существенно усложняется для матриц большой размерности. В таких случаях обычно Определение 5.5. Выпуклой оболочкой множества Р conv(P) используют методы декомпозиции ЗЛП, когда вместо решения задачи будем называть пересечение всех выпуклых множеств, содержащих Р.

с исходной матрицей строится координирующая задача с матрицей, Данное определение эквивалентно следующему. Выпуклая оболочка у которой мало строк, но много столбцов, или наоборот.

множества Р состоит из всех выпуклых линейных комбинаций Напомним некоторые сведения из теории выпуклых множеств всевозможных точек из Р, т. е.

и систем линейных неравенств.

n x n.

M Rm называется выпуклым, если Определение 5.1. Множество conv(P)= x = xi, = 1, i 0, xi P i i i=1 i=вместе с любыми двумя точками этого множества в нем x1, x2 M Определение 5.6. Выпуклая оболочка конечного числа точек назысодержатся все точки отрезка.

x1 + (1- )x2, [0,1] вается выпуклым многогранником, порожденным своими крайними Понятие выпуклого множества можно сформулировать в более точками.

общем, но эквивалентном виде.

Определение 5.7. Напомним, что функция : M R1, где – M Rm Определение 5.2. Множество называется выпуклым, если M Rm выпуклое множество, называется выпуклой, если вместе с точками x1,…, xk из M оно содержит все точки вида (5.2) (x1 + (1- )x2) (x1)+ (1- )(x2) k k x = xi, i 0, = 1.

i i для любых и.

x1, x2 M [0,1] i=1 i= Если же в (5.2) выполняется обратное неравенство, то функция Пересечение выпуклых множеств всегда выпукло.

называется вогнутой.

Pages:     | 1 | 2 || 4 | 5 |






















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

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