В конструкции механизма , A Vickrey- Clarke -Groves ( ВКГ ) механизм является общим правдивым механизмом для достижения социально оптимального решения. Это обобщение аукциона Викри – Кларка – Гроувса . Аукцион VCG выполняет конкретную задачу: разделение предметов между людьми. ВКГ механизм является более общим: он может быть использован , чтобы выбрать любой исход из множества возможных исходов. [1] : 216–233
Обозначение
Есть набор возможных результатов.
Есть агенты, которые имеют разные оценки для каждого результата. Оценка агента представлен как функция:
который выражает ценность каждой альтернативы в денежном выражении.
Предполагается, что агенты обладают квазилинейными функциями полезности ; это означает, что если результат и дополнительно агент получает платеж (положительный или отрицательный), тогда общая полезность агента является:
Наша цель - выбрать результат, который максимизирует сумму значений, то есть:
Другими словами, наша функция социального выбора утилитарна .
Семейство решений
Семейство VCG - это семейство механизмов, реализующих утилитарную функцию благосостояния. Типичный механизм в семействе VCG работает следующим образом:
1. Он просит агентов сообщить о своей функции ценности. Т.е. каждый агент должен сообщить для каждого варианта .
2. На основе отчета-вектора агентов. , он вычисляет как указано выше.
3. Это выгодно каждому агенту. , сумма денег, равная общей стоимости других агентов:
4. Это выгодно каждому агенту. , дополнительная сумма, основанная на произвольной функции значений других агентов:
где , это, является функцией, которая зависит только от оценок других агентов.
Правдивость
Каждый механизм в семействе VCG - это правдивый механизм , то есть механизм, в котором предложение истинной стоимости является доминирующей стратегией .
Уловка заключается в шаге 3. Агенту платят полную стоимость других агентов; следовательно, вместе с его собственной ценностью общее благосостояние агента в точности равно общему благосостоянию общества. Следовательно, стимулы агента согласованы с мотивами общества, и агент стимулируется быть правдивым, чтобы помочь механизму достичь своей цели.
Функция на шаге 4 не влияет на стимулы агента, поскольку зависит только от заявлений других агентов.
Clarke правило поворота
Функция - параметр механизма. Каждый выбор дает другой механизм в семействе VCG.
Мы могли бы взять, например:
- ,
но тогда нам придется платить игрокам за участие в аукционе. Мы бы предпочли, чтобы игроки давали деньги механизму.
Альтернативная функция:
Это называется правилом поворота Кларка . Согласно правилу поворота Кларка, общая сумма, выплачиваемая игроком, составляет:
- (социальное благополучие других, если отсутствовали) - (социальное благополучие других, когда настоящее).
Это как раз и есть внешний вид плеера.. [2]
Когда оценки всех агентов слабо положительны, правило поворота Кларка имеет два важных свойства:
- Индивидуальная рациональность : для каждого игрока i ,. Это означает, что все игроки получают положительную пользу от участия в аукционе. Никого не заставляют делать ставки.
- Нет положительных переводов: для каждого игрока i ,. Механизм не должен ничего платить участникам торгов.
Это делает механизм VCG беспроигрышной игрой : игроки получают желаемые результаты и платят сумму, меньшую их выигрыша. Таким образом, игроки остаются с чистой положительной прибылью, а механизм получает чистую положительную выплату.
Взвешенный механизм VCG
Вместо максимизации суммы значений мы можем захотеть максимизировать взвешенную сумму:
где это вес, присвоенный агенту .
Приведенный выше механизм VCG можно легко обобщить, изменив функцию цены на шаге 3 на:
Минимизация затрат
Механизм VCG можно адаптировать к ситуациям, в которых целью является минимизация суммы затрат (вместо максимизации суммы выигрышей). Затраты могут быть представлены как отрицательные значения, так что минимизация затрат эквивалентна максимизации значений.
Платежи на шаге 3 отрицательны: каждый агент должен оплатить полную стоимость, понесенную всеми другими агентами. Если агенты свободны выбирать, участвовать или нет, то мы должны убедиться, что их чистый платеж неотрицателен (это требование называется индивидуальной рациональностью ). Для этой цели можно использовать правило поворота Кларка: на шаге 4 каждый агент оплачивается полная стоимость, которую понесли бы другие агенты, если бы агент не будет участвовать. Чистый платеж агенту это его предельный вклад в снижение общей стоимости.
Приложения
Аукционы
Аукцион Викри-Кларка-Гроувса - это приложение механизма VCG для максимизации благосостояния. Здесь,- это набор всех возможных распределений элементов между агентами. Каждый агент присваивает индивидуальную денежную ценность каждому набору предметов, и цель состоит в том, чтобы максимизировать сумму значений всех агентов.
Хорошо известным частным случаем является аукцион Викри . Здесь всего один предмет, а набор содержит возможные исходы: либо продать предмет одному из агентов, либо не продавать его вообще. На шаге 3 агенту-победителю выплачивается 0 (поскольку общая стоимость остальных равна 0), а проигравшие получают выплату, равную заявленной стоимости победителя. На шаге 4 победитель платит вторую по величине ставку (общая стоимость остальных, если бы он не участвовал), а проигравшие оплачивают объявленную стоимость победителя (общую стоимость остальных, если бы они не участвовали). В общем, победитель платит вторую по величине ставку, а проигравшие - 0.
Механизм VCG также может использоваться в двойном аукционе . Это наиболее общая форма двойного аукциона, совместимого со стимулами, поскольку он может обрабатывать комбинаторный аукцион с произвольными функциями стоимости пакетов. К сожалению, он не сбалансирован по бюджету: общая сумма, которую платят покупатели, меньше общей суммы, полученной продавцами. Следовательно, чтобы заставить его работать, аукционист должен субсидировать торговлю.
Общественный проект
Правительство хочет решить, браться ли за определенный проект. Стоимость проекта C . Каждый гражданин извлекает из проекта разные ценности. Проект следует начинать, если сумма ценностей всех граждан превышает стоимость. Здесь механизм VCG с правилом поворота Кларка означает, что гражданин платит ненулевой налог за этот проект тогда и только тогда, когда они являются основными, то есть без их декларации общая стоимость меньше C, а с их декларацией общая стоимость больше , чем C . Эта схема налогообложения является стимулом-совместимыми, но опять - таки это не бюджет сбалансирован - общая сумма собранных налогов, как правило , меньше , чем C . [1] : 221
Самые быстрые пути
Проблема самого быстрого пути - это проблема минимизации затрат. [3] Цель состоит в том, чтобы отправить сообщение между двумя точками в сети связи, которое моделируется в виде графа. Каждый компьютер в сети моделируется как ребро в графе. Разные компьютеры имеют разную скорость передачи, поэтому каждое ребро в сети имеет числовую стоимость, равную количеству миллисекунд, необходимых для передачи сообщения. Наша цель - отправить сообщение как можно быстрее, поэтому мы хотим найти путь с наименьшей общей стоимостью.
Если мы знаем время передачи каждого компьютера (- стоимость каждого ребра), то мы можем использовать стандартный алгоритм для решения задачи о кратчайшем пути . Если мы не знаем время передачи, мы должны попросить каждый компьютер сообщить нам время передачи. Но у компьютеров есть свои эгоистичные интересы, поэтому они могут не сказать нам правду. Например, компьютер может сказать нам, что время его передачи очень велико, поэтому мы не будем беспокоить его своими сообщениями.
Для решения этой проблемы можно использовать механизм VCG. Здесь,- это множество всех возможных путей; цель - выбрать путь с минимальной общей стоимостью.
Ценность агента, , это минус время, потраченное на сообщение: оно отрицательно, если и он равен нулю, если . Платеж на шаге 3 отрицательный: каждый агент должен платить нам общее время, потраченное другими агентами на сообщение (обратите внимание, что это значение измеряется в единицах времени. Мы предполагаем, что можно платить компьютерам в единицах времени. , или что это стандартный способ перевести время в деньги). Это означает, что вместе со своим собственным затраченным временем каждый агент фактически теряет общее время, которое потребовалось сообщению, чтобы добраться до пункта назначения, поэтому агент стимулируется помочь механизму достичь кратчайшего времени передачи.
Чтобы сделать механизм индивидуально рациональным, можно использовать правило поворота Кларка: после оплаты стоимости каждый агент получает от нас положительный платеж, равный времени, за которое сообщение пришло бы к месту назначения, если бы агент не присутствовали. Очевидно, это время немного больше, чем время, необходимое, когда агент присутствует, поэтому чистая прибыль каждого агента слабо положительна. Интуитивно понятно, что каждому агенту платят в соответствии с его предельным вкладом в передачу.
Аналогичным образом могут быть решены и другие проблемы с графами, например, минимальное остовное дерево или максимальное соответствие . Аналогичное решение применимо к более общему случаю, когда каждый агент имеет некоторое подмножество ребер. [3]
Другой пример, в котором механизм VCG обеспечивает неоптимальное приближение, см. В разделе « Правдивое планирование заданий» .
Уникальность
Механизм VCG реализует утилитарную функцию социального выбора - функцию, которая максимизирует взвешенную сумму значений (также называемую аффинным максимизатором ). Теорема Робертса доказывает, что, если:
- Функции оценки агентов не ограничены (каждый агент может иметь в качестве функции значения любую функцию из к ), а также -
- Есть как минимум три различных возможных исхода ( и как минимум три разных результата от может случиться),
тогда могут быть реализованы только взвешенные утилитарные функции. [1] : 228, chap.12 Таким образом, при неограниченных оценках функции общественного выбора, реализуемые механизмами VCG, являются единственными функциями, которые могут быть реализованы правдиво.
Более того, ценовые функции механизмов VCG также уникальны в следующем смысле. [1] : 230–231 Если:
- Области оценок агентов представляют собой связанные множества (в частности, агенты могут иметь действительные предпочтения, а не только интегральные предпочтения);
- Есть правдивый механизм , реализующий определенный функция с определенными платежными функциями ;
- Есть еще один правдивый механизм, реализующий то же самое. функция с разными платежными функциями ;
Тогда существуют функции такое, что для всех :
Т.е. ценовые функции двух механизмов отличаются только функцией, не зависящей от оценки агента. (только от оценок других агентов).
Это означает, что механизмы VCG - единственные правдивые механизмы, которые максимизируют утилитарное социальное благосостояние.
Вычислительные проблемы
Механизм VCG должен рассчитать оптимальный результат на основе отчетов агентов (шаг 2 выше). В некоторых случаях этот расчет вычислительно труден. Например, на комбинаторных аукционах вычисление оптимального распределения NP-сложно .
Иногда существуют алгоритмы приближения к задаче оптимизации, но использование такого приближения может сделать механизм недостоверным. [3]
Смотрите также
Рекомендации
- ^ a b c d Вазирани, Виджай В .; Нисан, Ноам ; Roughgarden, Тим ; Тардос, Ева (2007). Алгоритмическая теория игр (PDF) . Кембридж, Великобритания: Издательство Кембриджского университета. ISBN 0-521-87282-0.
- ^ Аврим Блюм (28 февраля 2013 г.). «Алгоритмы, игры и сети - Лекция 14» (PDF) . Проверено 28 декабря 2015 .
- ^ а б в Нисан, Ноам; Ронен, Амир (2001). «Разработка алгоритмических механизмов». Игры и экономическое поведение . 35 (1–2): 166–196. DOI : 10,1006 / game.1999.0790 .