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

• Название: В теорию управления организационными
• Анкор: ВВедение в теорию управления организационными системами
• Дата: 21.05.2020
• Размер: 1.89 Mb.
• Имя файла: ВВедение в теорию управления организационными системами.pdf
• Тип: Учебник; #124282
• страница: 10 из 23

4.3. Механизмы распределения ресурса
Пусть какой-то ресурс имеется у центра, и он необходим аген- там. Задача центра – распределить его между агентами. Если центр знает эффективность использования ресурса подчиненными, то задача заключается в том, как распределить ресурс, например, чтобы суммарный эффект от его использования был максимальным. Если агенты являются активными, а центр не знает эффективности ис- пользования ресурса, и спрашивает у них: кому сколько ресурса нужно, и кто как будет его использовать, то, если ресурс ограничен, то агенты в общем случае не сообщат честно, кому сколько нужно, и ресурсов на всех не хватит. В каких ситуациях управляющий орган может предложить такую процедуру, то есть правило распределения ресурсов между агентами, которая была бы неманипулируема, то есть такую процедуру, чтобы каждому из агентов было выгодно говорить правду, независимо от того, сколько ресурса ему надо?
Рассмотрим механизм распределения ресурсов p(s), который обладает следующими свойствами:
1) процедура планирования непрерывна и монотонна по сооб- щениям агентов (монотонность означает, что чем больше просит агент ресурса, тем больше он его получает);

112 2) если агент получил некоторое количество ресурса, то он мо- жет, изменяя свою заявку, получить и любое меньшее количество ресурса;
3) если количество ресурса, распределяемое между группой агентов, увеличилось, то каждый из агентов этой группы получит не меньшее количество ресурсов, чем раньше.
Целевая функция агента
)
,
(
i
i
i
r
x
f
зависит от типа r
i
данного агента, который в случае механизмов распределения ресурса будет рассматриваться как оптимальное количество ресурса для данного агента.
Допустим, что целевая функция агента имеет единственный максимум по x
i
в точке пика. То есть агенту нужно некоторое коли- чество ресурса, если ему недодают ресурса – его полезность при этом меньше, если ему дают лишний ресурс – его полезность тоже меньше. Единственным максимумом может быть и бесконечность, то есть целевая функция может монотонно возрастать. Такие функ- ции предпочтения называются однопиковые (см. Рис. 4.1).
i
x
i
r
SP –однопиковая функция
Рис. 4.1. Однопиковая функция
Рассмотрим сначала пример, а потом приведем общие результа- ты.
Пример 4.1. Пусть n = 3,
,
)
(
3 2
1
R
s
s
s
s
s
x
i
i
i
+
+
=
=
p
R –количе- ство ресурса, s
i
Î [0; R]. Пусть R = 1;
5
,
0
;
4
,
0
;
3
,
0 3
2 1
=
=
=
r
r
r
Имеем:
1 2
,
1 3
2 1
=
>
=
+
+
R
r
r
r
1) Пусть каждый агент сообщает правду, тогда:
4
,
0
;
333
,
0
;
25
,
0 3
2 1
»
=
=
Þ
=
x
x
x
r
s
i
i
;

113 2) Пусть
33
,
0 3
=
=
Þ
=
R
x
R
s
i
i
Î (r
1
; r
2
).
Первый агент решает задачу:
7 6
3
,
0 2
1 1
1
=
Þ
=
+
s
s
s
,
35
,
0
;
35
,
0
;
3
,
0 1
;
1
;
7 6
*
3
*
2
*
1
*
3
*
2
*
1
=
=
=
Þ
=
=
=
Þ
x
x
x
s
s
s
Это – равновесие Нэша.
·
Приоритетные механизмы. В приоритетных механизмах рас- пределения ресурса, как следует из их названия, при формировании планов (решении о том, сколько ресурса выделить тому или иному агенту) в существенной степени используются показатели приорите- та агентов. Приоритетные механизмы в общем случае описываются следующей процедурой:
( )
( )
{
}
ï
ï
î
ï
ï
í
ì
>
h g
£
=
å
å
=
=
R
s
s
s
R
s
s
s
x
n
j
j
i
i
i
n
j
j
i
i
1 1
если
,
,
min если
,
, где n – число агентов, {s
i
}
i
Î N
– их заявки, {x
i
}
i
Î N
– выделяемые количества ресурса, R – распределяемое количество ресурса,
{
h
i
(s
i
)}
i
Î N
– функции приоритета агентов,
g – некоторый параметр.
Операция взятия минимума содержательно означает, что агент получает ресурс в количестве, не большем запрошенной величины.
Параметр
g играет роль нормировки и выбирается из условия вы- полнения балансового (бюджетного) ограничения:
{
}
R
s
s
n
i
i
i
i
=
h g
å
=1
)
(
,
min
, то есть подбирается таким, чтобы при данных заявках и функциях приоритета в условиях дефицита распределялся в точности весь ресурс R.
Приоритетные механизмы, в зависимости от вида функции при- оритета, подразделяются на три класса – механизмы прямых при-
оритетов (в которых
h
i
(s
i
) – возрастающая функция заявки s
i
,
i
Î N), механизмы абсолютных приоритетов, в которых приоритеты агентов фиксированы и не зависят от сообщаемых ими заявок
19
, и
19
Так как в механизмах абсолютных приоритетов планы, назначаемые
агентам, не зависят от их заявок, то в рамках гипотезы благожелатель-
ности можно считать любой механизм абсолютных приоритетов нема-

114
механизмы обратных приоритетов (в которых
h
i
(s
i
) – убывающая функция заявки s
i
, i
Î N). Рассмотрим последовательно механизмы прямых и обратных приоритетов.
Механизмы прямых приоритетов. Процедура распределения ресурса пропорционально заявкам, называется механизмом пропор-
ционального распределения:
x
i
(s) =
R
s
s
N
j
j
i
å
Î
Это – самый распространенный способ распределения ресурса.
Видно, что данная процедура распределения ресурса удовлетворят условию нормировки. При любых комбинациях сообщений агентов распределяется в точности весь ресурс. Условия непрерывности и монотонности также выполнены.
Предположим, что сообщение каждого агента лежит в диапа- зоне от нуля до всего количества ресурсов, то есть, как минимум, агент может отказаться от ресурса, как максимум, может попросить весь ресурс, который имеется у центра.
Если агент получил некоторое количество ресурса, то, умень- шая заявку, в силу непрерывности и монотонности процедуры рас- пределения ресурса, он всегда может получить меньшее количество, вплоть до нуля.
Если каждый агент скажет правду, сколько ему нужно, тогда он получит меньше, что логично, потому что ресурсов не хватает, агенты сказали правду и были «пропорционально урезаны».
Предположим, что игру центр разыгрывает неоднократно. На втором шаге агенты попросят больше. Если каждый будет просить максимально возможную заявку, то все получат поровну. Если кому- то этого много, то излишки он может отдать другому, но кому-то все равно не хватит.
Данный механизм является манипулируемым, потому что аген- там невыгодно сообщать достоверную информацию о своих типах – тех количествах ресурса, которое им необходимо.
Итак, выше рассмотрен пример механизма распределения ре- сурса. Рассчитано равновесие. Запишем результаты исследования
нипулируемым. Недостатком этого класса механизмов можно считать
то, что в них центр никак не использует информации, сообщаемой аген-
тами.

115 таких механизмов в общем виде. Для этого попробуем сначала понять, какими свойствами характеризуется равновесие. Агентов можно разделить на две категории:
1) «приоритетные» агенты (диктаторы) – те, кто получают абсолютно оптимальные для себя значения плана, то есть планы, равные их типам (при механизме распределения ресурса – те агенты, которые получают ресурса ровно столько, сколько им нужно),
2) «обделенные» агенты – те, кому не хватает ресурса, те, кто хоть и просит по максимуму, но в равновесии получает меньше, чем ему нужно.
Следующие два свойства характеризуют равновесие.
Утверждение 4.1.
1) Если некоторый агент в равновесии получает строго меньше ресурса, чем ему необходимо:
i
i
r
x
<
*
, то в равновесии он запросит максимально возможное количество ресурса:
R
s
i
=
*
2) Если кто-то из агентов в равновесии просит строго меньше максимума:
R
s
i
<
*
, то это значит, что он получает количество ресурса, оптимальное для него:
i
i
r
x
=
*
, то есть является диктато- ром.
Введем определение анонимного механизма принятия решений, то есть механизма, симметричного относительно перестановок агентов. Анонимность – демократическое требование, например, в процедурах выборов она отражается в том, что на избирательном участке обмен между двумя избирателями пустыми бланками бюл- летеней не меняет результата выборов. То есть все находятся в равных условиях. Тогда при перестановке местами агентов соответ- ственно переставляются и планы этих агентов.
Утверждение 4.2.
1) Все анонимные механизмы распределения ресурса эквива- лентны между собой, то есть приводят при одних и тех же предпоч- тениях агентов к одним и тем же равновесным количествам ресурса, которые они получают.
2) Так как механизм пропорционального распределения являет- ся анонимным (все агенты входят в него симметрично), а все ано- нимные механизмы эквивалентны между собой, то это значит, что все механизмы распределения ресурсов, которые являются аноним- ными, эквивалентны механизму пропорционального распределения.

116
Итак, любая анонимная процедура, удовлетворяющая перечис- ленным выше трем требованиям, приводит к одним и тем же резуль- татам. А механизм пропорционального распределения (который является анонимным) достаточно прост по своему виду, поэтому прост и для исследования, и для агентов (ресурс делится пропор- ционально запросам).
Таким образом, утверждение 4.2 говорит, что не нужно выду- мывать сложных механизмов распределения ресурса – если ограни- читься классом анонимных механизмов, то достаточно рассмотреть механизм пропорционального распределения. Кроме того, оказыва- ется, что механизм пропорционального распределения эквивалентен механизму последовательного распределения, рассчитать равнове- сие для которого совсем просто.
Механизмы последовательного распределения ресурса за- ключается в следующем. Это – прямой механизм, т.е. каждого аген- та спрашивают о том, сколько ресурса ему нужно.
Предположим, что агенты сделали свои сообщения. Упорядо- чим их по возрастанию сообщений (первый попросил меньше всех ресурса, потом второй и т.д.):
n
r
r
r

2 1
£
£
£
K
. Дальше применяем следующий алгоритм последовательного распределения (положив
x
i
:= 0, i
Î N):
Шаг 1. Если мы можем дать каждому агенту столько ресурса, сколько попросил первый агент, то даем всем по
1
r
(если
R
r
n
£
×
1

, то
1 1
1
;
,

:

,

:
r
n
R
R
N
i
r
r
r
r
x
x
i
i
i
i
×
-
=
Î
-
=
+
=
). Если не можем, распределяем ресурс между всеми агентами поровну (если
R
r
n
>
×
1

, то
N
i
n
R
x
i
Î
= ,
:
) и останавливаем алгоритм.
Шаг 2. Исключаем первого агента из рассмотрения, перенуме- ровываем агентов и возвращаемся к шагу 1.
Пример 4.2.1. Пусть
5
,
0 4
,
0 3
,
0
;
5
,
0
;
4
,
0
;
3
,
0
,
1 3
2 1
£
£
=
=
=
=
r
r
r
R
Предположим, что все агенты сообщили правду, тогда мы можем дать всем одновременно по минимуму
–
0,3:
3
,
0
;
3
,
0
;
3
,
0 3
2 1
=
=
=
x
x
x
После первого шага:
1
,
0
;
2
,
0
;
1
,
0
;
0 3
2 1
=
=
=
=
R
r
r
r
Первый агент удовлетворен полностью. Поэтому забываем про него и повто- ряем для тех, кому ресурс еще необходим. Остаток ресурса, равный
0,1, недостаточен для того, чтобы дать обоим агентам столько,

117 сколько требует первый (бывший второй) – по 0,1, следовательно, мы должны остаток ресурса поделить поровну, т.е. по 0,05.
В результате второй агент получит 0,35, третий тоже 0,35:
35
,
0 2
1 0
:
2 2
=
+
= x
x
·
Так работает механизм последовательного распределения. По- нятно, что максимум через n шагов, где n – количество агентов, процедура остановится.
Легко показать (сделайте это самостоятельно), что в механизме последовательного распределения ресурса агентам выгодно сооб- щать достоверную информацию, т.е. сообщение достоверной ин- формации является доминантной стратегией каждого агента.
Другими словами, механизм последовательного распределения является неманипулируемым прямым механизмом.
Рассмотрим на примере 4.2, может ли кто-то из агентов, сооб- щая неправду, улучшить свое положение?
Первый агент получает оптимальное количество ресурса, ему нет нужды искажать информацию. Предположим, что начинает изменять свое сообщение второй агент (завышает заявку или зани- жает). Если он будет уменьшать свою заявку, все изменится в тот момент, когда разность от сообщения окажется такой, чтобы, выда- вая столько, сколько просит второй агент, нам хватало бы ресурса.
Такая разность равна 0,05 (деление поровну). Это значит, что второй агент должен заявить 0,35. Если он заявляет 0,35, то он получает
0,35, что и получал до этого, т.е. никакой выгоды занижение ему не принесло. Если же он сообщит меньше, чем 0,35, то он и получит столько, сколько сообщит, т.е. меньше 0,35. Ему это не выгодно, т.к. в действительности ему требуется 0,4. Таким образом, уменьшать заявку ему не выгодно.
Если же он начинает просить больше, чем 0,4, то вообще ничего не изменится, т.к. на втором шаге ресурса и так не хватает, и его остаток делится поровну между вторым и третьим агентами.
Аналогично для других агентов показывается, что, увеличивая или уменьшая до определенного уровня заявку, они ничего для себя не меняют, а дальнейшее уменьшение заявки дает уменьшение количества получаемого ими ресурса.
Механизмы обратных приоритетов.Механизмы обратных приоритетов, в которых
h
i
(s
i
) является убывающей функцией s
i
,
i
Î N, обладают рядом преимуществ по сравнению с механизмами

118 прямых приоритетов. Проведем анализ механизма обратных при- оритетов с функциями приоритета
h
i
= A
i
/
s
i
, i
Î N, где {A
i
}
i
Î N
– некоторые константы (отметим, что механизм об- ратных приоритетов не удовлетворяет условию монотонности).
Величина A
i
характеризует потери ОС, если i-й агент вообще не получит ресурса. Тогда отношение A
i
/
s
i
определяет удельный эффект от использования ресурса. Поэтому механизмы обратных приоритетов иногда называют механизмами распределения ресур-
са пропорционально эффективности (ПЭ-механизмами).
Пример 4.2.2. Пусть имеются три агента (n = 3), А
1
= 16, А
2
= 9,
А
3
= 4; R = 18. Предположим сначала, что целью агентов является получение максимального количества ресурса. Определим ситуацию равновесия
Нэша.
Легко заметить, что функция
)}
/
(
,
{
min
)
(
i
i
i
i
s
A
s
s
x
g
=
достигает максимума по s
i
в точке, удовлетворяющей условию
s
i
=
g (A
i
/ s
i
).
Следовательно,
i
i
i
A
s
x
g
=
=
*
*
Определим параметр
g из балансового ограничения
R
A
x
n
i
i
n
i
i
=
g
=
å
å
=
=
*
1 1
. Тогда
2 1
÷
ø
ö
ç
è
æ
=
g
å
=
n
i
i
A
R
Для рассматриваемого примера
g = 4, а равновесные заявки, оп- ределяемые из условия
å
=
*
*
=
=
n
j
j
i
i
i
A
A
R
s
x
1
, равны: s
1
*
= 8; s
2
*
= 6,
s
3
*
= 4.
Проверим, что это действительно равновесие Нэша. Возьмем первого агента. Если он уменьшит свою заявку: s
1
= 7 < s
1
*
, то
s
1
+
s
2
*
+ s
3
*
< R. Следовательно, x
1
=
s
1
= 7< x
1
*
. Если же s
1
= 9> s
1
*
, то
g »4,5; x
1
= 8
º x
1
*
Легко показать [3], что вычисленные стратегии являются для агентов гарантирующими, то есть максимизируют их выигрыши при наихудших стратегиях остальных.
Если функции предпочтения агентов имеют максимумы в точ- ках {r
i
}
i
Î N
и если s
i
*
> r
i
, то i-й агент закажет ровно r
i
и столько же получит, так как при уменьшении заявки его приоритет возрастает.

119
Именно таким образом выделяется множество приоритетных потре- бителей ресурса.
·
Более того, можно показать, что при достаточно большом чис- ле агентов механизм обратных приоритетов со штрафами за несов- падение ожидаемого и планируемого эффектов оптимален в смыс- ле суммарной эффективности [3].