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

В эпоху Интернета, когда компьютеры действуют и взаимодействуют от имени эгоистичных субъектов, связь вышеописанной концепции с алгоритмическим дизайном напрашивается сама собой: предположим, что входные данные для алгоритма хранятся у эгоистичных агентов, которые стремятся максимизировать собственную полезность. Как спроектировать алгоритм таким образом, чтобы агенты решили, что сотрудничество будет в их интересах, и в итоге был получен результат (исход), близкий к оптимальному? Этот подход отличается от классических моделей распределенных вычислений, где агенты либо «хорошие» (то есть послушные), либо «плохие» (то есть неисправные или злонамеренные, в зависимости от контекста). Здесь подобное разделение невозможно. Просто предполагается, что все агенты стремятся достичь максимума полезности. Чтобы проиллюстрировать это, приведем

Пусть имеется взвешенный граф. Цель заключается в том, чтобы найти кратчайший путь (с учетом весов ребер) между заданными исходной и целевой вершинами. Каждое ребро контролируется эгоистичным субъектом, а вес ребра, <math>w_e</math>, представляет собой частную информацию. Если ребро выбрано алгоритмом для включения в кратчайший путь, оно понесет затраты, равные его весу со знаком минус (затраты на коммуникацию). Платежи ребрам разрешены, и общая полезность ребра, входящего в кратчайший путь и получающего платеж <math>p_e</math>, предполагается равной <math>u_e = p_e - w_e</math>. Обратите внимание, что ''кратчайший путь находится с учетом истинных весов агентов, хотя разработчику они не известны''.

Хотя этот пример написан на алгоритмическом языке, на самом деле это задача о дизайне механизмов, а решение, ставшее классическим, было предложено в 70-х годах прошлого века. Далее изложение будет организовано следующим образом: вначале дается абстрактная формулировка для таких задач, описывается классическое решение из области экономики, обсуждаются его преимущества и недостатки для алгоритмических целей. Затем в следующем разделе описываются новые результаты, которые дает алгоритмический дизайн механизмов.

''Функция социального выбора'' <math>f: V \to A</math> назначает социально желательную альтернативу любому заданному профилю стоимостей игроков. Это служит параллелью понятию алгоритма. ''Механизм'' представляет собой кортеж <math>M = (f, p_1, ..., p_n)</math> где f – функция социального выбора, а <math>p_i: V \to \mathfrak{R}</math> (для i = 1, ..., n) - цена, взимаемая с игрока i. Интерпретация заключается в том, что специалист по социальному планированию просит игроков раскрыть свои истинные оценки, выбирает альтернативу в соответствии с функцией f, как если бы игроки действительно действовали правдиво, и, кроме того, вознаграждает и наказывает игроков ценами. Эти цены должны порождать «правдивость» в следующем сильном смысле: независимо от того, что заявляют другие игроки, в интересах игрока i всегда раскрыть свою истинную оценку, поскольку это максимизирует его полезность. Формально это можно изложить следующим образом:

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

Для разрешения любой из этих трудностей требуется разработка механизма, отличного от ВКГ. Какие инструменты анализа следует использовать для этой цели? В экономике и классических подходах к дизайну механизмов стандартом является анализ для среднего случая, который опирается на знание исходного распределения. С другой стороны, вычислительные науки обычно предпочитают избегать сильных предположений о распределении и использовать анализ для наихудшего случая. Это различие является еще одной причиной уникальности ответов, которые дает алгоритмический дизайн механизмов. Далее описываются некоторые новые результаты, появившиеся в результате интеграции вычислительных наук и экономики. Многие другие направления исследований, использующие инструменты алгоритмического дизайна механизмов, описаны в следующих статьях: [[Ценообразование рекламных объявлений]], [[Конкурентные аукционы]], [[Аукционы с доказанным присутствием фиктивных участников]], [[Обобщенный аукцион Викри]], [[Ранжирование совместимых стимулов]], [[Механизм для однопараметрических агентов с одним покупателем/продавцом]], [[Многотоварные аукционы]], [[Позиционные аукционы]], [[Правдивая многоадресная рассылка]].

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

Чем вызван переход от «в основном возможного» к «в основном невозможному»? Связанные машины представляют собой одномерную область (игроки владеют только одним секретным числом), для которой правдивость характеризуется простым условием монотонности, что позволяет использовать достаточно гибкие подходы алгоритмического дизайна. В то же время несвязанные машины представляют собой многомерную область, и в алгоритмических условиях, подразумеваемых правдивостью в этом случае, работать сложнее. До сих пор неясно, подразумевают ли эти условия реальные математические невозможности или просто представляют собой более сложные препятствия, которые в принципе могут быть решены. Одной из многомерных областей планирования, возможности для которой известны, является случай <math>p_{ij} \in \{ L_j, H_j \}</math>, где «низкие» и «высокие» значения фиксированы и известны. Этот случай обобщает классическую многомерную модель ограниченных машин <math>(p_{ij} \in \{ p_j, \infty \} )</math> и допускает правдивую 3-аппроксимацию [27].

В данном построении элегантно используются принципы теории обучения. Аукционы с объявленной ценой для этого случая также возможны; в этом случае аддитивные потери возрастают до O(h log log h). В [19] рассматриваются полностью правдивые онлайн-аукционы для максимизации дохода, но авторам удается получить только очень высокие (хотя и фиксированные) коэффициенты конкурентоспособности. Построение полностью правдивых онлайн-аукционов с близким к оптимальному доходом остается открытым вопросом. Еще один интересный открытый вопрос связан с многомерными оценками. Работа [24] остается единственным источником для игроков, которым может требоваться несколько товаров. Однако их конкурентные гарантии довольно высоки, и достижение лучших приближенных гарантий (особенно в отношении дохода) является сложной задачей.

Как выглядит общий подход к разработке правдивого механизма? Самый простой способ – проверить, существуют ли для заданной функции социального выбора 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].

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

Аукционы рекламных объявлений – еще одно новое и быстро развивающееся направление применения теории аукционов в целом и новых алгоритмических аукционов в частности. Эти аукционы определяют рекламные объявления, размещаемые поисковыми системами рядом с результатами поиска, которые они показывают после того, как пользователь вводит ключевые слова для поиска. Заинтересованные компании конкурируют за право разместить свою рекламу на странице результатов по каждому ключевому слову, и это оказывается основным источником дохода для таких компаний, как Google. Несколько статей по ссылкам затрагивают эту тему более подробно, включая статьи «Ценообразование рекламных объявлений» и «Позиционные аукционы».

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