Теория игр - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Теория игр. Доклад-сообщение содержит 60 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Теория игр Теория игр представляет собой математическую теорию конфликтных ситуаций. Ее цель – выработка рекомендаций по разумному поведению участников конфликта Впервые описана в 1944 – в монографии фон Неймана и Моргеншерна

Слайд 2

Описание слайда:

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

Слайд 3

Описание слайда:

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

Слайд 4

Описание слайда:

Игры можно классифицировать Игры парные (2 игрока) и множественные. По количеству возможных стратегий: конечные (конечное у каждого игрока) бесконечные (хотя бы у одного игрока бесконечное число стратегий)

Слайд 5

Описание слайда:

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

Слайд 6

Описание слайда:

ОПРЕДЕЛЕНИЯ ОПРЕДЕЛЕНИЯ Стратегия – совокупность правил, определяющих выбор варианта действия игроком в зависимости от ситуации в игре. Целью является отыскание оптимальной стратегии для каждого игрока. Оптимальная стратегия – стратегия, которая при многократном повторении игры обеспечивает игроку максимально возможный выигрыш или минимально возможный проигрыш независимо от поведения противника. Выбор одной из возможных стратегий и ее реализация называется ходом. Ход – может быть личным (выбор стратегии сознателен) и случайным.

Слайд 7

Описание слайда:

Игру можно описать разными способами Позиционный – задается в виде дерева шагов. Нормальный – задаются допустимые стратегии для каждого игрока и функция выигрыша, которая определяет выигрыш или проигрыш для каждой стратегии. Чаще всего задается в виде платежной матрицы

Слайд 8

Описание слайда:

Конечная парная антагонистическая игра Два игрока (I и II) обладают конечным набором стратегий: I стратегии А1…..Am II стратегии B1….Bn Эта игра размерностью n×m.

Слайд 9

Описание слайда:

Предположим, что на некотором ходе игрок I выбрал стратегию Ai , а игрок II отвечает стратегией Bj Предположим, что на некотором ходе игрок I выбрал стратегию Ai , а игрок II отвечает стратегией Bj Тогда W1 (Ai , Bj) – выигрыш, который получит игрок I при этой паре стратегий. W2 (Ai , Bj) – выигрыш, который получит игрок II при этой паре стратегий Так как игра антагонистическая, то W1 (Ai , Bj) + W2 (Ai , Bj) =0 Или W1 (Ai , Bj) =- W2 (Ai , Bj) = W (Ai , Bj)

Слайд 10

Описание слайда:

Обозначим W (Ai , Bj)=aij тогда получим платежную матрицу Обозначим W (Ai , Bj)=aij тогда получим платежную матрицу

Слайд 11

Описание слайда:

Пример Играют 2 игрока, каждый называет цифру 1, 2, или 3. Если разница между цифрами игроков положительная, то это выигрыш I игрока, если отрицательная – II игрока, если =0, то ничья. I A1=1 A2=2 A3=3 II B1=1 B2=2 B3=3

Слайд 12

Описание слайда:

Запишем платежную матрицу. Запишем платежную матрицу.

Слайд 13

Описание слайда:

Следует найти оптимальную стратегию для I и II игроков. Следует найти оптимальную стратегию для I и II игроков. Используем основной принцип ТИ: Какую бы стратегию не выбрал I игрок, II игрок всегда ответит на нее такой стратегией, при которой выигрыш I будет минимальным и следовательно у II минимальный проигрыш.

Слайд 14

Описание слайда:

Для поиска лучшей стратегии I игрока найдем минимальный элемент в каждой строке платежной матрицы αi =min aij Для поиска лучшей стратегии I игрока найдем минимальный элемент в каждой строке платежной матрицы αi =min aij Среди αi найдем максимальный α=maxαi α=max (min aij) - нижняя цена игры или гарантированный выигрыш I (максимин) Стратегия I игрока, при которой достигается α называется максиминой или перестраховочной. При этой стратегии I игроку гарантирован выигрыш не менее α .

Слайд 15

Описание слайда:

Наилучшая стратегия для II игрока. Наилучшая стратегия для II игрока. Находим максимальный элемент в каждом столбце матрицы βj=max aij Среди βj найдем минимальныйβ=min βj β = min (max aij) верхняя граница или минимакс. Стратегия II игрока, при которой достигается это значение называется минимаксной или перестраховочной для II. Если II придерживается своей минимаксной стратегии, то он получает выигрыш не больший, чем β

Слайд 16

Описание слайда:

Слайд 17

Описание слайда:

В ТИ доказано, что α≤β В ТИ доказано, что α≤β Существуют игры, в которых α=β=γ - чистая цена игры, это игры с седловой точкой. Пара оптимальных стратегий (A*I, B*j) для I и II игроков , при которых достигается чистая цена игры называется седловой точкой платежной матрицы. Если игра содержит седловую точку, то говорят, что решение находится в чистых стратегиях.

Слайд 18

Описание слайда:

Пример

Слайд 19

Описание слайда:

Оптимальные чистые стратегии обладают свойством равновесия: игроки всегда придерживаются своих оптимальных стратегий, так как это выгодно. Оптимальные чистые стратегии обладают свойством равновесия: игроки всегда придерживаются своих оптимальных стратегий, так как это выгодно. I игрок не может увеличить выигрыш больше чем γ, а II игрок не может уменьшить проигрыш и сделать больше γ

Слайд 20

Описание слайда:

Если седловой точки в платежной матрице нет, то решение игры ищем в смешанных стратегиях. Если седловой точки в платежной матрице нет, то решение игры ищем в смешанных стратегиях. Смешанная стратегия – сложная стратегия, в которой чистые стратегии игроков применяются с некоторыми частотами (вероятностями)

Слайд 21

Описание слайда:

I игрок. р1 - вероятность применения стратегии А1,… рi- вероятность применения стратегии Аi … рm вероятность применения стратегии Аm pi≥0, i=1…m, ∑ pi=1. I игрок. р1 - вероятность применения стратегии А1,… рi- вероятность применения стратегии Аi … рm вероятность применения стратегии Аm pi≥0, i=1…m, ∑ pi=1. Чистая стратегия Аi называется активной, если вероятность ее использования отлична от нуля pi≠0.

Слайд 22

Описание слайда:

II игрок. q1 - вероятность применения стратегии B1,… qj- вероятность применения стратегии Bj … qn вероятность применения стратегии Bn qj≥0, j=1…n, ∑ qj=1. II игрок. q1 - вероятность применения стратегии B1,… qj- вероятность применения стратегии Bj … qn вероятность применения стратегии Bn qj≥0, j=1…n, ∑ qj=1. Чистая стратегия Bj называется активной, если вероятность ее использования отлична от нуля qj≠0.

Слайд 23

Описание слайда:

Любая антагонистическая парная конечная игра имеет по крайней мере одно решение, возможное в смешанных стратегиях. Любая антагонистическая парная конечная игра имеет по крайней мере одно решение, возможное в смешанных стратегиях. Следовательно игра имеет цену γ, α≤ γ ≤ β Игрок I стремится добиться выигрыша = γ, а игрок II стремится минимизировать проигрыш до γ. Смешанные стратегии также обладают свойством равновесия, обоим игрокам выгодно их применять.

Слайд 24

Описание слайда:

Теорема фон Неймана Применение оптимальных смешанных стратегий гарантирует игроку максимально возможный средний выигрыш (минимально возможный средний проигрыш) равный цене игры γ, независимо от поведения противника, если игрок не выходит за пределы своих активных стратегий.

Слайд 25

Описание слайда:

Доказательство Для I игрока предположим, что r стратегий активны, r≤m , следовательно p*A=(p1,….pr,0…0) Для II игрока предположим, что s стратегий активны, s≤n , следовательно q*B=(q1,….qs,0…0) Применяя эти стратегии I получит выигрыш =γ, а II – проигрыш =γ.

Слайд 26

Описание слайда:

Требуется доказать, что I применяя оптимальные стратегии независимо от действий II получит выигрыш =γ. Требуется доказать, что I применяя оптимальные стратегии независимо от действий II получит выигрыш =γ. Пусть первый применяет оптимальные стратегии А*, а II применяет чистые стратегии В1…Вs. Тогда выигрыш I будет γ1… γs. Так как II не применяет оптимальные стратегии, то он может получить проигрыш ≥γ: γ1≥γ…..γs≥γ.

Слайд 27

Описание слайда:

Выразим γ через γ1… γs . Выразим γ через γ1… γs . γ=q1γ1+….. +qsγs – средневзвешенное значение величин γ1… γs (веса- это вероятности) Это значение было бы >γ, если бы хотя бы одно γj >γ следовательно γ1… γs =γ., следовательно I независимо от действий II получит выигрыш =γ.

Слайд 28

Описание слайда:

Игра размерностью 2 на 2 В игре 2 участника и каждый имеет по 2 допустимые стратегии. I A1 A2 II B1 B2

Слайд 29

Описание слайда:

Предположим, что седловой точки нет, тогда решение будет находиться в смешанных стратегиях. Предположим, что седловой точки нет, тогда решение будет находиться в смешанных стратегиях. P=(p1,p2) q=(q1,q2) Обе стратегии активны, иначе - игра с седловой точкой. Найдем оптимальную стратегию для I игрока. Согласно теореме, если I игрок будет придерживаться оптимальной стратегии, то получит выигрыш =γ независимо от II игрока. Если II применяет стратегию B1, то I игрок получит выигрыш a11p1+a21p2=γ Если II применяет стратегию B2, то I игрок получит выигрыш a12p1+a22p2=γ

Слайд 30

Описание слайда:

Получаем систему Получаем систему Решаем и находим p1 p2 γ

Слайд 31

Описание слайда:

Слайд 32

Описание слайда:

Пример Дана платежная матрица

Слайд 33

Описание слайда:

Слайд 34

Описание слайда:

Геометрический метод В декартовой системе координат на оси абсцисс откладывается отрезок равный 1. Точка х=0 соответствует стратегии А1, х=1 – стратегии А2. На левой оси ординат откладываются выигрыши стратегии А1, на правой – стратегии А2.

Слайд 35

Описание слайда:

Если игрок II применяет стратегию В1, то его выигрыш при использовании стратегии А1 и А2 составляет соответственно а11 и а21. Если игрок II применяет стратегию В1, то его выигрыш при использовании стратегии А1 и А2 составляет соответственно а11 и а21. Соединим точки В1 В1. Если игрок I применяет смешанную стратегию, то средний выигрыш а11р1+а21р2=γ – точка N на прямой В1 В1, абсцисса ее равна р2. В1 В1 называют стратегией игрока I при применении стратегий А1 и А2 с соответствующими вероятностями р1 и р2.

Слайд 36

Описание слайда:

Если игрок II применяет стратегию В2, то его выигрыш при использовании стратегии А1 и А2 составляет соответственно а12 и а22. В2 В2 соответствует стратегии игрока II. Если игрок II применяет стратегию В2, то его выигрыш при использовании стратегии А1 и А2 составляет соответственно а12 и а22. В2 В2 соответствует стратегии игрока II. Точка пересечения В1 В1 и В2 В2 определяет цену игры γ. Ординаты точек отрезка В2 В2 равны среднему числу стратегий А1 и А2 с вероятностями р1 и р2. Ломаная В1 N В2 – это нижняя граница выигрыша, получаемого игроком I. В точке N он максимален и составляет γ

Слайд 37

Описание слайда:

Пример Найти оптимальную смешанную стратегию руководителю предприятия и гарантированный средний выигрыш при выборе новых технологий А1 и А2, если известны выигрыши каждого вида по сравнению со старой технологией:

Слайд 38

Описание слайда:

Решение Решение Нижняя цена игры α=max(1,2)=2 Верхняя цена игры β=min(3,6)=3 α ≠ β, седловой точки нет. Цена игры будет 2≤γ≤3. Находим решение игры в смешанных стратегиях геометрическим методом.

Слайд 39

Описание слайда:

Слайд 40

Описание слайда:

Игра размерностью m×n В ТИ доказано, что в играх размерностью m×n число активных стратегий равно min{m,n} Таким образом, решение игр m×2 и 2×n сводится к решению игр 2×2.

Слайд 41

Описание слайда:

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

Слайд 42

Описание слайда:

Если в матрице все элементы некоторой строки, соответствующие стратегии Ai I игрока не больше соответствующих элементов другой строки, то стратегии Ai называется заведомо невыгодной для I игрока. Если в матрице все элементы некоторой строки, соответствующие стратегии Ai I игрока не больше соответствующих элементов другой строки, то стратегии Ai называется заведомо невыгодной для I игрока. Если в матрице все элементы некоторого столбца, соответствующие стратегии Bj II игрока не меньше соответствующих элементов другого столбца, то стратегию Bj называется заведомо невыгодной для II игрока

Слайд 43

Описание слайда:

Рассмотрим платежную матрицу Рассмотрим платежную матрицу

Слайд 44

Описание слайда:

Матричные игры m×n Рассмотрим игру, которая будет описана следующей платежной матрицей.

Слайд 45

Описание слайда:

Алгоритм решения

Слайд 46

Описание слайда:

Находим решение в смешанных стратегиях I игрок чистые стратегии А1…..Am II игрок чистые стратегии B1….Bn Оптимальные смешанные стратегии p*A ,p*B Предположим, что все элементы платежной матрицы ≥0, иначе добавляем к каждому элементу положительное число, при этом оптимальные стратегии не меняются, а цена игры увеличивается на это число.

Слайд 47

Описание слайда:

Согласно теореме ТИ если I игрок будет придерживаться оптимальной смешанной стратегии, то он получит выигрыш ≥γ (цены игры). Согласно теореме ТИ если I игрок будет придерживаться оптимальной смешанной стратегии, то он получит выигрыш ≥γ (цены игры). При этом II игрок применяет свои чистые стратегии

Слайд 48

Описание слайда:

Введем обозначения xi=pi/γ i=1..m Введем обозначения xi=pi/γ i=1..m Разделим неравенства на γ

Слайд 49

Описание слайда:

Цель I игрока увеличить выигрыш γ Цель I игрока увеличить выигрыш γ Так как p1+…+pm=1, то x1+…xm=1/γ F=x1+…..+xm→min Получаем задачу линейного программирования.

Слайд 50

Описание слайда:

Составим аналогичную задачу для II игрока. Составим аналогичную задачу для II игрока. Если II игрок придерживается оптимальной смешанной стратегии, то он получит проигрыш ≤γ. При этом I игрок применяет свои чистые стратегии.

Слайд 51

Описание слайда:

Введем обозначения yi=qj/γ j=1..n Введем обозначения yi=qj/γ j=1..n Разделим неравенства на γ

Слайд 52

Описание слайда:

Таким образом, решение матричных игр m×n сводится к решению пары двойственных симметричных задач. Таким образом, решение матричных игр m×n сводится к решению пары двойственных симметричных задач.

Слайд 53

Описание слайда:

Решая эти задачи найдем оптимальное решение x*=(x1*.....xm*) y*=(y*1…y*n) Решая эти задачи найдем оптимальное решение x*=(x1*.....xm*) y*=(y*1…y*n) Отсюда найдем цену игры:

Слайд 54

Описание слайда:

Задача Найти оптимальную стратегию и цену игры

Слайд 55

Описание слайда:

Слайд 56

Описание слайда:

Слайд 57

Описание слайда:

Слайд 58

Описание слайда:

Слайд 59

Описание слайда:

Ответ У*=(0; 0,5; 1) X*=(0,5; 1; 0) γ=1/1,5=0,66= 2/3 α≤γ≤β q*B=(0;1/3;2/3) p*A=(1/3;2/3;0)

Слайд 60

Описание слайда:

Вопросы Каковы основные термины и определения теории игр? Какие классы игр можно выделить? Определите антагонистическую матричную игру. Каков принцип минимакса? Когда следует использовать смешанные стратегии и как их найти? Каков геометрический метод решения игры? Как найти решение с помощью симплекс-метода?

Теги Теория

Похожие презентации