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

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

Пусть имеется взвешенный граф. Цель заключается в том, чтобы найти кратчайший путь (с учетом весов ребер) между заданными исходной и целевой вершинами. Каждое ребро контролируется эгоистичным субъектом, а вес ребра, <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].

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

Существует множество классов оценок, которые ограничивают возможные оценки некоторым разумным форматом (подробнее см. в [28]). Например, субаддитивные оценки таковы, что для любых двух пакетов <math>S, T \subseteq \Omega, v(S \cup T) \le v(S) + v(T)</math>. Такие классы демонстрируют гораздо лучшие гарантии аппроксимации; например, для субаддитивных оценок известна 2-аппроксимация с полиномиальным временем [16]. Однако ни для одного из этих классов не известен полиномиальный по времени правдивый механизм (рандомизированный или детерминированный) с постоянным коэффициентом аппроксимации.

'''Открытый вопрос № 4''': существуют ли полиномиальные по времени правдивые аппроксимации с постоянным коэффициентом для особых случаев комбинаторных аукционов, которые являются NP-полными?

Разумеется, максимизация доходов комбинаторных аукционах также является важной целью. Эта тема все еще слабо изучена, за некоторыми исключениями. Механизм [7] получает те же гарантии в отношении оптимального дохода. Улучшенные аппроксимации имеются для многотоварных аукционов (в которых все товары одинаковы) с ограниченными по бюджету игроками [12], а также для комбинаторных аукционов с неограниченным предложением с целеустремленными участниками [6].

Идеи этой конструкции были позже использованы в [10] для построения двухсторонних рынков онлайн-аукционов, на которые множество продавцов и покупателей приходят в режиме онлайн.

Общий метод преобразования онлайновых алгоритмов в онлайновые механизмы предложен в [4]. Это делается для однотоварных аукционов и, в более общем плане, для однопараметрических областей. Этот метод конкурентоспособен как для расчета благосостояния, так и для расчета дохода.

Доход, который удается получить с помощью онлайн-аукциона из Теоремы 8, конкурентоспособен только относительно дохода аукциона ВКГ, который может быть далек от оптимального. Параллельное направление работ посвящено аукционам, максимизирующим доход. Для достижения хороших результатов необходимо сделать два предположения: (1) существует неограниченное предложение товаров (вспомним из раздела «Предметная область 2: цифровые товары и максимизация доходов», что F(v) – это оптимальный монопольный доход по фиксированной цене), (2) игроки не могут лгать о времени своего прибытия, а могут – только о своей ценности. Последнее предположение – очень сильное, но, очевидным образом, необходимое. Такие аукционы мы будем называть «ценностно-правдивыми», подчеркивая на отсутствие «временной правдивости».

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

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

'''Определение 3 [8, 23]'''. Функция социального выбора <math>f: V \to A</math> является «слабо монотонной» (W-MON), если для любых <math>i, v_{- i} \in V_{- i}</math> и любых <math>v, v_{-i} \in V_i</math> выполняется следующее условие. Предположим, что <math>f(v_i, v_{-i}) = a</math> и <math>f(v'_i, v_{-i}) = b</math>. Тогда <math>v'_i(b) - v_i(b) \ge v'_i(a) - v_i(a)</math>.

Другими словами, это условие означает следующее. Предположим, что игрок i меняет свое объявление с <math>v_i</math> на <math>v'_i</math>, и это вызывает изменение социального выбора с a на b. Тогда должна иметь место следующая ситуация: стоимость i для b увеличивается при переходе от <math>v_i</math> к <math>v'_i</math> не меньше, чем стоимость i для a.

'''Теорема 10 [35]. Зафиксируем функцию социального выбора <math>f: V \to A</math>, где V – выпуклая, а A – конечная. Тогда существуют цены p такие, что M = (f, p) правдива тогда и только тогда, когда 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>, остается фиксированным), то он должен выиграть и при v0i. Более того, в этом случае цена выигрывающего игрока должна быть установлена на инфимум по всем выигрышным ценностям.

Довольно просто построить алгоритмы, удовлетворяющие условию W-MON для одномерных областей, и для таких областей было получено множество положительных результатов – как в классическом, так и в алгоритмическом дизайне механизмов. Но насколько сложно удовлетворить условие W-MON для многомерных областей? Этот вопрос пока неясен и, похоже, является одной из задач алгоритмического дизайна механизмов. Контраст между одномерностью и многомерностью проявляется во всех предметных областях, рассмотренных выше, и, похоже, отражает некоторую внутреннюю трудность, пока не вполне понятную. Пусть задана функция социального выбора f; она называется ''реализуемой'' (в доминирующих стратегиях), если существуют цены p такие, что M = (f, p) является правдивой. Основной вопрос заключается в том, ''какие формы функций социального выбора являются реализуемыми''.

Как уже было сказано в начале, функция социального выбора, максимизирующая благосостояние, является реализуемой. Эта конкретная функция может быть слегка обобщена при помощи добавления весовых коэффициентов следующим образом: зафиксируйте некоторые неотрицательные вещественные константы <math>\{ w_i \}^n_{i = 1}</math> (не все они равны нулю) и <math>\{ \gamma_a \}_{a \in A}</math> и выберите альтернативу, которая максимизирует ''взвешенное'' социальное благосостояние, т. е. <math>f(v) \in argmax_{a \in A} \; \sum_i w_i v_i(a) + \gamma_a</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] исследовали этот вопрос для комбинаторных аукционов и подобных ограниченных областей и получили частичные ответы. Например:

'''Теорема 12 [23]. Любой правдивый комбинаторный аукцион или многотоварный аукцион между двумя игроками, который всегда должен распределять все имеющиеся товары и который аппроксимирует благосостояние на коэффициент лучше 2, должен быть аффинным максимизатором.'''

Конечно, это далеко не полный ответ. Что произойдет, если игроков будет больше двух? Что будет, если часть предметов можно будет «выбросить»? Эти вопросы, а также более общий и абстрактный вопрос о характеристиках, все еще остаются открытыми.

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

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

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

В работе [31] предлагается понятие «осуществимо доминирующих» стратегий, когда игроки раскрывают возможные ложные действия, которые они рассматривают, и механизм принимает это во внимание. Предполагая, что игроки ограничены в вычислениях, можно показать, что вместо того, чтобы действительно «лгать», игроки предпочтут раскрыть свои истинные типы действий плюс все возможные варианты ложных действий. В таком случае, поскольку механизм получил истинные типы действий игроков, будет гарантирован результат, близкий к оптимальному.

Другое определение пытается передать первоначальные интуитивные соображения, используя классическое теоретико-игровое понятие недоминируемых стратегий:

'''Определение 4 [5]'''. Механизм M является «алгоритмической реализацией c-аппроксимации (в недоминируемых стратегиях)», если существует набор стратегий D, такой, что (1) M получает c-аппроксимацию для любой комбинации стратегий из D за полиномиальное время, и (2) для любой стратегии, не входящей в D, существует стратегия в D, которая слабо доминирует над ней, и этот переход вычислим за полиномиальное время.

Согласно второму условию, разумно предположить, что игрок действительно будет играть, следуя ''некоторой'' стратегии из D; а, согласно первому условию, не имеет значения, какой набор стратегий из D будет выбран на самом деле, поскольку любая из них обеспечит аппроксимацию. Это переносит часть бремени с теоретико-игрового проектирования на алгоритмический дизайн, поскольку теперь гарантия аппроксимации должна обеспечиваться для большего диапазона стратегий. [5] используют это понятие для разработки детерминированного комбинаторного аукциона для многомерных игроков, который достигает гарантии аппроксимации, близкой к оптимальной. Схожим по духу понятием, хотя и более слабым, является понятие «множества Нэша» [25].

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

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

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