Методы и модели теории игр

Размещено на http://www.allbest.ru/

Департамент образования города Москвы

Государственное бюджетное образовательное учреждение

высшего профессионального образования города Москвы

«Московский городской педагогический университет»

Институт психологии, социологии и социальных отношений

Реферат

По дисциплине:

“Математические методы моделирования социологических процессов”

Тема:

Методы и модели теории игр

Выполнил:

студент 3 курса

заочной формы обучения

специальность «Социология»

Нарышкин А.Е.

Москва

2012

Содержание

Введение

1. Понятие о моделях и моделировании

2. Методы и модели теории игр

3. Основные понятия теории игр

4. Понятие об игровых моделях

3. Пример решения задачи 1

4. Пример решения задачи 2

Литература

Введение

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

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

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

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

1. Понятие о моделях и моделировании

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

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

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

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

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

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

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

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

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

2. Методы и модели теории игр

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

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

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

3. Основные понятия теории игр

Конфликтующие стороны называются игроками, одна реализация игры -- партией, исход игры -- выигрышем или проигрышем. Развитие игры во времени происходит последовательно, по этапам или ходам. Ходом в теории игр называют выбор одного из предусмотренных правилами игры действия и его реализацию. Ходы бывают личные и случайные. Личным ходом называют сознательный выбор игроком одного из возможных вариантов действия и его осуществление. Случайным ходом называют выбор, осуществляемый не волевым решением игрока, а каким-либо механизмом случайного выбора (бросание монеты, пасовка, сдача карт и т.п.).

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

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

4. Понятие об игровых моделях

В зависимости от причин, вызывающих неопределенность исходов, игры можно разделить на следующие основные группы:

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

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

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

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

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

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

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

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

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

5. Методы и модели решения игровых задач

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

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

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

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

Игровые модели в условиях коммерческого риска. Для принятия решений в условиях риска используют методы теории вероятностей по причине массовости явления. В таком случае факторы, например, состояния среды представляют собой либо случайные величины, либо случайные функции. Они описываются какими-либо статистическими характеристиками, например, математическим ожиданием и дисперсией, и обладают статистической устойчивостью. Принимающий решение ориентируется на средние, наиболее вероятные результаты, однако при этом не исключен риск получения не того результата, на который была рассчитана коммерческая стратегия, тогда мерой риска следует считать среднее квадратическое отклонение. Ситуации, в которых риск связан не с сознательным противодействием противоположной стороны (среды), а с недостаточной осведомленностью о ее поведении или состоянии лица, принимающего решение, называются «играми с природой». В таких играх человек старается действовать осмотрительно, например, используя стратегию, позволяющую получить наименьший проигрыш. Второй игрок (природа) действует незлонамеренно, совершенно случайно, возможные стратегии его известны (стратегии природы). Такие ситуации исследуются с помощью теории статистических решений.

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

Игровые модели конфликтов. Математическая теория игр дает научно обоснованные рекомендации поведения в конфликтных ситуациях, показывая «как играть, чтобы не проиграть». Для применения этой теории необходимо уметь представлять конфликты в виде игр. В процессе коммерческих переговоров приходится искать область взаимных интересов, позволяющую найти компромиссное решение. Делая большие уступки по менее значимым аспектам для фирмы, но более значимым для оппонента, коммерсант получает больше по другим позициям, которые более значимы и выгодны для фирмы. Эти уступки имеют минимальные и максимальные границы интересов. Это условие получило название «принцип Парето» по имени итальянского ученого В. Парето. Одним из типичных социально-психологических межличностных конфликтов является несбалансированное ролевое взаимодействие. Теоретическую основу анализа межличностных конфликтов предложил американский психолог Э. Берн, который дал описание взаимодействия партнеров в виде сетевых моделей. Каждый человек в процессе взаимодействия с окружающими вынужден играть более десятка ролей, причем далеко не всегда

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

6. Пример решения задачи 1

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

Условие: две компании, А и В, продают два вида лекарств против гриппа. Компания А рекламирует продукцию на радио (А1), телевидении (А2) и в газетах (А3). Компания В, так же, в рекламных целях использует радио (В1), телевидение (В2) и газеты (В3). В зависимости от умения и интенсивности проведения рекламной кампании, каждая из компаний может привлечь на свою сторону часть клиентов конкурирующей компании. Приведенная ниже матрица характеризует процент клиентов, привлеченных или потерянных компанией А.

Задание: найти оптимальное решение для каждого игрока.

Решение: решение игры основано на обеспечении наилучшего результата из наихудших для каждого игрока. Если компания А выбирает стратегию А1, то, независимо от того, что предпринимает компания В, наихудшим результатом является потеря компанией А 3 % рынка в пользу компании В. Это определяется минимумом элементов первой строки матрицы платежей. Аналогично при выборе стратегии А2 наихудшим исходом для компании А является уменьшение рынка на 2 % в пользу компании В. Наконец, наихудшим исходом при выборе стратегии А3 является потеря компанией А 6 % рынка в пользу компании В.

Эти результаты содержатся в столбце ``Минимумы строк''.

Чтобы достичь наилучшего результата из наихудших, компания А выбирает стратегию А2, так как она соответствует наибольшему максиминному элементу столбца ``Минимумы строк''.

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

Значение цены игры V находится между -2 и 2 - минимальные проигрыши обоих игроков.

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

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

Смешанные стратегии игрока А: А1,А2,…Аm можно обозначить как:

S1=(X1,X2,…Xm)

X1,X2,…Xm - вероятности использования первым игроком стратегий А1,А2…Аm, где:

Xi ? 0,

Смешанную стратегию игрока А можно записать:

Смешанные стратегии игрока В: В1, В2,…Вn можно обозначить как:

S2=(Y1,Y2,…Yn)

Y1,Y2,Yn - вероятности использования вторым игроком стратегий В1,В2,…Вn, где:

Yj ? 0,

Смешанную стратегию игрока В можно записать:

Тогда оптимальные значения вероятностей Xi, i = 1, 2, ..., m, игрока А могут быть определены путем решения следующей максиминной задачи:



Для преобразования записи в задачу линейного программирования:

Отсюда:

Следовательно:

Оптимальным решением для первого игрока является: Х1=0,39, Х2=0,31, Х3=0,29, V=-0,91

Для второго игрока аналогично:

Оптимальным решением для второго игрока является: Y1=0,32, Y2=0,08, Y3=0,60, V=-0,91

Ответ: цена игры составляет V=-0,91, при этом:

минимальная средняя потеря рынка сбыта для игрока А составляет 0,91% при проведении рекламных компаний на телевидении: 39%, на радио: 31%, в газетах: 29%;

минимальное среднее увеличение рынка сбыта для игрока В составляет 0,91% при проведении рекламных компаний на телевидении: 32%, на радио: 8%, в газетах: 60%.

Пример решения задачи 2

Решение задачи на основе Теории принятия решений.

Принятие решения в условиях определённости.

Решение задачи по расчёту модели методом линейного программирования.

Условие: ученик средней школы получил на выпускном экзамене ЕГЭ баллы, достаточные для поступления в университеты А, В и С. Для того чтобы выбрать университет, ученик сформулировал два основных критерия: расстояние от университета до дома и его рейтинг среди университетов.

Задание: найти наиболее оптимальный вариант поступления в университет.

Решение: будучи отличным учеником, абитуриент оценивает рейтинг университета в пять раз выше, чем его местонахождение. Это приводит к тому, что для идеального варианта выбора вес рейтинга университета (R) будет составлять примерно 83 %, а вес его расстояния до дома (L) 17 %, т.е.:

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

R - рейтинг;

L - расстояние до дома

По рассуждению абитуриента:

R=1/5*L

Уровень преимущества одного элемента над другим определяется по девятибальной шкале Саати:

1 - если отсутствует преимущество одного элемента над другим элементом;

3 - если имеется слабое преимущество одного элемента над другим элементом;

5 - если имеется существенное преимущество одного элемента над другим элементом;

7 - если имеется явное преимущество одного элемента над другим элементом;

9 - если имеется абсолютное преимущество одного элемента над другим элементом;

2,4,6,8 - промежуточные сравнительные оценки.

Все диагональные элементы матрицы должны быть равны 1, так как они выражают оценку критерия относительно самих себя.

Относительные веса критериев R и L могут быть определены путем деления элементов каждого столбца на сумму элементов этого же столбца. Следовательно, для нормализации матрицы А делим элементы первого столбца на величину 1 + 5 = 6, элементы второго на величину 1 + 1/5 = 1,2. Искомые относительные веса WR и WL критериев вычисляются теперь в виде средних значений элементов соответствующих строк нормализованной матрицы А.

Следовательно:

Соответственно, для идеального варианта:

вес рейтинга университета = 0,83 = 83%

вес расстояния от университета до дома = 0,17 = 17%

Относительные веса альтернативных решений, соответствующих университетам А, В и С, вычисляются в пределах каждого критерия R и L с использованием следующих двух матриц сравнения (элементы матриц определены на основе суждений абитуриента):

1. сравнение университетов относительно расстояний от них до дома абитуриента:

Суммы элементов столбцов:

1+2+5=8

Ѕ+2+2=3,5

1/5+1/2+1=1,7

2. сравнение университетов по их рейтингу:

Суммы элементов столбцов:

1+1/2+1/3=1,83

2+1+2/3=3,67

3+3/2+1=5,5

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



Величины (WRA, WRB, WRC) = (0,545, 0,273, 0,182) дают соответствующие веса для университетов А, В и С с точки зрения рейтинга среди университетов. Аналогично величины (WLA, WLB, WLC) = (0,129, 0,277, 0,594) являются относительными весами, касающимися местонахождения университетов.

Оценка трех университетов основана на вычислении комбинированного весового коэффициента для каждого из них:

Университет А: 0,17 Ч 0,129 + 0,83 Ч 0,545 = 0,4743.

Университет В: 0,17 Ч 0,277 + 0,83 Ч 0,273 = 0,2737.

Университет С: 0,17 Ч 0,594 + 0,83 Ч 0,182 = 0,2520.

На основе этих вычислений университет А получает наивысший комбинированный вес - 47,43% и, следовательно, является наиболее оптимальным выбором для абитуриента.

Литература

1. Фомин Г.П., «Математические методы и модели в коммерческой деятельности»: Учебник. -- 2-е изд., перераб. и доп. -- М.: Финансы и статистика, 2005. -- 616 с.

2. Вилкас Э., "Теория вероятности и ее применение", 1963, т. 8, в. 3, с. 324-27

3. А.М. Дубров, Б.А. Лагоша Е.Ю. Хрусталев, «Моделирование рисковых ситуации в экономике и бизнесе», М.: Финансы и статистика, 2000.

4. С.Д. Штовба, «Введение в теорию нечетких множеств и нечеткую логику», Горячая Линия - Телеком, 2007. - 288 с.

Размещено на Allbest.ru