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

Метод выбора, который максимизирует полезность

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

• 1 Обозначение
• 2 Семейство решений
• 3 Правдивость
• 4 Сводный момент Кларка правило
• 5 Взвешенный механизм VCG
• 6 Минимизация затрат
• 7 Приложения
  • 7.1 Аукционы
  • 7.2 Открытый проект
  • 7.3 Самые быстрые пути
• 8 Уникальность
• 9 Вычислительные проблемы
• 10 См. Также
• 11 Ссылки

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

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

$vi:\; X\; ⟶\; R\; +\; \{\backslash \; displaystyle\; v\_\; \{i\}:\; X\; \backslash \; longrightarrow\; R\; \_\; \{+\}\}$

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

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

$ui:\; =\; vi\; (x)\; +\; pi\; \{\backslash \; displaystyle\; u\_\; \{i\}:\; =\; v\_\; \{i\}\; (x)\; +\; p\_\; \{i\}\}$

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

$xopt\; (v)\; =\; arg\; \; max\; x\; \in \; X\; \sum \; i\; =\; 1\; nvi\; (x)\; \{\backslash \; displaystyle\; x\; ^\; \{opt\}\; (v)\; =\; \backslash \; arg\; \backslash \; max\; \_\; \{x\; \backslash \; in\; X\}\; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{n\}\; v\_\; \{i\}\; (x)\}$

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

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

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

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

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

$pi:\; =\; \sum \; j\; \ne \; ivj\; (x\; \ast )\; \{\backslash \; displaystyle\; p\_\; \{i\}:\; =\; \backslash \; sum\; \_\; \{j\; \backslash \; neq\; i\}\; v\_\; \{j\}\; (x\; ^\; \{*\})\}$

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

$pi\; +\; =\; hi\; (v\; -\; i)\; \{\backslash \; displaystyle\; p\_\; \{i\}\; +\; =\; h\_\; \{i\}\; (v\; \_\; \{-\; i\})\}$

где $v\; -\; i\; =\; (v\; 1,\dots ,\; vi\; -\; 1,\; vi\; +\; 1,\dots ,\; vn)\; \{\backslash \; displaystyle\; v\; \_\; \{-\; i\}\; =\; (v\_\; \{1\},\; \backslash \; dots,\; v\_\; \{i-1\},\; v\_\; \{i\; +\; 1\},\; \backslash \; dots,\; v\_\; \{n\})\}$, что is, $привет\; \{\backslash \; displaystyle\; h\_\; \{i\}\}$- это функция, которая зависит только от оценки других.

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

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

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

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

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

$hi\; (v\; -\; i)\; =\; 0\; \{\backslash \; displaystyle\; h\_\; \{i\}\; (v\; \_\; \{-\; i\})\; =\; 0\}$,

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

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

$hi\; (v\; -\; i)\; =\; -\; max\; x\; \in \; X\; \sum \; j\; \ne \; ivj\; (x)\; \{\backslash \; displaystyle\; h\_\; \{i\}\; (v\; \_\; \{-\; i\})\; =\; -\; \backslash \; max\; \_\; \{x\; \backslash \; in\; X\}\; \backslash \; sum\; \_\; \{j\; \backslash \; neq\; i\}\; v\_\; \{j\}\; (x)\}$

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

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

Это в точности внешний эффект игрока $i\; \{\backslash \; displaystyle\; i\}$.

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

• Индивидуальная рациональность : для каждого игрока i, $vi\; (x)\; +\; pi\; \ge \; 0\; \{\backslash \; displaystyle\; v\_\; \{i\}\; (x)\; +\; p\_\; \{i\}\; \backslash \; geq\; 0\}$. Это означает, что все игроки получают положительную пользу от участия в аукционе. Никого не заставляют делать ставки.
• Никаких положительных переводов: для каждого игрока i $p\; i\; \le \; 0\; \{\backslash \; displaystyle\; p\_\; \{i\}\; \backslash \; leq\; 0\}$. Механизм не должен ничего платить участникам торгов.

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

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

$xopt\; (v)\; =\; arg\; \; max\; x\; \in \; X\; \sum \; i\; =\; 1\; nwivi\; (x)\; \{\backslash \; displaystyle\; x\; ^\; \{opt\}\; (v)\; =\; \backslash \; arg\; \backslash \; max\; \_\; \{x\; \backslash \; in\; X\}\; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{n\}\; w\_\; \{i\}\; v\_\; \{i\}\; (x)\; \}$

где $wi\; \{\backslash \; displaystyle\; w\_\; \{i\}\}$- вес, присвоенный агенту $i\; \{\backslash \; displaystyle\; i\}$.

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

$pi:\; =\; 1\; wi\; \sum \; j\; \ne \; iwjvj\; (x\; \ast )\; \{\backslash \; displaystyle\; p\_\; \{i\}:\; =\; \{1\; \backslash \; over\; w\_\; \{i\}\}\; \backslash \; sum\; \_\; \{j\; \backslash \; neq\; i\}\; w\_\; \{j\}\; v\_\; \{j\}\; (x\; ^\; \{*\})\}$

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

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

Аукционы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Области оценок агентов - это связанные множества (в частности, у агентов могут быть реальные предпочтения, а не только интегральные предпочтения);
• Имеется правдивый механизм, который реализует определенную функцию $O\; utcome\; \{\backslash \; displaystyle\; Outcome\}$с определенными функциями оплаты $p\; 1,\dots ,\; pn\; \{\backslash \; displaystyle\; p\_\; \{1\},\; \backslash \; dots,\; p\_\; \{n\}\}$;
• Есть еще один правдивый механизм, который реализует ту же функцию $O\; utcome\; \{\backslash \; displaystyle\; Outcome\}$с разными функциями оплаты $p\; 1\; \prime ,\dots ,\; pn\; \prime \; \{\; \backslash \; displaystyle\; p\; \text{'}\_\; \{1\},\; \backslash \; dots,\; p\text{'}\; \_\; \{n\}\}$;

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

$pi\; \prime \; (vi,\; v\; -\; i)\; =\; pi\; (vi,\; v\; -\; i)\; +\; hi\; (v\; -\; i)\; \{\backslash \; displaystyle\; p\; \text{'}\_\; \{i\}\; (v\_\; \{i\},\; v\; \_\; \{-\; i\})\; =\; p\_\; \{i\}\; (v\_\; \{i\},\; v\; \_\; \{-\; i\})\; +\; h\_\; \{i\}\; (v\; \_\; \{-\; i\})\; \}$

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

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

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

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

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