7.3. Задачи распределения с неоднородными выпуском и факторами производства

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

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

Мы несколько упростим общую модель, считая, что каждый агент потребляет только один продукт выпуска (или вкладывает только один фактор). В то же время функции затрат (или производственные функции) имеют достаточно общий вид: С(0) = 0 , С не убывает по жг- для любого i.

1. Бинарный спрос. Значение Шепли. Бинарная задача распределения затрат — это тройка (/, С, х), где I — конечное множество агентов, С : {0,1}п —> IR+ — неубывающая функция затрат такая, что С(0) = 0 , х = (жг)ге/ — набор, описывающий спрос жг- каждого агента i, причем жг- = 0 или 1.

Поскольку каждый из жг- может принимать только два значения — 0 или 1, то очень удобно вектор спроса х обозначать через S С I (S может оказаться пустым), а именно жг- = 1 в том и только том случае, если i ? S (вспомним здесь нечеткие кооперативные игры и отождествление (простой) коалиции с ее характеристической функцией (см.

если S С Т, то C(S) < С(Т) для любых S, Т С I?

Решение бинарной задачи распределения затрат (/, С, S) — это набор «долей затрат» у = (уг)ге/ таких, что

iji > 0 для любого г и ^^ ijj = C(S).

iei

Бинарный метод распределения затрат — это отображение ip , ставящее в соответствие каждой задаче (/, С, S) решение y = Как обычно, этой задаче соответствует аналогичная бинарная задача распределения излишка, причем здесь S — множество активных агентов, a F(S) — результирующий выпуск, подлежащий распределению.

Идея распределения затрат пропорционально спросу в модели с бинарным спросом сводится к распределению C(S) поровну между всеми агентами из S (оставляя нулевые затраты агентам вне S). Однако этот метод не учитывает «ответственности» агентов за возникновение затрат. Здесь очевидное требование состоит в том, что агент, спрос которого не порождает затрат, не должен платить ничего, т.е. мы имеем дело с аксиомой «болвана».

Обозначим через diC(S) = C(S) — C(S \ i) предельные затраты (сбережения) удаления агента i из коалиции S . Ясно, что diC(S) = 0 для г ^ S .

Аксиома «болвана» (DUM — Dummy):

если д{С{Т) = 0 для любых Т С I, то tpi(I,C,S) = 0 для любых /, S,i и С .

Аналогично случаю кооперативных игр агент называется «болваном» для функции затрат С, если затраты на его обслуживание нулевые, т.е. C(i) = 0 и беззатратно его добавление к любой коалиции S . Очевидно, что эгалитарный метод (у- = для г G S , yi — 0 для г ? S) этой аксиоме не

удовлетворяет.

Аксиома аддитивности (ADD — Additivity):

?>(/, СЛ+С2, S) = ?>(/, С1, S)+(p{I, С2, S) для всех /, С1, С2, S.

Заметим, что DUM и ADD вместе обеспечивают свойство постоянной отдачи (см. п. 7.2). Если С линейна, т.е. С(х) = cixi 1 то тогда tpi(I, С, S) = CjXi, где ж; = 1, если i G S, и Xi = 0 для i ? S .

Обозначим семейство методов распределения затрат, удовлетворяющих аксиомам аддитивности и «болвана», через В (DUM, ADD).

Для каждого I метод приращений (Incremental Method) определяет для каждого непустого подмножества S С I (включая S = I) перестановку (упорядочение) a(S) = (y^{s) = C{°i{S)),

yy°k{s) = dak(S)C((j1(S),.. .,(Tk{S)) ДЛЯ любого к = 1,.. ,,s.

(3.1)

Значение случайного упорядочения (random order value) — это выпуклая комбинация методов приращения, в которой веса не зависят от С .

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

у = Отметим, что мы можем выбирать произвольное множество «выпуклых» коэффициентов (т. е. неотрицательных, да

ющих в сумме единицу) для любой коалиции S . Например, для S = {1,2,3} мы можем выбрать перестановку (2,1,3), а для S' = {1,2,4} — выбрать перестановку (1,2,4). Наконец, для характеризации значения Шепли нам понадобится еще одна аксиома — аксиома симметричности, которую мы назовем так же, как в п. 7.1, «равным агентам - поровну» и которая утверждает, что если два агента симметрично влияют на функцию затрат, то их доли должны быть равными, точнее «Равным агентам - поровну» (ЕТЕ):

Если С(Т Ui) = С(Т U j) для любых i, j ф Т , то (pi(I,C, S) = (pj(I,C, S) для любых S С I, для любых С, i, j-

Предложение 7.3.1. (Weber, 1988). Множество значений случайного упорядочения совпадает с множеством В (DUM, ADD) методов распределения затрат, удовлетворяющих аксиомам «болвана» (DUM) и аддитивности (ADD).

Следующее следствие этого предложения, по сути дела, нам уже хорошо знакомо (см.

Следствие 7.3.1. Аксиомы DUM, ADD и ЕТЕ однозначно определяют метод распределения затрат — это значение Шепли, т. е. множество В (DUM, ADD, ЕТЕ) содержит единственный метод:

^,-(7, C,S) = J2 1)! J2 diC(T\Ji) для любого i ? S,

t = О S' T:TCS\t

\T\ = t

(fij(I, С, S) = 0, если j ^ S.

Это следствие выводится из приведенной выше теоремы Вебера с помощью следующего наблюдения (см. Moulin, 1995): метод из В (DUM, ADD) должен удовлетворять аксиоме, известной как независимость от несущественных затрат (Independence of Irrelevant Costs):

если С1 (Г) = С2 (Г) для любых Т С S, то (p{I,C1,S) = (p{I,C2,S) для любых I,Cl,C2,S. Метод приращений и значения случайного упорядочения, определяемые в контексте фиксированной популяции, могут распределять приоритеты (или «взвешивать» различные упорядочения) несогласованно с изменениями S. Поэтому мы должны переключиться на переменную популяцию. Обозначим через АГ максимальное множество (конечное и бесконечное), из которого могут выбираться агенты, через а — порядок приоритетов на А/. На любом конечном множестве S этот порядок индуцирует упорядочение cr(S), а формула (3.1) определяет метод а -приращений. Аналогично, согласованное значение случайного упорядочения является выпуклой комбинацией методов <7-приращений, в которой а варьируется по всем упорядочениям множества N, а коэффициенты не зависят от /, С и S:

(p{I,C,S)= Kva{S)(I,C,S) для любых I,C,S.

(jGS(JV)

Следующая аксиома (согласованность относительно «болвана» — DCY — Dummy-Consistency) утверждает, что удаление «болвана» не влияет на распределение затрат между остальными агентами:

если д{С{Т) = 0 для любого Т С I, то

для всех S, для любых /, i и С.

Следующее предложение, касающееся уже переменной популяции, является следствием теоремы 7.3.1.

Предложение 7.3.2. Множество согласованных значений случайного упорядочения совпадает с множеством В (DUM, DCY, ADD).

Известно несколько альтернативных характеризаций значения Шепли и значений случайного упорядочения, при которых аксиома аддитивности заменяется другими требованиями. Мы остановимся здесь лишь на двух (причем в контексте фиксированной популяции).

В случае значения случайного упорядочения доля агента зависит только от предельных затрат д{С{Т) . Это свойство называется маржинализмом (Marginalism):

если д{С1{Т) = diC2(T) для любых Т С S , то

(fii(I, С1, S) = (fii(I, С2, S) для любых I, С1, С2, S и i. Значение Шепли однозначно характеризуется аксиомами маржинализма и ЕТЕ (Young, 1985).

Другая характеризация значения Шепли основана на так называемом потенциале:

P(/,C) = ^(s"1)-(,ra"s)!C(S), где n= |/|, s=\S\. SCI П'

Значение Шепли можно представить в виде

?>,?(/, С, S) = diP(S, С') = P(S, С) - P(S \ i,C'). (3.2)

С.Харт и А.Мас-Колелл (Hart, Mas-Colell, 1989) показали, что значение Шепли полностью характеризуется существованием некоторого потенциала Р, удовлетворяющего (3.2) и такого, что Р(0,С) = 0.

Это сразу видно для случая двух агентов. Действительно, из (3.2) следует, что «за нулевой спрос не нужно платить»: из i G S следует уг- = 0. Поэтому yi = P(/,C)-C(l), у2 = Р(1,С)-С(2), У1 + У2=С(( 1,2)).

Эта система дает нам значение Шепли в случае двух агентов:

Ш = (С(1, 2) + С(г) — C(j))/2.

(Для произвольного п результат может быть получен по индукции.)

2. Переменный спрос на неделимые товары. Спрос каждого агента i есть жг- G {0,1, 2,..., Хг} (мы считаем Xi конечным).

Функция затрат С есть отображение прямого произведения [0,%]] = Пг'е/[0> ХЦ в IR+ такое, что из С(0) = 0 и х < х следует С(х) < С(х') . (Подчеркнем, что здесь [0, жг] — интервал целых чисел.) Решением задачи распределения затрат (/, С, х), где х ? [О, АГт], является вектор у ? R1 такой, что

у> Он ^Уг = С(х).

iei

Эта модель обобщает предыдущую модель бинарного спроса, в которой Xi = 1 для любого i. Наша задача — обобщить приведенные выше результаты (для бинарного спроса) на случай переменного спроса. Как и выше, мы начнем со случая фиксированной популяции. Сформулируем две аксиомы — «болвана» и аддитивности.

Аксиома «болвана» (DUM):

если diX(x) = 0 для любого х ? [0,X[/j] , то

tpi(I,C,x)0 для любого х ? [0,%]], для любого /, С и любого i ? I,

где д{С(х) = С(х) — С(х ||г жг- — 1) (д{С(х) = 0, если Xi = 0) обозначает предельные затраты при увеличении спроса агента i с г, - 1 до жг-.

Аддитивность (ADD):

Рассмотрим обобщение методов приращения в бинарной модели. Зафиксируем перестановку а множества (фиксированного) I и определим метод <7-приращения (или метод упорядоченного приоритета а ) у = ipa (/, С, х) следующим образом:

yai = C{x[ai]l 0),

Уа2 = С(ж[(7ь(72],0) - С(ж[(71],0),

Усгг = - C{x[(Ju_)(Jt_l]l0)1

yгде (ж[у], 0) обозначает вектор с той же проекцией на Т , что и х, и 0 на I \ Т .

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

Рассмотрим ресурсно монотонный метод рационирования г (для неделимых товаров). Поскольку мы считаем I фиксированным, то будем писать r(t,x) вместо r(I,t,x), где х ? [0,%]] и 0 < t < ж/.

(3.3)

Уг = YTtLi diC(r(t, x))dri(t, х) для любых I, С, х и i,

где dri(t,x) = 1, если i = ц является t-м элементом последовательности в(ж) , и dri(t,x) = 0 в противном случае.

Метод распределения затрат (3.3) называется методом, порожденным траекторией, поскольку для каждого х доли затрат вычисляются вдоль траектории t —> r(t,x), т.е. «вдоль последовательности» s(I,x), следующим образом: С (г, (1,ж)) платит агент i\ , C(r(2, х)) — C(r(l, х)) платит агент i2 и т. д. Для фиксированной популяции I имеет место следующая теорема.

Теорема 7.3.1. (Wang, 1998). Каждый метод распределения затрат, удовлетворяющий аксиомам DUM и ADD, является выпуклой комбинацией методов, порожденных траекториями (с коэффициентами, зависящими от /, но не зависящими от Сих). Никакие другие методы распределения затрат не удовлетворяют этим аксиомам.

Пусть t —т- r(t,x) описывается последовательностью в(ж) = {ii, i2,..., iXl} , в которой агент i появляется ровно жг- раз. Каждому методу рационирования г , или, эквивалентно, каждому семейству последовательностей в(ж) (одной для каждого х ) из [0,X[jj] поставим в соответствие следующий метод распределения затрат у = Для формулировки результата для случая переменной популяции нам понадобится, как всегда, аксиома согласованности относительно «болвана» (DCY - Dummy Consistering): если diC(x) = 0 для любого х ? [O.Xjjj] , то ср(1, С, ж)[дг-] = tp(I \ г, С, ждг-) для любых х ? [0, , для любых I, С и i.

Нетрудно показать, что метод, порожденный траекторией, является согласованным относительно «болвана» тогда и только тогда, когда соответствующий метод рационирования согласован (согласованность г означает следующее свойство порождающей последовательности s(I, х): последовательность s(I \ i, ждг-]) получается из s(I, х) удалением всех появлений агента г). Поэтому мы называем метод порожденным согласованной траекторией, если он выводится из согласованного метода рационирования с помощью (3.3).

Следствие 7.3.2. Каждый метод из В (DUM, DCY, ADD) является выпуклой комбинацией методов, порожденных согласованными траекториями. В (DUM, DCY, ADD) не содержит других методов.

Мы завершим эту главу двумя примерами — методом Шепли-Шубика и методом Аумана-Шепли.

Пример 1. Метод Шепли—Шубика. Среднее арифметическое методов приращения называется также методом Шепли-Шубика:

П—1 | / ^ Ч |

yf5(/,C,aO = E J~ Е №*ифО)-С(Ж[5]],0)).

j=0 ' SCI\i

\S\=s

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

Интересно, что метод Шепли-Шубика может быть охарактеризован с помощью одной дополнительной (относительно DUM и ADD) аксиомы, а именно аксиомы нижней границы (LC — Lower Bound):

0[дг-]) для любых /, С, жиг,,

где 0(C) —число товаров, не являющихся «болванами» для

С.

Следствие 7.3.3. Метод Шепли-Шубика является единственным методом в В (DUM, ADD), удовлетворяющим LC.

Пример 2. Метод Аумана—Шепли. Зафиксируем (/, С) и рассмотрим бинарную задачу (кооперативную игру) с ж/ агентами, в которой каждая единица каждого товара г соответствует одному агенту, так что мы имеем жг- агентов типа г. Обозначим через Iх это новое множество агентов, а через С — функцию затрат на подмножествах Iх :

для любой S С Iх C(S) = C'(z) , где Z{ — число агентов типа i в S .

Применим метод Шепли-Шубика к задаче (Iх, С, Iх) и суммируем (идентичные) доли затрат всех агентов типа г. Получающиеся доли затрат и определяют метод Аумана-Шепли.

Для любого вектора t из N1 (т.е. |/|-мерного вектора с натуральными координатами) будем обозначать через

лт - {tl)l ( > ~ Тт—Р

число монотонных траекторий из 0 в t (в [0, t]). Тогда метод Аумана-Шепли определяется следующим образом: "?(И)

of(I,C,x) = -L V А(*)А(0 • I f - I C(t),

А(Х) ' > V, ОТ

где t'i = хг - U (А(0) = 0) .

Метод Аумана-Шепли представляется наиболее естественным продолжением пропорционального распределения затрат на случай неоднородных продуктов.