Автоматика и телемеханика, № 12, 2014
Системный анализ и исследование
операций
( 2014 г. М.А. ГОРЕЛОВ, канд. физ.-мат. наук (griefer@ccas.ru),
А.Ф. КОНОНЕНКО , д-р физ.-мат. наук
(Вычислительный центр РАН, Москва)
ДИНАМИЧЕСКИЕ МОДЕЛИ КОНФЛИКТОВ II. РАВНОВЕСИЯ
Статья является второй частью обзора, посвященного моделям динамических конфликтных ситуаций. В ней излагаются методы поиска и качественная структура равновесных решений динамических игр.
1. Введение
В первой части обзора [1] обсуждался выбор языка моделирования динамических конфликтов. В данной статье рассматриваются способы исследования конфликтов, в которых игроки равноправны. Под равноправием игроков в данном контексте понимается наличие симметрии у принципа оптимальности, используемого для описания конфликта. При этом, разумеется, игроки могут отличаться своими возможностями (в том числе и доступом к информации) и интересами. Симметричными, как правило, являются принципы оптимальности типа равновесия.
В основном рассматриваются ситуации равновесия по Нэшу и совершенные равновесия. Такие модели наиболее просты и поэтому наиболее часто используются.
Основное внимание уделяется вопросу о том, как изменения информированности игроков влияют на сложность оптимальных стратегий и на трудность возникающих перед исследователем модели задач.
Для конкретности речь идет о ситуациях равновесия в многошаговых играх. Этот выбор вызван в основном соображениями экономии места. На другие классы моделей все обсуждающиеся результаты переносятся более или менее непосредственно. Новые трудности, в основном технического характера, возникают лишь при исследовании моделей с непрерывным временем. Соответствующая техника подробно изложена в [2-4].
2. Совершенные равновесия
В данной статье будут рассмотрены многошаговые игры, которые задаются следующим образом.
Фиксируем множество игроков N = {1, 2,... ,п} и дискретный временной отрезок В = {0,1,... ,Т + 1}. Для каждого £ € В зададим множество возмож-
ных состояний (фазовое пространство) X динамической системы. В пространстве Хо выберем точку х0, которую будем интерпретировать как начальное состояние рассматриваемой динамической системы. Для каждого Ь € € В и каждого г € N зададим множество Цг, из которого в момент времени Ь игрок г производит выбор своего управления.
Динамику системы будем описывать уравнениями:
(1) х0 = ж0,
(2) ж+1 = ), Ь = 0,1,...,Т.
Интересы игрока с номером г будем моделировать стремлением к максимизации функции дг(хт +1) конечного состояния управляемой динамической системы.
В данном разделе будем рассматривать следующий вариант информированности игроков. Будем предполагать, что, принимая решение в момент времени Ь, игрок с номером г имеет информацию о текущем состоянии х^ и об управлениях , и2,..., и£-1, уже выбранных в данный момент игроками с меньшими номерами.
На формальном уровне это означает, что стратегией игрока г является на-
г-1
бор «г = («0, и?,..., «Т) функций « : X х П и/ — Цг (для г = 1 естественно
3 = 1
0
положить X г х Л и/ = Х4).
3=1
Если стратегии и1,«2,..., ип выбраны, то система уравнений (1), (2), дополненная уравнениями
и = «(х^и^и2,...,^-1), г = 1,2,..., п, Ь = 0,1,...,Т,
позволяет последовательно вычислить фазовые точки Ж1, Ж2,..., жт +1 и выигрыши д1(хт+1), д2(хт+1),... ,дп(хт+1). Таким образом, описанная игра может быть приведена к нормальной форме.
Все, о чем будет говориться в данном разделе, справедливо для общих игр такого рода. Однако сложность формул быстро растет с увеличением числа игроков. Поэтому ограничимся рассмотрением игр трех лиц (п = 3). Все качественные особенности в этом случае хорошо видны, а формулы получаются достаточно обозримыми.
Попробуем поискать рациональные способы поведения игроков в такой игре. Будем анализировать процесс принятия решений с конца.
Последнее решение принимается в момент времени Т игроком с номером три. В этот момент он уже знает текущее значение фазовой переменной хт и управления иТ,иТ, выбранные на данном шаге его партнерами. Поэтому для него все сводится к решению обычной задачи оптимизации функции
ВТ (хт, иТ, иТ; иТ) = д3(/т (хт, иТ, иТ, иТ)).
Логично предположить, что третий игрок выберет свое управление и2 (ж2 ,«2) так, что
(3) B2(ж2,«2; и2(ж2,«2,«2)) = max B2(ж2,«2,«2; «2)•
«Т euT
Это условие определяет функцию и2 : X2 х U2 х U2 — U2.
Теперь встанем на точку зрения второго игрока. В момент времени T он достоверно знает текущее состояние Xy динамической системы и управление «Т, выбранное на этом шаге первым игроком. Он не знает точно выбора на этом шаге третьего игрока, но, зная его интересы, вполне может предположить, что тот выберет свое управление и2(ж2,«2,«2) так, что оно будет удовлетворять уравнению (3). Если второй игрок примет такую гипотезу, то для него задача тоже сведется к максимизации функции
(4) В2 (ж2,«2 ; «2) = g2(/2 (жт,и2,«2 ,и2 (жт,и2,«2 )))•
Естественное решение в таком случае состоит в выборе управления ИТ(жт,«Т), удовлетворяющего условию
(5) В2(ж2,«2; ИТ(ж2,«2)) = max В2(ж2,«2; «Т).
«Т eu^
Наконец, взглянем на ситуацию глазами первого игрока. В момент времени T он знает только текущее состояние динамической системы. Но он вполне может провести изложенные выше рассуждения и предположить, что его партнеры будут выбирать свои управления, удовлетворяющими уравнениям (3) и (5). В таком случае первому игроку разумно выбирать свое управление «Т (жу) так, что
Bp(ж2; иТ(ж2)) = max Bp(ж2; «2), «Т euT
где
Bp (ж2 ; «2) = g1/ (ж2,«2,и2 (ж2,«2),и2 (ж2,«2,и2 (ж2,«2)))).
Если игроки будут руководствоваться такой логикой поведения, то, находясь в момент времени T в точке Жу, они могут рассчитывать на получение выигрышей
g2(жТ) = 9%(h(жТ, и2(жТ), и2(жТ, и2(Жу)), Иу(Жу, и2(Жу), «2(Ж2, «2)))),
i = 1, 2, 3.
Но теперь можно продолжить те же рассуждения, заменив T на T — 1, а функции gp,g2,g3 на функции gp,g2, g3 соответственно. В результате будут построены функции «2- i, «2- i, «2- i и gp- p ,g2- p ,g3_ p.
Продолжая подобным образом, можно получить оптимальные в определенном смысле стратегии и 1, и2 и и3.
Тем самым определен некий принцип оптимальности. Построенные подобным образом наборы стратегий (и1 ,и2, и3) называют ситуациями совершенного равновесия. Обсудим свойства этого принципа оптимальности.
Прежде всего стоит отметить, что всякая ситуация совершенного равновесия является ситуацией равновесия по Нэшу. Это означает, что если все игроки, кроме одного, будут рассуждать описанным выше образом, то и оставшемуся выгодно выбирать стратегию, входящую в ситуацию совершенного равновесия. Последнее следует понимать так. Если стратегии всех игроков, кроме одного, заданы, то для выделенного игрока проблема выбора решения превращается в задачу оптимального управления. В этом случае с понятием рационального выбора проблем не возникает: нужно просто выбирать стратегию, максимизирующую выигрыш. Одной из таких стратегий будет стратегия, входящая в выбранную ситуацию совершенного равновесия. Доказывается это простой индукцией «с конца».
Сказанное отвечает за слово «равновесие». в термине «совершенное равновесие». Слово «совершенное» отражает следующее обстоятельство.
Пусть указанным выше способом определена многошаговая игра. Тогда, выбрав момент времени т € В и точку хт € Хт, можно определить подыг-ру рассматриваемой игры. Множество игроков в ней будет тем же самым. В качестве временного отрезка будет фигурировать множество {т, т + 1,... ..., Т + 1}. Динамика системы будет описываться уравнениями (1), (2) (для Ь ^ т), а выигрыши - прежними функциями дг(хТ+1). Получим игру с той же структурой, что и прежде.
При этом если набор «г = («0,«{,..., «Т) является стратегией в исходной игре, то соответствующий набор («? , иТг+1,..., «Т) будет стратегией в подыгре.
Ситуации совершенного равновесия обладают следующим замечательным свойством, называемым универсальностью по подыграм. Если ситуация (и1, и2,..., и^) является ситуацией совершенного равновесия, то при любых т € В и хт € Хт ситуация, составленная из «кусков» стратегий вида («?, «г+1,..., «Т), будет ситуацией совершенного равновесия в соответствующей подыгре.
Именно свойство универсальности по подыграм позволяет применять метод анализа с конца для построения ситуаций совершенного равновесия, что и было сделано выше.
Это же свойство отвечает за другое приятное свойство совершенных равновесий. В рассматриваемой игре выигрыши игроков зависят от состояния динамической системы в конечный момент времени. Поэтому, попав в момент времени т в точку хт, игрок должен «смотреть вперед», его поведение не должно зависеть от того, каким образом развивались события раньше. Ситуации совершенного равновесия обладают таким свойством «независимости от предыстории».
Теперь придется добавить несколько ложек дегтя в эту бочку меда.
Прежде всего следует отметить, что определение совершенного равновесия сформулировано для многошаговой игры и не может быть переформулировано в терминах нормальной формы той же игры. Это иногда затрудняет анализ задачи.
Более существенные проблемы возникают, если максимум в уравнении (3) или его аналогах достигается в нескольких точках. Рассмотрим следующую игру.
Пример 1. Положим N = {1, 2}, В = {0,1}, Х0 = {0}, Х1 = {1, 2, 3, 4}, х0 = 0. Пусть динамика задается уравнением х1 = х0 + 2«1+и2, где и1 € Ц1 = = {0,1}, и2 € и2 = {0,1}, а функции выигрыша таковы, что д1(х1) = х1 — х1, а
д2(0) = 0, д2(1) = 2, д2(2) = 0, д2(3) = 1.
Уравнение, аналогичное уравнениям (3) или (5), в данном случае определяет две оптимальные стратегии второго игрока: «0(0, 0) = 0, «2(0,1) = 1 и «0(0, 0) = 1, «0(0,1) = 1. Но в случае выбора стратегии «2 первому игроку следует выбирать стратегию «0(0) = 1, а в противном случае - стратегию «1(0) = 0.
Таким образом, получаем две ситуации совершенного равновесия. Причем они неравноценны не только с точки зрения первого игрока, но и с точки зрения второго.
Как следствие, приходим к тому, что оптимальные стратегии в случае совершенного равновесия, вообще говоря, не могут выбираться игроками изолированно.
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.