Решение игр в смешанных стратегиях.
Если игра не имеет седловой точки, то применение чистых стратегий не дает оптимального решения игры. Так, в примере 1 α ≠ β, седловая точка отсутствует. В таком случае можно получить оптимальное решение, случайным образом чередуя чистые стратегии.
Смешанной стратегиейSA игрока А называется применение чистых стратегий A1, A2, ..., Am с вероятностями p1, p2, ..., pi, ..., pm причем сумма вероятностей равна 1:
Смешанные стратегии игрока А записываются в виде матрицы
или в виде строки SA = (p1, p2, ..., pi, ..., pm)
Аналогично смешанные стратегии игрока В обозначаются:
, или, SB = (q1, q2, ..., qi, ..., qn),
где сумма вероятностей появления стратегий равна 1:
Чистые стратегии можно считать частным случаем смешанных и задавать строкой, в которой 1 соответствует чистой стратегии. На основании принципа минимакса определяется оптимальное решение (или решение) игры: это пара оптимальных стратегий S*A , S*B в общем случае смешанных, обладающих следующим свойством: если один из игроков придерживается своей оптимальной стратегии, то другому не может быть выгодно отступать от своей. Выигрыш, соответствующий оптимальному решению, называется ценой игры v. Цена игры удовлетворяет неравенству:
α ≤ v ≤ β
где α и β — нижняя и верхняя цены игры. Справедлива следующая основная теорема теории игр — теорема Неймана. Каждая конечная игра имеет по крайней мере одно оптимальное решение, возможно, среди смешанных стратегий. Пусть S*A = (p*1, p*2, ..., p*i, ..., p*m) и S*B = (q*1, q*2, ..., q*i, ..., q*n) — пара оптимальных стратегий. Если чистая стратегия входит в оптимальную смешанную стратегию с отличной от нуля вероятностью, то она называется активной.
Справедлива теорема об активных стратегиях: если один из игроков придерживается своей оптимальной смешанной стратегии, то выигрыш остается неизменным и равным цене игры v, если второй игрок не выходит за пределы своих активных стратегий.
Эта теорема имеет большое практическое значение — она дает конкретные модели нахождения оптимальных стратегий при отсутствии седловой точки.
Рассмотрим игру размера 2Ч2, которая является простейшим случаем конечной игры. Если такая игра имеет седловую точку, то оптимальное решение — это пара чистых стратегий, соответствующих этой точке.
Игра, в которой отсутствует седловая точка, в соответствии с основной теоремой теории игр оптимальное решение существует и определяется парой смешанных стратегий S*A = (p*1, p*2) и S*B = (q*1, q*2).
Для того чтобы их найти, воспользуемся теоремой об активных стратегиях. Если игрок А придерживается своей оптимальной стратегии S'A, то его средний выигрыш будет равен цене игры v, какой бы активной стратегией ни пользовался игрок В. Для игры 2Ч2 любая чистая стратегия противника является активной, если отсутствует седловая точка. Выигрыш игрока А (проигрыш игрока В) — случайная величина, математическое ожидание (среднее значение) которой является ценой игры. Поэтому средний выигрыш игрока А (оптимальная стратегия) будет равен v и для 1-й, и для 2-й стратегии противника.
Пусть игра задана платежной матрицей
Средний выигрыш игрока А, если он использует оптимальную смешанную стратегию
,
а игрок В — чистую стратегию B1 (это соответствует 1-му столбцу платежной матрицы Р), равен цене игры v: a11 p*1+ a21 p*2= v. Тот же средний выигрыш получает игрок А, если 2-й игрок применяет стратегию B2, т.е. a12 p*1+ a22 p*2= v. Учитывая, что p*1+ p*2= 1, получаем систему уравнений для определения оптимальной стратегии S'A и цены игры v:
Решая эту систему, получим оптимальную стратегию
и цену игры
Применяя теорему об активных стратегиях при отыскании S*B- оптимальной стратегии игрока В, получаем, что при любой чистой стратегии игрока А (А1 или А2) средний проигрыш игрока В равен цене игры v, т.е.
Тогда оптимальная стратегия определяется формулами:
Пример 1.
Игра «поиск»
Игрок А может спрятаться в одном из двух убежищ (I и II); игрок В ищет игрока А, и если найдет, то получает штраф 1 ден. ед. от А, в противном случае платит игроку А 1 ден. ед. Необходимо построить платежную матрицу игры.
Решение. Для составления платежной матрицы следует проанализировать поведение каждого из игроков. Игрок А может спрятаться в убежище I – обозначим эту стратегию через A1 или в убежище II — стратегия A2 .
Игрок В может искать первого игрока в убежище I — стратегия B1 , либо в убежище II — стратегия B2. Если игрок А находится в убежище I и там его обнаруживает игрок В, т.е. осуществляется пара стратегий (A1, B1), то игрок А платит штраф, т.е. a11 = - 1. Аналогично получаем a22 = - 1 (A2, B2). Очевидно, что стратегии (A1, B2) и (A2, B1) дают игроку А выигрыш 1, поэтому a12 = a21 = 1. Таким образом, для игры "поиск" размера 2Ч2 получаем платежную матрицу
Применим полученные результаты для отыскания оптимальных стратегий для игры, рассмотренной в примере 1.
Пример 2.
Найти оптимальные стратегии игры, приведенной в примере 1.
Решение. Игра "поиск" задана платежной матрицей без седловой точки:
Поэтому ищем решение в смешанных стратегиях; для игрока А средний выигрыш равен цене игры v (при B1 и B2); для игрока В средний проигрыш равен цене игры v (при A1 и B2). Системы уравнений в данном случае имеют вид:
Решая эти системы, получаем
Это означает, что оптимальная стратегия каждого игрока состоит в том, чтобы чередовать свои чистые стратегии случайным образом, выбирая каждое из убежищ с вероятностью 1/2, при этом средний выигрыш равен 0.
РЕФЕРАТ ПО ДИСЦИПЛИНЕ «МАТЕМАТИКА»
НА ТЕМУ: «Решение игры в смешанных стратегиях».
Другие работы по теме:
Экономическая кибернетика
Эк. Кибернетика. Игра – матем. Модель конфликтной ситуации. Стратегия игрока – это правила выбора действий в сложившейся ситуации. Решение игры – это нахождение оптимальной стратегии для каждого игрока, т.е. нахождение цены игры.
Сущность теории игр
Теория игр как раздел математики для изучения конфликтных ситуаций. Основные понятия и критерии теории игр, количество стратегий. Увеличение среднего выигрыша путем применения смешанных стратегий. Мажорирование (доминирование) стратегий, алгоритм решения.
Теория игр и статических решений
Определение доминирующей стратегии в игре; равновесия в смешанных, осторожных и чистых стратегиях; совершенного подыгрового равновесия методом обратной индукции. Платежная матрица игры. Равновесный уровень заработной платы и занятости в статической игре.
Экономико-математическое моделирование
Построение сетевого графика согласно данным структурно-временной таблицы. Определение вероятности отказа и средней длины очереди для систем массового обслуживания. Решение игры в чистых стратегиях, по принципу доминирования и графическим методом.
Биматричные игры. Поиск равновесных ситуаций
Конфликтные ситуации в управленческой деятельности. Использование математического моделирования для решения управленческих задач. Определение биматричной игры и общий принцип ее решения. Состояние равновесия в смешанных стратегиях в биматричных матрицах.
Деловые игры
Хорошая форма для коллективного познания – деловые игры. Деловые игры моделируют реальную производственную, научную или иную "взрослую" деятельность. В этой главе мы дадим описание нескольких деловых игр.
Манипулятивное общение
Способы структурирования времени по Эрику Берну. Две жизненные позиции, выдвинутые Эриком Берном. Понятие манипуляции.
Игровая зависимость
Text 0)Отсутствие игровой зависимости («социальный» игрок). На этой стадии игра обусловлена познавательным интересом и используется для развлечения, отвлечения, расслабления, отдыха, отключения от проблем (семейных, личностных, потенциальных) 0)Отсутствие игровой зависимости («социальный» игрок).
Сочинения на свободную тему - Описание комнаты
Вхожу в светлую теплую небольшую комнату стол кровать шкафы с книгами и игрушками. Это моя комната. Я здесь провожу большую часть времени делаю уроки читаю играю. Моя комната имеет свое лицо здесь стоят книги которые необходимы мне в учебе развиваю.
Отчет
Ключевые слова: ацидокомплексообразование, донорное число, гидрофобные взаимодействия, водно-органические кристаллосольваты, галогениды меди, галогениды кадмия, диметилсульфоксид, диметилформамид, 1,4-диоксан, рентгеноструктурный анализ, колебательные спектры, валентные силовые постоянные
Тема Кол-во страниц
Игровая деятельность в жизни ребенка. Психолого-педагогическая характеристика игры
Теория игр
Классификация игр. Матричные игры. Смешанное расширение матричной игры.. Игры порядка 2 х 2.
Методы решения биматричных игр
Основные определения теории биматричных игр. Пример биматричной игры "Студент-Преподаватель". Смешанные стратегии в биматричных играх. Поиск "равновесной ситуации". 2x2 биматричные игры и формулы для случая, когда у каждого игрока имеется две стратегии.
Игровые модели и принятие решений
Московская сельскохозяйственная академия им. К.А. Тимирязева –––––––––––––––––––––––––––––––––––––––––––––––––––––––––– Кафедра экономической кибернетики
Бескоалиционные игры
Антагонистические игры, которые мы изучали ранее, описывают конфликты весьма частного вида. Более того, для большинства имеющих место в реальной жизни конфликтов антагонистические игры либо вовсе не могут считаться приемлемыми, адекватными описаниями, либо, в лучшем случае, могут рассматриваться как первые грубые приближения.
Теория игр 4
Курсовая работа по курсу математики Содержание Введение 1. Понятие об игровых моделях 2. Платёжная матрица. Нижняя и верхняя цена игры 3. Решение игр в смешанных стратегиях
Матричная игра
Вариант 1. 1. Для матричной игры, заданной платёжной матрицей A, найти: все максиминные стратегии игрока 1; все минимаксные стратегии игрока 2; все седловые точки;
Теория игр, рафический метод в теории игр
Челябинский юридический колледж Кафедра математических и естественнонаучных дисциплин КУРСОВАЯ РАБОТА по дисциплине «Математические методы» Теория игр. Графический метод решения теории игр
Сетевое планирование
Построение сетевой модели, расчет временных параметров событий. Критический путь модели. Оптимизация сетевой модели по критерию "минимум исполнителей". Исходные данные для оптимизации загрузки. Оптимальное решение игры двух лиц с нулевой суммой.
Описание картины Вратарь
Описание картины "Вратарь" Автор: Разное Картина Григорьева Сергея Алексеевича «Вратарь» была написана неяркими, приглушёнными красками в 1949 году. На ней мы видим футбольный матч.
Сочинение по картине С. Григорьева Вратарь
Автор: Разное С. Григорьев изобразил момент игры в футбол. На картине художника – осень, неясный день. Кустарники и трава уже пожелтели. Ребята собрались после школы поиграть в футбол.
Виды игр в педагогике
— относительно самостоятельная деятельность детей и взрослых. Она удовлетворяет потребность людей в отдыхе, развлечении, познании, в развитии духовных и физических сил.
Лавинг против Виргинии
Введение 1 Обстоятельства 2 Важные прецеденты Список литературы Лавинг против Виргинии Введение Уоррен, присоединились все Лавинг против Виргинии — историческое решение Верховного суда США, установившее свободу смешанных браков. Решение было поддержано единогласно всеми членами суда.
Олимпийские игры 5
Олимпийские игры (греч. Olэmpia) Древнейшие и наиболее популярные в Древней Греции общегреческие празднества и состязания. Устраивались в честь бога Зевса, согласно традиции, с 776 до н. э. в Олимпии 1 раз в 4 года. На время объявлялся обязательный для всех греков «священный мир», в это время в Греции не велось военных действий и дороги в Олимпию были безопасны.
Решение матричных игр
Реализация программы для решения матричных игр. Задание матрицы игры вручную и случайным образом, нахождение оптимальных стратегий игроков итерационным и методом чистых стратегий. Проектирование и листинг программного кода, сохранение матрицы игры.