Описание и программирование матричных игр

Федеральное агентство по образованию  ФГОУ ВПО

Брянский государственный  технический университет политехнический  колледж

 

0211691

230105

 

Курсовая работа

По дисциплине «Математические  методы»

Тема работы: «Описание  и программирование матричных игр»

 

Преподаватель:	Певнев А.А
Группа:	36 про 07
Студента:	Серпкова Н.И
Оценка:
Дата:

 

2010 

 

1. Введение

 

Теория игр – раздел математики, предметом которого является изучение математических моделей принятия оптимальных решений в условиях конфликта.

ИГРОЙ называется всякая конфликтная ситуация, изучаемая  в теории игр и представляющая собой упрощенную, схематизированную  модель ситуации. От реальной конфликтной  ситуации игра отличается тем, что не включает второстепенные, несущественные для ситуации факторы и ведется по определенным правилам, которые в реальной ситуации могут нарушаться

Классификацию игр можно  проводить: по количеству игроков, количеству стратегий, характеру взаимодействия игроков, характеру выигрыша, количеству ходов, состоянию информации и т.д.

Игры двух и более  игроков менее исследованы из-за возникающих принципиальных трудностей и технических возможностей получения  решения. Чем больше игроков - тем  больше проблем.

По количеству стратегий  игры делятся на конечные и бесконечные. Если в игре все игроки имеют конечное число возможных стратегий, то она называется конечной. Если же хотя бы один из игроков имеет бесконечное количество возможных стратегий, игра называется бесконечной.

Математическая теория игр способна не только указать оптимальный путь к решению некоторых проблем, но и прогнозировать их исход. Матричная игра – это конечная игра двух игроков с нулевой суммой, в которой задаётся выигрыш игрока 1 в виде матрицы (строка матрицы соответствует номеру применяемой стратегии игрока 2, столбец – номеру применяемой стратегии игрока 2; на пересечении строки и столбца матрицы находится выигрыш игрока 1, соответствующий применяемым стратегиям).

Матричные игры серьёзно изучаются специалистами, так как они довольно просты и к ним могут быть сведены игры общего вида. Поэтому теория матричных игр  хорошо развита, существуют различные методы поиска решения игр.

Главный момент, рассмотренный  в теории исследования операций —  выбор, принятие решения.

Оперирующая сторона имеет выбор альтернативных действий, и необходимо сделать его оптимально. Могут присутствовать другие оперирующие стороны.

Субъект характеризуется  наличием возможности выбора и наличием цели.

Перед субъектом стоят  две проблемы — необходимость  выбора (при этом, бездействие рассматривается как один из вариантов выбора, который присутствует всегда) и степень неопределенности, в которой совершается выбор. Если все исходы зависят только от выбора, и все варианты выбора известны, то получается выбор в условиях полной детерминированности; такие задачи решаются с помощью методов оптимизации, и такие задачи далее не рассматриваются.

В ситуации с неполной определенностью возможны варианты:

• Есть другая оперирующая сторона, и их интересы противоположны — антагонистические игры. Неопределенность состоит в том, что неизвестно, какое решение примет другая сторона.
• Другая оперирующая сторона не противодействует и не взаимодействует с целью помочь. Неопределенность связана с недостаточными знаниями.
• Есть другие оперирующие стороны, и интересы субъектов не являются противоположными. Неопределенность в том, что неизвестно, как будут поступать другие и, возможно, в недостатке знаний.
• Множество субъектов могут совместно преследовать одну цель.

В игре могут участвовать два или более игроков. Случай игры с одним участником (пасьянс, управление физическим объектом и т.д.) в сущности, является игрой двух лиц, где вторым участником выступает природа (судьба, рок, провидение).

Игроки могут в игре выступать каждый за себя или объединяться в группы. В последнем случае игра называется коалиционной.

Игры, в которых игроки осведомлены о состоянии своем  и партнеров, а также о прошлом  поведении участников игры, относятся  к категории игр с полной информацией (типичные примеры - шахматы, "крестики-нолики" и т.п.). Большинство же игр протекает в условиях неполной информации, где сведения о состоянии партнеров исчерпываются лишь вероятностными характеристиками (домино, карточные игры, игры против "природы").

Антагонистическую игру, где выигрыш одного коллектива равен проигрышу другого, называют игрой с нулевой суммой.

Система правил, однозначно определяющая выбор хода игрока в  зависимости от сложившейся ситуации, называется стратегией.

Каждая фиксированная  стратегия игрока, где любой ситуации сопоставлен конкретный выбор, называется чистой. В реальности чаще используются т.н. смешанные стратегии, где чистые стратегии смешиваются с некоторыми частотами.

ИГРОКОМ (лицом, стороной, или коалицией) называется отдельная  совокупность интересов, отстаиваемая в игре. Если данную совокупность интересов отстаивает несколько участников игры, то они рассматриваются как один игрок. Игроки, имеющие противоположные по отношению друг к другу интересы, называются  противниками. В игре могут сталкиваться интересы двух или более противников.

 

Простейшими являются игры 2 лиц с нулевой суммой.

Пусть в такой игре игрок 1 имеет m выборов и игрок 2 - n выборов. Если игрок 1 делает свой i - й выбор, а игрок 2 - свой j - й выбор, то выигрыш игрока 1 (проигрыш игрока 2) равен . Такая игра называется матричной и матрица: называется матрицей выигрышей (платежной матрицей).

При ведении игры игрок  должен ориентироваться на оптимальную  политику партнера и наказывать его  за отступления от таковой.

2. Аннотация

 

Цель выпускной квалификационной работы изучить некоторые методы приближённого решения матричных  игр, обосновать их алгоритмы, и, по возможности,  реализовать на языке программирования.

Работа состоит из введения, четырех  параграфов и приложения, в котором приведена программа на языке. С++, позволяющая находить приближённое решение матричной игры.

В первом параграфе приведены основные понятия и утверждения теории матричных игр.

Параграф второй посвящён антагонистическим  играм. В нем описаны условия существования равновесия в матричной игре, механизм случайности выбора стратегии, методы нахождения равновесного решения и использование игровых методов в планировании товарного ассортимента фирмы.

Параграф третий посвящён изложению  приближённого  решения игры методом Брауна-Робинсона (метод фиктивного разыгрывания) и его обоснованию. Приведён пример применения алгоритма для конкретной матричной игры.

В третьем параграфе  рассмотрен ещё один метод – монотонный итеративный алгоритм приближённого решения матричных игр.

 

3. Теоретическая часть

3.1. Общая постановка игры двух лиц

 

Модель игры двух лиц - одна из простейших моделей: в ней  всего две оперирующих стороны.

Пусть заданы две оперирующие стороны (два игрока). У каждого из игроков  есть множество возможных действий: у первого — , у второго — . Или, что, то же самое, и — множества стратегий первого и второго игроков, соответственно. Каждый игрок может выбрать любую из своих стратегий.

Если первый игрок  выбирает стратегию , второй игрок выбирает стратегию (при этом, помним, что бездействие — тоже стратегия), то формируется пара , называемая исходом игры. Каждый исход для каждого игрока имеет привлекательность (или выгодность, выигрыш, полезность). Эту привлекательность мы зададим с помощью функций выигрыша игроков: — функция выигрыша первого игрока, — функция выигрыша второго игрока, , . Функции выигрыши также называются функциями полезности и целевыми функциями.

Из этой модели видно, что выигрыш игрока зависит не только от его выбора, но и от выбора другого игрока.

В этой модели игра заключается  в том, что первый игрок выбирает свою стратегию, второй игрок — свою, и делается ход. В этой модели совершается  лишь один ход.

Задача первого игрока состоит в том, чтобы максимизировать  свою функцию полезности:

Второй игрок максимизирует  свою функцию полезности:

Кроме сделанного описания, принимаются гипотезы:

• Гипотеза полной информированности. Каждому из игроков точно известны его собственное множество стратегий и множество стратегий второго игрока, а также обе функции полезности. Единственное, что неизвестно каждому из игроков, — это выбор другого игрока. (Хотя, заметим, что во многих практических примерах игр двух лиц эта гипотеза не выполняется).
• Гипотеза рационального поведения игроков. Каждый из игроков считает другого не глупее себя: если первый игрок узнал какую-либо информацию об игре, то и второй игрок ее тоже знает; в другой формулировке: все интересы игрока заключены в максимизации его целевой функции.

3.2. Антагонистические игры

 

Антагонистические игры (или игры с нулевой суммой) —  это такие игры, в которых цели игроков прямо противоположные. Т.е., величина выигрыша одно игрока равна  величине проигрыша другого игрока:

Тогда получается, что максимизируя выигрыш одного игрока, минимизируем выигрыш другого. Рассмотрим частный случай таких игр, когда у каждого из игроков есть конечное число стратегий. Тогда множества возможных стратегий для игроков имеют вид:

Тогда в игре будет  всего  исходов. С каждым и сходом связан выигрыш первого игрока :

Обозначим за C матрицу, элементами которой являются величины выигрыша первого игрока:

Тогда, если оба игрока имеют конечные множества стратегий, антагонистическая игра полностью C.

 

Пример. (Игра в пальцы) Оба игрока одновременно показывают каждый по 1, 2 или 3 пальца и не может отказаться от игры. Если сумма количеств пальцев нечетна, то выигрывает второй, иначе выигрывает первый игрок. Сумма выигрыша есть количество пальцев, показанных обоими игроками.

Для этой игры множества  стратегий можем задать:

Матрица игры:

3.3. Существование равновесия

 

Рассмотрим вопрос о  существовании равновесия. В качестве примера рассмотрим игру в пальцы:

Гарантированные результаты для первого игрока есть , гарантирующая стратегия есть . Для второго: , гарантирующие стратегии - .

Рассмотрим исход  . Первому игроку выгоднее воспользоваться третьей стратегий, второму игроку — второй стратегией. Таким образом, не является равновесным исходом игры. Аналогичным образом приходим к выводу, что и не является равновесным исходом игры.

В связи с этим возникает  вопрос: как играть игрокам и как  определить, существует ли равновесный исход.

Из примеров видно, что  существует антагонистические игры с равновесным исходом и без  него. Поэтому, все антагонистические  игры можно разбить на два класса: в одном классе игры имеют равновесный исход, в другом не имеют.

Формально определим все используемые определения. Имеется множество D стратегий первого игрока, множество G стратегий второго игрока, первый игрок выбирает стратегию , второй игрок выбирает стратегию , и определяется исход игры . На множестве исходов игры задается функция выигрыша первого игрока , которая определяет выигрыш первого игрока, который равен проигрышу второго игрока.

Далее, определяется функция  гарантированного результата первого игрока при выборе им :

Гарантированный результат  первого игрока:

И гарантированный результат  первого игрока:

Аналогично, для второго  игрока определим функцию гарантированного результата , его гарантированный результат и гарантирующую стратегию :

Значение  называется максимином функции , — максиминная стратегия, a — минимакс, и — минимаксная стратегия.

Определим ситуацию равновесия в игре следующим образом:

Это определение равновесной  ситуации имеет тот смысл, что  ни одному из игроков не выгодно  менять стратегию, если другой игрок  не меняет свою.

Эти неравенства соответствуют в седловой точке функции . Т.е., пара является ситуацией равновесия тогда и только тогда, когда - седловая точка.

Стратегии игроков, соответствующие  ситуации равновесия, называют равновесными стратегиями.