Методы принятия решений. Принятие решений в условиях противоборства

Содержание

Слайд 2

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР В ТПР противоборство характеризуется нанесением конфликтующими

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР

В ТПР противоборство характеризуется нанесением конфликтующими

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

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР Игра – модель конфликтной ситуации, включающая

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР

Игра – модель конфликтной ситуации, включающая

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

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР Теория игр занимается моделями принятия решений,

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР

Теория игр занимается моделями принятия решений,

а не их поведенческими, психологическими аспектами или вопросами реализации решений.
Суть игры в том, что каждый из участников из множества альтернатив выбирает такую стратегию действий, которая, возможно, обеспечит ему наибольший выигрыш или наименьший проигрыш.
Результат зависит не только от него, но и от действий противника. Это значит, что он принимает решение в условиях неопределенности.
Слайд 5

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР Целью теории игр является выработка рекомендаций

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР

Целью теории игр является выработка рекомендаций

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

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР Если интересы участников противоположны, то эти

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР

Если интересы участников противоположны, то эти

модели называются антагонистическими играми.
Если интересы не совпадают, но не противоположны, то речь идет об играх с непротивоположными интересами.
Если в игре участвуют n лиц, то они могут вступать между собой в постоянные или временные коалиции, а игра называется коалиционной.
Слайд 7

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР Основные разновидности игр: антагонистические, игры с

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР

Основные разновидности игр:
антагонистические,
игры с непротивоположными интересами
коалиционные

игры
биматричные,
дифференциальные,
матричные,
статистические игры с природой
Слайд 8

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР Основной особенностью теории игр является расширение

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР

Основной особенностью теории игр является расширение

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

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР Другой особенностью игровых моделей является поиск

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР

Другой особенностью игровых моделей является поиск

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

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР Рассмотрим игры с ненулевой суммой. Если

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР

Рассмотрим игры с ненулевой суммой.
Если

для конечной бескоалиционной игры двух лиц ставить в соответствие стратегиям 1-го игрока строки некоторой таблицы, стратегиям 2-го игрока – её столбцы, а клетки таблицы заполнять значениями выигрыша 1-го игрока, то полученная таблица называется матрицей выигрыша 1-го игрока.
Если клетки той же таблицы заполнить значениями функции выигрыша 2-го игрока, то получится матрица выигрышей 2-го игрока.
Слайд 11

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР Эта пара матриц полностью описывает биматричную

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР

Эта пара матриц полностью описывает биматричную

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

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР Биматричная игра не обязательно является антагонистической,

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР

Биматричная игра не обязательно является антагонистической,

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

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР Игру n лиц с ненулевой суммой

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР

Игру n лиц с ненулевой суммой

всегда можно преобразовать в игру n+1 лиц с нулевой суммой путем добавления «фиктивного» игрока.
Слайд 14

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР

 

Слайд 15

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР

 

Слайд 16

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР

Слайд 17

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР Целью каждого игрока является максимизации индивидуального

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР

Целью каждого игрока является максимизации индивидуального

выигрыша. Тогда приведенная пара матриц однозначно задает правила игры.
Слайд 18

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР

 

Слайд 19

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР

 

Слайд 20

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР Пример биматричной игры - классическая задача

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР

Пример биматричной игры -
классическая задача теории

игр «Дилемма заключенного».
Игроками являются два узника, находящиеся в предварительном заключении по подозрению в совершении преступления. При отсутствии прямых улик возможность их осуждения зависит от того, будут они говорить (Г) или молчать (М). Если в ходе следствия оба будут молчать, то наказанием будет лишь срок предварительного заключения (1 год). Если оба сознаются, то получат срок 3 года, учитывающий признание как смягчающее обстоятельство. Если же заговорит только один, а другой будет молчать, то заговоривший будет выпущен на свободу, а сохранивший молчание получит 10 лет. Заключенных лишили контакта.
Слайд 21

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР Ситуация иллюстрируется следующими платежными матрицами:

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР

Ситуация иллюстрируется следующими платежными матрицами:

Слайд 22

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР Особенности переговорного процесса Рассмотрим две пиратских

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР

Особенности переговорного процесса
Рассмотрим две пиратских процедуры

дележа добычи (золото), которые выглядят вполне демократичными и открытыми, но происходят в атмосфере взаимного недоверия.
Пусть два пирата делят 1 кг золотого песка. Здесь лучшей процедурой считается «дели - выбирай»:
один делит на две части, а другой выбирает любую из них.
Слайд 23

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР Особенности переговорного процесса Пусть теперь три

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР

Особенности переговорного процесса
Пусть теперь три пирата

делят 1 кг золотого песка. Тогда процедура «дели - выбирай» состоит в следующем.
первый пират выделяет часть, на которую он претендует.
если второй и третий пираты одновременно согласны с выбором первого, то он получает свою долю и выбывает из дележа.
если не согласны оба пирата, то право деления передается другому пирату.
если же с предложением первого пирата согласен только один, то несогласному третьему пирату дается право выделить из доли первого пирата свою часть, и он выбывает из дележа.
Слайд 24

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР Иначе выглядит процедура деления золотых слитков.

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР

Иначе выглядит процедура деления золотых слитков.


Пусть n пиратов решили разделить 100 золотых слитков.
Установлена следующая процедура дележа.
Сначала дележ проводит старший пират. Его предложение принимается, если с ним согласна хотя бы половина пиратов, включая его самого. Если с ним не согласится больше половины, то он выбывает из дележа, а право дележа передается второму по старшинству пирату и т.д.
Слайд 25

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР Итоги дележа при этом будут выглядеть

ИСТОРИЯ, ЗАДАЧИ И РАЗНОВИДНОСТИ ИГР

Итоги дележа при этом будут выглядеть

следующим образом:
для двух пиратов – ( 100; 0 );
для трех пиратов – ( 99; 0; 1 ) (если бы средний пират предложил младшему объединиться против старшего пирата, пообещав ему половину золота, то где гарантия, что он его не обманет, заняв место старшего пирата и забрав все?);
для четырех пиратов – ( 99, 0, 1; 0 ) (cтарший пират рассуждает так: надо предложить дележ, который был бы выгоден хотя бы одному пирату, а мне давал бы наибольшую долю);
для пяти пиратов – (98, 0, 1; 0; 1) и т.д.
Слайд 26

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

 

Слайд 27

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

 

Слайд 28

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ В ситуации

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

В ситуации

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

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ Пример построения

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

Пример построения

платежной матрицы
Пример: игра Морра
Каждый из двух игроков показывает один или два пальца и одновременно называет количество пальцев, которое, по его мнению, покажет противник. Если один из игроков угадывает правильно, то он выигрывает сумму, равную сумме пальцев, показанных им и его противником, иначе игра заканчивается вничью.
Слайд 30

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

 

Слайд 31

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ Пример построения

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

Пример построения

платежной матрицы
Тогда игра состоит из 4×4 = 16 партий, а матрица выигрышей Q 1-го игрока имеет следующий вид:
Слайд 32

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ В антагонистических

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

В антагонистических

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

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ Для поиска

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

Для поиска

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

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ Проиллюстрируем критерий

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

Проиллюстрируем критерий

максимина/минимакса и понятие «седловая точка» на примере.
Пусть задана игра со следующей платежной матрицей:
Слайд 35

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

 

Слайд 36

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ Для данной

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

Для данной

матрицы α = β = ν =3, т.е. игра имеет седловую точку (точка равновесия, или точка Нэша). Здесь ν – чистая цена игры.
Cхематичное изображение седловой точки
Слайд 37

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ У седловой

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

У седловой

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

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

 

Слайд 39

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

 

Слайд 40

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ Большинство антагонистических

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

Большинство антагонистических

игр двух лиц с нулевой суммой не имеют седловой точки, т.е. нет решения в чистых стратегиях.
Например, в игре Морра с платежной матрицей
нет седловой точки. Действительно, α = - 2, β = 2, т.е. интервал [- 2, 2] является как бы ничейным и каждый из игроков может попытаться улучшить результат на этом интервале.
Слайд 41

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ Если α

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

Если α

< β, то существует ли в игре цена, и какие стратегии рекомендовать игрокам в качестве оптимальных стратегий?
Рассмотрим платежную матрицу в известной игре «Орлянка».
Игра «Орлянка»
По условиям игры 1-й игрок выкладывает монету на стол, а 2-й игрок, не видя монеты, угадывает, какой стороной вверх она положена («орел» - О или «решка» - Р). В случае угадывания он получает от 1-го игрока 1 рубль, а в противном случае уплачивает ему 1 рубль.
Слайд 42

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ Платежная матрица

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

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

этой игры имеет следующий вид:
Здесь α = - 1 < β = 1. Если игра проводится только один раз, то каждый из игроков может принять любое решение. О каких-то оптимальных стратегиях игроков здесь говорить не приходится. При многократном повторении игры положение меняется. Придерживаться одной стратегии невыгодно, их надо случайно смешивать (причем в данной игре – с одинаковой частотой).
Слайд 43

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

 

Слайд 44

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

 

Слайд 45

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ Чистые стратегии

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

Чистые стратегии

являются несовместными событиями и единственными возможными событиями.
Чистая стратегия – это частный случай смешанной стратегии.
Если в смешанной стратегии i-я чистая стратегия применяется с вероятностью 1, то все остальные чистые стратегии не применяются.
Для соблюдения секретности каждый игрок применяет свои стратегии независимо от выбора другого игрока (лотерея).
Слайд 46

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ Возможность нахождения

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

Возможность нахождения

каждым игроком своей оптимальной стратегии базируется на основной теореме теории игр. Она является доказательством существования решения для каждой конечной антагонистической игры двух лиц с нулевой суммой.
В 1927 г. Э.Борель сформулировал основную теорему теории игр, а в 1928 г. Дж.фон Нейман доказал эту теорему.
Ее доказательство основано на теореме Брауэра о неподвижной точке и в силу этого является неконструктивным, т.е. не дает способа нахождения решения игры.
Слайд 47

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ Основная теорема

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

Основная теорема

теории игр
Всякая конечная антагонистическая игра двух лиц с нулевой суммой имеет цену ν* и у каждого игрока имеется, по меньшей мере, одна оптимальная стратегия (ξ*, η*).
Слайд 48

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ Как и

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

Как и

большинство фундаментальных математических теорем о существовании решения, теорема не дает ответа, в данном случае, на два вопроса:
Если известна некоторая смешанная стратегия, то как определить является она оптимальной или нет?
Если решение всегда существует, то чему равна цена игры и какие стратегии игроков являются оптимальными?
Слайд 49

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

 

Слайд 50

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ Проверка оптимальности

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

Проверка оптимальности

некоторой заданной
смешанной стратегии
1. Определить величину среднего выигрыша М(ξ, η) для заданной смешанной стратегии.
2. Проверить, выполняются ли в (4) неравенства слева для всех I = 1, 2,…, m. Если для некоторого i неравенство не выполняется, то стратегия ξ не является оптимальной.
Слайд 51

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ Проверка оптимальности

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

Проверка оптимальности

некоторой заданной
смешанной стратегии
3. Проверить, выполняются ли в (4) неравенства справа для всех j = 1, 2,…, n. Если для некоторого j неравенство не выполняется, то стратегия η не является оптимальной и останов.
4. Если неравенства (4) справедливы для всех индексов i, j, то стратегии ξ и η являются оптимальными, а цена игры равна М(ξ, η).
Слайд 52

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ Пример платежной

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

Пример платежной

матрицы для игры Морра,
в которой нет седловой точки
Определим, являются ли оптимальными в этой игре следующие стратегии 1-го и 2-го игрока:
ξ = (0, 3/5, 2/5, 0) и η = (0, 4/7, 3/7, 0).
Оценим вначале величину среднего выигрыша для заданных стратегий:
Слайд 53

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

 

Слайд 54

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

 

Слайд 55

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ При поиске

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

При поиске

решения игры иногда необходимо выполнять операции над платежными матрицами.
Какое влияние это оказывает на решение игры (оптимальные стратегии и цену игры)?
Слайд 56

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

 

Слайд 57

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ На основании

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

На основании

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

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

 

Слайд 59

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ Пример упрощения матрицы игры

ОСНОВНАЯ ТЕОРЕМА АНТАГОНИСТИЧЕСКИХ ИГР ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ

Пример упрощения

матрицы игры
Слайд 60

ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ИГР Чистые стратегии игрока, входящие в его оптимальную смешанную

ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ИГР

Чистые стратегии игрока, входящие в его оптимальную смешанную

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

ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ИГР Теорема Если один из игроков придерживается своей оптимальной

ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ИГР

Теорема
Если один из игроков придерживается своей оптимальной

смешанной стратегии, то его выигрыш остается неизменным и равным цене игры независимо от того, какую стратегию применяет другой игрок, если только тот не выходит за пределы своих активных стратегий.
Слайд 62

ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ИГР Общий подход к решению игровых задач Найти цену

ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ИГР

Общий подход к решению игровых задач
Найти цену игры

ν* и оптимальные стратегии игроков ξ*, η* по имеющейся платежной матрице, действуя по следующей схеме:
установить, имеется или нет в игре седловая точка, которая указывает на цену игры и определяет оптимальные чистые стратегии игроков;
если седловая точка отсутствует, то выяснить, нельзя ли упростить игру;
собственно поиск решения игры каким-либо методом.
Слайд 63

ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ИГР Аналитическое решение для простейшего случая игры (2×2), которая

ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ИГР

Аналитическое решение для простейшего случая игры (2×2), которая

задана следующей матрицей Q:
В игре нет седловой точки и матрицу нельзя упростить (обе стратегии игроков являются активными, иначе игра имела бы седловую точку).
Чему равна цена игры ν* и оптимальные стратегии игроков ξ*=(ξ*1, ξ*2 ), η*= (η*1, η*2 )?
Слайд 64

ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ИГР

ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ИГР

 

Слайд 65

ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ИГР

ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ИГР

 

Слайд 66

ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ИГР

ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ИГР

 

Слайд 67

ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ИГР

ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ИГР

 

Слайд 68

ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ИГР

ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ИГР

 

Слайд 69

ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ИГР

ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ИГР

Слайд 70

ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ИГР

ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ИГР

 

Слайд 71

ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ИГР

ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ИГР

 

Слайд 72

ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ИГР

ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ИГР

 

Слайд 73

ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ИГР

ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ИГР

 

Слайд 74

ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ИГР Точка максимума на нижней огибающей двух прямых

ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ИГР

Точка максимума на нижней огибающей двух прямых

Слайд 75

ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ИГР

ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ИГР

 

Слайд 76

ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ИГР 6.1. На существующем графике через точку максимина проведем

ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ИГР

6.1. На существующем графике через точку максимина проведем

прямую, параллельную оси абсцисс. Обозначим точки ее пересечения с осями ординат через M и N. Поиск оптимальной стратегии 2-го игрока с использованием построенного графика:
Слайд 77

ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ИГР

ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ИГР

 

Слайд 78

ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ИГР

ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ИГР

 

Слайд 79

ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ИГР

ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ИГР

 

Слайд 80

ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ИГР

ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ИГР

 

Слайд 81

ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ИГР Утверждение В любой конечной игре существует решение, в

ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ИГР

Утверждение
В любой конечной игре существует решение, в

котором количество активных стратегий каждого игрока не превосходит числа
min(m, n).
Геометрический метод можно применять при поиске решений игр (2×n) и (m×2). Для этого используется данное утверждение, справедливость которого доказана.
Слайд 82

ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ИГР Игры (2×n) и (m×2) сводятся к решению игры

ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ИГР

Игры (2×n) и (m×2) сводятся к решению игры

(2×2). Их геометрический метод решения аналогичен рассмотренному выше.
Аналогично в трехмерном пространстве можно решать игры (3×n), (m×3), сводя их к игре (3×3). Однако получающиеся при этом построения оказываются весьма громоздкими и требуют привлечения методов начертательной геометрии.
Слайд 83

РЕШЕНИЕ ИГР МЕТОДОМ ПОСЛЕДОВАТЕЛЬНЫХ ПРИБЛИЖЕНИЙ Любое измерение имеет определенную погрешность, ошибки

РЕШЕНИЕ ИГР МЕТОДОМ ПОСЛЕДОВАТЕЛЬНЫХ ПРИБЛИЖЕНИЙ

Любое измерение имеет определенную погрешность, ошибки

могут накапливаться.
Поиск оптимального решения игры при большом количестве стратегий игроков - достаточно трудоемкий процесс.
Точность в определении значения игры и оптимальных стратегий игроков оправдана не всегда.
Достаточно найти приближённое решение, которое даёт средний выигрыш, близкий к цене игры, и приближённые оптимальные стратегии игроков.
Слайд 84

РЕШЕНИЕ ИГР МЕТОДОМ ПОСЛЕДОВАТЕЛЬНЫХ ПРИБЛИЖЕНИЙ Метод Брауна - Робинсон один из

РЕШЕНИЕ ИГР МЕТОДОМ ПОСЛЕДОВАТЕЛЬНЫХ ПРИБЛИЖЕНИЙ

Метод Брауна - Робинсон
один из

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

РЕШЕНИЕ ИГР МЕТОДОМ ПОСЛЕДОВАТЕЛЬНЫХ ПРИБЛИЖЕНИЙ Метод Брауна - Робинсон Для анализа

РЕШЕНИЕ ИГР МЕТОДОМ ПОСЛЕДОВАТЕЛЬНЫХ ПРИБЛИЖЕНИЙ

Метод Брауна - Робинсон
Для анализа

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

РЕШЕНИЕ ИГР МЕТОДОМ ПОСЛЕДОВАТЕЛЬНЫХ ПРИБЛИЖЕНИЙ Метод Брауна - Робинсон После каждого

РЕШЕНИЕ ИГР МЕТОДОМ ПОСЛЕДОВАТЕЛЬНЫХ ПРИБЛИЖЕНИЙ

Метод Брауна - Робинсон
После каждого

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

РЕШЕНИЕ ИГР МЕТОДОМ ПОСЛЕДОВАТЕЛЬНЫХ ПРИБЛИЖЕНИЙ Например, пусть дана следующая матрица выигрышей

РЕШЕНИЕ ИГР МЕТОДОМ ПОСЛЕДОВАТЕЛЬНЫХ ПРИБЛИЖЕНИЙ

Например, пусть дана следующая матрица выигрышей

1-го игрока:
В игре нет седловой точки (α = 0, β = 2).
Слайд 88

РЕШЕНИЕ ИГР МЕТОДОМ ПОСЛЕДОВАТЕЛЬНЫХ ПРИБЛИЖЕНИЙ Результаты вычислений по методу последовательных приближений:

РЕШЕНИЕ ИГР МЕТОДОМ ПОСЛЕДОВАТЕЛЬНЫХ ПРИБЛИЖЕНИЙ

Результаты вычислений по методу последовательных приближений:

Слайд 89

РЕШЕНИЕ ИГР МЕТОДОМ ПОСЛЕДОВАТЕЛЬНЫХ ПРИБЛИЖЕНИЙ

РЕШЕНИЕ ИГР МЕТОДОМ ПОСЛЕДОВАТЕЛЬНЫХ ПРИБЛИЖЕНИЙ

 

Слайд 90

РЕШЕНИЕ ИГР МЕТОДОМ ПОСЛЕДОВАТЕЛЬНЫХ ПРИБЛИЖЕНИЙ

РЕШЕНИЕ ИГР МЕТОДОМ ПОСЛЕДОВАТЕЛЬНЫХ ПРИБЛИЖЕНИЙ

 

Слайд 91

РЕШЕНИЕ ИГР МЕТОДОМ ПОСЛЕДОВАТЕЛЬНЫХ ПРИБЛИЖЕНИЙ В таблице приведены розыгрыши для 12

РЕШЕНИЕ ИГР МЕТОДОМ ПОСЛЕДОВАТЕЛЬНЫХ ПРИБЛИЖЕНИЙ

В таблице приведены розыгрыши для 12

партий.
В результате цена игры ν ≈ 0,9,
приближенное значение оптимальной стратегии 1-го игрока
ξ ≈ (1/12, 7/12, 4/12),
2-го игрока
η ≈ (0,8/12,4/12).
Приведем для сравнения точное решение: ν* = 1, ξ* = η* = (0, 8/12, 4/12).
Слайд 92

РЕШЕНИЕ ИГР МЕТОДОМ ПОСЛЕДОВАТЕЛЬНЫХ ПРИБЛИЖЕНИЙ

РЕШЕНИЕ ИГР МЕТОДОМ ПОСЛЕДОВАТЕЛЬНЫХ ПРИБЛИЖЕНИЙ

 

- Предыдущая
По истокам России
Следующая -
Мультики. Бэмби

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

Дифференцирование функций комплексной переменной. Понятие аналитической функции
Разные задачи. Урок 141
Подготовка к ОГЭ по математике
Степень с натуральным показателем и её свойства (7 класс)
Понятие обратной функции. Определение обратных тригонометрических функций
Квадратный корень из степени
Случайные величины
Уравнения, приводимые к квадратным
Взаимное пересечение поверхностей
Симметрия
Контрольная работа по математике (начальная школа)
Теорема Пифагора. Решение задач. Урок для 8 класса
Сложение и вычитание многочленов
Действия над комплексными числами
Перестановка слагаемых
Векторы
Линейная функция, её график, свойства
Числа на координатной прямой
Задачи для повторения. 5 класс
Співнапрямлені промені
введение в мат.статистику
Величины. Математический диктант
Solid Modeling
Степень с натуральным, целым и рациональным показателем. Свойства степеней
СЛУ. Теорема Крамера. Метод обратной матрицы
Математическая игра: Математика - царица наук
Көпжақтың қимасын салу, геометрия 10 сынып
Тренажёр. Таблица умножения на 8 и 9. Математика, 3 класс
Вы можете прислать нам Вашу презентацию и мы опубликуем ее на сайте.
Обратная связь
Для правообладателей
Email: Нажмите что бы посмотреть