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

Моделирование конфликтных ситуаций в экономике Рассмотрим две игры в чистых стратегиях A i \B j B1B1B1B1 B2B2B2B2 B3B3B3B3 αiαiαiαi A1A1A1A A2A2A2A A3A3A3A βjβjβjβj4444\-2 B1B1B1B1 B2B2B2B2 B3B3B3B3 αiαiαiαi A1A1A1A A2A2A2A βjβjβjβj \0.4 α < β игра не устойчивая. α = β игра устойчивая α = β Ситуации, в которых α = β, называются седловыми.

Моделирование конфликтных ситуаций в экономике Вопрос. Как построить игру, чтобы выигрыш был больше α, а проигрыш меньше β. Седловых ситуаций (точек) в матрице игры может быть несколько. Например: B1B1B1B1 B2B2B2B2 B3B3B3B3 B4B4B4B4 B5B5B5B5 B6B6B6B6 αiαiαiαi A1A1A1A A2A2A2A A3A3A3A A4A4A4A βjβjβjβj \2 Здесь α=β=2 Оптимальные стратегии игроков: А 1 и А 3 ; В 1,В 3 и В 5

Моделирование конфликтных ситуаций в экономике 1. Игры в смешанных стратегиях. Имеем S A c ={A 1,A 2,…,A m }, S c B ={B 1,B 2,…,B n }, F A (x), F B (y) Определение. Смешанной называется стратегия игрока, состоящая в случайном чередовании одной из своих чистых стратегий. Смешанная стратегия – дискретная случайная величина, значениями которой являются номера чистых стратегий. Т.е. каждой чистой стратегии ставится в соответствие вероятность ее появления в игре.

Моделирование конфликтных ситуаций в экономике 1. Игры в смешанных стратегиях. Имеем:S A c ={A 1,A 2,…,A m }, Р={p 1,p 2,…,p m }, Σp i = 1 S c B ={B 1,B 2,…,B n } Q={q 1,q 2,…,q n }, Σq i = 1 P и Q будем называть смешанными стратегиями игроков А и В. Определение. Множество S A ={P(p 1,p 2,…,p m ), Σp i = 1} называется множеством смешанных стратегий игрока А.

Моделирование конфликтных ситуаций в экономике 1. Игры в смешанных стратегиях. Свойства множества смешанных стратегий: - S A ={P(p 1,p 2,…,p m ), Σp i = 1} – бесконечно, -множество S A ={P(p 1,p 2,…,p m ), Σp i = 1} содержит множество S A c ={A 1,A 2,…,A m } как частный случай: А 1 = {1,0,0,…,0}, A 2 ={0,1,0,…,0}, A 3 ={0,0,1,0,…,0} Для смешанной стратегии справедливо равенство: P = p 1 A 1 +p 2 A 2 +…+p m A m = =p 1 (1,0,…,0)+p 2 (0,1,0…,0)+…+p m (0,0,…,1) = Σp i A i =p 1 (1,0,…,0)+p 2 (0,1,0…,0)+…+p m (0,0,…,1) = Σp i A i

Моделирование конфликтных ситуаций в экономике 1. Игры в смешанных стратегиях. Игра протекает следующим образом: Если игрок А придерживается одной из своих смешанных стратегий, то для определения конкретной чистой стратегии в партии, вначале запускается генератор случайных чисел и в соответствии с полученным числом делается ход. Например. Стратегия игрока А - P = {1/6, 3/6, 2/6}. 1. Бросается «кубик» с гранями {1,2,2,2,3,3}. 2. Если выпал «2», делается ход А 2.

Моделирование конфликтных ситуаций в экономике 2. Геометрическая интерпретация конфигураций смешанной игры. Если в качестве единичных орт взять чистые стратегии А 1,A 2,…,А m, тогда множество всех смешанных стратегий есть симплекс размерностью m-1с вершинами в точках А 1,A 2,…,А m. Примеры. M =2m=3 p2p2 p1p1 A1A1 A2A2 pipi 0.5 A1A1 A3A3 A2A2 pipi

Моделирование конфликтных ситуаций в экономике 3. Функция выигрыша в смешанных стратегиях. Игра в смешанных стратегиях есть расширение игры с множества чистых стратегий на множество смешанных стратегий. Состояние (PQ) в игре называется ситуацией в смешанных стратегиях. Вероятность появления в игре ситуации (A i B j ) равна произведению p i q j. Следовательно, (p i q j ) есть вероятность получения игроком А выигрыша F(A i B j )=a ij. Таким образом, вероятность появления выигрыша a ij есть дискретная случайная величина. Тогда средний выигрыш в игре есть математическое ожидание случайной величины a ij : M(x) = ΣΣp i a ij q j

Моделирование конфликтных ситуаций в экономике 3. Функция выигрыша в смешанных стратегиях Определение. Функция H(P,Q), заданная на множестве смешанных стратегий S A ×S B игроков А и В в ситуации (P,Q) называется функцией выигрыша игрока А, если ее значение равно среднему выигрышу в этой ситуации: H(P,Q) = ΣΣp i a ij q j, PQ є S A ×S B H(P,Q) = ΣΣp i a ij q j, PQ є S A ×S B или матричной форме: H(P,Q) = PAQ T Совокупность {S A,S B,H} множеств смешанных стратегий игроков А и В и функции выигрыша игрока А в смешанных стратегиях называют смешанным расширением игры {S A c,S B c,F A } (2.1) (2.2)

Моделирование конфликтных ситуаций в экономике 3. Функция выигрыша в смешанных стратегиях. Задача. Дана платежная матрица игры 2×3 и две смешанные стратегии игроков P 0 ={3/8,5/8}, Q 0 ={1/4,0,3/4} A i \B j B1B1B1B1 B2B2B2B2 B3B3B3B3 A1A1A1A10½5/6 A2A2A2A21¾½ Определить выигрыш игрока А в ситуациях: P 0 Q 0 ), (P 0 B 1 ), (P 0 B 2 ), (P 0 B 3 ) (P 0 Q 0 ), (P 0 B 1 ), (P 0 B 2 ), (P 0 B 3 )

Моделирование конфликтных ситуаций в экономике Задача. Решение Аналогично можно вычислить выигрыш игроков в различных ситуациях

Моделирование конфликтных ситуаций в экономике 4. Основные определения и теоремы. Теорема 1. Для каждой смешанной стратегии Р игрока А существует α(Р,S B ) = min H(PQ), a для каждой смешанной стратегии Q игрока В существует β(Q,S A ) = max Н(PQ) Определение. Число α(Р,S B ) называется показателем эффективности смешанной стратегии Р игрока А относительно множества смешанных стратегий игрока В. Если заменить S B на S B с, то получим определение показателя эффективности смешанной стратегии Р игрока А относительно множества чистых стратегий игрока В. Если Р есть А i, то α(Р,S B с ) =min H(PQ) = α i

Моделирование конфликтных ситуаций в экономике 4. Основные определения и теоремы. Теорема 2. Показатели эффективности любой смешанной стратегии Р игрока А относительно множеств S B с и S B равны между собой α(Р,S B ) = α(Р,S B с ). Расширение множества чистых стратегий игрока В не изменяет показателя эффективности игрока А.

Моделирование конфликтных ситуаций в экономике 4. Основные определения и теоремы. Определение. Число β(Р,S А ) называется показателем неэффективности смешанной стратегии Q игрока B относительно множества смешанных стратегий игрока A. Если заменить S A на S A с, то получим определение показателя неэффективности смешанной стратегии Q игрока B относительно множества чистых стратегий игрока A. Если Q есть B j, то β(Q,S A с ) =max H(PQ) = β j Справедлива теорема β(Q,S A с ) = β(Q,S A )

Моделирование конфликтных ситуаций в экономике 4. Основные определения и теоремы. Определение. Нижней ценой (максимином) матричной игры в смешанных стратегиях называется величина = max α(P) = max minH(PQ) = max α(P) = max minH(PQ) Верхней ценой (минимаксом) матричной игры в смешанных стратегиях называется величина = min β(Q) = min max H(PQ) = min β(Q) = min max H(PQ) Теорема. Для любой конечной матричной игры существуют нижняя и верхняя границы игры в смешанных стратегиях, т.е. для любой матрицы игры А существует смешанная стратегия Р 0, для которой V=max α(P)= α(P 0 ) и существует Q 0, для которой V=minβ(Q)= β(Q 0 ) Частный случай: Р 0 =А i, Q 0 =B i и равны соответственно максимину и минимаксу игры в чистых стратегиях

Моделирование конфликтных ситуаций в экономике 4. Основные определения и теоремы. Теорема. Нижняя цена игры α и верхняя цена игры β в чистых и нижняя V и верхняя V цены игры в смешанных стратегиях удовлетворяют следующему неравенству: αVVβ. Это означает, что в любой ситуации в смешанных стратегиях (PQ) выигрыш H(PQ) не ниже показателя эффективности α(P) его стратегий

Моделирование конфликтных ситуаций в экономике 5. Решение игры в смешанных стратегиях Определение. Если нижняя V и верхняя V цены игры в смешанных стратегиях равны, то их общее значение V называется ценой игры в смешанных стратегиях, а стратегии P 0 и Q 0, для которых выполняется равенство V = α(P 0 ) =β(Q 0 ) = H(P 0 Q 0 ) V = α(P 0 ) =β(Q 0 ) = H(P 0 Q 0 ) называются оптимальными смешанными стратегиями соответственно игроков А и В. называются оптимальными смешанными стратегиями соответственно игроков А и В. Оптимальные смешанные стратегии игроков обладают тем свойством, что, если один из игроков придерживается своей оптимальной стратегии, то противнику не выгодно отклоняться от своей оптимальной стратегии. Оптимальные смешанные стратегии игроков обладают тем свойством, что, если один из игроков придерживается своей оптимальной стратегии, то противнику не выгодно отклоняться от своей оптимальной стратегии. Цена игры в смешанных стратегиях: αVβ

Моделирование конфликтных ситуаций в экономике 5. Решение игры в смешанных стратегиях. Определение. Полным решением игры в смешанных стратегиях называется совокупность {S A 0, S B 0, V} множеств оптимальных стратегий игроков и цены игры. Определение. Любая пара оптимальных стратегий (P 0,Q 0 ) образуют частное решение игры в смешанных стратегиях. Теорема фон Неймана. Любая матричная игра имеет решение в смешанных стратегиях, т.е. существуют оптимальные стратегии игроков P 0, Q 0 и цена игры V. Точка H(P 0,Q 0 ) называется седловой точкой матрицы игры в смешанных стратегиях.