Задачи, сводящиеся к модели биматричной игры, и способы их решения
Игра как идеализированная математическая модель коллективного поведения. Биматричные игры, их виды, особенности, решение и применение в теории игр. Теория оптимального поведения игроков. Оптимальность и множество по Парето, метод идеальной точки.
| Рубрика | Экономико-математическое моделирование |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 17.06.2014 |
| Размер файла | 77,3 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Содержание
- Введение
- 1. Общее введение в теорию игр
- 2.Практическая часть
2.1 Биматричные игры
- 2.2 Оптимальность по Парето
- 2.3 Метод идеальной точки
- 2.4 Оптимальность по Парето в биматричной игре
- Введение
- В данной курсовой работе будет изучено применение теории игр в жизни, т.е. выбирать наиболее выгодные стратегии или беспроигрышные. Для этого будет рассмотрен раздел теории игр «Биматричные игры и их решение».
- В последнее время часто появляется необходимость согласования действий двух или нескольких фирм, объединений, министерств и других участников проектов в случаях, когда их интересы не совпадают. В таких ситуациях теория игр позволяет найти лучшее решение для поведения участников, обязанных согласовывать действия при столкновении интересов. Теория игр все шире проникает в практику экономических решений и исследований. Ее можно рассматривать как инструмент, помогающий повысить эффективность плановых и управленческих решений. Это имеет большое значение при решении задач в промышленности, сельском хозяйстве, на транспорте, в торговле, особенно при заключении договоров с иностранными партнерами на любых уровнях.
- Так, можно определить научно обоснованные уровни снижения розничных цен и оптимальный уровень товарных запасов, решать задачи экскурсионного обслуживания и выбора новых линий городского транспорта, задачу планирования порядка организации эксплуатации месторождений полезных ископаемых в стране. Классической стала задача выбора участков земли под сельскохозяйственные культуры.
- Обычно теорию игр определяют как раздел математики для изучения конфликтных ситуаций. Это значит, что можно выработать оптимальные правила поведения каждой стороны, участвующей в решении конфликтной ситуации.
В экономике, например, оказался недостаточным аппарат математического анализа, занимающийся определением экстремумов функций. Появилась необходимость изучения так называемых оптимальных минимаксных (выбор из максимальных наихудших проигрышей минимальных наилучших) и максиминных (выбор из минимальных наихудших выигрышей максимальных наилучших) решений. Следовательно, теорию игр можно рассматривать как раздел оптимизационного подхода, позволяющего решать новые задачи при принятии решений.
Игра - это идеализированная математическая модель коллективного поведения: несколько индивидуумов (участников, игроков) влияют на ситуацию (исход игры), причем их интересы (их выигрыши при различных возможных ситуациях) различны.
1. Общее введение в теорию игр
Противоборствующие интересы рождают конфликт, в то время как совпадение интересов сводит игру к чистой координации, для осуществления которой единственным разумным поведением является кооперация. В большинстве игр, возникающих из анализа социально-экономических ситуаций, интересы не являются ни строго противоборствующими, ни точно совпадающими. Продавец и покупатель согласны, что в их общих интересах договориться о продаже, конечно, при условии, что сделка выгодна обоим. Однако они энергично торгуются при выборе конкретной цены в пределах, определяющихся условиями взаимной выгодности сделки. Подобно этому рядовые избиратели, как правило, согласны отвести кандидатов, представляющих крайние точки зрения.
Однако при избрании одного из двух кандидатов, предлагающих различные компромиссные решения, возникает ожесточенная борьба. Нельзя не согласиться, что большинство напоминающих игры конфликтных ситуаций общественной жизни порождают как конфликтное, так и кооперативное поведение. Поэтому можно сделать вывод, что теория игр является полезным логическим аппаратом для анализа мотивов поведения участников в подобных ситуациях. Она располагает целым арсеналом формализованных сценариев поведения, начиная с некооперативного поведения и до кооперативных соглашений с использованием взаимных угроз. Для каждой игры в нормальной форме использование различных кооперативных и некооперативных концепций равновесия, как правило, приводит к различным исходам. Их сравнение является основным принципом теоретико-игрового анализа и, источником строгих содержательных рассуждений о побудительных мотивах поведения вытекающих только из структуры игры в нормальной форме.
Математическая теория предлагает для решения поставленных задач теорию игр, определяемую как раздел математики, ориентированный на построение формальных моделей принятия оптимальных решений в ситуации конкурентного взаимодействия. Данное определение главной задачей теории игр ставит последовательность действий эффективного поведения в условиях конкуренции, конфликтности.).
В теории игр участников конкурирующего взаимодействия называют игроками, каждый из них имеет непустое множество допустимых действий, совершаемых им по ходу игры, которые называются ходами или выборами. Набор всех возможных ходов по одному из списка возможных ходов каждого игрока (участвующих в парах, тройках и т.д. ходов) называется стратегией. Грамотно построенные стратегии взаимно исключают друг друга, т.е. взаимно исчерпывают все способы поведения игроков. Исходом игры называется реализация игроком выбранной им стратегии. Каждому исходу игры соответствует определяемое игроками значение полезности (выигрыша), называемое платежом.
Классификацию игр можно проводить: по количеству игроков, количеству стратегий, характеру взаимодействия игроков, характеру выигрыша, количеству ходов, доступности информации.
1. В зависимости от количества игроков различают парные игры и игры n игроков. Игры трёх и более игроков исследовать сложнее из-за трудностей реализации алгоритмов решения.
2. По количеству стратегий игры бывают конечные и бесконечные. Конечной называется игра с конечным числом возможных стратегий игроков. Если же хотя бы один из игроков имеет бесконечное количество возможных стратегий, то игра называется бесконечной.
3. По характеру взаимодействия игры делятся на:
· бескоалиционные: игроки не имеют права вступать в соглашения, образовывать коалиции;
· коалиционные (кооперативные) - игроки могут вступать в коалиции.
В кооперативных играх коалиции жестко заданы на этапе постановки задачи и не могут меняться во время игры.
4. По характеру выигрышей игры делятся на:
· игры с нулевой суммой (общий капитал всех игроков не меняется, а перераспределяется между игроками; сумма выигрышей всех игроков равна нулю);
· игры с ненулевой суммой.
5. По виду функций выигрыша игры делятся на: матричные, биматричные, непрерывные, выпуклые, и др.
Матричная игра - это конечная парная игра двух игроков с нулевой суммой, в которой задаётся выигрыш игрока 1 в виде матрицы (строка матрицы соответствует номеру применяемой стратегии игрока 2, столбец - номеру применяемой стратегии игрока 2; на пересечении строки и столбца матрицы находится выигрыш игрока 1, соответствующий применяемым стратегиям).
Для матричных игр доказано, что любая из них имеет решение и оно может быть легко найдено путём сведения игры к задаче линейного программирования.
Биматричная игра - это конечная игра двух игроков с ненулевой суммой, в которой выигрыши каждого игрока задаются матрицами отдельно для соответствующего игрока (в каждой матрице строка соответствует стратегии игрока 1, столбец - стратегии игрока 2, на пересечении строки и столбца в первой матрице находится выигрыш игрока 1, во второй матрице - выигрыш игрока 2.)
Для биматричных игр есть теория оптимального поведения игроков, однако решать такие игры сложнее, чем матричные. Непрерывной считается игра, в которой функция выигрышей каждого игрока является непрерывной в зависимости от стратегий. В теории математики доказано, что игры этого класса имеют решения, однако пока не разработано практически приемлемых методов их нахождения.
Целью любой игры является максимизация каждым игроком своей выгоды. Смысл математической теории игр, построенной на приведенной выше классификации, состоит в формализации (упрощении) и облегчении оптимального выбора. Множество всех возможных стратегий игр составляет большое число, растущее тем сильнее, чем больше игроков и набор доступных каждому ходов. Так для пары игроков, если условия игры позволяют каждому совершить по n ходов, в игре существует 2n стратегий.
Простой перебор и оценка (сравнение) такого числа стратегий представляют собой очень сложную задачу, и неприемлемы на практике. Математический аппарат позволяет значительно снизить число требующих анализа и сравнения стратегий, отбросив заведомо неэффективные. Когда же получен ограниченный, разумный для анализа набор точек равновесия (одинаково предпочитаемых всеми игроками исходов игры), на основе анализа выигрышей игроков, выбирается наиболее рациональный результат. При выборе результата существуют два основных подхода, которые дают название окончательной стратегии игры:
· Минимаксная стратегия (выбор из максимальных (наихудших) проигрышей минимальных (наилучших).
· Максиминная стратегия (выбор из минимальных (наихудших) выигрышей максимальных (наилучших).
Развитием теории игр с использованием методов вероятностного анализа является математическая теория принятия решений. Эта теория оперирует не действительным (актуальным) решением, а средним, которое есть ожидаемое решение игры в течение ее многократного повторения. Данное свойство актуально для решения правовых задач, поскольку нормативный характер права означает, что оно ориентировано на неопределенного субъекта и предполагает многократное повторение правоотношений. Чтобы не вдаваться в глубокие математические выкладки, отметим лишь, что теория принятия решений предлагает систему критериев, (например, критерий Гурвица, Ходжи-Лемана, Байесса, критерий ожидаемого значения) которые с помощью вероятностного анализа исходов игр позволяют осуществить выбор оптимального решения в условиях риска и неопределенности.
биматричный игра математический парето
2.Практическая часть
2.1 Биматричные игры
Математической моделью конфликтов с двумя участниками являются биматричные игры. Такая игра 2х2 задается матрицей А=(aij) и B=(bij). В кооперативном варианте такой игры игроки могут согласованно выбирать элемент матрицы. Если они выбрали элемент (a, b), то Первый игрок получает a , а Второй получает b . Цели игроков одинаковы - выиграть как можно больше в расчете на партию в среднем. Пусть (x, y), (a, b) - две точки из CE. Говорят, что (x, y) доминирует (a b) если x?a, y?b и хотя бы одно из этих неравенств строгое. Недоминируемые точки называются оптимальными по Парето, а их множество - множеством оптимальности по Парето. Оно определяется так: пусть Vk - максимальный выигрыш, который k-й игрок может обеспечить себе при любой стратегии другого игрока, тогда переговорное множество определяется как множество тех точек множества Парето, у которых k-я координата не меньше Vk. Для нахождения Vk на до решить две задачи ЛП:
V1>max, a11*x+a21*(1-x) ?V1,a11*x+a12*(1-x)?V1, 0?x?1;
V2>max, a11*y+a12*(1-y) ?V2,a21*y+a22*(1-y)?V2, 0?y?1.
Рассмотрим биматричную игру с 2 х 2-матрицами
и
Пусть и -- средние выигрыши игроков А и В.
Ситуация (р*, q*) в биматричной игре А и В наказывается оптимальной по Парето, если из того, что
и
вытекают равенства
Иными словами, в оптимальной по Парето ситуации игроки не могут совместными усилиями увеличить выигрыш одного из игроков, не уменьшив при этом выигрыш другого.
Различие ситуации равновесия от ситуации, оптимальной по Парето, состоит в следующем:
· В ситуации равновесия ни один из игроков, действуя в одиночку, не может увеличить своего собственного выигрыша;
· В ситуации, оптимальной по Парето, игроки, действуя совместно, не могут увеличить выигрыш каждого.
2.2 Оптимальность по Парето
Содержательные представления об устойчивости, выгодности и справедливости многообразны. Выше мы рассматривали проявление устойчивости через равновесие. Существует и иной вариант устойчивости ситуации, в большей степени, чем равновесность, отражающий черты ее выгодности. Это оптимальность по Парето.
Множество Парето
Рассмотрим на плоскости (U, V) множество Щ (рис. 1). Каждая его точка обладает одним из следующих свойств: либо все точки, ближайшие к ней, принадлежат множеству Щ (такая точка называется внутренней точкой множества Щ), либо сколь угодно близко от нее расположены как точки множества Щ, так и точки, множеству Щ не принадлежащие (такие точки называются граничными точками множества Щ). Граничная точка может как принадлежать множеству Щ, так и не принадлежать. Здесь рассматривается только такие множества, которым принадлежат все точки границы. Множество всех граничных точек множества называется его границей. Обозначение: дЩ.
Рис. 1 Рис. 2
Пусть М -- произвольная точка множества Щ, внутренняя или граничная, и (U, V) --ее координаты. Вопрос: можно ли, оставаясь во множестве Щ, переместиться из точки М в близкую точку так, чтобы при этом увеличились обе ее координаты. Если М -- внутренняя точка, то это бесспорно возможно. Если же М -- граничная тонка, то такое возможно не всегда (рис. 2). Из точек М1, М2, М3 это можно сделать, но уже из точек вертикального отрезка АВ можно переместиться, увеличивая лишь координату V (координата U при этом остается неизменной). Перемещая точку горизонтального отрезка PQ вправо, мы увеличиваем координату U (при этом координата V сохраняет свое значение). Что же касается дуги BQ, то перемещение вдоль нее способно увеличить лишь одну из координат при одновременном уменьшении другой.
Тем самым, точки множества Щ можно разбить на три класса:
· В первый класс относятся точки, которые, оставаясь во множестве и, можно сдвинуть так, чтобы одновременно увеличились обе координаты (в этот класс попадают все внутренние точки множества Щ и часть его граничных точек),
· Второй класс образуют точки, перемещением которых по множеству Щ можно увеличить только одну из координат при сохранении значения второй (вертикальный отрезок АВ и горизонтальный отрезок PQ на границе множества Щ),
· В третий класс попадут точки, перемещение которых по множеству Щ способно лишь уменьшить либо одну из координат, либо обе (дуга BQ границыдЩ) (рис. 10).
Множество точек третьего класса называется множеством Парето, или границей Парето данного множества Щ (выделено на рис. 3).
Рис. 3 Рис. 4
2.3 Метод идеальной точки
Пусть на плоскости (х, у) задано множество щ (рис. 4) и в каждой точке этого множества определены две непрерывные функции
U = Ф(х, у) и V = ш(х, у)
Рассмотрим следующую задачу.
Во множестве щ найти точку (х*, у*), в которой
и
Обычно это записывается так
Ф(х, у) > max и ш(х, у) > max
В общем случае поставленная задача решения не имеет. В самом деле, нарисуем на плоскости (U, V) все точки, координаты которых вычисляются по формулам
U = Ф(х, у) и V = ш(х, у),
Из рис. 5 видно, что наибольшее значение U - Umax -- и наибольше значение V - Vmax -- достигаются в разных точках, а точка с координатами
(Umax , Vmax)
лежит вне множества Щ.
Тем самым, в исходной постановке задача, вообще говоря, неразрешима -- удовлетворить обоим требованиями одновременно невозможно. И, следовательно, нужно искать компромиссное решение.
Опишем один из путей, использующий множество Парето.
Рис. 5 Рис. 6
Сначала на плоскости (U, V) задается целевая точка, в качеств координат которой часто выбирается сочетание наилучших значений обоих критериев U и V.
В данном случае это точка (Umax , Vmax).
Вследствие того, что обычно такая точка при заданных ограничениях не реализуется, ее называют точкой утопии.
Затем строится множество Парето и на нем ищется точка, ближайшая к точке утопии -- идеальная точка (рис. 6).
2.4 Оптимальность по Парето в биматричной игре
Обратившись к игре «Дилемма узников», покажем, как практически отыскиваются оптимальные по Парето ситуации.
Рис. 7
Напомним, что соответствующие платежные матрицы в этой игре имели следующий вид
Тем самым, на единичном квадрате
(рис. 14) возможных значений вероятностей р и q заданы две функции
Точки с координатами (U, V), вычисленными по приведенным формулам, на плоскости (U, V) заполняют четырехугольник с вершинами К(-1, -1), L(-9, 0),М(-6, -6) и N(0, -9) (рис. 8). Граница Парето этого множества -- ломаная NKL.
Рис. 8 Рис. 9
Каждый из игроков заинтересован в наибольшем значении своего среднего выигрыша
Нетрудно заметить, что в данном случае
Umax = 0 и Vmax = 0.
Тем самым, точкой утопии в этой задаче является начальная точка О (0, 0). Ближайшая к ней точка множества Парето -- К (-1, -1) (рис. 9).
Идеальная точка К (-1, -1) -- точка с наибольшими выигрышами для каждого из игроков -- оказывается лучше, чем равновесная точка М(-6, -6), и ей соответствуют чистые стратегии обоих игроков
p = 1, q = 1.
Размещено на Allbest.ru
...Подобные документы
Особенности формирования математической модели принятия решений, постановка задачи выбора. Понятие оптимальности по Парето и его роль в математической экономике. Составление алгоритма поиска парето-оптимальных решений, реализация программного средства.
контрольная работа [1,2 M], добавлен 11.06.2011Конфликтные ситуации в управленческой деятельности. Использование математического моделирования для решения управленческих задач. Определение биматричной игры и общий принцип ее решения. Состояние равновесия в смешанных стратегиях в биматричных матрицах.
реферат [26,9 K], добавлен 21.12.2010Элементы теории матричных игр. Способы решения матричных игр. Различия в подходах критериев оптимальности при определении оптимальной стратегии в условиях статистической неопределенности. Нахождение седловой точки игры. Графическое решение матричной игры.
контрольная работа [366,9 K], добавлен 12.05.2014Предмет и задачи теории игр. Сведение матричной игры к задачам линейного программирования. Основные принципы разработки деловых игр для исследования экономических механизмов. Деловая игра "Снабжение". Решение матричной игры в смешанных стратегиях.
курсовая работа [1,8 M], добавлен 15.10.2012Математическая теория оптимального принятия решений. Табличный симплекс-метод. Составление и решение двойственной задачи линейного программирования. Математическая модель транспортной задачи. Анализ целесообразности производства продукции на предприятии.
контрольная работа [467,8 K], добавлен 13.06.2012Основные методы решения задачи оптимального закрепления операций за станками. Разработка экономико-математической модели задачи. Интерпретация результатов и выработка управленческого решения. Решение задачи "вручную", используя транспортную модель.
курсовая работа [1,0 M], добавлен 25.01.2013Модели распределения доходов. Количественный подход к анализу полезности и спроса. Отношение предпочтения и функция полезности. Кривые безразличия, решение задачи оптимального выбора потребителя. Функции спроса, изменение цен и коэффициент эластичности.
курсовая работа [412,7 K], добавлен 11.02.2011Типы транспортных задач и методы их решения. Поиск оптимального плана перевозок методом потенциалов. Решение задачи с использованием средств MS Excel. Распределительный метод поиска оптимального плана перевозок. Математическая модель, описание программы.
курсовая работа [808,7 K], добавлен 27.01.2011Основные положения теории игр. Терминология и классификация игр. Решение матричных игр в чистых и в смешанных стратегиях. Сведение матричной игры к задаче линейного программирования. Применение теории игр в задачах экономико-математического моделирования.
курсовая работа [184,5 K], добавлен 12.12.2013Классическая теория оптимизации. Функция скаляризации Чебышева. Критерий Парето-оптимальность. Марковские процессы принятия решений. Метод изменения ограничений. Алгоритм нахождения кратчайшего пути. Процесс построения минимального остовного дерева сети.
контрольная работа [182,8 K], добавлен 18.01.2015Построение экономико-математической модели задачи, комментарии к ней и получение решения графическим методом. Использование аппарата теории двойственности для экономико-математического анализа оптимального плана задачи линейного программирования.
контрольная работа [2,2 M], добавлен 27.03.2008Разработка математической модели оптимальной расстановки игроков футбольной команды на поле с учетом распределения игровых обязанностей между футболистами и индивидуальных особенностей каждого для достижения максимальной эффективности игры всей команды.
курсовая работа [1,7 M], добавлен 04.08.2011Стохастические игры как разновидность многошаговых игр, в которых переход от одной позиции к другой совершается с определенной вероятностью. Расчетные методы их решения. Разработка и тестирование программного средства для решения игры "Герб-Решетка".
контрольная работа [364,0 K], добавлен 20.02.2013Рассмотрение теоретических и практических аспектов задачи принятия решения. Ознакомление со способами решения с помощью построения обобщенного критерия и отношения доминирования по Парето; примеры их применения. Использование критерия ожидаемого выигрыша.
курсовая работа [118,8 K], добавлен 15.04.2014Графический метод решения задачи оптимизации производственных процессов. Применение симплекс-алгоритма для решения экономической оптимизированной задачи управления производством. Метод динамического программирования для выбора оптимального профиля пути.
контрольная работа [158,7 K], добавлен 15.10.2010Исследование модели поведения на рынке двух конкурирующих фирм, выпускающих аналогичный пользующийся неограниченным спросом товар, с точки зрения теории игр. Определение прибыли игроков. Динамика изменения капитала во времени по секторам экономики.
контрольная работа [139,0 K], добавлен 20.01.2016Теория игр в контексте теории принятия решений. Игры без седловых точек. Использование линейной оптимизации при решении матричных игр. Критерии, используемые для принятия решений в играх с природой. Решение парных матричных игр с нулевой суммой.
контрольная работа [437,2 K], добавлен 14.02.2011Решение задачи линейного программирования графическим способом. Определение экстремальной точки. Проверка плана на оптимальность. Правило прямоугольников. Анализ и корректировка результатов решения задач линейного программирования симплексным методом.
контрольная работа [40,0 K], добавлен 04.05.2014Модели распределения доходов. Количественный подход к анализу полезности и спроса. Кривые безразличия, решение задачи об оптимальном выборе потребителя. Функции спроса и коэффициент эластичности. Предельная полезность и предельная норма замещения.
презентация [470,8 K], добавлен 28.04.2013Составление математической модели и решение задачи планирования выпуска продукции, обеспечивающего получение максимальной прибыли. Нахождение оптимального решения двойственной задачи с указанием дефицитной продукции при помощи теорем двойственности.
контрольная работа [232,3 K], добавлен 02.01.2012
