Воронов Е. М. Методы оптимизации управления ММС на основе стабильно-эффективных игровых решений (2001) (1264203), страница 20
Текст из файла (страница 20)
КЛАССИФИКАЦИЯ СТАБИЛЬНЫХ И ЭФФЕКТИВНЫХ РЕШЕНИЙНА ОСНОВЕ КОАЛИЦИОННОГО РАВНОВЕСИЯПонятие коалиционного равновесия базируется на фундаментальномпонятии V-решения, сформулированном в работе [39] (см. реферат даннойработы в приложении работы 1) при достаточно общем определении игры.Определение 3.1 [39]. Игрой называется наборГ = {N, S, {X K }, S(xK), { }},K(3.1)где N – произвольное множество объектов, S – произвольное множествоисходов игры, где в частном случае исход – значение показателя, X K –произвольное множество стратегий-решений коалиции K⊂N, S(xK)⊂S –множество возможных исходов, если коалиция K применяет стратегиюрешение xK∈X K , – транзитивное отношение предпочтений коалицииKK ⊂ N на S.Определение 3.2 [39].
Пара (K, xK), xK∈X K ≠∅ называется угрозой против исхода s∈S, если s ′ s для всехKs ′ ∈ S(xK).Определение 3.3 [39]. Пара (Q, xQ), xQ∈X Q ≠ ∅ называется контругрозой на угрозу (K, xK), если K∩Q≠ ∅ и для некоторого s′ ∈S(xK) и всехs′′ ∈S(xQ) имеет место s′′ s′ .Q1Cм. сноску в п.1.2.Стабильные эффективные решения и компромиссы. Часть I96Поясним определения 3.2 и 3.3. Пусть S = J(X) – множество достижимости значений функционалов – показателей эффективности игры намножестве решений X, где x = (x 1 ,…,x N )∈X, s = J(x)∈S.
Отношение предпочтений s s принимает вид J K ( x ) > J K ( x ) , где J K – показатель коаKлиции K⊂N. Подмножество S(x K )⊂S состоит из величин J(x||xK) при фиксированном решении xK∈X K коалиции K. Решение xK коалиции K являетсяугрозой относительно исхода игры s = J(x), если для любогоs ′ = J( x ′ ||xK)∈S(xK) имеет место J K ( x ′ ||xK) > J K (x).В свою очередь, решение xQ коалиции Q является контругрозой относительно угрозы xK коалиции K, если K∩Q≠∅, и для некоторогоs′ = J( x′ ||xK)∈S(xK) и всех s′′ = J( x′′ ||xQ)∈S(xQ), J Q ( x′′ ||xQ) > J Q ( x′ ||xK).Определение 3.4 [39]. Угроза считается эффективной, если на неенет контругрозы.
Исход игры считается оптимальным, если против негонет эффективных угроз. Множество всех оптимальных исходов естьV-решение.В [39] утверждается, что «в настоящее время кроме V-решения нет другого столь же простого, удобного для уточнений, но более сильного универсального решения».Существование V-решения связано с отсутствием «запрещенных ситуаций» в игре.Определение 3.5 [39].
Игра называется игрой без запрещенных ситуаций, если для любой ее реализации (P,x(P))(3.2)=S ( x ( P )) S ( x K ) ≠ ∅ ,K∈Pгде P – коалиционное разбиение, x(P) = (xK) K∈P – набор решений (ситуация).Отсутствие запрещенных ситуаций означает, что игру можно разыгратьбез согласования действий непересекающихся коалиций, когда независимый выбор любой коалицией своих решений в рамках данной структуры Pприводит к исходу игры.
Классы бескоалиционных и коалиционных игр,это, в основном, игры без запрещенных ситуаций. При ограничении действия коалиции выбором компонент дележа лишь своих членов кооперативная игра также является игрой без запрещенных ситуаций.Утверждение 3.1 [39]. Для любой игры без запрещенных ситуаций существует такая реализация игры (P, x(P)), чтоV⊃ S(x K ) ≠ ∅ .K ∈P(3.3)Э. Вилкас [39] отмечает, что в общем случае V-решение носит характерпредрешения, когда понятие оптимальности может уточняться и дополнить предрешение. При этом под уточнением решения автор понимаетопределение решения более узкого, чем V-решение, путем наложения дополнительных условий на контругрозу и модификации угрозы.Глава 3.
Стабильные и эффективные оптимальные решения97Ограничимся в дальнейшем более узким классом коалиционных игр(3.4)Г = {N, (X K ), (J K )}, K∈Р⊂Р,где N – множество объектов; X K = ∏ X i – множество стратегий-решенийi∈ Xкоалиции K⊂N; J K = {J i (x)} i∈K – векторная функция эффективности коалиции K, x∈X N (исходы игры Г).Для произвольной коалиционной структуры P, xP = {xK} K∈P , xK ∈X K .Тогда уточнение понятия V-решения может быть сформировано в видекоалиционного равновесия.Определение 3.6 [39]. Ситуация x P называется коалиционным равновесием, если принадлежит V-решению и для любых K∈P⊂P и xK∈X K :либо J i ( x P ) > J i ( x P x K ) хотя бы для одного i∈K,либо J i ( x P ) = J i ( x P x K ) для всех i∈K.Таким образом, ситуация x P будет коалиционным равновесием, еслиx P ∈V и для любого K∈P стратегия x P максимизирует по Парето векторвыигрышей J i ( x P x K ) в X K в том смысле, что если другая стратегиярешение дает больший выигрыш игроку i∈K , то одновременно она даетменьший выигрыш игроку j∈K .Очевидно, что принадлежность x P к V-решению означает «нежесткость» коалиционной структуры P, которая необходима, по меньшей мере,для образования контркоалиции при формировании контругрозы.Поэтому коалиционное равновесие определяется тремя «динамическими» факторами: множеством коалиционных структур P, видомV-решения и степенью «охвата» Парето-области коалиции.Утверждение 3.2.
В общем случае коалиционное равновесие реализуется на допустимом множестве коалиционных структур P (P∈P), котороеопределяется «начальным» P, набором возможных угроз K∉P и наборомсоответствующих контругроз (N\K)∉P.Наиболее общим коалиционным равновесием является сильное равновесие.Определение 3.7 [39]. Коалиционное равновесие называется сильным(абсолютным) равновесием x , если оно оптимально по Парето в X K относительно J i ( x x K ) , (i∈K) для всех K ⊂ N.Против сильного равновесия, очевидно, нет угроз.
Кроме того, оно является равновесием при любом P. Поэтому сильное равновесие являетсякоалиционным равновесием при любом P.98Стабильные эффективные решения и компромиссы. Часть IОпределение 3.8. Множество собственно коалиционных равновесийопределяется множеством оптимальных исходов в V-решении (множеством неэффективных угроз) на допустимом множестве коалиционныхструктур P при локальной Парето оптимизации в рамках коалиции.К собственно коалиционным равновесиям относится понятие угроз иконтругроз (УКУ-решения), введенное Вайсбордом–Жуковским [32, 50](см. также гл.
4).Определение 3.9. При отсутствии угроз (частный случай V-решения) ификсации коалиционной структуры P коалиционное равновесие x P при-()нимает вид векторного Нэш-равновесия (ВНР) x = x r , так как устойчивость данного равновесия определяется потерей эффективности при отклонении K-й коалиции от Парето-решения x K ∈ x P относительно вектораJ i ( x P x K ) , i∈K.Определение 3.10. При отсутствии угрозы и фиксации коалиционнойструктуры в виде одной коалиции K = N коалиционное равновесие x Pпринимает вид Парето-оптимального решения в задаче векторной оптимизации J i ( x K ) , i ∈ K =N(x = x ) .П«Сужение» множества решений может быть обеспечено тем или инымподходом Парето-оптимизации, например, Ω-оптимизацией на основе конусов доминирования [47, 428, 430]Ω = (x: BJ(x) ≥ 0),(3.5)где B – матрица конуса доминирования Ω.Этот подход Парето-оптимизации принят как основной в данной главе.Определение 3.11.
Подмножество ( xΩP , K ∈ P ) ВНР-решений называ-()ется Ω-равновесием xΩ = xΩr , если матрицы B K , K∈P многогранных конусов доминирования Парето-оптимизации коалиции K=Ω K {x K : B K J K ( x P x K ) ≥ 0} , K ∈ Pне равны единичной матрице B K ≠ E хотя бы частично.Определение 3.12. При отсутствии угроз, фиксации коалиционнойструктуры P и полной свертке показателей коалиции(3.6)ФK = ∑ αi J i , 0 ≤ αi ≤ 1, ∑ αi = 1, K ∈ Pi∈Kкоалиционное равновесие x P приобретает смысл скалярного Нэшравновесия.Определение 3.13.
При отсутствии угроз, фиксации набора коалиционных структур P (P∈P) и свертке показателей коалиции коалиционноеравновесие принимает вид кооперативного решения Харшаньи–Скеруса наоснове множества недоминируемых Нэш-равновесий на P [32].Глава 3. Стабильные и эффективные оптимальные решения99Данная классификация не претендует на полноту и может быть продолжена. Но даже и в представленном виде она показывает, что понятиекоалиционного равновесия является достаточно универсальным и включает, как частные случаи, поиск эффективных решений (Паретооптимальных, Ω-оптимальных и т.д.) и стабильных решений (скалярныхНэш-решений, векторных Нэш-решений, Ω-равновесных и т.д.).3.2.
АЛГОРИТМ ВЕКТОРНОЙ ОПТИМИЗАЦИИ НА ОСНОВЕ КОНУСОВДОМИНИРОВАНИЯ (ЭФФЕКТИВНЫЕ РЕШЕНИЯ)3.2.1.Сравнительный анализ методов векторной оптимизацииКак правило (см. [206] и, например, [32]), основным понятием оптимальности в задачах векторной оптимизации является Паретооптимальность, определение которой дано в свойствах коалиционногоравновесия (опр. 3.6.) и в главе 1.Следует отметить, что векторная оптимизация с определением областиПарето является частным подходом в общем классе кооперативных игр вхарактеристической форме, например [43, 199], где принципы оптимальности можно подразделить условно на два типа [32]:1) оптимальность, связанная с устойчивостью поведения игроков (оптимальность по Парето, C-ядро и Н–М-решение);2) оптимальность, которая явно или неявно предполагает наличие арбитра, формулирующего «разумные» свойства оптимального решения(арбитражная схема, среднеквадратическое решение, вектор дележаШепли).Все эти подходы будут обсуждаться в главе 5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
