автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.10, диссертация на тему:Неманипулируемые механизмы принятия решений в управлении организационными системами

Федеральное государственное бюджетное учреждение науки Институт проблем управления им. В.А. Трапезникова РОССИЙСКОЙ АКАДЕМИИ НАУК

УДК 519.8

На правах рукописи

КОРГИН НИКОЛАЙ АНДРЕЕВИЧ

НЕМАНИПУЛИРУЕМЫЕ МЕХАНИЗМЫ ПРИНЯТИЯ

РЕШЕНИЙ В УПРАВЛЕНИИ ОРГАНИЗАЦИОННЫМИ СИСТЕМАМИ

Специальность: 05.13.10 «Управление в социальных и экономических системах»

Автореферат диссертации на соискание ученой степени доктора технических наук

9 ЯНВ 2314

МОСКВА-2013

005544973

Работа выполнена в ФГБУН «Институт проблем управления им. В.А. Трапезникова РАН», лаборатория №57 «Активных систем»

Научный консультант: Бурков Владимир Николаевич

доктор технических наук, профессор Официальные оппоненты: Горошко Игорь Владимирович

доктор технических наук, профессор, ФГКОУ ВПО «Академия управления Министерства внутренних дел Российской Федерации», начальник кафедры «Информационных технологий управления органами внутренних дел» Орлов Александр Иванович доктор технических наук, доктор экономических наук, профессор, ФГБОУ ВПО «Московский государственный технический университет имени Н. Э. Баумана», профессор кафедры «Экономика и организация производства» научно-учебного комплекса «Инженерный бизнес и менеджмент»

Тренев Василий Николаевич

доктор технических наук, профессор, ФГБОУ ВПО «Московский педагогический государственный университет», профессор кафедры «Теории и истории социологии»

Ведущая организация: ФГАОУ ВПО «Национальный исследовательский университет «Высшая школа экономики»

Защита состоится «06» марта 2014 г. в 14-00 часов на заседании Диссертационного Совета Д 002.226.02 в ФГБУН «Институт проблем управления им. В.А. Трапезникова РАН» по адресу: 117997, Москва, ул. Профсоюзная, 65.

С диссертацией можно ознакомиться в библиотеке ИПУ РАН. Автореферат разослан: « 19 »декабря 2013 г. Ученый секретарь

Диссертационного Совета Д 002.226.02 кандидат физико-математических наук

Общая характеристика работы

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

Манипулируемость процедур принятия решений на основе сообщаемой информации является предметом исследования целого ряда научных направлений, в основе которых лежит теоретико-игровой подход к описанию взаимодействия людей как рациональных (ограниченно рациональных) субъектов: теория механизмов (mechanism design), вобравшая в себя теорию аукционов, теорию контрактов и теорию реализуемости (Бремзен A.C., Васин A.A., Гуриев С.М., До-манский В.К., Измалков С.Б., Крепе B.JT., Мазалов В.В., Островский М., Печерский B.JL, Савватеев A.B., Сегаль И.Р., Сонин К.И., Шварц M., Abreu D., Baçar Т., Chen Y., Clark E.H., d'Aspremont С., Dewatripont M., Gérrad-Varet L.A., Green J., Groves T., Healy P.J., Holmstrom P., Hurwic L., Jackson M., Krishna V., Laffont J.J., Maskin E., Martimort D., Mathevet L., Myerson R.B., Milgrom P., Mirrlees J.A., Roberts L., Roberts K., Tirol J., van Essen M., Vickrey W., Weber S., Whinston M. и др.)1; теория коллективного выбора (Айзерман М.А., Алескеров Ф.Т„ Данилов В.И., Карабекян Д.С., Сотсков А.И, Яновская Е.Б., Arrow К., Barbera S., Berga D., Black D., Bogomolnaya A., Border K.C., Ehlers L., Gibbard A., Jordan J„ Kelly J., Le Breton M., Massó J., Moulin H., Nehring K., Neme A., Peleg В., Peters H., Puppe С., Roth A.E., Sanver M.R.; Satterthwaite M.A., Sen A., Serizawa S., Shapley L., Sjöström T., Sprumont Y., Svensson L.G., Weymark J.A., Zaporozhets V., Zhou L. и др.); теория управления организационными системами (ранее - активными системами: Бурков В.Н., Губко М.В. Еналеев А.К., Заруба В.Я., Ириков В.А., Искаков М.Б., Кондратьев В.В., Мишин С.П., Новиков Д.А., Опойцев В.И., Орлов А.И., Петраков С.Н., Щепкин A.B. и др.), теория иерархических игр (Гермейер Ю.Б., Горелик В.А., Горелов М.А., Ерешко Ф.И., Кононенко А.Ф., Кукушкин Н.Ф. и др.).

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

В ходе этих исследований было показано, что при определенных условиях (Бурков В.Н. и Кондратьев В.Н., 1977; Dasgupta P., Hammond P., Maskin Е„ 1979; Myerson R.B., 1979)), в частности, при нетрансфе-рабельной полезности , оптимальные (для произвольного критерия эффективности) процедуры принятия решений в ОС можно искать именно в классе неманипулируемых механизмов. Это определяет целесообразность и актуальность разработки методов поиска эффективных механизмов планирования при нетрансферабельной полезности агентов именно в классе неманипулируемых механизмов. Выданном направлении исследований в настоящее время остается целый ряд открытых вопросов и проблем (см., например, Barbera S., 2010)

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

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

2. когда все принимаемые решения влияют на полезность всех агентов без исключения (далее - коллективное планирование, public goods).

При этом, несмотря на то, что возможно представление первой задачи как частного случая второй, описания неманипулируемых механизмов для этих двух задач и их свойства различаются. Это не позволяет, в частности, конструировать неманипулируемые механизмы для «смешанных» задач, в которых агенты могут быть заинтересованы только в части принимаемых решений, однако их декомпозиция до «индивидуальных» компонент невозможна (далее - смешанное планирование). Одной из наиболее актуальных задач планирования является задача распределения ресурсов - в которой центр должен принимать решение о распределении некоторого ограниченного ресурса в организационной системе на основании информации, поступающей от агентов. В настоящее время эта задача достаточно хорошо исследована как задача индивидуального планирования (Бурков В.Н., 1989; Sprumont Y, 1991; Новиков Д.А., 1997, Barberà S., Jackson M., Neme A., 1997 и др.). Но за исключением уточнения результатов Gibbard А. и Satterthwaite М.А. для подобных задач (Le Breton M., Zaporozhets V., 2009) и т.н. механизмов согласия (Бурков В.Н., 1993), практически не исследовалась с

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

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

Во-вторых, имеющееся на сегодня описание неманипулируемых механизмов для целого ряда задач принятия решений не позволяет осуществлять поиск оптимальных (по произвольному критерию) механизмов или не дает возможность реализовывать конструктивные алгоритмы их построения. В частности, для задачи распределения ресурсов как задачи индивидуального планирования существуют алгоритмы построения неманипулируемых механизмов, но отсутствует аналитическая форма их записи. Для задачи коллективного планирования в случае, если принимаемое решение описывается более чем одним параметром,(задача многокритериального коллективного планирования; задачи, в которых результат планирования - значение одного параметра, будем называть однокритериалъными), то условия, определяющие класс неманипулируемых механизмов в зависимости от множества допустимых результатов планирования (т.н. условия допустимости (Barbera S., Massó J., Neme A., 1997), могут быть неконструктивны - например, требовать проверки выполнения определенного условия в каждой точке определенной непрерывной области пространства параметров (Barbera S., Massó J., Serizawa S., 1998). Это, в частности, не позволяет рассматривать задачу распределения ресурсов как коллективное многокритериальное планирование. Подобные трудности обусловлены тем, что значительная часть исследований по неманипулируемым процедурам планирования сосредоточена на случае конечного множества допустимых результатов планирования (выбора), поэтому в исследуемых проблемах допустимы переборные варианты решений. Например, подходы к анализу степени манипулируемости процедур коллективного выбора с помощью индексов манипулируемости (Kelly J., 1993; Алескеров Ф.Т. Курбанов Э. 1998; Maus S., Peters Н., Storcken Т., 2007 и др.). Однако результаты этих исследований зачастую оказываются неприменимыми, если множество допустимых результатов планирования не является конечным.

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

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

В-четвертых, существующие результаты об оптимальности (по отдельным критериям) неманипулируемых механизмов принятия решений достаточно «требовательны» к тому, как именно описываются предпочтения подчиненных на множестве возможных вариантов принимаемых решений, в особенности - необходимость т.н. однопико-вости функции полезности агентов для задач однокритериального коллективного планирования (Moulin Н., 1980) или многомерной однопиковости для многокритериального планирования (Border К., Jordan J., 1983; Barbera S., Massó J., Neme A., 1997; Nehnng K., Puppe С., 2007). Это сильно сужает класс практических задач, для которых применимы результаты теоретических исследований. В частности, для многих практических задач распределения ресурсов^ целесообразным представляется использование аддитивных функций полезности, не удовлетворяющих требованиям многомерной однопиковости за исключением тривиальных случаев.

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

Подходы к построению механизмов управления с трансферабель-ной и нетрансферабельной полезностью отличаются достаточно сильно, в то время как задачи управления, для которых разрабатываются механизмы, не меняются. В частности, существующие результаты (Green J., Lafont J.J., 1979; Dasgupta P., Hammond P., Maskm E., 1979; Walker M. 1980) показывают, что неманипулируемые механизмы в условиях трансферабельной полезности оказываются менее эффективными (в частности, по критерию максимума суммарной полезности агентов), чем манипулируемые, в которых поведение агентов описывается теоретико-игровой концепцией равновесия Нэша. Поэтому представляется перспективным распространение подходов, успешно заре-

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

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

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

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

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

3. Разработка методов анализа погрешности манипулирования процедур планирования.

4. Разработка методов синтеза неманипулируемых механизмов, аппроксимирующих заданную целевую процедуру планирования.

5. Разработка методов анализа эквивалентности механизмов планирования.

6. Адаптация подходов к построению эффективных механизмов планирования с нетрансферабельной полезностью на модели с трансферабельной полезностью.

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

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

Научная новизна работы заключается в следующем:

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

2. Для задачи однокритериального коллективного планирования при

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

2.1. предложено аналитическое решение задачи активного планирования;

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

2.3. для класса процедур планирования на основе обобщенных линейных сверток определены процедуры, обладающие минимальной погрешностью манипулирования;

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

3. Для однокритериального индивидуального планирования при однопиковых предпочтениях агентов и непрерывных множествах результатов планирования получено аналитическое описание класса неманипулируемых механизмов распределения ресурсов, что позволило:

3.1. решить задачу активного планирования для широкого класса целевых процедур;

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

3.3. установить отношения эквивалентности между различными механизмами планирования, применяемыми на практике, и выделить класс достаточно «простых» механизмов.

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

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

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

5. Задачи индивидуального планирования представлена как задачи многокритериального коллективного планирования. Это позволило для однопиковых предпочтений агентов:

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

5.2. описать класс неманипулируемых анонимных и симметрич-

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

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

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

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

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

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

Апробация работы. Основные результаты диссертационной работы докладывались на всероссийских и международных конференциях: Теория активных систем (Москва 1999, 2001, 2007, 2009, 2011); Управление большими системами (Тбилиси 2000); Современные сложные системы управления предприятием (Липецк 2001); Проблемы управления безопасностью сложных систем (Москва 2001, 2012); Современные сложные системы управления (Старый Оскол 2002, Тверь 2004); Проблемы управления (Москва 2009); Управление развитием крупномасштабных систем (Москва 2009, 2011); Управление проектами: состояние и перспективы (Николаев 2011); Апрельская международная научная конференция по проблемам развития экономики и общества ВШЭ (Москва 2013); Game Theory and Management (Санкт-Петербург 2008, 2009, 2010, 2011, 2013); Economic mechanisms of the décision of global environmental problems in Russia (Барнаул 2008); Математика, компьютеры, образование (Дубна 2010), UKACC

International Conference on Control (Ковентри, 2010); International Meeting of the Society for Social Choice and Weifare (Москва 2010, Дели 2012); European Conference on Operational Research (Лиссабон 2010, Рим 2013); 18th World Congress of the International Federation of Automatic Control (Милан 2011); IFAC Conference on Manufacturing, Modelling, Management and Control (Санкт-Петербург 2013), Современные проблемы фундаментальных наук (Москва 2000, 2001, 2009, 2010, 2012); Государство и бизнес. Вопросы теории и практики: моделирование, менеджмент, финансы (Санкт-Петербург 2009); Развитие инфокоммуникаций в России в условиях перехода к информационному обществу (Москва, 2012); Управление в технических, эргатических, организационных и сетевых системах (Санкт-Петербург 2012, Дивно-морское 2013), а также на научных семинарах в ИПУ РАН, МФТИ, НИУ ВШЭ, АНХ.

Публикации. По теме исследования опубликовано 90 научных работ, включая 7 книг и 24 статьи в ведущих рецензируемых журналах.

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

Структура и объем работы. Диссертация состоит из введения, восьми глав, заключения и списка литературы. Работа содержит 286 страниц текста, список использованной литературы включает 312 наименования.

Содержание работы

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

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

В разделе 1.1 в рамках предлагаемого теорией управления в организационных системах (ОС) подхода к декомпозиции управленческого цикла описывается общая технология решения задачи планирования, состоящей из следующих основных этапов:

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

2. Анализ полученной процедуры на предмет ее устойчивости к проявлениям активности агентов (например, манипулирование сообщаемой информацией).

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

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

щей) данное искажение.

Формальная постановка задачи планирования записывается следующим образом. Обозначим через X — множество допустимых значений плана х (набора планируемых параметров) для ОС, О -множество возможных значений исходной информации со, передаваемой агентами центру (набора параметров, на основании которых определяется план). Пусть для некоторого критерия эффективности планирования в ОС К (например, затраты на производство, объем выпуска и т.д.) процедура планирования /': О. -> X - оптимальная без учета активности агентов (далее - целевая процедура). С точки зрения «управляемости» ОС, целевая процедура должна быть однозначной - в случае, если для какого-либо со существует множество планов

X' {со) с X , оптимальных по критерию К , то процедура планирования должна обеспечивать выбор единственного плана х* е X" {со).

Заинтересованность агентов в определенных результатах планирования формализуется функциями полезности и' :Г2х X -> Е1 , где I е N - индекс агента, N — множество агентов. Класс возможных функций полезности обозначим V . Набор функций полезности агентов {профиль предпочтений) обозначим и, а множество его возможных

значений - и = х.^и'. С точки зрения теории механизмов (точнее теории эффективных механизмов) особую роль играют процедуры планирования, которые являются эффективным по Парето.

Задачу планирования будем называть индивидуальной, если X = х(гЛ, X' т.ч. V/ е N и' :С1хХ' -> Е1 - т.е. набор планируемых параметр может быть разделен на несколько, от каждого из которых зависит целевая функция только соответствующего агента.

Задачу планирования будем называть смешанной, если ЭКс2'*\0: Х = хс^Хс: УС е К, У/еС и':Пх Xе —» Е1.

Задачу планирования будем называть коллективной, если функция полезности каждого из подчиненных зависит от всего плана - т.е. -,ЗКс2"\0: Х=хс^Хс, УС е К , У/еС и' :С1хХс ->К\

В рамках подобной формализации на этапе 2 необходимо определить сог :С1хи ->П - преобразование, описывающее искажение передаваемой информации агентами с учетом их активности при заданной / . Если со( == со, то процедура планирования / является неманипу-лируемой, т.е. устойчивой к активности агентов.

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

(1.1) Ау = mzxjfico)-f (о) f (со, н))||^.

По умолчанию в работе используется метрика L,. На этапе 4 решается задача активного планирования - задача уменьшения погрешности манипулирования. Для ее формализации

обозначим механизм p=<S,n>, где S = х.еЛ, S', 5' - множество допустимых действий (не только сообщений) подчиненного ieN, л-S-tX - процедура активного планирования, учитывающая активность подчиненных. Вообще, множества 5 и Q могут не иметь между собой ничего общего, но в рамках данной работы существенным является преобразование ^ : Q х t/S , определяющее действия подчиненных в процедуре /г. Множество допустимых процедур активного планирования обозначим П , множество допустимых механизмов - Р. Поиск решения задачи активного планирования будем производить на основе модифицированного критерия (1.1):

Д ,(р)= шах ||/(й>)-/г(^(®,и))|| •

weil,»et/ " "L

Определение 1. Механизм p'f е Р является решением задачи активного планирования, если он аппроксимирует целевую процедуру

Г:

(1.2) p"f £ Arg min Af (p) .

peV

Очевидно, что «идеальным» решением задачи активного планирования является механизм, для которого А f(p) = О

Определение 2. Механизм /?* е Р полностью реализует целевую процедуру Л если Af(p) = 0. При этом соответствующая целевая

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

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

Определение 3. Механизмы р =< S,n > и р =< S, к > эквивалентны для заданных Q и U, если Vtwefi, VueU

Определение 4. Процедура планирования / обладает нередуциру-емой погрешностью манипулирования, если механизм <Q,/> является решением задачи активного планирования.

Будем обозначать fp - целевую процедуру планирования, которая реализуется некоторым механизмом планирования р . Если обозначить Fp - множество всех целевых процедур планирования, реализуемых классом механизмов Р, то определение (1.2) решения задачи активного планирования может быть сформулировано в терминах подобных процедур: 12

(1 -3) p-.fpe Arg min max | f{co) - f(a)\.

fsfp

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

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

1. Состав участников процесса принятия решения:

1.1. Центр (Ц);

1.2. агенты (А).

2. Цели и интересы участников принятия решения в терминах соотношения желательных и реализующихся результатов (какое именно решение принимается).

3. Механизм принятия решения, состоящий из:

3.1. множеств допустимых сообщений агентов;

3.2. процедуры принятия решения, включая,

3.2.1. число периодов взаимодействия агентов и время принятия решения;

3.2.2. порядок сообщения агентами информации;

3.2.3. методы получения и обработки информации от агентов, методы получения решения на ее основе;

4. Информированность (осведомленность) всех участников принятия решения о:

4.1. предмете принимаемого решения;

ПРЕДМЕТ НАПРАВЛЕНИЕ ВОЗДЕЙСТВИЯ

Центр -» Агент Агент —» Центр Агент-» Агент

Состав 1. Формирование требуемого состава агентов 6. Принятие агентом решения об участии (или отказе) в принятии решения. 9. Воздействие агентом на принятие решений другими агентами об участии в принятии решения.

Интересы 2. Использование системы мотивации - индивидуальной (персонифицированной - для отдельных агентов) или единой (унифицированной) для всех агентов 7. Предложение финансовых гарантий (компенсации, гонорара) за обеспечение требуемого для агента результата принятия решения. 10. Передача агентом части своих «доходов» от принятия требуемого решения другим агентам.

Множество допустимых сообщений 3. Формирование повестки по принятию решения (или сценария и условий его принятия). - -

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

Информированность 5. Формирование у агентов определенных представлений о мнениях других агентов. - 12. Формирование у агентов определенных представлений о мнениях других агентов.

Таблица 1. Виды стратегического поведения участников ОС

4.2. других компонентах модели (порядок сообщения информации, процедура принятия решения и др.);

4.3. информированности других участников.

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

В результате анализа теоретико-игровой модели можно выделить 12 видов стратегического поведения, представленных в таблице 1. Рассматриваемое в рамках данной работы манипулирование является стратегическим поведением вида 8 (некооперативные модели манипулирования), элементом стратегического поведения видов 10 (кооперативное манипулирование с трансферабельной полезностью) и 11 (кооперативное манипулирование с нетрансферабельной полезностью).

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

Определение 5. Игра Г(р), индуцированная механизмом p-<S,7t> — это игра в нормальной форме, участниками которой являются агенты ОС, описываемая кортежем < N,S,<p,I > , где N — множество участников, S - множество допустимых действий участников, <р = {(р\...,<р"} - целевые функции участников, <р' (s) = и' (со, я'(.у)), 1 - информированность агентов.

В рамках теоретико-игрового подхода к моделированию преобразование sx является решением игры Г(р). Соответственно, разные механизмы могут приводить к разным решениям в индуцированных ими играх: равновесие в доминантных стратегиях (РДС), равновесие Нэша, равновесие Байеса-Нэша, максимин и т.д. - теоретико-игровые (ТИ) концепции.

Определение 6. Процедура планирования реализуема в некоторой теоретико-игровой концепции, если механизм, реализующий эту процедуру как целевую, индуцирует игру, решение которой определяется данной концепцией.

Будем обозначать множество процедур планирования, реализуемых в рамках определенной ТИ концепции (con), через Fcun.

С точки зрения теории управления организационными системами; наиболее «удачной» является концепция РДС, т.к. при ее реализации любому агенту нет необходимости пытаться угадать, просчитать или получить информацию о том, как будут действовать другие агенты. В тоже время, результаты теории механизмов, в первую очередь, ее

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

ОС с НТП

Реализуемость по Нэшу Ш

ОС с ТП

Л!

с

Реализуемость в доминантных стратегиях (Ду)

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

2. Возможно обеспечение коалиционной неманипу-лмрусмости механизмов.

т

1. Множество расширяется, но оказывается уже, чем в при использовании других концепций ТИ решений.

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

Другие концепции реализуемости

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

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

Определение 7. Механизм планирования <5,л> называется прямым, если 5 з Г2.

Обозначим Г2' — множество допустимых сообщений агента г е N в произвольном прямом механизме, О = и СУ . Тип агента г е N г' еП'

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

Определение 8. Прямой механизм планирования < О., тс > является неманипулируемым, если в индуцированной им игре доминантной стратегией любого агента является сообщение истинного значения своего типа: V/ е N , \/г°, г' е О! , У г'1 е xJeNЧi} & (г' ,г~')> (?' (г'

В соответствии с определением эквивалентности прямой механизм может быть эквивалентен некоторому другом механизму только при условии, что он является неманипулируемым. Этот же факт лежит в основе ключевого результата теории механизмов. В соответствии с принципом выявления, процедура планирования / реализуема в доминантных стратегиях тогда и только тогда, когда построенный на ее основе прямой механизм <П,/> является неманипулируемым. Именно поэтому, для предотвращения стратегического поведения вида 8 (см. таблицу 1) при решении задачи активного планирования целесообразно применять неманипулируемые механизмы планирования.

Для предотвращения стратегического поведения вида 11, необходима коалиционная неманипулируемость механизма планирования.

Обозначим гс е Ос = х.еС£Т - набор типов агентов из группы С с ТУ'

Определение 9. Прямой механизм планирования <0.,п> является коалиционно неманипулируемым, если в индуцированной им игре МС с N, Угс ,гс е Пс , \/гм'с <= £2Л"С выполняются условия:

для ОС с НТП: V/ е С ф (гс, ) > ф (гс, г™);

для ОС с ТП: ]>'(гс, > .

¡еС ¡<=С

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

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

В разделе 1.4 описывается структура актуальных проблем активного планирования в ОС с НТП и проводится обзор основных теоретических результатов, применимых при однокритериальном коллективном и индивидуальном планировании, многокритериальном коллективном и смешанном планировании. В соответствии с технологией активного планирования, описанной в разделе 1.1, выделяются следующие подзадачи.

1. Описание класса неманипулируемых механизмов: формальное описание / алгоритм построения.

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

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

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

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

5. Существование эффективных по Парею неманипулируемых механизмов (необходимое условия для коалиционной неманипулируе-мости механизмов).

6. Согласованность классов НМ для различных задач планирования.

На основании обзора определяется список актуальных теоретических задач, обуславливающих дальнейшую структуру работы. Результаты данной структуризации приведены в таблице 3. Знак + означает, что задача может считаться решенной, +/- — задача была решена частично,- — задача не рассматривалась. В таблице указывается, в какое состояние переводится задача в данном исследовании и номера разделов, в которых получен соответствующий результат.

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

т

ресурсным ограничением R е : X = {х = (*,,•••,*„,) е R^ | ^ R}.

]-1

Глава 2 посвящена рассмотрению задачи активного коллективного однокритериального планирования в ОС с НТП.

В разделе 2.1 вводятся основные понятия и определения.

Однокритериалъное планирование — IcB',

Предпочтения агента ieN и': fix X —> R1 называются одно пиковыми, если Voefi: существует единственная точка пика г' = argmaxw'(jc); Vz.z'e X , если r'>z>z\ то и'(z)>u'(z') , если

хеХ

z>z'>r', то ii'(z) < u'(z'). Класс однопиковых предпочтений будем обозначать U\. Moulin Н. в 1980 показал, что если предпочтения

агентов - из U\, a let1, то любая неманипулируемая процедура коллективного выбора - обобщенная медианная схема (ОМС): (2.1) х= min (max(a(S),r')),

Sc.V:ie5

где a(S) е X — параметры настройки механизма, определяемые для каждой из возможных групп агентов S с N \ 0 , причем a(S) > a(S) при S a S .

Тип плани-рования Подзадача4^, активного планирова- ^^ НИЯ Однокритери-альное коллективное планирование Индивидуальное планирование* Многокритериальное коллективное планирование Многокритериальное смешанное планирование* Многокритериальное коллективное планирование, расширение предпочтений*

Формальное описание НМ + +/--» + Раздел 3.2 + -->+/- Раздел 5.3 +/--» + Раздел 6.2

Алгоритм построения НМ + + +/--> + Раздел 4.2 Раздел 5.3 Раздел 6.2

Условие применимости НМ для решения задачи активного планирования + + - —► + Раздел 4.3 - Раздел 6.3

Парето-эффективность НМ + . + Раздел 5.3 Раздел 6.3

Решение задачи активного планирования на классе НМ +/-_> + Раздел 2.3 --»+/- Раздел 3.3 - -» + Раздел 4.3 - -->+/-Раздел 6.3

Определение механизмов, эквивалентных НМ +/--» + Раздел 2.4 +/--* + Раздел 3.4 --У + Раздел 4.3 - Раздел 6.3

Согласованность НМ для различных типов планирования +/--> + Раздел 5.2 Раздел 5.3 --» + Раздел 6.2

Таблица 3. Структуризация задач исследования и предварительные результаты для планирования в ОС с НТП * - в рамках задачи распределения ресурсов

** - «негативный» результат об отсутствии Парето эффективности.

Если a(S) не зависит от того, кто именно из агентов входит в группу S, а зависит лишь от числа агентов в группе US , то правило является анонимным. Все ОМС являются эффективными по Парето.

Hammond P., Maskin Е. в 1979, показали, что на классе однопико-вых предпочтений агентов множество реализуемы процедур совпадает с множеством процедур, которые реализуемы в доминантных стратегиях. Т.е. только ОМС могут быть реализуемыми процедурами планирования.

В.Н. Бурковым в 1989 исследовался класс механизмов планирования Р1 = {< X", л (s) >}, удовлетворяющих требованиям: М. процедура ;r(.s) монотонна по всем переменным при s еХ" ; С. функция л-(л-) непрерывна по всем переменным при .у е X" ; U. если обозначить s" -{а, ..., а), a e X, то к(s") = a {условие единогласия).

Было доказано, что Vp е Р1 существует эквивалентный прямой механизм.

В работе также используется представление ОМС в форме системы выбирающих коалиций (Barbera S., Gui F., Stacchetti E., 1993).

Система правых (левых) выбирающих коалиций для

X = [х,х] с К1 - это некоторое соответствие W , которое для каждого z e X определяет набор W(z) коалиций агентов, удовлетворяющих следующим условиям: принцип суверенитета; монотонность по коалициям; монотонность по результату; полунепрерывность сверху.

Любая система правых R(z) (левых L(z) ) выбирающих коалиций порождает ОМС х = /г( г) :

(2.2) й(г) = max {z s X | {/ € N [ t¡ > z} e Д(г)},

(2.3) (й(г) = min{z e ZI {/ e N \ т' < z} e L(z)j).

В разделе 2.2 вводится новое понятие — механизм на основе обобщенных линейных сверток. Обозначим i" - индекс агента i e N в упорядочении агентов по возрастанию значений s'. Если 3i,J e N

такие что s' =s' , то i' > f <=> i> j.

Определение 10. Механизм p =< X" ,7t(s) > является механизмом

на основе обобщенной линейной свертки (МОЛС), если л (s) = ^a's',

¡<sN

причем либо {a'},sN ={/П,еЛГ, либо {a'},vv = {/?'' },rV , где ]>>'=1,

teN

V/ &N р'> 0.

Если {се')1сУ = v : то МОЛС соответствует «классическому» механизму линейной свертки (Новиков Д. А., 1997). Если {or'}i>v = \jy }.e V , то МОЛС является анонимным.

Лемма 1. Любой механизм обобщенной линейной свертки при-

надлежит классу PI.

Откуда следует, что в соответствии с Бурков В.Н. и др., 1989, для любого MOJIC существует эквивалентный прямой механизм < X, h(j) > представимый как ОМС с a(S), S а. N \ 0 :

(2.4) a(S) = x + (x-x)^ р .

Соответственно, для анонимного МОЛС эквивалентный прямой механизм <X,h(t)> будет определяться ОМС, задаваемой п-1 числами:

(2.5) a(#S = k) = x + (I-x)^j3' .

В разделе 2.3 предлагается решение задачи активного однокри-териального коллективного планирования по критерию минимума погрешности манипулирования (1.2).

Бурковым В.Н. в 1989 было показано, что, если целевая процедура f : X" X является линейной сверткой, то решением задачи активного планирования в метрике L, является3 прямой неманипули-руемый механизм, эквивалентный механизму < X" ,f(s) > . В терминологии, введенной в данной работе, это означает, что линейные свертки как целевые процедуры обладают нередуцируемой погрешностью манипулирования. Однако данный результат не охватывал всего класса механизмов Р1.

Утверждение 1. Пусть целевая процедура планирования f(s) такова, что механизм < X", f(s) >е Р1. Тогда минимум погрешности манипулирования обеспечивает ОМС, в которой VS е 2'v \ 0 a(S) является решением уравнения

(2.6) 2 a(S) = f(L{S)) + f(I(S)),

l(S) = {Vi е S, s1 = a(S)л Vz e W \ S, s' = x}, s(S) = (V/ e S, s1 = x л V/ gN\S, s1 = a (£)}.

Следствие 1. Если целевая процедура планирования — анонимная, то решением задачи активного планирования будет анонимный механизм.

Следствие 2. Только обобщенные линейные свертки обладают нередуцируемой погрешностью манипулирования.

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

Утверждение 2. Пусть задано ограничение на допустимый «вес» сообщения агента - Vie N а' е[а;¿г]. Тогда минимальной погрешно-

3 Нетрудна показать, что для однокритериалыюго планирования минимум погрешности манипулирования в любой другой «выпуклой» метрике совпадает с минимумом в Ь)

4 тес1(п) - медиана ряда {1,...,п}. Для нечетных п тес!(М)=[п/2]+1, для четн1}1£

стью манипулирования обладает анонимная обобщенная линейная

свертка /?' =/?, г е N \ {к}, Р"=Р, где Р = тах{а,-——}, - - п -1

Р = 1 - (и - \)Р, к = мес!(Ы) 4.

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

(2.7) А = р[п/2](1-р[п/2])(х-х).

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

В разделе 2.4 исследуется вопрос эквивалентности различных механизмов однокритериального коллективного планирования. Анализ эквивалентности разных механизмов производится на основании сопоставления эквивалентных им прямых механизмов. Утверждение 3. Для любого анонимного механизма

< Х",л(я) >е Р1 существует эквивалентный МОЛС, определяемый следующим набором весов:

(2.8) )3'=(я(5(/-1))-»(л(0))/(Зс-х),1е{1,...,и},

где набор заявок л (/) состоит из / сообщений х и п - г сообщений х .

Следствие 3. Для неанонимного механизма < X", 7т(я) >е Р1 существует эквивалентный МОЛС, если V/ е N , У Б с N \ {;'} л-(5(5 и {/})) -яг(5(5)) = а', где 5(5) = {V/ е 51= х, V/ е N \ 51= х} . При этом процедура линейной свертки в МОЛС будет иметь вид

16 Л'

Из утверждения 3 и следствия 2 следует, что если в задаче активного коллективного однокритериального планирования к механизму предъявляется требование анонимности, то решение достаточно искать на классе МОЛС.

Глава 3 посвящена рассмотрению типовой задачи активного индивидуального планирования в ОС с НТП - задачи распределения ресурсов.

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

Задачей индивидуального однокритериального планирования считается задача индивидуального планирования, в которой — \ZigN ГсЕ1. Задача распределения ресурсов рассматриваются в следующей постановке. Организационная система состоит из одного центра и

4 тес!(п) - медиана ряда {1,...,п}. Для нечетных п те<1(Ы)=[п/2]+1, для четных тес!(М)Е{п/2, п/2+1}, где [а] обозначает целую часть д.

множества jV = {1,...,и} агентов. У центра имеются ресурсы в ограниченном количестве - ReR\, которые могут быть распределены между агентами. Необходимо найти механизм распределения ресурсов, максимизирующий значение некоторого критерия эффективности ОС К . Предпочтения каждого агента i е N относительно количества выделяемых ему ресурсов х е [О, Л] определяются однопиковой функцией и : -» Е1, определенной в главе 2, где г' > 0 . Считается, что предпочтения агентов не известны центру. В случае, когда ^ г' > R , имеет

место дефицит ресурсов.

Для распределения ресурсов центр использует механизм планирования х = n(s), определяя итоговое распределение ресурсов

х = {*,,..,*„}, x¡ > 0, е [0, /?] на основании сообщений (заявок)

/6 у

агентов = {s,,..,sj , л\ е S] , i e N, где S¡ - множество допустимых заявок i-го агента. Если в качестве сообщения агента просят сообщить значение своей точки пика, то такой механизм является прямым.

Определение 11.(Бурков В.Н. и др., 1989; Sprumont Y., 1991; Barberá S., Jackson M., Neme А., 1997) Прямой механизм последовательного распределения ресурсов (МПРР) - Vz е [0,7J] V/ е N определяются q'(-,z):2N\0 ~>[0,z], такие, что V5e2A'\0: ^9'(5,z) = z;

íeS

Vi g S q'(S,z) > q'(S,z) .

А ресурс R между агентами распределяется по следующему итерационному алгоритму:

Шаг 0. Агенты сообщают г,, множество диктаторов Ко=0, множество «неудовлетворенных» агентов N0~ N, доступные к распределению ресурсы Rq= R . Номер шага / = 1.

Шаг í¡. N, = \ K,_t , К, = {/ б N,: г' < q¡ (N,, )},

Шаг /2. Vi еК, х ~ т'. Если K¡ = 0 , то алгоритм останавливается, и VUN, х1 =q'(Nl,Rí_í).

Шаг l3. R, = - 1 = 1+1. Переход на шаг /,.

ык,

В работах Буркова В.Н. и др., 1989; Sprumont Y., 1991; Barberá S., Jackson M., Neme А., 1997 было показано, что любой неманипулируе-мый, эффективный по Парето и монотонный в группах5 механизм распределения ресурсов - это МПРР. Более того, Бурковым В.Н., 1989, было показано, что для любого механизма распределения ресурсов,

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

удовлетворяющего указанным выше требованиям, существует МПРР не меньшей эффективности. Sprumont Y. в 1991 показал, что существует единственный анонимный МПРР, удовлетворяющий описанным выше требованиям - т.н. единое правило (uniform rule, UR). Новиков Д. А. в 1997 показал, что любой анонимный механизм распределения ресурсов, удовлетворяющий указанным выше требованиям, эквивалентен UR. Однако аналитической формы записи МПРР построено не было.

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

Определение 12. (Бурков В.Н. и др., 1989) Приоритетным называется механизм распределения ресурсов:

s', если ^V < R .

(3.1) *'(*) = ] f ■/ -м '

minis', у7]' (V Н, если ¿^s' > R

где {77'(s')}/e,v - функции приоритета агентов, у - некоторый нормировочный параметр, обеспечивающий выполнение условия х' = R .

ieN

Приоритетные механизмы делятся на три подкласса:

1. прямых приоритетов - dT]'(s')/ ds' >0 W е S' и VieN;

2. обратных приоритетов - dTj'(s')/ds' < 0 Vs' е S' и Vi с N ;

3. абсолютных приоритетов — drj'(s')/ds' =0 W eS" и V/ е jV .

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

Определение 13. Механизм взвешенного пропорционального распределения ресурсов - механизм прямых приоритетов с функциями

приоритетов fj'(s') = A's , А' >0 i <z N .

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

В разделе 3.2 доказывается, что любой неманипулируемый механизм распределения ресурсов представляется в виде минимаксной схемы, аналитическая запись которой аналогична аналитической записи неманипулируемых механизмов однокритериального коллективного планирования в ОС с НТП:

Утверждение 4. Любой МПРР представим в виде:

(3.2) х' = min (г', max q'(S,R(S))}, ieN ,

v ' ScN-.ieS

где ВД = Я - £ , (•): 2" \ 0 х [О, Л] -> [О, Л], причем

УБ,Уе 2"\0, Уге[0,Д]: (■!?.*) = г ; Зд'^.г)/& > О ;

если 5 с К то = едк.г) =

В разделе 3.3 рассматривается задача активного однокритери-ального индивидуального планирования по критерию минимума погрешности манипулирования (1.2). Приводится решение задачи для анонимных процедур распределения ресурсов.

Утверждение 5. Пусть в задаче распределения ресурсов целевая процедура планирования / - анонимная. Тогда решением задачи активного однокритериального коллективного планирования по критерию минимума погрешности манипулирования является 1Ж. При этом погрешность манипулирования составляет

ДДр) = 2 —Л. п

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

Утверждение 6. Пусть в задаче распределения ресурсов целевая неанонимная процедура планирования / такова, что V/ е N возможно,

чтох" = Я. Тогда решением задачи активного однокритериального коллективного планирования по критерию минимума погрешности манипулирования является 1Л1. При этом погрешность манипулирова-

. . . „п—1„

ния составляет Д Ар) - 2-Я .

п

В разделе 3.4 исследуется вопрос эквивалентности различных процедур распределения ресурсов. Результат об эквивалентности анонимных процедур распределения ресурсов, полученный ранее Новиковым Д.А. и Бргитощ У. распространяется на неанонимные приоритетные механизмы.

Утверждение 7. Для любого механизма прямых приоритетов, задаваемого функциями приоритетов Ц Т' {/), ¡с N, при заданном количестве распределяемых ресурсов существует эквивалентный механизм взвешенного пропорционального распределения ресурсов, задаваемый следующими функциями приоритетов: - Л'У, где

(3.3) ^ =пГ (Я), .

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

{б'), /еЯ. Обозначим через У* (5), 5 с N, /е5 решение

системы уравнений У * (S) = ц 4' (У * (S))Ä(S) / £ 1 ^ '' * > 'е 5 »

jeS

R(S) = Д - X • Обозначим Z?'(S) = <У *(S)) •

Определение 14. Механизм обратных приоритетов с фиксированными весами агентов - механизм обратных приоритетов, удовлетворяющий условию VS с ЛГ, V/ е S B'(N) / Д' (S) = D(S), где D(S) зависит только от множества 5 и количества ресурсов R(S).

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

T]V (s') = B'(N)s', ieN.

Следствие 4. Механизм линейных обратных приоритетов с функциями приоритетов tji' = В' -a's', а' > 0 , i е N является механизмом

с фиксированными весами только при а' = a Vi с jV . В этом случае он эквивалентен пропорциональному механизму с функциями приоритетов rjV (s') = B's'.

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

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

В разделе 4.1 вводятся основные понятия и определения. Многокритериальное планирование - Хсй", m е N . Будем обозначать M - {1 ,...,т} - множество критериев. Обозначим проекцию X на критерий k е M как Хк, min Хк - минимальное значение проекции, хк = тах Хк - максимальное. Тогда минимальный контейнер

для X - В(Х) = • Множество В(Х)\Х назовем множеством

ЬеМ

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

Предпочтения агента ieN и': ПуХ -> S' называются многомерно однопиковыми, если Vaeß существует единственная точка пика

r'=argmaxMf(*)H Vz.z'eJ, из [z'e£({z, г(и')}) и z * z'] следует [

хъХ

u'(z') > u'{z) ]. Класс многомерно однопиковых предпочтений будем обозначать U". Проекцию точки пика агента ie N на критерий k е. M будем обозначать х'к.

Механизм —> эквивалентен механизму Ф Прямых приоритетов Обратных приоритетов

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

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

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

Таблица 4. Отношение эквивалентности между приоритетными механизмами

Barbera S., Massó J., Serizawa S., 1998, показали, что если предпочтения агентов — из U™, а X с 3:"' — компакт, то процедура коллективного выбора неманипулируема тогда и только тогда, когда она является обобщенной медианной схемой обладающей свойством пересечения. Для т > 2 обобщенная медианная схема может быть представлена в виде:

(4.1) хк - min (max(at(5),r¿)) , / е N , / е М

SQjV-.ieS

где ак (5) е Хк — параметры настройки механизма, определяемые для каждой из возможных групп агентов S q N \ 0 , причем ak(S)> ак (S) при S czS. Если ак (5) не зависит от того, кто именно из агентов входит в группу S, а зависит лишь от числа агентов в группе # S , то правило является анонимным по критерию /. Многокритериальная ОМС является анонимной, если она анонимная по всем критериям. ОМС называется симметричной, если \/{k,k} е М х Ai , V S с N \ 0 ak{S) = a-k{S).

В дальнейшем в работе используется представление ОМС в виде семейства W систем правых (левых) выбирающих коалиций - набора , где IVk - система правых (левых) выбирающих коалиций, определяющих ОМС для критерия ieM . Соответственно, многокритериальная ОМС х - /г(г), порождаемая семейством систем правых (левых) выбирающих коалиций R (L) записывается следующим образом:

(4.2) hk(r) = max{zeXk\{ieN\r'k>z}<=Rk(z)}, keM

(4.3) (hk (г) = min{z е Xt \ V eN\r'k<z}e Lk(z)}, keM).

Для произвольного семейства систем правых выбирающих коалиций R будем обозначать L* — соответствующее ему семейство систем левых выбирающих коалиций, в котором У к е М :

(4.4) L'k(z) = {tV s2N |Vz' E(z,X]b,W'eRk(z'),Wr\W' = 0}.

Семейства R и L* порождают эквивалентные ОМС. Многокритериальная ОМС является сепарабельной, т.е. результат

по каждому критерию определяется независимо - h(т): X" —> В{Х). Поэтому в случае, когда В{Х) -t- X , возможно, что даже при reí" некоторые ОМС будут давать недопустимые планы — А (г) g X. Как следствие, такие ОМС будут недопустимы в качестве механизма планирования для множества планов X . Свойство пересечения является необходимым и достаточным условием того, что ОМС всегда будет определять допустимые планы при re А" — является допустимой для X (Barbera S., Massó J., Neme A., 1997):

ОМС, порождаемая семейством систем правых выбирающих коалиций R, удовлетворяет условию пересечения для некоторого X , если Vу е В(Х) \X и для любого конечного множества {z ,...,z } с: X верно,что:

(4-5) П

U h (Ук)

teM*iy,z')

и

и i (л)

1!Г(уУ)

для любого подмножества агентов rk (ук) е Rk (ук) с /: е | М (_y,z') и любого подмножества агентов lk (ук) е L'k (ук) с к е [J ;=| M+(y,z'), где

М* (у, х) = {кеМ: хк > ук}, М~(у,х) = {к е М: хк < ук}.

Barbera S., Massó J., Neme А. в 1997 показали, что для каждого у е В{Х)\Х условие (4.5) достаточно проверять лишь для одного конкретного, существенного множества {z',...,zr} а X . Конечное множество S а X является существенным для у е В(Х)\Х если: l.Vz.zeS, z±z M\y,z)(£ M+(y,z) или M'(y,z) d M~(y,z);

2. Vx e X \ S 3z e S : Mf (7, z) с M+ (y,x) и AT (y, z) с M~ (y,x) .

Однако, проверка условия пересечения затруднительна, если множество недопустимых планов В(Х) \ X является непрерывным, т.к. требует проверки всех недопустимых планов (которых бесконечно много).

В разделе 4.2 предлагается блочный метод анализа выполнения условия пересечения ОМС для множества допустимых планов X , позволяющий осуществлять проверку конечного числа элементов

множества В(Х) \ X . В основе метода лежат понятия блока и направления.

Из определения ОМС следует, что V/ е М существует конечное множество {z\,z],...,zlk} а Xk, 4 = £t> zl" ~ хк мощности wk < 2" +1 , такое, что для любых 1 < wk < wk:

1. Rk{zk) = Rk{z^1), L\{zt) = L\(z?y,

2. Vzt < z? Rk (zk) с Rk (z?), L\ {zk) => L\ {z?);

3. Vz4 > z? Rk(zk) 3 Rk(zk'"), L'k(zt)cz L\(z? ) .

Эти множества определяются исключительно системой выбирающих коалиций для соответствующего критерия. Обозначим W = { w = (w,,.., wk): Vk е М I < wk < wk }.

Блоком назовем подмножество В{Х), определяемое следующим

т

образом: Вп, = >2Г'+']> w е w - Любая ОМС, задаваемая на множе-

*г =1

стве В(Х), порождает его блочное разбиение Bw = {5„.}„,бН,. По построению данного разбиения видно, что [J Bv = В(Х).

не»'

Блок Bw е В„. называется граничным, если Вп п!#0 и В.л. Г\ В(Х) \ X ф 0. Множество всех граничных блоков для X будем обозначать Bw (cIX).

Определим, что ОМС удовлетворяет условию пересечения для X в блоке Bw е Bw если \/у е Bw п В(Х) \Х и для любого конечного множества {z',...,zr} с X выполнено (4.5).

Лемма 2. Семейство R = {Rk }™=, правых выбирающих коалиций разбивает В(Х) на набор блоков В„,. Тогда, если V#u е Bw , У у е int Bw существуют ГсМ, М*,М; сМ , tcT, rk(yk)e Rk(yk), к еЦм; ,

1еТ

h (л) е L'k (v,), л G U М, такие, что:

тТ

п

и 'Дл)

и

II 1-м

= 0,

то М2 е £„. так же найдутся гк (гк ) б Кк (гк) , к е У М* , 1к(гк) е Ьк (гк),

к е У М, такие, что: Р|

и

и '*<**)

= 0 .

Из леммы 2 следует, что условие (4.5) достаточно проверять лишь для одного произвольного у е ¡т Ви, для каждого блока ВК, такие что п В(Х) \ X 0, для того, чтобы определить, удовлетворяет ли ОМС

условию пересечения для X .

Однако открытым остается вопрос, какую комбинацию правых и левых выбирающих коалиций следует проверять для каждого блока В , т.к. введенные выше существенные множества могут быть разными для разных у е Ви. п В(Х) \ X . Для ответа на данный вопрос используется понятие направления.

Для У {у, г} е к" направление от у к г -вектор с/(у, г) е 3 , где с!к(у,г) = 1 если >>,, <г,, с1к(у,г) = -1 если ук>гк, Ык(у,г) = О если ^ = 2к. Будем обозначать с! к (.у, г) - направление от у к г по всем критериям за исключением ке М. С помощью подобных векторов удобно описывать положение двух элементов в пространстве М™ по каждой из координат (критериев в нашей терминологии) в терминах: левее (-1), правее (1) и совпадают (0).

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

допустимых планов. Обозначим с1Х{у) = {ге с1Х: В(г,у)г\Х = г}.

Определение 15. Вектор ре 3м является направлением от уеКга\АГ к ЛГсГ, если 3г ес1Х(у):Ы(у,г) = р и если Зк е М :рк = 0, то -Зх е с!Х(у): с1_к(у,х) = р_к, ¿к(у,х) Ф 0 .

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

множеству допустимых планов. Обозначим В(у, X) = {р е 3 : р является направлением от уеК^Х к -Г с: Е'" } - множество всех направлений отуей"\1 к Хсй". Форма множества X определяет, существует ли >>е В(Х)\Х такой, что ИВ(у,Х)>\. Множество планов X будем называть блочно-выпуклым, если Уг, г е X В({г,г})г>Х * {г,г}. Очевидно, что любое выпуклое компактное множество является блочно-выпуклым.

Лемма 3. X - блочно-выпуклое о Уу е В(Х)\Х , 1.

Для любого блока Вк е Вп. такого, что Вп п В(Х) \ X * 0, определим множество направлений от Ви к X с: К" как 0(В„,Х) = {П(у,Х)}^ВпШ)хх.

Блок IIи, е В№ такой, что Вк п В(Х) \ X ф 0, будем называть плохим, если Эу е Вн, пВ(Х)\Х такой, что #В(у,Х) > 1. Множество всех плохих блоков будем обозначать ВВИ, (X).

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

Лемма 4. Семейство R = }"_, систем правых выбирающих коалиций, определяемое на В(Х) порождает ОМС, обладающую свойством пересечения для 1с1" тогда и только тогда, когда ЧуеВЮХХ^гМеЪЫ, кеМ'(у,Х), \/!к(ук) е Гк(ук),

кеМ+(у,Х):

(4.6)

П Цу)

кеМ'(у.Х)

п

*0,

п rt(y)

Jebf-(y.X)

M+(y,X) = {keM:3deD(y,X),dk=l}H М'(у,X) = {kGM:3deD{y,X), dk=-1}. Благодаря данной формулировке условия пересечения, можно выявить дополнительные свойства ОМС, позволяющие упростить условия проверки ее допустимости для некоторого JcÄ".

Лемма 5. (Монотонность условия пересечения по планам) Vy е В{Х) \ X: # D(y, X) = 1, если семейство R = {Rk систем правых выбирающих коалиций, определяемое на В(Х) порождает ОМС, удовлетворяющую условию пересечения для IcS" в у, тогда эта ОМС будет удовлетворять условию пересечения для в

Vz еВ(Х)\Х: d(z,у) = d{y,X) и #D(z,X) = 1

Из леммы 5 следует, что для всех блочно-выпуклых X с К"' достаточно проверять условие (4.5) для недопустимых планов, находящихся как можно «ближе» к cl(X). Т.е., с учетом блочного разбиения, достаточно проверять по одной альтернативе из каждого граничного блока. Формально это записывается следующим образом.

Утверждение 9. Семейство R = {Rt}™^ систем правых выбирающих коалиций, определенное на ¿(X) порождает ОМС, удовлетворяющую условию пересечения для X , если УВК е Bw (clX) и BBW (X) для одного выбранного произвольным образом у е int Вн, выполняется:

УйеО(Вп,Х) Угк(ук)еЯк(ук), кеМ~(0), У1к(ук) £ 1'к(ук),

п !к (У) п л г, (у)

АГ (£) = {£ е Л/:Зй?е Д</, =1} иМ"(0) = {ИеМ:3(/еД(/,=-1}.

На основе этого утверждения строится алгоритм проверки допустимости произвольной ОМС для некоторого множества допустимых планов X . Максимальное число проверяемых условий вида (4.7) - не более 2("+|,/" ((2п)т в случае анонимной ОМС).

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

Механизм многокритериального планирования < X",71(3) >, называют сепарабельным (Б), если план по каждому критерию не зависит от сообщений агентов по другим критериям - Ук е М хк = л:к {хк). Класс механизмов, обладающих свойством Б, в которых \!к е М 7Тк ) удовлетворяет условиям М, С, и (определенным в разделе 2.1), обозначим Рш . Множество допустимых планов X является прямоугольным, если X = В(Х).

Утверждение 10. Пусть множество допустимых планов X — прямоугольное. Для механизма планирования < X" > существует эквивалентный неманипулируемый механизм тогда и только тогда, когда < Х",л(з) >е Рш.

Утверждение 11. Пусть механизм планирования < А"' ,7г(х) >е Рш манипулируем. Тогда для него существует эквивалентный неманипулируемый механизм только если X — прямоугольное.

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

Утверждение 12. Пусть целевая процедура планирования

такова, что механизм < X", /(.$) >е Рт, а X - прямоугольное. Тогда минимум погрешности манипулирования обеспечивает ОМС, в которой е 2Л \ 0 ак (5), к е М является решением уравнения (4.8) 2ак (<>) = (¿(5)) + /к (5^(5)),

где = =&} и

.V, (5) = {V/ е 5, = I, л V/ е N \ 5,= ак (5)}.

Следствие 5. Если целевая процедура планирования — анонимная, то решением задачи активного планирования будет анонимный механизм.

Для многокритериального коллективного планирования существенную роль так же играют обобщенные линейные свертки. Обозначим - индекс агента / е N в упорядочении агентов по возрастанию значений ^ , ке М . Если 3/,_/ е N т.ч. = я/, то Г > уг о /' > у.

Определение 16. Механизм р=<Х",ж(з)> является механизмом на основе многокритериальной обобщенной линейной свертки (ММОЛС), если \ZieA/ = , где либо {а'к = \рк}.с „,

/е/У

либо ки = {< и,

.v

Утверждение 13. Если X — прямоугольное, то только механизмы на основе многомерной обобщенной линейной свертки обладают нередуцируемой погрешностью манипулирования.

Утверждение 14. Если X — прямоугольное, то для любого анонимного механизма <Х",л(8) >еРт существует эквивалентный ММОЛС, определяемый следующим набором весов:

/е{1,...,«}, кеМ, набор заявок (/) состоит из < сообщений х, и п - / сообщений хк.

В разделе 4.4 задача распределения ресурсов формулируются и исследуются как задача активного коллективного многокритериального планирования в ОС с НТП в условиях заинтересованности агентов в результатах планирования по всем критериям.

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

Обозначим множество проектов — М, #М = т, множество агентов И, = п , множество допустимых вариантов распределения

т

ресурса - X -{х = е | <Щ.

У=1

Заинтересованность (предпочтения) агентов описывается их многомерно однопиковыми функциями полезности и'(х): X —> Я,, / е N .

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

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

Утверждение 15. Vт,п> 1 симметричная и анонимная ОМС реа-

т

лизуема для X - {х = (х1,...,хя) е Л* | ]Гх] < К] тогда и только тогда,

м

когда задающая ее система правых выбирающих коалиций 9?(г) разГ и-1 "

бивает отрезок [О, Я] н& более чем на к =

+ 1 частей отрезками

{2,^,2,], 1 е {п-к + \,...,п}, гп_к =0, га = Л . Причем:

1. VI е{п-к + 1,...,п}, УБеЩг,) #5>/ и У/б(гн,г,] 9?(г) = 9? (г,).

т т

2. Для любого т.ч. ! < У? 5 но >Я необходимо, чтобы

т

^ > {т - 1)я +1.

Следствие 6. При т > п > 1 существует единственная симметричная и анонимная ОМС, допустимая в качестве неманипулируемого механизма распределения ресурсов: УуеМ х! =тш|г)1(( .

Следствие 7. При т = п > 1 симметричная и анонимная ОМС допустима в качестве неманипулируемого механизма распределения ресурсов, если описывающая ее система правых выбирающих коалиций удовлетворяет следующим требованиям: Уге(0,2„_,] < Я / т , Щг) = с N | #5 > »-1}.

Следствие 8. Если симметричная и анонимная ОМС допустима в качестве неманипулируемого механизма распределения ресурсов при определенных т и п , то она так же является допустимой при любом т < т и том же п .

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

Утверждение 16. Ут > 3 , V« > 2 3 г е X" т.ч. V/ е N X гу = Л '111,151

которого любая реализуемая симметричная и анонимная ОМС в качестве итогового распределение ресурсов будет давать V/ е М X; = 0.

Иными словами, неманипулируемые механизмы не допускают распределения ресурса в ситуациях «сильного» разногласия агентов. В частности, при т > п > 1 ресурсы распределяются полностью только в ситуации единогласия — V/ е N х = г'.

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

зуемая в механизме распределения ресурсов процедура многокритериального коллективного планирования (в том числе, симметричная и анонимная) — манипулируема, то для этого механизма не существует эквивалентного неманипулируемого механизма.

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

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

Множество анонимных неманипулируемых механизмов. Существует единственный анонимный нема-нипулируемый механизм - uniform rule. Множество неманипулируемых механизмов зависит от т,п . Только при т>п> 1 неманипулируемый механизм единственный.

Эффективность решения задачи распределения ресурсов. При дефиците весь ресурс распределяется полностью, распределение оптимально по Парето. Распределение не является оптимальным по Парето, ресурс распределяется полностью не всегда. При т > п > 1 ресурс распределяется полностью только в ситуации единогласия.

Таблица 5. Сопоставление неманипулируемых механизмов распределения ресурсов

Глава 5 посвящена рассмотрению задач распределения ресурсов и затрат как задач активного многокритериального смешанного планирования в ОС с НТП.

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

Обозначим М' с М - подмножество критериев, в результатах планирования по которым заинтересован агент / е N . Будем рассматривать задачи активного планирования, в которых предпочтения агентов являются многомерно однопиковыми на X' = Хк. Обозначим класс таких функций предпочтения через 0™. Очевидно, что

и™ с. 0™.

Для формализации «безразличия» агента г е N к результатам планирования по критериям из М\М' важным является понятие одномерной функцией предпочтения с одним плато — это отображе-

ние v'-.E1 -»К1, в котором Vi е N 3 ![г ; г, ] = Л rg max v' (х) и Vz,z' е R1

ЛЕЯ'

выполняется: если г' > z > z ', то v' (z) > v' (z'), если z > z ' > T', то v(z)<v(z').

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

Если обозначить множество всех функций предпочтений с плато как П , то компонента правила устранения многозначности t : П" ~> R" для агента i е. N - это функция /' : П" -» Ж1, такая, что

1. Vveir i'(v)e[l';f];

2. Vv 6 П" если V/ е N A rg max v' (х) = Arg max v' (x), то t' (v) = t' (v).

дге-Ч1 ï6-<'

Можно считать, что Vie N и V/t e M \ M' задана одномерная функция предпочтений с одним плато щ т.ч. =

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

Определение 17. Функция делегирования — отображение

f.Ü; -> X" такое, что VueÜ'tn V/ е N V/fc е Al' t'k(u) = r[, причем Vm е Uk такого, что т = г У к е M выполняется t\ (и) -1[ (и).

По сути, любая функция делегирования определяет для каждого агента i е N его заявку по критериям из M ' на основании значений точек пиков всех агентов.

В случае, когда хотя бы для одного из агентов i е N (быть может даже не известно какого) M 'cz M, будем говорить о гарантированном делегировании. Уровнем делегирования будем называть величину

ц = тт(/н-от'), где т' = #М'. В случае, когда Vie NM' задано

v'fc.V

априори, будем говорить о детерминированном делегировании.

В разделе 5.2 показывается, что любой механизм последовательного распределения ресурсов представим в виде ОМС, дополненной процедурой делегирования.

Задачи распределения ресурсов и затрат как задачи индивидуального планирования могут быть формализованы как частный случай задачи смешанного планирования следующим образом. Множество критериев планирования совпадает с множеством агентов - M = N , и наблюдается случай детерминированного делегирования V/eiV

М '={/} с уровнем делегирования ц = т-1. Это позволяет доказать следующее утверждение.

Утверждение 17. Пусть МПРР п(т) описывается набором функций \0х[О,Л]->[О,Л], г е N . Эквивалентным ему является ОМС /г(г), дополненная правилом устранения многозначности:

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

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

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

Следующее утверждение описывает допустимые правила делегирования.

Утверждение 18. В симметричной анонимной ОМС, применяемой как механизм распределения ресурсов, любое правило делегирования должно быть представимо в виде — V/ е N \/к е М \ М'

Где хк определяется только на основании сообщений агентов из Мк с помощью анонимной однокритериальной ОМС, а к' - номер проекта из М \ Мк в упорядочении по возрастанию хк.

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

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

Утверждение 20. Для произвольных т,п>2 при гарантированном делегировании с уровнем ц, допустимыми в качестве механизмов распределения ресурсов являются ОМС, которые допустимы - без гарантированного делегирования при том же п и т = шах {т, т +1 - ц}.

Доказанные утверждения позволяют сделать вывод о том, при каких условиях неманипулируемые анонимные и симметричные механизмы распределения ресурсов являются эффективными по Парето.

(5.1)

(5.2)

А, (г) = тах е [О, Я] | У е N | г/ > г} е 9?, (г)}, г^К , Я, (г) = {5 и {¿}: 5 с ЛГ \ {/} л \ 5, Я) > г}, // = тт{т', шах ^'(^(Я))}, /е АЛ{/},= т'.

г;=тш{^, л,■-][>/ /(пг-т'-к')}, Ук е М' = г[.

V /-=*' у

Следствие 9. Механизм распределения ресурсов на основе симметричной анонимной ОМС с делегированием может быть Парето-эффективен для любых /и > 3, л > 2 только при ц = т-1.

Глава 6 посвящена рассмотрению задачи распределения ресурсов как активного многокритериального коллективного планирования в ОС с НТП в условиях, когда заинтересованность агентов в результатах планирования не может быть описана многомерно однопиковыми функциями предпочтения.

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

Рассматривается постановка задачи распределения ресурсов, сформулированная в разделе 4.4. в предположении, что предпочтения агентов не являются многомерно однопиковыми. Описывается класс

многомерно однопиковых в пропор1{иях функций С/™ .

Показывается, что если в рамках задачи распределения ресурсов, сформулированной в разделе 4.4, предпочтения агентов принадлежат классу и^, то задачу можно рассматривать «в пропорциях», где предпочтения агентов многомерно однопиковые.

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

В разделе 6.2 описывается класс неманипулируемых механизмов распределения ресурсов для предпочтений 0"

Показывается, что неманипулируемым является любой механизм вида < > , где: / е М — базовое направление;

Х[/] = [хХИхЩ ~ область допустимых значений пропорций,

хЩ,хЩ задают соответственно минимально и максимально возможную пропорцию отношения ресурса, выделяемого для направления / относительно /; процедура йт: Х[/]" —> X : х1-Ях]1^Хк->

кеМ

/' е М, определяющая полное распределение ресурса на

т

X = {х = еЯ^ | ^X] = /?}, в которой для базового направле-

м

ния /еМ X/ = 1 > а Х-/ определяется из некоторой ОМС я: Х[/]" Х[/].

Утверждение 21. Механизм <Х[/]",/?гг > является неманипулируемым, если предпочтения агентов принадлежат классу ¿7™, а л-: Х[/]я -> Х[/] - ОМС. 38

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

Утверждение 22. У{1,к} е М2 не существует пары ОМС {к, таких, что механизмы <Х[/]"Л > и < > эквивалентны.

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

Утверждение 23. Если предпочтения агентов принадлежат классу

0™ , то любой неманипулируемый механизм, обеспечивающий полное распределение ресурсов представим в виде механизма <Х",И>, определяемого набором ОМС {*■[/]},и набором весов {«,},бМ :

Показывается, что реализация произвольного механизма < X",И > возможна лишь при выполнении гипотезы полной заинтересованности.

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

В разделе 6.3 результаты, полученные для ОМС в главе 4, распространяются на неманипулируемые механизмы при многомерно однопиковых в пропорциях предпочтениях агентов. Определяются условия, когда решение задачи активного планирования достаточно искать на классе неманипулируемых механизмов. Определяются процедуры планирования, представимые в виде ММОЛС в пропорциях.

В разделе 6.4 задача активного планирования решается для распределения ресурсов между тремя агентами = Ъ) с предпочтениями из класса О™ и целевой процедурой планирования, являющейся

1 ^ ,

усреднением их точек пика - х = — ¿^ г .

Глава 7 посвящена рассмотрению отдельных задач активного планирования в ОС с ТП. В разделе 7.1 вводятся основные понятия и определения: квазилинейные функции полезности, трансферы, механизмы с трансферами, допустимые трансферы, сбалансированность трансферов.

В разделе 7.2 рассматривается задача эффективного однокрите-риального коллективного планирования, в которой функции полезности агентов принадлежат классу И\, ХсМ',а критерий эффективности - максимум суммарной полезности общества:

(6.1 /■(и)еЛгепмх5у(*)-

хеХ

Исследуются следующие механизмы планирования р=< Б, {х,1} >.

$ = 51' = К1 ~ действие любого из агентов - заявка из I1;

(6.2) = ~ план определяется как среднеарифметическое заявок агентов;

(6.3) £>'(•*) = /?(*(•*)--О2, /е N - для каждого агента определяется штраф за разногласие, вычитаемый из полезности агента, с силой штрафа р > О, на основании которого для каждого агента рассчитывается трансфер полезности'.

(6-4) ''"(*) =/(*)--]•>'(*),

П

где параметр а <=. [0; 1] удобно трактовать как бачансировочный коэффициент, так как при а = 1 трансферы всегда сбалансированы:

п

УяеЯ^/,(■*) = 0. 1=1

Доказывается, что предлагаемые механизмы реализуют эффективное решение по Нэшу.

Утверждение 24. Если предпочтения агентов принадлежат классу и\ и являются вогнутыми кусочно-гладкими, то

1. Vа е [0;1], У р > 0 механизм р(а,Р) всегда обеспечивает решение задачи максимизации суммарной полезности общества;

2. \/р> 0 только при а = 1 механизм р(а, Р) обеспечивает сбалансированность трансфертов и является гарантированно индивидуально-рациональным.

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

Показывается, что механизм Гровса-Лейдярда (Сгоуез Т., 1хс1уагс11, 1977) принадлежит описанному классу механизмов.

В разделе 7.3. рассматривается задача распределения ресурсов. Результативность подхода к синтезу эффективных механизмов распределения ресурсов путем представления задачи многокритериальной активной экспертизы, предложенного в разделе 5.2., иллюстрируется за счет адаптации механизма, описанных в разделе 7.2. к решению задачи максимизации суммарной полезности всех агентов от результатов планирования и обеспечивающих сбалансированность трансфертных платежей. Рассматривается постановка задачи распределения ресурсов, сформулированная в разделе 3.1. в предположении, что критерием эффективности распределения ресурсов является значение суммарной полезности всех агентов, а сами функции полезности агентов не являются однопиковыми, но квазилинейными. Доказывается, что полученный механизм реализует эффективное распределение ресурсов по 40

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

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

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

Глава 8 посвящена описанию применения полученных теоретических результатов для решения отдельных прикладных задач. В разделе 8.1 приведены основные общие практические рекомендации по выбору процедур планирования, которые следуют из теоретических результатов, полученных в данной работе для задач экспертизы и распределения ресурсов.

В разделе 8.2 рассматривается ряд задач, связанных с реализацией технологий сетевой экспертизы, а также уточняется специфика сетевой экспертизы как задачи активного планирования в рамках классификации видов манипулирования, введенной в разделе 1.2. На основе FHG-модели (French J., 1956 - Harary F., 1959 -DeGroot M., 1974) социальной сети приводится оценка погрешности результатов сетевой экспертизы, получаемых как консенсус в сетевом сообществе экспертов. Решается задача минимизации полученной оценки.

Исследуется проблема определения значимости мнения эксперта, одним из распространённых подходов к решению которой является «ретроспективный», динамический подход ~ когда значимость мнения в рамках конкретной экспертизы определяется на основании истории участия эксперта в проводимых ранее экспертизах. Показывается, что при определенных условиях, для обеспечения неманипулируемости механизмов сетевой экспертизы не допустимо применение методов определения значимости мнения отдельного эксперта на основе истории его участия в предыдущих экспертизах. Описанные модели применялись при внедрении технологий сетевой экспертизы в ряде рос-

сийских компаний. В разделе 8.3 описан комплексный подход к созданию систем управления инновационным развитием регионов, муниципальных образований, отраслей и предприятий на основе принципов программно-целевого управления, математические методы решения задач управления, возникающих при его реализации и комплексный механизм управления реализацией программ развития. С помощью методов когнитивного моделирования, и комплексного оценивания предлагается формализация объекта управления в виде трехуровневой ОС. Используя полученную модель ОС, указывается, какие задачи активного планирования возникают на каких этапах управления программой развития и какие теоретические результаты настоящей работы могут быть использованы для их решения. Элементы описанного комплексного подхода были реализованы при разработке и модернизации систем управления территориальным развитием выполнявшихся ИПУ РАН и ряде российских компаний и корпораций.

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

Основные результаты и выводы

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

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

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

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

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

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

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

для задач:

1.1. распределения ресурсов в случае индивидуального планиро-

вания;

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

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

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

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

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

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

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

Получено аналитическое решение задач активного планирования для:

3.1. однокритериального коллективного планирования;

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

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

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

5.1. однокритериального коллективного планирования — это процедуры на основе обобщенных линейных сверток;

5.2. многокритериального коллективного планирования - это процедуры на основе многомерных обобщенных линейных сверток;

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

Конструктивно установлены соотношения эквивалентности между неманипулируемыми механизмами планирования и «простыми» в реализации механизмами планирования:

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

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

и механизмами взвешенного пропорционального распределения ресурсов.

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

Эффективность практического использования полученных теоретических результатов при решении ряда прикладных задач:

• анализ проблем манипулируемости в технологиях сетевой экспертизы;

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

подтверждена актами и справками о внедрении в ряде российских компаний и организаций.

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

Публикации в изданиях из перечня ВАК РФ:

1. Коргин H.A. Задача стимулирования и обменные схемы // Автоматика и Телемеханика. 2001. № 10. С. 147 - 153.

2. Иващенко A.A., Коргин H.A., Новиков Д.А. Модели и методы оценки эффективности портфеля проектов // Системы управления и информационные технологии. 2005. № 3(20). С. 92-98.

3. Иващенко A.A., Коргин H.A., Новиков Д.А. Неманипулируемые механизмы экспертизы // Вестник Воронежского государственного технического университета. 2005. Т.1. № 10. С. 96-98.

4. Коргин H.A., Новиков Д.А. Задача стимулирования в условиях внутренней неопределенности о типах агентов, описываемых распределением Парето // Системы управления и информационные технологии. 2006. №4(26). С.66-69.

5. Бурков В.Н., Искаков М.Б., Коргин H.A. Применение обобщенных медианных схем для построения неманипулируемого механизма многокритериальной активной экспертизы // Проблемы управления. 2008. № 4. С. 38-47.

6. Бурков В.Н., Искаков М.Б., Коргин H.A. Об эквивалентном прямом механизме для задачи активной экспертизы на строго выпуклом компакте // Управление большими системами: сборник трудов. 2008. №22. С.134-148.

7. Коргин H.A. Анализ реализуемости результатов многокритериаль-

ной экспертизы - применение "свойства пересечения" // Проблемы управления. 2009. № 6. С. 18-27.

8. Коргин Н. А. Эквивалентность и неманипулируемость неанонимных приоритетных механизмов распределения ресурсов // Управление большими системами: сборник трудов. 2009. № 26.1. С.319-347.

9. Барабанов И.Н., Коргин H.A., Новиков Д.А., Чхартишвили А.Г., динамические модели информационного управления в социальных сетях // Автоматика и Телемеханика. 2010. № 11. С. 172-182. Ю.Губанов Д.А., Коргин H.A., Новиков Д.А. Модели нечеткой сетевой экспертизы // Системы управления и информационные технологии. 2010. №4 (42). С. 13-18.

П.Акинфиев В.К., Коргин Н:А. Организационные методы снижения риска инвестиционных решений//Проблемы управления. 2011. №1. С. 40- 46.

12. Коргин H.A., Христюк A.A. Эффективный механизм активной экспертизы с платой за участие как инструмент принятия согласованных решений // Вестник Воронежского государственного технического университета. 2011. Т.7. №6. С. 117-121.

13.Губко М.В., Коргин H.A., Новиков Д.А. Управление организационными системами: современные научные направления // Проблемы теории и практики управления. 2011. № 12. С. 62-71.

14.Бондарик В.Н., Колосова Е.В., Коргин H.A. Применение неманипу-лируемых механизмов активной экспертизы и распределения ресурсов для решения задач оперативного проектного управления // Системы управления и информационные технологии. 2011. № 4.1 (46). С. 119123.

15.Куливец С. Г., Коргин Н. А. Модель информационного управления на основе игры на линейной когнитивной карте // Управление большими системами: сборник трудов. 2011. № 35. С. 94-113.

16. Зубарев В.В., Ириков В.А., Коргин H.A. Комплексный подход к построению систем управления инновационным развитием региона: проблемы и пути решения // Проблемы управления. 2012. № 1. С. 2633.

17.Коргин H.A., Новиков Д.А., Райков А.Н., Технологии сетевой экспертизы // Проблемы теории и практики управления. 2012. № 3. С. 61-69.

18. Коргин Н. А. Представление механизма последовательного распределения ресурсов как неманипулируемого механизма многокритериальной активной экспертизы // Управление большими системами: сборник трудов. 2012. № 36. С.186-208.

19. Бурков В.Н., Губко М.В., Коргин H.A., Новиков Д.А. Теория управления организационными системами и другие науки об управлении организациями // Проблемы управления. 2012. № 4. С. 2-10.

20.Бондарик В.Н., Коргин H.A. Механизмы распределения ресурсов на основе неманипулируемых симметричных анонимных процедур голосования с делегированием // Проблемы управления. 2012. № 5 С. 2632.

21.Бондарик В.Н., Коргин H.A. Применение блочного метода для определения допустимых неманипулируемых механизмов активной

экспертизы при решении задачи распределения ресурсов // Системы управления и информационные технологии. 2012. №4(50). С. 40-44.

22. V.N. Burkov, M.V. Goubko, N.A. Korgin, D.A. Novikov Mechanisms of Organizational Behavior Control: A Survey // Advances in Systems Science and Application. 2013. Vol. 13. № 1. P. 1-20.

23. V.N. Burkov, M.V. Goubko, N.A. Korgin, D.A. Novikov Integrated Mechanisms of Organizational Behavior Control // Advances in Systems Science and Application. 2013. Vol. 13. № 3. P. 217-225.

24.Коргин H. А., Корепанов В.О. Решение задачи эффективного распределения ресурсов на основе механизма Гровса-Лейдярда при трансферабельной полезности // Управление большими системами: сборник трудов. 2013. № 46. С. 216-266.

Монографии:

25.Коргин Н.А., Неманипулируемые механизмы обмена в активных системах. М.: ИПУ РАН, 2003. 108 с.

26.Бурков В.Н., Коргин Н.А., Новиков Д.А. Введение в теорию управления организационными системами: Учебник / Под ред. Д.А. Новикова. М.: Книжный дом «ЛИБРОКОМ». 2009. 264 с.

27.Бурков В.Н, Коргин Н.А. Модели, методы и механизмы управления и принятия решений в организационных системах: учебное пособие. М.: Академия ИБС: МФТИ, 2009. 224 с.

28.Бурков В.Н., Буркова И.В., Губко М.В., и др. Механизмы управления: Мультифункциональное учебное пособие / Под ред. чл.-к. РАН Д.А. Новикова. М.: Ленанд, 2010. 192 с.

29. Губанов Д.А., Коргин Н.А., Новиков Д.А., Райков А.Н. Сетевая экспертиза / Под ред. чл.-к. РАН Д.А. Новикова, проф. А.Н. Райкова. М.: Эгвес, 2010. 170 с.

30.Бурков В.Н., Боровкова А.В., Веретенников В.В. и др. Переход региона на инновационное развитие: пример проекта системы управления инновационным развитием Владимирской области. / Под ред. Ирикова В.А. М.: ИПУ РАН. 2011. 126 с.

31. Burkov V., Goubko М., Kondrat'ev V., Korgin N., Novikov D. Mechanism Design and Management: Mathematical Methods for Smart Organizations / Ed. by Prof. D. Novikov. New York: Nova Science Publishers, 2013. 163 p.

Материалы международных и всероссийских конференций:

32.Burkov V., Korgin N. Strategy-proof Mechanisms of Organizational Control / Game Theory and Management. Collected abstracts of papers, presented on the Second International Conference Game Theory and Management. Spb.: Graduate School of Management SPbU. 2008. P. 21-23.

33.Korgin N. Feasibility Problem for Generalized Median Voter Schemes / Game Theory and Management. Collected abstracts of papers, presented on the Second International Conference Game Theory and Management. Spb.: Graduate School of Management SPbU. 2009. P. 130-133

34.Gubanov D.A., Korgin N.A., Novikov D.A. Models of Reputation Dynamics in Expertise by Social Networks / Proceedings of UKACC International Conference on CONTROL. Coventry: Coventry University. 46

2010. P. 203-210.

35.Gubanov D.A., Korgin N.A., Novikov D.A. Network expertise and dynamics of reputation / Proceedings of X International Meeting of the Society for Social Choice and Welfare. Moscow: HSE. 2010. P. 27.

36.Korgin N.A., A constructive algorithm of feasibility verification for generalized median voter schemes on compact ranges / Proceedings of X International Meeting of the Society for Social Choice and Welfare. Moscow: HSE, 2010. P. 15.

37. Korgin N., Makarenko D. Models and Techniques of Recourse Allocation in Controlling the Semi-structured Social and Economic Objects / Proceedings of 24 European Conference on Operational Research. Lis-bon:Universidade de Lisboa. 2010 P. 175-176.

38.Korgin N. Virtual Implementation of Social Choice Function of Linear Aggregation / Game Theory and Management. Collected abstracts of papers, presented on the Fourth International Conference Game Theory and Management. Spb.: Graduate School of Management SPbU. 2010. P. 102104.

39.Burkov V., Korgin N. Management games: Implementing Advanced Robust Incentive Schemes/ Game Theory and Management. Collected abstracts of papers, presented on the Fifth International Conference Game Theory and Management. Spb.: Graduate School of Management SPbU.

2011. P. 43-45.

40. Korgin N. Algorithmic Verification of Feasibility for Generalized Median Voter Schemes on Compact Ranges // Proceedings of the 18th World Congress of the IFAC, Milan, Italy, August 29-September 2. 2011. P. 824-829.

41. Korgin N. A. Representation of sequential allotment rule as generalized median voter scheme with tie-breaking rule // Proceedings of XI International Meeting of the Society for Social Choice and Welfare. 2012. URL: https://editorialexpress.com/cgi-

bin/conference/download.cgi?db_name=SSCW2012&paper_id= 106 (дата обращения 25.12.2012).

42. Korgin N. Efficient mechanism for resource allocation with quadratic payments and its realization via an iterative bargaining process / 7th IFAC Conference on Manufacturing Modelling, Management, and Control, MIM 2013-Proceedings. 2013. P. 1176-1181.

43.Korgin N., Korepanov V., Boldyreva G., Experiment with efficient Groves-Ledyard mechanism for resource allocation // Collected abstracts of papers presented on the Seventh International Conference Game Theory and Management. SPb.: Graduate School of Management SPbU, 2013. P. 120121.

44.Korgin N. An efficient mechanism for resource allocation by voting with transferable utility / Abstract book of 26' European conference on operational research. 2013. P. 59.

45.Коргин H.A. Неманипулируемые механизмы распределения ресурсов при многомерно-однопиковых в пропорциях предпочтениях агентов / Шестая Всероссийская мультиконференция по проблемам управления (30 сентября - 5 октября 2013 г.), материалы мультиконференции. Ростов-на-Дону: Издательство Южного феде-

рального университета. 2013. ТЗ. С. 40-44.

Личный вклад автора в работах, опубликованных в соавторстве, заключается в следующем: в [2—4, 11, 14, 20, 21, 39] автору принадлежат формальная математическая постановка и решение задачи построения неманипулируемого механизма планирования, в [5, 6] — разработка общего аппарата проверки неманипулируемости механизмов планирования, в [13, 19, 22, 26, 27. 28, 32] — обобщение и структуризация основных результатов по построению неманипулируемых механизмов планирования, в [16, 15, 37] — интеграция методов когнитивного моделирования и теоретико-игровых подходов к решению задач планирования с сообщением информации, в [12, 22, 43] — разработка эффективных механизмов планирования в условиях трансферабельной полезности, в [9, 10, 16, 29, 35] - формализация и исследование моделей и методов социальных сетей и сетевой экспертизы и проблемы манипулируемости в них, в [23, 28, 30, 31] - алгоритмы реализации неманипулируемых механизмов планирования и методы их интеграции в существующие системы управления социально-экономическими объектами.

Научное издание

Коргин Николай Апдреевич

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

Автореферат диссертации на соискание ученой степени доктора технических наук

В печать от 10.12.2013 Формат 60x90/16 Уч.-изд. л. 2,4 Тираж 100. Заказ 126

117997, Москва, Профсоюзная, 65 Федеральное государственное бюджетное учреждение науки Институт проблем управления им. В. А. Трапезникова Российской академии наук

Федеральное государственное бюджетное учреждение науки Институт проблем управления им. В.А. Трапезникова РОССИЙСКОЙ АКАДЕМИИ НАУК

УДК 519.8

КОРГИН НИКОЛАЙ АНДРЕЕВИЧ

НЕМАНИПУЛИРУЕМЫЕ МЕХАНИЗМЫ ПРИНЯТИЯ РЕШЕНИЙ В УПРАВЛЕНИИ ОРГАНИЗАЦИОННЫМИ СИСТЕМАМИ

Специальность: 05.13.10 «Управление в социальных и экономических системах»

диссертация на соискание ученой степени доктора технических наук

Научный консультант: Бурков Владимир Николаевич

доктор технических наук, профессор

МОСКВА-2013

Содержание

Введение...........................................................................................................................5

Глава 1. Активное планирование в организационных системах..............................22

1.1. Учет активности при планировании в организационных системах.........22

1.2. Классификация видов стратегического поведения при планировании в организационных системах..................................................................................26

1.3. Неманипулируемые механизмы планирования..........................................41

1.4. Классификация задач активного планирования в организационных системах при нетрансферабельной полезности.................................................51

Глава 2. Коллективное однокритериальное планирование.....................................57

2.1. Основные понятия и определения................................................................57

2.2. Обобщенные линейные свертки...................................................................59

2.3. Решение задачи активного планирования...................................................61

2.4. Эквивалентность механизмов активного однокритериального коллективного планирования...............................................................................63

Глава 3. Индивидуальное планирование....................................................................65

3.1. Задача распределения ресурсов - основные понятия и определения.......65

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

3.3. Решение задачи активного планирования...................................................72

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

Глава 4. Коллективное многокритериальное планирование....................................79

4.1. Основные понятия и определения................................................................79

4.2. Блочный метод...............................................................................................82

4.3. Решение задачи активного планирования...................................................91

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

Глава 5. Смешанное многокритериальное планирование.....................................101

5.1. Основные понятия и определения..............................................................101

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

5.3. Распределение ресурсов как смешанное многокритериальное планирование.......................................................................................................107

Глава 6. Активное планирование при многомерно-однопиковых в пропорциях предпочтениях агентов...............................................................................................115

6.1. Многомерно однопиковые в пропорциях предпочтения агентов...........115

6.2. Неманипулируемые механизмы распределение ресурсов при многомерно однопиковых в пропорциях предпочтениях агентов......................................118

6.3. Решение задачи активного планирования при многомерно однопиковых в пропорциях предпочтениях агентов..................................................................120

6.4. Решение задачи активного планирования для трех агентов....................122

Глава 7. Активное планирование при трансферабельной полезности.................125

7.1. Основные понятия и определения..............................................................127

7.2. Эффективная активная экспертиза.............................................................128

7.3. Эффективное распределение ресурсов......................................................132

7.4. Динамика поведения агентов......................................................................137

7.5. Эксперименты с механизмами....................................................................146

Глава 8. Прикладные модели активного планирования..........................................157

8.1. Общие практические рекомендации по активному планированию.......157

8.2. Манипулирование в сетевой экспертизе...................................................161

8.3. Комплексный механизм управления реализацией программ развития . 177

Заключение..................................................................................................................196

Приложение 1. Доказательства..................................................................................200

Доказательства главы 2......................................................................................200

Доказательства главы 3......................................................................................210

Доказательства главы 4......................................................................................221

Доказательства главы 5......................................................................................228

Доказательства главы 6......................................................................................233

Доказательства главы 7......................................................................................243

Приложение 2. Акты о внедрении.............................................................................255

Литература...................................................................................................................261

ВВЕДЕНИЕ

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

Манипулируемость процедур принятия решений на основе сообщаемой информации является предметом исследования целого ряда научных направлений, в основе которых лежит теоретико-игровой подход к описанию взаимодействия людей как рациональных (ограниченно рациональных) субъектов: теория механизмов (mechanism design), вобравшая в себя теорию аукционов, теорию контрактов и теорию реализуемости (Бремзен A.C.[199], Васин А.А.[47], Гуриев С.М.[233], Доманский В.К.[70], Измалков С.Б.[243,244], Крепе В.Л. [70], Мазалов В.В.[113-115], Островский М.[287], Печерский В.Л.[142], Савватеев A.B.[192, 297], Сегаль И.Р.[298], Сонин К.Щ210, 211], Шварц М. [211, 287], Abreu D.[164], Ba§ar Т.[186], Chen Y.[305], Clark Е.Щ209], d'Aspremont C.[215], Dewatripont M.[194], Gérrad-Varet L.A.[215], Green J.[227, 273], Groves T.[229, 230], Healy P.J.[236], Holmstrom P.[238, 239], Hurwic L.[240, 241], Jackson M.[181, 183, 193, 245-248], Krishna V.[263], Laffont J.J.[227, 265], Maskin E.[5, 216, 271, 272], Mar-timort D.[265], Mathevet L.[236, 274], Myerson R.B.[ 283-285], Milgrom P.[239, 277], Mirrlees J.A.[278], Roberts J.[277], Roberts K.[293], Tiróle J.[303], van Essen M.[305],

Vickrey W.[307], Weber S.[192], Whinston M.[273] и др.)'; теория коллективного выбора (Айзерман MA.[2], Алескеров Ф.Т.[3-7,166-170], Данилов В.И.[66, 213, 214], Карабекян Д.С.[3, 168, 169], Сотсков А.И [66, 214], Яновская Е.Б. [142], Arrow К.[174], Barberà S.[178-185], Berga D.[179, 187], Black D.[190], Bogomolnaya A.[192, 193], Border K.C.[196], Ehlers L.[172-218], Gibbard A.[225], Jordan J.[196], Kelly J.[253], Le Breton M.[192, 266-268], Massó J.[184, 185], Moulin H.[124, 280, 281], Nehring K.[286], Neme A.[183, 184], Peleg B.[288, 289], Peters H.[275, 291, 292], Puppe C.[286], Sanver M.R.[3, 168, 169]; Satterthwaite M.A.[296], Sen A.[174, 266], Serizawa S.[185], Shapley L.[224], Sjöström T.[303], Sprumont Y.[301], Svens-son L.G.[172], Weymark J.A.[195, 267, 310], Zaporozhets V.[268], Zhou L.[312] и др.); теория управления организационными системами (ранее — активными системами: Бурков В.Щ24-43, 200-208], Губко М.В.[27, 64, 202], Еналеев А.К.[27, 31, 33, 36, 200, 201], Заруба В.Я.[74], Ириков В.А.[75, 80], Искаков М.Б.[37, 38], Кондратьев В.В.[27, 39, 202, 205], Мишин С.ГЦ121], Новиков Д.А.[11, 27, 30, 36, 43, 56, 130, 202], Опойцев В.Щ44], Орлов А.Щ139], Петраков С.Щ140], Щепкин A.B.[34] и др.), теория иерархических игр (Горелик В.А. и Горелов М.А.[52], Ерешко Ф.И.[76], Кононенко А.Ф.[76, 91], Кукушкин Н.С.[104] и др.).

В ходе этих исследований было показано, что при определенных условиях (Бурков В.Н. и Кондратьев В.Н., 1977 [39]; Dasgupta P., Hammond P., Maskin E., 1979 [216]; Myerson R.B., 1979 [283])), в частности, при нетрансферабелъной полезности2, оптимальные (для произвольного критерия эффективности) процедуры принятия решений в ОС можно искать именно в классе неманипулируемых механизмов. Это определяет целесообразность и актуальность разработки методов поиска эффективных механизмов планирования при нетрансферабельной полезности агентов именно в классе неманипулируемых механизмов. В данном направлении исследований в настоящее время остается целый ряд открытых вопросов и проблем (см., например, Barberà S., 2011 [178])

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

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

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

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

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

2. когда все принимаемые решения влияют на полезность всех агентов без исключения (далее — коллективное планирование, public goods).

При этом, несмотря на то, что возможно представление первой задачи как частного случая второй, описания неманипулируемых механизмов для этих двух задач и их свойства различаются. Это не позволяет, в частности, конструировать неманипулируемые механизмы для «смешанных» задач, в которых агенты могут быть заинтересованы только в части принимаемых решений, однако их декомпозиция до «индивидуальных» компонент невозможна (далее - смешанное планирование). Одной из наиболее актуальных задач планирования является задача распределения ресурсов — в которой центр должен принимать решение о распределении некоторого ограниченного ресурса в организационной системе на основании информации, поступающей от агентов. В настоящее время эта задача достаточно хорошо исследована как задача индивидуального планирования (Бурков В.Н., 1989 [33]; Sprumont Y, 1991 [301]; Новиков Д.А., 1997 [30], Barberá S., Jackson M., Neme A., 1997 [183] и др.). Но, за исключением уточнения результатов Gíbbard А.[225] и Satterthwaite М.А.[296] для подобных задач (Le Breton M., Zaporozhets V., 2009 [268]) и т.н. механизмов согласия (Бурков В.Н., 1993 [31]), практически не исследовалась с точки зрения проблемы манипулируемости как задача коллективного и смешанного планирования, в то время как подобные ее постановки являются крайне актуальными для практики.

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

мов для целого ряда задач принятия решений не позволяет осуществлять поиск оптимальных (по произвольному критерию) механизмов или не дает возможность реализовывать конструктивные алгоритмы их построения. В частности, для задачи распределения ресурсов как задачи индивидуального планирования существуют алгоритмы построения неманипулируемых механизмов, но отсутствует аналитическая форма их записи. Для задачи коллективного планирования в случае, если принимаемое решение описывается более чем одним параметром (задача многокритериального коллективного планирования; задачи, в которых результат планирования - значение одного параметра, будем называть однокритериальными), то условия, определяющие класс неманипулируемых механизмов в зависимости от множества допустимых результатов планирования (т.н. условия допустимости (Barberà S., Massó J., Neme A., 1997 [184]), могут быть неконструктивны - например, требовать проверки выполнения определенного условия в каждой точке определенной непрерывной области пространства параметров (Barberà S., Massó J., Serizawa S., 1998 [185]). Это, в частности, не позволяет рассматривать задачу распределения ресурсов как коллективное многокритериальное планирование. Подобные трудности обусловлены тем, что значительная часть исследований по неманипулируемым процедурам планирования сосредоточена на случае конечного множества допустимых результатов планирования (выбора), поэтому в исследуемых проблемах допустимы переборные варианты решений. Например, подходы к анализу степени манипулируемости процедур коллективного выбора с помощью индексов манипулируемости (Kelly J., 1993 [253]; Алескеров Ф.Т. Кур-банов Э. 1998 [4]; Maus S., Peters H., Storcken T., 2007 [275] и др.). Однако результаты этих исследований зачастую оказываются неприменимыми, если множество допустимых результатов планирования не является конечным.

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

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

В-четвертых, существующие результаты об оптимальности (по отдельным критериям) неманипулируемых механизмов принятия решений достаточно «требовательны» к тому, как именно описываются предпочтения подчиненных на множестве возможных вариантов принимаемых решений, в особенности - необходимость т.н. однопиковости функции полезности агентов для задач однокрите-риального коллективного планирования (Moulin Н., 1980 [280]) или многомерной однопиковости для многокритериального планирования (Border К., Jordan J., 1983 [196]; Barbera S., Massó J., Neme A., 1997 [184]; Nehring K., Puppe С., 2007 [286]). Это сильно сужает класс практических задач, для которых применимы результаты теоретических исследований. В частности, для многих практических задач распределения ресурсов целесообразным представляется использование аддитивных

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

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

Подходы к построению механизмов управления с трансферабельной и не-трансферабельной полезностью отличаются достаточно сильно, в то время как задачи управления, для которых разрабатываются механизмы, не меняются. В частности, существующие результаты (Green J., Lafont J.J., 1979 [227]; Dasgupta P., Hammond P., Maskin E., 1979 [216]; Walker M. 1980 [308]) показывают, что неманипулируемые механизмы в условиях трансферабельной полезности оказываются менее эффективными (в частности, по критерию максимума суммарной полезности агентов), чем манипулируемые, в которых поведение агентов описывается теоретико-игровой концепцией равновесия Нэш�