<< Пред. стр.

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

ОГЛАВЛЕНИЕ

След. стр. >>

x?0
iI I



ax ? R0 .
при ресурсном (балансовом, бюджетном) ограничении: i
iII

Распределение ресурса осуществляется следующим образом. Каждый
активный элемент сообщает центру оценку s i I W i , i I I , своего типа
(параметра своей функции полезности) j i ( x i , ri ) и получает ресурс в
количестве x i = p i (s ) , где p (s) = (p 1 ( s ), p 2 ( s ), ..., p n ( s )) называется
процедурой (механизмом) распределения ресурса.
Будем полагать, что множество возможных значений типов i-го АЭ W i
W i = [0, D ] I R 1 , iII ,
- является отрезком действительной оси:
0 < D < +? . В качестве ограничения D можно выбрать, например,
имеющееся в распоряжении центра количество ресурса R0 .

23
На процедуру распределения ресурса наложим следующие
ограничения:
1. Функция p i (s ) непрерывна по всем переменным и строго монотонна
по si для всех s I [0, D ] n , i I I .

ar > R0 (гипотеза дефицитности) и весь ресурс
2. Будем считать, что i
iII



ax = R0 .
распределяется полностью, то есть: i
iII

3. Каждая группа активных элементов может получить любое
количество ресурса, меньшее того, что она уже получила:
"s I W, "W I I " x i ? p i ( s ), i I W $ sW I W W : xW = p W ( sW , s I \W ) ,
где WW = O W j 3.
jIW


4. Если количество ресурса, распределяемого между АЭ из некоторого
подмножества W I I , увеличивается, то каждый АЭ получает количество
ресурса, не меньшее прежнего.
В качестве модели поведения примем равновесие Нэша. Вектор
сообщений s * (r ) называется равновесием Нэша при данном r I W , если
"i I I , "s i I W i выполняется следующее соотношение:
j i (p i ( s * ), ri ) > j i (p i ( s i , s -i ), ri ) .
*



Лемма 5.1. [52] Пусть s * (r ) - равновесие Нэша при данном r , тогда
оно удовлетворяет следующим условиям:
1) если x i* < ri , то s *i = D ;
2) если s *i I [0, D) , то x i* = ri .¦
Распределение ресурса в равновесии определяется следующим
алгоритмом.
Алгоритм 5.1. [52] На нулевом шаге полагаем s i0 = D для всех i I I и
вычисляем распределение ресурса x i0 = p i ( D, ..., D) . Множество4 Q на
нулевом шаге полагаем пустым Q 0 = ? .



3
Некоторое условие, записанное для индекса W I I , считается выполненным для всех АЭ i I W .
24
На шаге j ? 1 множество Q j определяем следующим образом:
Q j = {i I I | ( x j -1 ) i ? ri } .
Для АЭ из множества Q j по условию 2 определяем s Q I W Q такие, j j



что
p Q ( sQ , s Ij\-Q ) = rQ .
1
j j j j




В конце j -го шага получим s j = ( s Q , s Ij\-Q ) и x j = p ( s j ) .
1
j j




окажется, что Q k = Q k -1 , то алгоритм
Если на некотором шаге k

останавливается, и полагаем: s * = s k , x * = x k , Q = Q k . ·
Результаты применения данного алгоритма, заканчивающегося не
более чем за n шагов, имеют следующие свойства:
Лемма 5.2. [52] 1) Если i I Q k , то на любом шаге 1 ? j ? k , x j ? x j -1 и
x* ? x0 .
2) s* - равновесие Нэша при данном r .¦
Определим соответствующий исходному механизму распределения
ресурса прямой механизм h(˜ ) = p ( s * (˜ )) , ˜ I W . Таким образом, в
r r r
˜
механизме h(r ) i-ый элемент сообщает ˜ I W , при этом r может быть не
r i i i

равным ˜ .
ri
˜
Теорема 5.3. [52] Прямой механизм распределения ресурса h(r ) ,
определяемый алгоритмом 5.1, является механизмом открытого
управления.¦
Из теоремы 5.3 следует, что для любого механизма распределения
ресурса, удовлетворяющего введенным предположениям, существует
эквивалентный прямой механизм, то есть неманипулируемый механизм не
меньшей эффективности. Этот результат будет использован в
доказательстве оптимальности неманипулируемого механизма обмена в
ОС с веерной структурой взаимодействия агентов.



4
Множество Q I I включает активные элементы, получающие абсолютно оптимальные для

себя планы ( xi = ri , i I Q ). Такие АЭ называются «диктаторами» или (в механизмах распределения

ресурса) приоритетными потребителями.
25
Неманипулируемость прямых механизмов и множества
диктаторства [53,55,63].
Рассмотрим прямой механизм h : R n ® R n . Пусть для некоторого
˜
сообщения ˜ I R n выбирается вектор планов x = h(r ) . Так как полезность
r
каждого АЭ определяется однопиковой функцией полезности, то каждый
АЭ может находиться в одном и только одном из трех возможных
состояний: (а) либо h (˜ ) > ˜ и тогда АЭ будет получать план, строго
r r i i
hi (˜ ) = ˜
больший желаемого, (б) либо и АЭ будет назначаться
r ri
оптимальный для него план, (в) либо hi (˜ ) < ˜ и план будет
r ri
недостаточным. Для каждого активного элемента i I I введем индекс
состояния, принимающий значения из набора {a, c, m}=A, где a
соответствует состоянию (а), с - состоянию (б), а m - (в), и обозначим его
через r i (символы индекса являются первыми буквами фр. слов manque -
нехватка, contentement - удовлетворенность, abondance - избыток). Вектор
индексов состояния всех АЭ обозначим через rIAn.
Введем соответствия M:An®2I, C:An®2I, A:An®2I, значениями
которых для каждого вектора состояний rIAn будет подмножество АЭ из
I, таких, что индексы состояний этих элементов равны, соответственно, m,
c и a: M(r)={jII: rj=m}, C(r)={jII: rj=c}, A(r)={jII: rj=a}, rIAn.
Очевидно, для каждого r подмножества C ( r ), A( r ), M ( r ) в совокупности
являются разбиением множества всех элементов I .
Определение 2.1.1. [53] Разбиением D пространства R n назовем
совокупность множеств DrIRn, таких, что
D r = {˜ I R n hi (˜ ) < ˜ если i I M ( r ), hi (˜ ) = ˜ если i I C ( r )
r r ri r ri

и hi (˜ ) > ˜ , если i I A( r )} , r IAn .
r ri
Сокращенно неравенства hi (˜ ) < ˜ , при iIM(r) будем записывать
r ri
(˜) > r
r˜ (˜) > ˜
, а неравенства h (˜ ) > ˜ , при iIA(r) как h
hM ( r ) rr .
r r
M (r) A( r ) A( r )
i i

Как видно из определения, для каждого множества D r разбиения D задано
множество элементов C (r ) , называемых диктаторами, которые получают
оптимальные планы, остальные элементы при этом получают некоторые
26
неоптимальные для себя планы. Разбиение назовем разбиением на
B

множества диктаторства, а сами множества Dr - множествами
диктаторства.
Далее будем предполагать, что в каждом из множеств Dr разбиения
D планы, назначаемые всем активным элементам зависят только от
сообщений диктаторов C (r ) в этом множестве и не зависит от сообщений
остальных элементов, если вектор сообщений ˜ находится в этом
r
множестве. То есть, существует функция x r (˜ (r ) ) , определенная на для
rC
всех ˜ ( r ) I ProjC ( r ) D r , такая, что для всех ˜ I D r выполняется
rC r

h(˜ ) = x r (˜ (r ) ) и выполнено предположение
r rC
rIAn
А.2.1.1. [53] Для всех существует функция
x r : ProjC ( r ) D r ® R n , такая, что "˜ I D r выполнено h(˜ ) = x r (˜ (r ) ) .
r r rC
Содержательно предположение А.2.1.1 означает, что планы,
назначаемые для всех векторов сообщений из одного и того же множества
диктаторства, не зависят от сообщений АЭ, не являющихся диктаторами.
Определение 2.1.2. [53] Определим совокупность множеств
r r
n
Dr ={rIR : rM(r)> x M ( r ) ( rC ( r ) ) , Dr, rA(r)< x A( r ) (rC ( r ) ) },
rC( r ) = Proj
0
C(r)

rIAn.
Из определения 2.1.2 очевидно, что для любого r IAn выполнено
0
включение D r I Dr . Также очевидно, что если для любого вектора

сообщений ˜ I Dr выполняется h(˜ ) = x r (˜ (r ) ) , то для любого вектора
0
r r rC
0
истинных точек пика r I Dr сообщение достоверной информации является
0
наилучшим сообщением из Dr для всех АЭ.
Теорема 2.1.1. [53] Пусть I - множество активных элементов,
функции полезности которых обобщенно однопиковые. Пусть механизм
h : R n ® R n удолетворяет А.2.1.1 и D=D0 , тогда он неманипулируем.¦
Теорема 2.1.1. – это достаточные условия неманипулируемости
прямых механизмов планирования, которые будут использованы в разделе

27
3.1 для доказательства неманипулируемости механизма обмена в ОС с
веерной структурой взаимодействия агентов.

Стандартная модель теории контрактов [59,64,65,67-70,73-77,79-
82,85-89,91,95].
Рассматривается система из центра (principal) и одного АЭ (agent).
Центр продает агенту некий товар в количестве q по цене t. Функция
j 0 (t , q ) = t - C ( q ) .
полезности центра Функция C(q) – стоимость
производства товара для центра – дважды дифференцируемая выпуклая
функция, C`(0)=0, C`(?)=?. Функция полезности АЭ j1 (t , q,q ) = u (q , q ) - t .
q I Q = [q ,q ] – положительный параметр, тип АЭ, характеризующий его
«вкус». Функция является монотонно возрастающей функцией своих
аргументов.
Центру известно множество Q и вероятностное распределение типа
АЭ на этом множестве F(?).
Задача центра – максимизировать свою полезность.
На основании принципа выявления5 (revelation principle) строится
неманипулируемый механизм – «меню» контрактов {q(.), t (.)} , зависящий
от сообщаемой АЭ оценки своего типа.
Необходимые условия неманипулируемости механизма имеют
следующий вид:
¶u
i dt dq
(q ) = (q(q ),q ) (q )
i dq
( IC1 ) i ¶q dq
"q I Q, i
¶u2
dq
( IC2 ) (q(q ),q ) (q ) ? 0
i
i ¶q¶q dq
i
При выполнении условий Спенса-Мирлиса [91] -
¶ 2u
"q, "q , (q,q ) > 0 , доказано, что функция q(q ) является неубывающей
¶q¶q
функцией своего аргумента.



5
Принцип выявления – западный аналог принципа открытого управления, сформулированного в
ТАС. Для АС с одним АЭ эти принципы эквивалентны [10,53]
28
¶u
Предполагается, что "q, "q ,(q,q ) > 0 . Вводится функция прибыли
¶q
агента при использовании оптимального неманипулируемого механизма в
зависимости от его типа - n (q ) = u (q(q ),q ) - t (q ) . Причем, при выполнении
dn ¶u
(q ) = (q(q ),q ) > 0 . Поэтому, выполнение
условия IC1, "q I Q,
dq ¶q
условий индивидуальной рациональности агента ( "q I Q,n (q ) ? 0 ) может
быть обеспечено следующим образом - n (q ) = 0 , из чего следует, что
¶u
q
n (q ) = o (q(t ),t )dt , и
¶q
q


¶u
q
t (q ) = u (q(q ),q ) - o (q(t ),t )dt .
q ¶q


Задача центра (построение механизма, максимизирующего его
прибыль) сводится к решению следующего уравнения:
¶H * dq *
(q (q ),q ) = 0 при условии (q ) ? 0 . Здесь H (q (q ),q ) = j 0 (q (q ), t (q )) .
dq
¶q
Данный принцип построения неманипулируемых механизмов для
решения задач теории контрактов является частным случаем общего
принципа построения неманипулируемых механизмов обмена, который
будет введен в разделе 1.5.
Обменная экономика Эджворта.[81,85,94,95] Данная модель
экономики известна также как экономика чистого обмена (pure exchange
economy). Рассматривается система из двух агентов. В системе имеются
товары (ресурсы) двух типов в ограниченном количестве, распределенные
между агентами. Используя терминологию, введенную в разделе 1.1,
? y 110 y12 o
0

заданы начальное распределение ресурсов y = c 2 0 ? и ресурсные
0
cy 1 2 0?
y2o
e
ограничения Y1 и Y2 ( y 11 + y 21 = Y1 и y 1 2 + y 2 2 = Y2 , y1 = ( y 11 , y 1 2 ) ,
0 0 0 0



y2 = ( y 21 , y 2 2 ) ).
Каждый из агентов обладает собственными отношениями
предпочтения на множестве возможных распределений товаров,
заданными неприрывными функциями предпочтения j1 ( y1 ) и j 2 ( y 2 ) ,
29
которые также строго монотонны и квазивыпуклы (множество значений y
для которых j ( y ) ? j ( x) выпукло для "x ) [28,56,60,81,85,95].
Кроме того, задана рыночная стоимость каждого вида товаров
p = ( p1 , p2 ) , в соответствии с которой определяется рыночная ценность
набора товаров каждого из агентов - p ? yi , i = 1,2 .
Агенты могут перераспределять между собой ресурс с целью увеличит
рыночную стоимость своего набора товаров (с учетом своих
предпочтений). Задача заключается в определении оптимальных по Парето
распределений ресурсов (распределение ресурсов Парето оптимально, если
не существует другого распределения ресурсов, которое не менее
предпочтительное для каждого из агентов и более предпочтительное для
одного из них) с учетом заданных рыночных цен.
Для исследования описанной выше модели применяется «ящик
Эджворта» - графическое отображение на множестве возможных
распределений ресурсов (см. рисунок 4.)

y210
А
P2 2




P
y*
y220
1
Cc

Bl

y0
y120
Ps
А1 y110

Рис. 4. «Ящик Эджворта»

Длины сторон ящика равны общему количеству каждого из видов
ресурсов в системе (Y1 и Y2). Левый нижний угол - агент 1, верхний правый
30
– агент 2. Точка y0 – начальное распределение ресурсов в системе,
(учитывая, что y 11 + y 21 = Y1 и y 1 2 + y 2 2 = Y2 , берется y = y1 = ( y 11 , y 1 2 ) ).
Кривые Р1 и Р2 - кривые равных предпочтений агентов
( "yi I Pi j i ( yi ) = j i ( y 0 ), i = 1,2 ). Заштрихованная область между ними –
множество распределенй ресурсов, предпочтительных с точки зрения
каждого из агентов. Линия Bl - «бюджетная» линия - множество
распределений ресурсов, чьи рыночные стоимости эквивалентны
( "y I BL p ? y = p ? y 0 ). Кривая Ps - множество оптимальных по Парето
распределений ресурсов между агентами. Кривая Сс - контактная кривая
(contact curve) – часть кривой Ps, принадлежащая области
предпочтительных распределений ресурсов с точки зрения каждого из
агентов. Точка y* - точка пересечения кривой Сс и линии Bl – точка
равновесного по Вальрасу перераспределения ресурсов между агентами,
которая и является искомым рыночным равновесием. Само же равновесие
по Вальрасу определяется равновесными ценами p* и равновесным
перераспределением ресурсов y*.
Ящик Эджворта может быть широко использован для рассмотрения
задач обмена в активных системах, состоящих из двух агентов, и в которых
имеется два вида ресурсов. Подобные ОС будут рассмотрены в главе 2
данной работы, а данный графический метод будет использован в
дискретном подходе к построению неманипулируемых механизмов
обмена.
Механизмы Маскина и МакКельви. Данные механизмы известны,
как механизмы, реализующие заданное соответствие группового выбора
(СГВ).
Теория реализуемости представляет собой раздел теории управления
социально-экономическими системами с сообщением информации.
Наиболее полный обзор существующих результатов теории реализуемости
можно найти в [27,53,60,83,84,92,93]. В теории реализуемости исследуется
реализуемость соответствий группового выбора, свойства реализующих
механизмов [78,80,83,92], модели поведения АЭ в детерминированном
случае, и в случае наличия вероятностной неопределенности [87,88] и их
влияние на реализуемость СГВ.
31
Приведем известные условия реализуемости соответствий группового
выбора [66,83,90].
Говорят, что механизм G (полностью) реализует СГВ f [66], если
для всех R I A :
1) E G (R ) не пусто;

<< Пред. стр.

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

ОГЛАВЛЕНИЕ

След. стр. >>