Нахождение смешанных стратегий в играх с матрицей 2xN
Введение
Для принятия оптимальных решений необходимо использовать научный метод. В науке управления научный метод подразумевает наличие определенной структуры процесса принятия решений и использование различных методов и моделей принятия решений [1]. Очень часто принимать решение приходится в так называемых игровых ситуациях.
Плавила, условия игры определяют возможные поведение, выборы и ходы для игроков на любом этапе развития игры. Сделать выбор игроку, значит остановиться на одной из его возможностей. Игрок осуществляет этот выбор с помощью ходов. Сделать ход – это значит, на определенном этапе игры осуществить сразу весь выбор.
Теорию игр можно применять для решения ряда экономических задач. Эти задачи могут быть решены очень быстро с помощью заранее выработанных алгоритмов. Сейчас моментальное решение неожиданно возникающих проблем очень существенно, так как конкуренция растет с каждым днем все больше и больше. К тому же с помощью теории игр можно выработать такую оптимальную стратегию, при которой система не будет существенно изменяться под управлением каких-то внешних воздействий, да и потери будут не столь существенными.
В математической теории игр рассматриваются задачи принятия решения, когда на некоторую систему воздействуют несколько управляющих подсистем, каждая из которых имеет свои цели и возможности действий. Такой подход к принятию решения называется теоретико-игровым, а математические модели соответствующих взаимодействий называются играми [10]. Так как цели управляющих подсистем различны, а также существуют ограничения на возможности обмена информацией между ними, указанные взаимодействия носят конфликтный характер. Поэтому всякая игра представляет собой математическую модель конфликта. В терминологии теории игр первая управляющая подсистема называется игроком 1, вторая управляющая подсистема – игроком 2. Множества альтернативных действий игроков называются множествами стратегий этих игроков.
При решении задач теории игр необходимо осуществить следующие аспекты:
1. Выработка принципов оптимальности, то есть того, какое поведение игроков следует считать разумным или целесообразным.
2. Выяснение реализуемости принципов оптимальности, то есть установление существования оптимальных ситуаций и стратегий.
3. Отыскание оптимальных ситуаций, то есть реализация игры.
Основной целью теории игр является выработка рекомендаций для удовлетворительного поведения игроков в конфликте, то есть выявления для каждого из них «оптимальной стратегии».
Понятие оптимальной стратегии — одно из важнейших понятий теории игр, может пониматься в различных смыслах в зависимости от показателя оптимальности. Стратегия, оптимальная по одному показателю, может не быть оптимальной по другому показателю. Поэтому чаще всего оптимальная стратегия, определенная в результате применения теории игр к реальным конфликтным ситуациям, является оптимальной теоретически и в большинстве случаев реально удовлетворительной.
В данной работе рассматривается метод нахождения решения матричной игры двух лиц, в которых игрок 1 может применять только две стратегии, а игрок 2 больше двух стратегий, такие игры задаются платежной матрицей размерности 2хn. В работе приводятся основные понятия теории игр, необходимые для решения данной задачи, и решение конкретной задачи с заданными числовыми значениями.
НАХОЖДЕНИЕ СМЕШАННЫХ СТРАТЕГИЙ В ИГРАХ С МАТРИЦЕЙ 2xn
Постановка задачи в математической теории игр, оптимальные стратегии. Игра с нулевой суммой. Седловая точка игры
Игра с нулевой суммой означает, что сумма выигрышей всех игроков в каждой партии равна нулю. Игры двух игроков с нулевой суммой относятся к классу антагонистических игр. При этом выигрыш одного игрока равен, естественно, проигрышу другого игрока [2].
Матричная игра — конечная игра двух игроков с нулевой суммой. Таким образом, в матричной игре участвуют два игрока, множество стратегий каждого из игроков конечно, а выигрыш одного игрока равен проигрышу другого.
Матричная игра являются антагонистической. Такая игра задается платежной матрицей A = (aij), , , где m – число стратегий 1-го игрока, n – число стратегий 2-го игрока. В платежной матрице элементы aij — это значения выигрыша игрока 1 в ситуации, когда игрок 1 выбирает свою i-ю стратегию, а игрок 2 свою j-ю стратегию, и одновременно, значения проигрыша 2-го игрока.
Для определения оптимальных стратегий применим принцип получения максимального гарантированного результата при наихудших условиях. Он заключается в следующем.
Игрок 1 должен получить максимальный гарантированный результат при наихудших условиях. Значит, при выборе отвечающей этим условиям своей чистой i-й стратегии (в платежной матрице этой стратегии соответствует i-я строка выигрышей) он должен выбрать гарантированный результат в наихудших условиях, то есть наименьшее значение своего выигрыша aij , которое обозначим αi .
Чтобы этот гарантированный эффект в наихудших условиях был максимальным, нужно из всех αi выбрать наибольшее значение
Зарегистрируйся, чтобы продолжить изучение работы
.
Обозначим его α и назовем чистой нижней ценой игры («максимин»):
Таким образом, максиминной стратегии 1-го игрока отвечает строка матрицы, которой соответствует элемент α.
Какие бы стратегии ни применял игрок 2, игрок 1 максиминной чистой стратегией гарантировал себе выигрыш не меньший, чем α. Таково оптимальное поведение игрока 1.
Игрок 2 своими оптимальными стратегиями стремится уменьшить свой проигрыш. Поэтому при каждой j-й чистой стратегии он отыскивает величину своего максимального проигрыша βj в каждом j-м столбце:
Из всех своих n чистых стратегий игрок 2 отыскивает такую, при которой получит минимальный проигрыш, то есть игрок 2 определяет β – чистую верхнюю цену игры («минимакс»):
Т.е. игрок 2 за счет указанного выше выбора своих чистых стратегий не допустит, чтобы его проигрыш был больше, чем β. Таким образом, минимаксной стратегии 2-го игрока отвечает столбец матрицы, которому соответствует элемент β.
Чистая цена игры ν есть цена данной игры, если нижняя и верхняя ее цены совпадают, то есть
В этом случае игра называется игрой с седловой точкой.
Седловая точка является оптимальным совместным решением игроков 1 и 2. При этом оптимальной чистой стратегией игрока 1 является его максиминная стратегия, а оптимальной чистой стратегией игрока 2 является его минимаксная стратегия.
Игра без седловой точки, оптимальные смешанные стратегии
В играх без седловой точки применяют смешанные стратегии, которые можно представить в виде случайных величин, возможными значениями которых являются чистые стратегии [6].
Смешанная стратегия p= (p1, p2, …, pm) для игрока 1 – вероятностный вектор применения чистых стратегий А1, А2,..., Аm с соответствующими вероятностями p1, p2, …, pm, где
Число – это вероятность того, что игрок 1 применит чистую стратегию Аi .
Смешанная стратегия q= (q1, q2, …, qm) для игрока 2 – вероятностный вектор применения чистых стратегий B1, B2, … Bn с вероятностями q1, q2, …, qm, где
Число – это вероятность того, что игрок 2 применит чистую стратегию Вj.
Если мы окажемся в ситуации {Ai, Bj}, то есть когда игрок 1 применит стратегию Ai, а игрок 2 при этом применит стратегию Bj, то она реализуется с вероятностью .
В матричной игре, зная платежную матрицу A (она относится и к игроку 1, и к игроку 2), можно определить средний выигрыш игрока 1:
где p, q – векторы с компонентами pi, qj, соответственно.
Стратегии и называются оптимальными смешанными стратегиями игроков, если выполнено следующее условие оптимальности:
Левая часть этого неравенства
означает, что если первый игрок отклоняется от оптимальной стратегии p0, то его выигрыш может только уменьшиться при условии, что второй игрок придерживается оптимальной стратегии q0.
Аналогично, неравенство
означает, что если второй игрок отклоняется от оптимальной стратегии q0, то его проигрыш может только увеличиться.
Величина называется ценой игры.
Решить игру означает найти цену игры и оптимальные стратегии. Т.е. решением игры является нахождение «набора» (
Существование решения матричной игры обеспечивает основная теорема теории игр – теорема фон Неймана.
ТЕОРЕМА.
Для матричной игры с любой матрицей A величины
существуют и равны между собой:
Более того, существует, по крайней мере, одна ситуация ), для которой выполняется соотношение:
Другими словами, любая матричная игра имеет решение в смешанных стратегиях.
Мажорирование стратегий, принцип оптимальности
Мажорирование (доминирование) представляет отношение между стратегиями, наличие которого во многих практических случаях дает возможность сократить размеры исходной платежной матрицы игры [6].
Для игрока 1 его чистая стратегия k мажорируется его чистой стратегией s, если в платежной матрице каждый элемент строки k не больше соответствующего элемента строки s, т.е. akj≤asj, .
Для игрока 2 его чистая стратегия k мажорируется его чистой стратегией s, если в платежной матрице каждый элемент столбца k не меньше соответствующего элемента столбца s, т.е. aik≥ais, .
Строки и столбцы с мажорируемыми стратегиями можно исключить из платежной матрицы согласно принципу оптимальности, то есть выбору игроками такого поведение, какое следует считать разумным или целесообразным, т.е. заведомо игроку 1 стремиться увеличивать свой выигрыш, а игроку 2 стремиться уменьшать свой проигрыш.
Графоаналитический метод нахождения оптимальных смешанных стратегий
Существуют различные методы нахождения решения матричных игр. Применимость методов зависит, в том числе, от вида платежной матрицы
50% реферата недоступно для прочтения
Закажи написание реферата по выбранной теме всего за пару кликов. Персональная работа в кратчайшее
время!
Задать вопрос
на новый заказ в Автор24. Это бесплатно.
