Автоматика и телемеханика, № 2, 2015
Системный анализ и исследование
операций
( 2015 г. М.А. ГОРЕЛОВ, канд. физ.-мат. наук (griefer@ccas.ru),
, д-р физ.-мат. наук
А.Ф. КОНОНЕНКО
(Вычислительный центр РАН, Москва)
ДИНАМИЧЕСКИЕ МОДЕЛИ КОНФЛИКТОВ III. ИЕРАРХИЧЕСКИЕ ИГРЫ
Статья представляет собой третью, заключительную, часть обзора, посвященного моделям динамических конфликтов. Анализируется взаимодействие неравноправных игроков, а в качестве основного принципа рационального поведения ведущего игрока выбирается принцип получения максимального гарантированного результата.
1. Введение
Данная статья завершает обзор результатов, посвященных исследованию моделей динамических конфликтов, начатый в [1, 2]. В ней рассматриваются модели взаимодействия неравноправных игроков.
Исследование такого рода моделей было начато Ю.Б. Гермейером и его учениками [3-6]. Аналогичные модели рассматривались в теории активных систем [7-10]. В несколько иной постановке эти вопросы исследовались и на западе [11, 12].
Естественно ожидать, что в модели иерархической системы будет присутствовать много субъектов. Однако исследование такого рода моделей наталкивается на серьезные трудности. Игры двух лиц гораздо проще и изучены значительно лучше. По этой причине далее будут рассматриваться только динамические игры двух лиц.
Традиционно неравноправие игроков моделируется фиксацией порядка неодновременных ходов, совершаемых субъектами. Под ходом подразумевается выбор стратегии и сообщение ее партнерам. В случае игр двух лиц возможно всего два варианта. Либо оперирующая сторона (игрок, в интересах которого проводится исследование) делает свой ход первым, либо он делает ход после партнера. Второй случай представляет меньший интерес, так как тогда для оперирующей стороны задача сводится к обычной оптимизации. Таким образом, остается вариант, в котором оперирующая сторона обладает правом первого хода.
В подобных моделях наиболее естественным и методологически оправданным принципом рационального поведения является принцип максимального гарантированного результата. Для статических моделей этот принцип определяется практически однозначно, если пренебречь некоторыми чисто техниче-
скими тонкостями. В динамических моделях появляется некоторая вариативность, которую необходимо учитывать при построении конкретных моделей.
2. Принцип максимального гарантированного результата
Опишем принцип максимального гарантированного результата, введенный в научный оборот Ю.Б. Гермейером в [13]. Он определяется для игр в нормальной форме, поэтому начнем с рассмотрения таких игр.
Игра двух лиц в нормальной форме определяется заданием двух множеств U и V и двух функций g и h, отображающих декартово произведение U х V в множество действительных чисел R. Множества U и V интерпретируются как множества управлений (стратегий) первого и второго игроков соответственно. А стремлением к максимизации функций g и h описываются интересы участников конфликта.
Традиционно максимальный гарантированный результат определяется следующим образом. Предполагается, что игрок номер один обладает правом первого хода, т.е. он первым выбирает свою стратегию и сообщает ее партнеру. Тогда для второго игрока задача выбора управления превращается в задачу максимизации функции h(u, v) при известном значении u. Поэтому первому игроку не нужно никаких дополнительных предположений, чтобы оценить множество рациональных выборов R(u) партнера. Обычно его описывают так:
R(u) = \ v € V : h(u, v) = max h(u, w) > , [ wev J
если максимум в этой формуле достигается, и
(1) R(u) = < v € V : h(u, v) ^ sup h(u, w) — к >
I wev J
в противном случае (здесь к - фиксированное положительное число). А если так, то выбор стратегии u гарантирует первому игроку получение выигрыша infv€R(M) g(u, v), а его максимальный гарантированный результат равен suPu€U infv€R(u) g(u,v).
Можно рассуждать несколько иначе. Если стратегия u первого игрока гарантирует ему получение выигрыша 7, то все множество стратегий второго игрока можно разбить на два подмножества так, что будут выполняться следующие условия. Первому подмножеству принадлежат только такие управления, использование которых приводит к маленькому (меньше Л) выигрышу второго игрока, и потому эти управления не будут выбраны. А второму множеству принадлежат управления, использование которых позволяет получить первому игроку большой (больше 7) выигрыш. Поскольку какой-то выбор второй игрок непременно должен сделать, то второе множество не должно быть пустым. Таким образом, приходим к следующему. Если стратегия u гарантирует первому игроку получение выигрыша 7, то выполняется условие
ЗЛ € R : {[3v € V : h(u,v) — Л ^ 0] Л [Vv € V (g(u,v) — 7 ^ 0) V (Л — h(u,v) ^ 0)]}
или
sup min < sup h(u, v) — Л, inf max [g(u, v) — 7, Л — h(u, v)] > ^ 0. AeR Uev veV )
Следовательно, y является гарантированным результатом, если
3u € U ЗЛ € R : {[3v € V : h(u, v) — Л ^ 0] Л Л [Vv € V (g(u,v) — y ^ 0) V (Л — h(u, v) ^ 0)]}
или
sup sup min < sup h(u, v) — Л, inf max [g(u, v) — 7, Л — h(u, v)] > ^ 0. neu AeR Uev veV )
А максимальный гарантированный результат - это точная верхняя грань тех значений 7, которые удовлетворяют последнему неравенству.
Второе определение логически проще первого, поэтому во многих случаях оно может оказаться более удобным. В большинстве систематически исследовавшихся задач среди оптимальных стратегий первого игрока непременно находилась стратегия u, для которой верхняя грань в определении множества R(u) достигается. Можно показать, что для таких классов задач два приведенных определения совпадают.
Заметим, кстати, что традиционно существование оптимальной стратегии u, для которой верхняя грань в (1) достигается, проводилось просто предъявлением такой стратегии. В [14] предложен простой геометрический прием, позволяющий устанавливать этот факт непосредственно, до выяснения структуры оптимальных стратегий. Это во многих случаях упрощает исследование задачи, и до сих пор указанный прием не давал сбоев.
Следует иметь в виду фундаментальный результат, полученный Н.С. Кукушкиным в [15]: чем большим объемом информации обмениваются игроки в процессе игры, тем больше максимальный гарантированный результат первого игрока. Этот результат становится понятным, если заметить, что в игре с правом первого хода у игрока номер 1 второй игрок имеет полную информацию о действиях партнера. Поэтому расширение класса стратегий ему ничего не дает. А первый игрок, естественно, может только выиграть от расширения своего класса стратегий.
Приведем два примера, демонстрирующих сложности, возникающие при анализе иерархических игр.
Пример 1. Рассмотрим игру в нормальной форме, в которой U = V = = [0,1], g(u, v) = u — v, h(u, v) = v(u + v — 2).
Значения функции выигрыша второго игрока всегда неположительны и равны нулю при v = 0. Если первый игрок выберет стратегию u < 1, то v = 0 будет единственным рациональным ответом второго игрока, а значит, первый игрок гарантированно получит выигрыш, равный u. Этот выигрыш может быть сделан сколь угодно близким к единице. А выигрыш, равный единице, первый игрок может получить только в одном случае, когда u = 1 и v = 0. Но при u = 1 у второго игрока имеется два рациональных ответа: v = 0 и v = 1.
Поэтому с гарантией первый игрок может рассчитывать только на нулевой выигрыш.
Таким образом, уже в этом простом примере у первого игрока нет оптимальной стратегии, и можно говорить о достижении максимального гарантированного результата только приближенно. А это не позволяет, например, использовать для поиска оптимальных стратегий необходимые условия.
Следующий пример показывает, что множество оптимальных стратегий первого игрока может сильно меняться при малых изменениях параметров игры.
Пример 2. Рассмотрим игру в нормальной форме с параметром х € € [-1,1]. Пусть и = V = [0,1], д(и, V) = х2(и + V), Л,(и, V) = и — V.
Легко видеть, что при х = 0 у первого игрока есть одна оптимальная стратегия и = 1, а при х = 0 множество оптимальных стратегий представляет собой целый отрезок [0,1].
Отметим, что если рассматривать статические игры, то описанные неприятности могут возникать только в «исключительных» случаях. Если же исследовать динамические модели, то придется оперировать параметрическими семействами таких игр, а в этом случае возникновение разрывов может стать типичным. Об этом подробнее можно прочесть, например, в [16].
Будем рассматривать следующую модель динамической управляемой системы. В управлении системой принимают участие два игрока, которых будем называть первым и вторым. Все дальнейшее исследование будет проводиться с позиций первого игрока.
Пусть система функционирует на временном отрезке В = {0,1,... , Т + 1}. Состояние динамической системы в момент времени Ь € В будем описывать точкой х; множества Начальное состояние системы х0 будем считать заданным и известным обоим игрокам.
В момент времени Ь первый игрок выбирает управление щ из множества и;, а второй - управление г>; из множества V;. Если эти управления выбраны, то динамика системы задается системой уравнений:
Интересы первого и второго игроков будем описывать стремлением к максимизации значений функций д(хт+1) и Н(хт+1) соответственно.
Обратим внимание на то, что здесь используются более простые обозначения по сравнению с использовавшимися в [1, 2]. Это стало возможно потому, что в данной статье рассматриваются только игры двух лиц.
Как и принцип равновесия по Нэшу, принцип максимального гарантированного результата может быть встроен в модель динамического конфликта двумя способами. Можно использовать этот принцип для анализа поведения игроков в каждой «маленькой» подыгре. А можно, описав информированность игроков и тем самым задав их стратегии, привести динамическую игру
3. Пошаговый способ обмена информацией
(2) (3)
х0 = х0,
хг+1 = Л(х4,и4,у4), Ь = 0,1,...,Т.
к нормальной форме и применять принцип максимального гарантированного результата уже к ней. В данном разделе проанализируем первый способ. В остальных разделах будет рассмотрен второй способ.
Вернемс
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.