36. Решение игры в чистых стратегиях. Игры с седловой точкой.
Стратегией игрока называется совокупность правил, определяющих выбор варианта действий при каждом личном ходе игрока в зависимости от ситуации, сложившейся в процессе игры.
Стратегия выбираемая игроком сознательно исходя из анализа сложившейся обстановки называется личной (или чистой).
Стратегия игрока называется оптимальной, если она обеспечивает данному игроку (обычно игрокуА) при многократном повторении игры максимально возможный средний выигрыш или минимально возможный средний проигрыш независимо от поведения противника (могут быть использованы и другие показатели оптимальности).
Оптимальные стратегии характеризуются устойчивостью, то есть ни одному из игроков не выгодно отклоняться от своей оптимальной стратегии.
Партияигры – это однократная возможная реализация правил игры (стратегий) игроками.
Матричной игройназывается парная игра, осуществляемая по следующим
правилам:
1. В игре участвуют два игрока - А иВ;
2. Каждый из игроков обладает конечным набором стратегий (для игрока А- это стратегииА1, А2, …..Аm, а для игрокаВ- это стратегииВ1,В2,…….Вn);
3. Игра заключается в том, что каждый из игроков, не имея информации о действиях противника, делает один ход (выбирает одну из своих стратегий). Результатом выбора игроками стратегий является выигрыш и проигрыш в игре.
И выигрыш, и проигрыш выражаются числами аij, которые являются элементами, так называемойплатежной матрицы. В частности, выигрыш для игрокаАпри выборе стратегииАi, и игрокомВ– стратегииВjравенаij, а для игрокаВ – он равенвij =-аij, то есть является проигрышем.
Платежная матрица (или матрица игры) – является одним из способов задания матричной игры, который называетсянормальным. Второй способ задания игры – позиционный способ связан развернутой формой задания игры и сводится к построению графа последовательных шагов игры (дереву игры).
Если условие вij =-аij не выполняется, то есть каждый из игроков имеет свою платежную матрице, тогда эта парная игра является игрой с ненулевой суммой и называетсябиматричной игрой.
Решить матричную (антагонистическую) игру – значит найти для игроковАиВих оптимальные стратегии.
Решение игры связано с матрицей (аij) и следующими понятиями:
Нижняя цена игры α=maxmin аij(сначала находится минимум в каждой строке, а
i j потом из полученных минимумов находится максимум). Это гарантированный выигрыш игрокаА при любой стратегии игрокаВ.
Верхняя цена игры β=minmax аij (сначала находится максимум в каждом столбце,
j iа потом из полученных максимумов находится минимум). Это гарантированный проигрыш игрокаВ при любой стратегии игрокаА.
Очевидно α<= β. В случаеα=β говорят о цене игрыν=α=β. Соответствующие цене игры стратегии являются оптимальными, а сама игра естьигра с седловой точкой.
В случае, когда α<β седловой точки не существует. В этом случае решение игры ищестся в смешанных стратегиях. Доказано (Дж. Фон Нейман), что конечная матричная игра имеет, по крайней мере, одно оптимальное решение, возможно в смешанных стратегиях.
- 1. Теория принятия решений: задача принятия решений, цель, проблема, проблемная ситуация.
- 2.Измерения при формировании решений: ранжирование, парное сравнение, непосредственная оценка, виды неопределенностей и их измерение.
- 3.Виды экспертиз.
- 4.Метод Дельфы
- 5. Дерево целей и решений.
- 6.Определение усредненного мнения экспертов (среднее арифметическое, среднее геометрическое, мода, медиана Кемени
- 7.Определение согласованности мнений экспертов (коэффициент конкордации).
- 8.Виды критериев оптимальности и их содержание.
- 9. Критериальный анализ ситуации: метод базовых шкал, ранжирование и выбор критериев.
- 10.Нечеткие множества и основные операции над ними.
- 11.Экспертные методы определения функций принадлежности.
- 12. Аналитический и оптимизационный методы определения функций принадлежности.
- 13. Нечеткая задача оптимизации выбора вариантов проектов.
- 14. Модели стохастического математического программирования
- 15. Генерация альтернатив решений: понятие генетического алгоритма.
- 16. Генерация альтернатив решений: Дерево решений
- 17. Многокритериальная оптимизация. Проблемы многокритериальной оптимизации
- 18. Многокритериальная оптимизация. Множество Парето.
- 19. Многокритериальная оптимизация. Метод идеальной точки.
- 20. Принятие решений по многим критериям: Метод последовательных уступок
- 21. Принятие решений по многим критериям: Парето оптимальное решение
- 23.Принятие решений по многим критериям: Гарантированные достоинства и недостатки.
- 24.Принятие решений по многим критериям: Правило Борда.
- 25.Принятие решений по многим критериям: Принцип Беллмана-Заде
- 26. Принятие решений по многим критериям: Турнирная таблица
- 30.Согласование групповых решений: принцип большинства голосов, принцип диктатора, принцип вето, идеальной точки, консенсус.
- 31.Согласование групповых решений по Парето.
- 32. Согласование групповых решений: Метод идеальной точки
- 33. Марковская модель согласования решений.
- 34. Согласования групповых решений. (принципы Курно, Парето, Эджворта).
- 35. Теория игр: платежная матрица, чистые и смешанные стратегии, решение игры.
- 36. Решение игры в чистых стратегиях. Игры с седловой точкой.
- 37.Решение игры в смешанных стратегиях. Теорема фон Неймана.
- 38.Решение матричных игр МхN (сведение к задаче линейного программирования).
- 39.Игры с природой (теория статистических решений). Особенности платежной матрицы.
- 40.Байесовские стратегии в играх с природой (частичная неопределенность).
- 41. Критерии принятия решений в играх с природой (полная неопределенность).
- 42.Марковские процессы с дискретным временем: основные понятия и определения.
- 43.Игры с природой: оценка риска