Математическая теория игр

Министерство образования и науки Российской Федерации

Федеральное государственное  автономное образовательное учреждение

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

«Дальневосточный  федеральный университет»

(ДВФУ)

филиал в  г. Арсеньеве

 

 

Школа экономики  и менеджмента

 

 

 

 

 

КУРСОВАЯ  РАБОТА

 

По дисциплине: Математические методы в экономике    

Тема: Математическая теория игр        

 

 

 

Студент(ка) С17408 гр.Епифанцев И.С

 

Руководитель  Васько Ю.Е.  

                              

Курсовая работа допущена к защите:

«____»    _________________ 2011 г.

Курсовая работа защищена

с оценкой:______________________ 

 «____»    _________________ 2011 г.

 

 

 

 

 

 

Арсеньев - 2011

 

СОДЕРЖАНИЕ

 

 

 

ВВЕДЕНИЕ

 

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

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

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

1. рассмотреть основные теоретические аспекты математической теории игр, дать описание основным видам теории игр, рассмотреть основные аспекты математической модели;
2. сформулировать условие задачи теории игр для игрока (экономического субъекта), дать математическую и экономическую формулировку задачи, сделать анализ и интерпретацию результатов решения задачи;
3. осуществить проектирование поставленной задачи на ЭВМ с помощью программного комплекса Borland Delphi 7;
4. сделать выводы о применении теории игр к решению экономических и стратегических управленческих задач.

Были использованы научные  труды таких известных ученых, как Бережная Е.В. и Бережной В.И., Красс М.С. и Чупрынов Б.П., Росс С.И., Кундышева Е.С. и многих других.

 

1 ТЕОРЕТИЧЕСКИЕ АСПЕКТЫ МАТЕМАТИЧЕСКОЙ ТЕОРИИ ИГР

1.2 Теория игр как раздел теории принятия решений

 

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

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

Теория игр относится  к математическому обеспечению  моделирования явлений в основном социально-экономического характера [21, c. 42].

Принятие решений - это  достаточно широкое понятие. С точки  зрения математического описания под принятием решения понимается выбор из некоторого множества I элемента i. При этом определяется правило выбора и целесообразность выбора.

Математическая теория принятия оптимальных (рациональных, целенаправленных) решений называется теорией исследования операций. Таким образом, задачей теории исследования операций является построение количественных методов анализа процессов принятия решений во всех областях человеческой деятельности.

Совокупность  целенаправленных действий, т.е. действий, направленных на достижение некоторых целей, называется операцией.

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

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

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

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

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

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

Он может быть задан  следующими компонентами:

1. перечнем субъектов, участвующих в конфликте;
2. определением множеств их выборов;
3. интересами (мотивами), определяющими выбор.

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

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

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

Однако даже математическая теория игр не способна стопроцентно предопределить исход некоторых  конфликтов. Представляется возможным выделить три основные причины неопределенности исхода игры (конфликта).

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

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

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

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

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

Всякая математическая модель социально-экономического явления или конфликта должна выражать присущие ему черты:

1) заинтересованные стороны;

2) возможные действия каждой из сторон;

3) интересы сторон.

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

Любое возможное для  игрока действие называется его стратегией.

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

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

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

 

.     (1.1)

 

Игра – это совокупность правил, описывающих сущность конфликтной ситуации. Эти правила устанавливают:

1) выбор образа действия игроков на каждом этапе игры;

2) информацию, которой обладает каждый игрок при осуществлении таких выборов;

3) плату для каждого игрока после завершения любого этапа игры.

Игру можно  определить следующим образом:

1) имеются n конфликтующих сторон (игроков), принимающих решения, интересы которых не совпадают;

2) сформулированы правила выбора допустимых стратегий, известные игрокам;

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

4) всем игрокам (участникам игры) заранее известны платежи, соответствующие каждому возможному конечному состоянию. Платежи задаются в виде матрицы .

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

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

Задание стратегий (А и В) двух игроков в парной игре полностью определяет ее исход, т.е. выигрыш одного или проигрыш другого. Игра называется конечной, если у каждого игрока имеется конечное число стратегий. Результаты конечной парной игры с нулевой суммой можно задавать матрицей, строки и столбцы которой соответствуют различным стратегиям, а ее элементы — выигрышам одной стороны (равные проигрышам другой). Эта матрица называется платежной матрицей или матрицей игры   [3, c. 41].

Классификация игр строится на основе следующих признаков:

1. Число участников  – одиночные, парные, с тремя участниками, с четверыми участниками и т.д.
2. Число стратегий – конечные (каждый игрок располагает конечным множеством ходов) и бесконечные (по крайней мере один игрок располагает бесконечным множеством ходов, к примеру игра биологического вида с природой).
3. Характер отношений игроков – бескоалиционные игры, игроки в которых играют каждый за себя и кооперативные игры, игроки объединяются в коалиции с одинаковыми на время игры интересами.
4. Характер выигрыша – игры с нулевой суммой (сумма общего выигрыша не меняется,  а лишь перераспределяется или сумма выигрышей всех игроков во всех партиях данной игры  нулевая) и игры с ненулевой суммой, к примеру, лотерея, в которой организатор всегда выигрывает, а другие игроки (покупатели билетов) всегда получают суммарный выигрыш значительно меньший стоимости билетов.
5. Число ходов – одноходовые и многоходовые, последние из которых разделяются  на стохастические, дифференциальные.
6. Состояние информации игры – игры с полной информацией (игроки получают всю игровую информацию после очередного хода соперника) и игры с неполной, или со скрытой информацией [26, c. 39].

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

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

 

.     (1.2)

 

Пусть каждой стратегии первого игрока взаимооднозначно поставлена в соответствие строка некоторой матрицы А, а каждой стратегии второго игрока взаимооднозначно поставлен в соответствие столбец этой матрицы. Матрицу А называют платежной (или матрицей игры), если её элемент a_ij равен выигрышу первого игрока (т.е. проигрышу второго) при выборе первым игроком i-й стратегии, а вторым –j-й.

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

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

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

2) принцип оптимальности – описание правил рационального поведения игроков.

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

Математическая модель конфликта  и принцип оптимальности дают полное описание принятия решений в условиях конфликта.

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

1. Коалиции действий – совокупность действующих совместно в данной конфликтной ситуации субъектов.
2. Коалиции интересов – множество одинаково заинтересованных в исходе конфликта сторон.
3. Множества возможных выборов каждой из коалиций действия.
4. Описание предпочтений каждой из коалиций интересов.
5. Множество возможных исходов конфликта.

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

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

Заинтересованность j-го субъекта формализуется, как правило, функцией выигрыша, которая определяется отображением , где U - множество исходов. Выбор стратегии или управления определяется принципом оптимальности.

Таким образом, для описания конфликтной ситуации необходимо задать систему (1.3)

 

,    (1.3)

где N -множество игроков,

K_g - множество коалиций действия,

K_и - множество коалиций интересов,

U_i - множество выборов коалиции ,

g_j - функция выигрыша коалиции ,

S - множество возможных исходов игры.

 

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

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

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

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

1.2 Понятие  и принципы оптимальности в  математической теории игр

 

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

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

Основными содержательными  чертами оптимальности в применении к исходу или к множеству исходов конфликта можно считать интуитивные представления о выгодности и справедливости [21, c. 42].

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

1. Сделать оптимальный выбор.
2. Оценить результат при сделанном выборе.

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

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

 

,      (1.4)

 

реализующих максимум функций  . Данная игра эквивалентна задаче оптимизации.

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

Термин «оптимальный выбор» однозначно понимается при исследовании антагонистической игры , в которой существует седловая точка, т.е. выполняется равенство (1.5)

 

.   (1.5)

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

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

 

.    (1.6)

 

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

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

1. Должен быть таким, чтобы существовал оптимальный выбор, т.е. отображение φ не приводило к пустому множеству рациональных выборов.
2. Должен максимально сужать степень неопределенности, как во множестве выборов, так и в оценке ожидаемого результата.
3. Должен быть прост и понятен, чтобы можно было практически вычислить множество рациональных решений и оценить с большой степенью точности ожидаемый выигрыш; полученные результаты должны хорошо интерпретироваться на содержательном уровне.
4. Должен обладать устойчивостью, т.е. решение игры должно мало меняться при небольшом изменении параметров модели конфликтной ситуации.

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

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

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

 

.      (1.7)

 

Основными свойствами рациональности коллективных принципов оптимальности  являются:

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