Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
ТЕОРИЯ ПРИНЯТИЯ РЕШЕНИЙ
Курс лекций.
ВВЕДЕНИЕ
Искусство принятия наилучших решений, основанное на опыте и интуиции, является сущностью любой сферы человеческой деятельности. Наука о выборе приемлемого варианта решения сложилась сравнительно недавно, а математической теории принятия решений - около 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 |
1 |
k (u) k (v), i =1:3, поэтому K(u)P K(v).
k (u) k (s), i =1:3, поэтому K(u) P K(s), варианты s и v оказались доминируемыми, а остальные векторные оценки сравнить невозможно: k (u) N k (t) Таким образом все множество векторных оценок делится на два подмножества: эффективных { k(u),k(t)} и неэффективных { k(v), k(s)} векторных оценок. Из приведенного примера можно сделать важный вывод: если вариант имеет абсолютный max по какому-либо показателю, то он не может быть доминирован.
Аксиома Парето: Пусть даны две векторные оценки:
K(u)= ( k1 (u), k2 (u), ... km (u)) и
K(v)= ( k1 (v), k2 (v), ... km (v))
K(u) P K(v), если существует хотя бы одно j от 1 до m такое что:
i j ki (u) I ki(v), или ki (u) P ki(v), а kj (u) P kj (v).
P - "предпочтительность в смысле Парето".
Все векторные оценки, для которых не существует более предпочтительных в смысле Парето векторных оценок, образуют множество Hо эффективных векторных оценок, а соответствующие варианты - множество vо - эфективных вариантов.
Для нашего примера: H = { K(u), K(v), K(s), K(t)}, Hо = { K(u), K(t)} - множество эффективных векторных оценок. Определение множеств эффективных векторных оценок обычно не позволяет получить в чистом виде решение задачи, но является важным и обязательным этапом, так как практически всегда происходит сокращение имеющихся вариантов, кроме того, для Hо и vо могут выполняться допущения не верные для H и v, то есть задача в дальнейшем может упрощаться за счет дополнительных правил или информации после сокращения.
Принадлежность к v полученного решения - некоторая гарантия правильности результата. Полученное множество оптимальных векторных оценок последовательно суживается с использованием дополнительной информации, искусственных методов или с помощью введения новых правил. Рассмотрим некоторые из этих подходов.
1.4. Важность частных критериев и использование дополнительной информации для принятия решения.
Если при выборе того или иного варианта использование принципа Парето не дает единственного решения, необхлдимо найти способы сужения возможного выбора из множества эффективных вариантов. До сих пор предполагалось, что все критрии одинаковы по важности и одинаково влияют на предпочтительность векторного критерия. На самом деле часто превосходство по наиболее важным частным критериям ведет к предпочтительности векторной оценки в целом. Понятие относительной важности частных критериев возможно будет определить только когда они будут сравнимы, ( иначе как определить: что лучше - 200 тонн или 10 км ). Чтобы разшить эту проблему используют процедуру нормализации.
Частные критерии считаются нормализованными, если области их изменения Н i = 1 : m совпадают.
Нормализацию проводят различными способами - от применения более грубых шкал при измерении оценок, до вычисления разного рада статистик. Наибольшее распространение получила статистика вида :
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 году.
Этот метод, называемый еще итеративным, опирается на традиционный статистический принцип: основывать будущие решения на соответствующей предыстории.
Заключается он в последовательной процедуре "сближения" верхней и нижней цены игры с заданной точностью.
Глава . Биматричные игры
Функция выигрыша биматричной игры представляет собой две платежные матрицы : А - определяет выигрыш первого игрока, а В - выигрыш второго игрока. Первый игрок имеет 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 |
1 |
G1={(1,1),(1,3),(3,2),(3,3)}
G2={(1,1),(2,1),(2,3),(3,2)} G = {(1,1),(3,2)}
I v(1,1)= 3 II v(1,1)= 3
v(3,2)= 3 v(3,2)= 2
Таким образом, если в биматричной игре несколько равновесных ситуаций, то по выгодности они не равнозначны, в отличие от матричных игр.
Из примера хорошо видно, что хотя (1,1) и (3,2) - ситуации равновесия, ситуации (1,2) и (3,1) таковыми не являются, в отличие от матричных игр.
Принципиальным отличием биматричных игр от матричных является отсутствие в них антагонизма.В матричных играх переговоры между игроками были бессмысленны, так как их интересы были прямо противоположны, в биматритчных играх договоры между участниками имеют реальное основание.
Так, в рассматриваемом примере второй игрок заинтересован в том, чтобы первый выбрал i=1, так как при этом v(II)= 3. Первому же игроку с точки зрения выгоды безразлично какую стратегию выбрать - первую или третью - в любом случае его выигрыш составляет 3. Если первый игрок доброжелательно настроен по отношению к противнику, то он выберет первую стратегию, чтобы и второй игрок получил максимальный выигрыш. В противном случае первый потребует за выбор более выгодной для второго стратегии дополнительную плату, и если эта плата будет меньше единицы, то очевидно, что второй игрок согласится на эту сделку.Такая игра называется игрой с побочными платежами.
Если в биматричной игре ситуаций равновесия нет, но игроки имеют возможность договориться между собой, то обычно применяют такой искусственный прием: находится i*j* такая,что:
max ( aij + bij ) = ( ai*j* + bi*j* )
и делится между игроками по заранее оговоренному правилу.
Пример.
|
3 |
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 |
3 |
max = 5, ( i, j ) = (3,2). Эта сумма должна быть разделена между первым и вторым игроками.
В случае, если договор между игроками невозможен, игра станет неустойчивой и игрокам будет выгодно скрывать свои стратегии. Решение такой игры будет в смешанных, вероятностных стратегиях.
Понятие смешанных стратегий в биматричных играх такое же, как и в матричных играх, то есть это полный набор вероятностей применения их чистых стратегий. Выигрыш игроков тоже находится как математическое ожидание.
Задание по биматричным играм
Придумать условие биматричной игры n*m, n = m > 3 и найти ее решения в чистых стратегиях ("игра с побочными платежами")
Глава . Нестратегические игры
1. Основные понятия и определения.
На практике достаточно часто встречаются случаи, когда в типично игровых ситуациях участники вступают между собой в соглашения, образуют союзы, коалиции, корпорации, тресты, обьединения и т.п. При рассмотрении стратегических игр предполагалось, что каждый игрок действует изолированно от других, но в общем случае такое поведение не всегда выгодно. В решении биматричной игры с побочными платежами можно легко в этом убедиться.
Рассмотрим биматричную игру с побочными платежами. Если участники по условию игры в состоянии договориться с друг другом, то решение - то есть выигрыши игроков, не будет зависеть от выбираемых ими стратегий, а только лишь от способа дележа общего дохода. При этом для них важно еще и то, насколько выгодно им вступать в такое соглашение или коалицию.
Коалицией в кооперативное игре называется всякое (любое) подмножество множества игроков.
Пример. Пусть I = {1,2,...i...n} - некоторое множество игроков. Коалициями будут: k1 = {1,2,5,i};
k2 = {i} = i;
k3 = { } = ;
k4 = { 1,2,...n} = I.
Когда игроки обьеденены в коалицию, естественно рассматривать их общий выигрыш, который может быть получен в игре. Разумеется, игроков интересует максимально гарантированный выигрыш, который и является мерой полезности обьединения игроков.
Характеристической функцией v(k) называется наибольший выигрыш, уверенно получаемый коалицией k.
Пример. Допустим, существует небольшая бригада состоящая из двух рабочих и мастера. Дневное задание может выполняться всей бригадой или мастером с одним из рабочих. Выполнение дневного задания гарантирует бригаде заработок в С единиц (выигрыш).
Задать характеристическую функцию этой игры.
I = { M, p1, p2 } - множество игроков игры. Тогда
v() = v(p1, p2) = v (p1) = v (p2)= v (M) = 0,
v (M, p1, p2) = v( M,p1) = v( M, p2) = C.
Из заданной характеристической функции видно в какие коалиции выгодно вступать игрокам, так как выигрыш существенно зависит от состава коалиций. Таким образом, характеристическая функция задается на множестве всех подмножеств множества игроков I игры Г и принимает вещественные значеня.
Свойства характеристической функции:
1. Персональность vГ () = 0;
2. Супераддитивность vГ (КL) vГ (К) + vГ (L), где K,LI, KL = ;
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) + i, i 0, i I;
i = v(I) - v(i)
Нетрудно видеть, что компоненты вектора х удовлетворяют условию индивидуальной рациональности. Условие кооперативной рациональности
xi = v (i) + v(I) - v(i) = v(I) также выполняется.
i - это добавочный выигрыш игрока, получаемый за счет кооперации с другими участниками.
Важной отличительной чертой кооперативных игр является то, что для каждого игрока имеет значение не выигрыш коалиции в той или иной ситуации, а результат дележа, независящий от выбора стратегий. Поэтому этот класс игр называется нестратегическим.
В соответствии с приведенным определением можно построить бесконечное множество классических кооперативных игр. Для изучения их свойств игры делятся на непересекающиеся классы, внутри которых игры обладают одинаковыми или близкими свойствами.
Существующая классификация делит все кооперативные игры, прежде всего, на существенные и несущественные.
Несущественной игрой называется кооперативная игра, в которой характеристическая функция любой коалиции равна сумме характеристических функций любых подкоалиций.
v (КL) = v (К) + v (L), где K,LI, KL = ;
Существенными называются остальные игры.
Любая кооперативная игра с аддитивной (а не супераддитивной) характеристической функцией является несущественной, ее участники не заинтересованы в образовании коалиций, так как это не увеличивает их выигрыш (долю).
Признак аддитивности характеристической функции задается теоремой:
Теорема. Для того, чтобы характеристическая функция была аддитивной, необходимо и достаточно, чтобы выполнялось равенство v(i) = v(I).
Если в соответствии с этим признаком окажется, что рассматриваемая кооперативная игра несуществена, то характеристические функции легко можно найти по аддитивным формулам. Так же просто могут быть определены и дележи.
Теорема. В несущественной игре существуе только один дележ
( v(1), v(2),... v(n) ).
Во всякой существенной игре множество дележей бесконечно.
Это обьясняется тем, что в существенной игре обязательно существует
= v(I) - v(i) 0,
которая может быть разделена между игроками бесконечным большим числом способов.
Игроки так же делятся на существенных и несущественных (болванов), а множества игроков - на носителей игры и множества болванов.
Существенным называется игрок i, если существует такая коалиция К, что
v(K) + v(i) < v(Ki).
Болваном называется игрок i, если для любой коалиции KI cправедливо
v(K) + v(i) = v( Ki).
Допустим, L - множество болванов (несущественных игроков) и LK, тогда
v(K) = v(K\ L) + v(i), а если K = L, то v(K) = v(i).
Существенные игроки образуют множество носителей игры, NI. Признаком этого для коалиции К является:
v(K) = v(KN) + v(i) i K\N.
3. Аффинно-эквивалентные игры.
Существенные и несущественные игры тоже делятся на классы.
Кооперативная игра с множеством игроков I и характеристической функцией v называется аффинно-эквивалентной игре с тем же множеством игроков и характеристической функцией v’, если найдутся такое положительное число k и произвольные вещественные ci ( i I ), что для любой коалиции K L имеет место равенство:
v’(K) = k v(K) + ci , iK.
При афинной эквивалентности 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) - iK v(i))/ ( v(I) - iI v(i)) (3.1.)
Нетрудно видеть, что 0-1 редуцированная форма существенной кооперативной игры позволяет по характеристической функции сразу же судить об эффективности обьединения в коалицию (см.знаменатель), то есть в чистом виде рассматривать свойство супераддитивности.
Все дележи в 0-1 редуцированной форме должны отвечать условиям: xi 0, так как v(i) = 0, но есть еще , так как игра существенная 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) - iI 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 |
1 |