– М., 1998.
2. Воробьев Н.Н. Теория игр для экономистов-кибернетиков.
– М.: Наука, 1985.3. Дюбин Г.Н., Суздаль В.Г. Введение в прикладную теорию игр.– М.: Наука, 1981.
- Главная
- Разное
- Бизнес и предпринимательство
- Образование
- Развлечения
- Государство
- Спорт
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Религиоведение
- Черчение
- Физкультура
- ИЗО
- Психология
- Социология
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Что такое findslide.org?
FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.
Обратная связь
Email: Нажмите что бы посмотреть
Презентация на тему ТЕОРИЯ ИГР
Содержание
- 2. ЛитератураПетросян Л.А., Зенкевич Н.А., Семина Е.А. Теория
- 3. 1. Основные понятия теории матричных игр
- 4. Теория игр – это совокупность математических методов анализа и оценки конфликтных ситуаций.
- 5. Содержание теории игр: установление принципов оптимального поведения
- 6. Моделями теории игр можно описать экономические, правовые,
- 7. Игры можно классифицировать по различным признакам: стратегические
- 8. Рассмотрим простейшую модель – игру, в которой
- 9. Такую игру (Г ) называют матричной. Она
- 10. Пусть 1-й игрок имеет всего m стратегий,
- 11. Пусть
- 12. Второй игрок, выбрав стратегию j, в худшем
- 13. Схема:
- 14. Например, Соответствующие стратегии: i0=1(максиминная), j0=1,2 (минимаксная).
- 15. Справедливо неравенство:
- 16. Ситуация (i*, j*) называется ситуацией равновесия, или
- 17. Ситуация равновесия существует тогда и только тогда,
- 18. Например,(2,3)-ситуация равновесная, v =4 – цена игры,
- 19. Смешанной стратегией для 1-го игрока называется упорядоченная
- 20. Функция выигрыша K(x,y) в ситуации (x,y) определяется
- 21. Если для некоторых
- 22. Свойства оптимальных стратегий.
- 23. 1. Пусть K(x,y) – математическое ожидание выигрыша
- 24. 2. Пусть K(x,y) – математическое ожидание выигрыша
- 25. 3. Пусть K(x,y) – математическое ожидание выигрыша
- 26. 4. Если x*, y* – решение -игры ГА, то
- 27. 5. Пусть
- 28. 6 (Лемма о масштабе). Если ГА –
- 29. 2. ( ) - игры
- 30. Пусть
- 31. 1) решив две системы:
- 32. 2) по формулам:илиили
- 33. 3) в матричном виде:где
- 34. Найдем, например, решение игры с платежной
- 35. 1) Составим системы:Решив системы, получим:то есть
- 36. 2) Найдем решение по формулам:
- 37. 3) Найдем решение в матричном виде:
- 38. 3. и – игры
- 39. Рассмотрим игру с платежной матрицей
- 40. Если 1-й игрок применит смешанную стратегию
- 41. Аналогично при выборе 2-м игроком чистых стратегий
- 43. Точка A является точкой пересечения прямых (2)
- 44. По формулам решения – игры получим:
- 45. Тогда решение исходной игры имеет вид
- 46. Аналогично решаются
- 49. Точка B является точкой пересечения прямых (2) и (3). Найдем решение игры
- 50. Тогда решение исходной игры:
- 51. Пусть платежная матрица игры (3)x0x2(2)(1)Рис.31BAx1
- 52. A – точка пересечения прямых (2) и (3), ее абсциссу найдем, решая игру
- 53. B – точка пересечения прямых (1) и (2), ее абсциссу найдем, решая игру
- 54. Решение исходной игры:
- 55. 4. Доминирование стратегий
- 56. Иногда на основании простого рассмотрения матрицы игры
- 57. В результате вместо игры ГА с матрицей
- 58. Легко найти решение игры Можно предположить, что решение игры ГА будет иметь вид:
- 59. Говорят, что i-я стратегия 1-го игрока доминирует
- 60. Говорят, что j-я стратегия 2-го игрока доминирует
- 61. Стратегия может доминироваться также выпуклой линейной комбинацией
- 62. Если
- 63. теорема: пусть ГА –
- 64. 5. Множество решений матричной игры
- 65. Чтобы найти множество всех решений игры с
- 66. Множество всех решений каждого игрока является выпуклой линейной комбинацией найденных решений.
- 67. Решение игры, заданной квадратной подматрицей В, можно найти в матричном виде по формулам
- 68. Найдем, например, множество всех решений игры ГА с платежной матрицей
- 69. Подматрицы не дадут
- 70. Для В: является решением игры ГА (убеждаемся в этом проверкой).
- 71. Для С: – является решением игры
- 72. Таким образом, в игре ГА 1-й игрок
- 73. 6. Сведение матричной игры к двойственной задаче линейного программирования
- 74. Пусть матрица игры имеет вид K=K(x,y)– функция
- 75. Тогда по свойству 2 оптимальных стратегий для
- 76. То есть
- 78. Пример. Найти решение игры с матрицей
- 79. Решение. Перейдем к положительной матрице, прибавив 3 ко всем элементам матрицы А:
- 80. Составим двойственную задачу линейного программирования:
- 81. Решим задачу симплексным методом
- 86. Получаем решение двойственной задачи:
- 87. Тогда решение игры с матрицейРешение исходной игры:
- 88. 7. Приближенное решение матричных игр
- 89. где v – цена игры, k– номер
- 90. За приближенные оптимальные стратегии игроков принимают векторы, координатами которых являются относительные частоты выбора соответствующих чистых стратегий.
- 91. Пример. Найти приближенное решение игры, заданной матрицей
- 94. Скачать презентацию
- 95. Похожие презентации
ЛитератураПетросян Л.А., Зенкевич Н.А., Семина Е.А. Теория игр. – М., 1998.2. Воробьев Н.Н. Теория игр для экономистов-кибернетиков. – М.: Наука, 1985.3. Дюбин Г.Н., Суздаль В.Г. Введение в прикладную теорию игр.– М.: Наука, 1981.
Слайд 2
Литература
Петросян Л.А., Зенкевич Н.А., Семина Е.А. Теория игр.
– М., 1998.
– М.: Наука, 1985.3. Дюбин Г.Н., Суздаль В.Г. Введение в прикладную теорию игр.– М.: Наука, 1981.
Слайд 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-го игрока называется минимаксной.
Слайд 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 – решением игры.
Слайд 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-го игрока, необходимо и достаточно, чтобы для каждого
выполнялось неравенство .
Слайд 27 5. Пусть
,
, v – решение игры ГА.Тогда для любого , при котором
, выполняется неравенство xi=0, а для любого , при котором , выполняется неравенство yj=0.
Слайд 28
6 (Лемма о масштабе).
Если ГА – игра
с матрицей
, а – игра с матрицей , где , где α,β=const, α>0, то множества оптимальных стратегий игроков в играх ГА и совпадают, а .Иначе говоря, две игры, отличающиеся лишь началом отсчета выигрышей и масштабом их измерения, стратегически эквивалентны.
Слайд 30
Пусть
– платежная матрица
игры Г.Если она не имеет седловой точки, то единственное решение игры Г можно найти
Слайд 33
3) в матричном виде:
где –
определитель матрицы А,
А* – присоединенная к А матрица,
, , , JT и yT – транспонированные матрицы J и y.
Слайд 43 Точка A является точкой пересечения прямых (2) и
(3), поэтому решение исходной игры можно найти, решив игру
Слайд 45
Тогда решение исходной игры имеет вид
(номерам
столбцов, не вошедших в матрицу , соответствуют
нулевыекоординаты вектора ), .
Слайд 46 Аналогично решаются
- игры.
Пусть, например,
, – смешанная стратегия 2-го игрока, 1-й игрок выбирает чистые стратегии i=1,2,3.
Слайд 54
Решение исходной игры:
, где
, ,то есть 1-й игрок имеет множество оптимальных стратегий,
2-й игрок – единственную оптимальную стратегию, это чистая стратегия j=2.
Слайд 56 Иногда на основании простого рассмотрения матрицы игры можно
сказать, что некоторые чистые стратегии могут войти в оптимальную
смешанную стратегию лишь с нулевой вероятностью.
Слайд 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-го игрока в игре ,
то – его оптимальная стратегия в игре ГА.
Аналогичная теорема имеет место для доминируемого столбца.
Слайд 65
Чтобы найти множество всех решений игры с платежной
матрицей А, нужно рассмотреть все квадратные подматрицы матрицы А.
Найдя решения игр, заданных подматрицами, нужно составить их расширения на соответствующих местах и проверить, являются ли полученные стратегии оптимальными для игры ГА.
Слайд 66 Множество всех решений каждого игрока является выпуклой линейной
комбинацией найденных решений.
Слайд 69 Подматрицы не дадут решений,
так как матрица А не имеет седловых точек. Рассмотрим
подматрицы :
Слайд 72 Таким образом, в игре ГА 1-й игрок имеет
единственную оптимальную стратегию
2-й игрок имеет множество оптимальных
стратегий
где , , цена игры v=1.
Слайд 89
где v – цена игры,
k– номер партии,
– максимальное значение суммарного выигрыша
1-го игрока в k-ой партии при выборе различных стратегий, – минимальное значение суммарного проигрыша 2-го игрока в k-ой партии при выборе различных стратегий.
Слайд 90 За приближенные оптимальные стратегии игроков принимают векторы, координатами
