<< Пред. стр.

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

ОГЛАВЛЕНИЕ

След. стр. >>

7.

Рассмотренная схема позволяет трактовать задачи распределения
ресурсов [4,16,18,25,29,52,57] как задачи обмена.?1

1
Здесь и далее символ ? обозначает окончание примера или задачи. Символ ¦ обозначает
окончание доказательства леммы, утверждения или теоремы.
12
После введения четырех классов ограничений можно записать ряд
ключевых определений.
Определение 2. Множество возможных вариантов обмена (МВО)
Y(y0): Y(y0) I IR(y0), "y I Y(y0), y0>y I QS .

Т.е множество возможных вариантов обмена - совокупность всех
индивидуально рациональных распределений ресурсов, переход к которым
от начального распределения ресурсов возможен в рамках заданной
структуры.
Определение 3. Обменная схема (ОС) – кортеж {I, J, A, y0, QS, Q?,
IR(y0)}, для которой МВО не пусто.

Для обменных схем можно вести следующие замены:

Определение 4. Трансферт ресурса типа j для элемента i в процессе
0
обмена y0>y : x ij = y ij - y ij .

xi = ( x1i ,..., x m )
Соответственно можно определить - вектор
i



трансфертов всех ресурсов у элемента i; матрица трансфертов в ОС -
x = ( x0 ,.., xn ) T .

Данная замена актуальна тем, что любой из возможных обменов в ОС
однозначно определяется матрицей x. В то время как различным вариантам
обмена может соответствовать одинаковое конечное распределение
ресурса между агентами.
Определение 5. Множество возможных вариантов обмена в терминах
трансфертов Х: " xIX $y I Y(y0) : x = y - y0.

Множество Х зависит от y0, но, учитывая, что в определении
обменной схемы мы рассматриваем единственное начальное
распределение ресурсов, аргумент y0 опускается.
Определение 6. Функция полезности i-го агента от обмена:
f i ( xi ) = j i ( xi + y io ) - j i ( y io ) .


13
По аналогии с множеством Х, аргумент yio в записи функции
полезности опускается. Очевидно, что свойства функции полезности
абсолютно идентичны свойствам функции предпочтения. Фактически,
функции полезности от обмена – это и есть функции предпочтения, но
рассматриваемые в новой системе координат (трансфертах), полученной
путем сдвига из стартовой системы координат (ресурсы).
Пример 2. Пусть предпочтения агента описываются функцией
j ( y1 , y 2 ) = y 2 - ( y1 - Y1 ) 2 . Тогда, в соответствии с определением 6,
множество Х зависит от y0, но, учитывая, что в определении обменной
схемы мы рассматриваем единственное начальное распределение
ресурсов, аргумент y0 опускается.

Таким образом, целевая функция в обменной схеме для данного агента
будет иметь следующий вид:

f ( x1 , x2 ) = x2 - x1 + 2 x1 ( y10 - Y1 ) .
2



При начальном наборе ресурсов у данного агента {Y1,0}, его целевая
функция переписывается следующим образом
f ( x1 , x2 ) = x2 - x1 .?
2



Также, важными понятиями в рассмотрении обменных схем, являются
понятие структуры подчиненности и понятие информационного состояния
схемы.
Структура подчиненности определяет иерархию в обменных схемах –
т.е. кто определяет правила и последовательность обмена и предлагает
возможные варианты обмена для всей схемы. Отметим, что структура
подчиненности может не иметь ничего общего со структурой схемы,
определяемой ограничениями QS. Одним «экстремумом» множества
возможных структур подчиненности является равноправная структура –
когда все агенты оказывают сравнимое влияние на выбор вариант обмена
или правила обмена. В противоположность данной структуре можно
поставить иерархическую структуру с двумя уровнями иерархии – из
множества всех агентов выделяется один, в подчинение которого
находятся все остальные агенты схемы. Используя терминологию ТАС
14
[52], главенствующего агента можно назвать центром (Ц), находящихся у
него в подчинении агентов – активными элементами (АЭ). Для
рассмотрения более сложных структур подчиненности можно для i-ого
агента ОС ввести следующую характеристику – (IiA;IiP). IiA - множество
агентов ОС, которым данный агент подчиняется непосредственно. IiP -
множество агентов ОС, находящихся в непосредственном подчинении у
данного агента.
Информационное состояние ОС определяет информированность
агентов о параметрах ОС. В данной работе сохраняется классификация,
принятая в [14,18,19,52]. В соответствии с данной классификацией,
основное внимание в данной работе уделяется ОС с неполной и
ассиметричной информированностью агентов. Агент считается не
полностью информированными, если ему не известны точные значения
всех параметры ОС. Информационное состояние системы считается
ассиметричным, если агенты обладают разными уровнями
информированности о параметрах ОС.
Введя базовые определения, необходимые для рассмотрения
обменных схем, перейдем к формулировке задачи обмена.

1.2. Общая постановка задачи обмена в активной системе


Самая общая постановка задачи обмена может быть сформулирована
как стандартная задача управления [18,52]. Реализация любого из
вариантов обмена зависит от управляющего воздействия u IU: x =G(u).
Пусть на множестве U?X задан функционал Ф(u, x), определяющий
эффективность обмена с точки зрения управляющего органа (например
центра самого верхнего уровня, или совокупности всех элементов для
равноправной ОС). Величина K(u) = Ф(u, G(u)) называется
эффективностью управления u IU. Задача управляющего органа
заключается в выборе максимально эффективного допустимого
управления:
u * I Arg max K(u) = { u IU | " ? IU K(u) ? K(?)}.
uIU




15
1.3. Рассмотрение задач теории активных систем как задач обмена


Прежде чем обосновать смысл рассмотрения задач ТАС как задач
обмена, произведем сравнительный анализ классификации ТАС и
классификации ОС, предложенной в данной работе.
Базовая модель АС задается следующим набором параметров [16, 52],
который также служит основанием для классификации задач ТАС.
Состав АС – совокупность субьектов, являющихся агентами системы
(участниками АС).
Структура АС – совокупность информационных, управляющих и
других связей между участниками АС, включая отношения подчиненности
и распределения прав принятия решений.
Порядок функционирования – последовательность получения
информации и выбора стратегий участниками АС.
Число периодов функционирования – отражает наличие или
отсутствие динамики в рассматриваемой АС.
Предпочтения участников АС – определяют совместно с
принципами рационального поведения зависимость состояния системы от
управляющих воздействий и критерий эффективности системы.
Допустимые множества состояний (стратегий) участников АС –
отражают индивидуальные и общие ограничения на выбор состояний,
накладываемые окружающей средой, используемой технологией и т.д.
Информированность участников – та информация, которой
обладают участники.
Из данного набора параметров часть сохранена и в описании модели
обменной схемы. Это состав системы, порядок функционирования, число
периодов функционирования и информированность участников, которая в
данной работе формулируется как структура информированности агентов
ОС. Несовпадение остальных параметров классификации АС и
классификации ОС можно привести в виде таблицы 1.




16
Таблица 1.
Различие оснований классификации ОС и ТАС

Предпочтения Допустимые
ТАС Структура АС
участников АС множества
Ограничения в ОС
А
Qs
Q?
IR(y0)
Структура
подчиненности


Затемненные области в приведенной выше таблице указывают на
пересечение критериев классификации модели АС и ОС по смыслу.
Поясним эти пересечения.
Структура системы распадается на два параметра – структура
подчиненности, и структуру взаимодействия, задаваемую ограничениями
на возможность взаимодействия между агентами. Причем последний
параметр больше принадлежит к группе допустимые множества из
классификации ТАС, так как является именно ограничением в модели.
Разделение параметра предпочтения участников системы – всего лишь
углубление классификации, позволяющее более четко прояснить
структуры модели ОС. Параметр допустимые множества преобразуется
прежде всего ограничения на ресурс, но возможность обмена агентов
между собой в соответствии с некой структурой также можно расценивать
как ограничения на выбор состояний участниками АС.
Таким образом, ОС - это АС, при исследовании которых акцент
делается на возможности взаимодействия агентов между собой (обмена
ресурсами).
Совершенно очевидно, что многие (если не все) задачи ТАС, могут
быть рассмотрены как задачи обмена.
Задачи стимулирования [2,8,12-14,16-22,45-52,55,58] – центр
взаимодействует с активными элементами, требуя от них каких то
17
действий и назначая стимулирование за эти действия. Взаимодействие
между центром и АЭ может быть представлено в виде обмена – центр
обменивает свой ресурс (например деньги) на ресурс АЭ – их работу,
товар, т.д. Поэтому очевидно, что задачи стимулирования могут
рассматриваться как задачи обмена. В разделе 2.1 приводится строгое
доказательство эквивалентности задач стимулирования и обмена.
Задачи распределения ресурса [4,16,18,25,29,52,57] – центр неким
образом распределяет имеющийся у себя в наличии ресурс между АЭ. В
примере 1 рассмотрена ОС, где возможен только «односторонний» обмен
– один агент может распределить имеющийся у него в наличии ресурс
между остальными. Иными словами задачи распределения ресурсов можно
представить как частный случай задач обмена. Представляется
перспективным перенос результатов ТАС, полученных для задач
распределения ресурсов.
Задачи определения внутренних цен [2,7,13,14,16,17,19-22,25,26,55,58]
также могут быть рассмотрены как задачи обмена, где ресурсами к обмену
являются деньги и товары.
На рисунке 3 представлена структура рассматриваемых в работе
обменных схем. В главе 2 будут рассмотрены двухэлементные ОС, для
которых задачи обмена могут быть классифицированы как эквивалентные
задачам стимулирования, эквивалентные «обратным» задачам
стимулирования (центр стал АЭ, а АЭ – центром) и как «классический»
обмен – функции предпочтения агентов линейно зависят от количества
имеющихся у агентов ресурсов.




18
Обменные схемы (описание модели и постановка задачи обмена – глава 1)

Два агента (глава 2) Несколько агентов (глава 3)

Нет иерархии Иерархия Ц - АЭ

Неполная Полная
информированность информированность Неполная информированность центра
агентов центра

Взаимодействие Веерное
агентов типа взаимодействие
«цепочка» агентов


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


раздел 2.3 раздел 2.1 раздел 2.2 раздел 3.2 раздел 3.1




Обратная задача Задача «Классический»
стимулирования стимулирования обмен



Рис. 3. Рассматриваемые обменные схемы




19
1.4. Математические модели и методы, используемые для построения
неманипулируемых механизмов обмена в активных системах
В данном разделе приведем основные результаты ТАС и
микроэкономической теории, применимые для построения
неманипулируемых механизмов обмена в активных системах
Условия совершенного согласования. В отечественных работах
авторы сосредоточили внимание на способах организации деятельности
отдельных элементов системы. В [10-14,16-22,52,53,55,58,62,63]
исследуются механизмы функционирования систем, в которых
альтернатива представляет собой вектор Евклидова пространства, причем
в функции полезности каждого активного элемента явно участвует только
одна компонента этого вектора, обычно содержательно интерпретируемая
как план, назначаемый данному элементу. Такие системы в зарубежных
работах получили название экономик с частными товарами (Economies
with private goods) [45,61,72,53,55,].
Рассмотрим систему, состоящую из центра и n активных элементов.
Интересы элементов и центра выражаются их целевыми функциями
f i ( xi , yi , ri ) , i = 1, n и F ( x, y ) где ri I W i - параметр, параметризующий
класс допустимых целевых функций i - го элемента, x = ( x1 , ..., x n ) - вектор
планов, назначаемых элементам, а y = ( y1 , ..., y n ) - вектор действий,
выбираемых элементами. Порядок функционирования системы
следующий:
1. Этап сбора информации. Элементы сообщают центру оценки ( s1 , ..., s n )
параметров (r1 , ..., rn ) ;
2. Этап планирования. На основе полученных оценок центр, используя
S = O Wi , X = O Xi -
p : S ® X , где
процедуру планирования
iII iII
множество допустимых планов, назначает планы xi = p i (s ) элементам,
i = 1, n .




20
3. Этап выбора состояния. Получив плановые задания, элементы
y i IA i , где Ai, i = 1, n
выбирают свои состояния - множества
допустимых состояний.
В предположении рационального поведения элементов, при
фиксированных планах выбираемые действия yi* будут максимизировать
соответствующие целевые функции, то есть:
yi* I Pi ( xi , ri ) = Argmax f i ( xi , yi , ri ) .
yiIAi

Как и ранее, при сообщении оценок на этапе 2, будет иметь место
эффект манипулирования информацией. Задачей центра является выбор
такой процедуры планирования, чтобы в точке равновесия значение его
целевой функции было максимально. Введем эффективность механизма
S = (S , p )
K (S) = min Y ( p( s * ), r ) ,
r IS


где Y ( x, r ) = F ( x, y * ( x, r )) .
При заданных значениях параметра ri I W i и плане xi I X i элемент
yi* ( xi , ri ) I Pi ( xi , ri ) = Argmax f i ( xi , yi , ri ) .
выбирает действие Таким
yiIAi

образом, можно говорить о функции предпочтения (полезности) элемента
j i ( xi , ri ) = f i ( xi , yi* ( xi , ri ), ri ) .
Зададим для каждого активного элемента множества X i( s -i ) I X i и
рассмотрим следующую процедуру планирования:
(5.1) iY ( x, s) ® max
i xI X
i
ij i ( x i , s i ) = zI X ( s ) j i ( z, s i ).
max
i
(5.2) -i
i




Условие (5.2) обеспечивает назначение элементу плана,
максимизирующего его функцию предпочтения (в которую в качестве
«истинного» значения типа АЭ подставляется сообщенная им оценка) и
называется условием совершенного согласования (УСС). Условие (5.1) в
неявном виде задает процедуру планирования, максимизирующую


21
целевую функцию центра. Механизм, удовлетворяющий (5.1)-(5.2),
называется механизмом открытого управления (ОУ).
Теорема 5.1.2 [52] (Принцип открытого управления). Необходимым и
достаточным условием сообщения достоверной информации как
доминантной стратегии при любых r I W является существование
множеств X i( s - i ) , для которых выполнено условие совершенного
согласования.¦
Таким образом, принцип открытого управления является критерием
неманипулируемости механизма планирования в АС с сообщением
информации. Помимо манипулируемости, основным свойством любого
механизма является его эффективность. Возникает вопрос, в каких случаях
существует оптимальный неманипулируемый механизм (другими словами
– в каких АС при поиске оптимального механизма можно ограничиться
классом неманипулируемых механизмов). Частичный ответ на этот вопрос
дает теорема 5.2.
Теорема 5.2. [52] В активной системе с одним активным элементом для
любого механизма планирования существует механизм открытого
управления не меньшей эффективности.¦
Итак, теорема 5.2 утверждает, что механизм ОУ оптимален в
одноэлементной АС (другими словами, для любого механизма
планирования в одноэлементной активной системе существует
эквивалентный прямой механизм. Естественное желание обобщить этот
результат на случай многоэлементных АС наталкивается на ряд проблем,
основная из которых – зависимость равновесного сообщения si* (r )
каждого АЭ i I I от типов других АЭ [13]. Поэтому в общем случае в
многоэлементных АС механизмы открытого управления
(неманипулируемые) не оптимальны. В то же время, для широкого класса
практически важных частных случаев механизмов планирования в
многоэлементных АС доказаны результаты об оптимальности механизмов
ОУ. Некоторые из этих механизмов рассматриваются в работах


2
В разделе 1.4 нумерация определений, лемм, теорем, формул и т.д. соответствует их нумерации в
в источниках.
22
[8,13,19,48,52,55]. В данной работе УСС будут использованы в общем
методе построения неманипулируемых механизмов обмена, а теорема 5.2
обосновывает оптимальность неманипулируемых механизмов обмена,
которые будут построены в главе 1.
Оптимальность неманипулируемых механизмов распределения
ресурсов [4,13,14,16-22,46,47,52,53,55,63]. Рассмотрим систему,
состоящую из центра и n активных элементов. Центр владеет R0
единицами ресурса. Ценность ресурса для i -го элемента определяется его
функцией полезности j i ( x i , ri ) , где xi - получаемое им количество
ресурса, а ri - тип АЭ, параметризующий класс допустимых функций
полезности. Функция полезности может определять, например, прибыль
АЭ от использования ресурса в количестве xi .
Предположим, что о функции полезности АЭ центр не имеет
информации, за исключением той, что она принадлежит некоторому
классу однопиковых функций с точкой пика ri I W i и однозначно
определяется значением этого параметра, то есть получение ресурса в
количестве xi = ri доставляет максимум функции полезности i-го АЭ.
Задачей центра является распределение ресурса с целью, например,

aj ( x i , ri ) ® max
максимизации суммарной полезности всех элементов i

<< Пред. стр.

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

ОГЛАВЛЕНИЕ

След. стр. >>