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

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

Обозначения

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

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

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

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

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

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

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

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

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

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

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

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

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

3. Платит каждому агенту $i$ , сумма денег, равная общей стоимости других агентов:

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

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

p_{i}+h_{i}(v_{-i})

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

Правдивость

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

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

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

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

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

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

h_{i}(v_{-i})=0

,

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

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

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

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

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

i

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

i

присутствует).

Это именно внешний вид игрока $i$ . ^[2]

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

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

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

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

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

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

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

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

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

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

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

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

Приложения

Аукционы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

Ссылки

^ Перейти обратно: ^а ^б ^с ^д ^и Вазирани, Виджай В .; Нисан, Ноам ; Рафгарден, Тим ; Тардос, Ева (2007). Алгоритмическая теория игр (PDF) . Кембридж, Великобритания: Издательство Кембриджского университета. ISBN 0-521-87282-0 .
^ Аврим Блюм (28 февраля 2013 г.). «Алгоритмы, игры и сети. Лекция 14» (PDF) . Проверено 28 декабря 2015 г.
^ Перейти обратно: ^а ^б ^с Нисан, Ноам; Ронен, Амир (2001). «Проектирование алгоритмических механизмов». Игры и экономическое поведение . 35 (1–2): 166–196. CiteSeerX 10.1.1.16.7473 . дои : 10.1006/game.1999.0790 .

[AGT07-1] Перейти обратно: ^а ^б ^с ^д ^и Вазирани, Виджай В .; Нисан, Ноам ; Рафгарден, Тим ; Тардос, Ева (2007). Алгоритмическая теория игр (PDF) . Кембридж, Великобритания: Издательство Кембриджского университета. ISBN 0-521-87282-0 .

[2] Аврим Блюм (28 февраля 2013 г.). «Алгоритмы, игры и сети. Лекция 14» (PDF) . Проверено 28 декабря 2015 г.

[NisanRonen01-3] Перейти обратно: ^а ^б ^с Нисан, Ноам; Ронен, Амир (2001). «Проектирование алгоритмических механизмов». Игры и экономическое поведение . 35 (1–2): 166–196. CiteSeerX 10.1.1.16.7473 . дои : 10.1006/game.1999.0790 .

[1]

[2]

[3]