Содержание к диссертации
Введение
1 Динамические оптимизационные задачи на сетях с усилениями 10
1.1 Управляемые распределенные в пространстве динамические системы 10
1.1.1 Общая модель сложной детерминированной микроэкономической системыЮ
1.1.2 Управляемые системы с дискретным временем 12
1.1.3 Обобщенные динамические системы, распределенные в пространстве 16
1.2 Алгоритмы нахождения оптимального потока в сети с нелинейными усилениями 19
1.2.1 Формализация и оптимизация потоков в логистической системе 19
1.2.2 Общая постановка задачи нахождения оптимального потока в сети с усилениями в вершинах 23
1.2.3 Сети с нелинейными усилениями в дугах 28
1.2.4 Сеть с нелинейными усилениями с параллельным соединением дуг 33
1.2.5 Агрегированные сети с нелинейными усилениями. Теорема о композиции дуг 34
1.2.6 Нахождение оптимального псевдопотока в сети с непрерывными кусочно-линейными усилениями 37
1.3 Алгоритмы нахождения оптимального динамического потока в сети с нелиней
ными усилениями 43
1.3.1 Определение динамического потока в сети с нелинейными усилениями 43
1.3.2 Частные случаи. Модель Неймана как универсальная динамическая модель 45
1.3.3 Сведение задачи нахождения оптимального динамического потока к статической задаче 49
1.3.4 Алгоритм нахождения оптимального динамического потока методом динамического программирования з
2 Динамические нестратегические многокритериальные задачи на сетях 53
2.1 Динамические многокритериальные задачи 54
2.1.1 Семейство динамических многокритериальных задач и критерии оптимальности 55
2.1.2 Свойства оптимальных решений 57
2.1.3 Принципы динамической устойчивости задач многокритериальной оптимизации и их взаимосвязь 61
2.1.4 Теорема о динамической устойчивости многокритериальных задач для критериев — обобщенных интегральных выигрышей 65
2.2 Многокритериальные задачи в сетях 68
2.2.1 Постановка задачи многокритериальной оптимизации потока в сети с усилениями 68
2.2.2 Нахождение лексикографически оптимального потока в сети с усилениямибЭ
2.2.3 Алгоритмы нахождения потоков в сети с усилениями, оптимальных по Парето 70
2.3 Многокритериальная оптимизация динамических потоков в сетях 72
2.3.1 Два алгоритма многокритериальной оптимизации динамических потоков72
2.3.2 Пример 1: модель Леонтьева с разными периодами производства 75
2.3.3 Пример 2: распределение ресурсов между проектами 79
3 Динамические стратегические многокритериальные задачи на сетях 82
3.1 Коалиционные принципы оптимальности в динамических играх 83
3.1.1 Определение динамической игры с одновременными ходами игроков 83
3.1.2 Принципы оптимальности в динамической игре 86
3.1.3 Определение подыгры в развернутой форме 87
3.1.4 Динамическая устойчивость (коалиционных) равновесий в динамической игре и принцип Беллмана 89
3.1.5 Теорема о рекуррентных соотношениях динамического программирования для нахождения абсолютных равновесий в динамической игре 91
3.1.6 Теорема о рекуррентных соотношениях для нахождения всех равновесий в динамической игре 98
3.2 Обобщенные сетевые игры 101
3.2.1 Логистические сети и их формализация 101
3.2.2 Игры формирования сетей 103
3.2.3 Стратегические принципы оптимальности в сетевых играх 105
3.2.4 Коалиционные принципы оптимальности в сетевых играх 108
3.2.5 Определение параметрической сетевой игры 110
3.2.6 Определение групповой сетевой игры 116
3.3 Динамические сетевые игры 121
3.3.1 Определение динамической сетевой игры 121
3.3.2 Теорема о необходимых и достаточных условиях равновесия в динамической сетевой игре 125
3.4 Заключение 128
Список литературы
- Управляемые системы с дискретным временем
- Принципы динамической устойчивости задач многокритериальной оптимизации и их взаимосвязь
- Определение подыгры в развернутой форме
- Коалиционные принципы оптимальности в сетевых играх
Введение к работе
Актуальность темы
Развитие технологий и процессов производства в современном мире приводит к необходимости управления сложными системами, распределенными в пространстве и развивающихся во времени, с множеством различных интересов. Системы, распределенные в дискретном пространстве, моделируются графами и сетями. Задача управления подобной системой при наличии одного управляющего агента формализуется как задача оптимизации. При наличии нескольких действующих лиц (агентов) используется математический аппарат теории игр.
Задачи оптимизации сетей решаются с использованием двух подходов: сведением к задаче целочисленного линейного программирования (Данциг, Гомори) и комбинаторно-алгебраическими методами, опирающимися на свойства графов и упорядоченных алгебраических структур — эти методы в каждой задаче свои. Форд, Фал-керсон, Данциг развили теорию однопродуктовых и многопродуктовых потоков в сетях, к оптимизации которых сводятся многие другие оптимизационные задачи на сетях. Трумпер, Радзик, Тардос, Вейн рассмотрели более общую задачу оптимизации потоков в сетях с усилениями. Это аддитивные потоки, для которых величина потока в вершине складывается из величин потоков в дугах, заканчивающихся в этой вершине. Но многие экономические системы неаддитивны, и их таким образом смоделировать не удастся.
Для формализации управления многоагентными сетями используются сетевые игры. Параллельно развивались два класса сетевых игр: игры формирования сетей (Джексон, Волынски) и игры на сетях — в первую очередь, игры маршрутизации (Бэк-ман, Вардроп). При этом многие экономические системы являются динамическими и имеют свойства, для моделирования которых требуются и игры формирования сетей, и игры на сетях.
Многие сложные системы — в частности логистические — являются одновременно и динамическими, и распределенными в пространстве. Очевидно, для моделирования таких систем следует использовать динамические сети. При этом, обычно, ограничиваются описательным подходом: формализацией множества возможных состояний динамической сети без введения критериев качества и постановки оптимизационных задач. Например, Вольфрам предложил использовать для этого клеточные автоматы, Яенсен — раскрашенные сети Петри. Но в экономических системах важен оптимизационный аспект, и его надо учитывать при формализации. Форд, Фалкерсон, Майника формализовали задачи оптимизации динамических сетей как задачи о динамических потоках, Нейман и Гейл — как задачи оптимизации в модели межотраслевого баланса. В обоих случаях модель непрерывна и линейна. Между тем, актуальны также задачи оптими-
зации динамических сетей в нелинейном и в дискретном случае. Таким образом, актуальна формализация
неаддитивных оптимизационных задач в сетях, в том числе динамических — их можно описать обобщенными потоками в сетях;
динамических сетевых игр, обобщающих как игры формирования сетей, так и игры на сетях.
Цель диссертационной работы
Основной целью работы является построение и анализ математической модели управляемой динамической системы в дискретном пространстве с дискретным временем с множеством критериев оптимальности и алгоритмов принятия оптимальных решений об управлении такой системой. Для этого нужно исследовать:
-
статические потоки в сетях с нелинейными усилениями;
-
динамические потоки в сетях с нелинейными усилениями;
-
динамические сетевые игры и равновесия в них.
Положения, выносимые на защиту
-
Алгоритм нахождения оптимального потока в сети с непрерывными кусочно-линейными усилениями в дугах.
-
Модель управляемой логистической системы, распределенной в дискретном пространстве и развивающейся во времени. Формализация и решение задачи нахождения оптимальных управлений в такой системе.
-
Формализация сетевой игры, включающая в себя игры формирования сетей и игры на сетях, и алгоритмы нахождения равновесий в такой сетевой игре.
-
Формализация динамической сетевой игры и алгоритм нахождения равновесий в ней.
Научная новизна
Все результаты, выносимые на защиту, являются новыми.
Личный вклад автора
Личный вклад автора состоит в выполнении исследований, изложенных в диссертационной работе, построении алгоритмов и их реализации, в анализе и оформлении результатов в виде научных докладов и статей.
Теоретическая и практическая значимость
Теоретическая ценность работы с точки зрения системного анализа состоит в построении математических моделей динамических сетевых многокритериальных задач, рассматриваемых на среднесрочных интервалах времени (когда структура системы не меняется, но меняются ее параметры).
Теоретическая ценность работы с точки зрения математики заключается в формализации динамических игр формирования сетей, а также игр формирования сетей с параметрами дуг, определенными на произвольных нижних полурешетках. Построены алгоритмы нахождения равновесия в подобных играх.
Работа носит, в основном, теоретический характер, однако полученные результаты представляют также и практический интерес. Результаты диссертационной работы могут быть использованы для компьютерного моделирования и хранения информации о распределенных динамических экономических системах и принятия оптимальных решений в таких системах.
Апробация работы
Результаты работы докладывались и обсуждались на следующих конференциях:
-
Воронежская зимняя математическая школа "Современные методы теории функций и смежные проблемы". Воронеж;, 27 января - 2 февраля 2007 г.
-
38-я научная конференции аспирантов и студентов факультета ПМ-ПУ СПбГУ "Процессы управления и устойчивость" (SCPY2007). Санкт-Петербург, 9-12 апреля 2007 г.
-
Воронежская весенняя математическая школа "Современные методы теории краевых задач "Понтрягинские чтения-XVIII". Воронеж, 3-9 мая 2007 года.
-
43-я научная конференции аспирантов и студентов факультета ПМ-ПУ СПбГУ "Процессы управления и устойчивость" (8СРУ2012). Санкт-Петербург, 9-12 апреля 2012 г.
-
Заседания лаборатории теории игр и принятия решения СПб ЭМИ РАН.
6. Заседания кафедры моделирования социально-экономических систем факультета прикладной математики — процессов управления Санкт-Петербургского государственного университета.
0.1 Структура и объем работы
Управляемые системы с дискретным временем
В разделе 1.1.3 дано определение статической управляемой распределенной системы в дискретном пространстве. Подобные системы являются сетями — будем обозначать их буквой N. Параметрами сети можно управлять. Но определение, данное в предыдущем параграфе — слишком общее для формулировки содержательных оптимизационных задач. Далее конкретизируем определение микроэкономической системы.
Есть много способов опредедения экономической системы, позволяющих абстрагироваться от сложных свойств используемых в экономике технологий. Большинство из этих способов не охватывает всего многообразия экономических систем, а является упрощающим подходом к экономике. Процессами развития структурированных систем, процессами взаимодействия между элементами систем с фиксированной структурой и оптимизации параметров элементов и параметров взаимодействий занимается логистика [56]. Логистика — один из упрощающих подходов к экономике, абстрагирующийся от многообразия человеческих потребностей, от способов управления людьми, от жизненного цикла фирм на рынке и от многих других сложно формализуемых факторов. Логистика рассматривает лишь процессы производства, хранения, перевозки, распределения и сбыта продукции и оптимизацию этих процессов.
Таким образом, для математического моделирования систем указанного типа целесообразно пользоваться понятиями логистики. При этом возникают сетевые задачи многокритериальной оптимизации (статические и динамические) и сетевые игры (статические и динамические), в которых структура сети неизменна.
В логистике рассматриваются процессы 2-х видов: локальные процессы, происходящие в конкретном месте; потоковые процессы (потоки) — движение объектов между локальными процессами.
Таким образом, логистическую систему можно моделировать сетью, вершины которой — локальные процессы, а дуги — потоки, по которым перемещаются объекты. В логистических системах рассматриваются потоки 4 видов: 1. материальные потоки — перемещение материальных объектов, участвующих в производстве; 2. финансовые потоки — перемещение денег; 3. информационные потоки — перемещение информации; 4. потоки услуг — оказание услуг; чаще всего это сложные потоки, которые сводятся к более простым потокам и локальным процессам.
Потоки услуг не будем рассматривать, поскольку они сводятся к более простым потокам. Примем простейшее предположение о взаимной информированности агентов:
Предположение 1. Агенты принимают решения в дискретные моменты времени 1, 2,..., те, причем в каждый момент времени знают состояние системы x(t), но не знают о решениях других агентов Ui(t),... ,un(t).
Как мы увидим дальше, одновременные игры, основанные на этом предположении, включают в себя поочередные игры с полной информацией как частный случай. Это предположение позволяет нам не рассматривать информационные потоки и ограничиться только материальными. Материальные потоки бывают [56]: простые — по дуге га перемещается один продукт в количестве fm, и составные — перемещается к продуктов в количестве fm,---,fm , дискретные — fm Є Z, и непрерывные — fm Є Ш; стационарные — количество продукта fm не зависит от времени, и нестационарные — количество продукта fm(t) зависит от времени; детерминированные — fm не зависит от случайных воздействий, и стохастические — fm — случайная величина. Финансовые потоки могут быть стационарными и нестационарными, детерминированными и стохастическими, но они в логистике всегда — простые и непрерывные. Стохастические потоки мы не рассматриваем по предположению об отсутствии случайных воздействий. Детерминированные материальные и финансовые потоки всегда принадлежат некоторой частично предупорядоченной абелевой группе F: fm Є F в статическом случае и \/t fm(t) Є F в динамическом случае. Частичный предпорядок может характеризовать как пропускную способность ст дуги те, по которой движется поток (в этом случае fm cm), так и цель увеличения потока в дуге (в этом случае предпорядок — линейный, а величина fm — один из критериев оптимальности, т.е. ее нужно максимизировать).
Управляемые динамические сетевые системы часто моделируются раскрашенными сетями Петри [75]. Сети Петри применяются в логистике [64] для моделирования возможных процессов, которые могут происходить в логистической системе. Но у сетей Петри есть два недостатка. Во-первых, они предназначены для моделирования дискретных систем — для непрерывных систем (будь они даже распределены в дискретном пространстве) большинство методов работы с сетями Петри неприменимо. Во-вторых, сети Петри не описывают оптимизационный аспект, а тем более, множество критериев оптимальности.
Другой подход к логистическим системам — их моделирование кибернетическими системами [56, 14]. Тогда "входные сигналы" — это дуги, входящие в вершину г, и состояние вершины Si зависит от состояний этих дуг. "Выходные сигналы" — это дуги, выходящие из вершины г, и состояние этих дуг щ зависит от состояния вершины. Таким образом, тип вершины определяется, во-первых, множеством состояний, во-вторых, тем, как она преобразует "входные сигналы" в состояние, в-третьих, тем, как она преобразует состояние в "выходные сигналы".
Построим общую потоковую модель — сперва статическую, затем динамическую, основанную на кибернетической системе, позволяющую ставить оптимизационные задачи для материальных и финансовых потоков и включающую в себя раскрашенные сети Петри как частный случай. Для этого сперва рассмотрим возможные зависимости состояния вершины от величин входных потоков, затем — возможные зависимости величин выходных потоков от состояния вершины.
Состояние Si вершины / характеризует интенсивность локального процесса, происходящего в вершине, которую можно измерить численно и охарактеризовать функцией si = gi(xi,... , Xk), где Xi,..., Xk — интенсивности потоков, входящих в вершину. Если в вершине происходит несколько процессов 1,..., q с одинаковой интенсивностью gi(xi,... , Xk), то удобно добавить в систему q новых фиктивных вершин 1\,... ,lq (они не меняют пространство, описывающее систему, ибо находятся в той же точке пространства, что и вершина /), к которым идут дуги от / с одинаковой величиной потока /(г ) = gi{x\, ,xq), а состояние этих вершин определяется функцией sit = gii(x) = х. Если в вершине происходит несколько процессов с разной интенсивностью д}{х\,..., Xk), gf(xi,..., Xk), то удобно таким же образом добавить q фиктивных вершин и дуг с соответствующими функциями состояния gl,...,gf, а затем разбить вершину / на к новых фиктивных вершин 11,...,1к, в которые идут отдельные потоки величиной Х\,... ,Xk, и каждый поток Xj превращается в q потоков f(U,h) = fotiq) = Xj, идущих в вершины 1г,...,1д.
Принципы динамической устойчивости задач многокритериальной оптимизации и их взаимосвязь
Принципы оптимальности в задачах многокритериальной оптимизации исследовались в разных работах [12, 19, 43] с точки зрения нахождения самих принципов. В данной работе вопрос о построении принципов оптимальности в применении к логистическим системам не рассматривается. Эти принципы могут быть самыми разнообразными и зависеть от специфики рассматриваемой задачи. Но в задаче нестратегической многокритериальной оптимизации естественно предполагать, что любое оптимальное решение является Парето-оптимальным [43]. Поэтому, найдя все оптимумы Парето, можно затем перебрать их и выбрать из них те, которые удовлетворяют другим принципам оптимальности. Исходя из этого, далее построены алгоритмы нахождения всех оптимумов Парето.
Обозначим Pai/(X) — множество оптимумов Парето на множестве X по вектору критериев /. Оптимумы Парето удовлетворяют ряду важных условий.
Теорема 6. Если X — обобщенное многогранное множество, а все критерии (/ь ..., fn) — непрерывные кусочно-линейные, то оптимумы Парето удовлетворяют следующим условиям: 1. Существование: множество оптимальных решений непусто, т.е., Раг/(Х) ф 0. 2. Независимость от множества альтернатив: выбор оптимального решения зависит только от критериев оптимальности, но не от каких-либо иных свойств альтернатив. То есть это нестратегическая задача оптимизации, в которой заданы все возможные критерии оптимальности, и к ним больше нечего добавить. Формально, если х Є Раі/(Х); у Є Y, f(X) = f(Y) и f(x) = f(y), то у Є Par/(У). Очевидно, в этом, случае Раі/(У) = /_1(/(Раі/(Х))). 3. Независимость от способа измерения: оптимумы Парето не зависят от любых строго возрастающих преобразований критериев f (x) = gi(fi(x)), где gi — строго возрастающие функции: Раг/(Х) = Раг/ (Х). То есть этот принцип оптимальности можно применять для критериев, принимающих значения из любых порядковых шкал. 4- Независимость от посторонних альтернатив (рациональность): если х оптимально для множества X и х Є Xі С X, то х оптимально и для множества Xі. 5. Транзитивность: если множество альтернатив X разбито на подмножества (которые, вообще говоря, могут пересекаться): X = Хг U Х2 U U Хп то решение задачи многокритериальной оптимизации составляется из решений подзадач: Par/(X) = Par/(Par/(X1) U Раг/(Х2) U U Раг/(Хга)). Это усиление условия рациональности, означающее, что можно разбить решение сложной задачи на части, выбирая оптимальное решение из оптимальных решений подзадач.
Замечание 2.1.2. Условие единственности решения (даже в смысле единственности набора (fi(x),..., fn{x))) не рассматривается. Во-первых, для выполнения этого условия нужен ряд специфических ограничений на критерии, например, их строгая вогнутость [33]. Во-вторых, при управлении реальной экономической системой наличие нескольких оптимальных решений не является препятствием для принятия управленческого решения — для этого достаточно проделать произвольную стохастическую процедуру, вроде бросания монеты.
Прежде, чем доказать теорему, докажем лемму о принципах оптимальности, порожденных отношением порядка. Лемма 6.1. Пусть - — отношение предпорядка на Rn. Пусть принцип оптимальности задается как недоминируемость по этому отношению на множестве критериев: Sel/pQ = {х Уу Є X /(я) /(у)}. Тогда этот принцип удовлетворяет условию независимости от множества альтернатив и условию независимости от посторонних альтернатив. Если же выполнено усиленное условие существования: для любого х Є X в верхнем, конусе С (ж) = {у Є X midx у} существуют оптимальные элементы — тогда он удовлетворяет и принципу транзитивности.
Доказательство. Независимость от множества альтернатив очевидна из определения. Независимость от посторонних альтернатив очевидна: если элемент недоминируем в большем множестве, то он недоминируем и в меньшем. Докажем транзитивность. Пусть Sel X) = Sel/(Sel/(X1) U Sel/(X2) U U Sel/(Xra)). Докажем, что если х Є Sel/(X), то ж Є Selj(X).Sel/(Xj) — множество альтернатив, недоминируемых в /(Xj). Любая альтернатива, недоминируемая в X, принадлежит некоторому множеству Xj, а значит, по рациональности, принадлежит и Sel/(Xj). Следовательно, все такие альтернативы содержатся в объединении Sel/(Xi) U Sel/(X2) U U Sel/(Xra). Опять же, по независимости от посторонних альтернатив, все они содержатся в SeL(X).
Пусть теперь х Є Selj(X). Пусть х Є ХІ5 то есть х Є Sel/(Xj). От противного: пред положим, что х доминируемо неким элементом у. По усиленному условию существования, существует такой недоминируемый элемент z Є Xj, что у z. Следовательно, х - z, но при этом z Є Selj(Xj), а значит, не может быть х Є Selj(X) — противоречие. Следовательно, х недоминируемо, то есть х Є Sel/(X). Замечание 2.1.3. Усиленное условие существования имеет значение. Рассмотрим пример: пусть X = К, задан один критерий f(x) = х и - — обычное отношение порядка на X = R. Рассмотрим разбиение Е = Х\ U Х2 = (infty; 0] U (0; оо). Тогда Sel/(X) = 0, a Sel/(Sel/(Xi) U Self(X2)) = Self({0}U(H) = {0}. Перейдем теперь к доказательству теоремы:
Доказательство. 1. Существование. Достаточно доказать, что существует лексикографический оптимум по вектору критериев (fi(x),...,fn(x)). Максимум НКЛ-функции на ограниченном обобщенном многогранником множестве всегда существует. Пусть г/і = maxx&x fi(%)- Прообраз точки у\. Х\ = /1_1(г/і), очевидно, является ограниченным обобщенным многогранным множеством (как пересечение ограниченного обобщенного многогранного множества и прообраза НКЛ-функции для точки, который тоже является обобщенным многогранным множеством). Следовательно, существует максимум г/2 = піахжЄх /2 (х). Аналогично действуя дальше, получаем весь лексикографический максимум (гд,... , уга), который достигается на непустом обобщенном многогранном множестве Х . Для оптимума по Парето существование следует из того, что лексикографический оптимум оптимален по Парето и существует.
Определение подыгры в развернутой форме
Напомним определение динамической устойчивости для динамических игр [51]. Динамическая устойчивость для игр, так же, как и для многокритериальных принципов оптимальности, имеет смысл не для одной задачи (т.е., игры и принципа оптимальности), а лишь для семейства задач.
Определение 42. Пусть для игрового механизма М, соответствующего семейства задач (М(х ),(Щх1.Л,ф(х )) ситуация s, реализующая траекторию (x(ti),x(t2), .x(tn)), оптимальна: s Є ф(М(хо, to), Щх t -,). Ситуация s называется (слабо) динамически устойчивой, если во всех подыграх в развернутой форме Т(х(и),и), через которые проходит траектория, ситуация s{x{ti),ti) = (s1(x(ti),ti),... sn(x(ti),ti)), сужающая стратегии на множество точек с t U, оптимальна: s(x(U),U) Є ф(М(x(U), U), ЩХ М)) Определение 43. Будем говорить, что для игрового механизма М и соответствующего семейства задач (М{х ,(Щх1Л),ф{х выполняется принцип Беллмана или что оно является (слабо) динамически устойчивым, если всякая ситуация s = (s1,... sn) Є ф(М, (Hj)) в позиционных стратегиях слабо динамически устойчива.
Замечание 3.1.10. Обычно, говорят о динамически устойчивом принципе оптимальности [51]. Но надо понимать, что по умолчанию всегда предполагается некоторое семейство функций выигрыша для всех подмеханизмов. Как мы уже видели, можно так подобрать функции выигрыша, что даже обычный принцип оптимальности в задаче с одним игроком не будет динамически устойчив.
Покажем теперь, что для естественного семейства задач основные принципы оптимальности в динамических играх динамически устойчивы:
Теорема 12 (о динамической устойчивости равновесия). Если Rj — строго слева упорядоченная полугруппа, Hj(x) = f((x\) fl(xn) — обобщенный интегральный выигрыш и ф = NE — равновесие по Нэшу, то для естественного семейства задач выполняется принцип оптимальности Беллмана (т.е., оно слабо динамически устойчиво).
Доказательство. Рассмотрим произвольную равновесную ситуацию s Є NE(T) и соответствующую ей оптимальную траекторию p(s) = h = {х\}х 2}.. .х п). Ее оптимальность означает, что на ней достигается максимум выражения f{(x\) /2( 2) fn(xn) по множеству стратегий s3 каждого игрока j.
Рассмотрим теперь любую ее подтраекторию {x t)x t+l).. .х п) и докажем, что она максимизирует выигрыш j-ro игрока ft(xt) fn(xn) по всем его стратегиям, определенным, начиная с точки (x,t). Действительно, предположим противное: игроку j выгодно, применив стратегию s3 , отклониться от равновесной стратегии начиная с момента t t. Это значит, что существует иная подтраектория (xt, х"+1,... ж"), на которой достигается значение ft(x") - fn(xn) ft(xt) fn(xn)- Это, по строгости полугруппы выигрышей слева, означает, что ЛЮ - //( ) //+1( /+i) - UK) /iVi) - / Ю Л+і(жі+1) - й«), т.е. H3(s\\s-1 ) H3(s), что противоречит равновесности по Нэшу в исходной игре Г.
Следствие 12.1. Если Rj — упорядоченная группа и Hj(x) = f((xi) -fl(xn) — обобщенный интегральный выигрыш, то для естественного семейства задач выполняется принцип оптимальности Беллмана. Следствие 12.2. Если Rj — произвольная упорядоченная полугруппа и Hj(x) = Hj(xn) — терминальный выигрыш, то для естественного семейства задач выполняется принцип оптимальности Беллмана. Теорема 13 (о динамической устойчивости коалиционного равновесия). Если Rj — строго слева упорядоченная полугруппа, Hj(x) = f((x\) fl(xn) — обобщенный интегральный выигрыш и ф = Б — (слабое) коалиционное равновесие, где D — множество коалиций, то для естественного семейства задач выполняется принцип оптимальности Беллмана. Доказательство. Доказывается аналогично устойчивости равновесия по Нэшу. Единственная разница заключается в том, что вместо сравнения выигрышей Hi tJs) Hi t\(s ) выполняется сравнение векторов выигрышей (# ,t)(s) (x,t)(s)) (H(x,t)(s ) H(x,t)(s ))i гДе — поэлементный частичный порядок на множестве векторов, следующий из нестрогого по рядка по каждому элементу и наличия строгого порядка хотя бы по одному элементу. Нестрогий порядок по всем элементам сохраняется в упорядоченной полугруппе, строгий порядок по одному элементу сохраняется в строго слева упорядоченной полугруппе. Для слабого коалиционного равновесия — поэлементный частичный порядок на множестве векторов, следующий из наличия строгого порядка по каждому элементу. Строгий порядок по каждому элементу сохраняется в строго слева упорядоченной полугруппе.
Для произвольных упорядоченных полугрупп без свойства строгости слева не выполняется принцип оптимальности Беллмана даже для игры с одним игроком: существуют оптимальные траектории, конечные участки которых неоптимальны. Простой пример см. в разделе, посвященном многокритериальным задачам.
Сильная динамическая устойчивость и динамическая совместимость в играх определяются более сложно, чем в задачах многокритериальной оптимизации [51]. Не будем рассматривать их в настоящей работе, ибо даже оптимальность по Парето (а значит, и коалиционное равновесие) в большинстве случаев не удовлетворяет этим условиям.
Для нахождения оптимальных решений с помощью рекуррентных соотношений динамического программирования так же, как и в случае многокритериальных задач, требуется свойство позиционной динамической устойчивости, более сильное, чем обычная динамическая устойчивость.
Определение 44. Пусть для игрового механизма М, соответствующего семейства задач (M(Xtt),(Wxt- ),(/)(Xtt)) ситуация s в позиционных стратегиях оптимальна: s Є ф(М(хо, t0), Щ ts). Ситуация s называется позиционно динамически устойчивой (ПДУ-ситуацией), если во всех подыграх в развернутой форме Г (ж, ід.) соответствующая ситуация (sl{x,tk), sn{x,tk)), сужающая стратегии на множество точек с t tk, оптимальна (а значит, и позиционно динамически устойчива): s Є ф(М(х, tk), Wx t -,)
Замечание 3.1.11. В этом определении подыгры в развернутой форме в большинстве случаев не изоморфны никаким подыграм в нормальной форме, поскольку искомая ситуация для большинства подыгр в развернутой форме T(x,tk) вообще не попадает в множество допустимых, если соответствующая траектория не проходит через точку (x,tk) Пусть дано семейство задач (М, (Hj)(Xtt), ф), где М = (Х,Хо, (D, U,ir),i, (Uj) j=1, ) — динамический игровой механизм, а ф — статический принцип оптимальности. Определим рекуррентную ситуацию для игр аналогично определению для динамических принципов оптимальности:
Коалиционные принципы оптимальности в сетевых играх
Данное определение обобщает как определение статической управляемой системы в дискретном пространстве (если п = 1), так и определение параметрической сетевой игры (если N = L, р = І). В такой игре между вершинами а и Ь, которыми управляют несколько игроков, может быть несколько "параллельных" соединений. В их число входят и соединения игрока самого с собой.
Пример 14. Многошаговая игра с позиционными стратегиями, в которой могут ходить одновременно несколько игроков — это общая групповая игра со стратегиями из Xf .
Утверждение 3.2.9. Общую групповую игру можно свести к групповой игре без совместных вершин, если "размножить" вершины: каждую вершину а, управляемую игроками ii,... %k, превратить в к вершин (a, i\),... (a, ik). При этом, получится изоморфная игра.
Доказательство. Следует из сопоставления определений 55 и 56.
Групповую игру без совместных вершин, в свою очередь, можно свести к параметрической игре. Таким образом, дуги сети в общей групповой игре делятся на 2 класса: 1. Ребра взаимодействия Мр между разными игроками г и j соединяют вершины игрока і с вершинами игрока j. Они сохраняются и сливаются в одно ребро (i,j) при преобразовании игры в не групповую параметрическую игру. 2. Структурные дуги Ms, принадлежащие игроку і, соединяют между собой вершины игрока г. Они исчезают при преобразовании игры в не групповую параметрическую игру. Игры на сетях Определение 57. Игра на сети [42] — это общая групповая игра, в которой каждый игрок управляет каждой вершиной и нет взаимодействия между разными игроками (то есть все дуги — структурные). Таким образом, в игре на сети каждый игрок независимо от остальных управляет распределенной статической системой в дискретном пространстве. Важный частный случай игр на сетях: Определение 58. Сетевая игра управления потоками [70] — игра на сети, в которой множество стратегий Хi игрока г — это множество обобщенных потоков в сети.
Таким образом, игроки независимо друг от друга пускают по сети параллельные многопродуктовые потоки д\,..., дn и получают выигрыш, зависящий от результирующего потока д. Задача максимизации потока при этом тривиальна, поскольку потоки не зависят друг от друга, а следовательно, задача распадается в прямое произведение задач максимизации потока для каждого игрока.
Иное дело — если на каждой дуге задана функция стоимости, зависящая от всех потоков в сети. В этом случае, даже простейшие сетевые игры управления потоками в сетях без усилений с нелинейной функцией стоимости представляют интерес. Например, для сетей без усилений с вогнутыми функциями стоимости доказано существование равновесия [70]. Важный частный случай — игры маршрутизации, в которых каждый игрок выбирает один путь в сети, то есть поток величины 1 [8]
Требование отсутствия взаимодействий между игроками в игре управления потоками возникает потому, что иначе независимость стратегий игроков не позволяет выполнить условия потока.
Пример 15. Пусть имеются 3 вершины и 3 игрока, которые полностью управляют соответственно вершинами 1,2,3. Пусть в графе возможны только дуги (1,2) (2,3), через которые течет классический поток д, удовлетворяющий условию (/(1,2) = (/(2,3) (сколько втекает в вершину — столько из нее и вытекает). Тогда для стратегий s\, (s , s), S3 соответственно первого, второго и третьего игрока, определяющих неотрицательное значение потока в дугах, должно выполняться условие min(si, si) = min(s2, S3).
Очевидно, независимость стратегий игроков и это условие не противоречат друг другу только в том случае, когда для любых стратегий s\ = s\ Si,S3- Но это значит, что значение потока в сети полностью определяет 2-й игрок и реального взаимодействия с другими игроками нет. Аналогично, и в более сложных случаях в статической сетевой игре взаимодействие игроков невозможно, поскольку игроки не могут договориться заранее о соблюдении условий потока. Как мы увидим дальше, ситуация меняется в динамической игре, где игрок, ходящий раньше, может навязать некоторое значение потока игроку, ходящему позже.
В данном разделе определяются динамические сетевые игры с дискретным временем и исследуются свойства равновесия в динамической сетевой игре. Большая часть содержания раздела опубликована автором в [45] и [44].
Динамическая сетевая игра — это модель дискретного пространства-времени, в котором действует множество агентов, преследующих некие интересы. Ранее рассматривались динамические сетевые игры с полной информацией, т.е. поочередные игры, в которых состояние игры на каждом шаге — это граф взаимодействий игроков, т.е. сеть, в которой есть лишь простые дуги взаимодействия [65, 85, 55]. При этом моделировался динамический процесс формирования статической сети с помощью поочередных ходов игроков. Иначе говоря, целью игры является создание стабильной сети на последнем шаге, а выигрыш является терминальным.
Автором данной работы построена общая модель динамической сетевой игры с одновременными ходами игроков и тремя видами дуг: дугами взаимодействия, структурными дугами и динамическими дугами [45]. При этом, как и в статической игре, структурные дуги можно устранить, приведя игру к эквивалентному виду без структурных дуг. Но наличие динамических дуг — это существенное свойство динамической сетевой игры, делающее ее обобщением как повторяющейся статической сетевой игры, так и многошаговой игры с одновременными ходами игроков. Таким образом, можно моделировать различные динамические процессы в дискретном пространстве, в том числе и с интегральным выигрышем.
Чтобы определить динамическую сетевую игру, нужно прежде всего определить пространство и время игры. Будем рассматривать самый простой вариант шкалы времени: конечное время Т = {tl,t2,... ,tm}. Можно даже считать, что Т = {1, 2,... ,гп}.
Пространство игры, очевидно, должно быть пространством сетей G. Примем, для простоты, следующие предположения: 1. Множество вершин L не зависит от выбора сети из G. Это предположение не умаляет общности, поскольку всегда можно переименованием вершин и добавлением "фиктивных" вершин (с единственным состоянием, не связанных с другими вершинами) добиться, чтобы множества вершин у всех сетей совпали. Т.е. структура сети не меняется с течением времени, а меняются только состояния вершин и соединений. 2. Отношение управления р одно и то же для всех сетей. Это предположение также не умаляет общности, поскольку всегда можно считать, что каждый игрок управляет каждой вершиной — просто некоторые множества управления состоят из 1 элемента. 3. Множество соединений UJ3abJsa, Sb) между вершинами a, b игроков г и j зависит только от состояний вершин a, b и не зависит от состояний других вершин. Это предположение вытекает из определения дискретного пространства.