Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Стратегические игры
Содержание
- 1. Стратегические игры
- 2. Конфликтные ситуацииСитуации, в которых сталкиваются две или
- 3. Оптимизационные задачи теории игррешение принимает не одно,
- 4. Понятие игрыИгра – упрощенная формализованная модель реальной
- 5. Понятие стратегии игрокаИгрок – одна из сторон
- 6. Классификация игровых задач
- 7. Игра с нулевой суммойконфликт двух участников с
- 8. Понятие матричной игрыМатричная игра – конечная игра
- 9. Платежная матрицаСтратегии первого игрока пронумеруем числами от
- 10. Правила игрыИгра происходит партиями. Партия игры состоит
- 11. Решение игрыРешением игры можно назвать любое описание
- 12. Игра в чистых стратегияхПри анализе игр противник
- 13. Цена игрыЕсли α=β, то говорят, что игра
- 14. Пример В платежной матрицеуказано, какую долю рынка
- 15. Решение Нижняя цена игрысоответствует второй стратегии первого
- 16. Понятие смешанной стратегии игрокаСмешанная стратегия игрока –
- 17. Условия применения смешанных стратегий:игра без седловой точки;игроки
- 18. Игра в смешанных стратегиях. Обозначенияpi – вероятность,
- 19. Игра в смешанных стратегияхЕсли игроки играют со
- 20. Решение игры 2×2 в смешанных стратегияхПусть
- 21. Решение игры 2×2 в смешанных стратегияхЦена игры
- 22. Решение игры 2×2 в смешанных стратегияхЦена игры
- 23. Пример. Игра «Угадывание монеты»Правила игры таковы. Первый
- 24. Решение Платежная матрица имеет видПроверим, есть ли
- 25. Решение в смешанных стратегиях для первого игрока
- 26. Гарантированный выигрыш первого игрока
- 27. Решение в смешанных стратегиях для первого игрокаВторой
- 28. Решение в смешанных стратегиях для второго игрока
- 29. Верхняя граница проигрыша второго игрока
- 30. Решение в смешанных стратегиях для второго игрокаНаилучшее
- 31. Основная теорема теории матричных игрВ любой матричной игре у игроков есть оптимальные смешанные стратегии.
- 32. Решение игры 2×nМатрица игрыСмешанные стратегии игрока 1
- 33. Гарантированный выигрыш игрока 1Строим графики ожидаемых выигрышей
- 34. Пример Решить игру с платежной матрицей
- 35. Решение в чистых стратегиях Нижняя цена игрыВерхняя
- 36. Решение в смешанных стратегиях для первого игрокаПусть
- 37. Гарантированный выигрыш первого игрока
- 38. Оптимальная стратегия первого игрокаИз условия ν1(p) =
- 39. Решение в смешанных стратегиях для первого игрокаВторой
- 40. Оптимальная стратегия второго игрокаИз условия µ1(q) = µ2(q) находим q=7/11.Оптимальная смешанная стратегия второго игрока равна
- 41. Игра m ×n При решении матричной игры
- 42. Доминирующие стратегииГоворят, что стратегия А1 первого игрока
- 43. Основные теоремы теории игрНи одна из строго
- 44. Пример Решить игру, заданную платежной матрицей
- 45. Решение Стратегия А5 дублирует стратегию А2, поэтому
- 46. Решение Стратегия В3 доминирует над В4 и
- 47. Решение матричной игры сведением к задаче линейного
- 48. Постановка задачи линейного программирования для первого игрокаВведем
- 49. Постановка двойственных задач линейного программирования для первого и второго игроков
- 50. Оптимальные смешанные стратегии игроковЦена игрыОптимальные смешанные стратегии игроков
- 51. Замечание Если же в платежной матрице есть
- 52. Пример В условиях предыдущего примера решить игру с платежной матрицей сведением ее к задаче линейного программирования
- 53. Решение с помощью сведения задачи к паре
- 54. Пара двойственных задач линейного программирования
- 55. Оптимальные решения Оптимальные решения задач ЛПОптимальные смешанные стратегии игроковЦена игры
- 56. Скачать презентанцию
Конфликтные ситуацииСитуации, в которых сталкиваются две или более стороны, преследующие различные цели, причем результат, полученный каждой из сторон при реализации определенной стратегии, зависит от действий других сторон, называются конфликтными (борьба фирм
Слайды и текст этой презентации
Слайд 3Оптимизационные задачи теории игр
решение принимает не одно, а два или
более лиц, а результат решения зависит от совокупности решений всех
этих лицкаждому лицу не известны ни решения других лиц, ни вероятностные оценки их возможных решений
Слайд 4Понятие игры
Игра – упрощенная формализованная модель реальной конфликтной ситуации.
Математически
формализация означает, что выработаны определенные правила действия сторон в процессе
игры: варианты действия сторон; исход игры при данном варианте действия; объем информации каждой стороны о поведении всех других сторон.
Слайд 5Понятие стратегии игрока
Игрок – одна из сторон в игровой ситуации.
Стратегия игрока – его правила действия в каждой из возможных
ситуаций игры. 
Слайд 7Игра с нулевой суммой
конфликт двух участников с противоположными интересами, выигрыш
одной стороны конфликта в точности совпадает с проигрышем другой стороны
Участники
игры — лица, принимающие решения, — называются игроками. Целевые функции называются платежными функциями, и считается, что они показывают выигрыш игрока.
Стратегия игрока — это осознанный выбор одного из множества возможных вариантов его действий
Слайд 8Понятие матричной игры
Матричная игра – конечная игра двух игроков с
нулевой суммой. В общем случае ее платежная матрица является прямоугольной
Номер строки матрицы соответствует номеру стратегии, применяемой игроком 1.
Номер столбца соответствует номеру стратегии игрока 2.
Выигрыш игрока 1 является элементом матрицы.
Выигрыш игрока 2 равен проигрышу игрока 1.
Слайд 9Платежная матрица
Стратегии первого игрока пронумеруем числами от 1 до m,
а стратегии второго игрока — числами от 1 до n.
Конечная
игра с нулевой суммой однозначно определяется платежной матрицей (матрицей выигрышей)aij – платеж второго игрока первому
Слайд 10Правила игры
Игра происходит партиями.
Партия игры состоит в том, что
игроки одновременно называют свой выбор: первый игрок называет некоторый номер
строки матрицы П (по своему выбору или случайно), а второй — некоторый номер столбца этой матрицы (также по своему выбору или случайно).После этого происходит «расплата».
Цель каждого игрока — выиграть как можно бóльшую сумму в результате большого числа партий.
Слайд 11Решение игры
Решением игры можно назвать любое описание того, каким образом
должны вести себя игроки в той или иной игровой ситуации.
Стратегия называется чистой, если выбор игрока неизменен от партии к партии. У первого игрока, очевидно, есть m чистых стратегий, а у второго - n.
Решением может быть набор исходов игры.
Решением игры может быть и набор смешанных стратегий, если одних только чистых стратегий недостаточно.
Слайд 12Игра в чистых стратегиях
При анализе игр противник считается сильным, т.е.
разумным.
Нижняя цена игры
представляет собой максимальный гарантированный выигрыш первого игрока. Стратегия 1-го игрока – максиминная.
Верхняя цена игры
представляет собой величину, противоположную минимальному гарантированному проигрышу второго игрока (второй игрок гарантирует, что он не проиграет больше чем β). Стратегия 2-го игрока – минимаксная.
Слайд 13Цена игры
Если α=β, то говорят, что игра имеет седловую точку
в чистых стратегиях.
Общее значение α и β называется при
этом ценой игры и обозначается ν=α=β.Стратегии игроков, соответствующие седловой точке, называются оптимальными чистыми стратегиями.
Теорема. В любой матричной игре нижняя цена не превосходит верхней: α≤β.
Слайд 14Пример
В платежной матрице
указано, какую долю рынка выиграет предприятие у
своего единственного конкурента, если оно будет действовать согласно каждой из
возможных трех стратегий, а конкурент — согласно каждой из своих возможных трех стратегий. Требуется определить, имеет ли данная игра седловую точку в чистых стратегиях. Найти цену игры.
Слайд 15Решение
Нижняя цена игры
соответствует второй стратегии первого игрока.
Верхняя цена
игры
соответствует второй стратегии второго игрока.
Если первый игрок будет действовать со
второй стратегией, а второй игрок — со второй стратегией, то игроки могут гарантировать себе: первый — выигрыш не менее ν=α=β=0,3=30% рынка, а второй — что первый выиграет не более ν=30% рынка
Слайд 16Понятие смешанной стратегии игрока
Смешанная стратегия игрока – это полный набор
применения его чистых стратегий при многократном повторении игры в одних
и тех же условиях с заданными вероятностями.
Слайд 17Условия применения смешанных стратегий:
игра без седловой точки;
игроки используют случайную смесь
чистых стратегий с заданными вероятностями;
игра многократно повторяется в сходных условиях;
при
каждом из ходов ни один игрок не информирован о выборе стратегии другим игроком;допускается осреднение результатов игр.
Слайд 18Игра в смешанных стратегиях. Обозначения
pi – вероятность, с которой первый
игрок выбирает свою i-ю стратегию
qj – вероятность, с которой второй
игрок выбирает свою j-ю стратегиюСмешанной стратегией первого игрока называется вектор где все pi ≥ 0 (i = 1, 2, …, m), а Σ pi = 1, т.е. распределение вероятностей на множестве его чистых стратегий
Смешанной стратегией второго игрока называется вектор где все qj ≥ 0 (j = 1, 2, …, n), а Σ qj = 1,
Слайд 19Игра в смешанных стратегиях
Если игроки играют со своими смешанными стратегиями
p=(p1, p2, …,pm) и q = (q1, q2, …, qn)
соответственно, то математическое ожидание выигрыша первого игрока равно математическому ожиданию проигрыша второго игрокаСтратегии p*=(p*1, p*2, …,p*m) и q* = (q*1, q*2, …, q*n) называются оптимальными смешанными стратегиями соответственно первого и второго игрока, если
Если у обоих игроков есть оптимальные смешанные стратегии, то пара (p*, q*) называется решением игры (или седловой точкой в смешанных стратегиях), а число ν = M(p*, q*) – ценой игры
Слайд 20Решение игры 2×2 в смешанных стратегиях
Пусть
- матрица игры
Пусть (p1, p2) – оптимальная стратегия игрока 1;
(q1, q2) – оптимальная стратегия игрока 2
Тогда, исключая тривиальный случай (наличие чистой оптимальной стратегии хотя бы у одного из игроков), имеем:
p1 + p2 = 1, p1>0, p2>0;
q1 + q2 = 1, q1>0, q2>0;
Слайд 23Пример. Игра «Угадывание монеты»
Правила игры таковы. Первый игрок прячет в
кулаке одну из двух монет: 1 руб. или 5 руб.
по своему выбору и незаметно от второго игрока, а второй игрок пытается угадать, какая монета спрятана, и если угадывает, то получает эту монету, в противном случае платит первому игроку 3 руб. Требуется доказать, что данная игра не имеет седловой точки в чистых стратегиях и найти решение игры в смешанных стратегиях.
Слайд 24Решение
Платежная матрица имеет вид
Проверим, есть ли в игре седловая
точка в чистых стратегиях.
Нижняя цена игры
Верхняя цена игры
α≠β,
и седловой точки (в чистых стратегиях) в игре нет
Слайд 27Решение в смешанных стратегиях для первого игрока
Второй игрок так выбирает
свои стратегии, чтобы обеспечить первому минимальный выигрыш:
ν(p) = min {
ν1(p), ν2(p)}.Наилучший для первого игрока выбор соответствует
Из условия ν1(p) = ν2(p) или - p + 3(1- p) = 3 p - 5(1- p) находим
p= p* = 2/3.
Оптимальной смешанной стратегией первого игрока является стратегия
p* = (2/3, 1/3).
Цена игры равна ν* = ν1(2/3) = ν2(2/3) = 1/3.
Вне зависимости от того, какую стратегию выберет второй игрок, первый игрок будет выигрывать в среднем за большое число партий по 1/3 руб. за одну партию.
Слайд 30Решение в смешанных стратегиях для второго игрока
Наилучшее с точки зрения
второго игрока значение q определяется из условия
Из условия µ1(q)
= µ2(q) находим q* = 2/3. Поэтому оптимальная смешанная стратегия второго игрока равна
q* = (2/3, 1/3).
Слайд 31Основная теорема теории матричных игр
В любой матричной игре у игроков
есть оптимальные смешанные стратегии.
Слайд 32Решение игры 2×n
Матрица игры
Смешанные стратегии игрока 1 – вектор
Ожидаемый выигрыш
1-го игрока при применении игроком 2 своей j-ой стратегии:
Слайд 33Гарантированный выигрыш игрока 1
Строим графики ожидаемых выигрышей и по графику
устанавливаем точку М* - верхнюю точку нижней огибающей данного
семейства прямых, которая соответствует оптимальной стратегии первого игрока
Слайд 35Решение в чистых стратегиях
Нижняя цена игры
Верхняя цена игры
α ≠β,
значит, седловой точки (в чистых стратегиях) в игре нет
Слайд 36Решение в смешанных стратегиях для первого игрока
Пусть первый игрок играет
со смешанной стратегией
Обозначим νj(p) ожидаемый выигрыш первого игрока, если второй
игрок при этом выберет свою j-ю стратегию:
Слайд 38Оптимальная стратегия первого игрока
Из условия ν1(p) = ν2(p) находим p=6/11,
т.е. оптимальная стратегия первого игрока равна
Цена игры равна ν∗ =
ν1(6/11) = ν2(6/11)= −2/11.
Слайд 39Решение в смешанных стратегиях для первого игрока
Второй игрок, действуя разумно,
никогда не будет выбирать третью и четвертую стратегии, поэтому вектор
оптимальной смешанной стратегии второго игрока имеет видПроигрыш второго игрока равен
µ1(q) = − 2q + 3(1- q), если первый игрок выбирает свою первую стратегию, µ2(q) = 2q − 4(1-q), если первый игрок выбирает свою вторую стратегию.
Слайд 40Оптимальная стратегия второго игрока
Из условия µ1(q) = µ2(q) находим q=7/11.
Оптимальная
смешанная стратегия второго игрока равна
Слайд 41Игра m ×n
При решении матричной игры размерностью n ×
m могут быть применены два приема:
сведение задачи к задаче
m × 2 или 2×n; сведение задачи к задаче линейного программирования.
Слайд 42Доминирующие стратегии
Говорят, что стратегия А1 первого игрока доминирует стратегию А2,
если для всех j = 1, 2, …, n имеет
место a1j ≥ a2j. В этом случае стратегия A2 заведомо хуже стратегии A1. Стратегия A2 называется доминируемой и может быть исключена из рассмотрения.Говорят, что стратегия B1 доминирует стратегию B2 второго игрока, если для любого i справедливо ai1 ≤ ai2. Здесь стратегия B2 заведомо хуже стратегии B1, она называется доминируемой и может быть удалена из рассмотрения.
Слайд 43Основные теоремы теории игр
Ни одна из строго доминирующих чистых стратегий
не содержится в спектре оптимальных решений.
Если некоторая чистая стратегия
A, доминируется смешанной стратегией B, в спектре которой нет A, то удаление A приводит к тождественной игре.Решения игр будут тождественными, если каждый элемент платежной матрицы преобразуется следующим образом
пij = kaij + b, где k>0, b>0 – любые числа.
Без изменения оптимального решения каждый элемент платежной матрицы можно умножить на любое положительное число и сложить с любым положительным числом. При этом новая цена игры ν будет связана с реальной ценой соотношением νij = kν*ij + b
Слайд 45Решение
Стратегия А5 дублирует стратегию А2, поэтому любую из них
можно отбросить. Отбросим А5. Заметим, что в строке А1 все
выигрыши больше (или равны) выигрышам строки А4. Стратегия А1 доминирует над стратегией А4. Отбрасываем строку А4. Получим игру 3×5.
Слайд 46Решение
Стратегия В3 доминирует над В4 и над В5, а
В1 – над В2. Отбрасываем столбцы В2, В4, В5. Получим
игру 3×2.Стратегия А3 дублирует стратегию А1, поэтому любую из них можно отбросить. Отбросим А3. Получим игру 2×2.
Слайд 47Решение матричной игры сведением к задаче линейного программирования
Пусть рассматривается игра
с платежной матрицей, все элементы которой строго положительны
Смешанные стратегии первого
и второго игрокаЕсли стратегия p является оптимальной, то средний выигрыш первого игрока независимо от того, какую стратегию выберет второй игрок, будет не меньше цены игры ν∗:
Слайд 48Постановка задачи линейного программирования для первого игрока
Введем новые обозначения
Цель первого
игрока — максимизировать цену игры, т. е. минимизировать величину
Слайд 51Замечание
Если же в платежной матрице есть отрицательные элементы или
нули, то можно добавить ко всем элементам матрицы одно и
то же достаточно большое положительное число b, так чтобы все элементы матрицы стали положительными, затем поставить и решить пару двойственных задач линейного программирования, найти оптимальные смешанные стратегии игроков, а цену игры скорректировать путем вычитания из нее числа b.
Слайд 52Пример
В условиях предыдущего примера решить игру с платежной матрицей
сведением ее к задаче линейного программирования
Слайд 53Решение с помощью сведения задачи к паре взаимно двойственных задач
линейного программирования
От платежной матрицы
путем добавления положительного числа b = 5
перейдем к матрице
Слайд 55Оптимальные решения
Оптимальные решения задач ЛП
Оптимальные смешанные стратегии игроков
Цена игры
