Автоматика и телемеханика, № 7, 2021

Обзоры

А.К. ЕНАЛЕЕВ, канд. техн. наук (anverena@mail.ru),

Н.А. КОРГИН, д-р техн. наук (nkorgin@ipu.ru)

(Институт проблем управления им. В.А. Трапезникова РАН, Москва)

СОГЛАСОВАННОСТЬ И НЕМАНИПУЛИРУЕМОСТЬ

МЕХАНИЗМОВ ОРГАНИЗАЦИОННОГО УПРАВЛЕНИЯ:

ТЕКУЩЕЕ СОСТОЯНИЕ ПРОБЛЕМЫ, РЕТРОСПЕКТИВА,

ПЕРСПЕКТИВЫ РАЗВИТИЯ ТЕОРЕТИЧЕСКИХ ИССЛЕДОВАНИЙ¹

Описываются предпосылки появления такой ключевой для теории ак-

тивных систем и теории механизмов (mechanism design), концепции, как

проблема согласованности или совместимости со стимулами (incentive

compatibility), проводится обзор подходов к решению данной проблемы,

приведших к формулировке принципов открытого управления и откро-

венности (revelation principle), а также актуальных направлений развития

данной отрасли научного знания; обсуждаются потенциальные сложно-

сти и перспективы развития.

Ключевые слова: активные системы, дизайн механизмов, согласован-

ность, совместимость со стимулами, принцип открытого управления,

принцип откровенности, неманипулируемость, активное планирование.

DOI: 10.31857/S0005231021070023

1. Введение

В 2020 г. исполнилось 50 лет с момента появления в журнале ¾Автоматика

и телемеханика¿ публикации [1], в которой В.Н. Бурков и А.Я. Лернер пред-

ложили подход к формированию оптимальных планов хозяйственной систе-

мы таким образом, чтобы плановые задания оказались оптимальными также

и для отдельных подсистем. Свой подход они назвали принципом открыто-

го управления (ОУ). Суть подхода была очень проста: при решении задачи

планирования планирующий орган должен учитывать поступающую от под-

чиненных систем информацию об их предпочтениях, выбирая для них пла-

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

взаимовыгодные планы. Сформулированный ими подход и его формализация

были реакцией на предложения академика В.С. Немчинова об актуальности

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

ми системами, высказанные им в [2] в 1964 г. В.Н. Бурковым и А.Я. Лернером

было показано, что, если планы выбираются в соответствии с ОУ, то для ни-

жестоящих систем (для которых был предложен термин активный элемент)

действительно выгодно сообщать достоверную информацию о своих предпо-

чтениях.

От этой работы ведет отсчет история краеугольных понятий в теории ак-

тивных систем (ТАС) согласованности и достоверности сообщаемой ин-

формации.

¹ Исследование выполнено при финансовой поддержке РФФИ в рамках научного про-

екта №19-17-50190.

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

время международных исследований, инициированных в 50-60 годы прошло-

го века известными экономистами того времени, такими как Поль Самуэль-

сон [3], Якоб Маршак [4], Кеннет Эрроу [5], и специалистами по теории игр,

в первую очередь, Леонидом Гурвичем [6]. Уже в 1971 г. работа [1] должна

была быть представлена на международной конференции по теории диффе-

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

мент специалисты в области теории игр, как Гарольд Кунн и др. И кто знает,

каким было бы дальнейшее развитие теории активных систем, если бы этот

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

А.Я. Лернера переехать с семьей в Израиль, повлекшим за собой его уволь-

нение из Института проблем управления и потерю возможности заниматься

регулярной научной деятельностью [7]. Тем не менее доклад был опублико-

ван в сборнике трудов конференции [8]. Но эта статья оказалась последней

англоязычной публикацией по данному направлению на достаточно длитель-

ный период, за исключением ряда докладов на международных конгрессах

IFAC, например [9].

Проблем согласования интересов в хозяйственной системе Советского

Союза оказалось более чем достаточно, и внутри страны ТАС стала довольно

быстро развиваться, превратившись в крупное научное направление, знако-

мое многим читателям журнала ¾Автоматика и телемеханика¿ в настоящее

время также как теория управления организационными системами (ТУОС),

систематически исследующее математические модели взаимодействия рацио-

нальных или ограниченно рациональных агентов в условиях асимметричной

информации и нетривиального регламента их взаимодействия.

В настоящей обзорной статье акцентируется внимание на предпосылках

появления такой ключевой концепции, как проблема совместимости со стиму-

лами (incentive compatibility), или согласованности в задачах планирования,

перечисляются подходы к решению данной проблемы, приведшие к форму-

лировке принципов открытого управления и откровенности (revelation prin-

ciple).

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

ных исследований в ТАC, предоставляемого на регулярной основе в рамках

одноименной конференции [10], или общего позиционирования ТАС относи-

тельно смежных научных направлений, см. [11].

Вне фокуса внимания данной статьи останется (в значительной мере) дру-

гой краеугольный камень фундамента ТАС механизмы стимулирования и

сопоставление результатов в этой области с близким научным направлени-

ем теорией контрактов, см., например, [12], достаточно исчерпывающий

обзор по данной проблематике представлен в [13].

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

Для структуризации и унификации подачи материала в разделе 2 будет

описана модель активного планирования, предложенная в [14], на базе

которой в разделе 3 будет показано, что, стартуя изначально с разных пред-

посылок в различных постановках задач, отечественные и западные исследо-

ватели пришли к схожим техникам решения поставленных задач. В частности

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

ются на применение абсолютно идентичной техники исследование игр, по-

рождаемых разными механизмами управления, и предъявление эквивалент-

ности значения критерия эффективности в тех равновесиях, которые могут

быть обнаружены в этих играх. А ограничения применимости результатов

об оптимальности неманипулируемых механизмов, трактуемые несколько по-

разному в отечественной и западной литературе, определяются ключевыми

приемами данной техники эквивалентности.

Отталкиваясь от ретроспективной части обзора, в разделе 4 авторы сфор-

мулируют свое понимание текущего состояния исследований проблемы со-

гласованности и неманипулируемости механизмов организационного управ-

ления, выделят наиболее актуальные направления развития данной отрасли

научного знания, обсудят потенциальные сложности.

В разделе 5 проводится критический анализ современного состояния тео-

ретических исследований в области решения проблемы совместимости со сти-

мулами и неманипулируемости механизмов принятия коллективных решений

на основе ряда обзорных и постановочных статей, авторами которых явля-

ются известные специалисты в области теории реализуемости, дизайна меха-

низмов и коллективного выбора.

Акцент будет сделан на сложностях, связанных как с чисто вычисли-

тельными вызовами, порождаемыми комбинаторной природой большинства

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

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

2. Активное планирование

Формальная постановка задачи планирования может быть записана сле-

дующим образом.

Рассматривается двухуровневая организационная система (ОС), состоя-

щая из одного руководящего органа Центра, или Принципала в термино-

логии теории контрактов [15], и конечного числа подчиненных активных

элементов, или агентов. Обозначим через X множество допустимых значений

плана x (набора планируемых параметров) для организационной системы,

в качестве которого могут рассматриваться такие общепринятые величины,

как объем работ, отобранные к реализации проекты или плановые показате-

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

профиль предпочтений над некоторым множеством альтернатив, конкрет-

ные параметры контрактов и т.д. Обозначим через Ω множество возможных

значений исходной информации ω, передаваемой агентами Центру (набора

параметров, на основании которых определяется план).

Пусть для некоторого критерия эффективности планирования K(x, ω) (на-

пример, минимизация затрат на производство, максимизация объема выпус-

ка, максимизация суммарной полезности всех членов общества, максимиза-

ция индикатора принадлежности выбранного плана множеству Парето и т.д.)

может быть найдена целевая процедура планирования f : Ω → X, оптималь-

ная без учета активности агентов (далее целевая процедура):

f : K (f (ω),ω) ≥ K (x,ω),∀{x,ω} ∈ X × Ω.

Например, для экономики благосостояния (welfare economics) такими целе-

выми процедурами являются налог Линдаля [3] или расчет равновесия Валь-

раса [6].

С точки зрения ¾управляемости¿ ОС в ТАС сделано предположение, что

целевая процедура должна быть однозначной, т.е. в случае, если для какого-

либо ω существует множество планов X^∗(ω) ⊆ X, оптимальных по крите-

рию K, то процедура планирования должна обеспечивать выбор единствен-

ного плана x^∗ ∈ X^∗(ω). В общем случае это не так: процедура может быть

многозначной, определяя только X^∗(ω) ⊆ X, или быть стохастической, опре-

деляя некоторое вероятностное распределение на множестве возможных ис-

ходов.

В рамках предложенной в [14] технологии активного планирования, за-

дача поиска процедуры f является первым этапом:

1. Синтез процедуры планирования, оптимальной по требуемому критерию

в условиях пассивности подчиненных.

Заинтересованность агентов в определенных результатах планирования

формализуется их предпочтениями, задаваемыми над множеством резуль-

татов планирования с учетом возможных состояний системы X × Ω, или

функциями полезности uⁱ : X × Ω → R¹, где i ∈ N - индекс агента, N - мно-

жество агентов. Класс возможных предпочтений или функций полезности

i-го агента обозначим через Uⁱ. Набор функций полезности агентов (профиль

предпочтений) обозначим через u, а множество всех допустимых наборов че-

рез U = ×_i∈N Uⁱ. Следует отметить, что истинный профиль u предпочтений

может быть также не известен Центру, являясь частью ω.

Особую роль играют процедуры планирования, которые являются эффек-

тивными по Парето, т.е. ∀u ∈ U, ∀ω ∈ Ω ∄x ∈ X:

∃i ∈ N : uⁱ(x,ω) > uⁱ(f(ω),ω) и

∄j ∈ N u^j(x,ω) < u^j(f(ω),ω).

Задачу планирования будем называть индивидуальной, если X = ×_i∈N Xⁱ

и ∀i ∈ N uⁱ постоянна на X^-i = ×_j∈N{i}X^j, поэтому можно считать, что

uⁱ : Xⁱ × Ω → R¹. Это означает, что набор планируемых параметров может

быть декомпозирован на несколько подмножеств, от каждого из которых за-

висит целевая функция только соответствующего агента. Модель с одним

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

ния [15].

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

∃ℵ ⊆ 2^N\∅:

X = ×_C∈ℵX^C: ∀C ∈ ℵ и ∀i ∈ C uⁱ : Ω × X^C > R¹. Это означает, что не все

планируемые параметры представляют интерес для всех агентов. Классиче-

ским примером подобной задачи является задача определения уровня выпус-

ка коллективного блага и распределения затрат на его производство [3].

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

лезности каждого из агентов зависит от всех компонент вектора планов, т.е.

ℵ = {N} и ∀i ∈ N uⁱ : Ω × X → R¹. Большинство классических задач коллек-

тивного выбора могут быть отнесены к данному классу [16].

Проблема проявления активности (целенаправленности поведения аген-

тов, возможности самостоятельного принятия ими решений, выбора состоя-

ний и т.п.) формализуется следующим образом. При некоторых ω и u может

оказаться, что для некоторых агентов выгодно сообщение недостоверной

информации, поэтому Центр получает от агентов искаженную информацию

ω = ω, что, в свою очередь, может привести к падению эффективности пла-

нирования. Именно на эту проблему указывали в 50-е годы прошлого столе-

тия Поль Самуэльсон [3] и Якоб Маршак [4]. Считается, что систематическое

изучение данной проблемы инициировал Леонид Гурвич в своей пионерской

работе 1960 г. [6], положив начало направлению mechanism design, а позже

в работе 1973 г. [17] сформулировав условие совместимости со стимулами:

“Выгодно ли агентам с точки зрения своих индивидуальных интересов дей-

ствовать так, как им предписывает процедура планирования?” И негативный

результат состоит в том, что решения задачи максимизации коллективного

благосостояния в экономике с индивидуальными благами не совместимы со

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

почтениях. При их применении у агентов возникает мотивация к искажению

информации о своих предпочтениях.

Обозначим через преобразование ω_f : Ω × U → Ω возможные искажения

передаваемой информации агентами с учетом их активности (возможно-

сти использования имеющихся у них степеней свободы в рамках модели ОС

и правил планирования в собственных интересах) при заданной процедуре

планирования f. Если ω_f ≡ ω, то процедура планирования f является совме-

стимой со стимулами для раскрытия достоверной информации, или нема-

нипулируемой, т.е. устойчивой к активности агентов. В рамках техноло-

гии активного планирования задача определения преобразования ω_f являет-

ся вторым этапом:

2. Анализ полученной целевой процедуры на предмет ее устойчивости к про-

явлениям активности агентов.

Если ω_f = ω, то актуальным является вопрос, можно ли уменьшить по-

тери, возникающие при планировании вследствие активности агентов. Для

ответа на этот вопрос необходимо введение критерия, определяющего потери

в ОС при ω_f = ω, например, можно использовать критерий относительных

потерь minK(f(ωf (ω,u)))

. В ТАС этот критерий трактовался именно как

K(f(ω))

ω∈Ω,u∈U

относительные потери [18], а позже этому критерию было дано меткое назва-

ние “цена анархии” [19].

В [14, 20] в качестве такого критерия используется понятие близости ре-

зультатов планирования, оцениваемой величиной погрешности манипулиро-

вания ∆_f = max

∥f(ω) - f(ω_f (ω, u))∥_L, максимальным рассогласованием

ω∈Ω,u∈U

результатов планирования без и с учетом активности подчиненных по неко-

торой метрике L. В работах по теории коллективного выбора для процедур

выбора на основе предпочтений агентов, определенных над конечным мно-

жеством альтернатив, многие авторы оперируют критерием Келли долей

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

лируемой, см., например, [20-23].

Оценка ∆_f является третьим этапом технологии активного планирования.

3. В случае, если процедура неустойчива к активности, оценивается, насколь-

ко сильно результат планирования может быть искажен активными под-

чиненными.

Если исходная целевая процедура неустойчива к активности агентов, то

можно ли предложить какое-либо решение, уменьшающее потери, связан-

ные с проблемой несовместимости со стимулами? В ТАС и в теории ме-

ханизмов был предложен следующий подход. Вводится понятие механиз-

ма ρ =< S,π >, где S = ×_i∈NSⁱ, Sⁱ - множество допустимых действий (это

могут быть не только сообщения, передаваемые агентами Центру) агента

i ∈ N, π : S → X - процедура активного планирования, учитывающая ак-

тивность подчиненных в следующем смысле. Вообще множества S и Ω могут

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

существенным является преобразование s_π : Ω × U → S, определяющее ра-

циональное поведение агентов в рамках процедуры планирования π. О том,

как можно определить это преобразование, и определяемо ли оно в прин-

ципе, речь пойдет дальше. Учет активности подчиненных агентов как раз

и подразумевает необходимость определения данного преобразования. Мно-

жество допустимых процедур активного планирования обозначим через Π,

множество допустимых механизмов через P .

В некоторых работах по теории механизмов из процедуры планирования

выделяется отдельно процедура расчета трансферов, платежей между участ-

никами ОС. Это является целесообразным в том случае, когда для некото-

рых задач решение с побочными платежами сравнивается с решением без

платежей, см., например, [24]. Следует отметить, что в дальнейшем изло-

жении возможности перераспределения полезности между участниками ОС

через платежи будет отведено значительное внимание, поэтому будем вы-

делять ОС с трансферабельной полезностью (ТП) и с нетрансферабельной

полезностью (НТП).

В основу ответа на вопрос “что есть отображение s_π : Ω × U → S” в тео-

рии механизмов, теории выбора и теории активных систем был положен

теоретико-игровой подход. В рамках этого подхода преобразование s_π явля-

ется решением игры Γ (ρ), определяемой в общем виде следующим образом.

Игра Γ (ρ), индуцированная механизмом ρ = < S, π >,

это игра,

участниками которой являются агенты ОС, описываемая кортежем

< N, S, ϕ, I, T >, где N - множество участников, S - множество допу-

стимых профилей действий участников, ϕ = {ϕ¹,... ,ϕⁿ} - целевые функ-

ции участников, ϕⁱ(s) = uⁱ(ω, π(s)), I - структура информированности

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

раметрах игр, T - последовательность действий участников.

Здесь следует сделать важное замечание о том, что, на самом деле, по-

рядок действий агентов следует рассматривать как неотъемлемую компонен-

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

агентов между собой подразумевало, что они не должны дискриминировать-

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

к играм в нормальной форме, см., например, [25].

Задание порядка действий, а точнее, придание права первого хода неко-

торому игроку, образует серию задач определения оптимальной стратегии

первого игрока на основе определения его максимального гарантированного

результата. Исследование этих задач проводится преимущественно для си-

стем, состоящих из двух игроков, в работах по теории иерархических игр с

непротивоположными интересами, см., например, [26-29].

Соответственно разные механизмы могут приводить к разным решениям

в индуцированных ими играх в первую очередь это равновесие Нэша, на

основе которого Лео Гурвичем и было введено изначальное понятие совмести-

мости со стимулами [17]. Совместимыми со стимулами стратегиями агентов

предполагалось считать равновесные по Нэшу. Соответственно первоначаль-

ный вопрос формулировался так: является ли раскрытие информации о своих

предпочтениях равновесием Нэша в механизме, который призван обеспечить

максимум суммарного благосостояния всех агентов. В дальнейшем в фокусе

внимания исследователей оказались и другие теоретико-игровые концепции:

равновесие в доминантных стратегиях (РДС) и сильное равновесие Нэша (как

частные случаи равновесия Нэша), равновесие Байеса-Нэша, максимин и т.д.

[24, 30-41].

Определение отображения s_π : Ω × U → S позволяет исследовать вопрос

об эффективности того или иного механизма, в том числе осуществлять срав-

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

механизмов их эквивалентности.

Механизмы ρ = < S,π > и ρ =

S, π > эквивалентны для заданных Ω

и U, если ∀ω ∈ Ω, ∀u ∈ U π(s_π(ω,u)) ≡ π(s_π(ω,u)).

На эквивалентности между разными механизмами или даже отдельными

классами механизмов основан целый ряд ключевых результатов ТАС, напри-

мер [36, 37, 42] и теории механизмов, например [34, 43], которые подробнее

освещаются в дальнейшем изложении.

По аналогии с критерием, на основе которого на этапе 2 определяется, на-

сколько манипулируемой является целевая процедура, эффективность любо-

го механизма может сопоставляться с ¾эталонной¿. В частности, можно рас-

считывать цену анархии в ее робастной постановке: minK(f(π(sπ (ω,u)))),

K(f(ω))

ω∈Ω,u∈U

см., например, обзор [44]. А для задач коллективного выбора и экономики

благосостояния ключевым критерием эффективности механизма выступает

оптимальность по Парето определяемого плана для истинных предпочтений

агентов.

В [14, 20] рассматривался подход к оценке в пространстве планов. Оцени-

валась погрешность манипулирования - максимальное рассогласование ре-

зультатов планирования целевой процедуры и механизма ρ:

∆_f(ρ) = max

∥f(ω) - π(s_π(ω,u))∥_L .

ω∈Ω,u∈U

Перейдем к заключительному этапу технологии, на котором решается за-

дача активного планирования.

Механизм ρ^∗f ∈ P является решением задачи активного планирования,

если он аппроксимирует целевую процедуру f : ρ^∗f ∈ Argmin ∆_f (ρ).

ρ∈P

При этом подразумевается, что множество механизмов P должно быть

¾замкнуто¿ в том смысле, что любой из механизмов может быть реализован

и min∆f(ρ) существует.

ρ∈P

Очевидно, что ¾идеальным¿ решением задачи активного планирования

является механизм, для которого ∆_f (ρ) ≡ 0.

Механизм ρ^∗f ∈ P полностью реализует целевую процедуру f, если

∆_f(ρ) ≡ 0. При этом соответствующая целевая процедура называется пол-

ностью реализуемой.

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

подходом, получаем ключевое для теории механизмов понятие.

Процедура планирования реализуема в рамках некоторой теоретико-иг-

ровой концепции, если механизм, реализующий эту процедуру как целевую,

индуцирует игру, решение которой определяется данной концепцией.

С точки зрения теории управления организационными системами, наибо-

лее ¾удачной¿ является концепция РДС, так как при ее реализации любому

агенту нет необходимости пытаться угадать, просчитать или получить ин-

формацию о том, как будут действовать другие агенты [45, 46].

Именно для реализуемости в доминантных стратегиях ключевую роль иг-

рают неманипулируемые механизмы. Данное понятие определяется для пря-

мых механизмов.

Механизм планирования

< S,π > называется прямым, если S ≡ Ω

[34, 46].

Обозначим через Ωⁱ множество допустимых сообщений агента i ∈ N в про-⋃

извольном прямом механизме, Ω =_i∈N Ωⁱ. Тип агента i ∈ N rⁱ ∈ Ωⁱ - ис-

тинное значение тех компонент исходной информации ω, которые должен

сообщать Центру данный агент для принятия решения.

Прямой механизм планирования < Ω, π > называется неманипулируе-

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

та является сообщение истинного значения своего типа:

∀i ∈ N, ∀rⁱ, zⁱ ∈ Ωⁱ, ∀z^-i ∈ ×_j∈N\{i}Ω^jϕⁱ(rⁱ,z^-i) ≥ ϕⁱ(zⁱ,z^-i).

Также выделяется коалиционная неманипулируемость механизма плани-

рования [47-50]. Обозначим через r^C ∈ Ω^C = ×_i∈C Ωⁱ набор типов агентов из

группы C ⊆ N.

Прямой механизм планирования < Ω, π > является коалиционно немани-

пулируемым, если в индуцированной им игре ∀C ⊆ N, ∀i ∈ C, ∀r^C, z^C ∈ Ω^C ,

∀z^N\C ∈ Ω^N\C выполняются условия:

(

)

(

)

для ОС с НТП: ∀i ∈ C ϕⁱ r^C , z^N\C

≥ϕⁱ z^C, zN\C ;

∑ (

)

∑ (

)

для ОС с ТП:

ϕi r^C , z^N\C

≥ ϕⁱ z^C,z^N\C .

i∈C

В соответствии с определением эквивалентности прямой механизм может

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

он является неманипулируемым. Этот же факт лежит в основе ключевого

результата теории механизмов: в соответствии с принципом откровенности

(revelation principle) [34, 51, 52] процедура планирования f реализуема в до-

минантных стратегиях тогда и только тогда, когда построенный на ее основе

прямой механизм < Ω, f > является неманипулируемым. Следует отметить,

что в русскоязычной литературе также встречается перевод термина revela-

tion principle как принцип выявления, см., например, [53]. Однако используе-

мый в данной статье перевод, предложенный в русскоязычной версии класси-

ческой работы [54], по субъективному мнению авторов, лучше отражает его

смысл.

Таким образом, общая технология решения задачи активного планирова-

ния состоит из следующих основных этапов:

1. Синтез процедуры планирования, оптимальной по требуемому критерию

в условиях пассивности подчиненных.

2. Анализ полученной процедуры на предмет ее устойчивости к проявлениям

активности агентов (выражаемый в форме манипулирования сообщаемой

информацией).

3. Оценка, насколько сильно результат планирования может быть искажен

активными подчиненными в том случае, если процедура неустойчива к их

активности.

4. Синтез процедуры планирования, устраняющей (уменьшающей) данное

искажение.

Основываясь на формальной постановке задачи активного планирования,

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

чены ответы для перечисленных этапов технологии ее решения.

3. Ретроспектива исследований

В рамках теории коллективного выбора озвученный выше вопрос об устой-

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

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

ра f_U : U → X может быть неманипулируемым или может быть реализовано

через прямой неманипулируемый механизм (что в соответствии с принципом

откровенности одно и то же)?”.

Теорема Гиббарда-Саттертуэйта [30, 55] является наглядной иллюстра-

цией того факта, что для некоторых критериев планирования (например,

Парето-оптимальности выбранного плана) при произвольных предпочтениях

агентов на множестве результатов планирования неманипулируемые меха-

низмы позволяют реализовать лишь тривиальные целевые процедуры пла-

нирования диктаторские.

В то же время исследования в области экономики на предмет устойчиво-

сти ¾хороших¿ процедур планирования, таких как распределение стоимости

общественных благ [3, 6], показали, что эти процедуры неустойчивы к мани-

пулированию со стороны агентов [3, 17, 35, 56]. Из принципа откровенности

следует, что полностью реализовать подобные процедуры с помощью немани-

пулируемых механизмов нельзя. Но, решая задачу аппроксимации, возможно,

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

Поэтому актуальным является следующий вопрос: “При каких условиях

решение задачи активного планирования целесообразно искать на множестве

неманипулируемых механизмов?”.

Для ответа на этот вопрос крайне важными оказываются свойства класса

возможных предпочтений агентов U.

В терминологии, используемой в настоящей работе, U называется бога-

u = min(u, ũ) также

u∈Uⁱ.

В [34] показано, что, если правило группового выбора реализуемо в прямом

механизме в любой из следующих концепций равновесия: Нэша, Байеса-Нэша

и максимин, то оно также реализуемо и в доминантных стратегиях. Для бога-

того (в определенном выше смысле) класса предпочтений было показано, что,

если однозначное правило группового выбора реализуемо по Нэшу в некото-

ром непрямом механизме, то оно реализуемо и в прямом неманипулируемом

механизме.

Примерами богатых классов предпочтений являются:

• класс всевозможных предпочтений на X (в котором полностью реализуе-

мыми оказываются только диктаторские f_U );

• класс одномерных однопиковых функций полезности [47, 57];

• класс линейных аддитивных функций полезности [58].

Примерами классов предпочтений, не удовлетворяющих определению бо-

гатого, являются:

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

гомерно-однопиковых [47, 59-63].

• класс квазилинейных предпочтений, описываемых трансферабельными

функциями полезности [17, 35, 64].

Для последнего класса предпочтений было доказано, что эффективное по

Парето правило группового выбора не может быть реализовано прямыми

неманипулируемыми механизмами, зато может быть реализовано по Нэшу,

см. [34, 35, 64, 65].

В общем случае вопрос о соотношении реализуемости по Нэшу и реали-

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

предпочтений до сих пор остается открытым.

С озвученными выше результатами согласуются результаты, полученные

в рамках теории активных систем [8, 20, 36, 37]. В первую очередь рассматри-

вались задачи, сводимые к задачам индивидуального планирования с помо-

щью гипотезы слабого влияния: X =X ×_i∈N Xⁱ, где компоненты плана из Xⁱ

влияют только на полезность агента i ∈ N, а компоненты плана изX могут

влиять на полезность произвольной части агентов (в частном случае на

всех). Гипотеза слабого влияния предполагала: каждый агент i ∈ N считает,

что сообщаемая им информация не влияет на выбор Центром компоненты

плана из

X, а лишь на определение компоненты плана из Xⁱ. Это предпо-

ложение позволяло произвольные задачи планирования сводить к задачам

индивидуального планирования.

В [8] для частного случая, когда множество допустимых планов агента

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

вершенного согласования (УСС), которое в общем виде, полученном в [37],

записывается следующим образом:

(

)

∀i ∈ N, ∀s ∈ Ω uⁱ

πⁱ(sⁱ,s^-i), ω = {sⁱ,s^-i}

(

)

= max uⁱ

xⁱ,ω = {sⁱ,s^-i}

xⁱ∈Xⁱ(s-i)

где Xⁱ(s^-i) ⊆ Xⁱ - множество компонентов плана, влияющих на полезность

агента i ∈ N, допустимых с учетом сообщенной остальными агентами инфор-

мации s^-i. То есть в механизме планирования, удовлетворяющем УСС, план

должен выбираться таким образом, чтобы обеспечить максимальную полез-

ность каждому из агентов с учетом ограничений, накладываемых сообщенной

агентами информацией s.

Для частного вида функций полезности агента в [8], а затем для общего

случая в [37] было показано, что выполнение УСС является необходимым и

достаточным условием того, что в механизме π(s) сообщение достоверной ин-

формации агентами является равновесием в доминантных стратегиях. В [36]

при гипотезе слабого влияния показано, что в случае сведения задачи к ин-

дивидуальному планированию равновесный по Нэшу план реализуется про-

цедурой открытого управления. В [20, 37] для соответствующих задач было

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

тивную процедуру планирования f по Нэшу, существует эквивалентный пря-

мой механизм. То есть задачу активного планирования достаточно решать

на классе прямых неманипулируемых механизмов, см., например, [45].

Следует отметить, что в ТАС рассматривается и расширенная постановка

задачи обеспечения неманипулируемости. Имеется в виду, что агенты могут

не только искажать сообщаемую в Центр информацию, но и выбирать свои

решения, не совпадающие с планами. В этом случае под неманипулируемо-

стью понимается выполнение планов (мотивация агентов выбирать решения,

совпадающие с назначаемыми им планами) [66] и, собственно, сообщение до-

стоверной информации. Следует отметить, что обеспечение совпадения вы-

бираемых агентами своих решений с планами за счет изменения функций

полезностей агентов путем назначения Центром функций штрафов за откло-

нение решения агента от назначенного ему плана, а также назначения таких

планов, которые выгодно агентам выполнять, приводит к тому, что УСС в

этом случае приобретают следующий модифицированный вид:

(

)

∀i ∈ N, ∀s ∈ Ω, uⁱ

πⁱ(sⁱ,s^-i),ω = {sⁱ,s^-i}

(

)

max

uⁱ

xⁱ,ω = {sⁱ,s^-i}

xⁱ∈Xⁱ(s-i)∩Pⁱ(sⁱ,s-i)

где Pⁱ(sⁱ, s^-i) - множества планов, которые выгодно агентам выполнять при

заданных функциях штрафов. Заметим, что такое изменение УСС отменя-

ет принцип независимости множества, на котором определяется совершенно

согласованный план, от сообщения i-го агента.

В [67-72] рассматривается проблема выбора Центром оптимальных ме-

ханизма планирования, а также функций поощрения агентов и функций

штрафов, влияющих на функцию полезности агентов, при которых модифи-

цированное УСС обеспечивает неманипулируемость в расширенном смысле.

В [12, 68-72] исследованы задачи оптимального изменения Центром функций

полезности агентов путем назначения функций поощрений в зависимости от

величины планов либо выбираемых агентами решений, а также функций на-

казания агентов (штрафов) за отклонение выбранного решения от плана в

рамках заданных ограничений на фонд поощрения и множества допустимых

функций штрафов. В [68-70] доказана оптимальность и построен оптималь-

ный механизм для случая одного агента, в [71] для нескольких агентов, свя-

занных только общим фондом поощрения, в [72] для множества агентов,

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

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

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

агентами достоверной информации Центру для упомянутой выше расширен-

ной постановки задачи неманипулируемости в ТАС, а также представляют

методы построения оптимальных неманипулируемых механизмов.

В [50] был предложен топологический подход к обнаружению классов ме-

ханизмов, индуцирующих игры, в которых существует равновесие Нэша, и

таких, что для любого механизма из данного класса существует эквивалент-

ный прямой механизм. В частности, было показано, что при многомерно-

однопиковых предпочтениях агентов для любого механизма g : S → X, таких,

что Sⁱ ⊆ R¹ и ∀s ∈ S g(s) дважды непрерывно-дифференцируема, существует

эквивалентный прямой механизм. То есть несмотря на то, что класс предпо-

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

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

В рамках исследования коалиционной неманипулируемости в [47, 48] было

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

механизмы остаются коалиционно неманипулируемыми. В частности, для од-

нопиковых предпочтений неманипулируемые механизмы остаются коалици-

онно неманипулируемыми [47].

Таким образом, в ОС с НТП неманипулируемые механизмы целесообраз-

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

актуальным является вопрос: “Как именно должны выглядеть неманипули-

руемые механизмы планирования?”

Из работ по аксиоматическому подходу к построению неманипулируемых

правил коллективного выбора (см., например, [16, 34, 73-78]) следует выде-

лить следующее, пожалуй ключевое, условие, которому должны удовлетво-

рять неманипулируемые механизмы для ОС с НТП: выбираемый план дол-

жен определяться только на основе информации о наилучшем значении плана

для каждого из агентов.

Если обозначить Tⁱ(ω) = {τⁱ ∈ X : ∀x ∈ X uⁱ(τⁱ, ω) ≥ uⁱ(x, ω)}, то нема-

нипулируемый механизм должен быть представим в виде x = π(T (ω)), где

T (ω) = {Tⁱ(ω)}_i∈N . Существенность этого требования заключается в том,

что в неманипулируемых механизмах каждого из агентов следует спраши-

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

∀i ∈ N Ωⁱ = Xⁱ. И определять план лишь на основе данной информации.

Широко известный результат, который уже упоминался ранее, теорема

Гиббарда-Саттертуэйта [30, 55], указывает, что, если предпочтения агентов

на множестве возможных результатов планирования могут быть любыми, то

неманипулируемая процедура обязательно будет диктаторской: необходимо

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

какой план является наилучшим для него. И лишь для отдельных уточне-

ний класса предпочтений агентов над множеством результатов планирова-

ния, при условии сохранения его свойства богатости, можно показать, что

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

Сформулированное выше УСС согласуется с этими результатами, так как

из него следует, что, если для какого-либо из агентов i ∈ N Xⁱ(s^-i) = ∅,

то для него должен быть выбран наилучший план из данного множества [37].

Более детальную характеризацию того, как именно должны быть устрое-

ны прямые неманипулируемые механизмы, представляется удобным провести

на основе следующей классификации задач активного планирования [14]:

• однокритериальное коллективное планирование,

• индивидуальное планирование,

• многокритериальное коллективное планирование,

• многокритериальное смешанное планирование.

В рамках введенной терминологии в случае однокритериального плани-

рования задача активного планирования может быть только коллективной.

При многокритериальном планировании возможны задачи индивидуального,

коллективного и смешанного планирования.

Наиболее подробно исследованной можно считать задачу однокритериаль-

ного коллективного планирования.

В [47] для однопиковых предпочтений агентов был полностью описан класс

неманипулируемых механизмов, эффективных по Парето и показано, что все

эти механизмы коалиционно неманипулируемы. Это описание можно считать

конструктивным была предложена аналитическая запись для любой из

неманипулируемых процедур планирования. Это так называемые медиан-

ные схемы с дополнительными n - 1 фантомными агентами, чьи предпочте-

ния (точнее, наилучшие альтернативы) заранее фиксировались на множестве

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

упорядочении наилучших планов, сообщаемых реальными агентами и зара-

нее объявленных для фантомных агентов. В литературе этот класс механиз-

мов известен как обобщенные медианные схемы (ОМС) [79].

Так как в [34] было показано, что однопиковые предпочтения агентов яв-

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

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

точно решать на классе неманипулируемых механизмов. В [20, 42] был по-

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

игры, в которых решением игры является равновесие Нэша, было показано,

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

механизм (и был предъявлен алгоритм его построения). Описание немани-

пулируемых механизмов однокритериального коллективного планирования,

полученное в [20] как следствие УСС, было согласовано с аналитическим

описанием, полученным в [34], т.е. было показано, что ∀i ∈ N Xⁱ(s^-i) = ∅,

но существует не более одного агента, наилучший план для которого

принадлежит Xⁱ(s^-i).

В монографии [76] была предложена характеризация данного класса меха-

низмов на основе идеи блокирующих множеств в терминах УСС резуль-

татом выбора является сообщение того агента, для которого sⁱ ∈ Xⁱ(s^-i).

По сути, предложенный класс ОМС можно охарактеризовать как позици-

онное диктаторство выбор диктатора в любом таком механизме определя-

ется на основе упорядочения заявленных агентами наилучшими планами на

одномерном множестве результатов выбора, дополненном зонами нечувстви-

тельности при определенных сообщениях агентов о предпочитаемых аль-

тернативах выбирается одна из заранее определенных альтернатив

¾наи-

лучший план¿ одного из фантомных агентов.

В [80] класс однопиковых предпочтений агентов для задачи однокрите-

риального планирования был расширен до предпочтений с одним плато - у

каждого агента может быть более одного наилучшего плана, но множество

наилучших планов для каждого агента - связанное (плато). Было показано,

что весь класс неманипулируемых механизмов является все теми же ОМС, но

они должны быть дополнены правилом делегирования, позволяющего Центру

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

вход ОМС.

В [20] в качестве критерия эффективности решения задачи активного пла-

нирования был сформулирован критерий минимальной гарантированной по-

грешности. Первоначально полученное в указанной работе решение для от-

дельных ОМС было расширено на весь класс позже в [14].

Для задачи распределения ресурсов при индивидуальном планировании

был предъявлен алгоритм построения неманипулируемых механизмов пла-

нирования [20, 81, 82], но аналитическая запись была предъявлена лишь для

отдельного случая анонимных механизмов в [82]. Этот механизм известен в

иностранной литературе как ¾единое правило¿ (uniform rule), а в отечествен-

ной

как механизм последовательного распределения ресурсов (МПРР)

[14, 20, 83].

Было показано, что все неманипулируемые механизмы являются эффек-

тивными по Парето. Упомянутый выше результат [20] о достаточности пря-

мых неманипулируемых механизмов для решения задач активного индивиду-

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

распределения ресурсов при индивидуальном планировании. При этом было

показано, что все анонимные неманипулируемые механизмы эквивалентны

[82, 84] (точнее, что существует единственный неманипулируемый аноним-

ный механизм!) и вместо них могут использоваться достаточно простые, но

манипулируемые анонимные механизмы [84].

В [83, 85] была получена полная аналитическая запись всех немани-

пулируемых механизмов распределения ресурсов на основе анализа мно-

жеств Xⁱ(s^-i) для УСС.

Для случая двух агентов в [81] было показано, что неманипулируемый

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

низм однокритериального коллективного выбора, описанный в [34]. По сути,

впервые был поставлен вопрос об эквивалентности неманипулируемых меха-

низмов для разных классов задач планирования.

Результаты по неманипулируемости механизмов многокритериального

коллективного выбора [61-63, 86] в значительной мере опираются на резуль-

таты для однокритериального коллективного выбора [47]. В частности, для

многомерно-однопиковых предпочтений агентов в [61, 62, 86] было предъяв-

лено аналитическое описание класса неманипулируемых механизмов каж-

дый такой неманипулируемый механизм состоял из m однокритериальных

неманипулируемых механизмов коллективного выбора, описанных в [47] как

многомерные обобщенные медианные схемы (МОМС). Однако было доказа-

но, что эти неманипулируемые механизмы не являются эффективными по

Парето [62, 63]. Для применения этих результатов к задаче распределения

ресурсов необходимо проверять условие пересечения [60-62], которое в случае

непрерывного X требует бесконечного числа проверок [61]. В [87] предложен

алгоритмический подход, позволяющий осуществлять проверку свойства пе-

ресечения для конечного числа возможных планов.

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

полезности делается на задаче либо индивидуального, либо коллективного

планирования. Задачей смешанного планирования, исследованной в литера-

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

(см. [88, 89]).

В [83, 90] исследовались неманипулируемые механизмы для решения обоб-

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

лективного или смешанного планирования в ОС с n ≥ 2 агентами и мно-

жеством допустимых результатов планирования, определяемым ресурсным

ограничением







∑





X =

x = (x₁,...,x_m) ∈ R^m+

x_j ≤ R

R∈R¹⁺.





j=1

Частным случаем этой задачи является ¾классическая¿ задача распреде-

ления ресурсов при индивидуальном планировании когда каждый агент

заинтересован только в том количестве ресурса, которое выделяется именно

для него. Однако МОМС и МПРР не только различны по форме аналитиче-

ской записи, любой МПРР обеспечивает оптимальный по Парето результат

планирования, а МОМС нет.

В [83] этот разрыв был устранен. Удалось показать, что любой МПРР мо-

жет быть представлен в виде МОМС, дополненной правилом делегирования.

То есть агент сам выбирает, по каким компонентам плана он хочет принять

участие в его определении, а по другим компонентам делегирует механизму

(или Центру в соответствии с заранее объявленными правилами) право при-

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

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

к одномерным однопиковым в том смысле, что каждый агент заинтересо-

ван не более чем в одной компоненте плана, то результат планирования по

МОМС будет оптимальным по Парето. То есть если возможно разбиение все-

го множества агентов на непересекающиеся подмножества, для каждого из

которых из многокритериальной задачи планирования выделяется подзада-

ча, сводимая к однокритериальной, то результат МОМС будет оптимальным

по Парето. В случае, если хотя бы два подмножества агентов пересекаются,

гарантировать оптимальность по Парето нельзя. Кроме того, было показа-

но, что если принудительно разбивать агентов на подобные подмножества,

по сути, не учитывая их предпочтения по каким-либо из компонент пла-

на, то неманипулируемость МОМС пропадает. Этот результат согласуется

с результатами об оптимальности по Парето только одномерных процедур

планирования [57].

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

вании в [47] был получен следующий ¾негативный¿ результат. Если функ-

ции полезности агентов таковы, что ∀i ∈ N uⁱ(x) вогнутые, однопиковые в

смысле:

{

}

∑

arg max uⁱ (x) ∈ x :

x_k = R

x∈X

k=1

и неубывающие, при ∀R^′ > R:

maxui(x) > maxui(x),

x∈X^′

x∈X







∑





X^′ =

x = (x₁,...,x_m) ∈ R^m+

x_j

≤R^′





j=1

то любой неманипулируемый и эффективный по Парето механизм дикта-

торский.

Однако в [91] были предложены так называемые механизмы согласия

неманипулируемые недиктаторские механизмы, применимые для частно-

го случая данного класса предпочтений агентов: на основе многомерно-

однопиковых функций полезности конструируются многомерно-однопиковые

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

щений агентов определялись пропорции, в которых весь доступный ресурс R

должен быть разделен по направлениям m.

В [14] была предложена характеризация этого класса механизмов на осно-

ве МОМС.

Как уже было отмечено выше, для ОС с ТП результаты о реализуемости

в доминантных стратегиях в целом были негативными. При этом вопрос ха-

рактеризации самих неманипулируемых механизмов был исследован в самых

ранних работах.

Пожалуй, одной из визитных карточек науки “mechanism design” является

механизм Викри-Кларка-Гровса (VCG) [92-94], который является немани-

пулируемым и максимизирует суммарное благосостояние агентов без учета

трансферов:

)

(∑

< U, h > : h (u) ∈ Arg max

uⁱ(x) - C

x∈X

i∈N

где C ∈ R¹⁺ - некоторая константа, описывающая уменьшение полезности.

При этом само правило выбора плана состояло собственно из решения за-

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

лезности каждого агента и рассчитываемых по так называемой схеме налога

Кларка [94]:

∑

h =< x = argmax

uⁱ(x); t(x) >,

x∈X

i∈N

где

∑

t : X → Rⁿ⁺, ∀i ∈ N tⁱ =

u^j(x) - arg max

u^j(y).

y∈X

j∈N\{i}

Данные платежи можно проинтерпретировать как ¾компенсацию¿ со сто-

роны каждого агента i ∈ N потери суммарной полезности оставшихся членов

общества N \ {i}, возникающую вследствие учета его индивидуальных инте-

ресов.

Следует уделить особое внимание ¾изящности¿ этого решения: через та-

кие платежи функции полезности всех агентов становятся согласованными в

том смысле, что каждый агент стремится выбором своего сообщения макси-

мизировать сумму полезностей всех агентов! Однако гарантировать сбалан-∑

сированность этих платежей нельзя, так как в общем случае_i∈N tⁱ > 0, т.е.

в итоге суммарная полезность общества меньше максимально возможной.

При этом весь класс правил группового выбора, который может быть реа-

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

был полностью охарактеризован в работе Робертса 1979 г. [95]:

f (u) ∈ Argmax (ku^′ - C),

где u^′ - вектор-столбец предпочтений агентов, k ∈ Rⁿ⁺ - вектор неотрицатель-

∑

ных множителей, такой что_i∈N kⁱ > 0, C ∈ R¹⁺.

То есть реализуемыми являются только процедуры, обеспечивающие мак-

симум линейной свертки функций полезности агентов за вычетом некоторой

неотрицательной константы. Следует отметить, что этот результат крайне

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

[53, 96, 97], в отличие от его частного случая механизма VCG.

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

кали трансферабельную полезность у агентов, но при условии, что транс-

фер полезности для каждого из агентов определялся через компоненту плана

изX, т.е. с учетом гипотезы слабого влияния сообщения агентов (см., напри-

мер, [37]). Это позволяло разбивать задачу на набор слабосвязанных задач

Центр-Агент, для которых достаточность решения задачи активного плани-

рования была доказана в рамках ТАС [13, 37, 71] и в рамках mechanism design

[12, 15, 52].

В [68-70] показано, как соотносится задача построения механизма в усло-

виях интервальной неопределенности Центра с одной из задач теории кон-

трактов [98, 99].

Возможность трансферов полезности между агентами делает актуальным

вопрос исследования коалиционной неманипулируемости механизмов. Следу-

ет отметить, что необходимым условием коалиционной неманипулируемости

механизма является его Парето эффективность [35, 56]. Из того факта, что

при трансферабельной полезности неманипулируемые механизмы не могут

обеспечить решений, эффективных по Парето [35, 64], следует, что в ОС с ТП

невозможно обеспечить коалиционную неманипулируемость механизмов.

Описанный выше подход к представлению задачи многокритериального

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

шанного планирования в [100] применен для решения задачи распределения

ресурсов в ОС с ТП на основе реализуемости по Нэшу. По аналогии пред-

ставления МПРР как МОМС эффективный механизм решения задачи одно-

критериального выбора Гровса-Ледьярда [101] был адаптирован для реше-

ния многокритериальной задачи. Полученное решение обладало целым рядом

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

мой игре равновесия Нэша и сжимаемость отображения наилучших ответов,

что позволяло исследовать построенный механизм не только в условиях пол-

ной информированности агентов, как этого требует реализуемость по Нэшу

(что в настоящее время активно подвергается критике со стороны исследова-

телей об этом речь пойдет ниже). Перечисленные свойства позволили ис-

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

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

[102, 103]. Кроме того, в рамках разработанного механизма была обеспечена

сбалансированность трансферов, а в равновесии трансферы между любыми

двумя агентами отсутствовали, что отличало полученное решение от дру-

гих, предлагаемых в литературе не только по дизайну механизмов [104-106],

но и по распределенной оптимизации [107]. Однако дальнейшие лаборатор-

ные (в форме деловых игр) и вычислительные эксперименты [108] показали,

что не только синтезированный механизм, но и перечисленные выше реше-

ния дают эффективность решения задачи распределения ресурсов, не превы-

шающую эффективность ¾единого правила¿ (МПРР). Более того, в рамках

теоретического анализа [109] удалось показать, что для всех исследуемых

механизмов (пока только в рамках конкретных моделей задачи распределе-

ния ресурсов, которая рассматривалась в рамках эксперимента) существуют

эквивалентные механизмы, в которых у агентов есть доминантные страте-

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

для них существуют эквивалентные прямые механизмы. Для всех исследуе-

мых механизмов таким эквивалентным прямым механизмом оказалось ¾еди-

ное правило¿. Этот результат позволяет сделать предположение о том, что

утверждение о достаточности решения задачи открытого управления в ОС

с НТП можно распространить на широкий класс задач для ОС с ТП.

В соответствии с технологией активного планирования, описанной в

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

решить в рамках конкретной задачи активного планирования и которым уде-

лялось основное внимание в освещенных в данном разделе исследованиях:

1. Описание класса неманипулируемых механизмов:

a. формальное описание;

b. алгоритм построения.

2. Обоснование достаточности поиска решения задачи активного плани-

рования на классе неманипулируемых механизмов.

3. Поиск неманипулируемых механизмов, являющихся решением задачи

активного планирования.

4. Для произвольного неманипулируемого механизма определение множе-

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

Данный список дополним следующими актуальными вопросами для ис-

следования:

5. Существование эффективных по Парето неманипулируемых механиз-

мов (необходимое условие для коалиционной неманипулируемости ме-

ханизмов).

6. Согласованность классов неманипулируемых механизмов для различ-

ных задач планирования.

Последний пункт списка интересен с точки зрения возможности предложе-

ния универсального описания неманипулируемых механизмов в ОС с НТП.

Об этом пойдет речь в следующем разделе.

4. Откровенное открытое управление согласование и делегирование

На основе проведенной в предыдущих разделах структуризации попробу-

ем ответить на вопрос: какие ключевые выводы можно сделать из принципов

откровенности и открытого управления?

Первая линия водораздела между рассмотренными подходами проходит

через вопрос о возможности передачи полезности между агентами. Принци-

пы построения неманипулируемых механизмов и ответ на вопрос, можно ли

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

неманипулируемых механизмов, принципиально различаются для этих двух

подходов.

Для ОС с НТП, как было показано выше, неманипулируемые механизмы

могут быть построены в форме комбинации диктаторских правил с правила-

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

многих задач доказано, что поиск эффективного решения достаточно вести

на этом классе правил.

Для ОС с НТП принцип построения неманипулируемых механизмов иной:

конструируя функции трансферов полезности в соответствии с обобщением

подхода VCG, можно преобразовать функцию полезности каждого агента в

нужный критерий, причем теорема Робертса [95] указывает на то, что это воз-

можно для целевых критериев, являющихся линейной комбинацией функций

полезности агентов с неотрицательными множителями, среди которых хотя

бы один множитель не равен нулю. При этом для задач максимизации сум-

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

которой соответствуют данные механизмы, не дает того значения суммарной

полезности общества, которую можно получить при реализуемости в других

концепциях равновесия, в первую очередь по Нэшу.

Покажем, что на самом деле эти два направления абсолютно согласованы.

Начнем с того, что при переходе от НТП к ТП размерность любой зада-

чи планирования увеличивается на (n + 1)n/2 дополнительных компонент -

трансферов от одного агента к другому с учетом Центра, а без его учета

на (n - 1)n/2. При этом даже если изначальная задача планирования в ОС

с НТП могла быть дискретной, скажем, выбор из конечного числа альтер-

натив, то в ОС с ТП она априори становится непрерывной, так как каждый

трансфер можно определять непрерывным образом.

Аналогичный переход происходит и с функциями полезности агентов: ес-

ли в ОС с НТП можно было вести речь как о предпочтениях агентов, так и о

функциях полезности, то в ОС с ТП необходимо рассматривать только функ-

ции полезности агентов, причем они должны быть линейны по компоненте

трансферов. И этим объясняется то, что в неманипулируемых механизмах

в ОС с НТП используется информация только о том, какой план является

наилучшим с точки зрения агента, и не важно, какую именно полезность по-

лучает от выбора этого плана агент. Так как эту информацию никак нельзя

использовать, на функцию полезности агента разработчик может повлиять

только посредством выбора плана. А в ОС с ТП использовать информацию

о функциях полезности агентов можно и нужно.

Это различие оказывает драматическое влияние на множество оптималь-

ных по Парето планов. В ОС с НТП множество оптимальных по Парето пла-

нов может быть сколь угодно широким, вплоть до того, что будет включать в

себя все доступные планы! Например, в задачах коллективного выбора, если

число выбираемых альтернатив не превышает число агентов, на основе пред-

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

результат выбора будет оптимальным по Парето. Следует отметить, что чем

больше множество оптимальных по Парето планов, тем менее согласованы

интересы агентов.

А в ОС с ТП множество оптимальных по Парето планов ¾сжимается¿

только до тех планов, которые обеспечивают максимум суммарной полез-

ности агентов! То есть требованию оптимальности по Парето удовлетворя-

ют только такие x^∗ ∈ X, которые обеспечивают попадание вектора u(x) на

симплексе ∥u(x)∥

= C в пространстве Rⁿ! И ¾попасть¿ в такое ¾игольное

L₁

ушко¿ становится гораздо сложнее. Более того, учитывая, что трансферы по-

лезности рассматриваются как инструмент и разработчик механизма может

только взять полезность у любого из агентов и передать ее остальным или

уничтожить (сжечь, выбросить, забрать себе и т.д.), то условие оптимально-

сти по Парето для агентов подразумевает выполнение требования ¾сбаланси-

рованности платежей¿ ∥t∥

= 0. Все такие платежи располагаются на гипер-

L₁

плоскости в пространстве R^(n+1)n/2 (если рассматривать трансферы только

между агентами, то R^(n-1)n/2). Уже для ОС с тремя агентами это простран-

ство трехмерное (без учета трансферов центру, а с учетом шестимерное),

а как следует из обзора выше, если неманипулируемая процедура планиро-

вания в ОС с НТП не является диктаторской, то гарантировать попадание

в гиперплоскость в трехмерном (и более) случае она не может. Абсолютно

аналогичная сложность возникает и при проектировании трансферов и, как

и следует из перечисленных публикаций, она не может быть разрешена за

исключением отдельных специальных случаев.

Как выглядит диктаторская процедура в ОС с ТП? В принципе, можно в

ОС с ТП спросить агента, который был определен диктатором (позиционно

или персонально), о наилучшем для него плане. А можно и ¾помочь¿ ему,

спросив у него про его функцию полезности, и найти за агента ее максимум.

При этом платеж Кларка для всех агентов будет нулевым, так как рассчиты-

вается для набора весов агентов, где ненулевой вес будет только у диктатора,

а у остальных агентов вес будет равен нулю. То есть диктаторская процеду-

ра полностью удовлетворяет классической формулировке УСС, работающей

в ОС с НТП.

При этом и сам механизм VCG можно трактовать как диктаторский, пото-

му что тот план, который выбирается для системы, действительно оптимален

для каждого агента с учетом платежа Кларка.

Однако то, что план, выбираемый по какой-либо диктаторской процедуре,

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

является крайне экзотичным случаем наличием того самого центрального

(pivotal) агента.

То есть задачи планирования в ОС с НТП можно рассматривать как

¾сужение¿ по сравнению с аналогичными для ОС с ТП, что в свою очередь

сужает и множество доступных решений. При этом очевидно, что любой ме-

ханизм, который был неманипулируем в ОС с НТП, останется таковым в ОС

с ТП, см., например, [97].

Но обеспечение оптимальности по Парето результатов планирования с по-

мощью неманипулируемых механизмов в ОС с ТП не представляется воз-

можным. Из последнего следует, что в отличие от ОС с НТП для ОС с ТП

(за исключением некоторых крайне специфичных случаев) не удастся найти

коалиционно неманипулируемые механизмы, а любой индивидуально немани-

пулируемый механизм будет коалиционно манипулируем, включая механизм

VCG и диктаторские, так как сообщество агентов всегда сумеет за счет транс-

феров предложить диктатору d ∈ N выбрать более интересный для общества

план x^∗, чем оптимальный для него x^∗d, если ∥u(x^∗)∥L1 > u_d(x^∗d). Вопрос о

том, какая коалиция агентов может манипулировать выбором плана, следует

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

Однако если допустить, что Центр (или разработчик механизма) может

ограничить возможности по обмену полезностями между агентами, позво-

ляя только трансферы между Центром и каждым агентом индивидуально

(что является в некотором смысле реализацией гипотезы слабого влияния),

то описанного выше ¾схлопывания¿ множества Парето можно попробовать

избежать, сохраняя его как в ОС с НТП.

Вторая линия водораздела связана как раз с проблемой схлопывания мно-

жества Парето в задачах многокритериального планирования. И здесь выво-

ды, с одной стороны, достаточно конструктивные, с другой неутешитель-

ные. Гарантировать оптимальность по Парето нетривиального решения за-

дачи активного планирования (т.е. не полного диктаторства одного агента)

можно в том случае, если она может быть сведена к одномерной в смысле

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

одновременной декомпозицией множества агентов на непересекающиеся под-

множества, где каждый агент заинтересован в решении только одной подза-

дачи одномерного планирования. Только в этом случае множество немани-

пулируемых механизмов расширяется, допуская позиционное диктаторство,

поэтому в своих последних исследованиях Эрве Мулен призывает работать

именно с такими процедурами [57, 110], однако, как было показано в [83], по-

добное принудительное ограничение предпочтений агентов может привести

к потере свойства неманипулируемости у механизма планирования.

Таким образом, можно сформулировать следующие перспективные на-

правления теоретических исследований.

Во-первых, как тот набор ¾инструментов¿, который допустимо применять

при построении неманипулируемых механизмов в ОС с НТП (диктаторские и

константные процедуры), изменяется для ОС с ТП? То, что он расширяется,

это очевидно. Но сводится ли это расширение к дополнению инструментом

превращения целевой функции агента в целевую функцию планирования с

помощью трансферов платежом Кларка?

Как в целом результаты, полученные для конкретных постановок задач

планирования в ОС с НТП, переносятся на ОС с ТП?

Скорее всего, это не так, ведь весь значительный объем литературы по ди-

зайну экономических механизмов, включая недавно вышедший сборник [111],

речь о котором пойдет ниже, активно апеллирует к механизму VCG, но

крайне редко к теореме Робертса [95]. В упомянутом сборнике эта работа

упоминается лишь один раз в статье [97], в то время как VCG упоминается в

значительной части статей по теоретическим подходам.

Выше было показано, что классическое диктаторство (и, как следствие,

стохастическое тоже) легко укладывается в схему Робертса, но вопрос о кор-

ректном переносе схем Спрумона [82] и Мулена [47] (позиционное диктатор-

ство) пока остается открытым.

С точки зрения ТАС представляется целесообразным посмотреть, можно

ли отказаться от гипотезы слабого влияния для учета возможности транс-

феров в УСС. Здесь же следует отметить, что в работах по согласованным

механизмам стимулирования, обзор которых был упомянут во введении к

данной статье, в настоящее время рассматриваются нетривиальные сетевые

структуры (веерные, цепочки и т.д.) взаимодействия агентов, которые можно

трактовать как структуры возможных трансферов полезности [13]. Однако

вопрос для произвольных структур допустимых взаимодействий остается от-

крытым.

Во-вторых, результат подобной характеризации неманипулируемых меха-

низмов позволит заново посмотреть на вопрос об эквивалентности результа-

тов реализуемости в разных теоретико-игровых концепциях. Актуальность

ответа на этот вопрос представляется крайне важной, особенно в свете упо-

мянутых выше результатов о том, что в рамках задачи распределения ре-

сурсов можно получить эффективное ее решение, как равновесие Нэша, в

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

чивости этого решения на метаигровом уровне. В результате этого итоговая

эффективность решения задачи не превышает той, что может быть получена

в прямом неманипулируемом механизме без трансферов

¾едином правиле¿

[108, 109].

Интерпретируя написанное выше в позитивном ключе, можно завершить

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

ние права принятия решения одному агенту, можно сказать, что инструмен-

тарий открытого управления, сводящийся в моделях ОС с НТП к различным

формам делегирования, при переходе к ОС с ТП расширяется, дополняясь

инструментами согласования (возможность изменять целевые функции аген-

тов с помощью трансферов, подстраивая их под интересы системы). Однако

одновременно с расширением инструментария при переходе к трансферабель-

ной полезности множество планов, на которых возможно согласованное ре-

шение задачи активного планирования, значительно сокращается. А лишь на

этом множестве и возможно откровенное открытое управление!

5. Ближайшие перспективы и вызовы

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

циалистов направления исследований в области совместимости со стимулами

и неманипулируемости механизмов планирования.

Как уже было упомянуто выше, в своем свежем обзорно-постановочном

эссе Арунава Сен [97] задается теми же вопросами, которым был завершен

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

риваться как экстерналии. Там же он отмечает и то, что применение стоха-

стических процедур планирования, в которых результат планирования выби-

рается случайным образом, расширяет множество совместимых со стимулами

функций коллективного выбора.

В обзорной статье [112] один из авторов ключевой работы по эквивалент-

ности механизмов [34], Питер Хэммонд, систематизирует подходы к пробле-

ме учета экстерналей в разработке совместимых со стимулами решений за-

дач планирования на основе практически применимых моделей ОС, понимая

обобщенно под экстерналиями влияние выбора стратегии одним агентом на

предпочтения и стимулы остальных. Он отмечает, что модели, в которых

подобным влиянием можно пренебречь (т.е. выполняется гипотеза слабого

влияния), описывают практически вырожденные, идеализированные случаи,

такие как экономики с исключительно индивидуальными благами, в кото-

рых либо бесконечно много агентов, либо влияние агентов настолько мало,

что им можно пренебречь. При этом отмечается, что реализуемость по Нэ-

шу, позволяющая на теоретическом уровне разрабатывать эффективные и

совместимые со стимулами механизмы, также является идеализацией, так

как в своем изначальном виде представляет интерес только для крайне экзо-

тических случаев, когда Центр или разработчик механизма не обладает той

информацией, которая является общим знанием среди агентов. В случаях,

когда агенты не обладают полной информацией, реализуемость в концепции

равновесия Байеса-Нэша, превосходящая по эффективности неманипулируе-

мую реализуемость механизма планирования, подразумевает использование

Центром информации не только о предпочтениях и предпочитаемых резуль-

татах планирования, но и о взаимной информированности агентов, включая

их представления о представлениях друг о друге.

Очевидно, что, с одной стороны, разработка менее абстрактных подходов

к моделированию взаимной информированности (рефлексии), нежели услов-

ные вероятности, получаемые на основе общего распределения типов аген-

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

теоретико-игровых подходов (см., например, обзор [113]).

С другой стороны, до тех пор, пока нет возможности адекватно учитывать

взаимную информированность, преимущество реализуемости по Байесу-

Нэшу перед реализуемостью в доминантных стратегиях исчезает, что делает

актуальным применимость неманипулируемых механизмов и для ситуаций,

когда гипотеза слабого влияния невыполнима.

Эта же проблема выделяется среди основных в последних обзорах Гэб-

риела Кэррола, посвященных вопросам разработки устойчивых (робастных)

оптимальных механизмов планирования [114, 115]. Общий лейтмотив робаст-

ного подхода состоит в том, что с целью расширения применимости резуль-

татов теории механизмов акцент должен быть смещен с попыток реализации

оптимальных решений (как это сделано в классическом подходе) на попытку

минимизации числа параметров, учитываемых в разрабатываемых механиз-

мах. Иначе говоря, акцент должен быть сделан на простых механизмах.

Помимо упомянутой выше проблемы, связанной с необходимостью уче-

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

рациональности и вычислительной сложности.

В рамках проблемы корректного учета рациональности в качестве одного

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

принятия решения агентами (см., например, [22, 116]).

Другой проблемой в рамках данного направления является то, что во мно-

гих играх, индуцированных неманипулируемыми механизмами, помимо са-

мого равновесия в доминантных стратегиях, может существовать еще много

других равновесных по Нэшу ситуаций, что, в свою очередь, не гарантирует

сообщения агентами достоверной информации как равновесного исхода иг-

ры см., например, [108, 109, 117, 118].

Проблему вычислительной сложности можно декомпозировать на несколь-

ко аспектов.

Во-первых, само по себе решение задачи планирования без учета активно-

сти агентов может оказаться NP-трудным.

Во-вторых, для многих моделей теории игр расчет равновесия, в первую

очередь равновесия по Нэшу, может оказаться NP-трудным [119, 120].

Соответственно для ситуаций, когда полиномиально вычислимыми оказы-

ваются как решение задачи планирования без учета активности, так и реше-

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

какова окажется сложность расчета решения в соответствии с механизмом?

Здесь представляется целесообразным процитировать Поля Милгрома

[121], отметившего, что в реальных аукционах рассчитать результат в соот-

ветствии с подходом Викри-Кларка-Гровса не представляется возможным.

В целом ответ на этот вопрос негативный: вычислительная сложность рас-

тет [120, 122], хоть для отдельного класса задач и удается получить поло-

жительные результаты (при этом жертвуя эффективностью итогового реше-

ния). Например, неманипулируемый механизм, реализующий жадный алго-

ритм для задачи о ранце, имеет сложность, аналогичную сложности жадного

алгоритма и эффективность не менее 50 % от решения, получаемого полным

перебором.

Наконец, даже для манипулируемых механизмов можно задаться вопро-

сом: “Для каких из них сложность расчета решения в соответствии с заявками

агентов окажется ниже, чем сложность расчета оптимального манипулирова-

ния для отдельно взятого агента?” Для ряда процедур коллективного выбора

можно показать, что сложность расчета в соответствии с процедурой поли-

номиальная, а расчет рационального манипулирования NP-труден (см.,

например, [123, 124]).

В качестве аргумента против такого подхода можно привести цитату из

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

компанией Энрон 2002 г.: ¾Если закон Мерфи переформулировать для рыноч-

ного подхода к регулированию сферы электроэнергетики, то он будет звучать

следующим образом. Любая система, которая может быть обыграна, будет

обыграна и в самый неподходящий для этого момент¿. Иллюстрацией этого

также являются манипуляции, выявленные на отечественном рынке электро-

энергетики в рамках простых игровых экспериментов [125].

Неманипулируемые механизмы, реализуемые в рамках концепции РДС,

лишены этого недостатка и в совокупности со своей простотой вызывают

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

стве примера можно привести ¾единое правило¿ для задачи распределения

ресурсов, которое упоминалось выше. В последнее время интерес к нему не

уменьшается, особенно в свете того, что оно успешно конкурирует с други-

ми, более сложными и теоретически более эффективными решениями задачи

распределения ресурсов [57, 110, 108, 109].

Эрве Мулен в [57] отмечает, что с его точки зрения ключевой характери-

стикой для успешного решения задачи разработки механизмов является про-

стота пространства предпочтений агентов чем проще это пространство,

тем выше вероятность, что задача реализуемости будет не только решена

теоретически, но и внедрена в практику.

Про значимость предположений о множестве предпочтений Сальвадор

Барбера в [59] указывает, что малейшие изменения в требованиях к множе-

ству предпочтений оказывают драматическое влияние на то, какие немани-

пулируемые механизмы могут быть реализованы.

В работе [126], также вошедшей в упомянутый сборник, Вильям Томсон

агитирует за более ¾мягкий¿ аксиоматический подход, предлагая оценивать

не только то, насколько удовлетворяют отдельные механизмы некоторому на-

бору аксиом, что так часто приводит к негативным результатам, но и смот-

реть на то, насколько часто эти аксиомы нарушаются.

Созвучным с этой идеей оказывается результат, который представили в

своей готовящейся к публикации статье [127] двое из трех авторов работы [34],

Патриа Дасгупта и Эрик Маскин. Они показали, что правило выбора Кон-

дорсе удовлетворяет всем основным аксиомам коллективного выбора в том

случае, если возможно избежать в предпочтениях агентов циклов, приводя-

щих к парадоксу Кондорсе. Резюмируют они так: ¾подчеркивая этот недо-

статок, маркиз де Кондорсе обошелся несправедливо и с собой, и со всем

миром. . . ¿.

Этот результат резюмирует данный раздел, основной лейтмотив которого

заключается в том, что многие из перечисленных выше результатов еще ждут

своей правильной, не негативной интерпретации, которая позволит конструк-

тивно их использовать при решении реальных задач планирования.

6. Заключение

В качестве заключения хотелось бы озвучить следующую неожиданную

и, на первый взгляд, несколько ¾пессимистическую¿, но, на самом деле, по-

буждающую к размышлению мысль.

Более полувека теоретических и лабораторных исследований в области

проблемы согласованности и неманипулируемости механизмов принятия кол-

лективных решений свидетельствуют о том, что эффективность функцио-

нирования социально-экономических систем не может быть обеспечена без

согласованности интересов участников системы. Без корректного учета инте-

ресов участников механизмы принятия решений теряют свою устойчивость

(к стратегическому поведению), а корректный учет интересов приводит к

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

рить принятие решений одному лицу (диктаторство) или поделить все поров-

ну (¾единое правило¿).

С другой стороны, это лишний раз подтверждает очень точное название

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

ласти, принципы открытого управления и откровенности (revelation). Будем

открыты и откровенны если в вашей команде согласия нет, то и хорошего

результата вы не достигнете, какие бы изощренные и запутанные правила

управления вы ни применяли. Здесь уместно привести цитату Фридриха Эн-

гельса: ¾Где нет общности интересов, там не может быть единства целей, не

говоря уже о единстве действий¿. И, наоборот, если ваши интересы с кем-то

согласованы, то вы можете смело делегировать ему принятие решений, в лю-

бых областях, в которых он разбирается.

Тем не менее данная ¾откровенность¿ не означает, что на теоретических

и прикладных исследованиях в области согласованности и неманипулируе-

мости следует поставить ¾крест¿, ибо в дополнение к теоретическим направ-

лениям, которые выделены в разделах 4 и 5, количество задач выявления

несогласованности в действующих управленческих правилах и оценки по-

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

ния неисчерпаемо. В 2019 г. увидел свет сборник ¾Будущее экономиче-

ского дизайна¿ [111], часть статей которого, но далеко не все, упомянуты в

разделе 5. Этот сборник является наглядной иллюстрацией того, что пробле-

ма совместимости со стимулами и неманипулируемости механизмов принятия

коллективных решений находится в активной фазе исследований.

СПИСОК ЛИТЕРАТУРЫ

Бурков В.Н., Лернер А.Я. Принцип открытого управления активными систе-

мами // АиТ. 1970. № 8. C. 100-111.

Burkov V.N., Lerner A.Y. Open control principle for active systems // Autom.

Remote Control. 1970. No. 8. P. 1288-1297.

Немчинов В.С. Социалистическое хозяйствование и планирование производ-

ства // Коммунист. 1964. № 5. С. 77-78.

Samuelson P.A. The pure theory of public expenditure // Rev. Econom. Statist.

1954. V. 36. No. 4. P. 387-389.

Marschak J. Elements for a theory of teams // Management Sci. 1955. V. 1. No. 2.

P. 127-137.

Arrow K.J. Social choice and individual values. Chicago: Univ. of Chicago, 1951.

Hurwicz L. Optimality and Informational Efficiency in Resource Allocation Pro-

cesses / Mathematical Methods in the Social Sciences, 1960. P. 27-46.

Lerner A. Change of heart. Balaban International Science Services, 1992.

Burkov V.N., Lerner A.Ya. Fairplay in control of active systems / Differential games

and related topics. Amsterdam, London: North-Holland Publishing Company. 1971.

P. 164-168.

Burkov V.N., Yenaleev A.K., Kondrat’ev V.V. et. al. Regular functioning mecha-

nisms of organizational systems / Preprints of “Control science and technology for

the progress of society”. International Federation of Automatic Control. 8-th Trien-

nial World Congress. Kyoto. Japan. 1981. V. ХП. P. 31-37.

10.

Бурков В.Н., Новиков Д.А. Теории активных систем 50 лет: история разви-

тия // Теория активных систем - 50 лет / Материалы международной научно-

практической конференции, 18-19 ноября 2019 г. Под общ. ред. В.Н. Буркова.

М.: ИПУ РАН. C. 10-54.

11.

Бурков В.Н., Губко М.В., Коргин Н.А., Новиков Д.А. Теория управления ор-

ганизационными системами и другие науки об управлении организациями //

Проблемы управления. 2012. № 4. C. 2-10.

12.

Nobel Prize Committee et al. Oliver Hart and Bengt Holmström: Contract The-

ory // Scientific Background on the Sveriges Riksbank Prize in Economic Sciences

in Memory of Alfred Nobel. 2016.

13.

Еналеев А.К. Согласованные механизмы управления в активных системах //

Управление большими системами. Выпуск 83. М.: Изд-во ИПУ РАН, 2020.

С. 5-28.

14.

Коргин Н.А. Неманипулируемые механизмы принятия решений в управлении

организационными системами // Автореф. дис

д-ра техн. наук. М.: Изд-во

ИПУ РАН, 2014.

15.

Laffont J.J., Martimort D. The theory of incentives: the principal-agent model.

Princeton university press, 2009.

16.

Айзерман М.А., Алескеров Ф.Т. Выбор вариантов: основы теории. М.: Изд-во

“Наука”, 1990.

17.

Hurwicz L. The design of mechanisms for resource allocation // Amer. Econom.

Rev. 1973. V. 63. No. 2. P. 1-30.

18.

Бурков В.Н. Основы математической теории активных систем. М.: Изд-во “Нау-

ка”, 1977.

19.

Koutsoupias E., Papadimitriou C. Worst-case equilibria // Computer science re-

view. 2009. V. 3. No. 2. P. 65-69.

20.

Бурков В.Н., Данев Б., Еналеев А.К. и др. Большие системы: моделирование

организационных механизмов. М.: Изд-во “Наука”, 1989.

21.

Andersson T., Ehlers L., Svensson L.G. Budget balance, fairness, and minimal

manipulability // Theoretical Economics. 2014. V. 9. No. 3. P. 753-777.

22.

Bergemann D., Morris S. Robust mechanism design // Econometrica: J. Econom.

Soc. 2005. V. 73. No. 6. P. 1771-1813.

23.

Kelly J. Almost all social choice rules are highly manipulable, but few aren’t //

Social Choice and Welfare. 1993. V. 10. No. 2. P. 161-175.

24.

Jackson M. Mechanism Theory / The Encyclopedia of Life Support Systems. Ox-

ford: EOLSS Publishers. 2003.

25.

Губко М.В., Новиков Д.А. Теория игр в управлении организационными систе-

мами. М.: Изд-во “Синтег”, 2002.

26.

Гермейер Ю.Б. Игры с непротивоположными интересами. М.: Изд-во “Наука”,

1978.

27.

Горелов М.А., Кононенко А.Ф. Динамические модели конфликтов. III. Иерар-

хические игры // АиТ. 2015. № 2. С. 89-106.

Gorelov M.A., Kononenko A.F. Dynamic models of conflicts. III. Hierarchical

games // Autom. Remote Control. 2015. V. 76. No. 2. P. 264-277.

28.

Угольницкий Г.А., Усов А.Б. Алгоритмы решения дифференциальных моделей

иерархических систем управления // АиТ. 2016. № 5. С. 148-158.

Ougolnitsky G.A., Usov A.B. Solution algorithms for differential models of hier-

archical control systems // Autom. Remote Control. 2016. V. 77. No. 5. P. 872-880.

29.

Горелов М.А., Ерешко Ф.И. Иерархические игры в системе управления / Тео-

рия и практика системной динамики. 2019. С. 44.

30.

Бурков B.H., Опойцев В.И. Метаигровой подход к управлению активными си-

стемами // АиТ. 1974. № 1. C. 103-114.

Burkov V.N., Opoitsev V.I. Meta-game approach to control of hierarchical sys-

tems // Autom. Remote Control. 1974. V. 35. No. 1. P. 93-103.

31.

Satterthwaite M.A. Strategy-proofness and Arrow’s conditions: Existence and

correspondence theorems for voting procedures and social welfare functions //

J. Econom. Theory. 1975. V. 10. No. 2. P. 187-217.

32.

Бурков В.Н., Еналеев А.К., Кондратьев В.В. и др. Элементы теории опти-

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

стем. II // АиТ. 1984. № 11. С. 86-92.

Burkov V.N., Enaleev A.K., Kondrat’yev V.V. et. al. Fundamentals of theory of

optimal design for functioning mechanisms of two-level active systems. II // Autom.

Remote Control. 1984. V. 45. No. 11. P. 1457-1463.

33.

d’Aspremont C., Gérard-Varet L.A. Incentives and incomplete information //

J. Public economics. 1979. V. 11. No. 1. P. 25-45.

34.

Dasgupta P., Hammond P., Maskin E. The implementation of social choice rules:

Some general results on incentive compatibility // Rev. Econom. Stud. 1979. V. 46.

No. 2. P. 185-216.

35.

Walker M. On the nonexistence of a dominant strategy mechanism for making

optimal public decisions // Econometrica: J. Econom. Soc. 1980. V. 46. No. 6.

P. 1521-1540.

36.

Бурков В.Н., Кондратьев В.В. Механизмы функционирования организацион-

ных систем. М.: Изд-во “Наука”, 1981.

37.

Бурков В.Н., Еналеев А.К. Оптимальность принципа открытого управления.

Необходимые и достаточные условия достоверности информации в активных

системах // АиТ. 1985. № 3. С. 73-80.

Burkov V.N., Enaleev A.K. Optimality of the principle of open control. Necessary

and sufficient conditions for reliability of information in active systems // Autom.

Remote Control. 1985. V. 46 No. 3. P. 341-348.

38.

Sjöström T. On the necessary and sufficient conditions for Nash implementation //

Social Choice and Welfare. 1991. V. 8. No. 4. P. 333-340.

39.

Mookherjee D., Reichelstein S. Dominant strategy implementation of Bayesian in-

centive compatible allocation rules // J. Econom. Theory. 1992. V. 56. No. 2.

P. 378-399.

40.

Savvateev A. Coalition-proof incentive contracts / CORE, MIMEO - 2006.

41.

Izmalkov S., Lepinski M., Micali S. Perfect implementation // Games and Economic

Behavior. 2011 V. 71. No. 1. P. 121-140.

42.

Новиков Д.А. Оптимальность правильных механизмов управления активными

системами. I. Механизмы планирования // АиТ. 1997. № 2. 154-161.

Novikov D.A. Optimality of correct mechanisms of control of active systems //

Autom. Remote Control. 1997. V. 58 No. 2. P. 278-283.

43.

Myerson R.B. Optimal auction design // Math. Oper. Res. 1981. V. 6. No. 1.

P. 58-73.

44.

Roughgarden T., Talgam-Cohen I. Approximately optimal mechanism design //

Ann. Rev. Econom. 2019. V. 11. P. 355-381.

45.

Бурков В.Н., Еналеев А.К., Новиков Д.А. Механизмы функционирования со-

циально-экономических систем с сообщением информации // АиТ. 1996. № 3.

С. 3-26.

Burkov V.N., Enaleev A.K., Novikov D.A. Operation Mechanisms of Social Eco-

nomic Systems with Information Generalization // Autom. Remote Control. 1996.

V. 57. No. 3. P. 305-321.

46.

Новиков Д.А. Теория управления организационными системами / 3-е изд.

М.: Изд-во физ.-мат. лит-ры, 2012.

47.

Moulin H. On Strategy-proofness and Single-peakedness // Public Choice. 1980.

V. 35. No. 4. P. 437-455.

48.

Le Breton M., Zaporozhets V. On the Equivalence of Coalitional and Individual

Strategy-proofness Properties // Social Choice and Welfare. 2009. V. 33. No. 2.

P. 287-309.

49.

Barberà S., Berga D., MoreNo. B. Individual Versus Group Strategy-proofness:

When Do They Coincide // J. Econom. Theory. 2010. V. 145. No. 5. P. 1648-1674.

50.

Петраков С.Н. Механизмы планирования в активных системах: неманипули-

руемость и множества диктаторства. М.: Изд-во ИПУ РАН, 2001.

51.

Holmström B. On incentives and control in organizations. Stanford University, 1977.

52.

Myerson R B. Incentive compatibility and the bargaining problem // Econometrica:

J. Econom. Soc. 1979. V. 47. No. 1. P. 61-73.

53.

Николенко С.И. Теория экономических механизмов. М.: Изд-во Бином. Лаб.

знаний, 2009.

54.

Милгром П., Робертс Д. Экономика, организация и менеджмент: в 2-х т. Т. 1.

СПб.: Изд-во “Экономическая школа”, 1999.

55.

Gibbard A. Manipulation of voting schemes: a general result // Econometrica:

J. Econom. Soc. 1973. V. 41. No. 4. P. 587-601.

56.

Zhou L. Impossibility of strategy-proof mechanisms in economies with pure public

goods // Rev. Econom. 1991. V. 58. No. 1. P. 107-119.

57.

Moulin H. One-dimensional mechanism design // Theoretical Economics. 2017.

V. 12. No. 2. С. 587-619.

58.

Myerson R.B. Optimal auction design // Math. Oper. Res. 1981. V. 6. No. 1.

С. 58-73.

59.

Barberà S. Theoretical Unification, Domain Restrictions and Further Applications:

Some Comments on Future Research in Economic Design / Future Econom. Design.

Springer, Cham, 2019. С. 21-25.

60.

Barberà S., Masso J., Neme A. Voting under constraints // J. Econ. Theory. 1997.

V. 76. P. 298-321.

61.

Barberá S., Masso J., Serizawa S. Strategy-proof voting on compact ranges //

Games and Economic Behavior. 1998. V. 25 P. 272-291.

62.

Nehring K., Puppe C. Efficient and strategy-proof voting rules: A characteriza-

tion // Games and Economic Behavior. 2007. V. 59. No. 1. P. 132-153.

63.

Peters H., van der Stel H., Storcken T. Pareto optimality, anonymity, and strategy-

proofness in location problems // Int. J. Game Theory. 1992. V. 21. No. 3.

P. 221-235.

64.

Green J.R., Laffont J.J. Incentives in public decision making. Amsterdam: North-

Holland. 1979.

65.

Walker M. A simple incentive compatible scheme for attaining Lindahl alloca-

tions // Econometrica: J. Econom. Soc. 1981. V. 49. No. 1. P. 65-71.

66.

Еналеев А.К. Разработка механизмов стимулирования и управления в двух-

уровневых активных системах // Автореф. дисс

канд. техн. наук. М.:

МФТИ, 1980.

67.

Новиков Д.А. Оптимальность правильных механизмов управления активными

системами. II. Механизмы стимулирования // АиТ. 1997. № 3. С. 161-167.

Novikov D.A. Optimality of correct mechanisms of control of active systems. II:

Incentive mechanisms // Autom. Remote Control. 1997. V. 58. No. 3. P. 459-464.

68.

Еналеев А.К. Оптимальный механизм функционирования в активной систе-

ме с обменом информацией // Управление большими системами. 2010. № 29.

С. 108-127.

69.

Еналеев А.К. Оптимальность согласованных механизмов функционирования в

активных системах // Управление большими системами. 2011. № 33. С. 143-166.

Enaleev A.K. Optimal incentive-compatible mechanisms in active systems // Au-

tom. Remote Control. 2013. V. 74. No. 3. P. 491-505.

70.

Еналеев А.К. Оптимальные согласованные механизмы в активных системах и

задачи теории контрактов // Управление большими системами. 2014. № 49.

С. 167-182.

71.

Еналеев А.К. Оптимальный согласованный механизм в системе с несколькими

активными элементами // Проблемы управления. 2015. № 3. С. 20-28.

Enaleev A.K. Optimal incentive compatible mechanism in a system with several

active elements // Autom. Remote Control. 2017. V. 78. No. 1. P. 146-158.

72.

Еналеев А.К. Оптимальность согласованных механизмов в сетевых организа-

ционных структурах // Проблемы управления. 2020. № 1. С. 24-38.

73.

Aleskerov F. Arrovian Aggregation Models. Dordrecht: Kluwer, 1999.

74.

Le Breton M., Sen A. Separable preferences, strategyproofness, and decomposabil-

ity // Econometrica. 1999. V. 67. No. 3. P. 605-628.

75.

Le Breton M., Weymark J. A. Strategy-proof social choice with continuous separa-

ble preferences // J. Math. Econom. 1999. V. 32. No. 1. P. 47-85.

76.

Данилов В.И., Сотсков А.И. Механизмы группового выбора. М.: Изд-во “Нау-

ка”, 1991.

77.

Maskin E.S. Mechanism design: How to implement social goals // Amer. Econom.

Rev. 2008. V. 98. No. 3. P. 567-576.

78.

Weymark J.A. A unified approach to strategy-proofness for single-peaked prefer-

ences // SERIEs. 2011. V. 2. No. 4. P. 529-550.

79.

Barberá S. Strategyproof Social Choice // Handbook of social choice and welfare.

2011. V. 2. P. 731-831.

80.

Berga D. Strategy-proofness and single-plateaued preferences // Math. Soc. Sci.

1998. V. 35. No. 2. P. 105-120.

81.

Barberá S., Jackson M., Neme A. Strategy-Proof Allotment Rules // Games and

Economic Behavior. 1997. V. 18. No. 1. P. 1-21.

82.

Sprumont Y. The division problem with single-peaked preferences: A characteriza-

tion of the uniform rule // Econometrica. 1991. V. 59. No. 2. P. 509-519.

83.

Коргин Н.А. Представление механизма последовательного распределения ре-

сурсов как неманипулируемого механизма многокритериальной активной экс-

пертизы / Управление большими системами: сборник трудов. 2012. № 36.

С. 186-208.

Korgin N.A. Representing a sequential allotment rule in the form of a strategy-

proof mechanism of multicriteria active expertise // Autom. Remote Control. 2014.

V. 75. No. 5. P. 983-995.

84.

Бурков В.Н., Горгидзе И.И., Новиков Д.А., Юсупов Б.С. Модели и механизмы

распределения затрат и доходов в рыночной экономике. М.: Изд-во ИПУ РАН.

1997.

85.

Коргин Н.А. Эквивалентность и неманипулируемость неанонимных приоритет-

ных механизмов распределения ресурсов // Управление большими системами:

сборник трудов. 2009. № 26.1. С. 319-347.

Korgin N.A. Equivalence and strategy-proofness of non-anonymous priority allot-

ment mechanisms // Autom. Remote Control. 2016. V. 77. No. 11. P. 2065-2079.

86.

Border K., Jordan J. Straightforward elections, unanimity and phantom voters //

Rev. Econom. 1983. V. 50. P. 153-170.

87.

Бондарик В.Н., Коргин Н.А. Применение блочного метода для определения

допустимых неманипулируемых механизмов активной экспертизы при решении

задачи распределения ресурсов // Системы управления и информационные

технологии. 2012. № 4(50). С. 40-44.

88.

Barbera S., Jackson M.O. Strategy-proof exchange // Econometrica: J. Econom.

Soc. 1995. V. 63. No. 1. P. 51-87.

89.

Коргин Н.А. Задача стимулирования и обменные схемы // АиТ. 2001. № 10.

С. 147-153.

Korgin N.A. Incentive problems and exchange schemes // Autom. Remote Control.

V. 62. No. 10. P. 1673-1679.

90.

Бондарик В.Н., Коргин Н.А. Механизмы распределения ресурсов на основе

неманипулируемых симметричных анонимных процедур голосования с делеги-

рованием // Проблемы управления. 2012. № 5. C. 26-32.

91.

Бурков В.Н., Грацианский Е.В., Еналеев A.K., Умрихина Е.В. Организаци-

онные механизмы управления научно-техническими программами. М.: Изд-во

ИПУ РАН. 1993. 64 с.

92.

Vickrey W. Counterspeculation, auctions, and competitive sealed tenders // J. Fi-

nance. 1961. V. 16. No. 1. P. 8-37.

93.

Groves T. Incentives in teams // Econometrica: J. Econom. Soc. 1973. V. 41. No. 4.

P. 617-631.

94.

Clarke E.H. Multipart pricing of public goods // Public choice. 1971. V. 11. No. 1.

P. 17-33.

95.

Roberts K. The characterization of implementable choice rules // Aggregation and

revelation of preferences. 1979. V. 12. No. 2. P. 321-348.

96.

Lavi R., Mu’alem A., Nisan N. Two simplified proofs for Roberts’ theorem // Social

Choice and Welfare. 2009. V. 32. No. 3. С. 407.

97.

Sen A. Some Issues in Mechanism Design Theory / Future Econom. Design.

Springer, Cham, 2019. С. 355-357.

98.

Еналеев А.К., Лавров Ю.Г. Оптимальное стимулирование в активной системе

со стохастическим элементом // АиТ. 1990. № 2. C. 104-113.

Enaleev A.K., Lavrov Yu.G. Optimal incentives in an active system with a stochastic

element // Autom. Remote Control. 1990. V. 51. No. 2. P. 223-231.

99.

Bolton P., Dewatripont M. Contract Theory. Cambridge, Mass & London, England:

MIT Press, 2005.

100.

Коргин Н.А., Корепанов В.О. Решение задачи эффективного распределения

ресурсов на основе механизма Гровса-Лейдярда при трансферабельной по-

лезности // Управление большими системами: сборник трудов. 2013. № 46.

С. 216-266.

Korgin N.A., Korepanov V.O. An efficient solution of the resource allotment prob-

lem with the Groves-Ledyard mechanism under transferable utility // Autom. Re-

mote Control. 2016. V. 77. No. 5. P. 914-942.

101.

Groves T., Ledyard J.O. The Existence of Efficient and Incentive Compatible Equi-

libria with Public Goods // Econometrica: J. Econom. Soc. 1980. V. 48. No. 6.

P. 1487-1506.

102.

Arifovic J., Ledyard J.O. A behavioral model for mechanism design: Individual

evolutionary learning // J. Econom. Behavior Organizat. 2011. No. 78. P. 375-395.

103.

Mathevet L. Supermodular mechanism design // Theoretical Economics, Econo-

metric Society. 2010. V. 5(3). P. 403-443.

104.

Maheswaran R.T., Basar T. Nash equilibrium and decentralized negotiation in auc-

tioning divisible resources // Group Decision and Negotiation. 2003. V. 12. No. 5.

С. 361-395.

105.

Yang S., Hajek B. Revenue and stability of a mechanism for efficient allocation of

a divisible good // preprint. 2005.

106.

Yang S., Hajek B. VCG-Kelly mechanisms for allocation of divisible goods: Adapt-

ing VCG mechanisms to one-dimensional signals // IEEE J. on Selected Areas in

Communications. 2007. V. 25. No. 6. С. 1237-1243.

107.

Boyd S., Parikh N., Chu E. Distributed optimization and statistical learning via

the alternating direction method of multipliers. Now Publishers Inc, 2011.

108.

Korgin N.A., Korepanov V.O. Experimental Gaming Comparison of Resource Al-

location Rules in Case of Transferable Utilities // Int. Game Theory Rev. 2017.

V. 19. No. 02. С. 1750006.

109.

Korgin N.A., Korepanov V.O. Experimental and theoretical comparison of sev-

eral resource allocation mechanisms // IFAC-PapersOnLine. 2017. V. 50. No. 1.

С. 15592-15597.

110.

Moulin H. Fair division in the internet age // Ann. Rev. Econom. 2019. V. 11.

С. 407-441.

111.

Laslier J.-F. et al. (eds.) The Future of Economic Design, Studies in Economic

Design, Springer Nature Switzerland AG 2019.

112.

Hammond P.J. Allocation Mechanisms, Incentives, and Endemic Institutional Ex-

ternalities / Social Design. Springer, Cham, 2019. P. 175-186.

113.

Novikov D., Korepanov V., Chkhartishvili A. Reflexion in mathematical models of

decision-making // Int. J. Parallel, Emergent Distribut. Syst. 2018. V. 33. No. 3.

С. 319-335.

114.

Carroll G. Design for weakly structured environments / Future Econom. Design.

Springer, Cham, 2019. С. 27-33.

115.

Carroll G. Robustness in mechanism design and contracting // Ann. Rev. Econom.

2019. V. 11. С. 139-166.

116.

Zhang L., Levin D. Bounded rationality and robust mechanism design: An axiomatic

approach // Amer. Econom Rev. 2017. V. 107. No. 5. С. 235-39.

117.

Bochet O. From the Revelation Principle to the Principles of Revelation / Future

Econom. Design. Springer, Cham, 2019. С. 311-315.

118.

Bochet O., Tumennasan N. Dominance of truthtelling and the lattice structure of

Nash equilibria // J. Econom. 2020. V. 185. С. 104952.

119.

Nisan N., et al., editors. Algorithmic Game Theory. Cambridge University Press,

2007.

120.

Roughgarden T. Complexity-Theoretic Barriers in Economics / Future Econom.

Design. Springer, Cham, 2019. С. 159-163.

121.

Milgrom P., Segal I. Clock auctions and radio spectrum reallocation // J. Political

Economy. 2020. V. 128. No. 1. С. 1-31.

122.

Roughgarden T., Talgam-Cohen I. Approximately optimal mechanism design //

Ann. Rev. of Econom. 2019. V. 11. С. 355-381.

123.

Веселова Ю.А. Вычислительная сложность манипулирования: обзор пробле-

мы // АиТ. 2016. № 3. С. 7-32.

Veselova Y.A. Computational complexity of manipulation: A survey // Autom.

Remote Control. 2016. V. 77. No. 3. P. 369-388.

124.

Veselova Y.A. Does Incomplete Information Reduce Manipulability? // Group De-

cision and Negotiation. 2020. V. 29. No. 3. С. 523-548.

125.

Chirkin V. et al. Gaming Experiments for Analysis of Pricing Mechanisms at Elec-

tricity Markets // IFAC-PapersOnLine. 2016. V. 49. No. 32. С. 13-18.

126.

Thomson W. On the axiomatics of resource allocation: classifying axioms and map-

ping out promising directions / Future Econom. Design. Springer, Cham, 2019.

С. 213-222.

127.

Dasgupta P., Maskin E. Strategy-Proofness, IIA, and Majority Rule // Amer.

Econom. Rev.: Insights. 2020. V. 2. No. 4. P. 459-474.

Статья представлена к публикации членом редколлегии Д.А. Новиковым.

Поступила в редакцию 26.08.2020

После доработки 05.12.2020

Принята к публикации 15.01.2021