Тема 7. Лекция 15. Иерархические игры.

С точки зрения управления наиболее адекватными являются игры, в которых игроки принимают решения не одновременно, а последовательно, т.е., если мы говорим, что есть управляющий орган – центр – и управляемые субъекты (агенты), то сначала центр определяет правила игры, а дальше агенты принимают решения, исходя из этих правил. Такие игры называются иерархическими. По определению, иерархическая игра – игра с фиксированной последовательностью ходов.

Простейшая иерархическая игра – такая, в которой есть первый игрок – центр, второй игрок – агент (см. Рис. 2.2).

Рис. 2.2. Базовая структура «центр-агент»

Для иерархических игр характерно использование максимального гарантированного результата (МГР) в качестве базовой концепции решения игры. При этом «пессимистичность» МГР (взятие минимума по множеству неопределенных параметров) компенсируется возможностью передачи информации между игроками, что, очевидно, снижает неопределенность при принятии решения.

Критерии эффективности (целевые функции) первого и второго игроков обозначим[2] и соответственно. Выигрыши игроков зависят от их действий x₁ и x₂ из множеств действий , .С одной стороны, получается игра двух лиц в нормальной форме, поэтому, если не введено условие последовательности выбора стратегий, то возможно достижение равновесия по Нэшу и т.п.

Во всех моделях иерархических игр считается, что первый игрок (центр) имеет право первого хода. Его ход состоит в выборе стратегии . Понятие стратегии существенно отличается от понятия действия и тесно связано с информированностью первого игрока о поведении второго игрока – агента. Под стратегией игрока здесь и далее понимается правило его поведения, то есть правило выбора конкретного действия в зависимости от содержания и конкретного значения той информации, которую он получит в процессе игры. Выбирать же собственно действие центр может и после выбора действия агентом.

Самая простая стратегия центра состоит в выборе непосредственно действия x₁ (если поступления дополнительной информации о действии агента в процессе игры не ожидается), более сложная – в выборе функции (если в процессе игры ожидается информация о действии агента). Также стратегия центра может состоять в сообщении агенту некоторой информации, например, о планах своего поведения в зависимости от выбора агентом действия. При этом агент должен быть уверен, что первый игрок может реализовать эту стратегию, то есть что первый игрок будет точно знать реализацию действия x₂ на момент выбора своего действия x₁.

Например, если агент (выбирающий стратегию вторым) не ожидает информации о действии центра, то реализация права первого хода центра может состоять в сообщении центром агенту функции . Такое сообщение может рассматриваться, как обещание выбрать действие при выборе агентом действия x₂. Тогда стратегия агента состоит в выборе действия в зависимости от сообщения центра, . Если при этом агент доверяет сообщению центра, он должен выбрать действие , реализующее

.

Игра с описанным выше порядком функционирования называется для краткости игрой Г₂ (примером такой игры служит, как раз, задача стимулирования в условиях информированности центра о действии агента – см. ниже).

Если центр не ожидает информации о действии агента, и это известно агенту, то стратегия центра состоит, как уже было сказано, просто из выбора некоторого действия . Стратегия агента состоит в выборе (он делает ход вторым, уже зная действие центра). Такая игра называется игрой Г₁ (это, например, та же задача стимулирования, но уже в условиях отсутствия у центра информации о действии агента).

Рассмотрим сначала игру Г₁. Пара действий в игре Г₁ называется равновесием Штакельберга, если

(1) ,

(2) ,

то есть – функция наилучшего ответа агента на действие центра.

Равновесие в игре Г₁ отличается от равновесия Штакельберга (1) тем, что при определении оптимальной стратегии первого игрока вычисляется минимум по множеству :

(3) .

Пример. Рассмотрим Пример 2.1, в котором

f₁(x₁, x₂) = a x₁– x₁ x₂, f₂(x₁, x₂) = x₁ x₂ – (x₂)² / 2 r.

Содержательно, центр по тем или иным причинам заинтересован (a > 0 – известная константа) в завышении цены x₁ Î = [0; +¥), но, в то же время, он выбирает цену, по которой он готов приобрести продукцию, производимую агентом, и сообщает эту цену агенту, после чего агент принимает решение об объеме выпуска x₂.

При отсутствии технологических ограничений ( = [0; +¥)) максимум функции f₂(x₁, x₂) по x₂ достигается при выборе агентом действия = x₁ r (отметим, что в рассматриваемом примере множество состоит из единственной точки , поэтому равновесия (1) и (3) совпадают).

Находим = arg f₁(x₁, ) = a / 2 r, после чего вычисляем = a / 2. ·

В игре Г₁ агент выбирает действие в условиях полной информированности, уже зная действие центра. Максимизация выигрыша выбором своего действия является здесь частным случаем применения принципа МГР. Равновесное по Штакельбергу действие центра также дает ему гарантированный результат, если центр уверен в том, что агент выбирает свое действие в соответствии с (2) и принципом благожелательности. Таким образом, равновесные стратегии как центра, так и агента, являются для них и гарантирующими.

Однако ситуация, когда первый ход дает преимущество, все же более типична. Тогда, если порядок ходов определяется самими игроками, между ними возникает борьба за лидерство. Игре двух лиц в нормальной форме можно поставить в соответствие две игры Г₁ (игры первого порядка), отличающиеся последовательностью ходов. Тогда борьба за лидерство (первый ход) определяется выгодностью перехода от исходной игры к какой-либо из иерархических игр первого порядка. Известно [8], что, если в игре двух лиц имеются хотя бы два различных оптимальных по Парето равновесия Нэша, то в этой игре имеет место борьба за первый ход.

Тем не менее, во многих случаях соответствующее игре Г₁ поведение центра нельзя назвать эффективным. Поэтому, когда центр наблюдает действие агента, он заинтересован сообщить агенту о своих планах по выбору действия в зависимости от действия агента, реализуя тем самым игру Г₂.

Приведем формулировку теоремы о максимальном гарантированном результате центра в игре типа Г₂. К этой игре сводятся многие модели управления, например, задача стимулирования в условиях полной информированности (см. ниже). Определим необходимые для формулировки теоремы понятия.

Целевые функции игроков: , непрерывны на компактных множествах допустимых действий.

Стратегия центра – , то есть предполагается следующий порядок функционирования: игрок 1 (центр), обладая правом первого хода, сообщает игроку 2 (агенту) план выбора своей стратегии в зависимости от выбранной игроком 2 стратегии x₂. После этого второй игрок выбирает действие x₂, максимизируя свою целевую функцию с подставленной туда стратегией первого игрока, а затем первый игрок – действие .

Стратегия наказания определяется из условия

Если стратегий наказания несколько, то будем называть оптимальной стратегией наказания ту из них, на которой достигается максимум выигрыша первого игрока.

Гарантированный результат второго игрока (при использовании первым игроком стратегии наказания) равен

Множество действий второго игрока, обеспечивающих ему максимальный выигрыш при использовании первым игроком стратегии наказания есть E₂ = {x₂ | =L₂}.

Множество достижимости – это договорное множество рассматриваемой игры, то есть множество сочетаний стратегий первого и второго игроков, которые гарантировали бы второму результат, строго больший того, что тот может получить даже при наихудших для него действиях первого игрока (то есть при использовании первым игроком стратегии наказания).

Наилучший результат первого игрока на множестве достижимости есть . Принадлежность ситуации множеству достижимости гарантирует реализуемость этого результата путем использования стратегии наказания.

Определим действие первого игрока, дающее ему выигрыш при выборе вторым игроком рекомендуемого действия из D:

, .

Вычислим – гарантированный результат центра при применении им стратегии наказания (так как стратегии второго игрока ограничены множеством E₂).

Определим стратегию , которая реализует (с точностью до e) наилучший ответ центра на действие x₂ агента (e-доминантная стратегия), то есть

.

Теорема Ю.Б. Гермейера [6]. В игре Г₂ наибольший гарантированный результат центра равен . При K > M e-оптимальная стратегия центра . При K £ M оптимальная стратегия центра заключается в применении оптимальной стратегии наказания.

Каким же образом соотносятся выигрыши центра в играх Г₁ и Г₂ с одинаковыми функциями выигрыша? Существуют ли более рациональные для центра методы обмена информацией, дающие ему больший выигрыш? Ответ на эти вопросы дает рассмотрение информационных расширений игры, или метаигр.

Если центр не планирует самостоятельно получить информацию о действии агента, он может первым выбрать действие, реализуя игру Г₁. Однако ему можно порекомендовать и более сложное поведение. Центр может попросить агента сообщить ему свою стратегию , которая основана на ожидаемой агентом информации о действии центра. Реализация права первого хода центром состоит в этом случае в сообщении агенту стратегии . Эту стратегию можно интерпретировать, как обещание центра выбрать действие при условии, что агент обещает выбирать свое действие в соответствии с . Так образуется игра Г₃.

Если центр определяет порядок обмена информацией, он может выбирать, играть ему Г₁ или Г₃. В обеих играх центр вынужден выбирать действие, не зная действия, выбранного агентом. Можно считать Г₃, в некотором роде, усложнением игры Г₁.

Аналогично тому, как, с помощью образования дополнительной «петли обратной связи», из Г₁ была образована Г₃, можно усложнить и игру Г₂. Так образуется игра Г₄. В ней агент, ожидая от центра, как и в Г₂, информацию вида , формирует и сообщает центру свою стратегию . Центр, обладающий правом первого хода, пользуется стратегиями , которые определяют, какую функцию выберет центр в зависимости от сообщения агента .

Таким же способом можно на основе Г₃ построить игру Г₅, и так далее. В каждой из построенных четных игр Г_2m, m = 1, 2, …, центр использует в качестве стратегий отображения множества стратегий агента в этой игре на множество стратегий центра в игре Г_2m-2. Аналогично, стратегиями агента являются отображения множества стратегий центра в Г_2m на множество стратегий агента в игре Г_2m-2.

Такую рефлексию можно было бы наращивать бесконечно, переходя к все более сложным схемам обмена информацией, если бы рассмотрение этих игр увеличивало выигрыш центра (в интересах которого и проводится исследование всех метаигр). Однако имеет место следующий результат.

Теорема Н.С. Кукушкина. Максимальный гарантированный результат центра в игре Г_2m при m > 1 равен максимальному гарантированному результату центра в игре Г₂. В играх же Г_2m+1 при m > 1 максимальный гарантированный результат центра равен его максимальному гарантированному результату в игре Г₃.

Таким образом, при исследовании гарантированного результата центра можно ограничиться только играми Г₁, Г₂ и Г₃. Кроме того, известно [20, 34], что максимальный гарантированный результат центра в игре Г₂ не меньше его гарантированного результата в игре Г₃, а тот, в свою очередь, не меньше гарантированного выигрыша в игре Г₁. Этот факт показывает, что Г₂ является «идеальной» игрой для центра. Соответственно, если центр имеет возможность определять порядок и содержание обмена информацией, и, кроме того, при выборе своего действия знает действие, выбранное агентом, он должен играть Г₂. Если центр на момент выбора своего действия не знает действия агента – ему наиболее выгодна игра Г₃.

Темы, вопросы, упражнения, задачи практических занятий.