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

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

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

3 Оптимальные решения при недостатке информации В условиях конфликта стремление противника скрыть свои предстоящие действия порождает неопределённость. Наоборот, неопределённость при принятии решений можно интерпретировать как конфликт принимающего решения субъекта с природой. Поэтому теория игр рассматривается и как теория принятия оптимальных решений в условиях неопределённости. Она позволяет математизировать некоторые важные аспекты принятия решений в технике, сельском хозяйстве, медицине и социологии, управлении, планировании и прогнозировании. 3

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

5 Игра – формализованное представление о конфликте Точное описание конфликта в виде игры состоит поэтому в указании того, 1.кто и как участвует в конфликте, 2.каковы возможные исходы конфликта, 3.а также кто и в какой форме заинтересован в этих исходах. 5

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

7 Характеризующие признаки игры как математической модели ситуации: 1.наличие нескольких участников; 2.неопределенность поведения участников, связанная с наличием у каждого из них нескольких вариантов действий; 3.различие (несовпадение) интересов участников; 4.взаимосвязанность поведения участников, поскольку результат, получаемый каждым из них, зависит от поведения всех участников; 5.наличие правил поведения, известных всем участникам. 7

8 Представление игр Игры представляют собой строго определённые математические объекты. Игра образуется игроками, набором стратегий для каждого игрока и указания выигрышей, или платежей, игроков для каждой комбинации стратегий. Большинство игр описываются характеристической функцией, в то время как для остальных видов чаще используют нормальную или экстенсивную форму. 8

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

10 Задача: Два игрока играют в следующую игру: на координатной плоскости стоит фишка в точке с координатами (-2,1). Игроки ходят по очереди. Ход состоит в том, что игрок перемещает фишку из точки с координатами (х,у) в одну из трех точек: (х+3,у), (х,у+4), (х+2,у+2). Игра заканчивается, как только расстояние от фишки до начала координат превысит число 9. Выигрывает игрок, сделавший последний ход. Кто выиграет при правильной игре? Каким должен быть первый ход выигрывающего игрока? 10

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

12 Игра «Дилемма заключенного»: Двое преступников, А и Б, попались примерно в одно и то же время на сходных преступлениях. Есть основания полагать, что они действовали по сговору, и полиция, изолировав их друг от друга, предлагает им одну и ту же сделку: если один свидетельствует против другого, а тот хранит молчание, то первый освобождается за помощь следствию, а второй получает максимальный срок лишения свободы (10 лет). Если оба молчат, их деяние проходит по более лёгкой статье, и они приговариваются к 6 месяцам. Если оба свидетельствуют против друг друга, они получают минимальный срок (по 2 года). Каждый заключённый выбирает, молчать или свидетельствовать против другого. Однако ни один из них не знает точно, что сделает другой. 12

13 Представив игру в виде матрицы, получим: Рассмотрим ситуацию заключенного А. Если В молчит, лучше его сдать и выйти на свободу. Если он говорит, снова лучше все рассказать, и получить всего два года. Т.о., если каждый игрок выбирает, что лучше для него, оба сдадут друг друга, и получат два года, что не является оптимальной ситуацией для обоих. Преступник Б Стратегия «молчать»Стратегия «говорить» Преступник А Стратегия «молчать» Полгода каждому 10 Лет преступнику А Отпустить преступника Б Стратегия «говорить» 10 Лет преступнику Б Отпустить преступника А 2 года каждому 13

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

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

16 Пример: «Зачет» Задача состоит в определении оптимальных стратегий для студента и для преподавателя. Пусть игрок 1 – студент, готовящийся к зачету, а игрок 2 – преподаватель, принимающий зачет. Будем считать, что у студента две стратегии: А 1 – хорошо подготовиться к зачету; А 2 – не готовиться. У преподавателя имеется тоже две стратегии: В 1 – поставить зачет; В 2 – не поставить зачет. В основу оценки значений выигрышей игроков можно положить, например, следующие соображения, отраженные в матрицах выигрышей. В 1 В 2 В 1 В 2 А 1 + (5) (оценили по заслугам) - (-6) (обидно) А 1 + (0) (все нормально) - (-3) (проявил несправедли вость) А 2 (1) (удалось словчить) (0) (получил по заслугам) А 2 -2 (дал себя обмануть) - 1 (студент придет еще раз) Выигрыши студента Выигрыши преподавателя 16

17 Матрица выигрышей для игры «Зачет» В1В2В1В2 А1 5-5 А1 0-3 Оценили по заслугам Обидно Нормальная ситуация Поступил несправед- ливо А Удалось словчить Оценили по заслугам Дал себя обмануть Студент придет еще раз Выигрыши студентаВыигрыши преподавателя 17

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

19 Нестратегические игры Множеством ситуаций являются всевозможные дележи между игроками некоторого количества однородной полезности. Каждый делёж описывается теми суммами, которые получают отдельные игроки. Коалиция интересов называется выигрывающей, если она может даже в условиях противодействия со стороны всех остальных игроков присвоить и разделить между своими членами всю имеющуюся полезность. Все коалиции, не являющиеся выигрывающими, совсем не могут присвоить какой- либо доли полезности. 19

20 Кооперативная/ некооперативная игра Игра называется кооперативной, или коалиционной, если игроки могут объединяться в группы, беря на себя некоторые обязательства перед другими игроками и координируя свои действия. Этим она отличается от некооперативных игр, в которых каждый обязан играть за себя, не имея возможности формировать коалиции и координировать свои действия. 20

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

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

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

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

25 Цель теории игр - выработка рекомендаций по разумному поведению участников конфликта (определение оптимальных стратегий поведения игроков). 25

26 Правила игры От реального конфликта игра отличается тем, что ведется по определенным правилам. Эти правила устанавливают последовательность ходов, объем информации каждой стороны о поведении другой и результат игры в зависимости от сложившейся ситуации. Правилами устанавливаются также конец игры, когда некоторая последовательность ходов уже сделана, и больше ходов делать не разрешается. 26

27 Ограничения теории игр Теория игр, как и всякая математическая модель, имеет свои ограничения. Одним из них является предположение о полной (идеальной) разумности противников. В реальном конфликте зачастую оптимальная стратегия состоит в том, чтобы угадать, в чем противник «глуп» и воспользоваться этой глупостью в свою пользу. 27

28 Ограничения теории игр Еще одним ограничением теории игр является то, что каждому из игроков должны быть известны все возможные действия (стратегии) противника, неизвестно лишь то, каким именно из них он воспользуется в данной партии. В реальном конфликте это обычно не так: перечень всех возможных стратегий противника как раз и неизвестен, а наилучшим решением в конфликтной ситуации нередко будет именно выход за пределы известных противнику стратегий, использование чего-то совершенно нового, непредвиденного. 28

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

30 Принцип оптимальности – устойчивость ситуаций Рассматриваемые в теории игр объекты игры весьма разнообразны, и пока не удалось установить принципов оптимальности, общих для всех классов игр. Практически это означает, что единого для всех игр истолкования понятия оптимальности ещё не выработано. Поэтому прежде чем говорить, например, о наивыгоднейшем поведении игрока в игре, необходимо установить, в каком смысле эта выгодность понимается. Все применяемые в теории игр принципы оптимальности при всём их внешнем разнообразии отражают прямо или косвенно идею устойчивости ситуаций или множеств ситуаций, составляющих решения. 30

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

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

33 Способы нахождения принципов оптимальности Фактическое решение некоторых классов антагонистических игр сводится к решению дифференциальных и интегральных уравнений, а матричных игр к решению стандартной задачи линейного программирования. Разрабатываются приближённые и численные методы решения игр. Для многих игр оптимальными оказываются так называемые смешанные стратегии, то есть стратегии, выбираемые случайно (например, по жребию). 33

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