Оцените презентацию от 1 до 5 баллов!
Тип файла:
ppt / pptx (powerpoint)
Всего слайдов:
33 слайда
Для класса:
1,2,3,4,5,6,7,8,9,10,11
Размер файла:
154.17 kB
Просмотров:
56
Скачиваний:
0
Автор:
неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: Игровые аспекты принятия решений
Лекция 7
№2 слайд
Содержание слайда: Содержание
Текущий контроль
Часть 1. Общие положения теории игр и их классификация.
Часть 2. Примеры игр.
Часть 3. Эквивалентные преобразования игр.
Часть 4. Поиск решения игр в чистых стратегиях.
Часть 5. Поиск решения игр в смешанных стратегиях (алгоритм Брауна-Робинсона).
№3 слайд
Содержание слайда: Текущий контроль
Прогнозировать результаты голосования с помощью дерева вариантов, если число голосов каждой коалиции определяется номером студента k.
№4 слайд
Содержание слайда: Часть 1
Общие положения теории игр и их классификация
№5 слайд
Содержание слайда: Основные компоненты любой игры
конфликт;
принятие решения;
оптимальность решения.
№6 слайд
Содержание слайда: Характеризующие игру элементы
чередование либо одновременность ходов, которые могут быть, как логичными, так и случайными;
возможная недостаточность информации;
функция выигрыша, определяющая цену игры.
№7 слайд
Содержание слайда: Классификация игр
Матричные и позиционные;
Антагонистические и неантагонистические;
С полной и неполной информацией;
Игры двух и более лиц;
Игры с коалициями и без них;
Игры в чистых и смешанных стратегиях;
Игры с нулевой и произвольной суммой;
Игры с седловой точкой и без нее;
Конечные и бесконечные игры…
№8 слайд
Содержание слайда: Часть 2
Примеры игр
№9 слайд
Содержание слайда: Антагонистические и неантагонистические игры
Антагонистическая игра: матричная игра с полной информацией и нулевой суммой
Неантагонистическая игра: первый игрок выбирает наилучшую для себя стратегию, второй –выбирает ее случайно.
«Игра с болваном»: первый игрок выбирает наилучшую для себя стратегию, второй действует в интересах первого игрока.
№10 слайд
Содержание слайда: Теорема о предательстве
Игрок вступивший в коалицию и нарушивший ее рискует проиграть все.
№11 слайд
Содержание слайда: Дилемма заключенного
Каждому из двух заключенных, обвиняемых в одном преступлении, предлагается на выбор три альтернативы:
Признать вину – тогда он получит срок t лет, а другой заключенный выйдет на свободу.
Не признавать вину, тогда ему грозит срок Т лет.
Обвинить в преступлении другого заключенного, тогда обвинивший будет выпущен на свободу, а другой заключенный получит срок Т лет.
№12 слайд
Содержание слайда: Матричные антагонистические игры двух лиц с нулевой суммой и полной информацией
Игра определяется матрицей М, строки которой соответствуют стратегиям максимизирующего игрока, а столбцы – минимизирующего:
М =
№13 слайд
Содержание слайда: Часть 3
Эквивалентные преобразования игр
№14 слайд
Содержание слайда: Доминирующая и доминируемая стратегии
Стратегии i и j называются соответственно доминирующей и доминируемой, если каждый элемент i-ой стратегии “лучше” одноименного элемента j-ой стратегии. Это позволяет игнорировать доминируемые стратегии и, таким образом, облегчить поиск оптимальных стратегий игроков.
№15 слайд
Содержание слайда: Пример 1
№16 слайд
Содержание слайда: Самостоятельно
Отбросить доминируемые стратегии в игре, заданной матрицей М:
М =
№17 слайд
Содержание слайда: Часть 4
Поиск решения игры в чистых стратегиях
№18 слайд
Содержание слайда: Равновесные стратегии
Ситуация (пара стратегий) называется равновесной, если соответствующий ей элемент матрицы игры является одновременно наибольшим в своем столбце и наименьшим в своей строке.
№19 слайд
Содержание слайда: Пример 2
№20 слайд
Содержание слайда: Самостоятельно
Определить оптимальную стратегию преподавателя, определяемую седловой точкой в антагонистической игре двух лиц, заданной матрицей М (столбцы отвечают студентам, строки – стратегиям преподавателя):
М =
№21 слайд
Содержание слайда: Гарантирующие стратегии
Гарантирующие стратегии применяются в играх с полной информацией, когда отсутствует седловая точка.
Применительно к каждому игроку гарантирующей является стратегия, обеспечивающая ему лучшую цену игры из худших.
№22 слайд
Содержание слайда: Пример 3
№23 слайд
Содержание слайда: Самостоятельно
Формально определить гарантирующие стратегии игроков.
Чем гарантирующие стратегии отличаются от равновесных?
Определить гарантирующие стратегии игроков и цену игры, заданной матрицей М:
М =
Отбросить в М доминируемые стратегии.
№24 слайд
Содержание слайда: Часть 5
Поиск решения игры в смешанных стратегиях
№25 слайд
Содержание слайда: Смешанные стратегии
Игры с полной информацией, т.е. такие, в которых каждый игрок знает возможности и “наклонности” противника, реализуются, как в чистых, так и в смешанных стратегиях. В первом случае каждый игрок в ходе игры может придерживаться только одной, выбранной им стратегии, а во втором – нескольких стратегий, применительно к которым фиксируются лишь вероятности их выбора. Цель многоходовой антагонистической матричной игры с полной информацией состоит в определении оптимальных вероятностей выбора стратегий каждым из игроков.
№26 слайд
Содержание слайда: Формальная постановка задачи поиска оптимальной смешанной стратегии
Пусть - вероятность выбора i –ой стратегии одним игроком, а - вероятность выбора j –ой стратегии другим игроком. Цена игры V(Г) при фиксированных стратегиях и равна:
№27 слайд
Содержание слайда: Теорема о минимаксе
Справедлива теорема о минимаксе, в некотором смысле аналогичная теореме о седловой точке для матричной игры в чистых стратегиях:
№28 слайд
Содержание слайда: Метод Брауна-Робинсона
Идея метода заключается в том, что игра разыгрывается много раз, причем при каждом разыгрывании каждый игрок фиксирует эмпирические вероятности стратегий противника: если II игрок использовал j –ю стратегию qi раз, то игрок I выбирает i так, чтобы максимизировать . Аналогично, если игрок I использовал i –ую стратегию pi раз, то игрок II выбирает j так, чтобы минимизировать .
Доказано, что с ростом числа разыгрываний эмпирические распределения сходятся к оптимальным стратегиям.
№29 слайд
Содержание слайда: Алгоритм Брауна-Робинсона
Шаг 1. Ввод матрицы игры «а» и точности Ɛ.
Шаг 2.
Шаг 3.
Шаг 4. Определяется цена игры
Шаг 5. S= ∞.
Шаг 6. Выбор такого i, для которого сумма D=
максимальна (i=A).
Шаг 7. Выбор такого j=B, для которого сумма С =
минимальна.
№30 слайд
Содержание слайда: Алгоритм Брауна-Робинсона (продолжение)
Шаг 8. ха=ха+1.
Шаг 9. yв=yв+1.
Шаг 10. Вычисляется новая цена игры V1 :
Шаг 11. Если , то перейти к шагу 14, в противном случае – к шагу 12.
Шаг 12. V0=V1
Шаг 13. Перейти к шагу 6.
Шаг 14. Конец алгоритма, печать векторов Х и У.
№31 слайд
Содержание слайда: Пример 3
Решить игру, заданную матрицей а точностью Ɛ:
а =
Ɛ = 0,1.
№32 слайд
Содержание слайда: Решение
1.
2.
3. V₀ =8,33(3) .
4. D = 33, A = 3.
5. C = 19, B = 2.
6. x₃ =2, x₁ = x₂ = 1.
7. y₂ = 2, y₁ = y₃ = 1.
8. V₁ = 8,25.
9. Т. к. , алгоритм закончен. Ответ:
p₁ =p₂=0,25; p₃=0,5; q₁=q₃=0,25; q₂=0,5, V=8,25.
№33 слайд
Содержание слайда: Самостоятельно
Определить достоинства и недостатки метода Брауна-Робинсона.
Решить игру с матрицей а и точностью Ɛ=0,1:
а =