Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
ТЕОРИЯ ПРИНЯТИЯ РЕШЕНИЙ
Курс лекций.
Урицкая О.Ю.
ВВЕДЕНИЕ
Искусство принятия наилучших решений, основанное на опыте и интуиции, является сущностью любой сферы человеческой деятельности. Наука о выборе приемлемого варианта решения сложилась сравнительно недавно, а математической теории принятия решений - около 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), при k i (s) = k i (u) , ki (t) = ki (v) . Если отсюда следует, что К (s) Р К(t), то говорят, что i-тый векторный критерий независим по предпочтению от всех частных критериев. В противном случае методически удобнее при решении таких задач перейти к новой постановке, где предпочтительным было бы изменение всех частных критериев, например в сторону увеличения. При этом, если в исходной постановке задачи для части критериев предпочтительнее меньшее значение, то в новой постановке значения таких критериев рассматриваются с противоположным знаком.
Независимость по предпочтению частных критериев дает возможность перейти от задачи сравнения векторных с m частными критериями к решению m однокретериальных задач сравнения частных критериев между собой. В реальных задачах допущение о независимости частных критериев по предпочтению зависит от характера решаемого вопроса. Например, если в качестве частных критериев используют затраты, надежность, прибыль, льготы, то для них всегда наиболее предпочтительным будет экстремальное значение ( min или max ) вне зависимости от других частных критериев.
Если частные критерии определяют структуру сравниваемых обьектов, то например, рост и вес человека, количество наземного и подземного транспорта в городе, количество тепловых, атомных и гидроэлектростанций, то они обычно зависимы по предпочтению.
Необходимо отметить, что переход от независимых частных критериев к зависимым иногда связан с более "тонким" анализом самих предпочтений.
1.3. Аксиома Парето и эффективные варианты.
Сравнение между собой векторных критериев представляет собой достаточно сложную проблему.
Пример. U = (u,v,s,t) - множество альтернатив
k1
k2
k3
u 5 3 7 v 4 3 6 s 5 2 7 t 6 3 1k (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 совпадают.
Нормализацию проводят различными способами - от применения более грубых шкал при измерении оценок, до вычисления разного рада статистик. Наибольшее распространение получила статистика вида :
k i(v) - min k i (v)
ki ‘ (v) = --------------------------
max i k (v) - min i k (v)
Она удобна тем, что все k i (v)Î [0 ; 1], причем min k’i(v) = 0, max k’i (v) = 1. Таким образом, нормализованный частный критерий показывает, на какую часть всего диапазона изменений [0 ; 1] данный частный критерий превосходит минимальное значение.
Пример.
Исходные значения Нормированные значенияk1
k2
k3
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 0 0 1 K(w) 170 0,16 0,0007 1 1 0После нормализации частных критериев векторные критерии приобретают некоторые полезные свойства. Главное из них - любая перестановка частных критериев приводит к векторной оценке, которая входит в множество значений исходной векторной оценки.
Дополнительная информация задается в виде множества символов: равноценность частных критериев 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. Предмет и задачи теории игр.
Подавляющее большинство социально-экономических решений приходится принимать с учетом противоречивых интересов, относящихся либо к различным лицам или организациям, либо к различным аспектам рассматриваемого явления, либо к тому и другому. В таких случаях невозможно применить традиционные методы оптимизации. В обычных экстремальных задачах речь идет о выборе решения одним лицом, и результат решения зависит от этого выбора, то есть определяется действиями только одного лица. В такую схему не укладываются ситуации,где решения, оптимальные для одной стороны, совсем не оптимальны для другой и результат решения зависит от всех конфликтующих сторон.
Конфликтный характер таких задач не предполагает вражды между участниками, а свидетельствует о различных интересах. Необходимость анализировать подобные ситуации вызвала к жизни специальный математический аппарат - теорию игр.
Теория игр предстакляет собой часть обширной теории, изучающей процессы принятия оптимальных решений. Она дает формальный язык для описания процессов принятия сознательных, целенаправленных решений с участием одного или нескольких лиц в условиях неопределенности и конфликта, вызываемого столкновением интересов конфликтующих сторон.
Целью теории игр является выработка рекомендаций по рациональному образу действий участников в конфликтных ситуациях, то есть определение оптимальной стратегии каждого из них.
Первые работы по ТИ ( Цермело, Борель, фон Нейман ) относятся к началу ХХ века. Но только появление и широкое распространение ЭВМ привлекло к ТИ внимание широкого круга специаоистов.
Теория стратегических игр в своей математической форме возникла в 30-х годах нашего века. Ее создателем считается Джон фон Нейман. Первой фундаментальной книгой по теории игр была изданная в 1944 году работа "Теория игр и экономическое поведение"(Нейман Д., Моргенштерн О. М.:Наука,1970)
Практическое значение ТИ состоит в том, что она служит основой моделирования игровых экспериментов, в частности, деловых игр, позволяющих определять оптимальное поведение в сложных ситуациях.
Примеры практического и в том числе экономического содержания призваны скорее содержательно интерпретировать математические положения теории игр, чем указывать на фактические или возможные их приложения. От реальной конфликтной ситуации игра отличается тем, что ведется по вполне определенным правилам. Реальные конфликты обычно трудно поддаются формальному описанию, поэтому любая игра является упрощением исходной задачи, в ней отражаются лишь основные, первостепенные факторы, отражающие суть процесса или явления.
В зависимости от того, какими данными располагает исследователь и какую задачу перед собой ставит, могут быть сформулированы различные теоретикоигровые модели. Различают три основных типа задач:
1. Нахождение оптимального исхода. В качестве исхода в общем случае может рассматриваться социально-экономическая ситуация. В зависимости от содержания задачи ситуацию можно описать наборами благ, получаемых каждым игроком (выигрышами), или исходом может быть избрание того или иного кандидата, принятие того или иного проекта, договора и т.д.При этом в общем случае надо найти коалиционную структуру и коалиционные стратегии, при которых оптимальный исход реализуется.
2. Нахождение оптимального исхода при фиксированной коалиционной структуре, то есть когда нам заведомо известно, что, например, образование коалиций запрещено, невозможно или имеющаяся коалиционная структура не должна меняться по каким-либо политическим или экономическим соображениям. В этом случае общей задачей является нахождение правил принятия решений в коалициях (порядок вознаграждения ее членов), при которых данная коалиционная структура не распадется, и, значит, система будет функционировать согласно интересам и возможностям ее участников.
3. Нахождение устойчивой коалиционной структуры при заданных правилах принятия решений ( конституции, нормативных актах, уставе предприятия и др.) в коалициях.Такие задачи часто встречаются при решении экономических и социальных проблем.
Формализованные модели конфликтов известны с давних пор: это игры в буквальном смысле слова - шахматы, карты, кости и т.п. Эти игры носят характер соревнования, протекающего по известным правилам. Терминалогия, заимствованная из практики таких игр, применима и для других конфликтных ситуаций, которые рассматривает теория игр.
ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ
ИГРОЙ называется всякая конфликтная ситуация, изучаемая в теории игр и представляющая собой упрощенную, схематизированную модель ситуации. От реальной конфликтной ситуации игра отличается тем, что не включает второстепенные, несущественные для ситуации факторы и ведется по определенным правилам, которые в реальной ситуации могут нарушаться
Всякая игра включает в себя три элемента: участников игры - игроков, правила игры, оценку результатов действий игроков.
ИГРОКОМ (лицом, стороной, или коалицией) называется отдельная совокупность интересов, отстаиваемая в игре.Если данную совокупность интересов отстаивает несколько участников игры, то они рассматриваются как один игрок. Игроки, имеющие противоположные по отношению друг к другу интересы, называются противниками.В игре могут сталкиваться интересы двух или более противников.
Антагонистические игры
Игра Г = < 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* называется приемлемой для первого игрока, если a ij* £ ai*j* и приемлемой для второго игрока , если ai*j* £ a i*j.
Таким образом, всякое отклонение отприемлемой ситуации уменьшает выигрыш первого игпрока и увеличивает проигрыш второго.
Ситуация ( i*, j* ) называется равновесной, если она приемлема для обоих игроков. a ij* £ ai*j* £ a i*j . Применительно к антагонистическим играм говорят о седловых точках на поверхности выигрыша ( на них достигается max по первой координате и min по второй.
Свойства седловых точек:
1. Равноценность. Если в игре несколько седловых точек, то значения функции выигрыша в них одинаковы.
2. Взаимозаменяемость оптимальных стратегий. Игроки могут заменить свои оптимальные стратегии другими оптимальными стратегиями, при этом равновесие не нарушится, а выигрыш (проигрыш) останется неизменным.
Теорема. Аффинно-эквивалентные игры имеют одни и те же седловые точки ( то есть их решения совпадают).
Седловыке точки и минимаксы
Устойчивое решение игры может быть получено путем следующих рассуждений:
В самом неблагоприятном случае выигрыш первого игрока не может быть уменьшен по вине противника, если он удовлетворяет условию:
a ij* = min аij
С другой стороны, руководствуясь принципом выгоднгодности первый игрок будет стремиться увеличить свой выигрыш, сохраняя свойство устойчивости, поэтому vн = max min аij
Это нижняя цена игры. Рассуждая подобным образом за второго игрока получим верхнюю цену игры:
vв = min max аij
Интуитивно ясно, что значение ( цена ) игры лежит между vн и vв.
Теорема. Для того, чтобы в матричной игре существовали минимаксы, необходимо и достаточно, чтобы равны были минимаксы:
max min а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 году.
Этот метод, называемый еще итеративным, опирается на традиционный статистический принцип: основывать будущие решения на соответствующей предыстории.
Заключается он в последовательной процедуре "сближения" вержней и ниждей цены игры с заданной точностью.
Глава . Биматричные игры
[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 0 2 3 1 0 А: 1 2 0 В: 2 0 2 0 3 2 0 2 1G1={(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 0 2 1 3 0 А: 1 2 1 В: 2 1 2 2 3 0 0 2 3Ситуаций равновесия нет. Находим максимальный элемент в матрице А+В
4 3 2 А+В: 3 3 3 2 5 3max = 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 0 0 0 0,6 0,6 0,2 0,8 0,4 0,4 1 1 1 1 14. Доминирование дележей.
Рассмотрим кооперативную игру Г = < 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) - дележи и х dom 1,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
12
SP
13
SD
23
PD
1
S
2
P
3
D
v
1000 800 500 650 200 300 0v(0-1)
1 0,6 0,6 0,7 0 0 0Условие эффективности дележей
Условие неэффективности
(принадлежности к С-ядру)
Для редуцированной формы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 0 0 0 0- 100
1 2 0 - 400 0 0 0- 400
2 1 - 100 0 - 50 0 0- 150
2 2 - 50 - 200 - 50 0 0- 300
3 1 - 100 0 - 50 - 50 0- 200
3 2 - 80 - 80 - 50 - 50 0- 260
4 1 - 250 0 - 50 0 - 30- 330
4 2 - 150 0 - 50 0 0- 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 min0
200
20050
100
100 100100
60
100 100230
0
1305. Критерий Лапласа.
В ряде случаев представляется правдоподобным следующее рассуждение: поскольку неизвестны будущие состояния природы, постольку можно считать их равновероятными. Этот подход к решению используется в критерии “недостаточного основания” Лапласа.
Для решения задачи для каждого решения подсчитывается математическое ожидание выигрыша (вероятности состояний природы полагаются равными 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
[VU1]