Управление и оптимизация / Novikov - Refleksiya i upravleniye 2013

ì

*

*

ïx1* =

2 - x2

- x13

,

ìx*

=

17

,

3

35

ï

ï 1

ï

2 - x*

- x*

ï

12

ïx2*

=

1

3

,

ïx2*

=

,

3

35

ï

ï

*

*

ï

17

ïx*

=

2 - x31

- x2

,

ïx*

=

,

3

35

ï

3

ï 3

í

1- x132* - x13*

í

1

ïx*

=

,

ïx31*

=

,

5

ï

31

3

ï

ï

1- x31* - x132*

ï

1

ïx*

=

,

ïx13*

=

,

5

ï

13

3

ï

ï

*

*

ï *

1

ïx*

=

1- x31

- x13

,

ïx132 =

.

5

ï

132

3

î

î

Таким образом, действия реальных агентов в ситуации инфор-

мационного равновесия

будут

следующими:

x1* = x3* = 17/35,

x2* = 12/35. ∙

Завершив описание графа рефлексивной игры, продолжим ис- следование свойств информационного равновесия.

2.5.РЕГУЛЯРНЫЕ СТРУКТУРЫ ИНФОРМИРОВАННОСТИ

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

Конечность информационной структуры по своему определению означает не конечность ее дерева, а существование конечного бази- са, в рамках которого рассмотрение фантомных агентов, имеющих ту же информированность, что и другие реальные или фантомные агенты, не дает новой информации и поэтому нецелесообразно.

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

71

однозначно сказать какой бесконечной информационной структуре оно соответствует. Другими словами, может существовать множест- во информационных структур, любое конечное число верхних уров- ней которых совпадает.

Поэтому для определения информационного равновесия по ко- нечному дереву представлений агентов необходимо введение допол- нительных предположений. Например, можно постулировать, что каждый фантомный агент, соответствующий нижнему уровню ко- нечного дерева представлений, при определении своего действия считает, что агент, соответствующий предыдущему уровню иерар- хии, адекватно информирован о нем (см. предположения Пm в [117]

исубъективные байесовы равновесия в [253]).

Внастоящем разделе рассматриваются регулярные структуры информированности, обладающие, в частности, тем свойством, что, если задано конечное дерево представлений и известно, что инфор- мационная структура регулярна, то информационное равновесие определяется однозначно. Кроме того, для регулярных структур информированности удается: получить конструктивные условия существования информационного равновесия, исследовать зависи- мость информационного равновесия от структуры информированно- сти (раздел 2.6), поставить и решить задачу рефлексивного управле- ния (раздел 2.11).

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

Пусть в игре участвуют n агентов. Если (в простейшем случае) все агенты одинаково информированы, то структура информирован- ности имеет сложность n и единичную глубину. Будем изображать эту ситуацию в виде дерева, состоящего из корневой вершины, n ребер и n висячих вершин. На Рис. 11 изображено такое дерево для случая трех агентов (здесь и далее будем для большей наглядности

72

отмечать в вершинах дерева вместо θ1 , θ2 , θ12 и т.д. просто 1, 2, 12 и

т.д.).

21

2

23

Рис. 11. Регулярное конечное дерево

Данному РКД соответствует граф рефлексивной игры, приве- денный на Рис. 12.

3

12 2

Рис. 12. Граф рефлексивной игры для РКД, приведенного на Рис. 11

Далее РКД может «расти» следующим образом: к каждой вися- чей вершине τi, τ Σ, присоединяется ровно (n – 1) ребро, при этом возникает (n – 1) висячая вершина τij, j = 1, …, i – 1, i + 1, …, n. Построенное РКД будем интерпретировать так: если имеется вися- чая вершина τi, τ Σ, то τi-агент одинаково информирован с τ- агентом (если τ – пустая последовательность, то τi-агент является реальным, и его субъективные представления совпадают с объектив- ными).

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

Начнем с РКД, изображенного на Рис. 13.

73

21

2

23

12 132

Рис. 13. Пример РКД глубины 2

Если θ12 = θ2 и θ13 = θ3, то опять получаем граф, приведенный на Рис. 13. Если же хотя бы одно из этих равенств нарушено, получает- ся граф рефлексивной игры, изображенный на Рис. 14.

2 32

1

12 132

Рис. 14. Граф рефлексивной игры для РКД, приведенного на Рис. 13

Следующий случай РКД изображен на Рис. 15.

	21	2	23
12	132	21	23

Рис. 15. Пример РКД глубины 2

74

Здесь возможны два варианта графов рефлексивной игры, не сводимых к предыдущим – см. Рис. 16 и Рис. 17.

		23
	1		2
12	132	21	23

Рис. 16. Граф рефлексивной игры для РКД, приведенного на Рис. 15

3

12 2

13

Рис. 17. Граф рефлексивной игры для РКД, приведенного на Рис. 15

Наконец, последний случай РКД изображен на Рис. 18.

	21		2		23
12	132	21	23	312	32

Рис. 18. Пример РКД глубины 2

75

Этому случаю соответствуют три варианта графов рефлексив- ной игры, не сводимых к предыдущим – см. Рис. 19, Рис. 20 и Рис. 21. Как видим, графы на рисунках Рис. 20 и Рис. 21 являются не- связными.

1

2

3

122

132

212

232

312

322

Рис. 19. Граф рефлексивной игры для РКД, приведенного на Рис. 18

1			3
2	132	312	322

Рис. 20. Граф рефлексивной игры для РКД, приведенного на Рис. 18

32

12 21

21

132

2

Рис. 21. Граф рефлексивной игры для РКД, приведенного на Рис. 18

Содержательная интерпретация каждой из семи возможных структур информированности глубины не более двух не вызывает

76

затруднений. Остановимся на трех симметричных структурах (см.

Рис. 12, Рис. 19 и Рис. 21).

Рис. 12 соответствует, как отмечалось выше, одинаковой ин- формированности агентов. Их рефлексивные реальности совпадают. Можно сказать, агенты играют в одну игру, правила которой явля- ются общим знанием.

Рис. 19 соответствует в некотором смысле противоположной ситуации. У агентов искаженные и попарно несогласованные пред- ставления друг о друге. Каждый из них считает, что все одинаково информированы, но все агенты заблуждаются. На самом деле каж- дый играет в свою игру.

Рис. 21 соответствует ситуации, когда каждый агент считает се- бя более информированным, чем остальные. Например: агенты провели переговоры, сообщив друг другу свои представления о неизвестном параметре, однако все трое скрыли свои истинные представления, считая при этом, что остальные двое были правдивы и поверили своим оппонентам. Возможна и несколько иная интер- претация того же Рис. 21: агенты заключили договор, но каждый собирается его нарушить, считая при этом, что оппоненты считают договор стабильным – не собираются его нарушать, не ждут этого от оппонентов и т.д.

Описанные в настоящем разделе свойства регулярных инфор-

мационных структур будут использованы ниже при исследовании задач рефлексивного управления (см. раздел 2.11).

Рассмотрим в заключение настоящего раздела вопрос о сущест-

вовании информационного равновесия для регулярных структур информированности.

Из построения РКД видно, что равновесные действия агентов (если они существуют) могут быть найдены «снизу вверх», то есть от висячих вершин к корню РКД. Пусть, например, для некоторого τ Σ+ висячими являются (n – 1) вершин τij, j N \ {i}. Тогда, по определению РКД, n агентов из множества {τij}, j N, являются одинаково информированными (напомним, что в силу аксиомы автоинформированности (см. раздел 2.2) мы отождествляем τi- и τii- агентов). Поэтому для их равновесных действий справедливы соот- ношения xτ*ijk = xτ*ik , j, k N,

(1) x*	Arg max	f	j	(θ	τij	, x*	,..., x*	, x	, x*	..., x*	) , j N.
τij	xτij X i					τi1	τi, j−1	τij	τi, j+1	τin

77

Отметим, что остальные агенты находятся «вне поля зрения» рассматриваемых нами n агентов {τij}, j N.

Система (1) является записью «обычного» равновесия Нэша в игре с общим знанием. Если она имеет решение, из нее, в частности, можно найти действие τi-агента.

Далее, рассмотрим вершину τ, τ Σ+, и вершины τm, m N \{ω (τ)}, (напомним, что ω (τ) – последний индекс в последо- вательности τ), среди которых находится и вершина τi. Все τm – агенты делятся на два множества: одинаково информированные с τ– агентом и прочие (к последним относится и τi-агент). Чтобы удобнее было их разделять, введем обозначение:

Nτ = {k N | Iτk ~ Iτ }.

Как мы видели, равновесное действие τi-агента (и, аналогично, действия всех τm-агентов, m Nτ ) определяется независимо от действия прочих τm-агентов, m N. Поэтому все τk-агенты, k Nτ ,

могут просто подставить действия xτ*m , m Nτ , в свои целевые функции. Таким образом, для вычисления равновесных действий

x*

, k

N

τ

надо решить систему уравнений

τk

(2)

x* = arg max

f

(θ

, x*

,..., x*

, x

, x*

..., x* ) , k

.

k

N

τ

τk

xτk X k

τk

τ 1

τ ,k −1

τk

τ ,k +1

τn

Система (2) является записью равновесия Нэша в игре τk-

агентов, k

.

Ее

решение

(если

оно

существует),

позволяет

Nτ

найти равновесное действие xτ* .

Двигаясь от висячих вершин к корню, можно последовательно найти все равновесные действия. Для этого все системы типа (1) и

(2) должны иметь решение. Таким образом, можно сформулировать

следующее достаточное условие существования информационного равновесия для регулярных структур информированности (множест- во реальных агентов N, их целевые функции {fi}, множества допус- тимых действий {Xi}, а также множество возможных значений Θ неопределенного параметра считаем фиксированными).

Утверждение 2.5.1. Пусть для любого непустого множества N N справедлив следующий факт: для любых θk Θ, k N , и

78

любых x*

Xm, m

N

,

существует равновесие Нэша в

игре с

m

общим знанием k-агентов,

то есть существуют x* , k

,

удовле-

N

k

творяющие

x*

Arg max f

(θ

, x*,..., x*

, x , x*

..., x* ) , k

.

k

k

N

k

xk X k

1

k −1

k k +1

n

Тогда для любой конечной структуры информированности сущест- вует информационное равновесие.

Имея язык описания информированности агентов (информаци- онную структуру – см. раздел 2.2), определение решения рефлексив- ной игры (информационное равновесие – см. раздел 2.3), а также свойства графа рефлексивной игры (раздел 2.4) и регулярных струк- тур информированности (настоящий раздел), мы имеем возможность перейти к исследованию влияния информированности агентов (и, в первую очередь, рангов их рефлексии) на информационное равнове- сие, и, следовательно, на их выигрыши, что, в свою очередь, далее (в разделе 2.11) позволит изучить задачи рефлексивного управления.

2.6. РАНГ РЕФЛЕКСИИ И ИНФОРМАЦИОННОЕ РАВНОВЕСИЕ

Напомним, что в разделе 1.2 было определено параметрическое равновесие Нэша, в котором вектор равновесных действий зависел от значения состояния природы, которое являлось общим знанием. В разделе 2.3 было введено понятие информационного равновесия как субъективного равновесия, зависящего от структуры информиро- ванности I = (I1, I2, …, In), где Ii – структура информированности i-го агента, i N.

Обозначим x*(I			) – множество субъективно равновесных дей-
ствий19 i-го	i	i		структуру информированности Ii,
	агента,		имеющего
i N, x*(Ii) – соответствующие				множество векторов субъективно
равновесных	действий. Введем			Ψi – множество всевозможных

19 Напомним, что под субъективно равновесным действием агента понимается соответствующая его информированности компонента информационного равнове- сия.

79

структур информированности i-го агента20, ψiki – множество всевоз-

можных конечных (глубины не более ki) структур информированно- сти i–го агента, i N. В соответствии с определением, приведенным выше, будем считать, что агент, имеющий конечную структуру

информированности глубины k, обладает рангом информацион-

ной рефлексии, равным k – 1. Если информационные структуры всех агентов конечны, то глубина γ(I) информационной структуры I

также конечна и равна

γ(I) = 1 + max {ki}.

i N

Определим множество

(1) Xi*(Ψ) = Uxi*(Ii ) ,

Ii Ψ

где Ψ Ψi, тех действий i-го агента, которые могут быть субъектив- но равновесными при условии, что его информационные структуры принадлежат множеству Ψ, i N, и множество субъективных равно-

весий при всевозможных информационных структурах из множества

Ψ:

(2) X*(Ψ) = Ux*(I ) .

IΨ

Так как при фиксированном множестве Θ возможных значений состояний природы выполнено ψiki ψiki +1 , ki , i N, то с уве-

личением глубины структуры информированности множество воз- можных субъективных равновесий не сужается.

Таким образом, известны зависимости (1) и (2) множеств потен-

циальных равновесий от множества возможных информационных структур. При бесконечных информационных структурах i-го агента Ii Ψi множество возможных субъективных равновесий составляет

X *(Ψi ) = Ux*(Ii ) , i N. Возникает вопрос – существует ли мно-

Ii Ψi

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

20 Так как элементами информационной структуры являются значения состояния природы, то множество всевозможных структур информированности зависит от множества Θ возможных значений состояния природы. Помня об этом, отражать зависимость в явном виде мы не будем.

80