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

второго			агента:		j0	= arg max minbij – при нулевом ранге;
						j J i I
j	k	= arg maxb			– при ранге k ≥ 1.
			j J	ik −1 j

Из утверждения 3.2.4 следует, что множество допустимых дей- ствий по выбору ранга конечно. Поэтому мы можем перейти из исходной игры к игре рангов стратегической рефлексии, в которой

стратегией агента является выбор ранга стратегической рефлексии

(см. Табл. 7).

Табл. 7. Ранги рефлексии и действия агентов

	Ранг k	0	1	…	R
	Действие	i0	i1	…	iR
	первого агента
	Действие	j0	j1	…	jR
	второго агента

Верхняя оценка количества возможных попарно-различных пар стратегий составляет |I| × |J| = m × n. Тогда исходную биматричную игру можно преобразовать в биматричную игру R × R.

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

В силу того, что ik I, jk J, все действия агентов в игре рангов соответствуют действиям в исходной игре. Следовательно, справед- ливым является следующее утверждение.

Утверждение 3.2.5. Матрица выигрышей в игре рангов является подматрицей матрицы исходной биматричной игры.

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

æ(2, 3)		(0, 0)	(3,	2)	ö
(пример 3.2.5): çç	(0, 0)	(4,4)	(0,	1)	÷÷ .
ç	(3, 2)	(1, 0)	(2, 3)		÷
è					ø

191

Чтобы построить матрицу игры рангов, проанализируем выбор агентов при том или ином ранге рефлексии – см. Табл. 8.

Табл. 8. Ранги рефлексии и действия агентов в примере 3.2.5

		Ранг k			0	1	2	3	4	…
		Действие
		первого			3	1	1	3	3	…
		агента
		Действие
		второго			3	3	1	1	3	…
		агента
Таким образом, матрица игры рангов выглядит следующим об-
æ(2, 3)			(3, 2)	ö
разом: ç				÷ . Нетрудно видеть, что равновесная пара выиг-
ç		(3, 2)	(2, 3)	÷
è				ø

рышей исходной игры (4, 4) исчезла при переходе к игре рангов. · Возникает вопрос: могут ли при переходе к игре рангов появ-

ляться новые равновесия (которых не было в исходной игре)? Ока- зывается, что это невозможно.

Утверждение 3.2.6. Для произвольной биматричной игры пере- ход к игре рангов не приводит к появлению новых равновесий.

Доказательство. Пусть, как и ранее, I – множество действий первого агента, J – множество действий второго агента. Пусть, да- лее, I ' Í I и J ' Í J – множества действий первого и второго агентов соответственно в игре рангов.

Рассмотрим пару действий (iu, jv), iu Î I ', jv Î J ', являющуюся равновесием игры рангов.

Покажем сначала, что наилучшим ответом второго игрока на действие первого iu в исходной игре является jv. Действительно, наилучший ответ на множестве J входит в J ' (по правилу построения игры рангов), поэтому наилучший ответ на множестве J ' такой же, как наилучший ответ на множестве J. Но, по определению равнове- сия, наилучший ответ на множестве J ' – это как раз jv.

Аналогично, наилучшим ответом первого игрока на стратегию второго jv в исходной игре является iu. Поэтому пара действий (iu, jv) является равновесием исходной игры.

192

В силу произвольности выбора равновесной пары получаем, что

любое равновесие игры рангов является равновесием исходной игры, т. е. новых равновесий не появится. ·

Итак, при переходе к игре рангов новые равновесия не появля- ются (утверждение 3.2.6), а существующие могут исчезать (пример 3.2.5). Относительно количества равновесий в игре рангов справед- ливо следующее утверждение (которое существенно использует условия (20) и (21)).

Утверждение 3.2.7. Если выполнены условия (20) и (21), то в игре рангов существует не более двух равновесий.

Доказательство. Пусть в игре рангов существует три различных

равновесия: (iu , jv ) , (iu' , jv' ) и (iu'' , jv'' ) . По утверждению 3.2.6			они
являются	равновесиями и в исходной игре.	Тогда в силу	(20)
iu ¹ iu' ¹ iu''	. Без ограничения общности	предположим,	что

u = max {u; u'; u''}. Поскольку в равновесии действие агента является наилучшим ответом на действие оппонента, справедливы соотноше-

ния: iu = iv+1 = iu+2 = iv+3 = iu+4 = … ; jv = ju+1 = jv+2 = …		Аналогичные
соотношения верны для iu' ,	iu'' . Следовательно, iu+1 = iu'	, iu+1 = iu'' . Но
тогда iu' = iu'' . Полученное	противоречие доказывает	утверждение

3.2.7. ·

Следует отметить, что в некоторых случаях любой исход игры рангов дает обоим игрокам лучший результат, чем равновесие. Приведем пример такой биматричной игры (пример 3.2.6):

æ(6, 10)		(0, 0)	(10, 6)	ö
ç	(0, 0)	(5, 5)	(0, 1)	÷	. Равновесие приводит к паре выигрышей
ç				÷
ç	(10, 6)	(1, 0)	(6, 10)	÷
è				ø

(5, 5), что хуже (для обоих агентов) любого из исходов игры рангов,

в которой удалены дублирующиеся стратегии: çæ(6, 10)		(10, 6)	÷ö	. ·
ç	(10, 6)	(6, 10)	÷
è			ø

193

3.3. ОГРАНИЧЕННОСТЬ РАНГА РЕФЛЕКСИИ

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

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

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

В качестве информационного ограничения возьмем общеприня- тое в психологии число Миллера – 7±2 [5, 239], отражающее макси- мальное число объектов (признаков, альтернатив и т.д.), которыми человек может одновременно оперировать.

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

ранга рефлексии оппонента и выбора соответствующих наилучших ответов.

Рассмотрим процесс принятия решений i-ым агентом, точнее – элементарный акт анализа им игровой ситуации. Он может рассуж-

49 Частные модели, рассматриваемые в рамках дескриптивного аспекта, приведены в четвертой главе настоящей работы.

194

дать следующим образом. «Предположим, что я намереваюсь вы- брать действие xi Xi, а оппонент (под оппонентом будем понимать множество всех агентов50, кроме i-го) – действие x-i X-i (нулевой ранг рефлексии). Тогда, если этот факт отражен оппонентом (первый ранг рефлексии), то он может выбрать BR-i(xi), а я – BRi(x-i). Если и этот факт отражен оппонентом (второй ранг рефлексии), то появля- ются возможности выбора соответственно BR-i(BRi(x-i)) и BRi(BR- i(xi))». Данная цепочка построения графа наилучших ответов может продолжаться и далее (до тех пор, пока не исчерпается все множест- во допустимых действий – см. разделы 2.6 и 3.2, или пока в цепочке не перестанут появляться новые действия – см. раздел 3.2), если не учитывать информационных ограничений. Если w – ранг рефлексии, то число действий (число реальных и фантомных агентов), которые

необходимо	принимать во внимание агенту		(при произвольных
xi Xi и x-i X-i),		равно 2 (w + 1), а число связей между ними –
(w + 1)! (при	этом	предполагается, что агент	считает оппонента

примерно таким же рациональным, каким и себя).

Если учесть информационные ограничения, то получим, что, должно выполняться либо 2 (w + 1) ≤ 7±2, либо (w + 1)! ≤ 7±2. Реше-

ние первого неравенства в целых положительных числах дает w {0; 1; 2; 3}, второго – w {0; 1; 2}. При числе Миллера равном 7

получаем, что максимальный (в силу информационных ограни-

чений) ранг стратегической рефлексии равен двум.

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

50 В настоящем разделе предполагается, что в многоэлементной системе каждый агент рассматривает всех оппонентов в качестве одного агента. Если отказаться от этого предположения и считать, что каждый агент анализирует возможное поведе- ние каждого из своих оппонентов, то оценки максимального ранга стратегической рефлексии лишь уменьшатся (ему придется рассматривать n реальных агентов и n! связей между ними, что превышает число Миллера уже в системе с четырьмя агентами и на рефлексию «не остается места»).

195

формацией и формирующейся при этом информационной структу- рой является перспективной задачей будущих исследований.

Рассмотрев в разделах 3.1-3.3 подходы к описанию стратегиче- ской рефлексии в играх двух лиц, перейдем к общему случаю – методу рефлексивных разбиений, позволяющему описывать страте-

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

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

3.4. РЕФЛЕКСИВНЫЕ СТРУКТУРЫ И РЕФЛЕКСИВНОЕ УПРАВЛЕНИЕ

Рефлексивные разбиения. В рамках гипотезы индикаторного поведения (см. раздел 1.3 и [90, 123]) неявно предполагается, что агент, выбирая свои действия в соответствии с процедурой (1.3.2), не задумывается о том, что и другие агенты действуют так же. Если бы он об этом задумался (осуществил рефлексию), то ему следовало бы искать, принимая решения в момент времени t, наилучший ответ на прогнозируемые им в рамках выражения (1.3.2) действия других агентов. Т. е. положение цели определялось бы уже не выражением (1.3.1), а следующим образом:

(1) wi( xt		) = arg max Fi(y,	xt	),
	−i	y 1	−i
где xt	определяется выражением (1.3.1). При этом можно полагать,
−i

что рефлексирующий агент первого ранга считает всех остальных нерефлексирующими, что соответствует существующей в теории принятия решений (см. разделы 3.1 и 3.2) традиции считать, что агент, имеющий некоторый ранг стратегической рефлексии, считает всех остальных имеющими ранг на единицу меньше его собственно- го. Другие возможные предположения о представлениях агентов о рангах рефлексии оппонентов обсуждаются ниже (например, можно считать, что интеллектуальные агенты одного ранга рефлексии разыгрывают равновесие Нэша [258] и т. д.).

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

196

термина «ранг рефлексии k» используются термины «step k player», «level k player», «k-level player», «smart k-player» [235, 258], см. также

обзор [109]). Для этого определим = {N0, …, Nm} – разбиение множества агентов N, где Ni – множество агентов i-го ранга рефлек-

сии, i = 0, m , m – максимальный ранг рефлексии, ni = |Ni|, i Î N,

m

åni = n. Разбиение называют рефлексивным разбиением [64].

i=0

Будем пока считать, что агент некоторого ранга рефлексии k достоверно знает множества (или долю – см. ниже) агентов всех более низких рангов k’ (где k’ < k – 1) и считает всех агентов своего и бóльших рангов (k’’ ³ k) имеющими ранг на единицу меньше себя (т. е. ранг k – 1). Этим отражается предположение, что агент не допускает существования агентов, имеющих такой же или более высокий ранг рефлексии, чем он сам. При этом агент может непра- вильно оценивать множества агентов k – 1-го, k-го и более высоких рангов рефлексии.

Пусть задан вектор x0 «начальных» действий агентов. Рассмот-

рим следующую динамическую модель рефлексивного принятия ими решений, параллельно помня при этом, что соответствующие выражения для одношаговой «игровой» модели могут быть получе- ны как частный случай, в котором решения принимаются однократ- но при γi1 ≡ 1, i Î N.

Нулевой ранг рефлексии. Будем считать, что агенты с нуле- вым рангом рефлексии (принадлежащие множеству N0) выбирают свои действия, считая, что действия остальных агентов будут такими же, что и в предыдущем периоде. Тогда из (1.3.1) следует, что

(2) xit = xit−1 + γit [wi( x−t−i1 ) – xit−1 ], i Î N0, t = 1, 2, … .

Если рефлексирующих агентов нет (N0 = N), то в итоге все аген-

ты пронаблюдают реализованную траекторию (x0, …, xt, …) векто-

ров действий агентов, определяемых (2).

Первый ранг рефлексии. Агент j, обладающий первым рангом рефлексии (j Î N1), считает всех остальных агентов обладающими нулевым рангом рефлексии и в соответствии с (2) «предсказывает»

их выбор. Поэтому его собственный выбор x1tj будет ориентирован

197

на наилучший ответ на ту обстановку, которая с его точки зрения должна сложиться:

(3) x1t =	x1t−1 + γ t			[wj( xt		) –	x1t−1 ], j N1.
j	j		j	− j			j
Для	агента			j N1		прогнозируемой		является	траектория
(x0, …, ( x1t ,		xt	), …), а		на		самом деле	реализуется	траектория
	j	− j

(x0, …, ( x1tj N1 , xit N0 ), …). Т. е. реализованная траектория может не

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

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

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

Второй ранг рефлексии. Будем считать, что каждый агент j, обладающий вторым рангом рефлексии (j N2), знает достоверно множество N0 и считает всех агентов из множества N1 N2 \ {j} обладающими первым рангом рефлексии (отметим, что в общем случае, когда имеются несколько агентов второго ранга рефлексии, данный агент ошибочно приписывает им первый ранг). В силу этого он может «прогнозировать» поведение всех своих оппонентов. По- этому его выбор будет наилучшим ответом на ту обстановку, кото- рая с его точки зрения должна сложиться:

(4) x2t =	x2t−1 + γ t [wj( xt			,	x1t		) –	x2t−1	], j N2.
j	j	j	i N0		l N1 N2 \{ j}			j
Для	агента	j N2		прогнозируемой				является		траектория
(x0, …, ( x2tj , x1lt N1 N2 \{ j} ,			xit N0		), …), а	на самом			деле	реализуется
траектория (x0, …, ( x2tj N2			,	x1lt N1 , xlt N0		), …).

198

k-й ранг рефлексии (k ≤ m). Поведение агентов k-го ранга реф-

лексии описывается аналогично рассмотренным выше трем случаям (нулевого, первого и второго рангов рефлексии) с учетом следую-

щей рефлексивной структуры агентов. Обозначим через jk – субъ- ективное рефлексивное разбиение – представления агента j, обла-

дающего k-м рангом рефлексии, о разбиении всех агентов на ранги рефлексии:

(5) jk = (N0, N1, …, Nk-2, Nk-1 Nk … Nm \ {j}, {j}, , …, ), j Nk .

k m – k – 1

Агент k-го ранга будет выбирать действия в соответствии с про-

цедурой

(6) xkt	= xkt−1	+ γ t	[wj( xt	, x1t	, …, x[k −1]t	) –
j	j	j	l N0	l N1	l Nk −1 Nk ... Nm /{ j}

– xktj−1 ], j Nk.

В «статическом» случае агент k-го ранга выберет действие

(7) xk* ( jk) = arg max Fj(y, x1			, x11	, …,
j	y 1	l N0	l N1

…, x[k −1]1 ), j Nk.

l Nk−1 Nk ... Nm /{ j}

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

но задается рефлексивным разбиением . Отметим, что рефлексив- ная структура (5), введенная в рамках рассмотрения стратегической рефлексии, в некотором смысле аналогична структуре информиро- ванности, используемой в моделях информационной рефлексии – см. раздел 2.2.

Вектор действий агентов

(7) x*( ) = { xk*j ( jk)} j Nk , k =0,m

называют рефлексивным равновесием игры Г = {N, Fi(×)i N, } [64, 109]. То есть, рефлексивное равновесие – совокупность действий агентов, являющихся наилучшими ответами на предполагаемые в рамках существующей рефлексивной структуры действия оппонен- тов. В силу введенных выше предположений о существовании и

единственности наилучших ответов рефлексивное равновесие всегда существует. Отметим, что рефлексивное равновесие достаточно

199

экзотично в том смысле, что в нем действия агентов в общем случае не являются наилучшими ответами на действия, выбираемые оппо- нентами.

Целенаправленно изменяя рефлексивное разбиение, можно ме- нять действия агентов, т. е. осуществлять рефлексивное управление.

Вспомним, что при определении рефлексивного равновесия бы- ли введены следующие предположения:

–вектор x0 начальных действий агентов фиксирован и является общим знанием;

–агент ранга k имеет правильные представления о рангах реф- лексии всех агентов, имеющих ранг, меньший его собственного;

–агент ранга k считает всех агентов своего и более высоких рангов имеющими ранг k – 1.

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

Приведенная в настоящем подразделе общая модель рефлексив-

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

модели транспортных потоков и примеры из других прикладных областей в разделе 4.26.

Классификации моделей стратегической рефлексии. Обо-

значим через nijl представления агента i, обладающего j-м рангом рефлексии, о ранге рефлексии l-го агента. Для случая однородных

агентов обозначим через qijk представления i-го агента j-го ранга рефлексии о доле агентов, имеющих ранг k, qk = nk / n – «истинная» доля агентов k-го ранга.

Общий постулат, принимаемый практически во всех моделях рефлексивного коллективного поведения: агент некоторого ранга

200