Алгоритмический дизайн механизмов: различия между версиями

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

Более подробно этот результат описан в статье [[Механизм для однопараметрических агентов с одним покупателем]]. Итоговый вывод состоит в том, что, хотя социальная цель отличается от максимизации благосостояния, все же существует правдивый механизм для ее достижения. Нетривиальная гарантия аппроксимации достигается даже при дополнительном требовании вычислительной эффективности. Однако эта гарантия не соответствует наилучшей гарантии, возможной без требования правдивости, поскольку для этого случая известна аппроксимационная схема с полиномиальным временем выполнения (PTAS).

Как выглядит общий подход к разработке правдивого механизма? Самый простой способ – проверить, существуют ли для заданной функции социального выбора f правдивые цены. Если нет, то следует попытаться «исправить» f. Однако оказывается, что существует более структурированный способ – ''алгоритмическое'' условие, из которого будет следовать ''существование'' правдивых цен. Подобное условие возвращает разработчика на знакомую территорию алгоритмического дизайна. К счастью, такое условие существует, и лучше всего оно излагается в абстрактной постановке задачи социального выбора, описанного в разделе «Постановка задачи»:

Таким образом, разработчик должен стремиться к слабо монотонным алгоритмам, и ему не нужно беспокоиться о фактических ценах. Но насколько это сложно? Для одномерных областей оказывается, что условие W-MON оставляет разработчику алгоритмов достаточно гибкие возможности. Рассмотрим, например, случай, когда каждая альтернатива имеет либо стоимость 0 (игрок «проигрывает»), либо некоторое значение <math>v_i \in \mathfrak{R}</math> (игрок «выигрывает» и получает стоимость <math>v_i</math>). В таком случае нетрудно показать, что W-MON сводится к следующему условию монотонности: если игрок выигрывает при <math>v_i</math> и увеличивает свою стоимость до <math>v'_i > v_i</math> (при этом значение <math>v_{-i}</math> остается фиксированным), то он должен выиграть и при <math>v'_i</math>. Более того, в этом случае цена выигрывающего игрока должна быть установлена на инфимум по всем выигрышным стоимостям.

'''Теорема 11 [34]. Зафиксируем функцию социального выбора <math>f: V \to A</math>, такую, что (1) A конечна, <math>|A| \ge 3</math>, f отображается на A, и (2) <math>V_i = \mathfrak{R}^A</math> для всех i. Тогда функция f реализуема (в доминирующих стратегиях) тогда и только тогда, когда она является аффинным максимизатором.'''

Область V, которая удовлетворяет равенству <math>V_i = \mathfrak{R}^A</math> для всех i, называется ''неограниченной областью''. Теорема утверждает, что если область неограниченная, выбрано не менее трех альтернатив, а множество альтернатив A конечное, то не может быть реализовано ничего, помимо аффинных максимизаторов.

Однако предположение о том, что область является неограниченной, оказывается очень ограничивающим. Все приведенные выше примеры областей имеют некоторую базовую комбинаторную структуру и, следовательно, в той или иной степени ограничены. И, как обсуждалось выше, для многих ограниченных областей теорема попросту неверна. Где же пролегает граница возможного и невозможного? Как уже говорилось выше, это нерешенная проблема. Лави, Муалем и Нисан [23] исследовали этот вопрос для комбинаторных аукционов и подобных ограниченных областей и получили частичные ответы. Например:

В свете выводов, сделанных в предыдущем разделе, естественной идеей будет пересмотр используемой ''концепции решения''. Правдивость опирается на сильную концепцию доминирующих стратегий: для каждого игрока существует уникальная стратегия, которая максимизирует его полезность независимо от того, что делают другие игроки. Это очень сильная концепция, но она очень хорошо подходит для способа мышления вычислительных наук, опирающихся на наихудший случай. Какие еще концепции решения могут быть использованы? Как упомянуто выше, могут оказаться полезными рандомизация и ожидаемая правдивость. Родственной концепцией, опять же связанной с рандомизированными механизмами, является правдивость с высокой вероятностью. Другим направлением является рассмотрение механизмов, в которых игроки не могут ''слишком сильно'' улучшить свою полезность за счет отклонения от стратегии правдивости [21].

Одним из популярных примеров комбинаторного аукциона «в реальной жизни» является аукцион частот, который проводит правительство США для продажи лицензий на использование частот. Типичные предложения отражают стоимость разных диапазонов частот для удовлетворения различных географических и физических потребностей, где разные диапазоны могут дополнять или заменять друг друга. Правительство США вкладывает усилия в исследования, которые позволили бы определить наилучший формат такого аукциона, активно используя теорию аукционов. Любопытно, что законодательство США предписывает властям распределять эти диапазоны таким образом, чтобы максимизировать ''социальное благосостояние'', тем самым обеспечивая хороший пример полезности цели.