Реферат: Теория принятий решений

ТЕОРИЯ ПРИНЯТИЯ РЕШЕНИЙ

Курс лекций.

Урицкая О.Ю.

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

Основополагающийпринцип ТПР, сформулировали Нейман и Моргенштерн: лицо, принимающее решение,должно всегда выбирать альтернативу с максимально ожидаемой полезностью. Этотрезультат строится на ряде аксиом, его называют гипотезой ожидаемойполезности. Поэтому и задачи формулируются соответственным образом: чемполезнее, предпочтительнее альтернатива — тем выше численная оценка — “чембольше, тем лучше”.

Вобщем случае задача ТПР строится следующим образом: установливаются

1.Все возможные способы действия — альтернативы

2.Их последовательность и числовая оценка

3.Цели участников процесса принятия решений

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

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

Внашем курсе мы воспользуемся классификацией по моделям:

МОДЕЛИ ПРИНЯТИЯ РЕШЕНИЙ

ДЕТЕРМИНИСТИЧЕСКИЕ СТОХАСТИЧЕСКИЕ критериальный анализ теория игр линейное и нелинейное статистические стратегические программирование нестратегические /> /> /> />

определенность<-----------------------------------------> неопределенность

методы

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

Проблемавыбора решения и принципы оптимальности.

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

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

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

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

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

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

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

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

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

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

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

Глава1. ПРИНЯТИЕРЕШЕНИЙ В УСЛОВИЯХ ОПРЕДЕЛЕННОСТИ

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

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

1.1.Постановка задачи. Основные понятия.

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

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

Внашем курсе будем полагать, что U дискретно и счетно, а u — эмпирическийобьект, задаваемый «своим именем» ( например, названия банков ).

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

Вобщем виде: k — функция от альтернативы u: k(u)

U =( u1 ,u2 ,...un ), n — число альтернатив

K(u)= ( k1 (u), k2(u),...km(u)), где m — числочастных критериев ki(u)

1.Еслиm = 1 — однокритериальная задача, то есть задача линейного программирования.

2.Еслиm > 1, но k(u) P k(v) — тривиальный вариант, так как u всегда лучше v.

3.Еслипо одним критериям вариант u предпочтительнее варианта v, а по другим — наоборот, то это задача критериального анализа, способы решения которой будутрасмотрены в этом курсе.

Введемобозначения: K (u) P K (v) — вариант u предпочтительнее, K (u) I K (v) — одинаковы по предпочтени,K(u) N K(v) — несравнимы.

1.2.Формирование критериальной системы.

Дляформулировки задачи критериального анализа необходимо:

1.Четко сформулировать цель, задачу и требуемый результат

2.Классифицировать характеристики вариантов

3.Беспристрастно выбрать критерии

Требования к критериальной системе:

1.Соответствие критериев цели и задаче.

2.Критичность. Критерий должен быть «чувствительным» к изменению варианта выбора.

3.Вычислимость критериев.

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

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

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

Еслиесть U = ( u,v,s,t ) — множество альтернатив и варианты u и v такие, что для «j ¹ i верно kj (u) = kj (v), а ki(u) ¹ ki (v), причем К(u) P К(v); варианты s и tтакие, что для „j ¹ i верно kj (s) = kj (t) ¹ kj (u), при ki (s) = ki (u), ki(t) = ki (v). Если отсюда следует, что К (s) Р К(t), то говорят,что i-тый векторный критерий независим по предпочтению от всех частныхкритериев. В противном случае методически удобнее при решении таких задачперейти к новой постановке, где предпочтительным было бы изменение всех частныхкритериев, например в сторону увеличения. При этом, если в исходной постановкезадачи для части критериев предпочтительнее меньшее значение, то в новойпостановке значения таких критериев рассматриваются с противоположным знаком.

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

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

Необходимоотметить, что переход от независимых частных критериев к зависимым иногдасвязан с более “тонким» анализом самих предпочтений.

1.3.Аксиома Парето и эффективные варианты.

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

Пример. U = (u,v,s,t) — множество альтернатив

u 5 3 7 v 4 3 6 s 5 2 7 t 6 3 1

k(u) ³ k (v), «i =1:3, поэтому K(u)P K(v).

k(u) ³ k (s), „i =1:3, поэтому K(u) P K(s),варианты s и v оказались доминируемыми, а остальные векторные оценки сравнитьневозможно: k (u) N k (t) Таким образом все множество векторных оценок делитсяна два подмножества: эффективных { k(u),k(t)} и неэффективных { k(v), k(s)}векторных оценок. Из приведенного примера можно сделать важный вывод: есливариант имеет абсолютный max по какому-либо показателю, то он не может бытьдоминирован.

АксиомаПарето: Пусть даны две векторныеоценки:

K(u)=( k1 (u), k2 (u),… km (u)) и

K(v)=( k1 (v), k2 (v),… km (v))

K(u)P K(v), если существует хотя бы одно j от 1 до m такое что:

“ i ¹ j ki (u) I ki(v), или ki (u) P ki(v),а kj (u) P kj (v).

P — »предпочтительность в смысле Парето".

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

Длянашего примера: H = { K(u), K(v), K(s), K(t)}, Hо = { K(u), K(t)} — множество эффективных векторных оценок. Определение множеств эффективныхвекторных оценок обычно не позволяет получить в чистом виде решение задачи, ноявляется важным и обязательным этапом, так как практически всегда происходитсокращение имеющихся вариантов, кроме того, для Hо и vомогут выполняться допущения не верные для H и v, то есть задача в дальнейшемможет упрощаться за счет дополнительных правил или информации после сокращения.

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

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

Еслипри выборе того или иного варианта использование принципа Парето не даетединственного решения, необхлдимо найти способы сужения возможного выбора измножества эффективных вариантов. До сих пор предполагалось, что все критрииодинаковы по важности и одинаково влияют на предпочтительность векторногокритерия. На самом деле часто превосходство по наиболее важным частнымкритериям ведет к предпочтительности векторной оценки в целом. Понятиеотносительной важности частных критериев возможно будет определить только когдаони будут сравнимы, ( иначе как определить: что лучше — 200 тонн или 10 км ).Чтобы разшить эту проблему используют процедуру нормализации.

Частные критерии считаются нормализованными,если области их изменения Н i = 1: m совпадают.

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

ki(v) — min ki(v)

ki ‘ (v) = --------------------------

maxi k (v) — minik (v)

Онаудобна тем, что все ki (v)Î [0; 1],причем min k’i(v) = 0, max k’i (v) = 1. Таким образом,нормализованный частный критерий показывает, на какую часть всего диапазонаизменений [0; 1] данный частный критерий превосходит минимальное значение.

Пример.

Исходные значения Нормированные значения

k’1

k’2

k’3

K(u) 80 0,12 0,0030 0,10 0,60 0,77 K(v) 70 0,06 0,0107 1 K(w) 170 0,16 0,0007 1 1

Посленормализации частных критериев векторные критерии приобретают некоторыеполезные свойства. Главное из них — любая перестановка частных критериевприводит к векторной оценке, которая входит в множество значений исходнойвекторной оценки.

Дополнительнаяинформация задается в виде множества символов: равноценность частных критериевkr (u) и kt (u) обозначается r S t. Такая информацияназывается «словом». Слово r B t — информация о том, что частныйкритерий k (u) важнее, чем k (u).

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

1.5.Методы сравнения векторных оценок с использованием дополнительной информации.

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

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

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

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

Глава 2. ПРИНЯТИЕРЕШЕНИЙ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ.

ТЕОРИЯ ИГР.

2.1.Предмет и задачи теории игр.

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

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

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

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

Первыеработы по ТИ ( Цермело, Борель, фон Нейман ) относятся к началу ХХ века. Нотолько появление и широкое распространение ЭВМ привлекло к ТИ вниманиеширокого круга специаоистов.

Теориястратегических игр в своей математической форме возникла в 30-х годах нашеговека. Ее создателем считается Джон фон Нейман. Первой фундаментальной книгой потеории игр была изданная в 1944 году работа «Теория игр и экономическоеповедение»(Нейман Д., Моргенштерн О. М.: Наука,1970)

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

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

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

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

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

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

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

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

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

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

Г= < I, { x }, { H } > = < игроки, стратегии, выигрыши >

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

Стратегии — доступные для игроков действия, в общем случае — это набор правил иограничений.

Ситуации -возможные исходы конфликта. Каждая ситуация — результат выбора каждым игрокомсвоей стратегии.

Стратегические игры — игры, в которых конфликт отражает интересы активных участников, тоесть таких, которые оказывают влияние на выбор стратегий и ситуацию.

1.Предмет и задачи теории игр.

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

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

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

ОСНОВНЫЕПОНЯТИЯ И ОПРЕДЕЛЕНИЯ

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

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

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

ИграГ = < X,Y,H>, где X,Y — непустые множества стратегий соответственнопервого и второго игроков, H — функция выигрыша Н1 = -Н2называется антагонистической.

Впроцессе игры каждый игрок выбирает свою стратегию, в результате чегообразуется ситуация (x,y), которой соответствует выигрыш Н(x,y) для первогоигрока и — Н(x,y) для второго.

Вмножестве всех возможных антагонистических игр выделяются классыаффинно-эквивалентных игр.

Двеантагонистические игры Г = < X,Y,H> и Г’ = < X’,Y’,H’>, называютсяаффинно-эквивалентными, если X = X’, Y = Y’ и H’ = k H + a, где а — вещественное, а k > 0. В этом случае используется обозначение Г ~Г’.

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

Ситуацииравновесия (седловые точки).

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

Вматричных играх ситуация i*, j* называется приемлемой для первого игрока, если aij* £ ai*j* и приемлемой для второго игрока,если ai*j* £ ai*j.

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

Ситуация( i*, j* ) называется равновесной, если она приемлема для обоих игроков. aij* £ ai*j* £ ai*j.Применительно к антагонистическим играм говорят о седловых точках наповерхности выигрыша ( на них достигается max по первой координате и min повторой.

Свойстваседловых точек:

1.Равноценность. Если в игре несколько седловых точек, то значения функциивыигрыша в них одинаковы.

2.Взаимозаменяемость оптимальных стратегий. Игроки могут заменить своиоптимальные стратегии другими оптимальными стратегиями, при этом равновесие ненарушится, а выигрыш (проигрыш) останется неизменным.

Теорема.Аффинно-эквивалентные игры имеют одни и те же седловые точки ( то есть ихрешения совпадают).

Седловыкеточки и минимаксы

Устойчивоерешение игры может быть получено путем следующих рассуждений:

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

aij* = min аij

Сдругой стороны, руководствуясь принципом выгоднгодности первый игрок будетстремиться увеличить свой выигрыш, сохраняя свойство устойчивости, поэтому vн= max min аij

Этонижняя цена игры. Рассуждая подобным образом за второго игрока получим верхнююцену игры:

vв= min max аij

Интуитивноясно, что значение ( цена ) игры лежит между vн и vв.

Теорема.Для того, чтобы в матричной игре существовали минимаксы, необходимо идостаточно, чтобы равны были минимаксы:

maxmin аij= min max аij

Оптимальныесмешанные стратегии и их свойства.

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

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

Смешаннойстратегией игрока в матричной игре называется полный набор вероятностей x = (x1, x2 ... xm) и y = ( y1, y2… yn) применения его чистых стратегий. (чистые стратегии — исходные).

Свойствасмешанных стратегий.

1свойство. Если x" = ( x1, x2,… xm ) иy" = ( y1, y2,...yn ) - оптимальныесмешанные стратегии игроков в матричной игре, то для произвольных стратегий xи y справедливо

Н( А, x", y) = å aij xi" ³ v для всех j=1:n, так как это равносильно использованию вторымигроком чистой j-той стратегии: y = ( 0, 0,...yj=1,… 0, 0 )

Н( А, x, y") = å aij yj" £ v для всех i=1:m, так как это равносильноиспользованию первым игроком чистой i-той стратегии: x = ( 0, 0,...xi=1,…0, 0 )

2свойство. Если в матричной игре с матрицей А и ценой игры v стратегии x" иy" — оптимальные, то

если å aij xi" > v, то yj" = 0

еслиå aij yj" < v, то xi" = 0

еслинеравенства обращаются в равенства, то соответственно:

xi"¹ 0, yj" ¹ 0.

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

2.6.Доминирование в матричных играх.

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

Пусть задана матричная игра с платежной матрицей А, асмешанные стратегии игроков представлены в виде x = ( x1, x2,…xm ) и y = ( y1, y2,… yn). Векторх' строго доминирует вектор х"( вектор x" строго доминируется вектором x' ), если справедливо: xi' > xi",i=1:m. Если неравенство нестрогое, то и доминирование является нестрогим.

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

Еслиx~, y~- пара оптимальных смешанных стратегий игры с матрицей A, то удалив извектора x~ нулевую координату с номером r получим пару оптимальных смешанныхстратегий x`~,y~ игры с матрицей A`, полученной из матрицы A вычеркиваниемстроки с номером r.

Обратноеутверждение тоже верно. Если x`~,y~- пара оптимальных смешанных стратегий игрыс матрицей A`, то добавив в качестве r-той коодинаты вектора x`~ ноль и сдвинувна одно место вправо все координаты вектора x~ с номерами r, r+1… m-1,получим пару оптимальных смешанных стратегий x~,y~ игры с матрицей A.

Теорема.Если строка с номером r в матрице А нестрого доминируется выпуклой линейнойкомбинацией всех остальных строк, то существует оптимальная смешанная стратегияпервого игрока x~, у которой r-тая координата равна нулю.

Любаяпара x`~,y~ оптимальных смешанных стратегий игры с матрицей А` преобразуется впару оптимальных смешанных стратегий x~,y~ игры с матрицей А добавлением нулевойкоординаты с номером r в вектор x`~ и сдвигом координат этого вектора сномерами r, r+1,...m-1 на одно место вправо.

Вовсех этих случаях значение игры с матрицей А совпадает со значением игры сматрицей А~.

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

Еслиx~,y~ — пара оптимальных смешанных стратегий в игре с матрицей А, то удалив извектора y~ нулевую координату с номером s, получим пару оптимальных смешанныхстратегий x~,y`~ игры с матрицей A`, полученной из матрицы А вычеркиваниемстолбца с номером s.

Обратное:если x~,y`~ — пара оптимальных смешанных стратегий игры с матрицей A`, тодобавив в качестве координаты с номером s вектора y`~ ноль и сдвинув всекоординаты с номерами s, s+1,… n-1 на одно место вправо получим пару x~,y~оптимальных смешанных стратегий в игре с матрицей А.

Теорема.Если столбец с номером s в матрице А нестрого доминирует выпуклую линейнуюкомбинацию всех остальных столбцов, то существует такая оптимальная смешаннаястратегия y~ второго игрока, в которой координата с номером s равна нулю илюбая пара x~,y`~ оптимальных смешанных стратегий игры с матрицей А`преобразуется в пару оптимальных смешанных стратегий x~,y~ игры с матрицей Адобавлением нулевой s-той координаты и сдвигом координат с номерами s, s+1,…n-1 вектора y`~ вправо на одно место.

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

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

Методприближенного определения цены игры.

Способотыскания приближенного решения прямоугольных игр был сформулирован в работеГ.В.Брауна, а сходимость процесса была доказана Джулией Робинсон в 1951 году.

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

Заключаетсяон в последовательной процедуре «сближения» вержней и ниждей ценыигры с заданной точностью.

Глава. Биматричные игры

<a/>[VU1]

Функциявыигрыша биматричной игры представляет собой две платежные матрицы: А — определяет выигрыш первого игрока, а В — выигрыш второго игрока. Первый игрокимеет m чистых стратегий ( m строк в матрицах А и В ) Второй игрок имеет nчистых стратегий ( n столбцов в матрицах А и В ).

Врезультате выбора первым игроком i-той стратегии, а вторым игроком j-тойстратегии, первый игрок получает выигрыш aij, а второй — bij.

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

Вбиматричной игре ситуация i*j называется приемлемой для первого игрока, еслиего выигрыш в этой ситуации не меньше, чем в любой другой:

аi*j ³ аij j=1:n

Длявторого игрока ситуация ij* приемлема, если его выигрыш в этой ситуации неменьше, чем в любой другой:

bi*j ³ bij i=1:m

Tакимобразом, приемлемые ситуации для первого игрока — это максимальные элементывстолбцах матрицы А, а для второго игрока — максимальные (тоже!) элементы встроках матрицы В.

Ситуация i*j* в биматричной игре называется равновесной,если она приемлема для обоих игроков, то есть если любое отклонение от нее какдля первого игрока, так и для второго только лишь уменьшает их выигрыш:

аi*j* ³ аij*

bi*j* ³ bi*j

Множествоситуаций равновесия G образуется как пересечение множеств приемлемых ситуацийпервого и второго игроков.

Пример.

3 2 3 1 А: 1 2 В: 2 2 3 2 2 1

G1={(1,1),(1,3),(3,2),(3,3)}

G2={(1,1),(2,1),(2,3),(3,2)} G = {(1,1),(3,2)}

I v(1,1)= 3 II v(1,1)= 3

v(3,2)= 3 v(3,2)= 2

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

Изпримера хорошо видно, что хотя (1,1) и (3,2) — ситуации равновесия, ситуации (1,2) и (3,1) таковыми не являются, в отличие от матричных игр.

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

Так,в рассматриваемом примере второй игрок заинтересован в том, чтобы первый выбралi=1, так как при этом v(II)= 3. Первому же игроку с точки зрения выгодыбезразлично какую стратегию выбрать - первую или третью — в любом случае еговыигрыш составляет 3. Если первый игрок доброжелательно настроен по отношениюк противнику, то он выберет первую стратегию, чтобы и второй игрок получилмаксимальный выигрыш. В противном случае первый потребует за выбор болеевыгодной для второго стратегии дополнительную плату, и если эта плата будетменьше единицы, то очевидно, что второй игрок согласится на эту сделку.Такаяигра называется игрой с побочными платежами.

Еслив биматричной игре ситуаций равновесия нет, но игроки имеют возможностьдоговориться между собой, то обычно применяют такой искусственный прием:находится i*j* такая, что:

max ( aij + bij ) = ( ai*j* + bi*j*)

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

Пример.

3 2 1 3 А: 1 2 1 В: 2 1 2 2 3 2 3

Ситуацийравновесия нет. Находим максимальный элемент в матрице А+В

4 3 2 А+В: 3 3 3 2 5 3

max= 5, ( i, j ) = (3,2). Эта сумма должна быть разделена между первым и вторымигроками.

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

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

Заданиепо биматричным играм

Придуматьусловие биматричной игры n*m, n = m > 3 и найти ее решения в чистыхстратегиях («игра с побочными платежами»)

Глава. Нестратегические игры

1. Основные понятия иопределения.

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

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

Коалицией вкооперативное игре называется всякое (любое) подмножество множестваигроков.

Пример. Пусть I = {1,2,...i...n} — некоторое множествоигроков. Коалициями будут: k1 = {1,2,5,i};

k2= {i} = i;

k3= { } = Æ ;

k4 = { 1,2,...n} = I.

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

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

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

Задатьхарактеристическую функцию этой игры.

I ={ M, p1, p2 } — множество игроков игры. Тогда

v(Æ) = v(p1, p2) = v (p1)= v (p2)= v (M) = 0,

v(M, p1, p2) = v( M,p1) = v( M, p2)= C.

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

Свойствахарактеристической функции:

1.Персональность vГ (Æ) = 0;

2.Супераддитивность vГ (КÈL) ³ vГ (К) + vГ (L), где K,LÎI, KÇL = Æ;

3.Дополнительность vГ (К) + vГ (I\K) = vГ (I) =C,

гдеС — постоянная сумма выигрыша.

2.Дележи в кооперативных играх.

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

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

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

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

xi ³v(i) Эгалитарныйподход

å xi = v(I) Утилитарный подход

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

Дележом вусловиях характеристической функции v называется вектор х = ( х1, х2,… хn), удовлетворяющий условиям индивидуальной и коллективнойрациональности.

Классической кооперативной игрой называется система < I, v >, включающаямножество игроков I и характеристическую функцию v над этим множеством, а также множество Х дележей в условиях этой характеристической функции.

Теорема. Длятого, чтобы вектор х = ( х1, х2,… хn) был дележом в кооперативной игре < I, v >, необходимо и достаточно, чтобы

хi = v (i) + ai, ai ³ 0, i Î I;

å ai = v(I) — å v(i)

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

åxi = å v (i) + v(I) — å v(i) = v(I) также выполняется.

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

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

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

Существующаяклассификация делит все кооперативные игры, прежде всего, на существенные инесущественные.

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

v (КÈL) = v(К) + v(L), где K,LÎI, KÇL = Æ;

Существенныминазываются остальные игры.

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

Признакаддитивности характеристической функции задается теоремой:

Теорема.Для того, чтобы характеристическая функция была аддитивной, необходимо идостаточно, чтобы выполнялось равенство å v(i) = v(I).

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

Теорема. Внесущественной игре существуе только один дележ

( v(1), v(2),… v(n) ).

Во всякой существенной игре множество дележейбесконечно.

Этообьясняется тем, что в существенной игре обязательно существует

D= v(I) — å v(i) > 0,

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

Игрокитак же делятся на существенных и несущественных (болванов), а множества игроков- на носителей игры и множества болванов.

Существенным называется игрок i, если существует такая коалиция К,что

v(K)+ v(i) < v(KÈi).

Болваномназывается игрок i, если для любойкоалиции KÌI cправедливо

v(K)+ v(i) = v( KÈi).

Допустим,L — множество болванов (несущественных игроков) и LÌK, тогда

v(K)= v(K\ L) + å v(i), а если K = L, то v(K) = å v(i).

Существенныеигроки образуют множество носителей игры, NÌI. Признаком этого для коалиции К является:

v(K)= v(KÇN) + å v(i)i ÎK\N.

3.Аффинно-эквивалентные игры.

Существенныеи несущественные игры тоже делятся на классы.

Кооперативная игра с множеством игроков I ихарактеристической функцией vназываетсяаффинно-эквивалентной игрес тем же множеством игроков и характеристической функцией v’, если найдутсятакое положительное число k и произвольные вещественные ci ( i Î I ), что для любой коалиции KÌ L имеет место равенство:

v’(K) = k v(K) + å ci,iÎK.

При афинной эквивалентности v ~ v’ дележ xсоответствует дележу х’ так, что: xi ’ = k xi + ci.

Иногдавместо аффинной эквивалентности самих кооперативных игр удобно говорить обаффинной эквивалентности их характеристических функций.

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

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

Рассмотримс позиций стратегической эквивалентности несущественные игры.

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

Теорема.Всякая существенная игра аффинно эквивалентна нулевой игре.

Следствие. Всенесущественные игры с одним и тем же множеством игроков аффинно эквивалентныдруг другу.

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

Дляизучения существенных игр наиболее удобна a-b редуцированная форма, тоесть такая, в которой v(i) = a, v(I) = b. Обычно используются варианты a=0, b=1и a=1, b=0.

Теорема. Всякаясущественная игра аффинно эквивалентна одно и только одной игре в 0-1редуцированной форме.

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

v’(K) = ( v(K) — åiÎK v(i))/ (v(I) — åiÎI v(i)) (3.1.)

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

Вседележи в 0-1 редуцированной форме должны отвечать условиям: xi ³0, так как v(i) = 0, но есть еще D, так как играсущественная å xi = v(I) = 1.

Пример. Дана кооперативная игра, I = {1,2,3,4}. Заданахарактеристическая функция: v(1) = -1; v(2) = v(3) = -2; v(1,2,4) = v(1,3,4)= 2; v(2,3,4) =1;

v(4)= v(1,2)= v(1,3) = v(1,4) = v(2,3)= v(2,4) = v(3,4) = v(1,2,3) = v(1,2,3,4) = 0;

Найтихарактеристическую функцию 0-1 редуцированной формы.

Воспользуемсяформулой 3.1. В знаменателе выражения стоит постоянная величина v(I) — åiÎI v(i) = 0 — (-1-2-2) = 5. Остальные вычисления занесемв таблицу:

К 1 2 3 4 12 13 14 23 24 34 123 124 134 234 1234 v’ 0,6 0,6 0,2 0,8 0,4 0,4 1 1 1 1 1

4.Доминирование дележей.

Рассмотримкооперативную игру Г = < I, v > и два дележа в этой игре: х = (х1, х2,… хn) и y = ( y1, y2,… yn). Допустим, K Ì I — некоторая коалиция вигре.

Дележ х доминирует дележ у по коалиции К, есливыполняются неравенства åiÎK хi £ v(К) и хi > yi, iÎ К.Доминирование дележа по коалиции К обозначается хñК у, х domК y, или x Rк y.

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

Длякоалиции К доминирующий дележ полезнее, чем доминируемый. Эта коалиция будетего отстаивать. Иной случай, когда с этим дележом не согласятся остальныеигроки (входящие в множество I\K). Но коалиция К может сама обеспечить себетакой дележ, так как åiÎK хi £ v(К).

Следуетотметить, что доминирование возможно по любой коалиции, кроме коалиции изодного игрока и из всех игроков. В первом случае К = {i} из определенияследует, что хi £ v(i), что противоречитсвойству индивидуальной рациональности дележа х ( х ³ v(i)).

Вслучае К = I из хi > yi следует, что åхi > åyi = v(I), то есть дележ х должен давать в сумме больше, чем гарантированный выигрыш для всех игроков.

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

Теорема.Если v и v’ — аффинно-эквивалентные характеристические функции, причемдележам х и у в v соответствуют дележи x’ и y’ в v’, то из х ñК у следует х’ ñК у’.

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

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

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

Например, вигровой модели Шепли-Шубик, 1969 года (кооперация производства с обменомпродуктами) или просто модели обменов, вопрос о том, как кооперировать, можетбыть заменен вопросом: какое понятие оптимальности следует применять длядележа прибыли?

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

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

Рассмотримв качестве принципов оптимизации устойчивость коалиционной структуры и принципсправедливости.

Эксцессом дележа х для коалиции К в условиях характеристической функции v называется разность

ev(x,K) = v(K) - åiÎK хi, колторая показывает, насколько можеткоалиция К увеличить свой выигрыш по сравнению с суммой, предлагаемой подележу. Если эксцесс положителен, то соответственный дележ реализуем для даннойкоалиции, в этом случае дележ называется эффективным.

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

Дележ называется абсолютно неэффективным, еслион не эффективен ни для какой коалиции.

Дляигры с постоянной суммой эксцесс положителен и всегда эффективен.

Пример. Рассмотрим существенную игру трех лиц с постояннойсуммой. С позиций доминирования в этой игре можно рассматривать только коалиции{1,2}, {1,3}, {2,3}. Пусть х = ( х1, х2,… хn) и y = ( y1, y2,… yn) — дележи и х dom1,2 y. Из определения доминирования следует, что должно выполняться

х1+х2 = 1 — х3 £ v(1,2) и х1> у1, х2> у2.

Посколькупо свойству дополнительности для 0-1 редуцированной формы v(1,2) = v (1,2,3) — v(3) = 1 — 0 = 1, то неравенство x1 + x2 = 1 — x3 £ 1 всегда выполняется. Вторая группа неравенств изопределения доминирования дележей и х1 > у1, х2> у2 иусловие ее выполнения лучше всего иллюстрируются графически.

Таккак рассматривается 0-1 редуцированная форма, то

х1+х2+ х3 = y1+ y2+ y3 = 1и любой дележ в такой задаче можно представить как точку симплекса, задаваемуюбарицентрическими координатами.

Симплекс — простейший выпуклый многогранник данного числаизмерений n. При n = 3 cимплекс — произвольный, в том числе неправильныйтетраэдр. При n = 2 симплекс — произвольный треугольник, при n = 1 — отрезок,при n = 0 — одна точка, таким образом, n-мерный симплекс имеет n+1 вершину.

Еслив пространстве Rm дана система декартовых координат х1,х2,… хm в которой вершина еi ( i=0: n)имеет координаты х1(i), х2(i),… хm(i), тосимплекс с вершинами е0, е1, е2,… еn состоитиз всех точек пространства, координаты которых имеют вид:

хk= a0хk (0)+ a1хk (1)+ ...+ anхk(n), k = 1: m, a ³ 0 — произвольные, å ai= 1.

Барицентрическиекоординаты точки М на плоскости поотношению к трем базисным (не лежащим на одной плоскости) точкам А1,А2, А3 этой плоскости — такие три числа m1,m2, m3 (å mi=1), что точка М представляет собой центр тяжести системы из трех материальныхточек с массами m1, m2, m3, расположенными вточках А1, А2, А3 ( или вершинах симплекса).

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

Дляопределения всех точек симплекса, соответствующих дележам, доминируемымдележом х по коалиции {1,2}, необходимо провести через х прямые, параллельныесторонам симплекса 2,3 и 1,3. Заштрихованная область и дает множестводоминируемых дележей. Пунктир означает, что внутренние границы области в нее невходят. Точно так же можно построить все области доминирования дележом х покоалициям {1,2}, {2,3} и {1,3}. Незаштрихованные области — соответствуютдележам у1, доминирующим дележ х1.

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

Дляигры с непостоянной суммой могут иметь место и неэфективные дележи,поэтому неравенство хi + xj £ v(i,j), хi+ хj+ хl =1, может быть нарушено. Так как это равносильно 1- хl £ v(i,j), то условия доминирования принимают вид:

хi> уi , хj > уj, хl ³ 1 — v(i,j).

5. С — ядро (core).

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

Множество дележей в кооперативной игре, каждый изкоторых не доминируется какими — либо другими дележами, называется С-ядромэтой игры.

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

åiÎK хi ³ v(K), ( т.е. все дележи в С-ядре абсолютно неэффективны ).

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

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

Теорема.Во всякой существенной игре с постоянной суммой С-ядро пусто.

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

Пример.Рассмотрим общую кооперативную игрутрех лиц в 0-1 редуцированной форме. Имеем: v(Æ ) = v(1)= v(2) = v (3) = 0; v (1,2,3) = 1; v(1,2) = C3; v (2,3) = C1; V (1,3) = C2; 0 £ Ci £ 1, i = 1:3.

Изопределения свойств дележей, принадлежащих С-ядру, имеем:

x1+ x2 ³ C3; x1 + x2 ³ C3; x1 + x2 ³ C3; а поскольку для любого дележа справедливо правилогрупповой рациональности, x1 + x2 + x3 = 1, тоусловие принадлежности дележа к С-ядру имеет окончательный вид в форме:

1 — x3 ³ C3; 1 — x2 ³ C2; 1- x1 ³ C1; или x3 £ 1- C3; x2 £ 1- C2 ; x1 £ 1- C1.

Сложимпочленно все неравенства: x1 + x2 + x3 £ 3 — (C1 + C2 + C3).Имеем: C1 + C2 + C3 £ 2. Это условие является необходимым для существованиянепустого С-ядра.

6.Решение по Нейману — Моргенштерну.

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

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

Такоерасширение было произведено Дж. фон Нейманом и О.Моргенштерном путемиспользования понятий внутренней и внешней устойчивости.

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

Решением по Нейману-Моргенштерну ( Н-М решением )кооперативной игры называется такое множество R дележей, что:

1. Никакие два дележа из R не доминируют друг друга(внутренняя устойчивость);

2. Каким бы ни был дележ S R найдется дележ r R такой,что r dom s (внешняя устойчивость).

Теорема связимежду С-ядром и Н-М решением: Если в кооперативной игре существует С-ядро и Н-Мрешение R, то С Ì R.

Теорема.Если некоторое Н-М решение кооперативной игры <I,v> состоит изединственного дележа х, то характеристическая функция v является несущественной. (Н-М решение существенной кооперативной игры не может состоятьтолько из одного дележа).

НедостаткиН-М решения:

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

2.Кооперативные игры, если имеют Н-М решение, то, как правило, более одного.Поэтому принцип оптимальности, приводящий к Н-М решению не является полным: онне в состоянии указать игрокам единственной системы норм распределениявыигрыша.

3.Решения существенных кооперативных игр состоят из более чем из одного дележа.Таким образом даже выбор какого-либо конкретного Н-М решения еще не определяетвыигрыша каждого из игроков.

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

7.Вектор Шепли.

Досих пор были рассмотрены решения игр, отвечающие принципам оптимальности всмысле выгодности и устойчивости ( maxmin в чистых или смешанных стратегиях )или только устойчивости ( C-ядро и Н-М решение в кооперативных играх ).Рассмотрим решения, оптимальные в смысле справедливости.

Задачасостоит в том, чтобы найти вектор распределения общего выигрыша междуучастниками игры: Ф(v) = ( Ф1(v), Ф2(v),… Фn(v))

Приэтом необходимо, чтобы Ф(v) был дележом в условиях кооперативной игры, то естьотвечал бы требованиям игдивидуальной и групповой рациональности.

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

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

Формальноэти условия выражаеюся в том, что å Фi(v)= v (N), iÎN, и Фj(v) = v(j), jÎ I\N.

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

ФормальноФj(v) = Фpj(v), где p- целое положительное число.

Аксиома агрегации: еслиигрок принимает участие в двух играх с характеристическими функциями v’ и v”,то причитающаяся ему доля:

Ф(v’+ v”) = Ф(v’) + Ф(v”), если множества игроков в обоих играх совпадают.

Совокупностьаксиом является непротиворечивой и полной: для всякой характеристическойфункции v вектор Ф(v) существует и является единственным (вектор Шепли).Непротиворечивость обеспечивает существование, а полнота его единственность.

Теорема. Для любойхарактеристической функции v над I={1,2,...n} компоненты вектора Шеплиопределяются по формуле

Пример. Для кооперативной игры трех лиц в 0-1 редуцированнойформе эта формула имеет вид: Фi(v) = 1/6 (2 — 2Ci + Cj+ Cf).

Следовательно,координаты вектора Шепли:

Ф1(v)= 1/6 (2 — 2C1 + C2 + C3), где C1 =v(2,3);

Ф2(v)= 1/6 (2 — 2C2 + C1 + C3), где C2 = v(1,3);

Ф3(v)= 1/6 (2 — 2C3 + C1 + C2), где C3 = v(1,2).

Длятого, чтобы вектор Шепли принадлежал к С-ядру необходимо и достаточно, чтобывыполнялось неравенство: 4Ci + Cj + Cf £ 4 для всех i, j,f.

8.Примеры классических кооперативных игр.

Задача«Джаз-оркестр».

Условие.Владелец клуба в Париже обещает 1000 $певцу (S), пианисту (P) и ударнику (D) за совместную игру в клубе. Выступлениедуэта певца и пианиста он расценивает в 800 $, ударника и пианиста — в 650 $, аодного пианиста в 300 $. Другие дуэты и солисты не рассматриваются, априсутствие пианиста владелец считает обязательным.

Дуэтпевец — ударник зарабатывает 500 $ за вечер в одной удобно расположеной станцииметро, певец зарабатывает в среднем 200 $ за вечер в открытом кафе. Ударникодин ничего не может заработать.

Стоитли музыкантам соглашаться на приглашение владельца клуба и как поделить общийзаработок ?

Решение. Обозначим S, P,D — 1 игрок, 2 игрок и 3 игроксоответственно.

Найдем0-1 редуцированную форму исходной игры:

Коалиция

123

SPD

1000 800 500 650 200 300

v(0-1)

1 0,6 0,6 0,7

Условие эффективности дележей

Условие неэффективности

(принадлежности к С-ядру)

Для редуцированной формы

x1 ³ 1 — v(2,3) = 0,3

x1 £ 0,3

x2 ³ 1 — v(1,3) = 0,4

x2 £ 0,4

x3 ³ 1 — v(1,2) = 0,4

x3 £ 0,4

Для нередуцированной формы

xS + xP £ 800 , xD ³ 200

xS + xP ³ 800, xD £ 200

xS + xD £ 500, xP ³ 500

xS + xD ³ 500, xP £ 500

xD + xP £ 650, xS ³ 350

xD + xP ³ 650, xS £ 350

Найдемвектор Шепли для этой игры. В нередуцированной форме n=3, коалиции могут бытьиз одного, двух и трех игроков.

ФS= (3-3)!2! (1000 -650)/ 3! + 1!1![(800 — 300) + (500 — 0)] / 3! + 2!0! 200 / 3!= 350;

ФP = 475;

ФD = 175.

Нетрудновидеть, что, ФS + ФP + ФD = 1000, то естьусловие коллективной рациональности выполняется. С другой стороны:

ФS= 350 > v(S) = 200;

ФP= 475 > v(P) = 300;

ФD= 175 > v(D) = 0, то есть условия индивидуальной рациональности так жевыполняются. Таким образом, в данном случае вектор Шепли является дележом,кроме того, он входит в С-ядро:

xD= ФD=175 < 200, xP = ФP=475 < 500, xS= ФS=350 = 350 (выплата певцу оказалась максимальной).

Для0-1 редуцированной формы:

Ф1(v)= 1/6 (2 — 2C1 + C2 + C3) = (2 — 1,4 + 1,2)/ 6= 0,3;

Ф2(v)= 1/6 (2 — 2C2 + C1 + C3) = (2 — 1,2 + 1,3)/ 6= 0,35;

Ф3(v)= 1/6 (2 — 2C3 + C1 + C2) = (2 — 1,2 + 1,3)/ 6= 0,35.

ВекторШепли Ф(v) = ( 0,3; 0,35; 0,35) входит в С-ядро игры:

4Ci+ Cj + Cf = 2,8 + 0,6 + 0,6 = 4 ( £ 4), то есть условие соблюдается на границе для первогоигрока. Для других двух игроков:

4Ci+ Cj + Cf = 2,4 + 0,7 + 0,6 = 3,7 < 4, то естьусловие вхождения в С-ядро тоже соблюдается.

Ответ. Музыкантам выгодно предложение владельца клуба, таккак они заработают за этот вечер не менее, чем обычно. Общий заработок в1000 $ они должны поделить следующим образом: певцу 350 $, пианисту 435 $,ударнику 175 $.

Глава. Принятие решений в условиях частичнойнеопределенности.

Элементы теории статистических решений.

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

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

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

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

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

Впервых поведение природы известно полностью (заданы вероятностями). Во вторых- действия природы не известны, или изучены частично.

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

Поискомрешений в таких ситуациях и занимается теория статистических решений.

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

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

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

1.Игры с природой в условиях определенности.

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

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

Пример. Фирма купила станок за 100 ден.ед. Для его ремонтаможно купить специальное оборудование за 50 ед. или обойтись старымоборудованием. Если станок выходит из строя, его ремонт с помощью спецоборудования обходится в 10 ед., без спецоборудавания — в 40 ед. Известно, что втечение срока эксплуатации станок выходит из строя не более трех раз:вероятность того, что станок не сломается — 0,3; сломается 1 раз — 0,4;сломается 2 раза — 0,2; сломается 3 раза — 0,1. Требуется определитьцелесообразность приобретения специализированного ремонтного оборудования.

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

Выход станка из строя

Ремонтное оборудование ни разу 1 раз 2 раза 3 раза не купить -100 -140 -180 -220 купить -150 -160 -170 -180 /> /> /> /> /> />

Решение. Рассмотрим сначала эту задачу как антагонистическуюигру.

Вматрице методом минимакса находим седловую точку: (2,4), таким образом, x* = (0, 1 ), y* = ( 0, 0, 0, 1 ), v* = — 180 ден.ед.

Ответ: нужно купить специализированное оборудование.

Однаков играх с природой положение коренным образом меняется: уже в условии заложенаустойчивая смешанная стратегия природы: у = ( 0,3; 0,4; 0,2; 0,1) и мы знаем,что именно этой стратегии придерживается природа.

Еслиже человек — первый игрок — будет продолжать играть оптимально, то его выигрышсоставит v(x*) = — 150 0,3 — 160 0,4 — 170 0,2 — 180 0,1 = — 161, а еслиприменит первую, неоптимальную стратегию, то математическое ожидание еговыигрыша составит v(x') = — 100 0,3 — 140 0,4 — 180 0,2 — 220 0,1 = — 144.

Такимобразом, первому игроку выгодно играть неоптимально!

Ответ: не покупать специализированное оборудование.

Существенноеразличие между значениями v(x*) и v(x') обьясняется тем, что смешаннаястратегия природы неоптимальна и она, «отклоняясь» от своейоптимальной стратегии «недополучает» 36 ден.единиц выигрыша.

2.Игры с природой в условиях неопределенности.

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

Пример. Игра «Поставщик».

Выпускпродукции фирмы существенно зависит от скоропортящегося материала, например,молока или ягод, поставляемого партиями стоимостью 100ед. Если поставка неприбывает в срок, фирма теряет 400 ед. от недовыпуска продукции. Фирма можетпослать к поставщику свой транспорт (расходы 50 ед.), однако опыт показывает,что в половине случаев транспорт возвращается ни с чем. Можно увеличитьвероятность получения материала до 80%, если предварительно послать своего представителя, но расходы увеличатся еще на 50 ед. Существует возможностьприобретать более дорогой (на 50%) материал-заменитель у другого, вполненадежного поставщика, однако, кроме расходов на транспорт (50 ед.) возможныдополнительные издержки хранения материала в размере 30 ед., если его количество на складе превысит допустимую норму, равную одной партии.

Какойстратегии должен придерживаться завод в сложившейся ситуации?

Формализация. У природы два состояния: поставщик надежный ипоставщик ненадежный. У фирмы — четыре стратегии: 1) не осуществлять никакихдополнительных действий, 2) послать к поставщику свой транстпорт, 3) послать кпоставщику представителя и транстпорт, 4) купить и привезти материал-заменительот другого поставщика.

Составимтаблицу расчетов:

Затраты и убытки фирмы-изготовителя Ситуация Стоимость материала Недовыпуск продукции Транспорт Команди-ровочные расходы Издержки хранения

Общая сумма

1 1 — 100

— 100

1 2 — 400

— 400

2 1 — 100 — 50

— 150

2 2 — 50 — 200 — 50

— 300

3 1 — 100 — 50 — 50

— 200

3 2 — 80 — 80 — 50 — 50

— 260

4 1 — 250 — 50 — 30

— 330

4 2 — 150 — 50

— 200

Решение.На основе полученных результатоввычислений можно составить платежную матрицу:

min max

— 100

— 400

— 400

— 150

— 300

— 300

— 200

— 260

— 260 — 260

— 330

— 200

— 330

Ответ. Нужно придерживаться третьей стратегии и затраты непревысят 260 ед., если послать к поставщику представителя и транстпорт.

1. Рассмотренный способ поиска оптимального решения называетсякритерием Вальда (Максиминный критерий принятия решения). Выбираетсярешение, гарантирующее получение выигрыша не меньше, чем maxmin:

vW= maxi minj aij = -260 ед.

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

2. Максимаксный критерий. Самыйблагоприятный случай:

vM= maximaxj aij = -100 ед.

Еслифирма ничего не предпримет, то потратит не больше 100 единиц. Это критерийабсолютного оптимизма.

3.Критерий пессимизма-оптимизма Гурвица.

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

vH= maxi [a maxi aij + (1-a)minj aij ], где a — “степеньоптимизма”, 0£ a £1.

При a = 0 критерий Гурвица тождественен критерию Вальда, апри a =1 совпадает с максиминным решением.

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

Влияниестепени оптимизма на выбор решения в задаче “Поставщик”.

Степень оптимизма Решение 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9

А1

1 стратегия -370 -340 -310 -280 -250 -220 -190* -160* -130*

А2

2 стратегия -285 -270 -255 -240 -225* -210* -195 -180 -165

А3

3 стратегия -254* -248* -242* -236* -230 -224 -218 -212 -206

А4

4 стратегия -317 -304 -281 -278 -265 -252 -239 -226 -213

ВеличинаvH для каждого значения a отмечена*. При a£ 4/9 критерий Гурвица рекомендует в задаче “Поставщик”решение А3, при 4/9£ a£2/3 — решение А2. В остальных случаях А1.А4 не выгодно во всех случаях.

4.Критерий Сэвиджа(критерийминимакса риска).

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

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

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

Длярешения задачи строится так называемая “матрица рисков”, элементы котройпоказывают, какой убыток понесет игрок (ЛПР) в результате выбора неоптимальногоаврианта решения.

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

Еслибы игрок знал заранее будущее состояние природы j, он выбрал бы стратегию,которой соответствует max элемент в данном столбце: maxi aij,тогда риск: rij = maxi aij — aij.

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

vS= mini maxj rij = mini maxj(maxi aij — aij).

Длязадачи “Поставщик” минимакс риска достигается сразу при двух стратегиях А2 и А3:

max min

200

200

100

100 100

100

100 100

230

130

5.Критерий Лапласа.

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

Длярешения задачи для каждого решения подсчитывается математическое ожиданиевыигрыша (вероятности состояний природы полагаются равными yj = 1/n,j = 1:n), и выбирается то решение, при котором величина этого выигрышамаксимальна.

vL= maxi å1/n aij = 1/n maxi åaij.

Решениемигры “Поставщик” по критерию Лапласа является вторая стратегия:

max

-250

-225

-225

-230

-265

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

6.КритерийБайеса-Лапласа.

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

vBL= maxi å aij yj.

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

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

Исходяиз этого, можно приписать вероятность наступления первого состояния природывероятность yj = 0,75 = (1-0,25), второго — yj = 0,25.Тогда согласно критерию Байеса-Лапласа оптимальным является решение А1.

Стратегии

å aij yj

А1

— 175*

А2

-187,5

А3

— 215

А4

— 297,5

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

Решение Критерии Стратегии Вальда maxmax Гурвица Сэвиджа Лапласа Байеса-Л

А1

* * *

А2

* * *

А3

* * *

А4

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

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

Литература

1.Аллен Р. Математическая экономия. М., Изд.ин.лит.,1963

2.Вентцель Е.С. Исследование операций. М.: Советское радио, 1972

3.Вильямс Дж.Д. Совершенный стратег. — М.: ИЛ,1960

4.Карлин С. Математические методы в теории игр, программировании и экономике М.: Мир, 1964

5.Кофман А., Фор Р. Займемся исследованием операций. М: Мир, 1966

6.Ланге О. Оптимальные решения. М. Прогресс, 1967 .

7Мак-Кинси Дж. Введение в теорию игр. М., Физматгиз,1966

8.Оуэн Г. Теория игр. М., Мир 1971

9.Р.Л. Кини, Х.Райфа Принятие решений при многих критериях: предпочтения изамещения. М.: Радио и связь, 1981

10.Р.Штойер Многокритериальная оптимизация. Теория, вычисления, приложения.М.: Радио и связь, 1992

11.Вопросы анализа и процедуры принятия решений.- М.: Мир, 1976

12.Статистические модели и многокритериальные задачи принятия решений.-М.: Статистика, 1979.

13.Р.Л.Кини Теория принятия решений. — В кн.Исследование операций. М.: Мир, 1981 г.

14.Воробьев Н.Н. Теория игр для экономистов-кибернетиков, М.: Наука, 1985.

15.Крушевский А.В. Теория игр. Киев: Вища школа, 1977.

16.Дюбин Г.Н., Суздаль В.Г.Введение в прикладную теорию игр.М.: Наука, 1981

17.Мешковой Н.П., Закиров Р.Ш. Теория игр, конспект лекций. Челябинск, ЧПИ, 1974

18.Э.Й.Вилкас в сб. Современные направления теории игр. Вильнюс. Мокслас, 1976

19. А.Д.Школьников Основы теории игр. Л, Изд.горного института, 1970

20.Смоляков Всегда существующее решение кооперативных игр и его применение канализу рынков. М.: ВНИИСИ, 1978

еще рефераты

Еще работы по теории лорганизации

Реферат по теории лорганизации

Стратегическое планирование

1 Сентября 2013

Реферат по теории лорганизации

Билеты по предмету Организация торговли продовольственными и непродовольственными товарами

1 Сентября 2013

Реферат по теории лорганизации

Организация и планирование производства

1 Сентября 2013

Реферат по теории лорганизации

Экзаменационные билеты по теории организации за второй семестр 2000 г

1 Сентября 2013