, Поспелов играет без дирижера: размышления об эволюции некоторых технических систем и управлении ими (стр. 5 )

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

Рассмотрим некоторую условную ситуацию. Пусть у нас имеется водопроводная сеть, состоящая из рас­пределительных станций, соединенных между собой водоводами. Станция регулирует отпуск воды потре­бителям. Ее доход, с одной стороны, растет с увели­чением общего объема отпускаемой потребителям воды, но, с другой стороны, увеличение этого объема может привести к падению давления в магистралях, что вызовет определенные убытки и, следовательно, снижение дохода. При этом указанные зависимости определяются не только поведением самой станции, но и отбором воды из системы, осуществляемым бли­жайшими соседями станции. Аналогичные отношения возникают и в оросительных системах.

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

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

93

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

Рассмотрим простенький чис­ленный пример. Пусть участни­ки игры имеют по два соседа каждый, т. е. их графом взаимо­действия является окружность (рис; 3.14). Выигрыш каждого участника определяется его дей­ствием и действиями его правого и левого соседей. Каждый уча­стник может делать одно из двух действий, которые мы обозначим через А и Б. Величины выигрыша автомата в зависимости от дей­ствий его правого и левого соседей приведены ниже

Ситуация Выигрыш

ААА — 2

БАА 2

АБА 0

ББА 10

ААБ 10

БАБ 0

АББ 2

БББ —2

Отсюда видно, что среднему игроку выгодно изме­нять свое действие на другое, если он находится в си­туациях ААА, БАА, АББ и БББ, и невыгодно в ос­тальных ситуациях. Рассмотрим ситуацию ББАА, в которой третьему игроку выгодно изменить свое дей­ствие, что приводит нас к конфигурации БББА, в ко­торой становится выгодным изменить свое действие второму игроку. Ситуацией равновесия по Нэшу здесь является партия АБАБАБ... АБ. Средний выигрыш в партии Нэша для этой игры равен 0. С другой сто­роны, партия ААББААББ... ААББ обеспечивает средний выигрыш, равный 6, но, как мы видели, она неустойчива.

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

93

нию суммарного выигрыша в своей окрестности, а, значит, и во всем коллективе, становится для участ­ника невыгодным. Тогда и партия максимальной цены становится устойчивой по Нэшу, т. е. становится Таблица 3.2

Фрагмент партии Мора	Выигрыш	Фрагмент новой партии	Выигрыш
ААББА	22/3	АААБА	8/3
АББАА	14/3	АБААА	0
ББААБ	22/3	БББАБ	8/3
БААББ	14/3	БАБББ	0

партией Мора. Проиллюстрируем сказанное на нашем примере. Обратимся к табл. 3.2. В ней в первом столбце приведены фрагменты партии максимальной цены, во втором столбце — выигрыш среднего во фрагменте игрока при наличии локальной общей кас­сы, в третьем столбце—фрагмент, образующийся при смене действия средним игроком, и, в четвер­том — выигрыш среднего во фрагменте игрока при наличии локальной общей кассы в новой ситуации.

Из табл. 3.2 видно, что ни одному из участников игры при использовании процедуры локальной общей кассы в партии максимальной цены невыгодно изме­нять свое действие.

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

§ 3.5. «Он думает, что я думаю...»

У английского поэта Ковентри Патмора есть та­кие стихи:

— Он целовал Вас, кажется?

— Боюсь, что это так!

— Но как же Вы позволили?

94

— Ax, он такой чудак! Он думал, что уснула я И все во сне стерплю. Иль думал, что я думала, Что думал он: я сплю!

(перевод С. Маршака)

Эти стихи демонстрируют широко распространенную человеческую способность к рефлексии — рас-суждениям, при которых рассуждающий ставит себя на место другого человека и проводит рассуждения с его точки зрения. Рефлексивные рассуждения обла­дают свойством рекурсивности, т. е. как бы вклады­ваются друг в друга, как матрешки. Например, можно рассуждать о том, как некто рассуждает о вас или моделирует ваши рассуждения о нем. Ковентри Пат-мор в своем стихотворении прекрасно иллюстрирует эту рекурсивность рефлексивных рассуждении.

Зачем нам нужны рассуждения подобного типа? Мы их используем тогда, когда делаем выбор, успех и неуспех которого предопределяется не только на­шим собственным решением, но и решениями других людей, связанных с нами какими-то связями. Пример подобной ситуации—игра в размещения, в которой выигрыш каждого участника коллектива определяет­ся не только его индивидуальным действием, но и действиями остальных участников коллектива. По­этому использование в коллективном поведении ме­ханизмов, имитирующих рефлексивные рассуждения, может оказаться полезным. В данном параграфе мы постараемся показать это.

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

95

участниках коллектива и сигналах от среды; поступивших на их вход. Определение последующих ран­гов рефлексии происходит аналогичным образом. Ин­дивид или автомат имеет k-й ранг рефлексии, если он считает, что все остальные известные ему участ­ники коллектива имеют ранг рефлексии, равный k—1, и он может провести за них соответствующие рассуждения.

Такое определение ранга рефлексии связано лишь с мерой информированности системы, делающей вы­бор, о сигналах, поступивших на входы других си­стем. У человека же рефлексивные рассуждения в подавляющем большинстве случаев опираются на не­которые знания, хранящиеся в его «модели мира». Это знания о закономерностях поведения в данном обществе, человеческих возможностях в том или ином состоянии, нормах и ограничениях и т. п. Но даже в столь обедненном виде рефлексивные рас­суждения оказываются полез­ными в ряде моделей коллек­тивного поведения.

Рассмотрим следующую за­дачу. В дачном кооперативе пробурена скважина для по­дачи воды. На каждом участ­ке имеется свой собственный насос, способный подать воду из скважины в кольцевой коллектор, охватывающий все участки (рис. 3.15). Но мощ­ности этих насосов таковы. что создаваемый ими напор

в коллекторе позволяет производить поливку трех соседних участков, если включены два насоса. Другими словами, если на участках 2 и 3 насосы включены, то можно полить и посадки на участке 4. Каждый хозяин участка имеет индивиду­альную цель — обеспечить свой участок водой. Но имеется еще дачный трест — владелец всех n участ­ков, И у него есть собственная цель — экономия электроэнергии. При обеспечении поливки всех уча­стков для дачного треста невыгодно, чтобы работали все n насосов. Наилучшим для него является случай, когда работает только n/2 насосов (если п—четное), или (n+1)/2 насосов (если п—нечетное). Доста-

96

точно, например, включить насосы лишь на участках с четными (пли нечетными) номерами и весь полив будет обеспечен.

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

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

Перейдем теперь к описанию самой модели. Име­ется кольцо, состоящее из п автоматов (будем для определенности считать п четным). Каждый автомат может находиться в двух состояниях — рабочем и выключенном. Эти состояния мы для краткости бу­дем обозначать соответственно 1 и 0. Каждый авто­мат имеет информацию о своем состоянии и состоя­нии двух своих соседей. Число действий каждого ав­томата также равно двум. Эти действия есть просто сообщения о том, в каком состоянии находится в данный момент автомат. На каждом такте функцио­нирования автоматы получают на вход сигналы поощ­рения и наказания. При поощрении автомат сохраня­ет свое состояние, при наказании — меняет его. Взаимодействие автомата в кольце со средой (дач­ным трестом) определяется табл. 3.3.

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

97

Таблица 3.3

	Состояние		Вероятность наказания
собственное	левого соседа	правого соседа
0	0	0	1
0	0	1	0,5
0	1	0	0,5
0	1	1	0
1	0	0	0
1	0	1	0,5
1	1	0	0,5
1	1	1	1

состояния. Но в этом состоянии весь коллектив опять получит сигнал наказания, все автоматы перейдут в рабочее состояние, и цикл замкнется. Насосы на участках будут либо все включаться одновременно, либо бездействовать», а цель дачного треста так и не будет достигнута.

Введем теперь различные ранги рефлексии. Пусть, например, некоторый автомат имеет первый ранг реф­лексии. Тогда он делает свой выбор следующим обра­зом. Он анализирует переход, который должны совер­шить его соседи (а для этого, он должен иметь ин­формацию о соседях своих соседей), считая, что они обладают нулевым рангом рефлексии, т. е. при своем выборе руководствуются приведенной выше таблицей, а затем совершает переход на основании своего рас­суждения. При этом вероятность наказания для него задается уже не средой, а определяется им самим. Другими словами, кроме информации о состояниях, в которых находятся его непосредственные соседи и соседи его соседей, автомат с первым рангом рефлексии должен еще звать правый столбец табл. 3.3, Только при наличии этой дополнительной информа­ции он сможет провести правильное рефлексивное рассуждение. Для иллюстрации его рассмотрим си­туацию, показанную на рис. 3.16. Сначала наш авто­мат проводит рассуждения за левого соседа. Как сле­дует из таблицы, определяющей функционирование автомата с нулевым рангом рефлексии, левый сосед не может получить сигнал наказания и останется в своем состоянии 0. Правый же сосед с вероятностью 0,5 сменит свое состояние и с такой же вероятностью.

98

сохранит его. Что делать нашему автомату в подобной ситуации? Если правый сосед сменит свое состояние, то, сохранив свое состояние, наш автомат окажется в благоприятном положении. Если же этого на произойдет, то вероятность наказания, которая нависнет над ним, будет равна 0,5. Если же наш автомат сменит свое состояние, то либо он получит сигнал наказания с вероятнос­тью 1 (если правый сосед изменит свое состояние), либо с вероятностью 0,5 (если правый сосед со­хранит свое состояние). В любом случае автомату с первым рангом рефлексии лучше сохранить свое текущее состояние.

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

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

99

автоматами с рангом рефлексии выше нулевого. В этом случае прогноз их поведения не будет соответ­ствовать тому, что они на самом деле будут делать.

Можно поставить следующий вопрос: существуют ли такие распределения значений рангов рефлексии по коллективу автоматов, которые позволяли бы дач­ному тресту надеяться, что со временем коллектив придет к благоприятным состояниям (чередованию состояний 1—0—1—0 и т. д.). Моделирование этой задачи на ЭВМ показало, что коллектив выходит на этот глобальный оптимум не всегда, а лишь при оп­ределенных распределениях рангов рефлексии. Опти­мум по коллективу, например, всегда достигается, когда на кольце чередуются автоматы с нулевым и первым рангами рефлексии. Но он же достигается и не при столь регулярном их чередовании.

В конце § 3.4 мы рассмотрели модель, весьма близкую к той, которую мы сейчас проанализировали. В ней ситуацией равновесия оказывалась партия вида 1в обозначениях § 3.4 партия АБАБ... АБ). Это та партия, которая устраивает нас в задаче включения насосов. Но в ранее рассмотренной мо­дели выход игроков в эту точку обеспечивался за­данной на стр. 94 системой выигрышей. В нашем же случае такой системы выигрышей нет. И коллек­тив автоматов не обладает в этой партии точкой рав­новесия.

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

§ 3.6. Оптимисты и пессимисты в мире автоматов

Рассмотрим еще один способ введения неоднород­ности в коллектив автоматов, решающий некоторую задачу. Как всегда, начнем с некоторой содержатель­ной интерпретации задачи.

Пусть некто решил жениться. Но поскольку же­нитьба — шаг серьезный, то жених намеревается принять решение только после того, как он будет иметь некоторую информацию о своей будущей спут­нице жизни. Пусть для него жизненно важны две

100

вещи: наличие квартиры у его избранницы и умение ее готовить вкусные обеды. Такой меркантилизм не должен смущать читателя. Авторы книги вовсе не идеализируют героя этой истории, а может быть, и осуждают его за невнимание к вещам куда более серьезным, чем жилплощадь и пища. Но что подела­ешь. Иногда для наглядности приходится мириться с некоторыми недостатками героя примера. Степень информированности жениха об интересующих его предметах будем выражать следующим образом. Если квартира у избранницы есть, то Х1 = 1, в про­тивном случае Х1 = 0. Если же жених пока не обла­дает сведениями о наличии у своей избранницы от­дельной квартиры, то полагаем X1 = 0,5. Аналогично считаем, что умение готовить обеды приводит к Х2 = 1, неумение — к Х2 = 0, а значение Х2 = 0,5 свидетельствует об отсутствии у жениха необходимой информации. Введем еще переменную Y, которая бу­дет отражать решение жениха. Если он твердо решил жениться, то Y=1. Значение Y = 0 свидетельствует об его отказе от избранницы, а Y = 0,5, означает, что жених колеблется, не зная, что ему делать.

Составим отражающую эту ситуацию табл. 3.4. Она задает пять функций троичной логики, завися­щих от двух аргументов X1 и Х2. Наиболее проста из них функция Y1 Как видно из таблицы, Y1=min(X1,X2). В логике такую функцию принято называть конъюнкцией. Если жених использует для принятия своих решений эту функцию, то он согла­шается на брак только при условии выполнения двух своих требований: наличия квартиры и умения гото­вить вкусные обеды. Если хотя бы одно из этих усло­вий не выполнено, то он отказывается от брака. При наличии неопределенности в условиях, когда осталь­ные требования выполнены, или в условиях полной неопределенности (X1 = 0,5; X2 = 0,5) жених медлит с решением и не говорит ни да, ни нет. По-видимому, он ждет новой порции информации. Такое поведение жениха можно назвать объективным или бесстраст­ным.

Остальные функции в нашей таблице описывают способ принятия решений несколько иного типа. Функции Y2 и Yз отражают пессимистическую точку зрения. Жених такого типа всегда предполагает, что мир устроен не лучшим образом и всегда надо ждать

101

Таблица 3.4

X1	X2	Y1	Y2	Y3	Y4	Y5
0	0	0	0	0	0	0
0	0,5	0	0	0	0	0
0	1	0	0	0	0	0
0,5	0	0	0	0	0	0
0,5	0,5	0,5	0	0	0,5	1
0,5	1	0,5	0	0,5	1	1
1	0	0	0	0	0	0
1	0,5	0,5	0	0,5	1	1
1	1	1	1	1	1	1

от него подвоха. Поэтому он склонен интепретировать незнание как отрицательную оценку. Такой же­них — пример явного пессимиста. При этом, если он руководствуется функцией Y2, то его пессимизм до­стигает крайней степени. При наличии любой неопре­деленности происходит отказ от дальнейшего накоп­ления информации, и общение жениха с невестой прекращается. В случае функции Yз пессимизм не столь категоричен. Лишь в случае полной неопреде­ленности жених прекращает свои попытки устроить свою личную жизнь. При частичной неопределенно­сти он стремится продолжить сбор интересующей его информации.