Механизм Викри – Кларка – Гровса - Vickrey–Clarke–Groves mechanism

В конструкция механизма, а Викри–Кларк –Groves (VCG) механизм это общий правдивый механизм для достижения социально-оптимального решения. Это обобщение Аукцион Викри-Кларка-Гроувса. Аукцион VCG выполняет конкретную задачу: разделение предметов между людьми. VCG механизм является более общим: его можно использовать для выбора любого результата из набора возможных результатов.^[1]^:216–233

Обозначение

Есть набор ${ displaystyle X}$ возможных результатов.

Есть ${ displaystyle n}$ агенты, которые имеют разные оценки для каждого результата. Оценка агента ${ displaystyle i}$ представлен как функция:

{ displaystyle v_ {i}: X longrightarrow R _ {+}}

который выражает ценность каждой альтернативы в денежном выражении.

Предполагается, что у агентов есть Квазилинейная утилита функции; это означает, что если результат ${ displaystyle x}$ и дополнительно агент получает платеж ${ displaystyle p_ {i}}$ (положительный или отрицательный), тогда общая полезность агента ${ displaystyle i}$ является:

{ displaystyle u_ {i}: = v_ {i} (x) + p_ {i}}

Наша цель - выбрать результат, который максимизирует сумму значений, а именно:

{ displaystyle x ^ {opt} (v) = arg max _ {x in X} sum _ {i = 1} ^ {n} v_ {i} (x)}

Другими словами, наша функция общественного выбора утилитарный.

Семейство решений

Семейство VCG - это семейство механизмов, реализующих утилитарную функцию благосостояния. Типичный механизм семейства VCG работает следующим образом:

1. Он просит агентов сообщить о своей функции ценности. То есть каждый агент ${ displaystyle i}$ должен сообщить ${ Displaystyle v_ {я} (х)}$ для каждого варианта ${ displaystyle x}$ .

2. На основе отчета-вектора агентов. ${ displaystyle v}$ , он вычисляет ${ displaystyle x ^ {*} = x ^ {opt} (v)}$ как указано выше.

3. Это выгодно каждому агенту. ${ displaystyle i}$ , денежная сумма, равная общей стоимости Другой агенты:

{ displaystyle p_ {i}: = sum _ {j neq i} v_ {j} (x ^ {*})}

4. Это выгодно каждому агенту. ${ displaystyle i}$ , дополнительная сумма, основанная на произвольной функции ценностей других агентов:

{ displaystyle p_ {i} + = h_ {i} (v _ {- i})}

куда ${ displaystyle v _ {- i} = (v_ {1}, dots, v_ {i-1}, v_ {i + 1}, dots, v_ {n})}$ , то есть, ${ displaystyle h_ {i}}$ это функция, которая зависит только от оценки других.

Правдивость

Каждый механизм в семействе VCG - это правдивый механизм, то есть механизм, при котором предложение истинной стоимости доминирующая стратегия.

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

Функция ${ displaystyle h_ {i}}$ на шаге 4 не влияет на стимулы агента, так как зависит только от заявлений других агентов.

В Кларк правило поворота

Функция ${ displaystyle h_ {i}}$ - параметр механизма. Каждый выбор ${ displaystyle h_ {i}}$ дает другой механизм в семействе VCG.

Мы могли бы взять, например:

{ displaystyle h_ {i} (v _ {- i}) = 0}

,

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

Альтернативная функция:

{ displaystyle h_ {i} (v _ {- i}) = - max _ {x in X} sum _ {j neq i} v_ {j} (x)}

Это называется Правило поворота Кларка. Согласно правилу поворота Кларка, общая сумма, выплачиваемая игроком, составляет:

(социальное благополучие других, если

{ displaystyle i}

отсутствовали) - (социальное благополучие других, когда

{ displaystyle i}

настоящее).

Это как раз то внешность игрока ${ displaystyle i}$ .^[2]

Когда оценки всех агентов слабо положительны, правило поворота Кларка имеет два важных свойства:

Индивидуальная рациональность: для каждого игрока я, ${ displaystyle v_ {i} (x) + p_ {i} geq 0}$ . Это означает, что все игроки получают положительную пользу от участия в аукционе. Никого не заставляют делать ставки.
Без положительных трансферов: на каждого игрока я, ${ displaystyle p_ {i} leq 0}$ . Механизм не должен ничего платить участникам торгов.

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

Взвешенный механизм VCG

Вместо максимизации суммы значений мы можем захотеть максимизировать взвешенную сумму:

{ displaystyle x ^ {opt} (v) = arg max _ {x in X} sum _ {i = 1} ^ {n} w_ {i} v_ {i} (x)}

куда ${ displaystyle w_ {i}}$ это вес, присвоенный агенту ${ displaystyle i}$ .

Приведенный выше механизм VCG можно легко обобщить, изменив функцию цены на шаге 3 на:

{ displaystyle p_ {i}: = {1 over w_ {i}} sum _ {j neq i} w_ {j} v_ {j} (x ^ {*})}

Минимизация затрат

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

Платежи на этапе 3 отрицательны: каждый агент должен оплатить полную стоимость, понесенную всеми другими агентами. Если агенты свободны выбирать, участвовать или нет, то мы должны убедиться, что их чистый платеж неотрицательный (это требование называется индивидуальная рациональность ). Для этой цели можно использовать правило поворота Кларка: на шаге 4 каждый агент я оплачивается полная стоимость, которую понесли бы другие агенты, если бы агент я не будет участвовать. Чистый платеж агенту я это его предельный вклад в снижение общей стоимости.

Приложения

Аукционы

Аукцион Викри-Кларка-Гроувса представляет собой приложение механизма VCG для максимизации благосостояния. Здесь, ${ displaystyle X}$ - это набор всех возможных распределений элементов между агентами. Каждый агент присваивает индивидуальную денежную ценность каждому набору предметов, и цель состоит в том, чтобы максимизировать сумму значений всех агентов.

Хорошо известным частным случаем является Викри Аукцион. Здесь всего один предмет, а набор ${ displaystyle X}$ содержит ${ displaystyle n + 1}$ возможные исходы: либо продать предмет одному из ${ displaystyle n}$ агентов, либо не продавать его вообще. На шаге 3 агенту-победителю выплачивается 0 (поскольку общая стоимость остальных равна 0), а проигравшие получают выплату, равную объявленной стоимости победителя. На шаге 4 победитель платит вторую по величине ставку (общую стоимость остальных, если бы он не участвовал), а проигравшие оплачивают объявленную стоимость победителя (общую стоимость остальных, если бы они не участвовали). В итоге победитель платит вторую по величине ставку, а проигравшие - 0.

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

Общественный проект

Правительство хочет решить, браться ли за конкретный проект. Стоимость проекта составляет C. Каждый гражданин извлекает из проекта разные ценности. Проект следует предпринимать, если сумма ценностей всех граждан превышает стоимость. Здесь механизм VCG с правилом поворота Кларка означает, что гражданин платит ненулевой налог за этот проект тогда и только тогда, когда они являются основными, то есть без их декларации общая стоимость меньше, чем C и с их объявлением общая стоимость больше чем C. Эта схема налогообложения совместима со стимулами, но, опять же, она не сбалансирована с точки зрения бюджета - общая сумма собираемого налога обычно меньше C.^[1]^:221

Самые быстрые пути

В самый быстрый путь Проблема - это проблема минимизации затрат.^[3] Цель состоит в том, чтобы отправить сообщение между двумя точками в сети связи, которое моделируется в виде графа. Каждый компьютер в сети моделируется как ребро в графе. У разных компьютеров разная скорость передачи, поэтому каждое ребро в сети имеет числовую стоимость, равную количеству миллисекунд, необходимых для передачи сообщения. Наша цель - отправить сообщение как можно быстрее, поэтому мы хотим найти путь с наименьшей общей стоимостью.

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

Для решения этой проблемы можно использовать механизм VCG. Здесь, ${ displaystyle X}$ это множество всех возможных путей; цель - выбрать путь ${ displaystyle x in X}$ с минимальной общей стоимостью.

Ценность агента, ${ Displaystyle v_ {я} (х)}$ , минус время, потраченное на сообщение: оно отрицательно, если ${ Displaystyle я в х}$ и он равен нулю, если ${ Displaystyle я notin х}$ . Платеж на шаге 3 отрицательный: каждый агент должен заплатить нам общее время, потраченное другими агентами на сообщение (обратите внимание, что это значение измеряется в единицах времени. Мы предполагаем, что можно платить компьютерам в единицах времени. , или что это стандартный способ перевести время в деньги). Это означает, что вместе со своим собственным затраченным временем каждый агент фактически теряет общее время, которое потребовалось сообщению, чтобы добраться до места назначения, поэтому агент стимулируется помочь механизму достичь кратчайшего времени передачи.

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

Аналогичным образом можно решить и другие проблемы с графами, например минимальное остовное дерево или же максимальное соответствие. Аналогичное решение применимо к более общему случаю, когда каждый агент имеет некоторое подмножество ребер.^[3]

Другой пример, когда механизм VCG обеспечивает неоптимальное приближение, см. Правдивое планирование работы.

Уникальность

Механизм VCG реализует утилитарный функция социального выбора - функция, которая максимизирует взвешенную сумму значений (также называемую аффинный максимизатор). Теорема Робертса доказывает, что если:

Функции оценки агентов не ограничены (каждый агент может иметь в качестве функции значения любую функцию из ${ displaystyle X}$ к ${ Displaystyle mathbb {R}}$ ), и -
Есть как минимум три возможных исхода ( ${ displaystyle | X | geq 3}$ и как минимум три разных результата от ${ displaystyle X}$ может случиться),

тогда Только могут быть реализованы взвешенные утилитарные функции.^[1]^{:228, глава 12}Таким образом, при неограниченных оценках функции социального выбора, реализуемые механизмами VCG, являются Только функции, которые могут быть реализованы правдиво.

Более того, ценовые функции механизмов VCG также уникальны в следующем смысле.^[1]^:230–231 Если:

Области оценок агентов: связанные наборы (в частности, у агентов могут быть реальные предпочтения, а не только интегральные);
Существует правдивый механизм который реализует определенные ${ displaystyle Outcome}$ функция с определенными платежными функциями ${ displaystyle p_ {1}, dots, p_ {n}}$ ;
Есть еще один правдивый механизм, реализующий то же самое. ${ displaystyle Outcome}$ функция с разными платежными функциями ${ displaystyle p '_ {1}, dots, p' _ {n}}$ ;

Тогда существуют функции ${ displaystyle h_ {1}, dots, h_ {n}}$ такое, что для всех ${ displaystyle i}$ :

{ displaystyle p '_ {i} (v_ {i}, v _ {- i}) = p_ {i} (v_ {i}, v _ {- i}) + h_ {i} (v _ {- i}) }

То есть ценовые функции двух механизмов различаются только функцией, которая не зависит от оценки агента. ${ displaystyle v_ {i}}$ (только по оценкам других агентов).

Это означает, что механизмы VCG - единственные достоверные механизмы, которые максимизируют утилитарный социальное обеспечение.

Вычислительные проблемы

Механизм VCG должен рассчитать оптимальный результат на основе отчетов агентов (шаг 2 выше). В некоторых случаях это вычисление затруднительно. Например, в комбинаторные аукционы, вычисление оптимального назначения NP-жесткий.

Иногда бывают аппроксимационные алгоритмы к проблеме оптимизации, но использование такого приближения может сделать механизм неверным.^[3]