автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.10, диссертация на тему:Теоретико-игровые модели на линейных когнитивных картах в задачах информационного управления

Учреждение Российской Академии Наук Институт проблем управления им. В.А. Трапезнич-пвя ран

На правах ¡

Куливец Сергей Геннадьевич

ТЕОРЕТИКО-ИГРОВЫЕ МОДЕЛИ НА ЛИНЕЙНЫХ КОГНИТИВНЫХ КАРТАХ В ЗАДАЧАХ ИНФОРМАЦИОННОГО УПРАВЛЕНИЯ

Специальность: 05.13.10- «Управление в социальных и экономических

системах»

Автореферат

диссертации на соискание ученой степени кандидата технических наук

2 7 ОКТ 2011

Москва-2011

4858453

Работа выполнена в Учреждении Российской академии наук Институте проблем управления им. В.А. Трапезникова РАН

Научный руководитель: доктор технических наук,

профессор Кузнецов Олег Петрович

Официальные оппоненты: доктор технических наук,

профессор Бурков Владимир Николаевич, Учреждение Российской академии наук Институт проблем управления им. В.А. Трапезникова РАН,

кандидат технических наук, Ройзензон Григорий Владимирович, Учреждение Российской академии наук Институт системного анализа РАН

Ведущая организация: Учреждение Российской академии наук

Вычислительный центр им. A.A. Дородницына РАН

Защита диссертации состоится «3 у> 2011г. в часов на

заседании диссертационного совета Д 002.226.02 при Учреждении Российской академии науюИнституте проблем управления им. В.А. Трапезникова РАН.

Ь-

С диссертацией можно ознакомиться в библиотеке ИЛУ РАН. Автореферат разослан « № » 1 г.

Ученый секретарь диссертационного совета,

кандидат технических наук (У Лебедев В.Н.

Общая характеристика работы Актуальность темы диссертации

Задачи математического моделирования конфликтных ситуаций, т.е. взаимодействия рациональных агентов с несовпадающими интересами исследуются на протяжении нескольких десятилетий и находят приложения в различных задачах управления в социальной, экономической и геополитической сферах. Модели конфликтных ситуаций широко используются при анализе, моделировании и оптимизации механизмов принятия управленческих решений в организационных системах для повышения эффективности их функционирования. Традиционным подходом к решению этих задач является теоретико-игровой подход, при котором взаимодействие агентов рассматривается как игра, интересы агентов (игроков) формулируются как функции выигрыша, правила выбора возможных действий - как стратегии поведения, причем предполагается, что каждый агент располагает сведениями о стратегиях и функциях выигрыша других агентов. Одним из актуальных аспектов теоретико-игрового подхода являются задачи управления игрой путем воздействия на параметры игры с целью получения ее исхода, благоприятного для одного из игроков или внешнего по отношению к игре управляющего органа. Теоретико-игровые модели управления исследовались в работах многих отечественных и зарубежных авторов: Ю.Б. Гермейера, H.H. Моисеева, В.А. Лефевра, В.Н. Буркова, Д.А. Новикова, Т.А. Таран, А.Г. Чхартишвили, В.А. Горелика, А.Ф. Кононенко, J. Harsanyi, R. Myerson и др.

В последнее время особенно активно развивается направление, связанное с информационным управлением и рефлексивными играми. При информационном управлении параметром игры, который подвергается управляющему воздействию, является информированность агентов. Понятно, что при такой постановке задачи требуется более детальная формализация понятия информированности. Рефлексивный подход детализирует это понятие с точки зрения информации о противнике: агент А учитывает не только свое знание об агенте В, но и знание агента В об А и т.д. Однако при моделировании реальных конфликтных взаимодействий требуется учитывать знания не только о сопернике, но и обо всей игровой обстановке, в которой происходит взаимодействие, т. е. о ситуации, в которой присутствует не только соперник, но и внешние факторы, которые могут различным образом влиять на исход игры. Такого рода знания в рамках

теоретико-игрового подхода к моделированию конфликтов учитываются недостаточно.

В то же время математические средства описания знаний о ситуации уже более 40 лет разрабатываются в рамках исследований по когнитивному анализу слабо структурированных ситуаций. Такими средствами являются когнитивные карты. Когнитивная карта - это набор причинно-следственных утверждений о взаимодействии факторов в фиксированной предметной области, представленный в виде взвешенного ориентированного графа. Существенное достоинство графового представления когнитивной карты заключается в том, что оно позволяет увидеть общую структуру целого множества взаимосвязанных утверждений и исследовать ее методами теории графов. Основополагающими работами в когнитивном анализе ситуаций являются работы R. Axelrod, В. Kosko, F. Roberts. Среди отечественных авторов, внесших заметный вклад в это направление, следует отметить работы В.Б. Силова, В.В. Кульбы, В.И. Максимова, Е.К. Корноушенко, A.A. Кулинича, О.П. Кузнецова, H.A. Абрамовой, Г.В. Гореловой и др. В рамках данного подхода имеются работы, исследующие задачу управления развитием слабо структурированной ситуации, представленной когнитивной картой. В частности, появляются работы, где управление осуществляют несколько ЛПР, стремящиеся достичь различных целей. Однако в этих работах не уделяется должного внимания основным принципам теоретико-игрового подхода: рациональности каждого из ЛПР, учета возможных стратегий других участников игры и т.д.

Таким образо.м, становится актуальной задача объединения двух направлений, которая формулируется как задача применения методов традиционного теоретико-игрового моделирования конфликтов к сложным, как правило, слабоструктурированным ситуациям, описываемым с помощью когнитивных карт. Это позволит более детально учитывать среду, в которой разворачиваются конфликты, и тем самым более адекватно моделировать реальные конфликты. Именно этой задаче посвящена настоящая работа, что и определяет ее актуальность. Цель и задачи работы

Цель работы состоит в разработке моделей конфликтного взаимодействия агентов с несогласованными представлениями в слабо структурированных ситуациях и информационного управления таким взаимодействием. При этом

предполагается, что знания агентов о ситуации, в которой происходит взаимодействие, представлены в виде линейных когнитивных карт.

Достижение поставленной цели требует решения следующих основных

задач:

1. Разработка подхода к моделированию конфликтных ситуаций, объединяющего теоретико-игровые методы и средства представления знаний о ситуации на основе когнитивных карт.

2. Разработка и исследование моделей и методов взаимодействия агентов в слабоструктурированных ситуациях, представленных когнитивными картами, включая:

a. модели взаимодействия агентов с фиксированными и нефиксированными целями;

b. модели взаимодействия агентов с несогласованными представлениями о ситуации;

c. постановка и решение задачи информационного управления в игре одним из агентов.

3. Создание программного комплекса, реализующего полученные модели и методы, и проведение на нем вычислительных экспериментов.

Методы исследований.

Основным методом исследования является математическое моделирование с использованием подходов и результатов теории игр, методов когнитивного анализа ситуаций, теории активных систем и исследования операций. Научная новизна.

В работе были построены и исследованы математические модели взаимодействия агентов с несовпадающими интересами для случая, когда их знания о ситуации формально представлены в виде линейной когнитивной карты. В результате проведенных исследований: 1. Построены две теоретико-игровые модели взаимодействия агентов (в виде игры в нормальной форме), в которых а) представления агентов о проблемной ситуации совпадают и заданы линейной когнитивной картой, б) управляющие факторы агентов различны. Для каждой из моделей показано существование и определен порядок поиска решения в рамках концепции решения игры в виде равновесия Нэша в чистых стратегиях.

2. Построены две теоретико-игровые модели взаимодействия агентов (в виде игры в нормальной форме), представления которых о проблемной ситуации не совпадают и заданы различными линейными когнитивными картами. Для каждой из моделей показано существование решения и определен метод его поиска в рамках концепции решения игры в виде равновесия Нэша в чистых стратегиях. Модели друг от друга отличаются записью функций полезности агентов:

a. в модели с нефиксированными целями управления цель каждого агента задается направлением изменений значения фиксированных факторов;

b. в модели с фиксированными целями управления цель каждого агента задается желаемыми значениями для фиксированных факторов.

3. Разработана модель информационного управления сложными социально-экономическими и политическими системами, в которых один агент воздействует на других в игре с несогласованными представлениями агентов с фиксированными целями управления. Сформулированы необходимые и достаточные условия возможности такого управления. Задача поиска информационного управления представлена как задача поиска оптимума функции с ограничениями в виде неравенств. Поиск решения осуществляется численными методами.

Практическая значимость.

Результаты диссертационной работы позволяют разрабатывать и обосновывать механизмы эффективного информационного управления при взаимодействии агентов в слабо структурированных ситуациях. Апробация работы.

Результаты диссертационной работы докладывались на: семинарах Института проблем управления им. В.А. Трапезникова РАН, на III Всероссийской молодежной конференции по проблемам управления (Москва, 2008), на У-й международной научно-технической конференции «Интегрированные модели и мягкие вычисления в искусственном интеллекте» (Коломна, 2009), на VI Всероссийской школе-семинаре молодых ученых «Управление большими системами» (Ижевск, 2009), на X Международной научно-технической конференции «Искусственный интеллект. Интеллектуальные системы» (Таганрог, 2009), на международной конференции СЛ8С'2009 (Москва, 2009), на научной сессии Московского

инженерно-физического института (Москва, 2010), на VII Всероссийской школе-семинаре молодых ученых «Управление большими системами» (Пермь, 2010), I Российской конференции с международным участием «Системный анализ и семиотическое моделирование». SASM'2011 (Казань, 2011), на XI Международной научной конференции им. Т.А. Таран ИАИ-2011 (Киев, 2011), на VIII Всероссийской школе-семинаре молодых ученых «Управление большими системами» (Магнитогорск, 2011), на Международной летней школе-семинаре по искусственному интеллекту для студентов, аспирантов и молодых ученых «Интеллектуальные системы и технологии: современное состояние и перспективы» (ISyT'2011) (Тверь, 2011), на 18-м Всемирном Конгрессе IFAC (Милан, 2011). Публикации.

Основные результаты научных исследований по теме диссертации содержатся в 16 публикациях, в их числе 2 публикации в ведущих научных журналах перечня Высшей аттестационной комиссии (в списке публикаций №№11 и 16) и 1 публикация на Всемирном конгрессе IFAC-2011 (в списке публикаций № 15). Структура и объем.

Диссертационная работа состоит из введения, четырех глав, заключения и списка литературы.

Содержание работы.

Во введении обосновывается актуальность темы диссертационной работы, определяется цель исследования, характеризуются используемые методы и описывается структура работы.

Первая глава диссертационной работы «Проблема моделирования конфликтного взаимодействия агентов в слабо структурированной проблемной ситуации» содержит описание проблемы и особенностей решаемой задачи, а также обзор методов и задач в области управления слабо структурированными ситуациями и информационного управления.

В разделе 1.1 обозначена проблемная область исследования на стыке нескольких областей. Определяется понятие когнитивная карта, кратко описаны две задачи анализа ситуаций на основе когнитивной карты: статический анализ и динамический анализ. Приведено определение понятию игра и перечислены базовые допущения в теории игр относительно агентов в игре. Кратко описаны

5

задачи взаимодействия агентов в слабо структурированной ситуации с согласованными и несогласованными представлениями, а также задача информационного управления таким взаимодействием.

В разделе 1.2 приведены основные понятия из теории игр, описана одна из базовых моделей игры и концепция решения равновесие Нэша в чистых стратегиях.

В разделе 1.3 подробно рассмотрено общее понятие когнитивной карты. Проведен обзор основных задач, для решения которых используются когнитивные карты. В частности, рассмотрена модель импульсных процессов в когнитивной карте, и на ее основе приведено решение обратной задачи с фиксированной и нефиксированной целью управления.

В разделе 1.4 подробно рассматриваются модели рефлексивных игр, понятия структуры информированности агента, решения рефлексивной игры, приводится определение задачи информационного управления.

Вторая глава «Игра в нормальной форме п агентов на линейной когнитивной карте» посвящена разработке и исследованию теоретико-игровых моделей взаимодействия агентов в слабо структурированной ситуации, представленной в виде линейной когнитивной карты.

В разделе 2.1 вводится понятие линейной когнитивной карты, как взвешенного орграфа, вершины и дуги которого удовлетворяют фиксированным условиям, и задано правило (I) изменения значений вершин. Каждая вершина орграфа представляет фактор предметной области. Множество всех факторов обозначим А/={1,Ориентированные дуги представляют причинно-следственные связи между факторами. Задается матрица смежности орграфа W, элементы которой щ е R соответствуют весам дуг орграфа.

Пусть время дискретно и начальному состоянию системы соответствует нулевой момент времени. Автономный импульсный процесс во взвешенном орграфе определяется по правилу (1) с вектором начальных значений факторов л(0)=(л(0), дг2(0), ..., хт(0)), х(0) ей™, и вектором р(0) = (pi(0), р2(0), ..., рт(0)), р(0) е Л™, задающим внешний импульс, вводимый в каждую вершину в нулевой момент времени.

1/еМ

Здесь - элементы ^(матрицы смежности орграфа). Зафиксируем дискретный момент времени Т(Т> 0). Тогда вектор значений всех факторов х(Т) будет определяться из выражения:

х(Т) = х(0)+р(0)+р(\)+...+р(Т-\) =х(0)+р{0)+р(0уП'+...+р(0) ]\'тл = = *(0)+р(0)(Е+И'+... +\¥гл) = х(0)+/;(0)',й где Е - единичная матрица. Матрица г@ = Е+1У+...+1Уг'' называется матрицей достижимости воздействий к моменту времени Т для матрицы смежности IV. Тогда сумма последовательных приращений для фактора ху представима в виде

(2)

1=0 кеМ

Здесь щщ ~ элементы матрицы

Задача управления слабо структурированной ситуацией одним ЛПР в модели линейной когнитивной карты формулируется следующим образом. Управляющими воздействиями будут внешние импульсы, вводимые в каждую вершину в начальный момент времени р(0), результатом управления будет совокупность значений всех факторов в фиксированный момент времени Т:

(3) х,(Г) = *;(0) + £Л.(0 = */0)+ Хг^.-рДО), ]ем.

/=0 кеМ

Цель управления задается условиями, накладываемыми на результат управления х(Т) = (х\(Т), х2(Т), ..., хт(Т)), х(Т) е К". Например, она может быть задана как набор желаемых значений для всех или некоторых концептов. В этом случае поиск управления сводится к задаче решения системы уравнений

В разделе 2.2 рассматривается определение игры на линейной когнитивной карте. Обозначим множество всех агентов через Я- {1,...,«}, линейную когнитивную карту с множеством факторов М= {1,...,т} и матрицей смежности Ж обозначим через С. Агент с номером 1 е N располагает непустым подмножеством факторов М, с М, доступных ему для управляющего воздействия. Для любых двух агентов и е N1 Л/,ПЛ/, = 0, и и^л» Мк С М, ]Л/,| = т,.

В векторе совместных управляющих воздействий р(0) = (р^), р2[й),..., р,„(0)) отражается воздействие каждого из агентов. Стратегия ¡-го агента задается вектором, состоящим из упорядоченных компонентов вектора р(0) с номерами из множества {к\,кг.....кт1) =Л/,: з, = (0), ркг (0),..., (0)]. Каждый

агент воздействует на ситуацию, задавая значения лишь для «своих» компонентов

7

вектора р(0). Остальные компоненты вектора р(0), на которые не воздействует пи один из агентов, равны нулю:

Вводя ограничения на управляющие воздействия по каждому фактору в виде отрезка: (ууе11 1еММк) р/0) е \рГ,рП где рГ>рГ е К< мы заДаем множество стратегий ¡-го агента как декартово произведение

[рГ-РП х К>Г1 * -*

Множество всех возможных стратегий агентов 51 х... х5„ далее для краткости будем называть гиперкубом. Будем рассматривать (у, как вектор стратегий

всех агентов а) е ^х.-.х^,,.

Для каждого агента определим на множестве результатов управления функцию полезности /¡{хх{Т)^2{Т),...,хт[Т)). Цель управления ¡-го агента заключается в максимизации значения функции /,. Рассмотрим по отдельности два случая, для которых будут построены функции полезности.

1. Агенту / важно неограниченное увеличение (либо уменьшение) значения фактора х.. Тогда в случае увеличения значения фактора необходимо максимизировать выражение (х/Т) - */0)), а в случае уменьшения значения фактора необходимо максимизировать выражение -(х/Т)

2. Агенту I важно неограниченное приближение значения фактора х) к некоторому выгодному для него значению Тогда будем считать, что для него желательно максимизировать выражение -(х/Т) -ху )2.

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

Функция полезности для первого случая будет иметь вид: (4) /1(х1(Т),хг(Т),...,хт(Т))=

¡ш

Здесь \y.jl - «доля важности» значения >го фактора среди остальных факторов для 1-го агента, у,у е [-1,1], сумма величин \у,}, из (4) равна единице. Знак коэффициента у,, отражает направление изменения значения фактора, выгодное для агента. Если уд > 0, то /'-й агент стремится неограниченно увеличить значение >го фактора. Если уц< 0, то ;'-й агент стремится неограниченно уменьшить

значение j-то фактора. Если у,у = 0, то /-му агенту безразлично значение j-го фактора.

Функция полезности для второго случая будет иметь вид:

Здесь у,у — « доля важности» значения у'-го фактора для г'-го агента, уи е [0, 1], сумма величин у,у, фигурирующих в правой части выражения (5) равна единице.

Фактор, в выражении для которого в записи функции полезности для 1-го агента в виде (4) или (5) коэффициент y,j Ф 0, будем называть i¡елевым фактором для г'-го агента.

Поскольку при монотонных преобразованиях критериев множество равновесий Нзша в чистых стратегиях не меняется, полученные ниже решения игр будут актуальны для более широкого класса функций полезности.

Определив все параметры игры, запишем ее в нормальной форме:

(6) Гс = {N, {Sj }/gW, {fj }jeN, с}

Отметим, что рассматривается некооперативная статическая игра в нормальной форме, то есть игра, в которой агенты однократно, одновременно и независимо выбирают свои действия (стратегии). Игра (6), в которой функции полезности всех агентов записываются в форме (4), называется игрой с нефиксированными целями управления. Игра (6), в которой функции полезности всех агентов записываются в форме (5), называется игрой с фиксированными целями управления.

В разделе 2.3 рассматривается решение игры с нефиксированными целями управления. Выбрав произвольного агента isN, рассматриваем ситуацию с его точки зрения. Преобразуем функцию полезности/¡(х\(Т)^г{Т),...,хт{Т)) подставив в (4) вместо Xj(T) правую часть выражения (3). Получим:

j еМ jcM keM

/

Выполнив перегруппировку слагаемых и обозначив таЛ =

1л- -т%

\jeM

имеем целевую функцию агента (запись, в которой полезность агента явно зависит от его действий и действий других агентов):

(7) = Ег^-Л(0)= £ А (0).

кШ кШ1 кШ\М1

Представление целевой функции gi в виде (7) позволяет аддитивно выделить зависимость ее значения от выбранной /-м агентом стратегии. Согласно известной лемме из теории игр у агента / есть доминантная стратегия. Следовательно, Утверждение 1. Решением игры (6) с нефиксированной целью управления (4) будет совокупность доминантных стратегий агентов ¡1 {равновесие в доминантных стратегию:). Доминантные стратегии агентов определяются по формуле (8).

если Т(Ху < О

(8) р)(0) = - р™, если т-сГу > 0, \ijJeM,.

иначе 0 (для определенности)

В разделе 2.4 рассматривается решение игры с фиксированными целями управления. Выберем произвольного агента 1 е N. и далее будем рассматривать ситуацию с его точки зрения. Преобразуем его функцию полезности

/,ЫЛМТ).....хт{Т)), для этого в (5) вместо х/Т) подставим правую часть

выражения (3).

¡Ш *еМ

Получаем целевую функцию (9).

(9) (с,, + Е г % ■ Л( О))2 =" I Уч ' (с., +т % ■ +т Чг;

¡М кШ ¡аМ

Лемма 1. Функция (9) строго вогнута по переменной-стратегии ¿г. V« е(0,1)

« непрерывна по всем

своим переменным.

Утверждение 2. В игре (6) с фиксированной целью управления (5) всегда существует равновесие Нэша в чистых стратегиях.

Для поиска равновесия Нэша в чистых стратегиях запишем систему

уравнений = 0, V/ е М,-, V/ е N. Запишем эту систему уравнений в явном

' Ч®1 (0)

виде после соответствующего преобразования: С \

(Ю) £ ЪУ.ГтЧц-тЧщ ' А (0) = - £ Уч Т Чи ■ , V/ 6 Л/,-, V/ е ЛГ

Утверждение 3. Если решение системы уравнений (10) существует и принадлежит гиперкубу 5;*... Х5Л, то оно является равновесием Нэша в чистых стратегиях для игры (6) с фиксированной целью управления (5).

Утверждение 4. Если точка равновесия Нэша в чистых стратегиях для игры (б) с фиксированной целью управления (5) принадлежит внутренности гиперкуба 5;Х.„ то она является решением системы уравнений (10).

Из предыдущих двух утверждений и из существования равновесие Нэша в чистых стратегиях для модели с фиксированной целью управления следует справедливость следующего следствия.

Следствие 1. Если ни одно из решений системы уравнений (10) не принадлежит гиперкубу Б^.-.^Б,,, то точка равновесия Нэша в чистых стратегиях для игры (6) с фиксированной целью управления, лежит на границе гиперкуба Б\х...у5„.

В разделе 2.5 обсуждаются подходы к поиску равновесий Нэша в чистых стратегиях в игре агентов с разными типами целей.

В третьей главе «Игра в нормальной форме п агентов с несогласованными представлениями» приводится описание двух моделей: игры с нефиксированными целями управления и игры с фиксированными целями управления для случая, когда когнитивные карты у агентов различны. Приводится постановка и предлагается решение задачи информационного управления в игре с фиксированными целями управления.

В разделе 3.1 приводится описание игры с несогласованными представлениями у агентов. Несогласованные представления агентов отражаются в том, что каждый агент использует собственную когнитивную карту для вычисления прогноза управления. При сохранении общего знания в новой игре возможен поиск равновесия Нэша. Для этого должны выполняться следующие условия:

1) множества факторов в когнитивных картах всех агентов должны совпадать;

2) агенты знают когнитивные карты друг друга;

3) каждый агент верит в адекватность лишь собственной когнитивной карты (т. е. пользуется лишь своей когнитивной картой для прогноза будущих значений факторов);

4) пункты 1-3 являются общим знанием среди агентов.

В этом случае агенты могут по-разному предвидеть результаты одного и того же совместного действия. Это порождает определенную специфику их взаимодействия. В частности, в игре двух агентов с одним общим целевым фактором и с разными желаемыми значениями для него становится возможным такое совместное воздействие агентов, что каждый из агентов в своих

представлениях полностью достигает своей цели. Иначе говоря, несогласованные представления могут в некоторых случаях компенсировать существенное отличие в целевых установках и послужить причиной к полному согласию, там, где его не

Рис. 1. Представления агентов о ситуации, формализованные в виде когнитивных

карт

Каждый из агентов г е N формально может быть представлен тройкой параметров С,>:

1) возможностями по оказанию управляющего воздействия на ситуацию, которые задаются множеством стратегий 5;;

2) целью управления, которая описывается в виде функции полезности для агента

Л

3) знаниями агента об управляемой ситуации, которые задаются в виде линейной когнитивной карты С/.

Линейные когнитивные карты всех агентов С\, С2,..., С„ имеют одинаково упорядоченное множество факторов М= {1,...,м}, но могут отличаться причинно-следственными связями между факторами. Таким образом, когнитивные карты разных агентов имеют в общем случае различные матрицы смежности орграфов 1^X1)^ Однако вполне возможно, что у некоторых (в частном случае - у

всех) агентов матрицы смежности могут совпадать = Дискретное время в моделях когнитивных карт у всех агентов протекает одинаково. Начальный момент времени фиксирован для всех и равен 0. Всем агентам известен вектор начальных значений факторов х(0) е Л™. Как и в предыдущей главе, каждый агент I е N располагает непустым подмножеством факторов М-, с М, доступных ему для

управляющего воздействия. Для любых двух агентов ц е Л': М,С\М1 = 0, и Мк с М, Щ = тл Стратегия ¡-го агента ^ задается вектором, состоящим из упорядоченных компонентов вектора р(0) с номерами из множества {к,,к2,...,кт} = М,: Ь = (Ри1(0),Р12(0),...,рК (0)| Каждый агент воздействует на

ситуацию, задавая значения лишь для «своих» компонентов вектора р(0). Остальные компоненты вектора р(0), на которые не воздействует ни один из агентов, равны нулю: (V/ £ М \Ц^уМк),р/0)=0.

Вводя ограничения на управляющие воздействия по каждому фактору в виде отрезка: (У/б11 кеЫМк) д(0) 6 \рГ,рГ°*1 где д™п,р/ах е Д, мы задаем множество стратегий ¡-го агента $ как декартово произведение

[лТ>Г] * [ЛТ'ЛГ! * -х

Для каждого агента аналогично тому, как это было сделано во второй главе,

определяются функции полезности/, (х\{Т),х2{Т).....х,„(Т)) двух видов (4) и (5).

Заметим, в силу того, что при монотонных преобразованиях критериев множество равновесий Нэша в чистых стратегиях не меняется, полученные ниже решения игр будут актуальны для более широкого класса функций полезности.

Определив все параметры, запишем игру с несогласованными представлениями у агентов: (11) =

¡еЛГ» ш еЫ)

Далее в разделе 3.2 рассматривается игра (И) с нефиксированными целями управления у агентов с функциями полезности вида (4). Проводя действия, аналогичные проведенным в разделе 2.3, получаем

(°))= I

¡¿а у'еа/ ч/=0 ) кем _

Заметим, что при подстановке выражения (2) использовались элементы матрицы достижимости воздействий к моменту времени Т тОЛ для матрицы смежности орграфа т.е. знания ¿-го агента о ситуации. Это обосновано третьим условием, оговоренньм в предыдущем разделе 3.1, о том, что каждый

агент верит в адекватность лишь собственной когнитивной карты. (

у

РЛ 0)

Обозначив га-'к) =

\jzb4

, получим целевую функцию 1-го агента:

(12) a = Sr«i?-A(0)+

*бл/ *ел/, кШ\М,

Представление целевой функции g, в виде (12) позволяет аддитивно выделить зависимость ее значения от выбранной /-м агентом стратегии. Утверждение 5. Решением в игры (11) с нефиксированной целью управления (4) будет совокупность доминантных стратегий агентов S; (равновесие в доминантных стратегиях). Доминантные стратегии агентов вычисляются по формуле (13).

pf\ если Taf < О

(13) р)(0) = . р™\ если Tajp >0, Vj,jeMr

иначе 0 (дцл определенности)

В разделе 3.3 рассматривается игра (11) с фиксированными целями управления у агентов с функциями полезности вида (5). Проводя действия, аналогичные проведенным в разделе 2.4, получаем

!><,■[-W)-*tf)2]=-E Уу■ + Ег^'-аСО)-^)2-

j£m jzm аеа/

Заметим, что при подстановке выражения (2), как и в предыдущем разделе, при записи функции использовались элементы jq^ матрицы достижимости воздействий к моменту времени Т -¡^ для матрицы смежности орграфа Как и при записи функции (12), это обосновано третьим условием, оговоренным в разделе 3.1, о том, что каждый агент верит в адекватность лишь собственной когнитивной карты. Таким образом, из функции полезности (5) получаем целевую функцию (14).

(14) а =-2 г9-(с, + £■ Pkm2=-Svfa +г+г ■

j:M kc'.i je\f

Рассуждения, аналогичные проведенным в разделе 2.4, делают справедливыми аналогичные утверждения и следствие.

Утверждение 6. В игры (11) с фиксированной целью управления (5) всегда существует равновесие Нэша в чистых стратегиях.

Для поиска равновесия Нэша в чистых стратегиях запишем систему

уравнений ^'^¡(^ = 0, V/ е А/., Vi е N. Запишем эту систему уравнений в явном

виде после соответствующего преобразования:

(15) £ IУитчР-тяУ ■p^^-Y.Yrrqf-c^yieM^ieN

кШ IjeM V jeM

Утверждение 7. Если решение системы уравнений (15) существует и принадлежит гиперкубу S\*... *S„, то оно является равновесием Нэша в чистых стратегиях для игры (11 )с функциями полезности (5).

Утверждение 8. Если точка равновесия Нэша в чистых стратегиях для игры (11) с функциями полезности (5) принадлежит внутренности гиперкуба S\X... *S„, то она является решением системы уравнений (15).

Из предыдущих двух утверждений и из существования равновесие Нэша в чистых стратегиях для модели с фиксированной целью управления получаем следующее следствие.

Следствие 2. Если ни одно из решений системы уравнений (15) не принадлежит гиперкубу S\*...*S„, то точка равновесия Нэша в чистых стратегиях для игры (11) с фиксированной целью управления, лежит на границе гиперкуба S¡x... *S„.

В разделе 3.4 показана эквивалентность игры с несогласованными представлениями игре на линейной когнитивной карте, рассмотренной во второй главе. Две игры будем называть эквивалентными, если удается построить такое взаимно-однозначное отображение между множеством агентов и множеством их стратегий, что образ множества равновесий Нэша в чистых стратегиях в одной игре полностью совпадает со множеством равновесий Нэша в чистых стратегиях во второй игре. Построим отображение игры с несогласованными представлениями (11) в игру на линейной когнитивной карте (6) и докажем их эквивалентность.

Перенесем множество агентов N из игры (11) в игру (6) без изменений. Рассмотрим построение линейной когнитивной карты С для игры (6) по линейным когнитивным картам агентов Сь С2,..., Сп в игре (11). Когнитивную карту С будем называть когнитивной картой разделенных влияний (ККРВ) с матрицей смежности W. Исходные когнитивные карты агентов С|, С„ с матрицами смежности

ff¿l\ отражают системы убеждений агентов в игре с

несогласованными представлениями (11). Процесс построения ККРВ задается тремя этапами.

1. Добавим в множество факторов когнитивной карты С те факторы, которые

являются управляемыми в когнитивных картах всех агентов в игре (11):

UkÉNMt. Эти факторы будут управляемыми и в когнитивной карте С.

15

Множество всех управляемых факторов обозначим II (17= и¡се№ик = 1ЛсЛ,Мк, где и^Мк с сохранением нумерации факторов в Мк), и будем называть множеством управляемых факторов. Для любых двух агентов ¿у е Ы: ¡7/0 Ц,- = 0.

2. Выделим из множества факторов И такие факторы, которые являются целевыми факторами хотя бы для одного агента. Каждый из таких факторов продублируем столько раз в когнитивной карте С, какое количество агентов считают его для себя целевым. Сохраним в качестве целевого фактора за каждым из агентов ровно одну копию того фактора, который являлся для него целевым в исходной игре. Пусть X) - целевой фактор в игре (11) для одного или нескольких агентов, тогда для обозначения каждой его копии в когнитивной карте С будем использовать нотацию у}'\ где у - номер продублированного фактора в множестве факторов М, а / — номер агента, для которого полученная копия будет целевым фактором. В случае, если фактор являлся целевым лишь для одного агента, то добавляем его в С в единственном экземпляре. Для обозначения этого фактора для однообразия также будем использовать нотацию у/'\ где у - номер целевого фактора в множестве факторов М, а / — номер агента, для которого этот фактор был целевым фактором в игре (11). Множество всех целевых факторов в когнитивной карте С обозначим С. й, = {у/*}; - множество целевых факторов для /-го агента. Для когнитивной карты С для любых двух агентов /у е Л':

0.

3. Построим дуги из множества факторов и в множество факторов С по следующему правилу. При фиксированных /у е N (быть может, совпадающих) от управляемого фактора е ¿7; к целевому фактору уР е О, идет дуга с весом, равным элементу да^ в матрице ■¡(¿'К

Заметим что граф построенной когнитивной карты С является взвешенным двудольным орграфом. В нем содержатся только управляемые (Ц) и целевые (О) факторы для всех агентов, и все дуги идут из вершин-факторов множества и в вершины-факторы множества б. Веса дуг содержат интегральные влияния факторов множества I/ на факторы множества Б, так как они были взяты из соответствующих матриц Отметим, что в силу того, что орграф ациклический и двудольный, то после воздействий в начальный момент времени р(0) на

управляемые факторы значения всех факторов в когнитивной карте С уже после момента времени 1 не будут меняться.

Для каждого управляемого фактора из множества и сохраним ограничения на управляющие воздействия в виде отрезка допустимых значений, как в игре (11). В этом случае множества стратегий для каждого агента в игре (6) и в игре (И) полностью совпадают. Начальные значения всех факторов в когнитивной карте С для игры (6) совпадают с начальными значениями соответствующих факторов в игре (11), так в частности имеет место равенство у}'\0) = л/0) для всех целевых факторов в игре (6).

Для фиксированного агента ; е .V его функция полезности !у в игре (6) получается на основании его функции полезности соответствующего вида ((4) или (5)) в игре (11). В функции полезности для игры (11) все вхождения значений целевых факторов заменяются на значения соответствующих им целевых

факторов в когнитивной карте С в первый момент дискретного времени у/"(1).

Мы закончили построение игры вида (6) для фиксированной игры вида (11): (16) =

Утверждение 9. Для любого набора когнитивных карт С ь Съ ■■■, С„ несогласованных представлений существует когнитивная карта разделенных влияний С такая, что игра (11) с несогласованными представлениями Си Съ — , С„ эквивалентна игре (16) на когнитивной карте С.

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

агентов. В целях устранения информации, лишней для принятия решения, и упрощения задачи определяется одна вспомогательная когнитивная карта разделенных влияний (ККРВ) на основе когнитивных карт всех агентов, подробно рассмотренная в разделе 3.4.

Рис. 2. Схема информационного управления осуществляемого первым агентом

Ввиду того, что для игры (11) всегда можно построить соответствующую ей игру (16), далее будем рассматривать задачу информационного управления в игре агентов на ККРВ в виде игры (16).

Предположим, что общим знанием среди агентов в игре (16) являются функции полезности агентов и множества их стратегий. Первый агент в игре (16) знает оценки влияния управляемых факторов на целевой фактор тЦи <),---,тЯж') для каждого агента, и может рассчитать равновесие Нэша в чистых стратегиях для игры (истинное равновесие). В случае, если это равновесие его не устраивает по причине низкого выигрыша, то он при определенных условиях имеет возможность осуществлять информационное управление остальными агентами для его увеличения. Параметрами информационного управления первым агентом остальными являются величины тЧи'—'тЧтс ■ На рис.3 целевой для первого агента фактор выделен жирной линией, а параметры, которыми он может манипулировать - пунктирной линией.

Л

Агент 2

Рис. 3. Граф когнитивной карты разделенных влияний

В данном случае, решение задачи информационного управления можно записать в виде:

(17) (г<7,®->г<7£2)бАге тах

Здесь = ВЯ1(/1(г?1с)>""тЙс))> целевая функция первого агента вида (14). Задача поиска информационного управления заключается в нахождении первым агентом таких значений набора параметров тЧ\с >—>тЧт1 собственных оценок влияния управляемых факторов на целевой фактор усУ\ сообщение которых остальным агентам максимизировало бы его полезность. При этом у первого агента существуют истинные оценки влияния управляемых факторов на целевой т91с(1>,---, описывающие его действительное знание о ситуации,

которые он утаивает от остальных агентов. Первый агент, варьируя значения тд\с,—,т9т1> варьирует структуры информированности остальных агентов, а

значит, изменяет рефлексивную игру.

Под возможностью информационного управления первым агентом будем подразумевать тот случай, когда первый агент может сообщением ложной информации о значениях параметров своей когнитивной карты

изменить обстановку я.] в новой равновесной ситуации.

В игре (16) для каждого агента, исходя из его целевой функции вида (14), можно записать уравнение ему соответствующей гиперплоскости.

(18) и ■• I г ' ** + I г $ ' Ч = V -

кШ, кШ\М,

Из (14) можно заключить, что, чем меньше расстояние от точкир(0) = ■?-/) до гиперплоскости, соответствующей г'-му агенту (18), тем ситуация р(0) лучше для /-го агента. Рассмотрим случай, когда для агента г соответствующая ему

гиперплоскость (18) не имеет общих точек с внутренностью гиперкуба^х...*,?,,. В таком случае существует точка на поверхности гиперкуба ^х...*^ с минимальным евклидовым расстоянием до гиперплоскости, соответствующей /-му агенту. Очевидно, что, по крайней мере, одной из таких точек будет одна из вершин гиперкуба ^...х^,. Легко показать, что та часть координат точки гиперкуба с минимальным расстоянием до гиперплоскости (18), которая соответствует стратегиям из Л',, образуют множество доминантных стратегий ¡'-го агента. Пусть е' - вектор составленный из т компонент, каждая из которых равна 1, если номер компоненты принадлежит множеству Ми иначе 0. Утверждение 10. Информационное управление, осуществляемое первым агентом, возможно тогда и только тогда, когда существует агент / ф 1, такой, что для

т

него Ь, П ^ х... *Б„ ф 0 и £ ^ ■ е) Ф 0.

/=I

Вопрос целесообразности применения информационного управления не менее важен, и он не исчерпывается определенной выше возможностью информационного управления. Если решение системы уравнений (15) принадлежит гиперкубу стратегий *... т. е. если выполняется условие

то увеличение выигрыша первого агента невозможно и информационное управление неактуально. Под актуальностью информационного управления первым агентом подразумевается тот случай, когда информационное управление первым агентом возможно, и сообщение первым агентом ложной информации о ■(о л(п

значениях параметров гЧ\с '—>гЯтс позволяет ему увеличить свою полезность в сравнении с полезностью получаемой им, если он сообщит истинные оценки влияния управляемых факторов на целевой 7<71</'',. • •, ЩтР^-

Обозначим через Л^ тех агентов, которые имеют в игре (16) доминантные стратегии. Сами доминантные стратегии этих агентов будем обозначать в? = (р^(0), р£(0), ..., р^ (0)) /6 Ыф Запишем систему уравнений (19) для всех

агентов из подставляя значения, соответствующие доминантным

стратегиям для остальных агентов из Иф Коэффициенты уравнения для первого агента г^с* '■•■>тЯт1 являются искомыми параметрами для задачи (17).

(19) Е^-Р^-^О)

\/ieN\{Nliv{\})J=j{i)

Здесь с - номер целевого фактора для первого агента. Выпишем из (19) выражения для рк в виде параметрической зависимости от тЯ^ Рк = Рк(т€\---,тЯшсЛР1}?="), к£М\{М1), ¿еА^. В записи параметрической зависимости рк от т'1\с'--.тЯж возникает совокупность переменных {р,}™=\" в том случае если т>п. Полученные выражения для рк из системы (19) подставляем в выражение для целевой функции первого агента и решаем задачу оптимизации с ограничениями в виде неравенств:

(20) гшп

-\2

к£М\и{М,}, кеМ,, кеМ1

Атш <рк< рГ\ке М\{Л/,}, ( 6 МЛ {1}.

Здесь Ьрк = ЯЛ1({л > {Р^ыи.^У Приемлемое

допустимое решение этой задачи при относительно небольшом количестве ограничений в виде неравенств может быть найдено, например, с помощью обобщенного метода множителей Лагранжа.

В четвертой главе полученные результаты проиллюстрированы на примере анализа конфликта интересов Норвегии и России при подписании Договора о разделе спорной территории в Баренцевом море пополам. Различные точки зрения по этому вопросу формализованы в виде когнитивных карт. Анализ игры на когнитивной карте противников Договора показал, что, по их мнению, подписание Договора принесет России выгоду в краткосрочном периоде, но не выгодно в долгосрочном периоде. Проанализированы причины, которые привели к такому результату. На примере игр с несогласованными представлениями иллюстрируется вид возможного искажения представлений российской стороны для получения взаимного согласия к подписанию и ратификации Договора.

В заключении приведены результаты и выводы работы, которые заключаются в следующем.

Разработаны теоретико-игровые модели взаимодействия агентов в слабо структурированных конфликтных ситуациях и информационного управления таким взаимодействием. В том числе:

1. Предложен подход к моделированию конфликтных ситуаций, объединяющий теоретико-игровые методы и средства представления знаний о ситуации на основе когнитивных карт.

2. Построены две теоретико-игровые модели взаимодействия агентов в слабоструктурированной ситуации, представленной линейной когнитивной картой). Для каждой из моделей доказано существование и определен метод поиска решения в рамках концепции решения игры в виде равновесия Наша в чистых стратегиях. Показано, что в игре агентов с разными типами целей всегда существует равновесие Нэша в чистых стратегиях и определяется метод его поиска.

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

4. Сформулирована и решена задача информационного управления одним агентом другими в игре с несогласованными представлениями агентов.

5. Разработан программный инструмент для поддержки исследований рассматриваемых методов и моделей.

6. Разработанные в диссертационной работе модели внедрены в ФГУП НТЦ «Система» и ГОУ ВПО «Пермский государственный университет», что подтверждено актами о внедрении.

Список публикаций по теме диссертации.

1. Куливец С.Г. Применение инструментов нечеткой логики и искусственного интеллекта для проектирования и разработки экономических советующих систем. // Тезисы докладов Третьей международной конференции по проблемам управления. - М., 2006. - С. 162.

2. Куливец С.Г Применение нечеткой логики в разработке интеллектуальных систем для оценки финансового состояния предприятия И Материалы Международной научно-методической конференции «Актуальные проблемы математики, механики, информатики». -Пермь, 2006. - С. 132.

3. Куливец С.Г. Проектирование и разработка интеллектуальной системы управления финансами предприятия с применением инструментов нечеткой логики и искусственного интеллекта // Материалы IX Международной конференции «Интеллектуальные системы и компьютерные науки». М., 2006. - С. 168.

4. Куливец С.Г. Игра на линейной когнитивной карте с импульсным начальным управлением // Труды III Всероссийской молодежной конференции по проблемам управления. - М., 2008. - С. 134 - 135.

5. Куливец С.Г. Теоретико-игровые модели на линейных когнитивных картах // Сборник научных трудов У-й Международной научно-технической конференции «Интегрированные модели и мягкие вычисления в искусственном интеллекте». - М., 2009. - С. 379 - 386.

6. Куливец С.Г. Поиск равновесия Нэша в игре на линейной когнитивной карте с квадратичной функцией полезности // Сборник трудов У1-Й Всероссийской школы-семинара молодых ученых «Управление большими системами». -Т1. -Ижевск, 2009. - С. 251 - 255.

7. Куливец С.Г. Равновесие Нэша в игре на линейной когнитивной карте с квадратичной функцией полезности // Материалы X Международной научно-технической конференции «Искусственный интеллект. Интеллектуальные системы» (ИИ-2009). - Таганрог, 2009. - С. 245 - 247.

8. Куливец С.Г. Моделирование конфликтной ситуации между агентами с несогласованными представлениями // Труды международной конференции СА8С'2009. - М., 2009. - С. 105 - 108.

9. Куливец С.Г. Моделирование конфликтных ситуаций с несогласованными представлениями у агентов // Аннотации докладов Научной сессии НИЯУ МИФИ-2010. - Т1. - М., 2010.-С. 65.

10. Куливец С.Г. Модель информационного управления на основе игры на линейной когнитивной карте // Сборник трудов УП-й Всероссийской школы-семинара молодых ученых «Управление большими системами». -Т1.-Пермь, 2010. - С. 305-310.

\\.Куливец С.Г. Моделирование конфликтных ситуаций с несогласованными представлениями у агентов на основе игр на линейных когнитивных картах // Проблемы управления. - 2010 - №4 - С. 42-48.

12.Кузнецов О.П., Житкова Л.Ю., ГубановД.А., Куливец С.Г. Сетевые модели: ресурсы, влияния, конфликты // Материалы I Российской конференции с международным участием «Системный анализ и семиотическое моделирование». SASM'2011. Казань, 2011.

13.Куливец С.Г., Коргин H.A. Модель информационного управления на основе игры на линейной когнитивной карте // Материалы VIH Всероссийской школы-конференции молодых ученых «Управление большими системами» -Магнитогорск, 2011.-С. 181-184.

14. Коргин H.A., Куливец С.Г. Построение когнитивной карты разделенных влияний для игры с несогласованными представлениями // Материалы VIII Всероссийской школы-конференции молодых ученых «Управление большими системами» -Магнитогорск, 2011. - С. 177-180.

1 S.KulivetsS. A game-theoretic model of interactions between agents with different beliefs in the form of linear cognitive maps / Preprints of the 18th World Congress of the International Federation of Automatic Control (IFAC). Milano (Italy), August 28 - September 2,2011. P. 1982-1985. 16. Куливец С.Г., Коргин H.A. Модель информационного управления на основе игры на линейной когнитивной карте // Управление большими системами -2011 (в печати).

В работах с соавторами лично Куливцом С.Г. сделано следующее. В работе [12] предложена теоретико-игровая модель взаимодействия агентов с несогласованными представлениями и метод поиска равновесий Нэша в чистых стратегиях. В работах [13, 14, 16] предложена постановка задачи информационного управления в игре агентов с несогласованными представлениями и поиск её решения.

Подписано в печать:

09.09.2011

Заказ № 5933 Тираж -100 экз. Печать трафаретная. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 www.autoreferat.ru

ВВЕДЕНИЕ.

ГЛАВА 1. ПРОБЛЕМА МОДЕЛИРОВАНИЯ КОНФЛИКТНОГО ВЗАИМОДЕЙСТВИЯ АГЕНТОВ В СЛАБО СТРУКТУРИРОВАННОЙ ПРОБЛЕМНОЙ СИТУАЦИИ.

1.1. Описание проблемной ситуации.

1.2. Элементы теоретико-игрового моделирования.

1.3. Когнитивная карта как математическая модель системы убеждений ЛПР

1.4. Модели рефлексивного взаимодействия и информационного управления

1.5. Выводы.

ГЛАВА 2. ИГРА В НОРМАЛЬНОЙ ФОРМЕ /V АГЕНТОВ НА ЛИНЕЙНОЙ КОГНИТИВНОЙ КАРТЕ.

2.1 Управление ситуацией в модели линейной когнитивной карты.

2.2 Описание теоретико-игровой модели конфликта.

2.3 поиск решения для модели с нефиксированной целью управления.

2.4 поиск решения для модели с фиксированной целью управления.

2.5 Игра агентов на линейной когнитивной карте с двумя типами целей.

2.6'выводы.

ГЛАВА 3. ИГРА В НОРМАЛЬНОЙ ФОРМЕ N АГЕНТОВ С НЕСОГЛАСОВАННЫМИ ПРЕДСТАВЛЕНИЯМИ.

3.1 Описание теоретико-игровой модели конфликта.

3.2 Поиск решения для модели с нефиксированной целью управления.

1 3.3 Поиск решения для модели с фиксированной целью управления.

3.4 Эквивалентность игры с несогласованными представлениями агентов игре на линейной когнитивной карте.

3.5 Задача информационного управления одним агентом другими в игре с несогласованными представлениями с фиксированными целями управления

3.6 Выводы.

ГЛАВА 4. КОГНИТИВНЫЙ АНАЛИЗ КОНФЛИКТА ИНТЕРЕСОВ НОРВЕГИИ И РОССИИ В БАРЕНЦЕВОМ МОРЕ.

4.1 Краткое описание ситуации конфликта интересов между Россией и Норвегией в Баренцевом море.

4.2 Игра двух агентов (Россия и Норвегия) на одной когнитивной карте.

4.3 Игра с несогласованными представлениями.

4.4 Информационная рефлексия в игре агентов с несогласованными представлениями.!.

4.5 Выводы.1.

Актуальность темы диссертации

Задачи математического моделирования конфликтных ситуаций, т.е. взаимодействия рациональных агентов с несовпадающими интересами, исследуются на протяжении нескольких десятилетий и находят приложения в различных задачах управления в социальной, экономической и геополитической сферах. Модели конфликтных ситуаций широко используются при анализе, моделировании и оптимизации механизмов > принятия управленческих решений в организационных системах для повышения эффективности их функционирования. Традиционным подходом к решению этих задач является теоретико-игровой* подход, при котором взаимодействие агентов рассматривается как игра, интересы агентов (игроков) формулируются как функции выигрыша, правила выбора возможных действий - как стратегии поведения, причем предполагается, что каждый агент располагает сведениями о»стратегиях и функциях выигрыша других агентов. Одним из актуальных аспектов теоретико-игрового подхода являются задачи управления игрой путем воздействия; на параметры игры с целью получения ее исхода, благоприятного для одного из игроков или внешнего по отношению к игре управляющего органа. Теоретико-игровые модели управления исследовались в работах многих отечественных и зарубежных авторов: Ю.Б. Гермейера, H.H. Моисеева, В.А. Лефевра, В.Н. Буркова, Д.А. Новикова, Т.А. Таран, А.Г. Чхартишвили, В.А. Горелика, А.Ф. Кононенко, J. Harsanyi, R. Myerson и др.

В последнее время особенно активно развивается направление, связанное с информационным управлением и рефлексивными играми. При информационном управлении параметром игры, который подвергается управляющему воздействию, является информированность агентов. Понятно, что при такой постановке задачи требуется более детальная формализация понятия информированности. Рефлексивный подход детализирует это понятие с точки зрения информации о противнике: агент А учитывает не только свое знание об агенте В, но и знание агента В об А и т.д. Однако при моделировании реальных конфликтных взаимодействий требуется учитывать знания не только о сопернике, но и обо всей игровой обстановке, в которой происходит взаимодействие, т. е. о ситуации, в которой присутствует не только соперник, но и внешние факторы, которые могут различным образом влиять на исход игры. Такого рода знания в рамках теоретико-игрового подхода к моделированию конфликтов учитываются недостаточно.

В то же время математические средства описания знаний о ситуации уже более 40 лет разрабатываются в рамках исследований по когнитивному анализу слабо структурированных ситуаций. Такими средствами5 являются когнитивные карты. Когнитивная карта - это набор- причинно-следственных утверждений- о-взаимодействии факторов в фиксированной предметной области, представленный в виде взвешенного ориентированного графа. Существенное достоинство графового-представления когнитивной карты.заключается в том, что оно* позволяет увидеть общую структуру целого множества утверждений о связях между факторами ситуации и исследовать ее методами теории^ графов. Основополагающими работами в когнитивном анализе ситуаций являются работы R. Axelrod, В*. Kosko, F. Roberts. Среди отечественных авторов, внесших заметный вклад в это направление, следует отметить работы В.Б. Силова, В.В. Кульбы, В.И'. Максимова, Е.К. Корноушенко, A.A. Кулинича, О.П. Кузнецова, H.A. Абрамовой, F.B. Гореловой и др. В~рамках данного подхода имеются работы, исследующие задачу управления развитием слабо структурированной ситуации, представленной когнитивной картой. В частности, появляются, работы, где управление осуществляют несколько ЛПР; стремящиеся достичь различных целей. Однако в этих работах не уделяется должного внимания основным принципам теоретико-игрового подхода: рациональности каждого из ЛПР, учета возможных стратегий других участников игры и т.д. Таким образом, становится актуальной задача объединения двух направлений, которая формулируется' как задача применения методов традиционного теоретико-игрового моделирования конфликтов к сложным, как правило, слабоструктурированным ситуациям, описываемым с помощью когнитивных карт.

Это позволит более детально учитывать среду, в которой разворачиваются конфликты, и тем самым более адекватно моделировать реальные конфликты. Именно этой задаче посвящена настоящая работа, что и определяет ее актуальность.

Цель и задачи работы

Цель работы состоит в разработке моделей конфликтного взаимодействия агентов с несогласованными представлениями в слабо структурированных ситуациях и информационного управления таким взаимодействием. При этом предполагается, что знания агентов о ситуации, в которой происходит взаимодействие, представлены в виде линейных когнитивных карт.

Достижение поставленной цели требует решения следующих основных задач:

1. Разработка подхода к моделированию конфликтных ситуаций, объединяющего теоретико-игровые методы и средства представления знаний о ситуации на основе когнитивных карт.

2. Разработка и исследование моделей и методов взаимодействия агентов в слабоструктурированных ситуациях, представленных когнитивными картами, включая: a. модели взаимодействия агентов с фиксированными1 и нефиксированными целями; b. модели взаимодействия агентов с несогласованными представлениями о ситуации; c. постановка и решение задачи информационного управления в игре одним из агентов.

3. Создание программного комплекса, реализующего полученные модели и методы, и проведение на нем вычислительных экспериментов.

Методы исследований.

Основным методом исследования является математическое моделирование с использованием подходов и результатов теории игр, методов когнитивного анализа ситуаций, теории активных систем и исследования операций.

Научная новизна.

В работе были построены и исследованы математические модели взаимодействия агентов с несовпадающими интересами для случая, когда их знания о ситуации формально представлены в виде линейной когнитивной карты. В результате проведенных исследований:

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

2. Построены две теоретико-игровые модели взаимодействия агентов (в виде игры в нормальной форме), представления которых о проблемной- ситуации не совпадают и заданы различными линейными когнитивными картами. Для'каждой из моделей показано существование решения и определен метод его поиска в рамках концепции решения игры в виде равновесия Нэша в чистых стратегиях. Модели друг от друга отличаются записью функций.полезности агентов: a. в модели с нефиксированными целями управления цель каждого агента задается направлением изменений значения фиксированных факторов; b. в модели с фиксированными целями управления цель каждого агента задается желаемыми значениями для фиксированных факторов.

3. Разработана модель информационного управления сложными социально-экономическими и политическими- системами, в которых один агент воздействует на других в игре с несогласованными представлениями агентов с фиксированными целями управления. Сформулированы необходимые и достаточные условия возможности такого управления. Задача поиска информационного управления представлена как задача поиска опти6 мума функции с ограничениями в виде неравенств. Поиск решения осуществляется численными методами.

Практическая значимость.

Результаты диссертационной работы позволяют принимать более обоснованные решения в слабо структурированных конфликтных ситуациях, а также разрабатывать и обосновывать механизмы эффективного информационного управления при взаимодействии агентов в таких ситуациях.

Апробация работы.

Результаты диссертационной работы докладывались на: семинарах Института' проблем управления им. В.А. Трапезникова РАН, на III Всероссийской' моло-дежной.конференции по-проблемам управления (Москва, 2008), на V-й международной научно-технической конференции «Интегрированные модели и мягкие вычисления в искусственном интеллекте» (Коломна, 2009); на VI Всероссийской школе-семинаре молодых ученых «Управление большими, системами» (Ижевск, 2009), на X Международной- научно-технической' конференции* «Искусственный интеллект. Интеллектуальные системы» (Таганрог, 2009), на международной конференции CASC'2009 '(Москва,. 2009), на научной сессии'Московского инженерно-физического института (Москва, 2010), на VII Всероссийской школе-семинаре молодых ученых «Управление большими системами» (Пермь, 2010), I Российской конференции с международным участием «Системный анализ и семиотическое моделирование». SASM'2011 (Казань, 2011), на ХЪ Международной научной конференции,им. Т.А. Таран ИАИ-2011 (Киев, 2011), на VIII Всероссийской школе-семинаре молодых ученых «Управление большими системами» (Магнитогорск, 2011), на Международной летней школе-семинаре по искусственному интеллекту для студентов, аспирантов и молодых ученых «Интеллектуальные системы и технологии: современное состояние и перспективы» (ISyT'2011) (Тверь, 2011), на 18-м Всемирном Конгрессе IFAC (Милан, 2011).

Публикации.

Основные результаты научных исследований по теме диссертации содержатся в 16 публикациях, в их числе 2 публикации в ведущих научных журналах 7 перечня Высшей аттестационной комиссии (в списке публикаций №№ 35 и 37) и 1 публикация на Всемирном конгрессе 1БАС-2011 (в списке публикаций № 5).

Структура и объем.

Диссертационная работа состоит из введения, четырех глав, заключения и списка литературы. Работа содержит 101 страницу текста, список литературы включает 52 наименования.

4.5 Выводы

В четвертой главе: проиллюстрировано использование аппарата игры, на когнитивных картах для анализа конфликта интересов Норвегии и России при подписании Договора о разделе спорной территории в Баренцевом море пополам. Различные точки зрения по этому вопросу формализованы; в виде когнитивных карт. Анализ игры на одной когнитивной карте (противников Договора) - путем последовательного расчета РДС показал- что подписание Договора принесет России выгоду в краткосрочном периоде; но/не выгодно в долгосрочном периоде. Проанализированы причины; которые привели к такому результату. На примере игр с несогласованными представлениями иллюстрируется вид возможного искажения представлений российской стороны; для; получения взаимного согласия к • подписанию и ратификации Договорам В заключение приводятся возможные структуры информированности агентов, среди которых выделены те, при которых подписание Договора возможно без долгих предварительных переговоров.

ЗАКЛЮЧЕНИЕ

В настоящей работе разработаны теоретико-игровые модели взаимодействия агентов в слабо структурированных конфликтных ситуациях и информационного управления таким взаимодействием. В том числе:

1. Предложен подход к моделированию конфликтных ситуаций, объединяющий теоретико-игровые методы и средства представления знаний о ситуации на основе когнитивных карт.

2. Построены две теоретико-игровые модели взаимодействия агентов в слабоструктурированной ситуации; представленной линейной.когнитивной картой). Для' каждой из моделей доказано, существование и определен метод поиска решения в рамках концепции решения игры в виде равновесия-Нэша. Показано; что в игре агентов с разными типами целей всегда существует равновесие Нэша в чистых стратегиях и определяется метод его поиска.

3. Построены две теоретико-игровые мод ели .взаимодействия'агентов, представления которых о-проблемной ситуации не совпадают и; заданы различными линейными когнитивными, картами (игра с несогласованными представлениями). Для каждой из моделей показано существование решения и определен метод его поиска в рамках концепции решения игры в виде равновесия Нэша. Показана эквивалентность игры с несогласованными представлениями на нескольких картах игре на одной линейной когнитивной карте.

4. Сформулирована и решена задача информационного управления одним агентом другими в игре с несогласованными представлениями агентов.

5. Разработан программный инструмент для поддержки исследований рассматриваемых методов и моделей.

6. Разработанные в диссертационной'работе модели внедрены В; ФГУП НТЦ «Система» и ГОУ ВПО «Пермский государственный университет», что подтверждено актами о внедрении.

1. Axelrod R. Structure of Decision: The Cognitive Maps of Political Elites. -Princeton, 1976.-395 p.

2. Bryant J. Modelling Alternative Realities in Conflict and Negotiation II Operational Research Society. 1984. Vol. 35, No. 11. 985-993 p.

3. Klein J.H. and Cooper D.F. Cognitive maps of decision makers in a complex game II Operational Research Society. 1982. Vol. 33. 63-71 p.

4. Kosko B. Fuzzy Cognitive Maps // International Journal of Man-Machine Studies. 1986.-Vol. 1.-P. 65-75.

5. Langfield-Smith K. and Wirth A. Measuring Differences Between Cognitive Maps II Operational Research Society. 1992. Vol. 43, No. 12. 1135-1150 p.

6. Mas-Collel A., Whinston M.D., Green J.R. Microeconomic Theory. -N.-Y.: Oxford Univ. Press, 1995. 981p.

7. Myerson R.B. Game Theory: Analysis of Conflict. London: Harvard Univ. Press, 1991.-568 p.

8. Moulin H. (1981) Theorie des jeux pour I'economie et la politique.

9. Novikov, D., Chkhartishvili, A. (2005). Models of reflexive decision-making. In: Systems Sciense. Vol. 30. No. 2. P. 45-59.

10. Owen G. (1968) Game theory. W.B. Saunders company.

11. Roberts, F. (1976) Discrete mathematical models with application to social, biological and environmental problems. Rutgers University. Prentice-Hall, Inc. Englewood Cliffs, New Jersey.

12. Tolman E. Cognitive Maps in Rats and Men // Psychological Review. 1948. -N55.-P. 189-208.

13. Балмасов С., Трухачев В. Россия и Норвегия разделили воды Арктики. http://ns 1 .warandpeace.ru/ru/news/view/56637/ (25.03.2011)

14. Гермейер Ю.Б. Игры с непротивоположными интересами. М.: Наука, 1976.-327 с.

15. Горелик В.А., Горелов М.А., Кононенко А.Ф. Анализ конфликтных ситуаций в системах управления. М.: Радио и связь, 1991. - 288 с.

16. Горелова W.C. Позиционные игры на взаимодействующих когнитивных моделях. Материалы конференции- CASC-2006. М.: ИЛУ РАН, 2006. с. 185-191.

17. Губко М.В., Новиков Д.А. Теория игр в управлении организационными системами. М.: СИНТЕГ, 2002. - 148 с.

18. Губко М.В. Механизмы управления организационными системами с коалиционным взаимодействием участников. М.: ИЛУ РАН, 2003. - 118 с.

19. Калашников Л.И. Газпром мечты Норвегии сбываются. http://www.tovota-club.net/files/lib/z st/11-03-20 lib nord.htm (24.03.2011), http://www.arcticway.ru/index.php?id=172 (25.03.2011).

20. Кононенко А.Ф., Халезов А.Д., Чумаков B.B. Принятие решений в условиях неопределенности. М.: ВЦ АН СССР, 1991. - 211 с.

21. Коргин H.A., Куливец С.Г. Построение когнитивной карты разделенных влияний для игры с несогласованными представлениями II Материалы VIII Всероссийской школы-конференции молодых ученых «Управление большими системами» Магнитогорск, 2011. - С. 177-180.

22. Кузнецов О.П., Кулинич A.A., Марковский A.B. Анализ влияний при управлении слабоструктурированными ситуациями на основе когнитивных карт. II Человеческий фактор < в управлении. — М.: КомКнига, 2005. -С. 313-344.

23. Кузнецов О.П., Жилякова Л.Ю., Губанов Д.А., Куливец С.Г. Сетевые модели: ресурсы, влияния, конфликты II Материалы I Российской конференции с международным участием «Системный анализ и семиотическое моделирование». SASM'2011. Казань, 2011.

24. Куливец С.Г. Применение инструментов нечеткой логики и искусственного интеллекта для проектирования и разработки экономических советующих систем. II Тезисы докладов Третьей международной конференции по проблемам управления. М., 2006. - С. 162.

25. Куливец С.Г. Играла линейной когнитивной карте с импульсным начальным управлением II Труды III Всероссийской молодежной конференции по проблемам управления. М., 2008. - С. 134 - 135.

26. Куливец С.Г. Теоретико-игровые модели на линейных когнитивных картах II Сборник научных трудов; У-й Международной научно-технической конференции «Интегрированные модели и мягкие вычисления в искусственном интеллекте». М., 2009. - С. 379 - 386.

27. Куливец С.Г. Поиск равновесия Нэша в игре на линейной когнитивной карте с квадратичной функцией полезности II Сборник трудов У1-й Всероссийской школы-семинара молодых ученых «Управление большими системами». -Т1. Ижевск, 2009. - С. 251 - 255.

28. Куливец С.Г. Моделирование конфликтной ситуации между агентами с несогласованными представлениями II Труды международной конференции СА8С2009. -М., 2009. -С. 105- 108.

29. Куливец С.Г. Моделирование конфликтных ситуаций с несогласованными представлениями у агентов II Аннотации докладов Научной сессии НИЯУ МИФИ-2010. Tl. - М., 2010. - С. 65.

30. Куливец С.Г. Модель информационного управления на основе игры на линейной когнитивной карте II Сборник трудов VII-й Всероссийской школы-семинара молодых ученых «Управление большими системами». Т1. — Пермь, 2010.-С. 305-310.

31. Куливец С.Г. Моделирование конфликтных ситуаций с несогласованными представлениями у агентов на основе игр на линейных когнитивных картах II Проблемы управления. 2010 - №4 - С. 42-48.

32. Куливец С.Г., Коргин H.A. Модель информационного управления на основе игры на линейной когнитивной карте II Материалы VIII Всероссийской школы-конференции молодых ученых «Управление большими системами» -Магнитогорск, 2011.-С. 181-184.

33. Куливец С.Г., Коргин H.A. Модель информационного управления на основе игры на линейной когнитивной карте II Управление большими системами -2011 (в печати).38: Лефевр В.А. Конфликтующие структуры. М.: Советское радио, 1973. -158 с.

34. Лефевр В.А. Лекции по теории рефлексивных игр. М.: «Когито-Центр», 2009.-218 с.

35. Максимов В.И., Корноушенко Е.К. Аналитические основы применения когнитивного подхода при> решении слабоструктурированных задач II Труды Института проблем управления им. В.А. Трапезникова РАН. Том И. -М., 1999.-С. 95- 109.

36. Максимов В.И. Структурно-целевой анализ развития социально-экономических ситуаций // Проблемы управления. — 2005. № 3. — С. 30 — 38.

37. Новиков Д.А. "Когнитивные игры": линейная импульсная модель // Проблемы управления. 2008. - №3 - С. 14-22.

38. Новиков Д.А., Чхартишвили А.Г. Рефлексивные игры. М.: СИНТЕГ, 2003.- 160 с.

39. Новиков Д.А., Чхартишвили А.Г. Прикладные модели информационного управления. М.: ИЛУ РАН, 2004. - с. 130.

40. Новиков Д.А., Чхартишвили А.Г. Активный прогноз. М.: ИЛУ РАН, 2002. 101 с.

41. Новиков Д.А., Чхартишвили А.Г. Рефлексивные игры. М.: СИНТЕГ, 2003, 160 с.

42. Орешенков A.M. Арктический квадрат возможностей. Северный полюс и шельф Шпицбергена не могут быть норвежскими // Россия в глобальной политике. http://www.globalafFairs.ru/number/Arkticheskii-kvadrat-vozmozhnostei-15069 (17.12.2010).

43. Орешенков A.M. Норвегия выигрывает борьбу за Шпицберген за счет юридических манипуляций? // Право.ru. http://pravo.ru/process/view/32454/ (21.06.2010).

44. Таран Т.А., Шемаев В.Н. Метод моделирования рефлексивного управлеtния на основе когнитивных карт» // Тр. IV междунар. конф. «Когнитивный анализ и управление развитием ситуаций. М.: ИПУ РАН, 2004. С. 132— 139.

45. Taxa Хемди А. Введение в исследование операций. М.: Издательский дом «Вильяме», 2005. 912 с.

46. Чхартишвили А.Г. Теоретико-игровые модели информационного управления. М.: ЗАО «ПМСОФТ», 2004. - 227 с.

47. ШульцВ.Л., Кульба В.В., Шелков А.Б., Кононов Д.А., Чернов И.В. Информационное управление в условиях активного противоборства: модели и методы. ИПУ РАН. М.: Наука, 2011. - 187 с.