Петраков С. - Механизмы планирования в активных системах
ИНСТИТУТ ПРОБЛЕМ УПРАВЛЕНИЯ им. В.А. ТРАПЕЗНИКОВА
Введение
В социально-экономических системах (активных системах), функционирующих в условиях изменяющейся внутренней и внешней среды наряду с социально-экономическими факторами, действие которых учитывается управляющим органом (Центром), существуют факторы, предсказать возникновение и воздействие которых достаточно сложно для управляющего органа в силу ограниченности возможностей цента по сбору и переработке информации. Обычно, остальные участники активной системы (активные элекменты) осведомлены о неизвестных центру параметрах гораздо лучше центра.
Для более обоснованного принятия решений логичным представляется организация обмена информацией между центром и активными элементами (АЭ) и использование при принятии решений информации, предоставляемой активными элементами. Однако при обмене информацией АЭ могут сообщать недостоверную информацию, которая влияет на качество (эффективность) принимаемых решений.
Необходимость получения достоверной информации для принятия эффективных решений требует разработки методов создания механизмов функционирования систем с сообщением информации, поощряющих сообщение достоверной информации.
Исследование неманипулируемости механизмов
функционирования систем с сообщением информации ведется в нашей стране и за рубежом в рамках различных научных направлений. К ним, в частности, относятся: теория игр с непротивоположными интересами, теория коллективного выбора (в т.ч. теория реализуемости), теория активных систем - см. ссылки ниже. Несмотря на большой интерес к манипулируемости механизмов функционирования систем с сообщением информации, следует отметить, что в работах, посвященных этой теме, конструктивные условия неманипулируемости получены лишь для достаточно частных случаев.
Необходимость построения универсальных и удобных в использовании методов изучения неманипулируемости механизмов планирования определяет актуальность настоящего исследования.
Объектом настоящего исследования являются механизмы функционирования активных систем с сообщением информации. Предметом исследования является неманипулируемость механизмов планирования в активных системах с сообщением информации.
В случае, если сообщение достоверной информации является равновесием Нэша, механизм планирования называется
неманипулируемым.
Целью работы является получение условий неманипулируемости механизмов планирования в активных системах с нетрансферабельной полезностью и однопиковыми и сепарабельными функциями полезности активных элементов.
Реализация указанной цели подразумевает решение следующих
задач:
- получение условий неманипулируемости прямых механизмов;
- получение общих условий существования эквивалентных прямых механизмов;
- получение конструктивных условий существований эквивалентных прямых механизмов для широкого класса практически значимых частных случаев механизмов планирования;
- исследование влияния множества допустимых сообщений на существование эквивалентного прямого механизма.
В работе развивается метод анализа множеств диктаторства1, который основывается на применении аппарата теории активных систем, системного анализа и исследования операций.
Ниже описан предложенный автором метод анализа множеств диктаторства в механизмах планирования. На основе предложенного метода получены: достаточные условия неманипулируемости прямых механизмов в терминах множеств диктаторства; необходимые и достаточные условия коалиционной неманипулируемости прямых механизмов планирования общего вида; достаточные условия неманипулируемости механизмов планирования с векторными планами; достаточные условия существования эквивалентных прямых механизмов; конструктивные достаточные условия существования эквивалентных прямых механизмов для случаев дифференцируемых и линейных механизмов планирования в терминах свойств матрицы Якоби процедуры планирования; в рамках выбранного метода исследовано влияние множества возможных сообщений на существование эквивалентного прямого механизма.
Результаты работы позволяют значительно расширить множество прямых механизмов планирования, для которых доказана их неманипулируемость. Также расширен класс непрямых механизмов, для которых доказано существование эквивалентных прямых механизмов.
Конструктивные условия существования эквивалентных прямых механизмов позволяют строить эффективные (с точки зрения критерия управления) неманипулируемые механизмы планирования, для активных систем, в которых существуют удовлетворительные (с той же точки зрения) непрямые механизмы планирования.
Во введении обосновывается актуальность проблемы, формулируется цель и задачи работы, приводится краткое изложение основного содержания работы.
Изложение материала имеет следующую структуру. Первая глава посвящена общей постановке задачи и обзору результатов исследований активных систем с сообщением информации, полученных в отечественных и зарубежных работах. В §1 дается общая постановка задачи: определяются состав, информированность и порядок функционирования системы с сообщением информации, а также описываются предпочтения элементов системы, определяются механизм функционирования системы с сообщением информации и модели поведения элементов системы.
В §§ 2-3 приводится обзор существующих на настоящий момент работ, посвященных неманипулируемости механизмов планирования и реализуемости соответствий группового выбора. В §4 приводится обзор результатов работ, посвященных условиям существования эквивалентных прямых механизмов для непрямых механизмов планирования.
В §5 конкретизируется постановка задачи настоящего исследования.
Вторая и третья главы посвящены изложению оригинальных результатов по неманипулируемости и условиям существования эквивалентных прямых механизмов. Во второй главе приводятся условия неманипулируемости прямых механизмов, сформулированные в терминах множеств диктаторства. В §1 исследуется неманипулируемость механизмов в случае, когда элементы системы не могут вступать в коалиции.
Параграф 2 посвящен исследованию условий неманипулируемости механизмов функционирования систем с сообщением информации, когда используемая модель поведения элементов системы допускает образование коалиций элементов (в рамках нетрансферабельной полезности). В §3 приводятся результаты исследования структуры множеств диктаторства механизмов планирования, неманипулируемость которых доказана ранее в работах других авторов, а так же исследуется реализуемость этих механизмов.
В §1 главы 3 формулируется задача поиска эквивалентного прямого механизма. В параграфе 2 доказывается существования равновесия Нэша для непрямых механизмов планирования и приводится ряд технических результатов, необходимых для доказательства теорем о существовании эквивалентных прямых механизмов. Параграф 3 посвящен условиям существования эквивалентных прямых механизмов для непрямых механизмов планирования общего вида.
В §4 доказываются условия существования эквивалентных прямых механизмов для частных случаев дифференцируемых и линейных процедур обработки информации.
В заключении формулируются выводы настоящей работы и обсуждаются перспективные направления дальнейших исследований
неманипулируемости механизмов планирования в активных системах.
На рис. 0.1 приведена схема результатов настоящей работы.
Жирными линиями и затенением указаны результаты, полученные ранее другими авторами. Тонкими линиями указаны результаты, полученные автором настоящей работы и связи между ними.
Глава 1. Механизмы функционирования активных систем с сообщением информации
§1. Описание модели активной системы с сообщением информации
Будем рассматривать организационные (активные) системы (АС) с двухуровневой структурой. Такая организация состоит из управляющего органа центра и конечного числа подчиненных ему активных элементов (АЭ).
Множество АЭ обозначим I = {1, ..., п}. Задачей центра
является выбор некоторого множества альтернатив X из заранее определенного множества возможных альтернатив A . Предпочтения элементов и центра [104,119,122] на множестве A задаются бинарными отношениями, определяющими в общем случае нестрогий порядок над A. Элемент i е I характеризуется отношением предпочтения R. Множество возможных предпочтений i - го элемента обозначим ЭТІ. Строгую компоненту отношения Ri е ЭТ будем обозначать Pi.
Вектор отношений предпочтения всех элементов R = (Rj,..., Rn) называется профилем предпочтений. Множество всех возможных профилей предпочтений обозначим через ЭТ, ЭТ = ^ЭТІ . Предпочтения центра
iel
также будем задавать бинарным отношением и обозначать RP(R1,....,Rn), отношение предпочтения центра является нестрогим порядком над A , который зависит от профиля предпочтения активных элементов (изучение конкретного вида этой зависимости, а также задач агрегирования предпочтений [3,22,108] выходит за рамки настоящей работы).
Будем предполагать, что для каждого профиля предпочтений АЭ R еЭТ задана альтернатива z(R) е A , которая является наихудшей из допустимых для центра альтернатив. Определим верхний срез H(z(R), RP (R)) отношения RP (R) по альтернативе z(R) следующим
образом H(z(R), RP(R)) = {a е A| aRP(R)z(R)}. Множество допустимых
для центра альтернатив определим как соответствие F (R) = H (z( R), RP (R)) и будем называть это соответствие соответствием группового выбора (СГВ).
Сделаем следующее предположение об информированности: центру неизвестен профиль предпочтения активных элементов, активные элементы имеют информацию о предпочтениях других элементов [28,29,43,44,49,113,121].
Примем следующий порядок функционирования системы. Поскольку профиль предпочтений неизвестен центру, он запрашивает от элементов информацию, и те посылают в центр сообщения s,.
Множество возможных сообщений i - го участника обозначим S,. Совокупность сообщений участников назовем вектором сообщений и обозначим s = (sj, ..., sn). Множество всех возможных векторов
сообщений обозначим через S , S = П Si . Получив сообщения, центр по
ІеІ
процедуре принятия решения g: S ® A выбирает единственную альтернативу g(s) е A , которая считается решением. Совокупность множества возможных сообщений S и заданной на нем процедуры называется механизмом принятия решений, G = (S, g).
Моделью поведения активного элемента служит понятие равновесия [89,96,104,106,115]. В настоящей работе используются два типа равновесия: равновесие Нэша и равновесие в доминантных стратегиях.
Допустим, задан профиль предпочтений элементов R еЭТ и механизм (S, g). Вектор сообщений s’* называется равновесием Нэша при данном R е ЭТ, если для любого активного элемента i е І и любого его сообщения si е Si выполняется
g (s*) Rig (s-, si,),
где s-i называется обстановкой для i - го активного элемента и обозначает вектор размерности n - 1 с компонентами вектора s за исключением i - ой компоненты: s-i = (s1, ..., si-1, si+1, ..., sn). Таким
образом, в равновесии Нэша s’* ни один из игроков не выигрывает, отклоняясь из равновесия в одиночку и посылая сообщение si , отличное
от равновесного si* .
Сообщение элемента s* называется доминантной стратегией для элемента i е І при данном Ri е ЭТ, если Vsi е Si и Vs_i е S_t выполняется
g(s**, s-i) Rig (si, s-i).
То есть, сообщение si* является для i - го элемента при данном Ri оптимальным независимо от того, что сообщают остальные активные элементы.
Вектор сообщений s* называется равновесием в доминантных стратегиях при данном профиле предпочтений R е ЭТ, если i е I, st е Si, s_i е S_ выполнено g(s*, s_i )Rig (si, s_i). Другими словами, у каждого элемента есть сообщение s*, оптимальное при любых сообщениях остальных элементов s_, и в равновесии s каждый элемент посылает именно это сообщение.
Пусть задан механизм G = (S, g) и множество возможных профилей предпочтений ЭТ . Для R е ЭТ множество равновесных векторов сообщений обозначается через EQ (R) при использовании определения равновесия Нэша и Е^ (R) при использовании определения равновесия в доминантных стратегиях. Когда ясно, какое из определений равновесия используется, либо утверждение верно для обоих определений, индекс равновесия указываться не будет: Eg (R).
Легко показать, что для любого механизма G = (S, g) при любом профиле предпочтений R еЭТ выполняется eQD (R) с eQ^ (R).
В качестве иллюстрации введенных определений рассмотрим следующий пример.
Пример 1.1.1. Пусть n городам (активным элементам) необходимо пробурить артезианскую скважину в некоторой области - множестве возможных альтернатив A . Для простоты положим, что это - единичный
квадрат A = [0, 1] х [0, 1] с R2. Координаты скважины обозначим
- 1 2
х = (х , х ). Будем считать, что для каждого города i е I есть оптимальная с экономических позиций точка ri = (r1, rt2) е [0, 1]2 множества A , стоимость доставки воды из которой минимальна, например, центр этого города. Положим эту стоимость равной нулю.
Далее предположим, что затраты на транспортировку пропорциональны квадрату расстояния от скважины до абсолютно оптимальной точки. Предпочтения элементов могут быть заданы функцией полезности, поскольку она порождает транзитивное бинарное отношение. Если предположить, что каждый город стремится минимизировать собственные затраты, получим, что предпочтения каждого города выражены некоторой функцией полезности
jг (х, Г) = _[(х1 _r/)2 + (х2 _r2)2].
В качестве центра в этом примере выступает комиссия по экологической безопасности, которая стремится минимизировать ущерб, наносимый природе при транспортировке воды. Если считать, что этот ущерб пропорционален затратам на транспортиро вку, то целевая функция центра может быть представлена в виде Ф(г,..., rn, x) = Z ji (x, ri). Чтобы
І?І
минимизировать суммарные затраты всех городов на транспортировку воды, необходимо разместить скважину следующим образомZ Гі .
i?
Центр, не зная истинных положений оптимальных точек элементов, готов допустить отклонение значения целевой функции от максимального значения на 50 %, то есть СГВ будет выглядеть следующим образом
F 0і,..., Гп ) = ! x ?[0,1]Z ji(x,ri) ^,5Z ji\ пZri,ri
І?І
І?І
В этом примере функции полезности ji (x, r) представляют отношения предпочтения Ri, поскольку все функции полезности параметризованы параметром r можно считать предпочтения заданными, когда задано значение r .
Поскольку скважина строится сообща, у администраций городов
просят сообщить положения идеальных точек. Администрация каждого
города направляет в комиссию по строительству скважины оценку
- , 2 -
положения идеальной точки si = (si, si), где si ? [0, 1] х [0, 1]. Координаты скважины находятся по этим оценкам следующим образом
x = g..., sn) = П Zsi.
п І?І
Здесь в качестве сообщений выступают оценки положений идеальных точек si , а множеством возможных векторов сообщений будет
S = П[0, 1] . Процедурой принятия решения будет g(s1, ..., sn) = Z S .
І?І П І?І
Пара (S, g) составляет механизм принятия решений.
Допустим п = 2 и идеальная точка первого города r = (0.8, 0.4), а второго r2 = (0.9, 0.2). Если города сообщат достоверную информацию, то скважина будет построена в точке x = (0.85, 0.3).
Затраты городов yi будут равны у = 0.0125 и у2 = 0.0125. Если первый город сообщит оценку s = (0.7, 0.6), а второй город по-прежнему будет сообщать достоверную информацию, скважина будет пробурена в точке х = (0.8, 0.4) и затраты городов на транспортировку воды будут равны соответственно 0 и 0.05.
Если комиссия поставит условия, что скважина будет пробурена только после того, как оценки стабилизируются, то получим многошаговый процесс, во время которого каждый город будет изменять свое сообщение, пытаясь максимизировать свою функцию полезности.
Если администрации городов не обмениваются информацией, оценки стабилизируются только тогда, когда изменять своё сообщение каждому городу при неизменном сообщении другого города будет невыгодно. В нашем примере такими сообщениями будут s* = (0,6; 0,8) и s* = (1; 0).
Затраты городов при этом будут равны соответственно (0, 0.05). Очевидно, меняя своё сообщение, второй город не может приблизить место бурения к своей оптимальной точке. Скважина будет пробурена точно в точке, оптимальной для первого города. r
Таким образом, ситуация, когда сообщение первого города s*, а второго s* будет при заданных г* и r2 равновесием Нэша (но не будет равновесием в доминантных стратегиях).
Как видим, если комиссия не имеет информации о местоположении идеальных точек городов, место бурения, определенное при помощи механизма принятия решения (S, g), не будет равным х = (0.85, 0.3), т.е. не будет оптимальным с точки зрения минимизации
экологической опасности проекта. Однако, суммарные затраты городов на транспортировку воды от места бурения, определенного при помощи механизма (S, g) , будут составлять 0,05, а от точки, оптимальной для центра - 0,025. Так как центр готов допустить отклонение значения целевой функции от максимального значения на 50%, построенный механизм можно считать удовлетворительным. -
Рассмотренный пример в общих чертах качественно отражает введенные определения и проблемы, возникающие при исследовании механизмов функционирования систем с сообщением информации.
Таким образом, при изучении системы с сообщением информации необходимо выделить элементы системы, определить их предпочтения, информированность и порядок функционирования системы, а также модели поведения АЭ. На основании предпочтений центра строится СГВ, отражающее представления центра об эффективности функционирования системы. В настоящей работе будем
предполагать, что элементы системы, предпочтения, информированность и порядок функционирования системы определены и фиксированы.
Допустимое для центра СГВ определяется из соображений оптимальности его для центра. Выбору оптимальных для центра альтернатив посвящено большое количество работ по исследованию операций [77,95,102,103,121].
Поскольку в круг наших интересов будет входить в основном анализ механизмов функционирования, мы будем полагать, что допустимое для центра СГВ определено.
Как видно из примера 1.1.1, каждый из АЭ стремится максимизировать собственную полезность, вследствие чего может сообщать недостоверную информацию. В тоже время, сообщение недостоверной информации может быть нежелательным для центра.
Таким образом, одной из задач центра может быть построение неманипулируемого механизма функционирования АС, в котором АЭ выгодно сообщать достоверную информацию.
С другой точки зрения, манипулируемый механизм, построенный в примере 1.1.1, может считаться центром удовлетворительным (так как обеспечивает не более 50% потерь). Таким образом, в задачи центра также может входить построение удовлетворительных с его точки зрения механизмов функционирования АС, то есть механизма функционирования, реализующего заданное СГВ (см. раздел 1.2).
Качественно, из литературы известно, что при достаточно богатых множествах возможных предпочтений АЭ механизмы с сообщением информации оказываются диктаторскими (в теоремах о невозможности [3,7,22,32] существует единственный АЭ - диктатор). В настоящей работе мы рассматриваем более "узкий" класс предпочтений (сепарабельные, обобщенно однопиковые), что приводит к появлению групп диктаторов, различных для разных подмножеств множества возможных предпочтений.
В следующих двух параграфах приведем результаты работ, посвященных задачам построения неманипулируемых механизмов, а также реализуемости СГВ.
§2. Неманипулируемость механизмов планирования в активных системах с сообщением информации
В этом параграфе рассмотрим результаты работ, посвященных исследованиям неманипулируемых механизмов функционирования систем с сообщением информации. Среди большого числа работ, посвященных этой проблеме, можно выделить несколько групп работ: работы, посвященные исследованию механизмов функционирования систем с сообщением информации, полезность элементов которых трансферабельна, как общего вида [23,30,31,32,33,34,35,37] так и механизмов частного вида [4,7,36,37,38,54,69,70,120]; работы, посвященные исследованию неманипулируемости прямых механизмов функционирования систем с сообщением информации, в которых в явном виде выделены условия неманипулируемости механизмов функционирования [7,9,10,22].
Эти работы и будут представлять для нас основной интерес.
В настоящем параграфе будем рассматривать механизмы, в которых каждый элемент с номером i е I сообщает центру только своё отношение предпочтения Ri е Шг-. Тогда пространство возможных
сообщений S будет совпадать с Ш , а процедура планирования h будет отображением из Ш в A. Такие механизмы называются прямыми. Обычно прямые механизмы обозначаются H = (Ш, h).
Прямые механизмы, в которых сообщение достоверной информации является равновесием в доминантных стратегиях
R е eH (R), называются неманипулируемыми. Формальное определение неманипулируемого механизма следующее.
Пусть H = (Ш, h) - прямой механизм. Механизм H неманипулируем, если и только если R еШ, R е eH (R), либо (что одно и тоже)
і е I, Ri е Ші, Ri е Ші, R_i е Ш_і выполняется
h( R,, R_I) Rih( R', R_,).
Интересен тот факт, что определение неманипулируемого механизма можно строить, используя определение равновесия по Нэшу eH (R), что устанавливается следующей теоремой.
Теорема 1.2.1 [22]. В прямом механизме H = (Ш, h) для любого R еШ ,
R е eH (R) тогда и только тогда, когда R еШ, R е EH (R).
Парадоксальный на первый взгляд результат о том, что если сообщение достоверной информации является равновесием Нэша, то оно удовлетворяет более сильным условиям равновесия в доминантных стратегиях объясняется тем, если сообщение достоверной информации является равновесием Нэша при любом профиле предпочтений, то сообщение достоверной информации является наилучшим сообщением для каждого АЭ при любых сообщениях других АЭ, поскольку множество возможных профилей сообщений совпадает с множеством возможных сообщений.
Одной из основных проблем в теории коллективного выбора является существование набора так называемых результатов о невозможности существования функций коллективного выбора, удовлетворяющих тем или иным условиям (impossibility results), и, в частности, теорема Эрроу [2,3].
Рассмотрим активную систему с n АЭ. Множество возможных альтернатив A состоит не менее чем из трех альтернатив, |A| 3. Предпочтения каждого i - го АЭ представляются упорядочением (полным, транзитивным, ассиметричным бинарным отношением) P множества A . Обозначим S(A) - класс всех допустимых упорядочений множества A , а S(A) - класс всех упорядочений, которые допустимы в качестве коллективного выбора.
Функцию коллективного агрегирования (ФКА) 3 определим как отображение из 3: (S(A))n ® S(A). Таким образом функция коллективного агрегирования каждому набору предпочтений активных элементов из множества (S(A))n ставит в соответствие коллективное упорядочение из множества S(A).
Говорят, что ФКА 3: (S(A)) ® S(A) оптимальна Парето (ПО) [2,3], если для любых двух альтернатив a1, а2 е A и любого профиля P = (P-,..., Pn) такого, что Vi е I a-P^ выполняется а-3(P)a2.
Говорят, что ФКА 3: (S(A))n ® S(A) удовлетворяет условию независимости от посторонних альтернатив по Арроу (НПАА) [2,3], если для любых двух альтернатив a1, a2 и любых двух профилей
предпочтения P, P таких, что a1Pia2 тогда и только тогда, когда a-Pfa выполняется а-3(P)a2 тогда и только тогда, когда a-3(P')a2.
Говорят, что ФКА 3: (S(A))n ® S(A) удовлетворяет условию универсальности множества возможных предпочтений (УМВП), если S(A) является множеством всех упорядочений над A .
Говорят, что ФКА 3: (S(A)) ® S(A) является диктаторской, если существует АЭ i е I такой, что для любого P е (S(A))n выполняется 3(P) = р.
Верна следующая
Теорема 1.2.2 [2,3]. Любая ФКА удовлетворяющая ПО, НПАА, УМВП является диктаторской.
Механизм коллективного выбора g : (S(A)f ® A назовем
диктаторским, если существует АЭ i е I такой, что для любого профиля
предпочтений P = (P\_,..., Pn) е (S(A))n и для любой альтернативы из
множества значений механизма а е
, если а Ф g(P), то g(P)Pia .
Как и для функций коллективного агрегирования справедлив следующий результат о невозможности.
