Механизмы распределения ресурса

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

Рассмотрим механизм распределения ресурсов , который обладает следующими свойствами:

1) Процедура планирования непрерывна и монотонна по сообщениям агентов (монотонность означает, что чем больше просит агент ресурса, тем больше он его получает).

2) Если агент получил некоторое количество ресурса, то он может получить и любое меньшее количество ресурса.

3) Если количество ресурса, распределяемое между группой агентов, увеличилось, то каждый из агентов этой группы может получить не меньшее количество ресурсов, чем раньше.

Целевая функция i -го агента зависит от типа r_i данного агента, который в случае механизмов распределения ресурса будет рассматриваться как оптимальное для данного агента количество ресурсов, и называться точка пика.

Допустим, что целевая функция агента имеет единственный максимум по x_i в точке пика. Т.е. агенту нужно некоторое количество ресурса, если ему недодают ресурса – его полезность при этом меньше, если ему дают лишний ресурс – его полезность тоже меньше. Единственным максимумом может быть и бесконечность, т.е. целевая функция может монотонно возрастать. Т.е. по мере удаления агента от точки пика полезность агента убывает. Такие функции предпочтения называются однопиковые (см. рисунок 13).

Рис. 13. Однопиковая функция

Рассмотрим сначала пример, а потом приведем общие результаты.

Пример 3. n = 3, R –количество ресурса, , i = 1, 2, 3. Пусть R = 1; .

Имеем: .

1) Пусть каждый агент сообщает правду:

если .

2) Пусть Î (r₁; r₂).

Первый агент должен найти такое свое сообщение, которое обеспечивает ему оптимальное количество ресурса при условии, что оба его оппонента сообщают максимальные заявки. То есть, он решает задачу: . Получаем следующее равновесие Нэша:

.

Процедура распределения ресурса пропорционально заявкам, называется механизмом пропорционального распределения, это – самый распространенный способ распределения ресурса. Видно, что данная процедура распределения ресурса удовлетворяет условию нормировки – при любых комбинациях сообщений агентов распределяется в точности весь ресурс. Условия непрерывности и монотонности также выполнены.

Предположим, что сообщение каждого агента лежит от нуля до всего количества ресурсов, т.е., как минимум, агент может отказаться от ресурса, как максимум – может попросить весь ресурс, который имеется у центра.

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

Если каждый агент скажет правду, сколько ресурса ему нужно, тогда он получит меньше, что логично, потому что ресурса на всех не хватает – агенты сказали правду и были "пропорционально урезаны".

Предположим, что игру центр разыгрывает неоднократно. На втором шаге агенты попросят больше. Если каждый будет просить максимально возможную заявку, то все получат поровну. Если кому-то этого много, то излишки он может отдать другому, но кому-то все равно не хватает.

Данный механизм является манипулируемым, потому что агентам невыгодно сообщать достоверную информацию о своих типах – тех количествах ресурса, которое им необходимо. ·

Итак, рассмотрен пример механизма распределения ресурса. Рассчитано равновесие. Запишем результаты исследования таких механизмов в общем виде. Для этого попробуем сначала понять, какими свойствами характеризуется равновесие. Агентов можно разделить на две категории:

- «приоритетные» агенты (диктаторы) – те, кто получают абсолютно оптимальные для себя планы, то есть планы, равные их типам (при механизме распределения ресурса – те агенты, которые получают ресурса ровно столько, сколько им нужно),

- «обделенные» агенты – те, кому не хватает ресурса, те, кто хоть и просит по максимуму, но в равновесии получает меньше, чем ему нужно.

Утверждение 7. 1) Если некоторый агент в равновесии получает строго меньше ресурса, чем ему необходимо: , то в равновесии он запросит максимально возможное количество ресурса: .

2) Если кто-то из агентов в равновесии просит строго меньше максимума: , то это значит, что он получает количество ресурса, оптимальное для него: , т.е. является диктатором.

Утверждение 7 дает два свойства, характеризующие равновесие в механизмах распределения ресурса.

Введем определение анонимного механизма принятия решений, т.е. механизма, симметричного относительно перестановок агентов. Анонимность – демократическое требование, например, в процедурах выборов она отражается в том, что на избирательном участке обмен между двумя избирателями пустыми бланками бюллетеней не меняет результата выборов. Т.е. все находятся в равных условиях. Тогда, переставляя местами агентов, мы соответственно переставляем и планы этих агентов.

Утверждение 8.

1) Все анонимные механизмы распределения ресурса эквивалентны между собой, т.е. приводят при одних и тех же предпочтениях агентов к одним и тем же равновесным количествам ресурса, которые они получают.

2) Так как механизм пропорционального распределения является анонимным (все агенты входят в него симметрично: если мы поменяем их местами, ничего не изменится), а все анонимные механизмы эквивалентны между собой, то это значит, что все механизмы распределения ресурсов, которые являются анонимными, эквивалентны механизму пропорционального распределения.

Таким образом, любая анонимная процедура, удовлетворяющая перечисленным выше трем требованиям, приводит к одним и тем же результатам. А механизм пропорционального распределения (который является анонимным) достаточно прост по своему виду, поэтому прост и для исследования, и для агентов (ресурс делится пропорционально запросам),

Таким образом, утверждение 8 говорит, что, если мы ограничимся классом анонимных механизмов, то не нужно выдумывать сложных механизмов распределения ресурса – достаточно рассмотреть механизм пропорционального распределения. Кроме того, оказывается, что механизм пропорционального распределения эквивалентен механизму последовательного распределения, рассчитать равновесие для которого совсем просто.

Механизмы последовательного распределения ресурса. Механизм пропорционально распределения хорош тем, что он имеет простой вид и для него просто посчитать равновесие.

Механизм последовательного распределения заключается в следующем. Это – прямой механизм, т.е. каждого агента спрашивают о том, сколько ресурса ему нужно.

Предположим, что агенты сделали свои сообщения. Упорядочим их по возрастанию сообщений (первый попросил меньше всех ресурса, потом второй и т.д.): . Дальше применяем следующий алгоритм последовательного распределения (положив x_i:= 0, i Î N):

Шаг 1. Если мы можем дать каждому агенту столько, сколько попросил первый агент, то даем всем по (если , то ). Если не можем, распределяем ресурс между всеми агентами поровну (если , то ) и останавливаем алгоритм.

Шаг 2. Исключаем первого агента из рассмотрения, перенумеровываем агентов и возвращаемся к шагу 1.

Пример 4. Предположим, что все сообщили правду, тогда мы можем дать всем одновременно по минимуму – 0,3:

После первого шага: Первый агент удовлетворен полностью. Поэтому мы забываем про него и повторяем для тех, кто что-то еще требует. Остаток ресурса, равный 0,1, недостаточен для того, чтобы дать обоим агентам столько, сколько требует первый (бывший второй) – по 0,1, следовательно, мы должны остаток ресурса поделить поровну, т.е. по 0,05.

В результате второй агент получит 0,35, третий тоже 0,35:

Так работает механизм последовательного распределения. Понятно, что максимум через n шагов, где n – количество агентов, процедура остановится.

Утверждение 9. В механизме последовательного распределения ресурса агентам выгодно сообщать достоверную информацию, т.е. сообщение достоверной информации является доминантной стратегией каждого агента.

Другими словами, механизм последовательного распределения является неманипулируемым прямым механизмом.

Рассмотрим на предыдущем примере, может ли кто-то из агентов, сообщая неправду, улучшить свое положение?

Первый агент получает оптимальное количество ресурса, ему нет нужды искажать информацию. Предположим, что начинает изменять свое сообщение второй агент (завышает заявку или занижает). Если он будет уменьшать свою заявку, все изменится в тот момент, когда разность от сообщения окажется такой, чтобы, выдавая столько, сколько просит второй агент, нам хватало бы ресурса. Такая разность равна 0,05 (деление поровну). Это значит, что второй агент должен заявить 0,35. Если он заявляет 0,35, то он получает 0,35, что и получал до этого, т.е. никакой выгоды занижение ему не принесло. Если же он сообщит меньше, чем 0,35, то он и получит столько, сколько сообщит, т.е. меньше 0,35. Ему это не выгодно, т.к. в действительности ему требуется 0,4. Таким образом, уменьшать заявку ему не выгодно.

Если же он начинает просить больше, чем 0,4, то вообще ничего не изменится, т.к. на втором шаге ресурса и так не хватает, и его остаток делится поровну между вторым и третьим агентами.

Аналогично для других агентов показывается, что, увеличивая или уменьшая до определенного уровня заявку, они ничего для себя не меняют, а дальнейшее уменьшение заявки дает уменьшение количества получаемого ресурса.

Утверждение 9 говорит о том, что при механизме последовательного распределения агентам выгодно сообщать достоверную информацию. Анонимность (симметричность агентов) необходима для того, чтобы мы могли распределять минимум всем и/или делить ресурс поровну.

Следствием утверждения 9 является следующее: для механизма пропорционального распределения и, соответственно, для любого анонимного механизма (в силу утверждения 8) существует механизм последовательного распределения, в котором доминантной стратегией каждого агента является сообщение достоверной информации.

Дата добавления: 2014-01-20