1 Антюхов В.И.. 2 Тема 4. Модели конечных стратегических игр Лекция : Классификация и основные характеристики моделей конечных стратегических игр Учебные. - презентация

1 1 Антюхов В.И.

2 2 Тема 4. Модели конечных стратегических игр Лекция : Классификация и основные характеристики моделей конечных стратегических игр Учебные вопросы: 1.Матричные игры 2.Технология формирования математической модели чрезвычайной конфликтной ситуации и определение цены игры 3.Принцип минимакса в теории матричных игр

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

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

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

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

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

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

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

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

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

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

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

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

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

16 16 Классификация игр Парные неантагонистические игры представлены моделью биматричной игры, являющейся стратегической одноходовой конечной Кроме того, к парным неантагонистическим играм относятся игры «человек – природа», имеющие важное значение именно при ликвидации чрезвычайных ситуаций силами и средствами МЧС

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

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

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

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

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

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

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

24 24 Дерево игры, в которой ни одна сторона не знает выбора другой стороны Динамическая игра может быть представлена в виде дерева игры А В В ВВ АА А АААА А а 1 а 4 а 3 а 2 b 1 b 2 b 1 a 1a 2a 3 3-й шаг 2-й шаг

25 25 Динамические (многоходовые) игры На рисунке символы и обозначают, какая именно сторона делает выбор на данном ходе Отрезки с символами а i, а i, b j – конкурирующие на данном ходе варианты действий Такую форму формального описания динамической игры называют развернутой Всякая динамическая игра с конечным числом ходов может быть сведена к статической (одноходовой) Поэтому методы решения матричных задач разработаны для одноходовых игр или динамических игр, сведенных к одноходовым АВ

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

27 27 Динамические (многоходовые) игры Так, на представленном выше рисунке стратегиями стороны А будет выбор на первом и третьем ходах соответственно вариантов: А 1 – а 1 и a 1, А 2 – а 1 и a 2, А 3 – а 1 и a 3, А 4 – а 2 и a 1 и т.д. до А 12 – а 4 и a 3. Стратегиями стороны В будут В 1 – b 1 и В 2 – b 2. Следовательно, динамическая игра сведена к статической При этом для стороны В, имеющей один ход, понятия «стратегия» и «вариант действий» совпадают. Кроме того, ни одна из сторон не знает выбора другой стороны

28 28 Динамические (многоходовые) игры В случае, если одна из сторон имеет информацию о выборе стратегий другой стороной, то стратегии первой будут изменяться Пусть стороне В известен выбор стратегии стороной А, т.е. сторона В знает какая пара вариантов действий стороны А имеет место: а 1, а 2 или а 3, а 4 Если предположить, что в условиях такой осведомленности сторона В по-прежнему делает выбор между вариантами действий b 1 и b 2, то число стратегий стороны В, подлежащих рассмотрению, изменится – их будет не две, а четыре:

29 29 Динамические (многоходовые) игры Стратегия В 1 – использовать вариант действий b 1 при любой паре вариантов действий стороны А (а 1, а 2 или а 3, а 4 ) Стратегия В 2 – использовать вариант действий b 1, если известно, что сторона А использует один из вариантов действий пары а 1, а 2, или использовать вариант действий b 2, если известно, что сторона А использует один из вариантов действий пары а 3, а 4 Стратегия В 3 – использовать вариант действий b 2 при любой паре вариантов действий стороны А (а 1, а 2 или а 3, а 4 ) Стратегия В 4 – использовать вариант действий b 2, если известно, что сторона А использует один из вариантов пары а 1, а 2, или использовать вариант b 1, если известно, что сторона А использует один из вариантов пары а 3, а 4

30 30 Рисунок игры в которой стороне В известен выбор стороны А Дерево игры в этом случае примет вид: А В В ВВ АА А АААА А а 1 а 4 а 3 а 2 b 1 b 2 b 1 a 1a 2a 3 3-й шаг 2-й шаг a 1a 2 a 3 1-й шаг b1b1 b2b2 b1b1 b2b2 b1b1 b2b2 b1b1 b2b2 a 1 a 2 a 3 a 4

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

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

33 33 Платёжная матрица A i ВjВj В1В1 В2В2 …ВnВn А1А1 u 11 u 12 …u1nu1n А2А2 u 21 u 22 …u2nu2n …...……… АmАm um1um1 um2um2 …u mn

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

35 35 Платёжная матрица Пусть существуют оптимальные смешанные стратегии: - для стороны А – стратегия 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 называют активными, а если эти вероятности равны нулю – неактивными

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

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

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

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

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

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

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

43 43 Учебный вопрос 2. Технология формирования математической модели чрезвычайной конфликтной ситуации и определение цены игры Для оптимальной смешанной стратегии матричной игры выражение для вычисления цены игры имеет вид:

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

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

46 46 Учебный вопрос 3. Принцип минимакса в теории матричных игр

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

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

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

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

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

52 52 Учебный вопрос 3. Принцип минимакса в теории матричных игр 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

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

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

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

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

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

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

59 59 Учебный вопрос 3. Принцип минимакса в теории матричных игр 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

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

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

62 62 Учебный вопрос 3. Принцип минимакса в теории матричных игр 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

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

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

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