Приложения квадратичных стохастических операторов к нелинейным проблемам консенсуса

Полный текст

ОГЛАВЛЕНИЕ 1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 2. Средние процессы Краузе . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 3. Квадратичные стохастические процессы . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 4. Нелинейные задачи Перрона-Фробениуса . . . . . . . . . . . . . . . . . . . . . . . . . . 115 5. Средние процессы Краузе через квадратичные стохастические операторы . . . . . . . . 116 6. Обзор предыдущих результатов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 7. Основной результат . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 8. Пример . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 1. ВВЕДЕНИЕ Многоагентная система- это система, составленная из многих взаимодействующих так называемых интеллектуальных агентов, которые могут иметь различную информацию и/или расходящиеся интересы. Агенты могут быть роботами, людьми или командами людей. Люди - это сложные личности, чье поведение регулируется многими аспектами, относящимися к социальному контексту, культуре, закону и другим факторам. Несмотря на эти многочисленные факторы, человеческое общество характеризуется поразительной глобальной закономерностью, в которой мы можем видеть переходы от беспорядка к порядку. Эти макроскопические явления, естественно, требуют математической модели для понимания социального поведения, т. е. модели для понимания закономерностей в большом масштабе как коллективных эффектов взаимодействия между отдельными людьми. В основе человеческого поведения лежат мнения, которые могут рассматриваться как внутреннее состояние личностей, побуждающее к определенным действиям. Динамика мнений- это процесс слияния индивидуальных мнений, в котором группа взаимодействующих агентов непрерывно объединяет свои мнения по одному и тому же вопросу на основе установленных правил слияния для достижения консенсуса, поляризации или фрагментации на конечной стадии. © РОССИЙСКИЙ УНИВЕРСИТЕТ ДРУЖБЫ НАРОДОВ, 2022 Эта работа доступна по лицензии Creative Commons 4.0 International https://creativecommons.org/licenses/by-nc-nd/4.0/deed.ru 110 Для изучения эволюции мнений группы взаимодействующих индивидуумов были построены различные математические модели. Большинство подобных моделей является линейными. Обычно исследователи сосредоточены на задаче консенсуса и ищут пути его достижения. Исторически идея достижения консенсуса для структурированной синхронной среды, инвариантной по времени, была предложена Де Грутом (см. [6]). Позднее в работе Чаттерджи и Сенеты (см. [5]) было произведено обобщение модели Де Грута для структурированной синхронной среды с переменным временем. В этих моделях динамика обмена мнениями в структурированной синхронной многоагентной системе с переменным временем представлена обратным произведением квадратных стохастических матриц. В то же время, неоднородная цепь Маркова представляется в виде прямого произведения квадратных стохастических матриц. Следовательно, консенсус многоагентных систем и эргодичность цепи Маркова являются двойственными задачами друг к другу. С этого момента консенсус, будучи наиболее общим феноменом многоагентных систем, становится популярным в различных научных сообществах, таких как биология, физика, инженерия управления и социальные науки (см. [12, 23, 45, 46]). В недавнее время были построены некоторые нелинейные модели для характеризации динамики мнений в обществе (см. [10, 11, 17-20]). Более общая модель динамики обмена мнениями описывается средним процессом Краузе, в котором мнения представлены в виде векторов. Читатель может обратиться к монографии [21] за подробным рассмотрением средних процессов Краузе. В серии работ [34-39] была установлена корреляция между средними процессами Краузе и квадратичными стохастическими процессами. Квадратичный стохастический процесс (см. [7, 43]) является простейшей нелинейной цепью Маркова. Аналитическая теория квадратичных стохастических процессов, порожденных кубическими стохастическими матрицами, была построена в работах [7, 43]. Исторически квадратичный стохастический оператор (сокращенно КСО) был впервые введен Бернштейном (см. [4]). Квадратичный стохастический оператор рассматривался как важный инструмент анализа для изучения динамических свойств и моделирования в различных областях, таких как биология (см. [15, 22, 26]), физика (см. [47]), системы управления (см. [34-39]). Множества фиксированных точек и омегапредельные множества квадратичных стохастических операторов, определенных на конечномерном симплексе, были изучены в [1, 2, 27, 40-42]. Эргодичность и хаотическая динамика квадратичных стохастических операторов на конечномерном симплексе была изучена в работах [13, 14, 28, 32, 33]. Подробное самостоятельное изложение последних достижений и открытых проблем теории квадратичных стохастических операторов и процессов было представлено в [9, 24]. Данная работа содержит обзор недавнего развития приложений квадратичных стохастических операторов к нелинейным задачам консенсуса. Мы также даем некоторые уточнения и улучшения предыдущих результатов. 2. СРЕДНИЕ ПРОЦЕССЫ КРАУЗЕ Сначала дадим обзор общей модели динамики обмена мнениями в многоагентной системе, представленной в работе [10], которая охватывает все классические модели динамики обмена мнениями (см. [3, 5, 6]). Рассмотрим группу из m индивидуумов Im := {1,... ,m}, действующих вместе как команда или комитет, каждый из которых может выразить его/ее собственное субъективное распределение для некоторой данной задачи. Предполагается, что если индивидуум i информирован о распределениях каждого из остальных членов группы, то он/она может захотеть пересмотреть свое субъективное распределение в соответствии с этой информацией. Пусть x(t) = (x1(t),...,xm(t))T - субъективные распределения многоагентной системы в момент времени t, где для всех i ∈ Im. Пусть pij(t,x(t)) обозначают вес, который индивидуум i сопоставляет значению xj(t), когда он/она делает пересмотр в момент времени t + 1. Предполагается, что и . После информирования о субъективных распределениях других членов группы, индивидуум i пересматривает свое субъективное распределение от xi(t) к xi(t + 1) следующим образом: . Пусть P(t,x(t)) обозначает стохастическую матрицу из m × m строк, чей (ij)-й элемент равен pij(t,x(t)). Общая модель структурированной синхронной системы с переменным временем определяется следующим образом: x(t + 1) = P(t,x(t))x(t), ∀ t ∈ N. (2.1) Тогда мы можем получить все классические модели (см. [3, 5, 6, 10, 11]), выбирая подходящие матрицы P(t,x(t)). Говорят, что консенсус в структурированной синхронной многоагентной системе с переменным временем (2.1) достигнут, если распределения x(t) сходятся к c = (c,...,c)T при t → ∞. Стоит отметить, что консенсус c = c(x(0)) может зависеть от начального мнения x(0). Более общая модель динамики обмена мнениями- это средний процесс Краузе, в котором мнения представлены в виде векторов. Читатель может обратиться к выдающейся монографии У. Краузе [21] за детальным описанием средних процессов. Пусть S - непустое выпуклое подмножество в Rd и Sm - m-кратное декартово произведение S. Определение 2.1 (см. [21]). Последовательность , где x(t) = (x1(t),...,xm(t))T , называется средним процессом Краузе на Sm, если выполнено xi(t + 1) ∈ conv{x1(t),...,xm(t)}, ∀ i ∈ Im, t ∈ N, где conv{·} - выпуклая оболочка множества. Другими словами, последовательность является средним процессом Краузе, если conv{x1(t + 1),... ,xm(t + 1)} ⊂ conv{x1(t),...,xm(t)}, ∀ t ∈ N. Определение 2.2 (см. [21]). Отображение T : Sm → Sm называется средним оператором Краузе, если его траектория с произвольной начальной точкой x(0) ∈ Sm порождает средний процесс Краузе на Sm. Следует отметить, что нелинейная модель динамики обмена мнениями (2.1) является средним процессом Краузе, потому что действие стохастической матрицы P = (pij)mi,j=1 на вектор x = (x1,...,xm)T может быть рассмотрено как набор арифметических средних с весами pij. Различные виды нелинейных моделей средних процессов были изучены в серии работ [10, 11, 17-20]. 3. КВАДРАТИЧНЫЕ СТОХАСТИЧЕСКИЕ ПРОЦЕССЫ Пусть - стандартный базис в пространстве Rm. Положим, что пространство Rm наделено l1-нормой , где x = (x1,...,xm)T ∈ Rm. Будем говорить, что x 0 (и, соответственно, x > 0), если xk 0 (соответственно, xk > 0) для всех k ∈ Im. Пусть Sm-1 = {x ∈ Rm : x - (m - 1)-мерный стандартный симплекс. Элемент симплекса Sm-1 называется стохастическим вектором. Пусть c- центр симплекса Sm-1, а intSm-1 = {x ∈ Sm-1 : x > 0} и ∂Sm-1 = Sm-1 \ intSm-1, - соответственно, внутренность и граница симплекса Sm-1. Теперь дадим необходимые определения неоднородных цепей Маркова и квадратичных стохастических процессов согласно работам [7, 8, 25, 43, 44]. Пусть P = (pij)mi,j=1 - матрица. Определим векторы (pi•)T := (pi1,...,pim) и p. Квадратная матрица называется строчно-стохастической (столбцово-стохастором для всехтической, соответственно), если векторi ∈ Im (для всех j ∈ Impi,• соответственно). Квадратная матрица(p•j, соответственно) является стохастическим век-P = (pij)mi,j=1 называется дважды стохастической, если она одновременно является строчно-стохастической и столбцово-стохастической. Мы говорим, что, соответственно), если p, соответственно) для всех i ∈ Im. В течение нескольких последних десятилетий большие усилия были приложены к построению различных необходимых и/или достаточных условий эргодичности неоднородных цепей Маркова (см. [25, 44] и цитируемые в них источники). Одной из главных областей в изучении неоднородных цепей Маркова является нахождение условий, при которых цепь является слабо/сильно эргодической. Основная техника, используемая для этого, состоит в том, чтобы установить, что все конечные произведения регулярны, и затем потребовать выполнения некоторых условий на размер положительных элементов в матрицах перехода (см. [44]). При нахождении множеств квадратных стохастических матриц, используемых при построении слабо/строго эргодических неоднородных цепей Маркова, необходимо найти подмножества регулярных квадратных стохастических матриц, которые образуют полугруппы. Множество квадратных стохастических матриц скремблирования является одним из таких множеств (см. [44]). Стохастическая матрица P = (pij)mi,j=1 называется матрицей скремблирования, если для любого i,j ∈ Im существует число k ∈ Im такое, что pikpjk > 0, т. е. любые две строки такой квадратной стохастической матрицы не ортогональны. Квадратная стохастическая матрица с идентичными строками называется устойчивой (постоянной) матрицей. Очевидно, что любая положительная квадратная стохастическая матрица является скремблирующей. Более того, любая устойчивая (постоянная) квадратная стохастическая матрица также является скремблирующей матрицей. Одним из классических результатов в теории линейных марковских цепей является тот факт, что стохастическая матрица является сильно эргодической, т. е. ее степени сходятся к некоторой устойчивой/постоянной стохастической матрице тогда и только тогда, когда некоторая ее степень является скремблирующей матрицей. Семейство квадратных строчно-стохастических матриц называется неоднородной цепью Маркова с дискретным временем, если для любых натуральных чисел r,s,t таких, что r < s < t, выполняется следующее условие, известное как уравнение Колмогорова-Чепмена: . Линейный оператор L[r,t] : Sm-1 → Sm-1, ассоциированный с квадратной строчно-стохастичесm кой матрицей, где , называется линейным стохастическим оператором (Маркова) (см. [25, 44]). Отметим, что уравнение Колмогорова-Чепмена может быть записано в следующем виде: L[r,t] = L[s,t] ◦ L[r,s], r < s < t. Пусть P = (pijk)mi,j,k=1 - кубическая матрица (см. [7, 8, 43]). Определим следующие векторы: pij• := (pij1,...,pijm)T ∀ i,j ∈ Im. Кубическая матрица P = (pijk)mi,j,k=1 называется стохастической, если pij• - стохастический вектор для любых i,j ∈ Im. Семейство кубических стохастических матриц с начальным распределением x(0) ∈ Sm-1 называется квадратичным стохастическим процессом с дискретным временем, если для любых натуральных чисел r,s,t при r < s < t выполнено одно из следующих условий, так называемых нелинейных уравнений Колмогорова-Чепмена: , где . Отметим, что условия (A) и (B) не эквивалентны. Читатель может обратиться к работам [7, 43] для изучения квадратичных стохастических процессов. Непрерывное отображение Q[r,t] : Sm-1 → Sm-1, ассоциированное с кубической стохастической m матрицей, где , называется квадратичным стохастическим оператором (нелинейным марковским оператором). Очевидно, имеем x(ν) = Q[0,ν](x(0)). Отметим, что нелинейное уравнение Колмогорова-Чепмена может быть записано в виде Q[r,t] = Q[s,t] ◦ Q[r,s], r < s < t. Определим следующие стохастические векторы и квадратные строчно-стохастические матрицы, ассоциированные с кубической стохастической матрицей P = (pijk)mi,j,k=1: pij• := (pij1,pij2,...,pijm)T , i,j ∈ Im, Pi•• := (pijk)mj,k=1, i ∈ Im, Px := . Легко проверить, что квадратичный стохастический оператор имеет следующие векторную и матричную формы: (векторная форма), (3.1) (матричная форма). (3.2) Определение 3.1 (см. [16]). Непрерывное отображение M : Sm-1 → Sm-1 называется нелинейным марковским оператором, если M(x) = Mxx ∀ x ∈ Sm-1, где - стобцово-стохастическая матрица, зависящая от x ∈ Sm-1 (что вводит нелинейность). Квадратичный стохастический оператор Q : Sm-1 → Sm-1, введенный формулой (3.1), на самом деле является нелинейным марковским оператором, поскольку он может быть записан в матричной форме, определенной формулой (3.2). Следует отметить, что существуют некоторые нелинейные марковские операторы, не являющиеся квадратичными стохастическими операторами (см. [16]). Следовательно, множество всех квадратичных стохастических операторов не может покрыть множество всех нелинейных марковских операторов. 4. НЕЛИНЕЙНЫЕ ЗАДАЧИ ПЕРРОНА-ФРОБЕНИУСА Теорема Перрона-Фробениуса играет решающую роль в изучении задачи консенсуса (см. [3, 6, 21]). Теорема Перрона-Фробениуса (см. [44]) утверждает, что линейный стохастический (марковский) оператор, ассоциированный с положительной квадратной стохастической матрицей, имеет единственное стационарное распределение (неподвижную точку) в симплексе и является сильно эргодическим (регулярным) относительно этого стационарного распределения (т. е. траектория, начинающаяся в любой начальной точке, сходится к единственной неподвижной точке). Более того, такой оператор также является сжатием. Другими словами, класс положительных сильно эллиптических эргодических (регулярных) линейных стохастических (марковских) операторов совпадает с классом положительных сжимающих линейных стохастических (марковских) операторов. Однако в нелинейном случае ситуация становится более сложной, чем можно ожидать. Вопервых, в отличие от линейного случая, положительность не гарантирует единственности неподвижных точек квадратичных стохастических (нелинейных марковских) операторов. Вовторых, положительность и единственность неподвижных точек не влечет сильную эргодичность (регулярность) квадратичных стохастических (нелинейных марковских) операторов. Наконец, существуют положительные сильно эргодические (регулярные) квадратические стохастические (нелинейные марковские) операторы, не являющиеся сжатием. Это свойство неожиданно для квадратических стохастических операторов. Теперь приведем примеры для каждого случая. Примеры, данные в этом разделе, разбросаны по различным источникам, однако ради полного и всестороннего изучения мы собрали их все здесь, чтобы получить полное представление о проблеме. Приведем их кратко, не вдаваясь в детальные объяснения. Пример 4.1 (положительность ⇒ единственность неподвижной точки; [40, 41]). Выберем три точки A и C = (0,59, 0,31, 0,1)T из симплекса S2. Определим положительный квадратичный стохастический оператор Q : S2 → S2 следующим образом: ⎧ Q 319300232873 2 + 4717 x22 + 63860207 x23 + 75x1x2 + 53x1x3 + 501 x2x3, ( (x))1 = x1 10300 Q ⎪⎪⎨⎪⎪ Q 27 2 + 1x22 + 203 x23 + 814300470171x1x2 + 407150378421x1x3 + 814300158157x2x3, :( (x))2 = 100x1 2 54 433 27037 18409 191589 1454157 ⎪⎪⎪⎪⎩⎪(Q(x))3 = 79825x21 + 10300x22 + 31930x32 + 814300x1x2 + 407150x1x3 + 814300 x2x3. Непосредственное вычисление показывает, что точки A,B,C являются неподвижными точками положительного квадратичного стохастического оператора Q : S2 → S2. Пример 4.2. (положительность единственность неподвижной точки ⇒ сильная эргодич-R → ность; [30, 31]). Определим положительный квадратичный стохастический оператор ε : S2 S2 для любого следующим образом: , Положительный квадратичный стохастический оператор Rε имеет единственную неподвижную точку c , которая является отталкивающей. Следовательно, он не является сильно эргодическим (регулярным). Пример 4.3 (сильная эргодичность ⇒ сжатие; [29, 32]). Определим положительный квадратичный стохастический оператор Qε : S2 → S2 для любого следующим образом: , Положительный квадратичный стохастический оператор является сильно эргодическим (регулярным) с единственной неподвижной точкой p . Однако он не является сжимающим. В самом деле, пусть - положительное число, A = (0,a,1 - a)T и 2 2ε e3 = (0,0,1)T . Тогда легко видеть, что 3 1 - - - 3 1. Эти примеры показывают, что нелинейный аналог теоремы Перрона-Фробениуса для положительных квадратичных стохастических операторов является неверным. В то же время эти примеры дают нам основание для изучения нелинейной задачи Перрона-Фробениуса для некоторого подкласса положительных квадратичных стохастических операторов. Обсудим этот вопрос в следующих разделах. 5. СРЕДНИЕ ПРОЦЕССЫ КРАУЗЕ ЧЕРЕЗ КВАДРАТИЧНЫЕ СТОХАСТИЧЕСКИЕ ОПЕРАТОРЫ В этом разделе мы установим некоторую корреляцию между средними процессами Краузе и квадратичными стохастическими операторами. Сначала введем некоторые понятия и обозначения. Определение 5.1. Кубическая матрица P = (pijk)mi,j,k=1 называется дважды стохастической, если . Замечание 5.1. В данной работе мы не требуем выполнения условия pijk = pjik для всех i,j,k ∈ Im. Пусть P = (pijk)mi,j,k=1 - кубическая дважды стохастическая матрица и - квадратная матрица для фиксированного k ∈ Im. Ясно, что матрица также является квадратной стохастической матрицей. В дальнейшем будем писать P = (P••1|...|P••m) для кубических дважды стохастических матриц. Определим квадратичный стохастический оператор Q : Sm-1 → Sm-1, ассоциированный с кубической дважды стохастической матрицей, следующим образом: . (5.1) Также определим линейный стохастический оператор Lk : Sm-1 → Sm-1, ассоциированный с квадратной стохастической матрицей P••k = (pijk)mi,j=1, следующим образом: . (5.2) Из выражений (5.1) и (5.2) следует, что , где через (·,·) обозначено стандартное скалярное произведение двух векторов. Следовательно, квадратичный стохастический оператор Q : Sm-1 → Sm-1, заданный формулой (5.1), может быть записан в виде , (5.3) где оператор Lk : Sm-1 → Sm-1 определен формулой (5.2) для всех k ∈ Im. Теперь определим m × m-матрицу . (5.4) Покажем, что матрица P(x) является дважды стохастической матрицей для любого x ∈ Sm-1. m В самом деле, известно, что, где . (5.5) Следовательно, имеем . Следовательно, из (5.3) и (5.4) следует, что Q(x) = P(x)x. (5.6) Назовем эту матрицу матричной формой квадратичного стохастического оператора (5.1), ассоциированного с кубической дважды стохастической матрицей P = (P••1|...|P••m). Теперь представим нелинейную динамику обмена мнениями в многоагентной системе. Q DSM-протоколSm-1 → Sm-1 :- квадратичный стохастический оператор, ассоциированный с кубическойПусть P = (P••1|...|P••m) - кубическая дважды стохастическая матрица идва: многоагентной системе порождена квадратичным стохастическим операторомжды стохастической матрицей P = (P••1|...|P••m). Положим, что динамика обмена мнениями вQ : Sm-1 → Sm-1 следующим образом: x, x(0) ∈ Sm-1, где x- субъективное распределение после n пересмотров. Мы предлагаем интерпретацию многоагентной системы DSM-протокола. Положим, что каждый агент может пересмотреть свое мнение по некоторому вопросу после воздействия всех возможных групп из 2-х агентов, что очевидно создает нелинейность в предложенной модели. Для того чтобы модель оставалась однородной, мы интерпретируем воздействие отдельного агента как воздействие группы из двух идентичных агентов. Более точно, сделаны следующие допущения: • Имеется группа из m агентов Im := {1,... ,m}, действующих вместе как команда или комитет. • Каждый агент может обозначить свое мнение по некоторому вопросу. Мнение- это общее понятие, которое представляет убеждение, поведение или отношение агента. • Профиль мнения в момент времени n является стохастическим вектором x, . • Каждый агент, например, k, подвержен воздействию группы из двух агентов, например, {i,{j}}, в которой агент j является представителем группы. • Воздействие группы из двух агентов, например, {i,{j}} (соответственно, {j,{i}}) с представителем j (соответственно, i), на агента k обозначим через pij,k (соответственно, pji,k). В общем случае возможно, что. • Профиль воздействия группы {i,{j}} с представителем j - это стохастический вектор pij• := (pij,1,pij,2,...,pij,m)T . • Воздействия всех возможных групп из двух агентов на агента k задаются квадратной стохастической матрицей P••k = (pij,k)mi,j=1. • Агент верит, что группа из двух агентов является доверенной/влиятельной, если ее влияние на агента высоко. • Доверие pkj(x(n)) агента k агенту j с профилем мнения x(n) - это среднее влияние всевозможных групп из двух агентов, для которых агент j является представителем агента k с профилем мнения x(n), т. е.. • Матрица доверия с профилем мнения x(n) является квадратной стохастической матрицей . • Профиль мнения в момент времени n + 1 пересматривается следующим образом: x(n+1) := . Из формулы (5.6) следует, что динамика обмена мнениями в многоагентной системе, заданная DSM-протоколом, может быть записана как x, x(0) ∈ Sm-1, где x- субъективное распределение после n пересмотров. Это значит, что согласно матричной форме (2.1) динамика обмена мнениями в многоагентной системе, заданной формулой DSM-протокола, порождает средний процесс Краузе. Следовательно, имеем следующий результат. Утверждение 5.1 (см. [38]). Пусть P = (P••1|...|P••m) -кубическая дважды стохастическая матрица, а оператор Q : Sm-1 → Sm-1 - ассоциированный квадратичный стохастический оператор. Тогда динамика обмена мнениями в многоагентной системе, данная формулой DSM-протокола, порождает средний процесс Краузе. Очевидно, что для любого ненулевого вектора x 0 имеем x , где x . Следовательно, если и если . Таким образом, в отличие от линейного случая, симплекс является единственным инвариантным множеством при действии квадратичного стохастического оператора, т. е.. Другими словами, для любого начального мнения x(0) ∈ Sm-1 динамика обмена мнениями в многоагентной системе, заданная DSM-протоколом, порождает векторную последовательность , для которой x(n) ∈ Sm-1 при всех n ∈ N. Аналогично линейному случаю, говорят, что в структурированной синхронной многоагентной системе с переменным временем достигнут консенсус, если векторная последовательность сходится к c = (c,...,c)T ∈ Sm-1 при n → ∞. Однако,очевидно, что только стохастический вектор симплекса с равными распределениями является центром симплекса, т. е. c . Следовательно, в отличие от линейного случая, консенсус в динамике обмена мнениями, заданной DSM-протоколом, не зависит от начального мнения x(0) ∈ Sm-1 и может быть сформулирован следующим образом. Определение 5.2. Говорят, что многоагентная система с течением времени достигает консенсуса, если динамика обмена мнениями сходится к центру cсимплекса Sm-1. 6. ОБЗОР ПРЕДЫДУЩИХ РЕЗУЛЬТАТОВ В этом разделе мы даем обзор предыдущих результатов (см. [34-39]) в области нелинейных задач консенсуса. Определение 6.1. Кубическая матрица P = (pijk)mi,j,k=1 называется трижды стохастической, если имеет место . Очевидно, что если матрица P = (pijk)mi,j,k=1 является кубической стохастической матрицей, то она также является кубической дважды стохастической. Следовательно, квадратичный стохастический оператор, ассоциированный с кубической трижды стохастической матрицей, также порождает средний процесс Краузе. TSM-протоколQ Sm-1 →: Пустьm-1 - квадратичный стохастический оператор, ассоциированный с кубическойP = (P••1|...|P••m) - кубическая трижды стохастическая матрица и пусть : S в многоагентной системе порождена квадратичным стохастическим операторомтрижды стохастической матрицей P = (P••1|...|P••m). Положим, что динамика обмена мнениямиQ Sm-1 → Sm-1 : следующим образом: x, где x- субъективное распределение после n пересмотров. Определение 6.2. Кубическая матрица P = (pijk)mi,j,k=1 называется диагонально положительной, если ее диагональ diag(P) := (pjjk)mj,k=1 положительна, т. е. diag(P) > 0, где diag . Следующий результат был доказан в работах [34-39]. Теорема 6.1 (консенсус кубической трижды стохастической матрицы; см. [34-39]). Пусть P = (P••1|...|P••m) - кубическая трижды стохастическая матрица, и пусть Q : Sm-1 → Sm-1 - ассоциированный стохастический оператор. Если diag(P) > 0, то динамика обмена мнениями многоагентной системы, заданная TSM-протоколом, со временем достигает консенсуса. Это показывает, что справедлив нелинейный аналог теоремы Перрона-Фробениуса для квадратичных стохастических операторов, ассоциированных с (диагонально) положительными кубическими стохастическими матрицами. В следующем разделе мы улучшаем этот результат для случая квадратичных стохастических операторов, ассоциированных с (диагонально) положительными кубическими дважды стохастическими матрицами. Также хотелось бы подчеркнуть, что поскольку мы не требовали условия pijk = pjik при i,j,k ∈ Im, то в общем случае двойная стохастичность не влечет тройной стохастичности кубических матриц. 7. ОСНОВНОЙ РЕЗУЛЬТАТ Теперь мы готовы сформулировать основной результат нашей работы. |P Теорема 7.1m) - кубическая дважды стохастическая матрица, и пусть(консенсус кубической дважды стохастической матрицыQ :).SПустьm-1 → PSm-=1 -ассоци-(P••1|... •• ированный квадратичный стохастический оператор. Если diag(P) > 0, то динамика обмена мнениями многоагентной системы, заданная DSM-протоколом, со временем достигает консенсуса. Интерпретация многоагентной системы. Предположим, что динамика обмена мнениями в многоагентной системе задана DSM-протоколом. Если влияние каждой группы из двух идентичных агентов на любого другого агента положительно, то многоагентная система со временем достигает консенсуса. Доказательство. Пусть P = (P••1|...|P••m) - диагональная положительная кубическая дважды стохастическая матрица. Пусть - траектория ассоциированного квадратичного стохастического оператора Q : Sm-1 → Sm-1, начинающаяся с точки x(0) ∈ Sm-1. Согласно определению, многоагентная система со временем достигает консенсуса, если сходится к центру c симплекса Sm-1. Очевидно, поскольку diag(P) > 0, то для любого значения x ∈ Sm-1 мы имеем . Это означает, что Q(Sm-1) intSm-1. Поскольку Q(Sm-1) - компактное множество, то существует число α > 0 такое, что . Следовательно, достаточно исследовать динамику квадратичного стохастического оператора Q : Sm-1 → Sm-1 над множеством Sα = {x ∈ Sm-1 : x αe}, которое является инвариантным. Пусть x(0) ∈ Sα. Поскольку Sα - инвариантное множество, имеем, т. е. xe для любых n ∈ N. Из матричной формы (5.6) квадратичного стохастического оператора следует, что x, (7.1) где P(x) - квадратная стохастическая матрица, определенная уравнением (5.4). Пусть для любых двух целых чисел s > r выполнено . Тогда для любых n r 0 получаем, что x(n+1) = P[x(n),x(0)]x(0) = P[x(n),x(r)]x(r). Для квадратной стохастической матрицы из (5.5) следует, что . Это значит, что квадратная стохастическая матрица P(x(n)) положительна для любых n ∈ N. Более того, она является скремблирующей. Пусть - коэффициент Добрушина эргодичности квадратной стохастической матрицы P = (pij)mi,j=1 (см. [44]). Поскольку матрица P(x(n)) положительна, а ее элементы равномерно отделены от нуля для любого n ∈ N, то мы получаем, что . (7.2) Следовательно, имеем . Следовательно, обратное произведение стохастических матриц слабо эргодично (см. [44]), а также сильно эргодично, т. е. lim P[x(n),x(0)] = mcT c и n→∞ lim x(n+1) = lim P[x(n),x(0)]x(0) = c, x(0) ∈ Sα, n→∞ n→∞ где c. Это завершает доказательство. Замечание 7.1. Из теорем 6.1 и 7.1 следует, что консенсус устанавливается в динамике обмена мнениями, заданной диагонально положительными кубическими дважды, а также трижды стохастическими матрицами. Вероятно, можно было ожидать того же результата для динамики обмена мнениями, заданной диагонально положительными кубическими одинарно стохастическими матрицами. Однако это не так. Например, консенсус не может быть установлен для динамики обмена мнениями, заданной примерами 4.1 и 4.2. В самом деле, пример 4.1 показывает, что динамика обмена мнениями, заданная (диагонально) положительными кубическими одинарно стохастическими матрицами, может сходиться к трем различным непостоянным состояниям, зависящим от начального мнения. Более того, в отличие от случая задачи консенсуса, пример 4.2 показывает, что состояние консенсуса (которое является центром симплекса) может быть отталкивающим положением равновесия для динамики обмена мнениями, заданной (диагонально) положительными кубическими одинарно стохастическими матрицами. Следовательно, двойная стохастичность кубической матрицы играет ключевую роль в изучении нелинейных задач консенсуса. 8. ПРИМЕР Рассмотрим кубическую дважды стохастическую матрицу P = (P1••|P2••|P3••), где P1••, P2•• и P3•• являются квадратными дважды стохастическими матрицами следующего вида: . Следующий квадратичный стохастический оператор Q : S2 → S2 представляет DSM-протокол: Q(x) = x1 (P1••x) + x2 (P2••x) + x3 (P3••x) = P(x)x, (8.1) где P(x) = x1P1•• + x2P2•• + x3P3•• - квадратная дважды стохастическая матрица. В работах [34-39] было показано, что если квадратные дважды стохастические матрицы P1••,P2••,P3•• положительны и , (8.2) то в системе, заданной DSM-протоколом достигается консенсус. Однако теорема 7.1 улучшает этот результат. А именно, в отсутствие положительности квадратных дважды стохастических матриц P1••,P2••,P3•• и в отсутствие ограничений (8.2) в системе, заданной DSM-протоколом, по-прежнему достигается консенсус, если кубическая дважды стохастическая матрица P является (только) диагонально положительной, т. е. diag. тельности второго столбца матрицыДругими словами, мы требуем только положительности первого столбца матрицы P1••,P3положи-••, чего P2•• и положительности третьего столбца матрицы достаточно для установления консенсуса системы. Строчно-стохастическая матрица как минимум с одним положительным столбцом иногда называется матрицей Маркова (см. [44]). В этом смысле результат данной работы обобщает и расширяет все предыдущие результаты работ [34-39]. Благодарности. Авторы глубоко признательны анонимному рецензенту за внимательное чтение рукописи и конструктивные замечания и предложения, которые в значительной степени способствовали улучшению качества и оформления статьи.

Об авторах

М. Сабуров

Американский университет Ближнего востока

Автор, ответственный за переписку.
Email: msaburov@gmail.com
Эгайла, Кувейт

Х. Сабуров

Национальный университет Узбекистана им. М. Улугбека

Email: khikmatdr@gmail.com
Ташкент, Узбекистан

Список литературы