Модель поддержки принятия решений по формированию коалиций в условиях неопределенности А. А. Кулинич Институт проблем управления РАН. - презентация

1 Модель поддержки принятия решений по формированию коалиций в условиях неопределенности А. А. Кулинич Институт проблем управления РАН

2 Постановка задачи Для каждого игрока i N определены: 1. Модель объекта управления M i (A); 2. Цель управления G i ; 3. Ресурсы управления R i ; 4. Стратегии управления S i. Задано: 1. Динамический (социальный, политический, экономический) объект управления A; 2. Множество заинтересованных сторон (игроков) N N G1G1 G4G4 G2G2 G3G3 G5G5 GNGN S1S1 S2S2 S3S3 S4S4 S5S5 SNSN Каждый игрок i N пытается перевести объект А в целевое состояние G i, применяя для этого собственные ресурсы R i в рамках некоторой стратегии S i.

3 Задачи коалиционного управления динамической системой Под коалиционным управлением динамической системой понимается управление, при котором подмножество заинтересованных сторон K N объединяют свои ресурсы R i с целью достижения своих целей G i. 1. Выбор сторонников по коалиции (K N ) 2. Обеспечение устойчивости коалиции Под устойчивостью коалиции понимается равновесная ситуация, в которой каждому участнику коалиции не выгодно ее покидать. Выбор метода решения этих задачи зависит от: 1. Уровня информированности каждой из сторон о целях, ресурсах, стратегиях потенциальных сторонников; 2. Предсказуемости поведения потенциальных сторонников; 3. Возможности дележа, полученного коалицией выигрыша. 1. В условиях полной информированности возможно аналитическое решение задачи коалиционного управления в рамках теории коалиционных игр. 2. В условиях неопределенности возможны правдоподобные решения задачи коалиционного управления, получаемые с помощью советующей системы.

4 Модель объекта управления (когнитивная карта) * Когнитивная карта – это модель представления знаний эксперта о динамической системе. Когнитивная карта определена как орграф G=(F,W): F = {f i }- факторы ситуации; W – матрица смежности орграфа; X(0) = (x 1,…, x n ) – начальное состояние, x i 0; P(0) = (p 1,…, p n ) – входное воздействие, p i [-1,1]; * Новиков Д.А. «Когнитивные игры»: линейная импульсная модель. Проблемы управления. 3, 2008 г. Прогноз развития ситуации: P(t+1)=W · P(t), где P(t) – вектор приращений значений факторов в моменты времени 0 < t n ; p i (t+1)= w ji · p j (t) - элемент вектора приращения в момент t+1. Состояние ситуации в момент времени t+1 определяется из соотношения: X(t+1)=X(t)+P(t+1), где X(t) – состояние ситуации в момент времени t. Целевой фактор Входной фактор

5 Постановка задачи: коалиционного управления динамической системой в условиях полной информированности 1. N – множество заинтересованных сторон (игроков); 2.Y(t+1) = W Y(t) – модель динамической системы; 3. I i F - множество входных факторов игрока i N; 4. R i =(r i1,…,r im ) - ресурсы управления игрока; 5. S i = r ij – множество стратегий игрока i, j=1..m, s q S i, s q =(x q 1,…,x q e ) - стратегия игрока (вектор входных воздействий для управления ситуацией); 6. O i F - множество целевых факторов, G i =(g i1,…,g in ) - цель игрока; 7. f i (Y*, s iq, ) - целевая функция игрока i, Y*- прогноз развития ситуации для стратегии игрока i - s iq, – стратегии других игроков; 8. К N - множество игроков, объединившихся в коалицию (2 N -1); 9. S K = S i - множество стратегий коалиции K, i К. 10. S N\K = S i - множество стратегий коалиции N\K, i N\К. 11. Для игрока q N необходимо найти такую коалицию К и такую стратегию этой коалиции s j K S K, что для всех игроков этой коалиции i К выполняется следующее условие : f i (Y i *, s j K, s t N\K )> f i (Y *, s j K |s iq S N\K, s N\K ), s i K S K, s j N\K S N\K, s iq S i, i К.

6 Коалиционная игра в условиях полной информированности 12. Коалиционная игра в характеристической форме задается множеством игроков N и характеристической функцией ( ), определенной на подмножествах игроков - возможных коалициях – (N, ( ) ); 13. (K) - значение характеристической функции определяет выигрыш коалиции (K N); 14. x=(x 1, x 2, …, x n ) – дележ выигрыша коалиции, x E( ), E( ) – множество дележей игры (N, ( ) ),. 15. Решение коалиционной игры – это множество недоминируемых дележей E * ( ) E( ) игры (N, ( ) ), x *s x d, x * E * ( ), x E( )\ E * ( ) ; 16. Устойчивость коалиции обеспечивает дележ, отказаться от которого игроки не могут. 17. Методы решения коалиционной игры: С-ядро, НМ-решения, вектор Шепли и др.

7 1. N – множество заинтересованных сторон (игроков); 2. (A) – модель динамической системы; 3. - ресурсы управления игрока; 4. - множество стратегий игрока i; 5. - цель игрока; 6. - прогноз развития ситуации; 7. - выигрыш коалиции; 1. Nishizaki I., Sakawa M. Fuzzy cooperative games arising from linear production programming problems with fuzzy parameters. Fuzzy Sets and Systems 114 (2000) pp Aubin J.P., Cooperative fuzzy games. Mathematical Operational Research. 6 (1981), pp. 1–13. Теория коалиционных игр в условиях полной информированности позволяет предсказать результаты переговоров и предложить дележ, обеспечивающий устойчивость коалиции. (Трансферабельность полезности, рациональность игроков) Решение задачи коалиционного управления динамической системой в нечетких условиях

8 ПЕРЕГОВОРЫ Решение задачи коалиционного управления динамической системой в условиях неопределенности Этапы переговоров Содержание этапа Системы поддержки принятия решений Подготовка Аналитическая работа: анализ обстановки, выделение потенциальных сторонников, исследование вариантов решений и т.д. Data mining, имитационное моделирование и др. Собственно переговоры Обмен информацией, поиск компромиссных решений и обеспечение их устойчивости. INSPIRE, Smart Settle Анализ результатов переговоров Анализ полученного решения, поиск возможностей улучшить решение и т.д. INSPIRE, Smart Settle * Э.А. Трахтенгерц. Компьютерная поддержка переговоров при согласовании управленческих решений. СИНТЕГ Компьютерная поддержка переговоров * Функции переговоров: информационная; коммуникативная; координация действий; контроль; отвлечени е внимания; пропаганд а ; проволоч ки

9 Модель формирования коалиций включает: 1. Нечеткую модель объекта управления (А); 2. Экспертные нечеткие характеристики игроков (цели, ресурсы, стратегии ); 3. Необходимые и достаточные условия привлекательности заинтересованной стороны в качестве сторонника по коалиции. Компьютерные системы поддержки принятия решений, основанные на экспертных знаниях Объяснение решений; Альтернативность решений; Открытость; Дружественные интерфейсы (когнитивная графика).

10 Нечеткая модель объекта управления Модель объекта управления представлена в виде нечеткой когнитивной карты, основанной на правилах (Rule Based Cognitive Map): F={f i } - множество факторов ситуации, i=1…n; Лингвистическая переменная, где f-название переменной, L –множество лингвистических значений и их функции принадлежности L i ={l ij \ }, i=1…n, j=1…m - упорядоченное множество лингвистических значений фактора f i, - функция принадлежности лингвистического значения l ij, Х- носитель нечеткого множества. f i = «Цены на нефть» L={l ij }, j=1,…,5; l i1 =«Очень малый»; l i2 =«Малый»; l i3 =«Средний»; l i4 =«Большой»; l i5 =«Очень большой» X=[0, 200] $\баррель abc

11 Нечеткая модель объекта управления Динамика изменения значений факторов ситуации в нечеткой когнитивной карте задается отображением: W:Y(t) Y(t+1), где Y(t) – состояние ситуации ; W - система нечетких правил «Если, То», заданная на множестве лингвистических значений факторов ситуации: «Если x 1 есть A 1 и x 2 есть С 1 и x 3 есть D 1 и т.д., То y есть B 1 »; «Если x 1 есть A 2 и x 2 есть С 2 и x 3 есть D 2 и т.д., То y есть B 2 »; «Если x 1 есть A m и x 2 есть С 4 и x 3 есть D 5 и т.д., То y есть B 3 »; ПРИМЕР: П1. Если «Спрос на нефтепродукты» есть «Малый» и «Предложение нефтепродуктов» есть «Большое» и «Уровень конкуренции» есть «Очень высокий» То «Цены на нефтепродукты» есть «Очень Низкие» П2. Если «Спрос на нефтепродукты» есть «Средний» и «Предложение нефтепродуктов» есть «Большое» и «Уровень конкуренции» есть «Очень высокий» То «Цены на нефтепродукты» есть «Низкие» П3. Если «Спрос на нефтепродукты» есть «Большой» и «Предложение нефтепродуктов» есть «Большое» и «Уровень конкуренции» есть «Очень высокий» То «Цены на нефтепродукты» есть «Средние» x 1 ={A 1,A 2,…,A 5 } x 2 ={C 1,C 2,…,C 5 } x 3 ={D 1,D 2,…,D 5 } y={B 1,B 2,…,B 5 }

12 Нечеткая модель объекта управления Прогноз развития ситуации получается методом последовательных итераций. Вывод на каждой итерации осуществляется с использованием модели Мамдани. Y q (1)=W Y q (0), Y q (2)=W Y q (1),…, Y q (n)=W Y q (n-1) Состояние (прогноз развития) ситуации на n шагах есть вектор: Y(n)=(,, …, ), где = ( l i1 \,…, l i1 \ ), l ij L i лингвистические значения прогнозного вектора, – степень неопределенности прогноза на шаге n, [0,1]. ПРИМЕР: L 1 = Цены на нефть; L 2 = Цены на продукты питания; L 3 = Инфляция Лингвистические значения (i=1,2,3): l i1 =«Очень малый»; l i2 =«Малый»; l i3 =«Средний»; l i4 =«Большой»; l i5 =«Очень большой» Y(n)=(l 11 /0, l 12 /0.7, l 13 /1.0, l 14 /0.6, l 15 /0; l 21 /0, l 22 /0.4, l 23 /1.0, l 24 /0.3, l 25 /0; l 31 /0, l 32 /0.1, l 33 /1.0, l 34 /0.6, l 35 /0) (Цены на нефть) = [Очень малый /0, Малый /0.7, Средний /1.0, Большой /0.6, Очень большой /0]; (Цены на продукты питания)= [Очень малый /0, Малый /0.2, Средний /0.4, Большой /1.0, Очень большой /0.1]; ( Инфляция)= [Очень малый /0, Малый /0.1, Средний /1.0, Большой/0.6, Очень большой /0])

13 Участники конфликтной ситуации Каждый игрок определен кортежем: g q, r q, e q, q (Y q, g q ), где экспертные характеристики игроков: g q - правдоподобная цель игрока q N; r q - правдоподобная стратегия игрока q N; e q – прогнозируемая эффективность достижения игроком q N собственной цели ; q (Y q, g q ) – возможность достижения игроком q N своей цели в условиях противодействия потенциальных противников.

14 Правдоподобная цель игрока (Участники конфликтной ситуации) Правдоподобная цель игрока q N - g q = (,…, ) = (l 1j / L1 (l 1j ),…,l nb / Ln (l nb )) (l 1j,…,l nb ) - лингвистические значения целевого вектора; ( L1 (l 1j ),…, Ln (l nb )) – степень уверенности игрока, принимающего решение, в значении факторов целевого вектора игрока q N. Целевые факторы (f i ): 1. Цены на нефть; 2. Цены на продукты питания 3. Инфляция Лингвистические значения (i=1,2,3): l i1 =«Очень малый»; l i2 =«Малый»; l i3 =«Средний»; l i4 =«Большой»; l i5 =«Очень большой» Правдоподобная цель: g q = (,, ) = (l 11 /0, l 12 /0.7, l 13 /1.0, l 14 /0.6, l 15 /0; l 21 /0, l 22 /0.4, l 23 /1.0, l 24 /0.3, l 25 /0; l 31 /0, l 32 /0.1, l 33 /1.0, l 34 /0.6, l 35 /0) (Цены на нефть) = Очень малый /0, Малый /0.7, Средний /1.0, Большой /0.6, Очень большой /0; (Цены на продукты питания) = Очень малый /0, Малый /0.4, Средний /1.0, Большой /0.3, Очень большой /0; (Инфляция) = Очень малый /0, Малый /0.1, Средний /1.0, Большой/0.6, Очень большой /0;

15 Правдоподобная стратегия игрока ( Участники конфликтной ситуации) Правдоподобная стратегия игрока q N - r q =(,…, ) = (l 1j / L1 (l 1j ),…,l nb / Ln (l nb )) – правдоподобная стратегия управления, l i j - лингвистическое значение ресурса; L1 (l 1j ) - степень уверенности в значении l i j ; q N. Факторы ресурсов (f i ): 1. Административный ресурс; 2. Информационный ресурс; 3.Депозиты. Лингвистические значения (i=1,2,3): l i1 =«Очень малый»; l i2 =«Малый»; l i3 =«Средний»; l i4 =«Большой»; l i5 =«Очень большой». Правдоподобная стратегия: r q = (,, ) = (l 11 /0, l 12 /0.7, l 13 /1.0, l 14 /0.6, l 15 /0; l 21 /0, l 22 /0.4, l 23 /1.0, l 24 /0.3, l 25 /0; l 31 /0, l 32 /0.1, l 33 /1.0, l 34 /0.6, l 35 /0) (Административный ресурс) = Очень малый /0, Малый /0.7, Средний /1.0, Большой /0.6, Очень большой /0; (Информационный ресурс) = Очень малый /0, Малый /0.4, Средний/1.0, Большой /0.3, Очень большой /0; (Депозиты) = Очень малый /0, Малый /0.1, Средний /1.0, Большой/0.6, Очень большой /0;

16 Прогнозируемая эффективность достижения цели (Участники конфликтной ситуации ) e q :(u(g q ),(v(r q ))) R + - прогнозируемая эффективность достижения игроком цели, где u(g q ) – прогнозируемая полезность целевой ситуации, u:g q R + ; v(r q ) – затраты игрока для достижения целевой ситуации для правдоподобной стратегии r q, :r q R + ;

17 Возможность достижения целевой ситуации (Участники конфликтной ситуации) (Y q,g q ) - возможность достижения игроком q K своей цели только за счет собственных ресурсов в условиях противодействия игроков противников, определяется как степень нечеткого включения прогнозной ситуации Y q его целевую ситуацию g q : (Y q,g q ) = (1-Y q, g q ) Y q – прогноз развития ситуации при условии противодействия противников только за счет собственных ресурсов для игрока q K.

18 Потенциальные сторонники (противники) (Участники конфликтной ситуации) Определение. Потенциальными сторонниками игрока i N называются игроки q N, степень нечеткого включения правдоподобных целей которых в правдоподобную цель игрока, принимающего решение, превышает порог нечеткого включения t inc 0.5 : (g q, g i )= (1-g q, g i ), q i, q,i=1…n, q,i N. Если (g q,g i ) 0.5, То q,i K - потенциальные сторонники; Если (g q,g i )

19 Прогноз развития ситуации, при условии противодействия противников (Участники конфликтной ситуации) Правдоподобная стратегия потенциальных противников r N|K есть нечеткая сумма их правдоподобных стратегий: r N|K = Прогноз развития ситуации Y q при условии противодействия и только за счет собственных ресурсов: Y q (1)=W r q r N\K, Y q (2)=W Y q (1),…, Y q (n)=W Y q (n-1) Y q (n) – прогноз развития ситуации игрока q N, при условии противодействия противников только за счет собственных ресурсов r q. (Y q,g q ) = (1-Y q (n), g q )

20 Необходимые условия образования коалиции Структура информированности игрока, принимающего решение: g q - правдоподобная цель игрока q N; r q - правдоподобная стратегия игрока q N; e q – эффективность достижения игроком q N своей цели; q (Y q, g q ) – возможность достижения игроком q N своей цели в условиях противодействия потенциальных противников. Необходимым условием привлекательности игрока в качестве сторонника по коалиции является нечеткое включение его целевого g q состояния в целевое состояние g i игрока принимающего решение по созданию коалиции: q K, если (g i,g q ) 0,5, q i, q,i=1…n.

21 Критерий устойчивости коалиции (Достаточные условия образования коалиции) Устойчивость коалиции обеспечивает рациональное распределение выигрыша коалиции: дележ выигрыша. Анализ устойчивости возможных коалиций на основе анализа индивидуальных характеристик игроков и их взаимной полезности. Коалиция – управляющая система: Множество элементов; Функции элементов; Связи между элементами; Целостность. С.Д. Брамс, А.Д. Тейлор. Делим по справедливости, или гарантия выигрыша каждому. - М.: СИНТЕГ, 2002, 196 с. Методы справедливого дележа: «очередность», «дели-и-выбирай», «подстраивающийся победитель». Критерии справедливого дележа: отсутствие зависти, равноценность и эффективность. Объект управления Коалиция К Управляющая система

22 Индексы влияния Пример: взвешенная мажоритарная игра Диктатор: (51; 51, 25, 24); Вектор Шепли: (1, 0, 0); Коалиции: {1}. Равные силы: (2; 1, 1, 1); Вектор Шепли: (,, ); Коалиции: {1,2}, {1,3}, {2,3}, {1,2,3}. Индексы влияния характеризуют возможности игроков влиять на исход голосования. Индексы влияния – это индивидуальная характеристика игрока, определяющее его силу (власть). (Шепли-Шубик, Банцаф, Джонсон, и др.) 1. Shapley L.S., Shubik M. A method for Evaluting the Distribution of Power in a Committee System // American Political Science Review. V P Banzhaf J. F. Weighted Voting Doesn' t Work: А Mathematical Analysis // Rutgers Law Review. V P Алескеров Ф.Т. Индексы влияния, учитывающие предпочтения участников по созданию коалиций // ДАН Т С

23 Критерий привлекательности игрока для образования устойчивой коалиции (Достаточные условия образования коалиции) Критерий привлекательности для образования устойчивой коалиции строится как функция от уровня мотиваций участия в конфликтной ситуации и уровня мотиваций объединения в коалицию: m q =f(m e, m ). где m e - уровень мотиваций игроков участия в конфликтной ситуации m - уровень мотиваций игроков объединения в коалицию

24 Уровень мотиваций участия в конфликтной ситуации ( Достаточные условия образования коалиции) 1. е 1 - [0 е 1- ]. Это интервал низкой эффективности, в котором затраты игрока для достижения целевой ситуации больше выигрыша от ее достижения. 2. е 2 - [1+ е 1- ] характеризуется большими мотивациями участников игры для достижения целевой ситуации. Мотивации участия и неучастия игрока приблизительно равны. 3. е 3 - [E max е 1+ ]. Здесь игрок получает выигрыш, превышающий затраты на его получение, и, следовательно, мотивации участия в игре для достижения целевой ситуации достаточно высокие. m e =e q /E max - уровень мотиваций участия в конфликтной ситуации e1e1 e2e2 e3e3 Высокий Средний Низкий Гипотеза 1. Чем выше эффективность достижения целевой ситуации e q игрока q K, тем выше его уровень мотивации участия в игре М е = {е 1,е 2,е 3 } = {«Низкий», «Средний», «Высокий»}

25 Уровень мотивации объединения в коалицию ( Достаточные условия образования коалиции ) [ ]. Здесь возможность достичь целевой ситуации за счет собственных ресурсов низкая. Мотивации образования коалиции в этом случае высокие [ ], где - окрестность точки, в которой шансы достичь целевой ситуации или не достичь ее примерно равны. характеризует область высокого риска не достижения целевой ситуации. Здесь мотивации для образования коалиции средние [ ]. Игроки, возможность достижения целевой ситуации которых попадает в этот интервал, могут достичь целевой ситуации за счет только собственных ресурсов, т.е. мотивации для образования коалиции у таких игроков крайне низкие. Высокий Средний Низкий m =1- q - уровень мотиваций объединения игроков в коалиции Гипотеза 2. Чем выше возможность достижения целевой ситуации игрока q K собственными силами q, тем меньше у него уровень мотиваций поиска сторонников в игре (мотиваций образования коалиции). М = { 1, 2, 3 } = {«Низкий», «Средний», «Высокий»}

26 Привлекательность игрока для образования устойчивой коалиции Уровни мотивации объединения в коалицию m : М е = { 1, 2, 3 }={высокий, средний, низкий}. Уровни мотивации участия в конфликтной ситуации m е : М = {е 1,е 2,е 3 } ={высокий, средний, низкий}. Значения устойчивости мотиваций образования коалиции М q (интерпретация всех пар множества { 1, 2, 3 } {е 1,е 2,е 3 } ) : 1. Единоличники 2. Надежные сторонники 3. Привлекательные сторонники 4. Непривлекательные сторонники 5. Колеблющиеся сторонники 6. Чистые лоббисты 7. Лоббисты с личным интересом m q : М е М М q

27 Устойчивость коалиции (2) 1. Игроки из этой области имеют высокую эффективность достижения целевой ситуации, высокий уровень мотиваций участия в игре, и поэтому, толерантны к возможным вариантам дележа выигрыша. 2. Игроки из этой области имеют не высокую эффективность достижения целевой ситуации и, следовательно, невысокие мотивации участия в игре. Для этих участников необходимы преференции (или обещание преференций) при дележе выигрыша для повышения их мотиваций участия в игре. 3. Игроки из этой области могут рассматриваться как потенциальные сторонники, если мотивации их участия в игре будут увеличены при дележе выигрыша.

28 Выводы 1. Учитывая грубость описания целей, ресурсов и стратегий игроков, а также достаточно сильное допущение о единой для всех игроков нечеткой модели объекта управления, от приведенной выше модели поддержки принятия решений можно ожидать правдоподобные рекомендации, подсказки по выбору потенциальных сторонников для образования коалиции. 2. Система поддержки принятия решений, основанная на предложенной выше модели может быть использована на этапе подготовки переговорного процесса по образованию коалиции в условиях неопределенности.

29 Публикации 1. Кулинич А.А. Модель поддержки принятия решений для создания коалиции в условиях неопределенности. Четвертая международная конференция по проблемам управления (26 – 30 января 2009 года): Сборник трудов. М.: Учреждение Российской академии наук Институт проблем управления им. В.А. Трапезникова РАН, – 2030 с. стр Кулинич А.А. Модель выбора сторонников по коалиции в нечетких условиях. Интегрированные модели и мягкие вычисления в искусственном интеллекте. Сборник научных трудов V-й Международной научно-практической конференции (28-30 мая 2009 г., Коломна). В 2-х томах. Т.1. Стр Кулинич А. А. Выбор стратегии коалиционного управления динамической системой в условиях неопределенности. Третья Международная конференция «Системный анализ и информационные технологии» САИТ – 2009 (14 – 18 сентября 2009 г., Звенигород, Россия): Труды конференции. М., стр Кулинич А.А. Когнитивный подход поддержки принятия решений коалиционного управления ситуацией. VIII Международная конференция Когнитивный анализ и управление развитием ситуаций (CASC2009). Труды международной конференции (17-19 ноября 2009 г.) – М.: Институт проблем управления им. В.А. Трапезникова РАН. – 288 с. стр