ТЕОРИЯ ИГР. МАТРИЧНЫЕ ИГРЫ С ПРИРОДОЙ

III Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке

Личный портфель

ТЕОРИЯ ИГР. МАТРИЧНЫЕ ИГРЫ С ПРИРОДОЙ

Кутькина Т.Ю. 1Колосова А.К. 1
1МБНОУ "ГКЛ"
Забусова А.А. 1
1МБНОУ
Автор работы награжден дипломом победителя II степени
Диплом школьникаСвидетельство руководителя
Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF

Введение

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

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

Цель работы: определить наиболее удобный критерий решения матричных игр с природой при выборе оптимального решения.

Объект исследования: матричные игры с природой.

Предмет исследования: критерии решения матричных игр с природой.

Для достижения этой цели необходимо выполнить следующие задачи:

  1. изучить теоретический материал по данной теме;

  2. рассмотреть примеры решения матричных игр с природой при помощи различных критериев: Гурвица, Вальда и Сэвиджа;

  3. решить подобранные задачи при помощи критериев;

  4. описать данные критерии и выбрать наиболее оптимальный из них;

  5. составить собственные задачи по теме работы.

Методы:

  1. изучение и теоретический анализ литературы по исследуемой проблеме;

  2. анализ некоторых вариантов контрольных работ, предложенных студентам РЭУ им. Плеханова;

  3. систематизация задач.

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

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

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

Глава I. Теоретическая часть 1.1. Матричные игры. Основные понятия

Зачастую человек осуществляя какую-либо деятельность, сталкивается с проблемой принятия решения в условиях множества факторов, влияющих на само решение.

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

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

Матричные игры — это игры, где два игрока играют в игру с нулевой суммой, имея конечное число «чистых» стратегий: {1,…, m} и {1,…, n} и ∀ (ij) задан платеж aij второго игрока первому. Матрица (aij) задает выигрыш первого игрока и проигрыш второго, aij ≷ 0! (Матрица — математический объект, записываемый в виде прямоугольной таблицы или поля, которая представляет собой совокупность строк и столбцов, на пересечении которых находятся её элементы).

Обычно выделяют 2 наиболее важных типа матричных игр:

  • «Игры с природой», в которых только один участник стремится максимизировать свою прибыль, которая зависит от того, какой будет погода, или каким будет состояние рынка. Если единственный участник принял решение оптимально спланировать свою хозяйственную деятельность при самых неблагоприятных погодных или рыночных условиях, то он может считать природу или рынок активным враждебным субъектом.

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

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

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

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

Тогда, если обозначить то

Парная игра с нулевой суммой формально задается платежной матрицей

элементы aij которой определяют выигрыш первого игрока (лица А) и соответственно проигрыш второго (лица В), если первый игрок выбирает i – ю строку (Аi стратегию), а второй игрок выбирает j – й столбец (Вj стратегию).

В каждой i – й строке игроку А гарантирован минимальный выигрыш, то есть . Игрок А стремится максимизировать свой минимальный выигрыш, то есть получить

(2)

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

Игроку В в каждом j – м столбце гарантирован максимальный проигрыш, то есть . Он стремится минимизировать свой проигрыш, то есть получить (3)

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

Отметим что всегда .

Если , то имеем в матрице М элемент который является максимальным в j – м столбце и минимальным в i – й строке. Этот элемент называется седловой точкой.

Его индексы: - указывает оптимальную стратегию игрока А, - указывает оптимальную стратегию игрока В.

Значит, в этом случае матричная игра решается в чистых стратегиях: игрок А получает оптимальную стратегию , игрок В получает оптимальную стратегию , цена игры .

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

.

Игрок В выбирает стратегию с вероятностью . Аналогично смешанные стратегии игрока В записываются в виде вектора , причем , или в виде матрицы

. [1]

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

1.2. Классификация игр

Обычно игры классифицируют следующим образом:

  • По количеству игроков: игры 1, 2, n игроков.

  • По количеству стратегий: конечные и бесконечные игры. Если у игроков конечное число стратеги, то такая игра конечная, иначе —бесконечная.

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

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

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

  • По свойствам функций выигрышей: непрерывные, выпуклые, сепарабельные и т. д. Если сумма выигрышей всех игроков в каждой партии равна нулю, то это — игра с нулевой суммой. Игра двух игроков c нулевой суммой называется антагонистической. В такой игре один игрок выигрывает за счет другого. Конечная антагонистическая игра называется матричной игрой. В играх с ненулевой суммой все игроки в сумме могут получить меньше их суммарного взноса. [1]

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

1.3. Методы решения матричных игр

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

  • Решение матричной игры сведением к задаче линейного программирования: В этом случае вся игра задана платежной матрицей. Оптимальные смешанные стратегии игроков А и В могут быть найдены в результате решения пары двойственных задач линейного программирование.

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

  • Решение игр с природой по различным критериям: поскольку игры с природой являются частным видом парных матричных игр, то вся теория стратегических игр переносится и на игры с природой. Однако игры с природой обладают и некоторыми особенностями. Например, при упрощении платежной матрицы отбрасывать те или иные состояния природы нельзя, так как она может реализовать любое состояние. И ещё одна важная особенность: в играх с природой смешанные стратегии имеют ограниченное значение. Смешанные стратегии приобретают смысл только при многократном повторении игры. [3]

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

1.4. Игры с природой

На практике часто встречается класс матричных игр, в которых стратегия второго игрока неопределенна. Это, так называемые, "игры с природой". Например, нас интересует вопрос об объемах поставок продукции на рынок в условиях полной неопределенности о величине спроса на эту продукцию.

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

Критерий Вальда:

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

1. минимаксный критерий: W = min(max[aji]);

2. максиминный критерий: W = max(min[aji]).

Если в исходной матрице результат aji представляет потери лица, принимающего решение, то при выборе оптимальной стратегии используется минимаксный критерий. Для определения оптимальной стратегии Aj необходимо в каждой строке матрицы результатов найти наибольший элемент max(aji), а затем выбирается действие Aj (строка j), которому будет соответствовать наименьший элемент из этих наибольших элементов, т. е. действие, определяющее результат, равный W = min(max[aji]) Если в исходной матрице по условию задачи результат aji представляет выигрыш (полезность) лица, принимающего решение, то при выборе оптимальной стратегии используется максиминный критерий. Для определения оптимальной стратегии Aj в каждой строке матрицы результатов находят наименьший элемент min[aji], а затем выбирается действие Aj (строка j), которому будут соответствовать наибольшие элементы из этих наименьших элементов, т. е. действие, определяющее результат, равный W = max(min[aji]).

Критерий Сэвиджа:

,

где - элементы матрицы R – матрицы риска. Матрица риска составляется по правилу: в столбце определяется наибольший элемент и из этого числа вычитаются последовательно все элементы этого столбца. Критерий Сэвиджа использует матрицу рисков |rji|, где rji есть разность между наилучшим значением в столбце i и значениями aji при том же i.

Критерий Гурвица:

Критерий Гурвица основан на следующих двух предположениях: «природа» может находиться в самом невыгодном состоянии с вероятностью (1 — k) и в самом выгодном состоянии с вероятностью k, где k — коэффициент доверия. Если результатa aji — прибыль, полезность, доход и т.п., то критерий Гурвица записывается так:

G = max[kmax[aji]+(1-k)min[aji]]Когда целевая функция представляет затраты (потери), то:

G = min[kmin[aji]+(1-k)max[aji]]

Критерий Гурвица устанавливает баланс между случаями крайнего пессимизма и крайнего оптимизма путем взвешивания обоих способов поведения соответствующими весами (1 —k) и k, где 0

Просмотров работы: 2981