В общем случае схема решения игры 2xn или nx2 графическим методом состоит в следующем.

1. Строят прямые, соответствующие стратегиям второго (первого) игрока.

2. Находят две стратегии второго (первого) игрока, которым соответствуют две прямые, пересекающиеся в точке с максимальной (минимальной) ординатой. Эти стратегии являются активными в оптимальной смешанной стратегии второго (первого) игрока.

3. Находят координаты точки пересечения, тем самым определяя оптимальную стратегию первого (второго) игрока и цену игры.

4. Оптимальную стратегию другого игрока находят, решая систему уравнений, включающую его активные стратегии.

 

Пример 5.4. Найдите решение игры, заданной матрицей:

A =

7 9 8 10 6 9

.

 

Решение.

Сначала проверим наличие седловой точки: = 7, = 9. Поскольку нижняя и верхняя цены игры не совпадают, седловая точка отсутствует, и решение следует искать в смешанных стратегиях.

Выполним построения на плоскости XY в соответствии с методикой, приведенной выше. Результат представлен на рисунке 5.3.

 

 

Рисунок 5.3 – Геометрическая интерпретация игры примера 5.4

Точка М находится на пересечении отрезков, соответствующих стратегиям B₁ и B₂ второго игрока.

Найдем ее координаты:

B₁B^'₁:

= , откуда y = 3x + 7,

B₂B^'₂:

= , откуда y = -3x + 9,

 

3x + 7 = -3x + 9, 6x = 2, x = 1/3, т.е. = 2/3, = 1/3, цена игры v = 8.

Активными стратегиями игрока B являются стратегии B₁ и B₂, следовательно, = 0.

Используя выражение (5.2), вытекающее из теоремы об активных стратегиях, составим систему из двух уравнений с двумя неизвестными:

7 + 9 = 8, + = 1.

Второе уравнение умножим на семь и вычтем из первого:

2 = 1, = 1/2, = 1/2.

Ответ: U^* = (2/3, 1/3); Z^* = (1/2, 1/2, 0); v = 8.

 

Пример 5.5. Найдите решение игры, заданной матрицей:

A =

6 5 4 6 2 7 1 8

.

Решение.

Проверим наличие седловой точки.

= max (5, 4, 2, 1) = 5, = min (6, 8) = 6.

Седловая точка отсутствует, поэтому решение следует искать в смешанных стратегиях.

Выполним построения на плоскости XY в соответствии с методикой, приведенной выше. Результат представлен на рисунке 5.4.

 

 

Рисунок 5.4 – Геометрическая интерпретация игры примера 5.5

В данном случае необходимо отыскать точку, соответствующую минимальному гарантированному проигрышу. Такая точка (точка М) находится на пересечении отрезков, соответствующих стратегиям А₁ и А₄ игрока А.

Найдем координаты:

A₁A^'₁:

= , откуда y = -x + 6,

A₄A^'₄:

= , откуда y = 7x + 1,

 

7x + 1 = -x + 6, 8x = 5, x = 5/8, = 3/8, = 5/8, v = 43/8.

Активными стратегиями игрока A являются стратегии A₁ и A₄, следовательно, = = 0.

Используя выражение (5.1), вытекающее из теоремы об активных стратегиях, составим систему из двух уравнений с двумя неизвестными:

6 + = 43/8, + = 1.

Вычтем из первого уравнения второе:

5 = 35/8, = 7/8, = 1/8.

Ответ: U^* = (7/8, 0, 0, 1/8); Z^* = (3/8, 5/8); v = 43/8.

21.Доминирование смешанных стратегий для игрока A.

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

			…
			…
			…
…	…	…	…	…
			…

 

 

А=

Между множеством смешанных (в том числе и чистых) стратегий игрока А и выпуклыми комбинациями

строк ( матрицы А, представляющими собой строки выигрышей , j=1,2,…,n, игрока А в ситуациях , j=1,2,…,n, устанавливается взаимно-однозначное соответствие

из которого ясно, что, в частности, каждой чистой стратегии игрока А ставится во взаимно-однозначное соответствие k-я строка матрицы А.

Если для двух выпуклых комбинаций строк матрицы А

и

выполняются неравенства

то говорят, что строка (2) доминирует строку (1), а строка (1) доминирует строкой (2). Если каждое неравенство (3) является равенством, то строки (1) и (2) называют дублирующими. Если же каждое неравенство (3) является строгим, то говорят, что строка (2) строго доминирует строку (1), а строка (1) строго доминируется строкой (2).

Аналогичная терминология используется и для соответствующих стратегий игрока А. А именно, если строка (2) доминирует, соответственно дублирует, соответственно строго доминирует строку (1), то говорят, что стратегия доминирует, соответственно дублирует, соответственно строго доминирует стратегию .

Таким образом, по данным определениям и для игрока А, предпочтительными оказываются доминирующие стратегии.

22.Доминирование смешанных стратегий для игрока B.

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

			…
			…
			…
…	…	…	…	…
			…

 

 

А=

 

 

Между смешанными (в том числе и чистыми) стратегиями игрока В и выпуклыми комбинациями

^T,

столбцов ^T, j=1,2,…,n, матрицы А (Т- значок транспонирования), представляющими собой столбцы ^T

проигрышей Н(, i=1,2,…,m, игрока В в ситуациях (, i=1,2,…,m, устанавливается взаимно-однозначное соответствие

^T ,

из которого видно, что, в частности, каждой чистой стратегии , l =1,2,…,n, игрока В ставится во взаимно-однозначное соответствие l -й столбец ^T матрицы А.

Если для двух выпуклых комбинаций столбцов матрицы А

^T

и

^T

выполняются неравенства

то говорят, что столбец (4) (стратегия доминирует столбец (5) (стратегию , а столбец (5) (стратегия ) доминируется столбцом (4) (стратегией ). Если каждое неравенство (6) является равенством, то столбцы (4) и (5) (стратегии и ) называют дублирующими друг друга. Если же каждое неравенство (6) является строгим, то говорят, что столбец (4) (стратегия ) строго доминирует столбец (5) (стратегию ), а столбец (5) (стратегия ) строго доминируется столбцом (4) (стратегией ).

Таким образом, по данным определениям для игрока В предпочтительными оказываются доминирующие стратегии.

23. Решение матричной игры m × n сведением к задаче линейного программирования для игрока A.

Пусть дана матричная игра с матрицей А порядка m х n.

			…
			…
			…
…	…	…	…	…
			…

А=

 

P^o=(p1^o,p2^o,…,pm^o)

,

Если игрок А применяет любую смешанную стратегию P=(p1,p2,…,pm) против любой чистой стратегии B_j игрока В, то он получает выигрыш

F(P,B_j)=a₁jp₁+a₂jp₂+…+a_njp_m, j=1,2,…,n

.

Разделим каждое неравенство на V>0 и введем

x1=p1/v, x2=p2/v,…,xm=pm/v

Разделив на V>0 равенство , получим выражение x1+x2+…+xm=1/v

Получаем задачу линейного программирования для игрока А:

x1+x2+…+xm->min(поскольку первый игрок стремится найти такие значения хi и, следовательно, pi, чтобы цена игры v была максимальной)

P^o=(p1^o=x₁^o*V, p₂^o=x₂^o*V,…,p_m^o=x_m^o*V)

24. Решение матричной игры m × n сведением к задаче линейного программирования для игрока B.

Пусть дана матричная игра с матрицей А порядка m х n.

			…
			…
			…
…	…	…	…	…
			…

А=

Q^o=(q1^o,q2^o,…,qn^o)

Если игрок В применяет любую смешанную стратегию Q=(q1,q2,…,qm) против любой чистой стратегии A_i игрока A, то он получает проигрыш

F(P,B_j)=a₁jq₁+a₂jq₂+…+a_njq_m, j=1,2,…,n

.

Разделим каждое неравенство на V>0 и введем

y1=q1/v, y2=q2/v,…,ym=qm/v

Разделив на V>0 равенство , получим выражение y1+y2+…+ym=1/v

Получаем задачу линейного программирования для игрока В:

y1+y2+…+ym->max (поскольку второй игрок стремится найти такие значения yj и, следовательно, qj, чтобы цена игры v была наименьшей)

Q^o=(q1^o=y₁^o*V, q₂^o=y₂^o*V,…,q_m^o=y_m^o*V)

25. Основные понятия и определения теории игр с природой.

Во многих задачах финансово-экономической сферы принятие решения осложняется наличием неопределенности, заключающейся в неполноте информации об окружающей среде. Такую неопределенность могут порождать различные причины. Это могут быть действительные природные физические (климатические), биологические, химические, социальные и другие процессы, которые сопровождают экономическую деятельность, политика гос-ва и др. Поэтому в таких задачах принятие решения зависит от реальных условий, которые называют в соответствующей математической модели «природой». Саму же модель называют «игрой с природой». «Природа» может выступать как антагонистическая сторона, а может как кооперативная среда. Игру с природой можно определить как парную игру, в которой сознательный игрок А, заинтересованный в наиболее выгодном для него исходе игры, выступает против участника, совершенно безразличного к результату – природа (обозначим его П). Очевидно, что при решении игр с природой достаточно найти наилучшие рекомендации только для игрока А, потому как природа в рекомендациях не нуждается, развиваясь в соответствии с определенными законами независимо от того, удобно это человеку или нет.