Игровые аспекты принятия решений

Сентябрь 7, 2022

Главная
Алгебра
Игровые аспекты принятия решений

Содержание

2. Содержание Текущий контроль Часть 1. Общие положения теории игр и их классификация. Часть 2. Примеры игр.
3. Текущий контроль Прогнозировать результаты голосования с помощью дерева вариантов, если число голосов каждой коалиции определяется номером
4. Часть 1 Общие положения теории игр и их классификация
5. Основные компоненты любой игры конфликт; принятие решения; оптимальность решения.
6. Характеризующие игру элементы чередование либо одновременность ходов, которые могут быть, как логичными, так и случайными; возможная
7. Классификация игр Матричные и позиционные; Антагонистические и неантагонистические; С полной и неполной информацией; Игры двух и
8. Часть 2 Примеры игр
9. Антагонистические и неантагонистические игры Антагонистическая игра: матричная игра с полной информацией и нулевой суммой Неантагонистическая игра:
10. Теорема о предательстве Игрок вступивший в коалицию и нарушивший ее рискует проиграть все.
11. Дилемма заключенного Каждому из двух заключенных, обвиняемых в одном преступлении, предлагается на выбор три альтернативы: Признать
12. Матричные антагонистические игры двух лиц с нулевой суммой и полной информацией Игра определяется матрицей М, строки
13. Часть 3 Эквивалентные преобразования игр
14. Доминирующая и доминируемая стратегии Стратегии i и j называются соответственно доминирующей и доминируемой, если каждый элемент
15. Пример 1 5 Вопрос: влияет ли на цену игры изменение порядка отбрасывания доминируемых стратегий ?
16. Самостоятельно Отбросить доминируемые стратегии в игре, заданной матрицей М: М =
17. Часть 4 Поиск решения игры в чистых стратегиях
18. Равновесные стратегии Ситуация (пара стратегий) называется равновесной, если соответствующий ей элемент матрицы игры является одновременно наибольшим
19. Пример 2 - Седловая точка
20. Самостоятельно Определить оптимальную стратегию преподавателя, определяемую седловой точкой в антагонистической игре двух лиц, заданной матрицей М
21. Гарантирующие стратегии Гарантирующие стратегии применяются в играх с полной информацией, когда отсутствует седловая точка. Применительно к
22. Пример 3 Желтым цветом выделены гарантирующие стратегии игроков. Цена игры при использовании гарантирующих стратегий равна семи
23. Самостоятельно Формально определить гарантирующие стратегии игроков. Чем гарантирующие стратегии отличаются от равновесных? Определить гарантирующие стратегии игроков
24. Часть 5 Поиск решения игры в смешанных стратегиях
25. Смешанные стратегии Игры с полной информацией, т.е. такие, в которых каждый игрок знает возможности и “наклонности”
26. Формальная постановка задачи поиска оптимальной смешанной стратегии Пусть - вероятность выбора i –ой стратегии одним игроком,
27. Теорема о минимаксе Справедлива теорема о минимаксе, в некотором смысле аналогичная теореме о седловой точке для
28. Метод Брауна-Робинсона Идея метода заключается в том, что игра разыгрывается много раз, причем при каждом разыгрывании
29. Алгоритм Брауна-Робинсона Шаг 1. Ввод матрицы игры «а» и точности Ɛ. Шаг 2. Шаг 3. Шаг
30. Алгоритм Брауна-Робинсона (продолжение) Шаг 8. ха=ха+1. Шаг 9. yв=yв+1. Шаг 10. Вычисляется новая цена игры V1
31. Пример 3 Решить игру, заданную матрицей а точностью Ɛ: а = Ɛ = 0,1.
32. Решение 1. 2. 3. V₀ =8,33(3) . 4. D = 33, A = 3. 5. C
34. Скачать презентацию

Слайд 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
5
Вопрос: влияет ли на цену игры изменение порядка отбрасывания

доминируемых стратегий ?

Слайд 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.

Игровые аспекты принятия решений

Содержание

СодержаниеТекущий контрольЧасть 1. Общие положения теории игр и их классификация.Часть 2.

Текущий контрольПрогнозировать результаты голосования с помощью дерева вариантов, если число голосов

Часть 1Общие положения теории игр и их классификация

Основные компоненты любой игры конфликт; принятие решения; оптимальность решения.

Характеризующие игру элементычередование либо одновременность ходов, которые могут быть, как логичными,

Классификация игрМатричные и позиционные;Антагонистические и неантагонистические;С полной и неполной информацией;Игры двух

Часть 2Примеры игр

Антагонистические и неантагонистические игрыАнтагонистическая игра: матричная игра с полной информацией и

Теорема о предательствеИгрок вступивший в коалицию и нарушивший ее рискует проиграть

Дилемма заключенногоКаждому из двух заключенных, обвиняемых в одном преступлении, предлагается на

Матричные антагонистические игры двух лиц с нулевой суммой и полной информацией Игра

Часть 3Эквивалентные преобразования игр

Доминирующая и доминируемая стратегииСтратегии i и j называются соответственно доминирующей и

Пример 1 5Вопрос: влияет ли на цену игры изменение порядка отбрасывания

СамостоятельноОтбросить доминируемые стратегии в игре, заданной матрицей М:М =

Часть 4Поиск решения игры в чистых стратегиях

Равновесные стратегииСитуация (пара стратегий) называется равновесной, если соответствующий ей элемент матрицы

Пример 2- Седловая точка

СамостоятельноОпределить оптимальную стратегию преподавателя, определяемую седловой точкой в антагонистической игре двух

Гарантирующие стратегииГарантирующие стратегии применяются в играх с полной информацией, когда отсутствует

Пример 3Желтым цветом выделены гарантирующие стратегии игроков.Цена игры при использовании гарантирующих

СамостоятельноФормально определить гарантирующие стратегии игроков.Чем гарантирующие стратегии отличаются от равновесных?Определить гарантирующие

Часть 5Поиск решения игры в смешанных стратегиях

Смешанные стратегииИгры с полной информацией, т.е. такие, в которых каждый игрок

Формальная постановка задачи поиска оптимальной смешанной стратегииПусть - вероятность выбора i

Теорема о минимаксеСправедлива теорема о минимаксе, в некотором смысле аналогичная теореме

Метод Брауна-РобинсонаИдея метода заключается в том, что игра разыгрывается много раз,

Алгоритм Брауна-РобинсонаШаг 1. Ввод матрицы игры «а» и точности Ɛ.Шаг 2.

Алгоритм Брауна-Робинсона (продолжение)Шаг 8. ха=ха+1.Шаг 9. yв=yв+1.Шаг 10. Вычисляется новая цена

Пример 3Решить игру, заданную матрицей а точностью Ɛ:а =Ɛ = 0,1.

Решение1.2.3. V₀ =8,33(3) . 4. D = 33, A = 3.5.

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