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

73

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

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

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

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

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

Пусть а1 и а2 (а2=1—а1) — доли автоматов, вы­бравших в некоторой партии игры первую и вторую стратегии соответственно. Пусть P1 и P2 —вероят-

74

ности единичного выигрыша, равного для нашего примера 400 руб., и, значит, (1—p1) и (1—p2) — вероятности единичного проигрыша той же суммы. Тогда функции, задающие игру, определяют математическое ожидание единичного выигрыша при

p1==1—0,25а12 и p2==0,85—0,05а2.

При а1==0,8 и а2==0,2 автоматы, выбравшие первую стратегию, будут выигрывать с вероятностью 0,84 и проигрывать с вероятностью 0,16. Если, как мы пред­положили, единичные выигрыши и проигрыши равны :±400 руб., то математическое ожидание выигрыша на первой стратегии будет равно (0,84—0,16)*400=272 руб., что совпадает с выигрышем в точке Нэша.

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

(1 —p1)a1 = (1 —p2)a2 или 0,25а13 =(0,15+0,05а2)а2.

Решением этого уравнения служит а1=0,63 и а2==0,37. При этом в каждый момент времени 0,63 всех автоматов будет изменять свою стратегию с пер­вой па вторую и столько же автоматов будет перехо-дить со второй стратегии на первую.

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

75

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

первую стратегию в партии максимальной цены. Пусть ан> >аА>ам, что, кста­ти, имеет место в нашем примере, где ан= =0,8, аА==0,63, ам= =0,51. Тогда с ростом глубины памяти рас­пределение автоматов по стратегиям будет удаляться от партии максимальной цены к

партии Нэша и средний выигрыш автоматов будет падать. Действительно, в нашем примере средний выигрыш автоматов в партии Антоса равен 299,28 руб., а в партии Нэша — 272 руб. На рис. 3.7, 3.8, 3,9 приведены типы зависимости среднего выиг­рыша от глубины памяти автоматов при различных типах взаимного расположения точек, соответствую­щих партиям игры,

76

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

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

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

77

Антоса совпадет с точкой, отвечающей партии мак­симальной цены, и вероятности выигрыша будут равны

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

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

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

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

78

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

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

Во-первых, оно показывает, что выводы, которые делаются на основании рассмотрения средних вели­чин, не всегда справедливы — при таком анализе средних величин в игре Гура автоматы всегда долж­ны разыгрывать партию Антоса.

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

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

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

В заключение данного параграфа заметим, что если в игре Гура средний выигрыш возрастает с

79

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

§ 3.3. Распределение ограниченного ресурса

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

В предыдущих параграфах данной главы мы рас­смотрели две игры — игру в размещения и игру в распределения (игру Гура). В обеих играх эффек­тивность функционирования системы зависела от рас­пределения ограниченного числа участников игры по стратегиям. В качестве примера мы говорили о рас­пределении трудового ресурса по местам работы. Ресурсом в этих задачах могли служить объекты са­мой различной природы, например, задания, вы­полняемые в многопроцессорной вычислительной система. Существенным здесь было то, что мы

80

«персонифицировали» типы ресурса - и занимались организацией их коллективного поведения.

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

Задача об оптимальном распределении ресурса между потребителями имеет смысл только тогда, когда этот ресурс ограничен. В качестве ресурса мо­гут выступать самые различные объекты: деньги, энергия, сырье, машины ч т. п. Существенно здесь то обстоятельство, что каждый потребитель, используя некоторое количество ресурса, добивается определен­ного эффекта. Для того чтобы задача о распределе­нии ресурса имела смысл, необходимо также, чтобы в пределах всей системы эти эффекты были соизме­римы. Поиск такой общей меры является самостоя­тельной задачей и в ряде случаев (если не в боль­шинстве), не привносится в систему «сверху», а так­же порождается совмест­ным функционированием подсистем. Здесь, однако, мы будем предполагать, что такая мера существует.

Рассмотрим несколько примеров. Пусть у нас име­ется система, состоящая из k объектов и одного обслу­живающего устройства (рис. 3.10). Обслуживающее ус­тройство периодически с периодом длительности Т через коммутатор подклю­чается к каждому обслу­живаемому объекту и работает с ним в течение

времени tk. При этом очевидно, что Сумма( tk )=Т. Дли­тельность периода Т выступает здесь в качестве огра­ниченного ресурса, распределяемого между объекта­ми обслуживания. На каждом объекте в результате обслуживания его в течение времени tk достигается эффект, равный Фиk(tk). Заметим опять, что все эф­фекты соизмеримы, т. е. измерены в одних и тех же

81

единицах. При этом могут существовать различные системные критерии качества функционирования.

Предположим, что в качестве объектов выступают следящие устройства с импульсным регулированием через один и тот же регулятор (обслуживающее устройство). Качество функционирования каждого сле­дящего устройства, зависящее при заданном периоде от скважности сигналов регулятора, определяется, например, среднеквадратичным отклонением от от­слеживаемой величины. Поведение системы опреде­ляется среднеквадратичным отклонением наихудшего устройства. В этом случае наилучшее поведение си­стемы получается при достижении min max Фиk(tk). Нетрудно понять, что этот критерий удовлетворяется в том случае, когда среднеквадратичные ошибки во всех устройствах одинаковы. Действительно, если при определенном распределении времен обслужива­ния в течение периода в одном из каналов слежения ошибка больше, чем в других, то имеет смысл увели­чить время обслуживания этого следящего устрой­ства путем некоторого увеличения ошибки в других каналах. Здесь мы исключаем из рассмотрения такие экзотические случаи, когда распределение времен об­служивания, обеспечивающее равные ошибки во всех следящих устройствах, вообще недостижимо. Для это­го. достаточно предположить, что ошибки в этих уст­ройствах монотонно уменьшаются при уменьшении скважности регулирования. Оптимальное распределе­ние ресурса в таком случае определяется решением системы уравнений

Фиk(tk) - Лямбда = 0, (k=1, k); Сумма (tk) = T.

В качестве общесистемного критерия может выступать и просто арифметическая сумма эффектов, которые возникают у потребителей ресурса, как, на­пример, было с лесозаготовительными участками в приведенном выше примере (см. § 3.2). В системе, структура которой изображена на рис. 3.10, такой эффект функционирования системы может опреде­ляться суммарным достигаемым эффектом и поведени­ем системы, обеспечивающем приближение к Сумма[Фиk(tk)]. В этом случае, как следует из теории нелинейного программирования, оптимальное распределение до­стигается в ситуации,. определяемой решением систе-

82

мы уравнений

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

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

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

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

Теперь возникает естественный вопрос — существуют ли локальные правила формирования заявок на

83

ресурс при описанном способе его распределения, обеспечивающие оптимизацию поведения системы по общесистемному критерию?

Рассмотрим задачу с минимаксным критерием. Допустим вначале, что центральное устройство на­значает величину л и сообщает ее всем потребителям ресурса, а потребители ресурса указывают свои за­явки на ресурс так, чтобы сделать получаемый ло­кальный эффект равным Лямбда. Тогда, если у потребителя эффект меньше Лямбда, он увеличивает заявку, а если больше — уменьшает ее. Если все потребители уменьшают свои заявки, то это означает, что Лямбда мень­ше, чем необходимо, а если увеличивают, то Лямбда боль­ше, чем необходимо. В связи с этим центр ведет себя следующим образом: уменьшает Лямбда, если сумма заявок меньше наличного количества ресурса, и увеличива­ет Лямюда, если наличное количество ресурса меньше сум­мы заявок на него. В ситуации, когда все эффекты равны Лямбда и сумма запрошенного ресурса равна налич­ному его количеству, система находится в устойчивом равновесии. Заметим, однако, что мы нарушили анон­сированный выше принцип — центральное устройство занимается регулированием значения Лямбда. Кроме того, центральное устройство должно сообщать потреби­телям текущее значение Лямбда. С другой стороны, если весь ресурс распределяется пропорционально подан­ным заявкам, то количество выделяемого потребите­лю ресурса несет информацию о соотношении суммы запросов и наличного запаса ресурса. Этой информа­цией можно воспользоваться и находить свои запро­сы на шаге (Тау + 1) следующим образом:

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

Коэффициент Альфа определяет «чувствительность» потребителя, т. е. степень его инерционности. В этом смысле он некоторым образом аналогичен глубине Памяти автоматов в рассмотренных выше моделях поведения. Точность достижения оптимума растет с

84

уменьшением Альфа, но при этом падает способность опе­ративно реагировать на изменение условий функцио­нирования.

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

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

§ 3.4. Что дает случайное взаимодействие

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

85

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

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

Какие же типы взаимодействия мы можем отне­сти к простейшим? К таким типам с нашей точки зрения следует отнести случайное парное взаимодей­ствие и однородное взаимодействие с ограниченным числом соседей.

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

При взаимодействии с ограниченным числом сосе­дей для каждого члена коллектива указывается его окрестность — список участников игры, называемых соседями данного автомата по игре, с которыми он

86

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

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

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

Нетрудно видеть, что и в игре в распределения, если мы зададим некоторое начальное распределение игроков по стратегиям и организуем случайный пар­ный обмен стратегиями (первый тип взаимодействия).

87

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

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

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

Мы уже говорили выше, что в игре Гура чрезвы­чайно медленная сходимость объясняется тем, что при любой глубине памяти точкой динамического рав­новесия является точка, при которой автоматы рав­номерно распределены по стратегиям. Более того, в любой другой партии опять-таки при любой глубине памяти математическое ожидание изменения распре­деления автоматов по стратегиям направлено в сто­рону точки равномерного распределения. Можно предложить сравнительно простую процедуру случай­ного парного взаимодействия (взаимодействие второ-

88

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

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

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

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

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

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

Действительно, если читатель согласен не забивать себе голову аналитическими выкладками и готов поверить нам на слово, то оказывается, что в «игре в распределения» случайное парное взаимодействие, состоящее в том, что в случае смены действия в каче­стве нового действия выбирается действие партнера по паре, обеспечивает выход простейших автоматов на партию Нэша. Этот факт также замечателен, тах как без взаимодействия для обеспечения выхода на точку Нэша необходимы автоматы с бесконечно боль­шой глубиной памяти. Резкое снижение требуемого объема памяти играющих автоматов столь же суще­ственно снижает время, необходимое для выхода на стационарное распределение, и значительно улучшает характеристики поведения в случае изменения внеш­них условий. На рис. 3.11, 3.12 и 3.13 (на них 1 — случайное парное взаимодействие, 2—общая касса, 3—обычная игра) приведены зависимости среднего выигрыша автоматов от глубины их памяти при ком­бинированном способе случайного парного взаимодей­ствия для игр, рассмотренных на рис. 3.7, 3.8 и 3.9.

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

В качестве примеров управляющих систем с сетевой структурой могут выступать также системы

91

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