Реферат: Теория принятий решений
Рассмотрим кооперативную игру Г = < 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.
Аксиома симметрии: игроки, входящие в игру симметрично, должны получать одинаковый доход. Здесь симметричность понимается как одинаковое влияние на характеристическую функцию. Это утверждение равносильно тому, что доход игрока не зависит от его номера или "имени".
