Автоматика и телемеханика, № 8, 2015
Стохастические системы, системы массового обслуживания
© 2015 г. В.В. БРЕЕР, канд. техн. наук (cogelet@gmail.com), А.Д. РОГАТКИН (andreyrogatkin@gmail.com)
(Институт проблем управления им. В.А. Трапезникова РАН, Москва)
ВЕРОЯТНОСТНАЯ МОДЕЛЬ ПОРОГОВОГО ПОВЕДЕНИЯ В МНОГОАГЕНТНЫХ СИСТЕМАХ
Исследуется пороговая модель поведения в многоагентных системах, основанная на модели Грановеттера, которая расширена для случая стохастических значений порогов агентов. С использованием методов больших уклонений получен явный вид функционала действия, максимальное значение которого соответствует наиболее вероятной траектории динамики системы. Установлена связь функционала действия с детерминированной траекторией модели Грановеттера и его связь с относительной энтропией.
1. Введение
Модель Грановеттера [1], являющаяся основой стохастической модели данной статьи, описывает так называемое пороговое поведение агентов, повторяющих действия своего окружения. Эта модель образовала целое направление исследований коллективного поведения в системах с большим количеством агентов и фигурирует в десятках публикаций (см. подробнее обзор [2, 3]). Теоретические результаты нашли широкую область приложений начиная с простого поведения при погромах, выборе между двумя малознакомыми ресторанами и заканчивая моделями поведения на выборах и формирования общественного мнения (см. подробнее табл. 4 в [4]).
В модели Грановеттера, кроме подверженности влиянию окружающих, каждому агенту приписывается индивидуальная характеристика, называемая порогом. Агент может находиться в двух состояниях - либо действовать, либо бездействовать. Выбор соответствующего состояния осуществляется агентом, с одной стороны, исходя из его порога и с другой - исходя из социального «давления», которое на него оказывают другие агенты. Если доля действующих соседей данного агента превышает его порог, то он начинает действовать, в противном случае - бездействует. На основании анализа функции распределения порогов исследуется динамика поведения агентов и сходимость соответствующей динамической системы к равновесному состоянию.
В модели [1] характеристикой всего множества агентов является доля агентов, действующих в равновесном состоянии. Эта доля носит континуальный
характер, поэтому модель Грановеттера неприменима для описания поведения конечного числа агентов. В [4] вводится теоретико-игровая модель конформного поведения, которая лишена этого недостатка и позволяет исследовать поведение любого конечного числа агентов с точки зрения их целенаправленного поведения (индивидуального принятия решений с учетом прогноза поведения оппонентов). Здесь игровое поведение характеризуется равновесием Нэша. Показано, что для вычисления этого равновесия необходимо решить алгебраическое уравнение, в котором участвует эмпирическая функция распределения величин порогов агентов. Но так как исследуется равновесие Нэша в чистых стратегиях, то эмпирическая функция распределения не носит стохастического характера и пороги считаются детерминированными величинами.
В настоящей статье сделана попытка «навести мост» между детерминированной моделью [1] и теоретико-игровой моделью [4]. Для этого согласно аксиоматике Колмогорова [5] строится вероятностная модель независимых случайных величин - порогов и исследуется момент выхода из области устойчивого положения равновесия случайной последовательности, порожденной эмпирической функцией распределения порогов. Оказалось, что для большого числа агентов вероятностное распределение этого момента можно оценить через функционал действия, зависящий от теоретической функции распределения порогов.
Предлагаемая вероятностная модель порогового поведения в отличие от моделей из [4] и [1] позволяет оценить вероятность редких событий, в том числе время выхода системы из области притяжения положения равновесия (далее - выход из области), а также наиболее вероятную траекторию этого выхода (выход из области притяжения аналогичен преодолению частицей потенциального барьера в квантовой физике).
Доказано множество теорем, позволяющих оценить близость эмпирической и теоретической функций распределения. Так, классическая теорема Гливенко-Кантелли [6] доказывает сходимость эмпирической функции распределения к теоретической при стремлении числа выборок к бесконечности. После этого начиная с работы Санова [7] теория больших уклонений занимается исследованием скорости сходимости в этом пределе, точнее, изучением энтропии. Формулировка центрального утверждения 3, которая приведена в этой статье, стоит ближе всего по смыслу к фундаментальной работе Вент-целя и Фрейдлина [8], которая только в 2000 г. после перевода на английский язык стала популярной на Западе.
В процессе исследования вероятностной модели точное выражение (12) для вероятности выхода из области получается достаточно сложным для анализа, но метод больших уклонений [8-10] позволяет найти адекватную грубую асимптотическую оценку. Получающаяся в пределе величина носит название функционала действия и аналогично, как это делается в вариационном исчислении, позволяет оценить наиболее вероятную траекторию и число шагов выхода из области. Кроме того, функционал действия тесно связан с относительной энтропией, а именно: его можно вычислить как условный экстремум относительной энтропии.
Настоящая статья имеет следующую структуру. В разделе 1 описывается пороговая модель Грановеттера. Далее в качестве иллюстраций приведены примеры функций распределения и введена классификация точек равновесия и областей устойчивого равновесия. Также указаны свойства функции распределения порогов агентов, соответствующие доле «конформистов», «провокаторов» и «иммунизаторов» группы.
В разделе 2 строится вероятностная модель порогового поведения агентов и на основании условий равновесия Нэша, полученных в [4], вводится в рассмотрение соответствующая стохастическая динамическая система. Тем самым теоретико-игровая модель расширяется за счет перехода от детерминированных порогов к случайным.
После того как построена стохастическая динамическая система и определен параметр «количество шагов выхода из области», выводится точное выражение (12) для вероятности выхода из области за конечное число шагов. Можно выделить следующее ключевое свойство. Если система находится в области притяжения, то для бесконечного числа агентов искомая вероятность есть бесконечно малая величина.
В связи с этим в разделе 4 оценивается асимптотическая характеристика вероятности редкого события - функционала действия и исследуются его свойства. Вводится понятие экстремальной траектории, на которой достигается максимум функционала действия. Если начальная точка находится в области притяжения детерминированной системы, то экстремальная траектория есть траектория модели Грановеттера. Этот свидетельствует о том, что построенная вероятностная модель является обобщением модели Грано-веттера.
В завершение в рамках принципа максимизации энтропии доказывается утверждение, что функционал действия есть экстремальное значение относительной энтропии по некоторому множеству.
2. Модель Грановеттера для порогового поведения.
Классификация точек равновесия
Рассмотрим социальную группу, в которой любой агент может либо «действовать» (его действие условно равно единице), либо «бездействовать» (действие равно нулю). Для агента выбор действия или бездействия имеет свои положительные и отрицательные стороны. Агенты являются рациональными, а именно: исходя из своих целей и предпочтений, а также из влияния со стороны других агентов они принимают решения так, чтобы максимизировать свой выигрыш.
Будем считать, что выигрыш агента, с одной стороны, зависит от действий (или бездействия) других агентов (т.е. от социального фактора - давления группы), а с другой - от его индивидуальных предпочтений (т.е. индивидуального фактора - автономности агента). В работе М. Грановеттера [1] такого рода поведение, зависящее от социального и индивидуального факторов, описывается в виде так называемой модели порогового коллективного поведения, к которой далее и переходим.
F(х)
х
Рис. 1. Пример динамики поведения агентов при хо > 0,5: график 1 - ^ (х); график 2 - х.
Пусть индивидуальный фактор описывается числом 9 € [0,1] - порогом, а социальный фактор - долей действующих агентов х € [0,1]. В определенный момент времени агент сравнивает значение своего индивидуального фактора с значением социального фактора и принимает соответствующее решение -действовать или бездействовать: если 9 > х, то агент бездействует, если 9 ^ ^ х, то агент действует. Обозначим теоретическую функцию распределения порогов через ^ (■) : [0; 1] — [0; 1]. Таким образом, величина ^ (х) является долей агентов, пороги которых не превышают доли действующих агентов х € € [0,1]. Рассмотрим изменение доли действующих агентов во времени (в этом описании следуем [1]). Обозначим через {х^}^>о последовательность долей действующих агентов в дискретном времени, где к - номер момента времени (шага).
Предположим, что известна доля хо агентов, действующих на нулевом шаге. Доля агентов, пороги которых не превышаютхо, составляет по определению величину ^ (хо), поэтому на шаге 1 х1 = F (хо). На следующем шаге будет действовать такая доля агентов х2, что пороги агентов, входящих в нее, не превышают х1, т.е. х2 = F (х1). Рассуждая аналогичным образом, для последующих шагов можно записать рекуррентное соотношение, описывающее динамику поведения множества агентов [1],
(1) хк+1 = F (хк) .
Положения равновесия системы (1) х* определяются точками пересечения графика функции F с биссектрисой первого квадранта F (х*) = х*. Устойчивыми являются точки равновесия, в которых график функции F пересекает биссектрису, приближаясь к ней «сверху», неустойчивыми - «снизу». Точные определения этих видов равновесия можно найти, например, в [11]. Пример динамики поведения агентов (1) при хо > 0,5 изображен на рис. 1.
Точки x = 0 и x = 1 всегда являются устойчивыми положениями равновесия, а точка x = 0,5 в данном примере - неустойчивы
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.