Воронов Е. М. Методы оптимизации управления ММС на основе стабильно-эффективных игровых решений (2001) (1264203), страница 34
Текст из файла (страница 34)
Часть IУтверждение 5.4. Парето-граница Парето–Нэш-множества компромиссов однотипных ММС содержит множество предпосылок дележей.До к аз ат е льс тво . Как известно, Парето–Нэш-множество составляетпрямоугольный многомерный конус с вершиной в J ir (i ∈ N ),( BJ ≥ J r , B =E) , ограниченный Парето-границей J iП J iП ≥ J i ≥ J ir .Характеристическая функция (5.1) имеет вид ν(i ) =J ir1 , при этомrФNr1 \i1= ∑ J j . j∈N \i (5.9)Сравнение равновесия J ir (i ∈ N ) и ( J ir1 , ФNr1 / i ) показывает, что для однотипных систем с равными ресурсами оптимизация суммы имеет эффектлокальной Парето-оптимизации. Поэтому ситуация равновесия ( J ir1 , ФNr1 / i )«сместится» в сторону увеличения эффективности на множестве N \ i иуменьшения эффективности для системы i .
Следовательно, выполняетсяусловие индивидуальной рациональности дележа(5.10)J iП ≥ J ir ≥ J ir1 =ν(i ), i ∈ N .Условие коллективной рациональности выполняется тождественно(5.11)∑ J iП ≡ ν( N ) ,i∈Nпоэтому предпосылки дележей принадлежат Парето-решениям П–Н-множества компромиссов. Данное утверждение очевидно для N = 2 , так как вэтом случае J ir = ν(i ) .Утверждение теоремы очевидно и для характеристической функциивида (5.3).
В этом случае по определению___=J ir1 ≥ n(i ) max=min J i ; (i 1, n ),iN \iтак как равновесные значения функционалов «не хуже» [32], чем гарантированные.Поэтому J iП ≥ J i ≥ ν(i ) , таким образом, Парето-граница П–Н-множества содержит предпосылки дележей, среди которых может быть выбран наилучший.Далее, в данном пункте приводятся основные определения и утверждения кооперативных игр в форме характеристической функции касающиесяпонятий доминирования дележей, решения в форме С-ядра, НейманМоргенштерн-решения и их свойств.Определение 5.5.
Дележ J d' доминирует дележ J d'' по коалицииK ( J d' J d'' ) , если:Глава 5. Оценка эффективности кооперативного компромисса1771) J d' i > J d'' i для всех i ∈ K ,2)∑ J d'i≤ ν( K ) .(5.12)Первое условие очевидно, а второе условие означает, что члены коалиции в состоянии реализовать делёж, т.е. сумма выигрышей членов коалиции не должна превосходить уверенно получаемое ею количество, имеющего смысл приближения локального Парето-решения в равновесии( ν( K ), ν( N \ K )) .
Иначе, встретившись с дележом, дающим столько,сколько коалиция самостоятельно не в состоянии добиться, должна согласиться на него и не заниматься его сравнением с другими дележами.Определение 5.6 [199]. Дележ J d' доминирует дележ J d'' , если существует такая произвольная коалиция K ⊂ N, что J d' J d'' . Доминированиепо коалиции, состоящее из одного игрока, а также по множеству всех игроков невозможно, так как в этом случае нарушаются первое и второесвойство дележа.Определение 5.7 [199]. Множество всех недоминируемых дележей вкооперативной игре называется её С-ядром.
Любой делёж из С-ядраустойчив, так как ни одна коалиция не имеет желания изменить его.Утверждение 5.5. Если множество значений v является выпуклым, тоС-ядро не является пустым множеством.Главное основание утверждения – свойство супераддитивности v, прикотором v выпуклая 1.Следствие 5.1 [42]. Для несущественной игры С-ядро существует и состоит из единственного дележа.Следствие 5.2 [42]. Во всякой существенной игре с постоянной суммойС-ядро пусто.Утверждение 5.6 [42, 199].
Для того, чтобы дележи J d принадлежалиС-ядру, необходимо и достаточно, чтобы выполнялось неравенство(5.13)∑ J d i ≥ ν( K )i∈Sдля любой коалиции K ⊂N [K ≠ N, |K| >l), где |K| – мощность множества K.В работе [199] дана интерпретация результата в дифференциальных играх и сформулированы сложные условия оптимальности.В работе [42] дан способ формирования С-ядра в общих играх трёх лиц.Всё же часто С-ядро оказывается пусто.Определение 5.8.
Множество дележей L называется Нейман–Моргенштерн (Н–М)-решением с характеристической функцией ν , если:а) из J d′ , J d′′ ∈ L следует, что J d′ и J d′′ не доминируют друг друга (внут-1См. Розенмюллер Н. Кооперативные игры и рынки. – М.: Мир, 1974. – 160 с.178Стабильные эффективные решения и компромиссы. Часть Iренняя устойчивость); б) для всякого J d′ ∉L найдется такой J d′′ ∈L, что J d′′> J d′ (внешняя устойчивость).
Множество L расширяет множество С.Утверждение 5.7 [42]. Если в кооперативной игре существует С-ядроС- и Н–М-решение L, то C ⊂ Z.Методы поиска Н–М-решения трёх лиц даны в работе [42]. Некоторыеинтерпретации для дифференциальных игр на уровне условий и свойствоптимизационного подхода даны в работе [199].В общем случае [42] неизвестно каких-либо критериев, позволяющихсудить о наличии у кооперативной игры Н–М-решения. При наличииН–М-решений надо иметь в виду, что решения существенных кооперативных игр состоят более чем из одного дележа, поэтому выбор какоголибо конкретного Н–М-решения L ещё не определяет выигрыша каждого из игроков.Ввиду больших сложностей при определении существования и в способах отыскания оптимальных дележей на основе С-ядра и Н–М-решенийв играх общего вида особого внимания заслуживает подход на основе вектора Шепли, который на основе обоснованных предположений даёт практически реализуемое правило формирования оптимального дележа.5.3.
ФОРМИРОВАНИЕ ДЕЛЕЖА В ФОРМЕ ВЕКТОРА ШЕПЛИ5.3.1.Анализ общего выражения вектора Шепли [199]Условия оптимальности дележа на основе С-ядра и Н–М-решений идругих близких к ним подходов являются плохо обусловленными в условиях невыпуклости и некомпактности обсуждаемых множеств и труднореализуемыми даже при наличии наилучших свойств множеств.Поэтому [199] имеет смысл поставить вопрос о заранее ожидаемомопределённом значении выигрыша каждого игрока.
Оказывается, что некоторое априорно ожидаемое значение можно найти.Пусть π – любая перестановка множества N , т.е. преобразование каждого игрока i в π(i). Всего таких преобразований N!, где N – число элементов множества. Пусть игроки образуют одну коалицию, вступая в неё поодному в произвольном порядке, т.е. порядок вступления в коалицию случаен. Следовательно, игроки упорядочиваются согласно некоторой случайной перестановке π : N → N.Все перестановки равновероятны, т.е. имеют вероятность 1/N! каждая.Множество первых i игроков по порождённому перестановкой π порядкуобозначим через KiπKiπ = {k∈N| π(k) ≤ i}.Глава 5.
Оценка эффективности кооперативного компромисса179Когда игрок i входит в коалицию π(i)-м по порядку, то множество первых π(i) игроков равно K ππ(i )= {k ∈ N / π ( k ) ≤ π ( i )}, а множество игроков,вступивших в коалицию до него, имеет видK ππ(i ) \(i) = {k∈N| π(k) < π(i)}.Общий выигрыш коалиции K ππ(i ) \(i) есть ν ( K ππ(i ) \(i)).После вступления в коалицию i-го игрока равновесный выигрыш соот-()ветственно равен ν K ππ(i ) .) (()Тогда разность ν K ππ(i ) – ν K ππ(i ) \(i)) − «лепта» игрока i, вносимая имв коалициюK ππ(i ).Для пояснения изложенного рассмотрим пример:112π23 32313123 → K : (1),(1, 2)(1, 2,3) 2 → K : (1),(1,3)(1,3, 2) 3 → K : (2),(2,1)(2,1,3) π Ki ;1 → K : (2),(2,3)(2,3,1) 2 → K : (3),(3,1)(3,1, 2) 1 → K : (3),(3, 2)(3, 2,1) K ππ(1) = (1);(1); (2,1); (2,3,1), (3,1), (3,2,1) = (1); (2,1);(3,1);(2,3,1);K ππ(2) = (1,2); (1,3,2); (2), (2), (3,1,2)(3,2) = (1,2); (1,3,2);(2);(3,2) и т.д.;K ππ(1) \(1) = (0);(0); (2); (2,3), (3), (3,2) = (0); (2);(3);(2,3);K ππ(2) \(2) = (1);(1,3); (0); (0),(3,1), (3) = (1); (1,3);(0);(3) и т.д.;(ν K ππ(1))()– ν K ππ(1) \(1)) = ( ν (1) – ν (0); ν (1) – ν (0); ν (2,1) – ν (2);ν (2,3,1) – ν (2,3); ν (3,1) – ν (3); ν (3,2,1) – ν (3,2)).Определение 5.9.
Игрок i в кооперативной игре называется болваном,если() ()ν K ππ(i ) – ν K ππ(i ) \(i)) = ν (i).(5.14)То есть игрок i не привносит в коалицию ничего по сравнению с тем,что он имел бы, если бы действовал самостоятельно.Определение 5.10. Коалиция, содержащая всех игроков, не являющихся болванами,(5.15)R = {i∈N: ν (K) – ν (K\(i)) > ν (i), K ⊂ N, (i)⊂K}называется носителем игры.Стабильные эффективные решения и компромиссы. Часть I180Определение 5.11. Если R – носитель игры, а K – любая коалицияK ⊂ N, то(5.16)ν (K) = ν (RK)+∑ ν (i), (i)∈N\R,где N \ R − множество болванов.Так как игроки вступают в коалицию в любом порядке, то можносформировать «априорно ожидаемый выигрыш» игрока i как усредненнуюпо всем перестановкам «долю» игрока i [152, 119]1(5.17)=Ф∑ ν K ππ(i ) − ν K ππ(i ) \ (i ) .i (V )N! π() ()Определение 5.12.
ВекторФ( ν ) = {Ф i ( ν ), i = 1,N}называется вектором Шепли.В соответствии с примером:11Ф1=( ν)=[2 ( ν(1) − ν(0) ) +∑ [ν( K ππ(1) ) − ν( K ππ(1) \ (1))]3! π3!+ ( ν(2,1) − ν(2) ) + ( ν(3,1) − ν(3) ) + 2 ( ν(2,3,1) − ν(2,3) )] =1rrr= [2 J1r + ( J 2 + J1 ) − J 2r + J ( J 3 + J1 ) − J 3r + 2 ( J1 + J 2 + J 3 ) −6(5.18)(5.18а)−2 ( J 2 + J 3 ) ].rТаким образом, при малом N вектор Шепли можно получить непосредственно из общего выражения (5.17).5.3.2.Свойства вектора дележа ШеплиСвойство 5.1.
Основным свойством по определению является то, чтоФ i ( ν ) есть оценка выигрыша игрока, которая получена путем его усреднения по перестановкам множества N .Свойство 5.2 [42, 152, 199]. Для всякой характеристической функцииν существует единственный вектор Ф( ν ), удовлетворяющий трём следующим аксиомам:A1. Если R – носитель игры, то(5.19)∑ Фi ( ν) =ν( R) .i∈RЭта аксиома означает, что из общего выигрыша коалиции R выделяетсядополнительно «болвану» – или на «болванов» ничего не выделяется изобщественных средств и не взимается с них.А2.
Для любой перестановки π такой, чтоν (π(K)) = ν (K),гдеГлава 5. Оценка эффективности кооперативного компромисса181K = (i 1 …i K ), π(K) = (π(i 1 ) … π(i K )),Ф i ( ν ) = Ф π(i) ( ν ).(5.20)То есть игроки, одинаково входящие в коалицию, получают одинаковый выигрыш – или [152] игроки при переименовании получают те жезначения выигрыша (выигрыш не зависит от обозначений).А3.
Если ν′ и ν′′ – любые игры со своей характеристической функцией, то(5.21)Ф i ( ν′ + ν′′ ) = Ф i ( ν′ ) + Ф i ( ν′′ ),где( ν′ + ν′′ )(K) = ν′ (K)+ ν′′ (K).Это означает, что при участии игрока в двух играх выигрыши отдельных игр складываются.Свойство 5.3 [199]. Для любой характеристической функции векторШепли является дележом.До к аз ат е льс тво . На основании равенства (5.16) при K = Nν( N ) =ν( R ∩ N ) + ∑ ν(i ) =ν( R ) + O .i∈N \ RТо есть N является тривиальным носителем игры, поэтому из аксиомыА1 следует∑ Фi ( ν) =ν( N ) .i∈NУсловие коллективного рационального дележа выполнено.
Раскроемвыражение (17)1( ν){[ ν( K1 ) − ν( K1 \ (i ))] + ... + [ ν( K N ! ) − ν( K N ! \ (i ))]} ,Фi=N!где K i – все возможные коалиции, содержащие i-го игрока. Тогда, применяя свойство супераддитивности функции νν( Kl ) − ν( Kl \ (i )) ≥ ν(i ), l =1 N ! ,получим1[ N ! ν(i )] =ν(i ) .N!Условие индивидуальной рациональности дележа также выполнено.Следовательно, Ф( ν ) − вектор дележа.Свойство 5.4. Для того чтобы вектор Шепли принадлежал С-ядру,необходимо и достаточно, чтобы для любого K ⊂ N он удовлетворял условию∑ Фi ( ν) ≥ ν( K ), K ⊂ N .Фi ( ν) ≥i∈KДействительно, так как вектор Шепли является дележом, для негосправедливы все утверждения для дележей. Напомним, что С-ядро суще-182Стабильные эффективные решения и компромиссы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
