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

1 Моделирование конфликтных ситуаций в экономике Методы решения игровых задач

2 Моделирование конфликтных ситуаций в экономике 1. Принцип доминирования. Цель. Уменьшить размерность задачи (редуцировать платежную матрицу). Принцип доминирования – один из приемов редуцирования платежной матрицы. Идея принципа – выбросить из рассмотрения те стратегии игроков, которые являются очевидно не выгодными для игроков.

3 Моделирование конфликтных ситуаций в экономике Рассмотрим применение принципа на примере. Пусть матрица игры имеет вид: 1. Значения проигрышей игрока В в столбцах В 2 и В 5 совпадают. Это означает, что с точки зрения исхода игры стратегии В 2 и В 5 равноценны и дублируют друг друга. Игроку В не имеет смысла оставлять в своем арсенале обе стратегии. Одну можно исключить. Пусть В. А i \B j B1B1B1B1 B2B2B2B2 B3B3B3B3 B4B4B4B4 B5B5B5B5 А1А1А1А А2А2А2А А3А3А3А Начнем анализ этой матрицы с позиций игрока В.

4 Моделирование конфликтных ситуаций в экономике Пример (Принцип доминирования, продолжение). 2. Столбец В 3 приносит максимальный проигрыш игроку В при любой стратегии игрока А, т.к. а i3 >a ij при всех i и j3. Такой столбец (стратегию) называют строго доминирующим остальные столбцы. Столбец В 3 можно удалить, т.к. разумный игрок этой стратегией никогда не воспользуется. А i \B j B1B1B1B1 B2B2B2B2 B3B3B3B3 B4B4B4B4 А1А1А1А А2А2А2А2-42 А3А3А3А В результате получена матрица игры на один столбец меньше. Вывод. Матрица игры может содержать дублирующие столбцы (строки).

5 Моделирование конфликтных ситуаций в экономике Пример (Принцип доминирования, продолжение). В этом случае говорят, что столбец (стратегия) В 4 не строго доминирует столбец (стратегию) В 1. Столбец (стратегию) В 4 можно исключить из рассмотрения, т.к. эта стратегия приносит не меньший проигрыш, что и стратегия В 1. А i \B j B1B1B1B1 B2B2B2B2 B4B4B4B4 А1А1А1А1-210 А2А2А2А2-4 А3А3А3А Если сравнить столбцы В 1 и В 4, то видно, что а 14 >а 11, a 24 =a 21, a 43 >a 31, т.е. в столбце В 4 содержатся элементы, которые либо строго больше элементов столбца В 1, либо равны соответствующим элементам столбца В 1.

6 Моделирование конфликтных ситуаций в экономике Пример (Принцип доминирования, продолжение). Вывод. Прежде, чем начинать решение игры, следует по возможности уменьшить ее размерность. Одним из приемов понижения размерности является принцип доминирования. А i \B j B1B1B1B1 B2B2B2B2 А1А1А1А1-21 А2А2А2А2-4 А3А3А3А31-5 В результате рассмотрения неэффективности стратегий игрока В, удалось игру размерностью 3×5 уменьшить до размера 2×3. С аналогичных позиций можно рассмотреть эффективности стратегий игрока А, т.е. выявить дублирующие, строго и не строго доминирующие строки (стратегии) игрока А.

7 Моделирование конфликтных ситуаций в экономике 2. Геометрический метод решения игры 2×2. Учитывая минимальную размерность игры, все смешанные стратегии обоих игроков можно разместить на одном отрезке [0,1]. A i \B j B1B1B1B1 B2B2B2B2 A1A1A1A1 a 11 a 12 A2A2A2A2 a 21 a 22 Общий вид матрицы игры 2×2 Решению такой игры можно дать наглядную геометрическую интерпретацию. Метод базируется на том, что множество всех смешанных стратегий игроков можно представить в виде отрезка [0,1].

8 Моделирование конфликтных ситуаций в экономике 2. Геометрический метод решения игры 2×2. Пусть игрок А имеет смешанную стратегию Р={p 1, p 2 }. Обозначим p 2 через p, учитывая, что p 1 +p 2 =1, получим p 1 =1-p, или P={(1-p), p}. При р=0 Р={1,0} – стратегия А 1, при р=1 P={0,1} – стратегия А 2. Если точка 0 соответствует стратегии А 1, а точка 1 стратегии А 2, то устанавливается взаимно однозначное соответствие между точками отрезка [0,1] и множеством смешанных стратегий игрока А. 0 р 1 р 1 =1-рр 2 =р А2А2 А1А1

9 Моделирование конфликтных ситуаций в экономике 2. Геометрический метод решения игры 2×2. Пусть игрок А выбирает свою смешанную стратегию P={1-p, p}, а игрок В чистую стратегию В 1. Тогда выигрыш игрока А есть: H(P,B 1 ) = Σp i a i1 = p 1 a 11 +p 2 a 21 =(1-p)a 11 +pa 21 = = p(a 21 -a 11 )+a 11 (6.1) В системе координат (p,H) зависимость (6.1) представляет собой отрезок прямой, заданный на отрезке [0,1], проходящий через точки (0,а 11 ) и (1, а 21 )

10 Моделирование конфликтных ситуаций в экономике 2. Геометрический метод решения игры 2×2. Пусть для определенность а 11

11 Моделирование конфликтных ситуаций в экономике 2. Геометрический метод решения игры 2×2. 0(А 1 ) а 11 а 21 1(А 2 ) H(P) Зависимость H(P,B 2 )=H(P) есть отрезок между точками (0,a 12 ) и (1,a 22 ). Пусть а 12 >а 22. Вопрос. Как определить опти- мальную смешанную стратегию игрока А? Показатель эффективности смешанной стратегии P={1-p,p} а 12 а 22 есть min{H(P,B 1 ),H(P,B 2 ). Графически это нижняя огибающая отрезков а 11 -а 21 и а 12 -а 22.

12 Моделирование конфликтных ситуаций в экономике 2. Геометрический метод решения игры 2×2. 0(А 1 ) α = а 11 а 21 1(А 2 ) H(P) а 12 а 22 N p V Оптимальной стратегии игрока А соответствует max α(P) или наивысшая точка на огибающей. В данном случае это точка N пересечение отрезков а 11 -а 21 и а 12 - а 22. Абсцисса точки N соответст- вует оптимальной стратегии P 0 ={1- p N,P N } игрока А. Ордината точки N – цена игры V. Показатель эффективности стратегии А 1 - α(A 1 )=min a 11,a 12 =a 11, показатель эффективности стратегии А 2 - α(A 2 )=min (a 22,a 21 )=a 22. Нижняя цена игры – min(α(A1), α(A2))=a 11

13 Моделирование конфликтных ситуаций в экономике 2. Геометрический метод решения игры 2×2. 0(А 1 ) α = а 11 А 21 =β 1(А 2 ) H(P) а 12 а 22 p V Оптимальные стратегии игрока В лежат на верхней огибающей отрезков а 11 -а 21 и а 12 -а 22. Соответственно неэффектив- ности стратегий игрока В и верх- няя цена игры соответственно есть: β(В 1 )=max (a 11,a 21 )=a 21, β(В 2 )=max(a 12,a 22 )=a 12, β=min(β(В1),β(В2))=a 12. N Для нахождения оптимальной смешанной стратегии игрока В необходимо вспомнить, что В=-А Т и провести аналогичные построения.

14 Моделирование конфликтных ситуаций в экономике 2. Геометрический метод решения игры 2×2. а 12 a 22 =β а 11 а 21 =α N p H(P) a 11 =a 21 а 12 a 22 а 11 N p H(P) P 0 ={0,1} а 21 α=βα=β а 11 а 12 а 21 a 22 α=β=a 12 P 0 ={1,0} Положение оптимальной стратегии зависит от соотношений между компонентами платежной матрицы.

15 Моделирование конфликтных ситуаций в экономике 2.1 Решение игры 2×N Игрок А имеет S A ={A 1, A 2 } Игрок В имеет S B ={B 1,B 2,B 3,…,B n } Тогда получим: H(P,B 1 )=(1-p)a 11 +pa 21 =p(a 21 -a 11 )+a 11 H(P,B 2 )=(1-p)a 12 +pa 22 =p(a 22 -a 12 )+a 12 H(P,B n )=(1-p)a 1n +pa 2n =p(a 2n -a 1n )+a 1n Получаем N отрезков в координатах (р,Н), строим огибающую, ищем наивысшею точку на ней.

16 Моделирование конфликтных ситуаций в экономике 3. Аналитическое решение игры 2×2. Рассмотрим случай, когда матрица игры не имеет седловой точки. Тогда решение можно получить исходя из геометрического решения. Имеем: Условие наличия цены игры V есть: H(P,B 1 ) = H(PB 2 ) H(P,B 2 )=Σp i a i2 = p(a 22 -a 12 )+a 12 (7.4) H(P,B 1 ) = Σp i a i1 = p(a 21 -a 11 )+a 11 (7.3)

17 Моделирование конфликтных ситуаций в экономике 3. Аналитическое решение игры 2×2. Приравняв выражения (7.3) и (7.4), получим уравнение, из которого легко вычислить значение р=Р 2 0 : p(a 21 -a 11 )+a 11 p(a 22 -a 12 )+a 12 = p(a 21 -a 11 )+a 11 илир(а 11 +а 22 -а 12 -а 21 )= а 11 -а 12 Откуда следует: р 2 0 = р = а 11 – а 12 (а 22 + а 11 ) – (а 12 + а 21 ) р 1 0 = 1-р = а 22 – а 21 (а 22 + а 11 ) – (а 12 + а 21 )

18 Моделирование конфликтных ситуаций в экономике 3. Аналитическое решение игры 2×2. Соответственно для игрока В получим: H(Q,A 1 )=q 1 a 11 +q 2 a 12 = q(a 12 -a 11 )+a 11 H(Q,A 2 )=q 1 a 21 +q 2 a 22 = q(a 22 -a 21 )+a 21 Откуда следует: q 2 0 = q = a 11 – a 21 (а 22 + а 11 ) – (а 12 + а 21 ) q 1 0 =1- q = a 22 – a 12 V= (а 22 + а 11 ) – (а 12 + а 21 ) a 11 a 22 – a 12 a 21

19 Моделирование конфликтных ситуаций в экономике 3. Аналитическое решение игры 2×2. Вопрос. При каком условии справедливы полученные соотношения? Очевидно, когда знаменатель не равен 0. Равенство нулю выражения (7.5) является необходимым условием наличия седловой точки в матрице игры. (а 22 + а 11 ) – (а 12 + а 21 ) 0 (7.5)

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

21 Моделирование конфликтных ситуаций в экономике 4. Матричные игры и задачи линейного программирования. Теорема. Решение матричной игры m×n c матрицей А, элементы которой a ij >0, эквивалентно решению следующей пары двойственных задач линейного программирования:

22 Моделирование конфликтных ситуаций в экономике 4. Матричные игры и задачи линейного программирования. Поясним теорему, опуская доказательство. Пусть имеем матрицу игры m×n. Оптимальная стратегия P={p 1,p 2,…,p m } обеспечивает ему выигрыш H(P,Q) V. Если игрок В выбирает чистую стратегию В j, то выигрыш игрока А есть: H(P,B j )=Σa ij p i =a 1j p 1 +a 2j p 2 +…+a mj p m V; Σp i = 1 H(P,B j )=Σa ij p i =a 1j p 1 +a 2j p 2 +…+a mj p m V; Σp i = 1 Получим систему из n неравенств.

23 Моделирование конфликтных ситуаций в экономике (7.6) Если V>0, то все неравенства можно разделить на V. Условие V>0 легко достигается путем прибавления к каждому элементу a ij константы r>0. Эта операция приведет к смещению цены игры V на r, но не повлияет на выбор оптимальных стратегий.

24 Моделирование конфликтных ситуаций в экономике В результате получим: (7.7) 4. Матричные игры и задачи линейного программирования.

25 Моделирование конфликтных ситуаций в экономике 4. Матричные игры и задачи линейного программирования. Вводя переменные x 1 =p 1 /v, x 2 =p 2 /v,… и, учитывая, что игрок А стремится получить максимальный выигрыш (V=>max или 1/v=>min), получим задачу линейного программирования для игрока А: (Аналогичные рассуждения приводят к двойственной задачи для игрока В) x 1 +x 2 +x 3 +…+x m =>miny 1 +y 2 +y 3 +…+y n =>max x 1 +x 2 +x 3 +…+x m =>miny 1 +y 2 +y 3 +…+y n =>max a 11 x 1 +a 21 x 2 +…+a m1 x m 1 a 11 y 1 +a 12 y 2 +…+a 1n y n 1 a 12 x 1 +a 22 x 2 +…+a m2 x m 1 a 21 y 1 +a 22 y 2 +…+a 2n y n 1 a 1n x 1 +a 2n x 2 +…+a mn x m 1a m1 y 1 +a m2 y 2 +…+a mn y n 1 Решения этих задач позволяет найти оптимальные смешанные стратегии игроков А и В.

26 Моделирование конфликтных ситуаций в экономике Пример. Пусть исходная матрица игры имеет вид. Задачи линейного программирования для игроков А и В имеют вид: Х 1 +х 2 +х 3 => min y 1 +y 2 +y 3 =>max 1x 1 +5x 2 +8x 3 1 1y 1 +8y 2 +8y 3 1 8x 1 +2x 2 +8x 3 1 5y 1 +2y 2 +5y 3 1 8x 1 +5x 2 +2x 3 1 8y 1 +8y 2 +2y 3 1 А\В В1В1В1В1 В2В2В2В2 В3В3В3В3 αiαiαiαi А1А1А1А11881 А2А2А2А25252 А3А3А3А38822 βjβjβjβj8888\2 А\В В1В1В1В1 В2В2В2В2 В3В3В3В3 αiαiαiαi А1А1А1А А2А2А2А А3А3А3А βjβjβjβj4444\-2 Решение есть: Z=0.2045; V 1 =1/z=4.89; V=V 1 -4=0.89 x 1 =0.045; x 2 =0.106; x 3 =0.053; p 1 =0.222; p 2 =0.519; p 3 =0.259; q 1 =0.444; q 2 =0.037; q 3 =0.519