Презентация на тему "ТЕОРИЯ ИГР"

Скачать презентацию (0.56 Мб)
103 загрузки
4.5 оценка

Включить эффекты

1 из 94

ВКонтакте Одноклассники Мой Мир Телеграм

Ваша оценка презентации

Оцените презентацию по шкале от 1 до 5 баллов

4.5

2 оценки

Аннотация к презентации

Посмотреть презентацию на тему "ТЕОРИЯ ИГР" в режиме онлайн с анимацией. Содержит 94 слайда. Самый большой каталог качественных презентаций по математике в рунете. Если не понравится материал, просто поставьте плохую оценку.

Формат

pptx (powerpoint)
Количество слайдов

94
Слова

математика
Конспект

Отсутствует

Содержание

Слайд 1
ТЕОРИЯ ИГР
Слайд 2

Литература Петросян Л.А., Зенкевич Н.А., Семина Е.А. Теория игр. – М., 1998. 2. Воробьев Н.Н. Теория игр для экономистов-кибернетиков. – М.: Наука, 1985. 3. Дюбин Г.Н., Суздаль В.Г. Введение в прикладную теорию игр.– М.: Наука, 1981.
Слайд 3

1. Основные понятия теории матричных игр
Слайд 4

Теория игр – это совокупность математических методов анализа и оценки конфликтных ситуаций.
Слайд 5

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

Моделями теории игр можно описать экономические, правовые, классовые, военные конфликты, взаимодействие человека с природой. Все такие модели в теории игр принято называть играми.
Слайд 7

Игры можно классифицировать по различным признакам: стратегические и чисто случайные, бескоалиционные и коалиционные, игры 1, 2, …, n лиц (по числу игроков), конечные и бесконечные (по числу стратегий), игры в нормальной форме и динамические, с нулевой суммой («антагонистические») и с ненулевой суммой.
Слайд 8

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

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

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

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

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

Схема:
Слайд 14

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

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

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

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

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

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

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

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

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

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

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

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

4. Если x*, y* – решение -игры ГА, то
Слайд 27

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

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

2. ( ) - игры
Слайд 30

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

1) решив две системы:
Слайд 32

2) по формулам: или или
Слайд 33

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

Найдем, например, решение игры с платежной матрицей , которая не имеет седловой точки.
Слайд 35

1)Составим системы: Решив системы, получим: то есть -решение игры.
Слайд 36

2) Найдем решение по формулам:
Слайд 37

3) Найдем решение в матричном виде:
Слайд 38

3. и – игры
Слайд 39

Рассмотрим игру с платежной матрицей
Слайд 40

Если 1-й игрок применит смешанную стратегию , а 2-й игрок – чистую стратегию , то .(1)
Слайд 41

Аналогично при выборе 2-м игроком чистых стратегий , , (2) (3) (4)
Слайд 42

1 A Рис.1 (1) x 0 x (3) (2) (4)
Слайд 43

Точка A является точкой пересечения прямых (2) и (3), поэтому решение исходной игры можно найти, решив игру
Слайд 44

По формулам решения – игры получим:
Слайд 45

Тогда решение исходной игры имеет вид (номерам столбцов, не вошедших в матрицу , соответствуют нулевые координаты вектора ), .
Слайд 46

Аналогично решаются - игры. Пусть, например, , – смешанная стратегия 2-го игрока, 1-й игрок выбирает чистые стратегии i=1,2,3.
Слайд 47

(1) (2) (3)
Слайд 48

(1) y 0 y (3) (2) 1 B Рис.2
Слайд 49

Точка B является точкой пересечения прямых (2) и (3). Найдем решение игры
Слайд 50

Тогда решение исходной игры:
Слайд 51

Пусть платежная матрица игры (3) x 0 x2 (2) (1) Рис.3 1 B A x1
Слайд 52

A – точка пересечения прямых (2) и (3), ее абсциссу найдем, решая игру
Слайд 53

B– точка пересечения прямых (1) и (2), ее абсциссу найдем, решая игру
Слайд 54

Решение исходной игры: , где , , то есть 1-й игрок имеет множество оптимальных стратегий, 2-й игрок – единственную оптимальную стратегию, это чистая стратегия j=2.
Слайд 55

4. Доминирование стратегий
Слайд 56

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

В результате вместо игры ГА с матрицей А можно рассмотреть игру с матрицей
Слайд 58

Легко найти решение игры Можно предположить, что решение игры ГА будет иметь вид:
Слайд 59

Говорят, что i-я стратегия 1-го игрока доминирует его k-ю стратегию, если для всех и хотя бы для одного j . В этом случае говорят также, что i-я стратегия (или строка) – доминирующая, k-я – доминируемая.
Слайд 60

Говорят, что j-я стратегия 2-го игрока доминирует его l-ю стратегию, если для всех и хотя бы для одного i В этом случае j-ю стратегию (столбец) называют доминирующей, l-ю – доминируемой.
Слайд 61

Стратегия может доминироваться также выпуклой линейной комбинацией других стратегий. Так, i-я стратегия 1-го игрока доминируется выпуклой линейной комбинацией остальных стратегий, если ; j-я стратегия 2-го игрока доминируется выпуклой линейной комбинацией остальных стратегий, если
Слайд 62

Если – некоторая смешанная стратегия, то ее расширением на i-ом месте будем называть стратегию вида
Слайд 63

теорема: пусть ГА – -игра, в которой i-я строка доминируема, – игра с матрицей , полученной из А вычеркиванием i-ой строки. Тогда 1) ; 2) всякая оптимальная стратегия 2-го игрока в игре является оптимальной и в игре ГА; 3) если x* – оптимальная стратегия 1-го игрока в игре , то – его оптимальная стратегия в игре ГА. Аналогичная теорема имеет место для доминируемого столбца.
Слайд 64

5. Множество решений матричной игры
Слайд 65

Чтобы найти множество всех решений игры с платежной матрицей А, нужно рассмотреть все квадратные подматрицы матрицы А. Найдя решения игр, заданных подматрицами, нужно составить их расширения на соответствующих местах и проверить, являются ли полученные стратегии оптимальными для игры ГА.
Слайд 66

Множество всех решений каждого игрока является выпуклой линейной комбинацией найденных решений.
Слайд 67

Решение игры, заданной квадратной подматрицей В, можно найти в матричном виде по формулам
Слайд 68

Найдем, например, множество всех решений игры ГА с платежной матрицей
Слайд 69

Подматрицы не дадут решений, так как матрица А не имеет седловых точек. Рассмотрим подматрицы :
Слайд 70

Для В: является решением игры ГА (убеждаемся в этом проверкой).
Слайд 71

Для С: – является решением игры ГА. Для D получим такое же решение, как для В.
Слайд 72

Таким образом, в игре ГА 1-й игрок имеет единственную оптимальную стратегию 2-й игрок имеет множество оптимальных стратегий где , , цена игры v=1.
Слайд 73

6. Сведение матричной игры к двойственной задаче линейного программирования
Слайд 74

Пусть матрица игры имеет вид K=K(x,y)– функция выигрыша, , , .
Слайд 75

Тогда по свойству 2 оптимальных стратегий для любых , должно выполняться условие
Слайд 76

То есть
Слайд 77
Слайд 78

Пример. Найти решение игры с матрицей
Слайд 79

Решение. Перейдем к положительной матрице, прибавив 3 ко всем элементам матрицы А:
Слайд 80

Составим двойственную задачу линейного программирования:
Слайд 81

Решим задачу симплексным методом
Слайд 82
Слайд 83
Слайд 84
Слайд 85
Слайд 86

Получаем решение двойственной задачи:
Слайд 87

Тогда решение игры с матрицей Решение исходной игры:
Слайд 88

7. Приближенное решение матричных игр
Слайд 89

где v – цена игры, k– номер партии, – максимальное значение суммарного выигрыша 1-го игрока в k-ой партии при выборе различных стратегий, – минимальное значение суммарного проигрыша 2-го игрока в k-ой партии при выборе различных стратегий.
Слайд 90

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

Пример. Найти приближенное решение игры, заданной матрицей
Слайд 92
Слайд 93
Слайд 94

Приближенное решение игры за 12 партий: v =1,45, ; ,