Игровые методы и модели

Практическая работа №9  Игровые методы и модели

 

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

 

“Экономика – это  поиск и выбор оптимального способа  действий”.

Теория игр представляет собой  теоретические основы математических моделей принятия оптимальных решений  в конфликтных ситуациях рыночных отношений, носящих характер конкурентной борьбы, в которой одна противоборствующая сторона выигрывает за счет проигрыша другой. Наряду с такой ситуацией в теории принятия решений также рассматривают ситуацию  риска и ситуацию неопределенности.

Рассмотрим ситуацию риска, предполагающую не только возможные условия, в которых  нужно принимать решение, но и  вероятности  их появления.

При рассмотрении вопроса выбора решения, в экономических ситуациях, сталкиваются не менее 2-х сторон, которые различными способами действуют на ситуацию и выбор которых зависит от действий  противоборствующей стороны. Такие ситуации называются конфликтными и характеризуются следующими чертами:

1. Наличие заинтересованных сторон.
2. Существование возможных действий каждой из сторон.
3. Интересы сторон.

Заинтересованные стороны  называют игроками.

Любое возможное в  игре действие игрока называется его чистой стратегией. Игра является конечной, если множество стратегий каждого игрока конечно.

Оптимальной  называется  стратегия, которая при многократно повторяющейся игре гарантирует игроку максимально возможный средний выигрыш (средний проигрыш). Выбор оптимальной стратегии базируется на принципе разумности в одинаковой степени и поведении каждого игрока.

Если в парной игре (2 игрока) игроки преследуют противоположные цели, то  игра называется антагонистической. В такой игре один из игроков выигрывает  ровно столько, сколько проигрывает другой.

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

Если игроки А и В независимо друг от друга выбрали смешанные стратегии Р = (р₁, … , р_т), Q = (q₁, …, q_n), то упорядоченная пара  (P, Q) – называется  ситуацией в смешанных стратегиях.

Выигрыш игрока А в ситуации (P, Q) в смешанных стратегиях представляет дискретную случайную величину, принимающую значения  a_{i j}   с вероятностью  p_i · q_j. Средний выигрыш игрока А  - есть  математическое ожидание указанной случайной величины

     (1)

Функция выигрыша игрока А в смешанных стратегиях:

H (P, Q) =

    (2)

(P, Q) S_A × S_B      (S_A × S_B – декартово произведение множеств). D×E = {(d, e) : d D, e E}. d – первая координата сомножителя множества D, e – вторая координата сомножителя множества E), где Р = (р₁, р₂, … , р_т)     Q = (q₁, q₂, …, q_n). Также данную функцию можно представить в виде матричной формы :

      H (P, Q) = РA Q^T     (3)

P = (p₁, …, p_m) - вектор-строка размера 1×ò.

 

A^выигр. =  - матрица игры (выигрыша игрока А

в чистых стратегиях)

Q^T =

Координаты чистой стратегии  А_k (k = ) в базисе А₁, …,  А_т можно записать с помощью символа Кронекера

б

   i = 1, …, k, …, m,

А_k = (б , …, б )  (k = ) ,   при  Р = А_k

 H (А_k, Q) =

Для каждой смешанной стратегии  P S_A  игрока  А  существует

α (Π, S_B) = min  H (P, Q)     (4)

Q S_B

 

Для каждой смешанной стратегии  Q S_B игрока В существует

β (Q, S_A) = max H (P, Q)     (5)

  P S_A

 

α (Π, S_B) – показатель эффективности смешанной стратегии, P S_A игрока А относительно множеств S_B смешанных стратегий игрока В.

β (Q, S_A) – показатель неэффективности смешанной стратегии Q S_B  игрока В относительно множества S_A смешанных стратегий игрока А.

Нижняя цена игры в смешанных  стратегиях

V = max α (Π) = max     min H (P, Q)   (4’)

               P S_A        P S_A     Q S_B

Верхняя цена игры в смешанных стратегиях

= min β (Q) = min     max H (P, Q)   (5’)

Q S_B  Q S_B  P S_A

 

Если   V = = V – цена игры в смешанных стратегиях, тогда H (P⁰, Q⁰) - оптимальные смешанные стратегии, то

α ? V = β

Любая пара оптимальных  стратегий P⁰, Q⁰  и  V – цена игры, образуют частное решение в смешанных стратегиях.

Если первоначально  дана только матрица игры  А^выигр., то согласно теореме:

Для того, чтобы число V было ценой игры, а P⁰  и Q⁰ – оптимальными стратегиями, необходимо и достаточно выполнение неравенств:

H (P⁰, В_j) =

 (j = )   (6)

H (A_i, Q⁰) =

  (i = )   (7)

Для оптимальной стратегии  игрока  А    Р ⁰ = (р )  и цены игры V выполняется неравенство (6)

Тогда, разделив обе части  на V

 

      (j = )

Пусть  ,  тогда        

 

Т.к. первый игрок стремится  получить максимальный выигрыш, то он должен обеспечить минимум величины 1/V. Определение оптимальной стратегии первого игрока сводится к нахождению минимального значения функции  F* =     (8)    при условиях            (9).

Для определения оптимальной  стратегии игрока В сводим к нахождению максимального значения функции   F =    (10)  при условиях    (11),    x_j = 0  ( j = )   

 

 

Исходная (прямая) задача: Найти максимальное значение (10) при  условии  (11).

Двойственная: Найти минимальное  значение  (8) при условии (9).

 

Используя решение пары двойственных задач (симплекс-методом), определяем оптимальную  стратегию и цену игры:

 

 

Р⁰ =

 

V =

(i = ; j = )

 

где       и    - оптимальное решение исходной и двойственной задачи.

 

 

Рассмотрим две конкурирующие  финансовые  компании А и В. Компания В ведет переговоры с организаторами каждого из трех проектов В₁, В₂, В₃ на предмет инвестирования. Задача компании В – положительный результат переговоров. Компания А ставит своей задачей свести переговоры компании В к отрицательному результату с тем, чтобы занять место компании В в инвестировании.

Компания А для достижения своей цели – срыва переговоров компании  - может применить одно из двух средств: А₁ – предложить организаторам проектов более выгодные для них условия инвестирования по сравнению с компанией В,  А₂ – предоставить в распоряжение организаторов проектов материалы, компрометирующие компанию В.

Действие А₁ компании А приводит к отрицательному результату переговоров компании В с организаторами проектов В₁, В₂, В₃ соответственно с вероятностями 0, ?, 5/6, а действия игрока А₂ – с вероятностями 1, ѕ, Ѕ.

Компании А и В преследуют противоположные цели, следовательно, игра является антагонистической. Игроками являются финансовые компании А  и В.  Игрок А  имеет 2 чистые  стратегии .

Игрок В ? . Игрок В выбирает один из трех проектов, игрок А выбирает одно из двух своих действий.

Построим платежную матрицу:

 

Bj    Ai	B1	B2	В3
A1	0	1/2	5/6
A2	1	3/4	1/2

 

Проверим, является ли данная задача с нулевой суммой.

 

Bj Ai	B1	B2	B3	ai
A1	0	1/2	5/6	0
A2	1	3/4	1/2	1/2
b j	1	3/4	5/6	0 3/4

 

α_i ? β_j  => что данная задача решается в смешанных стратегиях.

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

 

 Q = x₁ + x₂ + x₃ → max

 

x₂/2 + 5x₂/6 = 1   исходная

x₁ + 3x₂/4 + x₃/2 = 1  задача

x₁, x₂, x₃ = 0

 

 

Р = у₁ + у₂  →min

 

      y₂ = 1   двойственная

y₁/2 + 3y₂/4 = 1   задача

5y₁/6 + y₂/2 = 1

y₁, y₂ = 0

 

 

 

Решаем симплекс-методом и находим оптимальный план   х*  (2/5; 0; 6/5)  и у* = (3/5; 1). Цена игры

V =

P* =

=>                P⁰ =

    Q* =

  =>         Q⁰ =

Для определения стратегии выигрыш  игрока  А  в ситуации  (P⁰ ; В₁), (P⁰ ; В₂), (P⁰ ; В₃) и проигрыш игрока  В в ситуации (А₁, Q⁰), (А₂, Q⁰).

А – принимает смешанную стратегию, игрок В – чистую [B₁ = (1; 0; 0); b₂ = (0; 1; 0); B₃ = (0; 0; 1)].

Н (Р⁰, В₁) =

Н (Р⁰, В₂) =

Н (Р⁰, В₃) =

α (Р⁰) = min  {0, 625; 0,656; 0,625} = 0,625 -   что соответствует

   1=j=3

стратегиям  В₁  и В₃  игрока  В.  Игрок В – принимает смешанную стратегию, игрок А – чистую  [A₁ = (1; 0)      A₂ = (0; 1)].

H (A₁, Q⁰) = 0,625     H (A₂, Q⁰) = 0,625

β (Q⁰) = max {0, 625; 0,625} = 0,625   - что соответствует стратегиям  А₁ и  А₂.

Любая из стратегий  А₁  и А₂ ведет к минимальному проигрышу игрока А и максимальному выигрышу игрока В.