Применение дизайна механизмов в различных задачах

Как уже отмечалось во введении, дизайн механизмов применяется в самых различных областях. Данная секция предназначена для ознакомления читателя с тем, какие вообще бывают механизмы, какие задачи они позволяют решать. В качестве примера будет рассмотрено применение дизайна механизмов для задачи о пробках (congestion games).

Впервые задачи о пробках стал изучать Rosenthal (1973). Он рассматривал задачи следующего вида: имеется n игроков и t факторов. У каждого игрока есть набор стратегий, который соответствует выбору подмножества факторов. Затраты игрока от стратегии рассчитываются как сумма затрат от использования выбранных факторов, которые в свою очередь зависят от количества людей, использующих данный фактор (чем больше людей его использует, тем больше затраты).

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

Модель задается следующим образом.

Есть одно благо, которое каждый агент может или потреблять, или не потреблять. Потребление блага увеличивает затраты, которые зависят от среднего уровня потребления блага. Затраты могут различаться, но количество возможных функций затрат ограничено. За R обозначается множество индексов возможных функций затрат. Агенты делятся на группы по типу функции затрат (у двух агентов из одной группы — одинаковые функции затрат). За m_r (r? R) принимаются доли групп относительно общего числа людей. То есть, ?m_r = 1.

z_r? [0; m_r] - доля людей в группе r, потребляющих благо.

Z = {z? R^|R| ||? r? R, z_r? m_r} - множество состояний населения.

x = ?z_r? [0; 1] - общая доля людей, потребляющих благо.

Если агент i, принадлежащий группе r? R, потребляет благо, то его выигрыш составляет v_i — и_r •T (x), где v_i — индивидуальная выгода от потребления блага; T — издержки (строго возрастающая, выпуклая функция); и_r — параметр, соответствующий группе r. Если агент не потребляет благо, то его выигрыш составляет 0.

За D_r: R > [0; m_r] обозначается функция совокупного спроса на благо группы r. (•) — обратная функция спроса. (y) отображает наивысшую готовность y платить за благо в группе r.

В каждой группе предельным агентом называют агента, который получает наименьший выигрыш из всех, кто потребляет благо в этой группе. Его выигрыш F_r(z) = (z_r) — и_r •T (x).

Также предполагается, что для каждой группы r и_r лежит в закрытом интервале [; ].

Как уже говорилось, в модели предполагается, что планировщик знает T и {D_r}_{r ? R}, но не знает {и_r}_{r ? R}.

Игра задается как G = (F, и), где F = {F_r}_{r ? R}.

Состояние населения z? Z — равновесие по Нэшу, если? r? R:

.

Fujishima предлагает в качестве блага рассматривать вождение (индивиды выбирают ездить или нет, x — общее количество трафика на дорогах, T (x) — время в пути) или пользование Интернетом (индивиды выбирают подключать Интернет или нет, T (x) — время соединения, если общий объем подключившихся x).

Далее автор изучает динамику и вводит ценовую схему P (x) — налог, установленный на людей, потребляющих благо. Планировщик хочет достичь социальный оптимум. Вводится функция общественного благосостояния:

.

Таким образом, планировщик хочет применить функцию социального выбора f ^* И > Z:

.

Fujishima решает эту задачу для различных видов динамики.

Sandholm (2005) наоборот рассматривал случай, где планировщик знает функции затрат агентов, но не знает функции спроса.

В действительности же, планировщику обычно неизвестны ни функция спроса, ни функция затрат. Han et al (2010) пытались разобраться с этой проблемой. Они свели задачу о пробках к вариационным неравенствам и решали ее с помощью созданного ими итерационного алгоритма. Но, во-первых, в их модели у планировщика есть оценка функций затрат в каждом периоде и предполагается, что она сходится к действительной функции затрат. Во-вторых, в их модели транспортное движение находится в равновесии в каждом периоде (это предположение для вариационных неравенств), но в действительности агентам требуется время, чтобы прийти к равновесию.

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

Также существует довольно много статей, посвященных другим вопросам. Например, Fujishima (2011) рассматривает эволюционное внедрение (evolutionary implementation) оптимального числа и размера городов, где планировщик приводит экономику к оптимуму в долгосрочном периоде без «комовой» (lumpy) миграции и не зная предпочтений.