1 2 Классификация и основные характеристики моделей конечных стратегических игр Содержание: 1.Игры с нулевой суммой (матричные игры) 2.Метод формирования. - презентация

1 1

2 2 Классификация и основные характеристики моделей конечных стратегических игр Содержание: 1.Игры с нулевой суммой (матричные игры) 2.Метод формирования математической модели конфликтной ситуации и определение цены игры 3.Принцип минимакса в теории матричных игр

3 Введение Первая значительная книга по теории игр появилась в 1944г (Дж. фон Нейман, С. Моргенштерн «Теория игр и экономическое поведение»). В 1994 г. за успехи в развитии теории игр трем ученым J.F. Nash, J.C. Harsanyi и R. Selten была присуждена Нобелевская премия по экономике. Теория игр она нашла свое применение, прежде всего, в военном деле, политике, юриспруденции, психологии, биологии и экономике.

4 4

5 Моделями теории игр можно описать экономические, правовые, классовые, военные конфликты, взаимодействие человека с природой. Все такие модели в теории игр принято называть играми.

6 6

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

8 8 Вопрос 1. Матричные игры В условиях неопределенности развития чрезвычайной ситуации проблема выбора наилучшего варианта действий (принятия решений) как правило, включает ряд подпроблем: - оценку возможных вариантов развития чрезвычайной ситуации; - определение рациональных вариантов использования личного состава и имеемых средств для ликвидации чрезвычайной ситуации; - выбор лучшего (оптимального) варианта использования личного состава и имеемых средств для ликвидации чрезвычайной ситуации с минимумом потерь

9 9 Вопрос 1. Матричные игры Следовательно, сотруднику МЧС при управлении ликвидацией чрезвычайной ситуации приходится действовать в условиях конфликта и принимать решения в конфликтной ситуации на основе так называемой теории игр Теория игр – это теория математического моделирования конфликтных ситуаций (прокурор – адвокат, преступник – сотрудник МВД, пожар – сотрудник ГПС МЧС и др.)

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

11 11 Классификация игр по числу вариантов действий конфликтующих сторон Кооперативные игры, когда действуют не менее двух сторон, каждая из которых выступает со своими наборами вариантов действий (стратегий) Некооперативные игры, когда действует всего одна либо существует коалиция сторон, все участники которой выступают с одним набором вариантов действий

12 12 Классификация игр по числу участвующих в конфликтной ситуации сторон Парные игры (участвуют две стороны: - человек – человек; - человек – природа); Множественные игры (участвуют более двух сторон)

13 13 Классификация игр по целям действий, которые преследуют стороны Антагонистические игры (игры с нулевой суммой), когда цели действий сторон прямо противоположны (выигрыш одной стороны – есть проигрыш другой) Неантагонистические игры (игры с ненулевой суммой), когда стороны преследуют различные, но не противоположные цели (выигрыш одной стороны не является в точности проигрышем другой)

14 14 Классификация игр по числу возможных вариантов действий в стратегической игре Конечные игры, когда все участвующие стороны имеют конечное число возможных вариантов действий (шахматы, шашки) Бесконечные игры, когда хотя бы одна из сторон имеет бесконечно большое число вариантов действий (теннис, футбол)

15 15 Классификация игр по количеству ходов (шагов) для выбора стороной одного из предусмотренных вариантов действий в стратегически конечных и бесконечных играх Одноходовые игры (одношаговые, статические), когда каждая из сторон имеет по одному ходу; Многоходовые игры (многошаговые, динамические), когда каждая из сторон имеет множество ходов, т.е. реализует динамический процесс принятия решений в процессе конфликтной ситуации

16 16 Классификация игр по временным особенностям конфликтных ситуаций в многоходовых (динамических) играх Дискретные игры, в которых стороны принимают решения в некоторые дискретные, отстоящие друг от друга моменты времени (ликвидация последствий землетрясения) Непрерывные игры, в которых управление разрешением конфликтной ситуации требует непрерывного выбора вариантов действий (ликвидация пожара на взрывоопасном объекте)

17 17 Классификация игр по вероятности окончания многоходовой (динамической) дискретной или непрерывной игры Стохастические игры, когда на каждом ходе с некоторой вероятностью игра может закончиться Рекурсивные игры, когда вероятность прекращения игры может быть равна нулю Дифференциальные игры, это те же рекурсивные игры, но с бесконечным числом состояний и непрерывным временем

18 18 Классификация игр по сущности сторон, принимающих участие в конфликтных ситуациях, моделируемых парными антагонистическими играми Игра «человек – человек» («группа людей – группа людей») Игра «человек – природа» («группа людей – природа»)

19 19 Классификация игр по числу ходов в парных антагонистических конечных играх Матричные игры, которые являются одноходовыми (статическими) Квазиматричные игры, которые являются многоходовыми (динамическими)

20 20 Вопрос 1: Матричные игры Наибольший интерес для принятия решений в конфликтных ситуациях представляют матричные игры, так как: 1) на примере матричных игр наиболее удобно рассмотреть многие понятия и определения теории игр; 2) матричные игры являются составным элементом многих других классов игр; 3) матричные игры имеют хорошо апробированный аппарат и находят широкое применение при моделировании конфликтных ситуаций

21 Орлянка Простейшим примером матричной антагонистической игры является игра "Орлянка". Первый игрок прячет монету орлом или решкой вверх, а второй пытается угадать, как она спрятана. Если он не угадывает - он платит первому одну денежную единицу, если угадывает - первый платит ему одну денежную единицу. В данной игре каждый участник имеет две стратегии: "орел" и "решка". Множество ситуаций в игре состоит из четырех элементов. В строках таблицы указаны стратегии первого игрока х, в столбцах - стратегии второго игрока y. Для каждой из ситуаций указаны выигрыши первого и второго игроков. X\YОрелРешка Орел-1;11, -1 Решка1, -1-1, 1

22 Орлянка В аналитическом виде функция выигрыша первого игрока имеет следующую форму: где x X и y Y - стратегии первого и второго игроков, соответственно. Так как выигрыш первого игрока равен проигрышу второго, то F 2 (x,y) = F 1 (x,y).

23 23 Постановка задачи матричной игры 1) пусть имеются две стороны А и В; 2) сторона А имеет m вариантов действий, а сторона В – n вариантов; 3) «выигрыш» стороны А при выборе ею варианта действий А i, а стороной В – варианта В j, составляет а ij, ; 4) «проигрыш» стороны В в этом случае составляет также а ij ; 5) сторона А выигрывающая, а В – проигрывающая; 6) стороне А точно известен все варианты возможных действий стороны В и выигрыши а ij для каждой из пар вариантов действий (А i, В j );

24 24 Постановка задачи матричной игры 7) аналогично стороне В точно известен весь возможный набор вариантов действий стороны А и свои проигрыши а ij ; 8) сторона А и сторона В измеряют «выигрыши» и «проигрыши» одной мерой; 9) неизвестно каждой из сторон какой именно вариант из числа известных выберет другая сторона, но известен принцип, по которому обе стороны выбирают оптимальный для себя план действий

25 25 Ключевые термины матричных игр 1. Стратегия стороны – совокупность правил, определяющих выбор этой стороной варианта действий при каждом личном ходе (сознательном выборе стороной одного из возможных вариантов действий) в зависимости от сложившейся конфликтной ситуации

26 26 Ключевые термины матричных игр 2. Правила игры – система условий, регламентирующих: - возможные варианты действий (ходов) обеих сторон, участвующих в парной игре; - исход (результат) игры, к которому приводит каждая конкретная совокупность ходов обеих сторон; - объем информации у каждой стороны о ходах другой 3. Случайный ход – выбор стороной одного из возможных вариантов действий с помощью механизма случайного выбора (бросание монеты, выбор карты из перетасованной колоды)

27 27 Ключевые термины матричных игр 4. Игра с нулевой суммой – одна сторона выигрывает ровно столько, сколько проигрывает другая, т.е. сумма выигрышей сторон ровна нулю 5. Чистая стратегия – совокупность правил, определяющих выбор вариантов действий (последовательности ходов) при каждом личном ходе в зависимости от конфликтной ситуации, сложившейся в процессе игры 6. Оптимальная стратегия – стратегия, которая при многократном повторении игры обеспечивает максимально возможный средний выигрыш (минимально возможный средний проигрыш)

28 28 Ключевые термины матричных игр 7. Цена игры средний выигрыш стороны А (средний проигрыш стороны В) при применении конфликтующими сторонами своих оптимальных стратегий 8. Смешанная стратегия – стратегия, состоящая в случайном чередовании чистых стратегий, с определенным соотношением частот

29 29 Платёжная матрица Исчерпывающую информацию о парной матричной игре дает матрица, называемая платежной матрицей Элементами этой матрицы является выигрыш стороны А (проигрыш стороны В) при соответствующей паре стратегий конфликтующих сторон

30 30 Платёжная матрица A i ВjВj В1В1 В2В2 …ВnВn А1А1 а 11 а 12 …а1nа1n А2А2 а 21 а 22 …а2nа2n …...……… АmАm аm1аm1 аm2аm2 …а mn

31 31 Платёжная матрица Элемент платёжной матрицы а ij есть выигрыш стороны А (проигрыш стороны В), если сторона А избрала стратегию A i, i = 1, 2,…, m, а сторона В – стратегию В j, j = 1,2,…,n Для вычисления значений а ij необходимо использовать либо статистические данные, либо специальные математические модели конфликтных ситуаций, разработанные с помощью различных методов исследования операций В результате решения матричной игры определяются оптимальные стратегии (в общем случае оптимальными являются смешанные стратегии) сторон и цена игры

32 32 Платёжная матрица Пусть существуют оптимальные смешанные стратегии: - для стороны А – стратегия S A = (p 1, p 2, …, p i, …, p m ); - для стороны В – стратегия S B = (q 1, q 2, …, q j, …, q n ), где p j и q j – вероятности (частоты) применения сторонами А и В своих стратегий A i и В j соответственно Если вероятности p i и q j отличаются от нуля, то соответствующие им стратегии A i и В j называют активными, а если эти вероятности равны нулю – неактивными

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

34 34 Платёжная матрица Применение же случайного выбора (путем жеребьевки) при большом числе повторений партий игры обеспечивает: 1) оптимальную частость применения полезных стратегий: 2) маскировку от противоборствующей стороны выбора стратегии в очередной партии

35 35 Вопрос 2. Метод формирования математической модели конфликтной ситуации и определение цены игры Формирование математической модели конфликтной ситуации должно осуществляться в два этапа: Этап 1. Описание конфликтной ситуации Этап 2. Интерпретация ситуации как того или иного класса конфликтных ситуаций (в терминах теории игр)

36 36 Вопрос 2. Метод формирования математической модели конфликтной ситуации и определение цены игры На этапе 1(описание конфликтной ситуации) проводятся следующие работы: 1) определяются цели использования сил и средств для разрешения ситуации; 2) проводится концептуальная формулировка оптимизационной задачи использования сил и средств; 3) выделяются элементы ситуации, от которых зависит выбор группы методов оптимизации в условиях неопределенности (игра «человек – человек» или игра «человек – природа»); 4) осуществляется формализованная постановка задачи

37 37 Вопрос 2. Метод формирования математической модели конфликтной ситуации и определение цены игры На этапе 2 (описание конфликтной ситуации) проводятся следующие работы: 1) выявляются конфликтующие стороны; 2) определяются цели конфликтующих сторон; 3) определяется полный набор стратегий сторон, их особенности для того, чтобы ответить на вопросы: - является ли данная ситуация одной из разновидностей конечных игр; - имеются ли помимо личных случайные ходы; - является ли матричная игра одноходовой или многоходовой (в последнем случае - как её можно свести к одноходовой); 4) выявляется, не присутствуют ли в изучаемой конфликтной ситуации элементы случайности. Если они есть, то определяется возможность применения для моделирования аппарата стохастических, рекурсивных, дифференциальных игр; 5) определяются способы вычисления выигрышей а ij сторон для всех возможных пар стратегий

38 38 Вопрос 2. Метод формирования математической модели конфликтной ситуации и определение цены игры На втором этапе формирования математической модели конфликтной ситуации, кроме того: - в случае конечных игр вычисляются значения а ij для всех возможных пар стратегий сторон; - в случае антагонистических игр за а ij принимают выигрыши условно принятой выигрывающей стороны, которые одновременно являются характеристиками проигрыша условно принятой проигрывающей стороны Для вычисления а ij используют математические модели

39 39 Вопрос 2. Метод формирования математической модели конфликтной ситуации и определение цены игры С помощью аппарата теории игр на втором этапе формирования математической модели конфликтной ситуации вычисляют: - среднее значение выигрыша выигрывающей стороны; - среднее значение проигрыша проигрывающей стороны Это среднее значение (математическое ожидание) и является ценой игры

40 40 Вопрос 2. Метод формирования математической модели конфликтной ситуации и определение цены игры Для оптимальной смешанной стратегии матричной игры выражение для вычисления цены игры имеет вид:

41 41 Вопрос 2. Метод формирования математической модели конфликтной ситуации и определение цены игры Достижение цены игры гарантировано сторонам конфликтной ситуации, если стороны придерживаются оптимальных смешанных стратегий и правил выбора активных стратегий в очередной партии игры Если же какая-либо из сторон ведет себя неоптимальным образом, её выигрыш может уменьшиться (проигрыш увеличиться) в пользу другой стороны

42 42 Вопрос 2. Метод формирования математической модели конфликтной ситуации и определение цены игры Для нахождения оптимальных стратегий сторон и цены игры в теории игр используют принцип минимакса Этот принцип лежит в основе методов решения матричных игр

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

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

45 3. Принцип доминирования Пример (Принцип доминирования, продолжение). 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А В результате получена матрица игры на один столбец меньше. Вывод. Матрица игры может содержать дублирующие столбцы (строки).

46 3. Принцип доминирования Пример (Принцип доминирования, продолжение). В этом случае говорят, что столбец (стратегия) В 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.

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

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

49 4. Геометрический метод решения игры 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

50 4. Геометрический метод решения игры 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 (1) В системе координат (p,H) зависимость (1) представляет собой отрезок прямой, заданный на отрезке [0,1], проходящий через точки (0,а 11 ) и (1, а 21 )

51 4. Геометрический метод решения игры 2×2 Пусть для определенность а 11

52 4. Геометрический метод решения игры 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.

53 4. Геометрический метод решения игры 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

54 4. Геометрический метод решения игры 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 Для нахождения оптимальной смешанной стратегии игрока В необходимо вспомнить, что В=-А Т и провести аналогичные построения.

55 4. Геометрический метод решения игры 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} Положение оптимальной стратегии зависит от соотношений между компонентами платежной матрицы.

56 4. Геометрический метод решения игры 2×2 Решение игры 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 отрезков в координатах (р,Н), строим огибающую, ищем наивысшею точку на ней.

57 5. Аналитическое решение игры 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 (5.2) H(P,B 1 ) = Σp i a i1 = p(a 21 -a 11 )+a 11 (5.1)

58 5. Аналитическое решение игры 2×2. Приравняв выражения (5.1) и (5.2), получим уравнение, из которого легко вычислить значение р=Р 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 )

59 5. Аналитическое решение игры 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

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

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

62 62 6. Принцип минимакса в теории матричных игр Пусть, например, сторона В имеет три возможных стратегии (В 1, В 2, В 3 ), а противоборствующая ей сторона А – четыре (А 1, А 2, А 3, А 4 ) При этом ни одна из сторон не знает о выборе конкретной стратегии противоборствующей стороной Значения а ij выполнения стороной А поставленной задачи для различных пар A i B j стратегий сторон вычисляются и сведятся в матрицу игры

63 63 6. Принцип минимакса в теории матричных игр Оценивая каждую свою стратегию A i, сторона А определяет для нее минимально возможный выигрыш α i, для чего просматриваются выигрыши А ij при всех стратегиях стороны: B j, j =, т.е. α i = а ij

64 64 6. Принцип минимакса в теории матричных игр Сторона А – выигрывающая, она стремится максимизировать свой выигрыш, поэтому она просматривает все выигрыши αi, i =, и выбирает максимальный из них, т.е.: Величину α называют нижней ценой игры или максимином

65 65 6. Принцип минимакса в теории матричных игр Стратегию стороны А, при которой достигается максиминный выигрыш, называют максиминной стратегией Пусть имеется следующая платёжная матрица (см. следующий слайд)

66 66 6. Принцип минимакса в теории матричных игр A i BjBj B1B1 B2B2 B3B3 αiαi A1A1 0,700,400,25 A2A2 0,400,550,500,40 A3 A3 0,300,600,750,30 A4A4 0,700,350,400,35 ßjßj 0,700,600,75

67 67 6. Принцип минимакса в теории матричных игр В рассматриваемом примере α = 40, а максиминной стратегией является А 2 Сторона В, выбирая стратегию, поступает аналогично Так как сторона В – проигрывающая, то, исходя из принципа минимакса, она считает необходимым при оценке каждой своей стратегии учитывать возможность такого ответного хода противоборствующей стороны, при котором ее проигрыш будет максимальным

68 68 6. Принцип минимакса в теории матричных игр Поэтому для каждой своей стратегии B j она ищет максимальный проигрыш, просматривая все стратегии A i противоборствующей стороны, т.е.: Затем сторона В определяет минимальный из всех максимальных проигрышей, т.е.:

69 69 6. Принцип минимакса в теории матричных игр Значение β называют верхней ценой игры, а соответствующую ей стратегию В – минимаксной стратегией В рассматриваемом примере ß = 0.60, а минимаксной является стратегия В 2 Следует подчеркнуть, что в рассматриваемом случае всегда ß α

70 70 6. Принцип минимакса в теории матричных игр Рассмотрение максиминной и минимаксной стратегий показывает следующее: 1) применение максиминной стратегии гарантирует стороне А выигрыш не менее, чем α, какие бы стратегии ни принимала сторона В; 2) применение минимаксной стратегии гарантирует стороне В, что ее проигрыш не более, чем ß при любых стратегиях стороны А

71 71 6. Принцип минимакса в теории матричных игр Стремление сторон повысить свой выигрыш и снизить проигрыш делает максиминную и минимаксную стратегии неустойчивыми при наличии у соответствующих сторон информации о поведении противоборствующей стороны

72 72 6. Принцип минимакса в теории матричных игр Например, если стороне А стало известно, что сторона В применяет стратегию В 2, то стороне А будет целесообразно вместо стратегии А 2 применить стратегию А 3, (см.таблицу, представленную ранее) При этом её выигрыш повысится с 0.55 до 0.60

73 73 6. Принцип минимакса в теории матричных игр A i BjBj B1B1 B2B2 B3B3 αiαi A1A1 0,700,400,25 A2A2 0,400,550,500,40 A3 A3 0,300,600,750,30 A4A4 0,700,350,400,35 ßjßj 0,700,600,75

74 74 6. Принцип минимакса в теории матричных игр Если же факт применения стороной А стратегии А 3 станет известен стороне В, то ей будет выгодно вместо стратегии В 2 применить стратегию В 1 Это понизит её проигрыш с 0.60 до 0.30

75 75 6. Принцип минимакса в теории матричных игр Существуют также конфликтные ситуации, в которых даже полное знание обеими сторонами поведения друг друга не дает им возможность сменить максиминную (минимаксную) стратегию на другую, т.к. это приведет к снижению эффективности поведения (снижению выигрыша, повышению проигрыша) Пусть имеет место матрица игры, представленная на следующем слайде

76 76 6. Принцип минимакса в теории матричных игр A i BjBj B1B1 B2B2 B3B3 αiαi A1A1 0,700,400,25 A2A2 0,400,550,500,40 A3 A3 0,650,600,750,60 A4A4 0,700,350,400,35 ßjßj 0,700,600,75

77 77 6. Принцип минимакса в теории матричных игр Используя принцип минимакса, можно определить нижнюю и верхнюю цены игры: α = 0,60 и ß = 0,60, т.е α = ß Эта величина является минимальной в строке А 3 и максимальной в столбце В 2 Этот элемент платежной матрицы называют седловой точкой Он и является ценой игры ν, т.к. при наличии седловой точки любая из сторон, отказавшаяся от стратегии на основе принципа минимакса, обязательно потеряет в эффективности, если другая сторона придерживается этой же стратегии

78 78 6. Принцип минимакса в теории матричных игр Такая ситуация называется ситуацией равновесия, т.к. даже наличие у сторон информации о поведении другой стороны не дает им возможности повысить свою эффективность за счёт изменения стратегии

79 79 6. Принцип минимакса в теории матричных игр Таким образом, максиминная и минимаксная стратегия при α = ß являются оптимальными стратегиями При этом решение игры осуществляется в чистых стратегиях Доказано также, что игры с полной информацией всегда имеют седловую точку, обладающую устойчивостью, и, значит, обладают решением в чистых стратегиях

80 Пусть – платежная матрица игры Г. Если она не имеет седловой точки, то единственное решение игры Г можно найти 7. Принцип линейного программирования в теории матричных игр

81 1) решив две системы:

82 2) по формулам: или

83 3) в матричном виде: где – определитель матрицы А, А* – присоединенная к А матрица,,,, J T и y T – транспонированные матрицы J и y.

84 Найдем, например, решение игры с платежной матрицей, которая не имеет седловой точки.

85 1) Составим системы: Решив системы, получим: то есть -решение игры.

86 2) Найдем решение по формулам:

87 3) Найдем решение в матричном виде:

88 Рассмотрим игру с платежной матрицей

89 Если 1-й игрок применит смешанную стратегию, а 2-й игрок – чистую стратегию, то.(1)

90 Аналогично при выборе 2-м игроком чистых стратегий,, (2) (3) (4)

91 1 A Рис.1 (1) x 0 x (3) (2) (4)

92 Точка A является точкой пересечения прямых (2) и (3), поэтому решение исходной игры можно найти, решив игру

93 По формулам решения – игры получим:

94 Тогда решение исходной игры имеет вид (номерам столбцов, не вошедших в матрицу, соответствуют нулевые координаты вектора ),.

95 Аналогично решаются - игры. Пусть, например,, – смешанная стратегия 2-го игрока, 1-й игрок выбирает чистые стратегии i=1,2,3.

96 (1) (2) (3)

97 (1) y 0 y (3) (2) 1 B Рис.2

98 Точка B является точкой пересечения прямых (2) и (3). Найдем решение игры

99 Тогда решение исходной игры:

100 Пусть платежная матрица игры (3) x 0 x2x2 (2) (1) Рис.3 1 BA x1x1

101 A – точка пересечения прямых (2) и (3), ее абсциссу найдем, решая игру

102 B – точка пересечения прямых (1) и (2), ее абсциссу найдем, решая игру

103 Решение исходной игры:, где,, то есть 1-й игрок имеет множество оптимальных стратегий, 2-й игрок – единственную оптимальную стратегию, это чистая стратегия j=2.