🗊Презентация Теория игр и принятие решений

Учебные вопросы: 1. Предмет и задачи теории игр. 2. Матричные игры. Равновесная ситуация. 3. Смешанные стратегии матричных игр. 4. Игры с природой.

1. Предмет и задачи теории игр.

1. Предмет и задачи теории игр.

2. Матричные игры: Пусть в игре участвуют два игрока. Игрок А имеет m стратегий, а игрок В – n стратегий. Обозначим стратегии игрока А как А1,А2,…,Аm , а стратегии игрока В – как В1 ,В2 …,Вn . Если игрок А выбрал стратегию Ai , а игрок B – стратегию Bk , то выигрыш игрока A составит аik , а игрока B – bik , причем аik = - bik (1)

2. Матричные игры: Поэтому при анализе такой игры достаточно рассмотреть выигрыш только одного игрока, например выигрыш аik игрока А. Зная выигрыш аik по формуле (1) легко определить выигрыш bik . Матричные игры называются парными играми с нулевой суммой, в которых выигрыш одного игрока равен проигрышу другого. Если известны все значения аik для каждой пары стратегий {Ai Bk }, i =1, 2, …, m, k = 1, 2, …, n, то их удобно записать в виде прямоугольной таблицы, строки которой соответствуют стратегиям игрока A , а столбцы – стратегиям игрока В (табл. 1).

2. Матричные игры:

2. Матричные игры: Равновесная ситуация Пусть матричная игра m×n задана платежной матрицей A = (2) Строки этой матрицы соответствуют стратегиям игрока , а столбцы – стратегиям игрока . В теории игр предполагается, что оба игрока действуют разумно, т.е. стремятся к получению максимального выигрыша, считая, что соперник действует наилучшим для себя образом.

2. Матричные игры: Определим оптимальные стратегии каждого из игроков. Начнем с анализа стратегий игрока А . На стратегию Аi игрока A игрок B ответит такой стратегией Bk, при которой выигрыш игрока A будет минимальным. Аналогично игрок B будет отвечать на все m стратегий игрока A . Другими словами, найдем в каждой строке матрицы минимальный элемент (минимальные выигрыши игрока A) и запишем их в правом столбце табл. 2.

2. Матричные игры:

2. Матричные игры: Принцип построения стратегии игрока А, основанный на максимизации минимальных выигрышей, называется принципом максимина (maxmin). Проведем анализ стратегий игрока В. Для этого найдем в каждом столбце матрицы максимальный элемент (максимальные выигрыши игрока А ): И запишем их в нижней строке табл. 2. Действуя разумно, игрок B остановится на той стратегии , для которой выбираем минимальное число (4) Число β называется верхней ценой игры.

2. Матричные игры: Принцип построения стратегии игрока B, основанный на минимизации максимальных выигрышей, называется принципом минимакса (minmax). Нижняя цена игра α и верхняя цена игра β связаны неравенством α ≤ β. (5) Если или (6) то ситуация оказывается равновесной, и ни один игрок не заинтересован в том, чтобы ее нарушить. В том случае, когда верхняя цена игры равна нижней, их называют просто ценой игры. Если α=β, то такую игру называют также игрой с седловой точкой, а пара оптимальных стратегий – седловой точкой матрицы. Цена игры обозначается буквой v. Тогда .

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

3. Смешанные стратегии матричных игр

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

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

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

3. Смешанные стратегии матричных игр Поэтому выигрыш игрока А (проигрыш игрока В) определяют его математическим ожиданием, рассчитываемым по формуле (10) Функция (10) называется платежной функцией игры с матрицей, заданной в табл. 5. Нижней ценой игры называется число , рассчитываемое по формуле: (11) Верхней ценой игры называется число , рассчитываемое по формуле: (12)

3. Смешанные стратегии матричных игр

3. Смешанные стратегии матричных игр Величину определенную соотношением (13), называют ценой игры.

3. Смешанные стратегии матричных игр

3. Смешанные стратегии матричных игр Пусть , - оптимальные смешанные стратегии и - цена игры. Оптимальная смешанная стратегия игрока А складывается только из тех чистых стратегий (т.е. только те вероятности , могут отличаться от нуля), для которых Аналогично, только те вероятности могут отличаться от нуля, для которых

3. Смешанные стратегии матричных игр Графические решения матричных игр Графический метод применим к тем играм, в которых хотя бы один игрок имеет две стратегии. Рассмотрим игру 2×п, представленную в табл. 6. Эта игра не имеет седловой точки. Согласно теореме имеем (15)

3. Смешанные стратегии матричных игр Максимум функции (16) найдем, построив ее график. Для этого поступаем следующим обра­зом. Построим графики прямых для каждого к = 1, 2,..., п в системе координат pOw (рис.1). В соответствии с требованием (16) на каждой из построенных прямых определяются и отмечаются наименьшие значения. На рис. 2 эти значения выделены полужирной ломаной линией. Эта ломаная огибает снизу все семейство построенных прямых и называется нижней огибающей семейства.

3. Смешанные стратегии матричных игр

3. Смешанные стратегии матричных игр

3. Смешанные стратегии матричных игр