Основы теории матричных игр. Принятие решений в условиях неопределенности

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

Основы теории матричных игр. Принятие решений в условиях неопределенности, слайд №2

Основы теории матричных игр. Принятие решений в условиях неопределенности, слайд №3

Основы теории матричных игр. Принятие решений в условиях неопределенности, слайд №4

Основы теории матричных игр. Принятие решений в условиях неопределенности, слайд №5

Основы теории матричных игр. Принятие решений в условиях неопределенности, слайд №6

Основы теории матричных игр. Принятие решений в условиях неопределенности, слайд №7

Основы теории матричных игр. Принятие решений в условиях неопределенности, слайд №8

Основы теории матричных игр. Принятие решений в условиях неопределенности, слайд №9

Основы теории матричных игр. Принятие решений в условиях неопределенности, слайд №10

Основы теории матричных игр. Принятие решений в условиях неопределенности, слайд №11

Основы теории матричных игр. Принятие решений в условиях неопределенности, слайд №12

Основы теории матричных игр. Принятие решений в условиях неопределенности, слайд №13

Основы теории матричных игр. Принятие решений в условиях неопределенности, слайд №14

Основы теории матричных игр. Принятие решений в условиях неопределенности, слайд №15

Основы теории матричных игр. Принятие решений в условиях неопределенности, слайд №16

Основы теории матричных игр. Принятие решений в условиях неопределенности, слайд №17

Основы теории матричных игр. Принятие решений в условиях неопределенности, слайд №18

Основы теории матричных игр. Принятие решений в условиях неопределенности, слайд №19

Основы теории матричных игр. Принятие решений в условиях неопределенности, слайд №20

Основы теории матричных игр. Принятие решений в условиях неопределенности, слайд №21

Основы теории матричных игр. Принятие решений в условиях неопределенности, слайд №22

Основы теории матричных игр. Принятие решений в условиях неопределенности, слайд №23

Основы теории матричных игр. Принятие решений в условиях неопределенности, слайд №24

Основы теории матричных игр. Принятие решений в условиях неопределенности, слайд №25

Основы теории матричных игр. Принятие решений в условиях неопределенности, слайд №26

Основы теории матричных игр. Принятие решений в условиях неопределенности, слайд №27

Основы теории матричных игр. Принятие решений в условиях неопределенности, слайд №28

Основы теории матричных игр. Принятие решений в условиях неопределенности, слайд №29

Основы теории матричных игр. Принятие решений в условиях неопределенности, слайд №30

Основы теории матричных игр. Принятие решений в условиях неопределенности, слайд №31

Основы теории матричных игр. Принятие решений в условиях неопределенности, слайд №32

Основы теории матричных игр. Принятие решений в условиях неопределенности, слайд №33

Основы теории матричных игр. Принятие решений в условиях неопределенности, слайд №34

Основы теории матричных игр. Принятие решений в условиях неопределенности, слайд №35

Основы теории матричных игр. Принятие решений в условиях неопределенности, слайд №36

Основы теории матричных игр. Принятие решений в условиях неопределенности, слайд №37

Основы теории матричных игр. Принятие решений в условиях неопределенности, слайд №38

Основы теории матричных игр. Принятие решений в условиях неопределенности, слайд №39

Содержание ▲

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

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

Слайд 1

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

Слайд 2

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

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

Слайд 3

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

1. Основные понятия теории 1. Основные понятия теории матричных игр

Слайд 4

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

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

Слайд 5

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

Отдельные математические вопросы, касающиеся конфликтов, рассматривались начиная с 17 в. многими учёными. Отдельные математические вопросы, касающиеся конфликтов, рассматривались начиная с 17 в. многими учёными. Систематическая же математическая теория стратегических игр была детально разработана в 30-х годах XX века как средство математического подхода к явлениям конкурентной экономики. В ходе своего развития теория игр переросла эти рамки и превратилась в общую математическую теорию конфликтов. Её создателем считается Джон фон Нейман. Первой фундаментальной книгой по теории игр была изданная в 1944 году работа "Теория игр и экономическое поведение" (Нейман Д., Моргенштерн О. М.:Наука,1970).

Слайд 6

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

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

Слайд 7

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

Всякая игра включает в себя три элемента: участников игры – игроков, правила игры, оценку результатов действий игроков. Всякая игра включает в себя три элемента: участников игры – игроков, правила игры, оценку результатов действий игроков. Игроком (лицом, стороной, или коалицией) называется отдельная совокупность интересов, отстаиваемая в игре. Если данную совокупность интересов отстаивает несколько участников игры, то они рассматриваются как один игрок. Игроки, имеющие противоположные по отношению друг к другу интересы, называются противниками. В игре могут сталкиваться интересы двух или более противников. Одна реализация игры называется партией; выбор действия (в пределах правил) – ходом. Ходы бывают личные и случайные. Личный ход предполагает сознательный выбор того или иного действия, разрешенного правилами игры, а случайный – не зависит от воли игрока (например, он может быть определён подбрасыванием монеты или игральной кости). Игры, в которых имеются личные ходы, называются стратегическими. Игры, состоящие только из случайных ходов, называют азартными.

Слайд 8

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

Стратегией игрока называется совокупность правил, определяющих выбор варианта действий при каждом личном ходе в зависимости от сложившейся ситуации. Стратегией игрока называется совокупность правил, определяющих выбор варианта действий при каждом личном ходе в зависимости от сложившейся ситуации. В зависимости от числа стратегий игры делятся на конечные и бесконечные. Игра называется конечной, если у каждого игрока имеется в распоряжении только конечное число стратегий. В противном случае игра называется бесконечной. Оптимальной стратегией игрока называется такая, которая обеспечивает ему наилучшее положение в данной игре, т.е. максимальный выигрыш. Если игра повторяется неоднократно и содержит, кроме личных, ещё и случайные ходы, оптимальная стратегия обеспечивает максимальный средний выигрыш. Игра называется игрой с нулевой суммой, если сумма выигрышей всех игроков равна нулю, т.е. каждый игрок выигрывает только за счёт других. Самый простой случай – парная игра с нулевой суммой – называется антагонистической. Антагонистической игрой называется система G=, где A,B - непустые множества стратегий соответственно первого и второго игроков; H(a,b) – функция выигрыша игрока A (то есть функция потерь игрока B), aA, bB. Таким образом, в процессе игры каждый игрок выбирает свою стратегию, в результате чего образуется ситуация (a, b), которой соответствует выигрыш Н(a, b) для первого игрока и – проигрыш Н(a, b) для второго.

Слайд 9

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

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

Слайд 10

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

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

Слайд 11

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

Такую игру (Г ) называют матричной. Такую игру (Г ) называют матричной. Она определяется тройкой Г=(X,Y,K), где Х – множество стратегий 1-го игрока, Y – множество стратегий 2-го игрока, K=K(x,y) – функция выигрыша (выигрыш 1-го игрока и соответственно проигрыш 2-го при условии, что 1-й игрок выбрал стратегию , а 2-й – стратегию ). Пару (x,y) называют ситуацией в игре Г.

Слайд 12

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

Пусть 1-й игрок имеет всего m стратегий, а 2-й – n стратегий: Пусть 1-й игрок имеет всего m стратегий, а 2-й – n стратегий: Х=М={1,2, …, m}, Y=N={1,2, …, n}. Тогда игра Г полностью определяется заданием матрицы , где aij=K(i,j) – выигрыш 1-го игрока при условии, что он выбрал стратегию (т.е. строку) i, а 2-й игрок – стратегию (т.е. столбец) j (эти стратегии называют чистыми). Матрица А называется матрицей игры или платежной матрицей.

Слайд 13

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

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

Слайд 14

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

Пусть – платежная матрица игры Г. Пусть – платежная матрица игры Г. Если 1-й игрок выбрал стратегию i, то в худшем случае он выиграет . Поэтому он всегда может гарантировать себе выигрыш соответствующая стратегия 1-го игрока называется максиминной.

Слайд 15

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

Второй игрок, выбрав стратегию j, в худшем случае проиграет , а значит, может гарантировать себе проигрыш , Второй игрок, выбрав стратегию j, в худшем случае проиграет , а значит, может гарантировать себе проигрыш , соответствующая стратегия 2-го игрока называется минимаксной.

Слайд 16

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

Схема: Схема:

Слайд 17

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

Например, Например, Соответствующие стратегии: i0=1(максиминная), j0=1,2 (минимаксная).

Слайд 18

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

Справедливо неравенство: Справедливо неравенство:

Слайд 19

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

Ситуация (i*, j*) называется ситуацией равновесия, или седловой точкой, если для любых , , выполняется неравенство Ситуация (i*, j*) называется ситуацией равновесия, или седловой точкой, если для любых , , выполняется неравенство Соответствующие стратегии i*, j* называются оптимальными чистыми стратегиями 1-го и 2-го игроков, а число называется ценой игры. Элемент является одновременно минимумом в своей строке и максимумом в своем столбце.

Слайд 20

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

Ситуация равновесия существует тогда и только тогда, когда (это значение и является ценой игры v). Ситуация равновесия существует тогда и только тогда, когда (это значение и является ценой игры v).

Слайд 21

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

Например, Например, (2,3)-ситуация равновесная, v =4 – цена игры, i*=2, j*=3 – оптимальные стратегии 1-го и 2-го игроков. Выбрав их, 1-й игрок обеспечит себе выигрыш не менее 4 ед., а 2-й игрок проиграет не более 4 ед. при любом выборе другого игрока.

Слайд 22

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

Смешанной стратегией для 1-го игрока называется упорядоченная система m действительных чисел x=(x1, x2, …, xm), , Смешанной стратегией для 1-го игрока называется упорядоченная система m действительных чисел x=(x1, x2, …, xm), , , которые можно рассматривать как относительные частоты (вероятности), с которыми 1-й игрок выбирает чистые стратегии i=1, 2, …, m. Аналогично определяется смешанная стратегия для 2-го игрока: y=(y1, y2, …, yn), , .

Слайд 23

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

Функция выигрыша K(x,y) в ситуации (x,y) определяется как математическое ожидание выигрыша 1-го игрока при условии, что 1-й и 2-й игроки выбрали соответственно стратегии x=(x1, x2, …, xm) и y=(y1, y2, …, yn): Функция выигрыша K(x,y) в ситуации (x,y) определяется как математическое ожидание выигрыша 1-го игрока при условии, что 1-й и 2-й игроки выбрали соответственно стратегии x=(x1, x2, …, xm) и y=(y1, y2, …, yn): .

Слайд 24

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

Если для некоторых и и для всех и выполняется неравенство , то x*, y* называются оптимальными смешанными стратегиями игроков, Если для некоторых и и для всех и выполняется неравенство , то x*, y* называются оптимальными смешанными стратегиями игроков, число называется ценой игры, пара (x*, y*) – стратегической седловой точкой тройка x*, y*, v – решением игры.

Слайд 25

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

Свойства оптимальных стратегий. Свойства оптимальных стратегий.

Слайд 26

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

1. Пусть K(x,y) – математическое ожидание выигрыша в игре ГА с ценой v. 1. Пусть K(x,y) – математическое ожидание выигрыша в игре ГА с ценой v. Тогда, для того чтобы элемент был оптимальной стратегией 1-го игрока, необходимо и достаточно, чтобы для каждого элемента выполнялось неравенство Аналогично, для того чтобы был оптимальной стратегией 2-го игрока, необходимо и достаточно, чтобы для каждого выполнялось неравенство

Слайд 27

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

2. Пусть K(x,y) – математическое ожидание выигрыша в игре ГА, 2. Пусть K(x,y) – математическое ожидание выигрыша в игре ГА, v – действительное число, , . Тогда, для того чтобы v было ценой игры, а x* и y* были оптимальными стратегиями соответственно 1-го и 2-го игроков, необходимо и достаточно, чтобы для любых и выполнялось неравенство

Слайд 28

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

3. Если x*, y* – решение -игры ГА, то 3. Если x*, y* – решение -игры ГА, то

Слайд 29

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

4. Пусть , , v – решение игры ГА. 4. Пусть , , v – решение игры ГА. Тогда для любого , при котором , выполняется неравенство xi=0, а для любого , при котором , выполняется неравенство yj=0.

Слайд 30

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

5. (Лемма о масштабе). 5. (Лемма о масштабе). Если ГА – игра с матрицей , а – игра с матрицей , где , где α,=const, α>0, то множества оптимальных стратегий игроков в играх ГА и совпадают, а . Иначе говоря, две игры, отличающиеся лишь началом отсчета выигрышей и масштабом их измерения, стратегически эквивалентны.

Слайд 31

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

2. ( ) - игры 2. ( ) - игры

Слайд 32

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

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

Слайд 33

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

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

Слайд 34

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

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

Слайд 35

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

3) в матричном виде: 3) в матричном виде: где – определитель матрицы А, А* – присоединенная к А матрица (транспонированная матрица из алгебраических дополнений), , , , JT и yT – транспонированные матрицы J и y.