Механизм Викри–Кларка–Гроувса

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

Существует ряд возможных результатов.${\displaystyle X}$

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

${\displaystyle v_{i}:X\to \mathbb {R} _{+}}$

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

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

${\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 я}$${\displaystyle v_{i}(x)}$${\displaystyle x}$

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

3. Он выплачивает каждому агенту сумму денег, равную общей стоимости других агентов:${\displaystyle я}$

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

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

${\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. Агенту выплачивается общая стоимость других агентов; следовательно, вместе с его собственной стоимостью, общее благосостояние агента в точности равно общему благосостоянию общества. Следовательно, стимулы агента соответствуют стимулам общества, и агент мотивирован быть правдивым, чтобы помочь механизму достичь своей цели.

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

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

Например, можно взять:

${\displaystyle h_{i}(v_{-i})=0}$,

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

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

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

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

(социальное благополучие других, если мы отсутствуем) - (социальное благополучие других, когда мы присутствуют).${\displaystyle я}$${\displaystyle я}$

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

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

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

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

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

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

где — вес, назначенный агенту .${\displaystyle w_{i}}$${\displaystyle я}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Механизм VCG должен вычислять оптимальный результат на основе отчетов агентов (шаг 2 выше). В некоторых случаях этот расчет является вычислительно сложным. Например, в комбинаторных аукционах вычисление оптимального назначения является NP-трудным . ^{[1] : 270–273, гл.11}

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

• Разработка алгоритмического механизма
• Совместимость стимулов
• Квадратичное голосование