стр. 1
(общее количество: 15)

ОГЛАВЛЕНИЕ

След. стр. >>

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




Н.А. Коргин



НЕМАНИПУЛИРУЕМЫЕ МЕХАНИЗМЫ ОБМЕНА
В АКТИВНЫХ СИСТЕМАХ




Москва - 2003
УДК 519
ББК 22.18
К 66

Коргин Н.А. Неманипулируемые механизмы обмена в
активных системах. М.: ИПУ РАН (научное издание), 2003. – 126 с.


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



Рецензент: д.т.н. Д.А. Новиков




Утверждено к печати Редакционным советом Института


Текст воспроизводится в виде, утвержденном Редакционным советом
Института




a Институт проблем управления РАН, 2003




2
СОДЕРЖАНИЕ
Введение............................................................................................................... 4
Глава I. Общие принципы построения неманипулируемых механизмов
обмена в активных системах.............................................................................. 9
1.1. Модель обменной схемы ............................................................................. 9
1.2. Общая постановка задачи обмена в активной системе .......................... 15
1.3. Рассмотрение задач теории активных систем как задач обмена........... 16
1.4. Математические модели и методы, используемые для построения
неманипулируемых механизмов обмена в активных системах ................... 19
1.5. Общий метод построения неманипулируемых механизмов обмена в
активных системах ............................................................................................ 38
Глава II. Неманипулируемые механизмы обмена в двухэлементных
активных системах ............................................................................................ 45
2.1. Представление задачи стимулирования в виде задачи обмена ............. 46
2.3. Решение задачи обмена для двухэлементных обменных схем без
иерархии ............................................................................................................. 65
Глава III. Неманипулируемые механизмы обмена в многоэлементных
активных системах ............................................................................................ 90
3.1. Неманипулируемые механизмы обмена для обменных схем с веерной
структурой взаимодействия агентов ............................................................... 91
3.2. Неманипулируемые механизмы обмена для обменных схем со
структурой взаимодействия агентов типа «цепочка» ................................... 97
Заключение ...................................................................................................... 117
Литература ....................................................................................................... 119




3
ВВЕДЕНИЕ
Современный руководитель сталкивается с большим количеством
проблем в процессе управления подчиненным ему субъектом
(коллективом, предприятием, государством и т.д.) или планирования его
деятельности. Среди наиболее насущных следует выделить проблему
недостатка информации, необходимой для осуществления эффективного
управления и планирования. В областях математики, исследующих
управление в социально-экономических и организационных системах
(теория игр, теория активных систем, микроэкономика и т.д.), предложены
различные методы устранения информационной неопределенности
руководителя системы. Один из распространенных приемов - сообщение
необходимой информации подчиненными руководству (например в теории
активных систем механизмы управления с сообщением информации
называются механизмами планирования [52]). При разработке механизмов
управления с сообщением информации, наряду с традиционной задачей
максимизации эффективности управления системой [18,52], возникает
задача устранения возможности подчиненных манипулировать
сообщаемой ими информацией в собственных целях.
Пример «Традиционная проблема воровства». Если у повара,
работающего в неком ресторане за фиксированную зарплату, начальство
требует изготовления блюд, рецепты которых не известны руководству но
известны повару, сколько продуктов нужно для приготовления того или
иного блюда, то у повара возникает естественное желание завысить
называемые количества, тем самым, заполучив в свое распоряжение
излишки продуктов.
В настоящее время проблема манипулируемости получила достаточно
широкое освещение как в отечественных [4,10-14,16-
22,46,47,52,53,55,58,62,63], так и в зарубежных публикациях
[59,61,64,65,67-70,72-77,79-82,85-89,91,95]. Однако, до сих пор не
существует единого аппарата построения неманипулируемых механизмов
управления социально-экономическими и организационными системами.
Основной трудностью является многообразие рассматриваемых моделей
систем и различных постановок задач управления.
4
В данной работе развивается один из возможных подходов,
призванный свести воедино многие полученные ранее результаты.
Насколько хорошо понятие «обмен» описывает взаимодействие между
людьми? Рассмотрим произвольное сообщество. Каждый из членов этого
сообщества обладает своим ресурсом (или несколькими видами ресурсов)
– деньгами, знаниями, возможностью выполнить какую-либо работу,
хорошим настроением и т.д. Люди, члены данного сообщества могут
обмениваться между собой этими ресурсами. Зачем? Например, с целью
улучшить свое благосостояние. Оставив за рамками данной книги
нетривиальный вопрос – что такое благосостояние человека, скажем лишь,
что и материальное богатство человека, выраженное в деньгах, и его
уважение в обществе, и даже его моральное удовлетворение можно
рассматривать как благосостояние. Важно лишь, что благосостояние
человека зависит от имеющихся у него в наличии ресурсов.
Таким образом, обмен – это перераспределение ресурсов между
элементами системы, с целью улучшения их благосостояния.
Очевидно, что экономические системы являются частным случаем
сообщества людей, причем элементами подобных систем могут являться
как отдельные люди, так и целые коллективы, предприятия, фирмы,
страны и т.д. – экономические субъекты. Поэтому, процесс
функционирования экономической системы может быть представлен как
процесс обмена. В качестве ресурсов, обмениваемых участниками
системы, могут выступать производимые ими товары, оказываемые
услуги, деньги.
Пример «Взаимодействие мельника и пекаря». Схема обмена
выглядит следующим образом. Мельник передает пекарю некоторое
количество муки, заказывая у него выпечь из нее булок. Обмен между
мельником и пекарем здесь очевиден – обменивается ресурс типа «мука»
на ресурс типа «булки». В случае, если условия обмена определяет
мельник, а пекарь либо соглашается на них либо нет, в роли управляющего
органа (центра) выступает мельник, а пекарь – в роли активного элемента
[23]. Проблема неполной информированности центра (мельника) о
параметрах схемы (типе пекаря) может быть сформулирована следующим

5
образом. Мельник не знает точно технологии пекаря, но знает, что на
изготовление одной булки пекарю требуется от 600 до 900 грамм муки.
Возникает вопрос о том, сколько же муки обменять на сколько булок.
Мельник может поступить следующим образом – он может спросить у
пекаря о его технологии, и в зависимости от сообщенной информации
предложить различные варианты обмена, тем самым реализовав механизм
обмена с сообщением информации. Проблема манипулируемости
подобного механизма очевидна – пекарь может воспользоваться неполной
информированностью мельника в своих интересах, сообщив завышенное
значение требуемого количества муки, а полученные излишки использовав
в своих интересах.
Рассматривая различные процессы функционирования социально-
экономических и организационных систем как процессы обмена, можно
расширить области применения полученных ранее результатов решения
отдельных задач управления (в частности, задачи построения
неманипулируемх механизмов управления).
Для разработки эффективных неманипулируемых механизмов обмена
в активных системах необходимо решение следующих основных задач:
- Разработка модели обменной схемы и формулировка общей задачи
обмена в активной системе.
- Разработка общих методов построения неманипулируемых
механизмов обмена в активных системах в условиях неполной
информированности руководящего органа (центра).
- Синтез эффективных и неманипулируемых механизмов обмена для
базовых обменных схем: двухэлементных и многоэлементных (веерного
типа и типа «цепочки»).
Структура изложения.
Перечисленные общие теоретические задачи настоящего
исследования определяют структуру дальнейшего изложения его
результатов. Первая глава посвящена общей постановке проблемы
построения неманипулируемых механизмов обмена в активных системах.
В разделе 1.1 формулируется математическая модель обменной схемы


6
(ОС). Вводятся определения обмена, множества вариантов обмена (МВО)
и ОС, а также ряд других ключевых определений.
В разделе 1.2 задача обмена формулируется как задача управления.
В разделе 1.3 изучается возможность рассмотрения задач теории
активных систем (ТАС) как задач обмена. Проводится сравнительный
анализ классификации активных система (АС) и классификации ОС.
Раздел 1.4 посвящен обзору основных математических моделей и
методов, которые могут быть использованы для построения
неманипулируемых механизмов для ОС. Формулируется принцип
открытого управления и приводятся достаточные условия
неманипулируемости прямых механизмов планирования. Приведен
принцип построения неманипулируемых механизмов для решения задач
теории контрактов. Рассматривается модель обменной экономики
Эджворта. Излагаются принципы построения механизмов Маскина и
МакКельви, реализующих заданное соответствие группового выбора
(СГВ).
В разделе 1.5 дается общая постановка задачи построения
неманипулируемых механизмов обмена для АС с неполной
информированностью центра. Формулируется общий метод построения
неманипулируемых механизмов обмена.
Вторая глава посвящена рассмотрению «базовых» обменных схем,
состоящих из двух агентов.
В разделе 2.1 строится модель ОС, соответствующая модели АС для
задача стимулирования. Доказывается эквивалентность решений
детерминированных задач стимулирования и обмена для соответствующей
ОС. Осуществляется переход от детерминированной ОС к ОС с
внутренней неполной информированностью центра – вводится понятие
типа АЭ, полностью характеризующее АЭ, и не известное достоверно
центру. Формулируются условия на зависимость функции предпочтения
АЭ от типа, при выполнении которых возможно применение общего
метода построения неманипулируемого механизма обмена.
Раздел 2.2 посвящен построению механизмов ОУ в двухэлементных
ОС с внутренней неполной информированностью. Рассматриваются

7
дискретный и непрерывный методы построения механизмов ОУ.
Дискретный метод построения неманипулируемых механизмов обмена
основан на «графическом» анализе функций предпочтения агентов.
Непрерывный метод является частным случаем предложенного в разделе
1.5 общего метода построения неманипулируемых механизмов обмена.
Доказана эквивалентность двух предложенных методов.
Раздел 2.3 посвящен решению двухэлементных задач обмена без
иерархии. Предлагается метод решения подобных задач, основанный на
механизмах ОУ для аналогичных двухэлементных иерархических ОС.
Агенты самостоятельно распределяют между собой роли Ц и АЭ.
Определяется зависимость распределение ролей от параметров ОС для
«квазиинтеллектуальных» (не производящих анализ сообщений
оппонента) и «интеллектуальных» (анализирующих сообщения оппонента)
агентов.
Третья глава работы посвящена исследованию механизмов ОУ в ОС с
конечным числом элементов.
В раздел 3.1 рассматривается ОС с веерной структурой
взаимодействия элементов и одним уровнем иерархии. Т.е ОС состоит из
одного центра и конечного числа АЭ. Для многоэлементных ОС,
соответствующих многоэлементной задачи стимулирования строится
эффективный механизм обмена ОУ.
В разделе 3.2 рассматриваются ОС со структурой взаимодействия
элементов типа «цепочка» и одним уровнем иерархии. Предлагаются три
метода построения неманипулируемых механизмов обмена для случая,
когда общий метод неприменим. Первый метод – метод «консолидации
АЭ» – центр рассматривает всех АЭ как единый АЭ и решает задачу
нахождения механизма обмена ОУ для полученной двухэлементной ОС.
Второй метод – метод «разбиения схемы» – цент взаимодействует с
каждым АЭ по отдельности. Третий метод – метод «доносчика» - центр
делегирует права промежуточного центра тому АЭ, который сообщит
наилучшую оценку типов всех АЭ.
Заключение содержит основные результаты работы и обсуждение
перспективных направлений дальнейших исследований.
8
ГЛАВА I. ОБЩИЕ ПРИНЦИПЫ ПОСТРОЕНИЯ
НЕМАНИПУЛИРУЕМЫХ МЕХАНИЗМОВ ОБМЕНА В АКТИВНЫХ
СИСТЕМАХ
В данной главе формулируется математическая модель ОС, ставится
задача обмена. Проводится сравнительный анализ оснований для
классификации АС и ОС, в результате которого обосновывается
актуальность рассмотрения задач ТАС как задач обмена. Приводится обзор
основных известных моделей и методов, которые могут быть
использованы для построения неманипулируемых механизмов обмена для
ОС. Формулируется общая постановка задачи построения
неманипулируемых механизмов обмена для АС с неполной
информированностью центра. Предложен общий метод решения этой
задачи. Выводятся необходимые и достаточные условия
неманипулируемости механизма обмена, сформулированные в терминах
функций предпочтения агентов. Полученные автором результаты,
содержащиеся в первой главе, были опубликованы в работах [33,37,40,43].

1.1. Модель обменной схемы


Понятие обмена можно понимать в буквальном смысле – считая
обменными бартерные схемы. Можно попытаться расширить рамки
понятия процесса обмена, рассматривая его, как процесс взаимодействия
между членами социально-экономической системы с целью улучшения
своего благосостояния. Для этого необходимо построить модель обменной
схемы, которая не противоречит проводимым ранее исследованиям
бартерных схем [1,5,6,7,9,15,24,26,31,44] и позволяет рассмотреть другие
задачи функционирования социально-экономической системы (активной
системы в терминах ТАС) как задачи обмена.
Рассмотрим АС, состоящую из n+1 агентов и m видов ресурсов.
Множество всех агентов обозначим I = {0,…,n}. Множество всех ресурсов
обозначим J = {1,…,m}. Набор всех имеющихся у агента i ресурсов
обозначим yi = ( y1i ,..., y m ) . Здесь y ij обозначает наличие у i-ого агента
i




9
ресурса типа j. Соответственно распределение ресурсов по всем агентам
можно записать в виде матрицы: y = ( y0 ,.., y n ) T .
Нумерация агентов от 0 до n оправдана тем, что большинство ОС,
рассматриваемых в данной работе будут представлять из себя АС,
состоящие из одного руководящего агента и n подчиненных ему агентов.
Функции и возможности руководящего и подчиненных агентов будут
рассмотрены ниже, при описании структуры подчиненности агентов.
Предпочтения каждого агента опишем произвольной функцией
(функция предпочтения): j i ( y i ) : R m ® R; i = 0, n + 1 .
Агенты обладают возможностью взаимодействовать между собой
путем взаимного обмена ресурсами.
Определение 1. Обмен – перераспределение ресурсов из множества J
между элементами из множества I: y0>ye.
Здесь y0 – матрица начального распределения ресурса (или
существующего распределения), ye – соответственно конечного.
Определение 1 и само описание набора агентов и ресурсов выглядят
пока достаточно абстрактно, но именно данный подход позволяет дать
наиболее общее определение обменной схемы и самого процесса обмена.
Рассмотрим качественно, какие ограничения (требования) могут быть
наложены на описанную выше модель и приведем примеры данных
ограничений. Данные ограничения могут трактоваться как основания для
классификации ОС.
Ограничения по ресурсам. Ограничения данного класса определяют
множества всевозможных значений матрицы распределения ресурсов y:
yIA. Примером подобных ограничений являются ограничения на общее
n

ay = Y j , и ограничения на количество ресурса
количество ресурса i
j
i =o


(ресурсов) у отдельного агента, например y ij ? Y ji .
Ограничения по возможности взаимодействия между агентами.
Ограничения данного класса фактически превращают некий
произвольный набор агентов в сетевую структуру – указывают, с какими
агентами данный конкретный агент может обмениваться какими
10
ресурсами. На рисунке 1 приведен пример ограничений данного класса –
линии, связывающие агенты указывают на возможность взаимодействия
(обмена) между ними, подписи к линиям – указывают на типы ресурсов,
которыми данные агенты могут обмениваться. Ограничения данного
класса обозначим QS. Запись y0>ye I QS обозначает, что обмен y0>ye
возможен в рамках определенной структуры.




Рис. 1. Структура взаимодействия агентов
Ограничения на вид функций предпочтения агентов. Это
достаточно широкий класс ограничений. Например, функции всех агентов
принадлежат к классу вогнутых однопиковых непрерывных функций. Или
вид функций предпочтения может быть указан явным образом, например:
m
j i = a Bi j ( yij - a i j ) .
b ij

j =1


Ограничения данного класса обозначим Q?.
IR(y0).
Ограничения индивидуальной рациональности
Ограничения данного класса определяют требования, налагаемые на
значения функций предпочтения агентов. Например "i I I j i ( y ie ) ? j i ( y i0 ) .
Множество распределений ресурсов, индивидуально рациональных по
отношению к начальному распределению ресурса, обозначим IR(y0).
Очевидно, что IR(y0) I A.
Накладывая на рассматриваемую схему ограничения приведенных
выше четырех классов в различных комбинациях, можно получить
достаточно большое количество моделей взаимодействия агентов.




11
Пример 1. Схема “Распределение ресурсов” (см. рисунок 2)




Рис. 2. ОС «Распределение ресурсов»
Опишем модель АС, используемую в задаче распределения ресурсов
[4,16,18,25,29,52,57] в терминах обменных схем:
1. Кол-во агентов - n+1 (Центр – агент с номером 0)

2. Кол-во видов ресурсов – 1
n
Ограничения на ресурс A: a y1i = Y1
3.
i =o




Ограничения QS: агенты с номерами i = 1, n могут
4.
взаимодействовать только с агентом номер 0 (центр).

5. Ограничения Q?: функции благосостояния для агентов с
номерами i = 1, n – однопиковые, максимум функции благосостояния
k-ого достигается при наличии у него ресурса в кол-ве rk.

6. Ограничения ИР зависят от начального распределения
ресурса и записываются следующим образом
"i = 1, n, " y I A, j i ( yi ) ? j i ( yi )
0




Начальное распределение ресурса: y 0 = (Y1 ,0,...,0) T

стр. 1
(общее количество: 15)

ОГЛАВЛЕНИЕ

След. стр. >>