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

Постановка задачи

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

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

Мотивирующий пример: поиск кратчайших путей

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

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

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

Абстрактная формулировка

Структура состоит из множества A альтернатив, или результатов, и n игроков, или агентов. Каждый игрок i имеет оценочную функцию [math]\displaystyle{ v_i: A \to \mathfrak{R} }[/math], которая присваивает ценность каждой возможной альтернативе. Эта оценочная функция принадлежит к области [math]\displaystyle{ V_i }[/math] всех возможных оценочных функций. Положим [math]\displaystyle{ V = V_1 \times \cdots \times V_n }[/math] и [math]\displaystyle{ V_{- i} = \prod_{j \ne i} V_j }[/math]. Заметим, что этот подход обобщает пример с поиском кратчайшего пути, приведенный выше: A – это все возможные s - t путей в данном графе, [math]\displaystyle{ v_e(a) }[/math] для некоторого пути [math]\displaystyle{ a \in A }[/math] равно либо [math]\displaystyle{ w_e }[/math] (если [math]\displaystyle{ e \in a }[/math]), либо нулю.

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

Определение 1 (правдивость). Механизм M является «правдивым» (в доминирующих стратегиях), если для любого игрока i, любого профиля оценок других игроков [math]\displaystyle{ v_{-i} \in V_{-i} }[/math] и любых двух оценок игрока [math]\displaystyle{ iv_i, v'_i \in V_i }[/math], выполняется соотношение

[math]\displaystyle{ v_i(a) - p_i (v_i, v_{-i}) \ge v_i(b) - p_i (v'_i, v_{-i}) }[/math], где [math]\displaystyle{ f(v_i, v_{-i}) = a }[/math] и [math]\displaystyle{ f(v'_i; v_{-i}) = b }[/math].

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

Определение 2 (максимизация общественного благосостояния). Функция социального выбора [math]\displaystyle{ f: V \to A }[/math] максимизирует общественное благосостояние, если [math]\displaystyle{ f(v) \in argmax_{a \in A} \sum_i v_i(a) }[/math] для любого [math]\displaystyle{ v \in V }[/math].

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

Теорема 1 (Викри-Кларка-Гровса, ВКГ). Зафиксируем любое множество альтернатив A и любую область V и предположим, что [math]\displaystyle{ f: V \to A }[/math] максимизирует общественное благосостояние. Тогда существуют цены p, такие, что механизм (f, p) является правдивым.

Этот подход дает «бесплатное» решение задачи поиска кратчайшего пути и многих других алгоритмических проблем. Большим преимуществом схемы ВКГ является ее универсальность: она подходит для любых предметных областей. Недостатком, однако, является то, что метод специализирован под максимизацию общественного благосостояния. Это обстоятельство оказывается ограничивающим, особенно в алгоритмических и вычислительных задачах, по нескольким причинам:

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

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

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

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

Существуют два разных, но тесно связанных направления исследований. Первое представляет собой серию работ, изучающих «цену анархии» заданной системы. Эти работы анализируют существующие системы, пытаясь количественно оценить потерю социальной эффективности из-за эгоистичного характера участников, в то время как подход алгоритмического дизайна механизмов заключается в том, чтобы понять, как следует проектировать новые системы. Подробнее об этом см. статью «Цена анархии». Второе касается алгоритмического исследования различных способов вычисления равновесий. Эти работы привносят вычислительные аспекты в экономику и теорию игр, поскольку задаются вопросом, какие представления о равновесии разумно принять, если требуется вычислительная эффективность; а работы, описанные здесь, привносят теорию игр и экономику в вычислительные науки и теорию алгоритмов, поскольку задаются вопросом, какие алгоритмы разумно разработать, если требуется устойчивость к эгоистичному поведению. Подробнее об этом см., например, статьи Алгоритмы для равновесия Нэша и Равновесие в общем случае.

Основные результаты

Предметная область 1: планирование заданий

Планирование заданий – это классическая алгоритмическая формулировка задачи: n заданий необходимо распределить между m машинами, при том что задание j требует времени обработки pij на машине i. В теоретико-игровой формулировке предполагается, что каждая машина i является эгоистичным субъектом, который несет затраты pij от обработки задания j. Заметим, что платежи в этой формулировке (и в общем случае) могут быть отрицательными, компенсируя такие затраты. Популярной алгоритмической целью является распределение заданий между машинами с целью минимизации «продолжительности работы»: maxi Pj назначается i pij. Это отличается от ориентации на максимизацию благосостояния, которая в данном случае сводится к минимизации Pi Pj назначается pij, что еще раз иллюстрирует проблему различия алгоритмических целей. Таким образом, схема VCG не может использоваться, необходимо разработать новые методы.

Результаты для этой предметной области зависят от конкретных предположений о структуре векторов во время обработки. В случае связанных машин pij = pj/si для любого ij, где значения pj являются общеизвестными, а единственным секретным параметром игрока i является его скорость, si.

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

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

Открытый вопрос № 1: существует ли правдивая схема PTAS для минимизации продолжительности работы на связанных машинах? Если число машин фиксировано, в работе [ ] приводится такая правдивая схема PTAS.

Вышеприведенная картина полностью меняется при переходе к более общему случаю несвязанных машин, где элементы pij могут быть произвольными:

Теорема 3 [13, 30]. Ни один правдивый механизм планирования для несвязанных машин не может аппроксимировать оптимальную продолжительность работы с коэффициентом лучше 1 + p2 (для детерминированных механизмов) и 2 - 1/m (для рандомизированных механизмов).

Заметим, что это утверждение справедливо независимо от вычислительных соображений. В этом случае переход от максимизации благосостояния к минимизации продолжительности работы приводит к сильной невозможности. Что касается возможностей, о них практически нечего сказать. Механизм ВКГ, который минимизирует общие социальные затраты, является m-аппроксимацией оптимальной продолжительности работы [32] – и, по сути, ничего лучшего на настоящее время не известно:

Открытый вопрос № 2: какова наилучшая возможная аппроксимация для правдивой минимизации продолжительности работы на несвязанных машинах?

Чем вызван переход от «в основном возможного» к «в основном невозможному»? Связанные автоматы – это одномерная область (игроки владеют только одним секретным числом), для которой правдивость характеризуется простым условием монотонности, что позволяет использовать достаточно гибкие подходы алгоритмического дизайна. С другой стороны, несвязанные автоматы представляют собой многомерную область, и в алгоритмических условиях, подразумеваемых правдивостью в этом случае, работать сложнее. До сих пор неясно, подразумевают ли эти условия реальные математические невозможности или просто представляют собой более сложные препятствия, которые в принципе могут быть решены. Одной из многомерных областей планирования, возможности для которой известны, является случай pij2 f Lj;Hjg, где «низкие» и «высокие» 's фиксированы и известны. Этот случай обобщает классическую многомерную модель ограниченных машин (pij 2 fpj;1g) и допускает правдивую 3-аппроксимацию [27].

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

1 Эта модель не изучалась в явном виде в классической теории аукционов, но стандартные результаты из нее можно легко адаптировать к данной ситуации.

В этой формулировке задачи каждый покупатель имеет известную частным образом ценность для получения одного экземпляра товара. Максимизация благосостояния просто подразумевает выделение одного товара каждому покупателю; более интересным вопросом является вопрос максимизации дохода. Как аукционист должен построить аукцион, чтобы максимизировать свою прибыль? Стандартные инструменты, используемые при изучении аукционов, максимизирующих доход1 , предлагают просто объявить цену на покупателя, определяемую вероятностным распределением ценности покупателя, и сделать предложение типа «хотите берите, хотите нет». Однако такой механизм требует знания исходного распределения. Алгоритмический дизайн механизмов предлагает альтернативный результат для наихудшего случая, в духе моделей и анализа вычислительных наук.

Предположим, что аукционист обязан продавать все товары по одинаковой цене, как это бывает у многих «реальных» монополистов, и обозначим за F(vE) максимальный доход от продажи по фиксированной цене участникам аукциона со значениями v = v 1... vn, предполагая, что все значения известны. Упорядочив индексы следующим образом v1 > v2 > • • • > vn и положим F(vE) = maxi i ■ vi. Проблема, конечно, заключается в том, что на самом деле мы ничего не знаем о значениях. Поэтому необходим правдивый аукцион, который бы извлекал значения игроков. Может ли такой аукцион обеспечить прибыль, составляющую постоянную долю от F(vE), при любом v (т. е. в наихудшем случае)? К сожалению, ответ доказуемо отрицательный [17]. В доказательстве используется ситуация, когда вся прибыль поступает от участника торгов с самой высокой ставкой. Поскольку возможности конкуренции между участниками нет, правдивый аукцион не может заставить этого единственного участника раскрыть свое значение.

К счастью, существенно помогает небольшое ослабление критериев оптимальности. В частности, обозначим за F(2)(vE) = max;>2 i - vi (т. е. эталоном является аукцион, на котором товар продается не менее чем двум покупателям).

Теорема 4 [17, 20]. Существует правдивый рандомизированный аукцион, который приносит ожидаемый доход не менее F(2)/3:25 даже в наихудшем случае. С другой стороны, ни один правдивый аукцион не может аппроксимировать F(2) с коэффициентом лучше 2,42.

В литературе было рассмотрено несколько интересных форматов непараметрических аукционов с максимизацией дохода. Общим для всех них является случайное разбиение множества покупателей на случайные подмножества, анализ каждого множества по отдельности и применение полученных результатов к другим множествам. В каждом аукционе используется отличный от других анализ двух подмножеств, что дает несколько различающиеся гарантии аппроксимации. В [ ] описан элегантный метод дерандомизации такого типа аукционов, при этом коэффициент аппроксимации становится в 4 раза меньше. Более подробную информацию об этой предметной области можно найти в статье «Конкурентные аукционы».

Предметная область 3: комбинаторные аукционы

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

Комбинаторным аукционом называется многотоварный аукцион, участники которого заинтересованы в приобретении пакетов предметов. Такая структура оценки может представлять взаимозаменяемость предметов, взаимодополняемость предметов или комбинацию того и другого. Если говорить более формально, m предметов {Q) должны быть распределены между n игроками. Игроки оценивают подмножества предметов, а vi(S) обозначает ценность i-го пакета SCi]. Оценки дополнительно обладают следующими свойствами: (i) монотонности, то есть vi(S) < vi(T) для S С T, и (ii) нормализации, то есть vi (;) = 0. В литературе в основном рассматривается цель максимизации общественного благосостояния: требуется найти распределение (S1 ; : : : ; Sn), для которого значение Pi vi №) максимально.

Поскольку в общем случае размер оценки экспоненциален относительно n и m, необходимо учитывать проблему представления. Обычно рассматриваются две модели (более подробно см. [ ]). В модели языков торгов ставка игрока представляет его оценку в краткой форме. Для этой модели задача аппроксимации общественного благосостояния в пределах отношения Q(m1/2~€) для любого e > 0 (если разрешены «целеустремленные» ставки; точное определение дано ниже) является NP-полной. В модели доступа по запросу механизм итеративно опрашивает игроков в процессе вычислений. Для этой модели любой алгоритм с коммуникациями полиномиальной сложности не может получить коэффициент аппроксимации Q{mll2~€) для любого e > 0. Эти границы являются строгими, поскольку существует детерминированная pm-аппроксимация с полиномиальной сложностью вычислений и коммуникаций. Таким образом, в рамках общей структуры оценки вычислительного статуса само по себе вполне понятно.

Основной вопрос стимулирования также вполне понятен: механизм ВКГ обеспечивает правдивость. Поскольку ВКГ необходим точный оптимум, вычисление которого является NP-полной задачей, эти два соображения конфликтуют друг с другом при попытке использовать классические техники. Разработка алгоритмических механизмов направлена на разработку новых техник, позволяющих объединить эти два желаемых аспекта.

Первый положительный результат для этой интеграционной задачи был получен в работе [29] для особого случая «целеустремленных» участников торгов: каждый участник торгов, i, заинтересован в приобретении конкретного пакета Si за стоимость vi (любой пакет, содержащий Si, стоит vi, а другие пакеты имеют нулевую стоимость). И vi, и Si являются частными для игрока i.

Теорема 5 [29]. Существует правдивый детерминированный комбинаторный аукцион для целеустремленных участников с полиномиальным временем выполнения, позволяющий получить pm-аппроксимацию к оптимальному общественному благосостоянию.

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

Теорема 6 [7]. Существует правдивый детерминированный многотоварный комбинаторный аукцион с полиномиальным временем выполнения для B > 3 экземпляров каждого товара, позволяющий получить O(B ■ m1 B~2')-аппроксимацию к оптимальному общественному благосостоянию.

Этот аукцион справляется с проблемой представления (поскольку предполагаются общие оценки) путем доступа к оценкам через «оракул спроса»: заданные цены за единицу товара {px}xeQ> определяют пакет S, который максимизирует vi(S)

У этого типа аукциона есть два основных недостатка, которые стимулируют дальнейшие исследования по этому вопросу. Во-первых, при увеличении B разумно ожидать, что коэффициент аппроксимации будет приближаться к 1 (действительно, существуют алгоритмы с полиномиальным временем выполнения с гарантией такой аппроксимации). Однако здесь коэффициент аппроксимации не уменьшается ниже O(log m) (это значение достигается для B = O(log m)). Во-вторых, этот аукцион не дает решения для исходной формулировки задачи, с B = 1 – и, вообще говоря, для малых B коэффициент аппроксимации довольно высок. Одним из способов решения этих проблем является введение случайности:

Теорема 7 [26]. Существует ожидаемо правдивый рандомизированный многотоварный комбинаторный аукцион с полиномиальным временем выполнения для B > 1 экземпляров каждого товара, позволяющий получить O(m1 /(B+1))-аппроксимацию к оптимальному общественному благосостоянию.

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

Однако это понятие строго слабее детерминистского, поскольку оно неявно подразумевает, что игроков волнует только ожидание их полезности (а не, например, дисперсия). В экономической литературе это называется предположением о «нейтральном отношении к риску». Промежуточным понятием для рандомизированных механизмов является понятие «универсальной правдивости»: механизм правдив при любом фиксированном результате броска монеты. Здесь нейтральное отношение к риску уже не требуется. В [15] приводится универсально правдивый комбинаторный аукцион для В = 1, который дает O(pm)-аппроксимацию.

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

Открытый вопрос № 3: каков наилучший возможный коэффициент аппроксимации, который детерминированные и правдивые комбинаторные аукционы могут получить за полиномиальное время?

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

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

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

Тема комбинаторных аукционов обсуждается также в статье «Многотоварные аукционы.

Предметная область 4: онлайн-аукционы

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

Интеграция онлайновых условий, анализа наихудших случаев и теории аукционов была предложена в работе [24]. Авторы рассмотрели случай, когда игроки приходят по одному, и аукционист должен дать ответ каждому игроку по мере его прихода, не зная будущих ставок. Имеется k одинаковых товаров, и у каждого участника аукциона может иметься собственное значение ценности для каждого возможного количества товара. Предполагается, что эти значения незначительно снижаются, и каждое предельно возможное значение лежит в интервале [v, v]. Частная информация участника торгов включает как его функцию оценки, так и время прибытия, поэтому правдивый аукцион должен стимулировать игроков прибывать вовремя (без опозданий) и раскрывать свои истинные значения ценности. Наиболее интересный результат для этой постановки задачи получен для большого k, так что фактически существует континуум товаров:

Теорема 8 [24]. Существует правдивый онлайн-аукцион, который позволяет одновременно получить аппроксимацию, с поправкой на коэффициент O(log(v/v)), оффлайнового оптимального благосостояния и оффлайнового дохода в ВКГ. Более того, ни один правдивый онлайн-аукцион не может обеспечить лучший коэффициент аппроксимации по любому из этих критериев (по отдельности).

Этот аукцион имеет интересное свойство: он является аукционом «объявленной цены». От каждого участника аукциона не требуется раскрывать свою функцию оценки; напротив, ему дается цена для каждого возможного количества, а затем он просто сообщает желаемое количество товаров по этим ценам.

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

Этот коэффициент аппроксимации может быть значительно улучшен до константной величины, равной 4, если предположить, что (1) в аукционе участвует только один товар и (2) значения ценности игроков являются независимыми и одинаково распределенными случайными величинами из некоторого фиксированного распределения. Никакого априорного знания этого распределения не требуется, поскольку ни механизм, ни игроки не обязаны его использовать. В работе [19] проанализирован этот вопрос и установлена любопытная связь с классом задач о выборе секретаря.

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

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

Теорема 9 [9]. Для любого e > 0 существует ценностно-правдивый онлайн-аукцион для случая неограниченного предложения, с ожидаемым доходом не менее (F(v))/(1 + e) - O(h/e2).

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

Вопросы повышенной сложности

Монотонность

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

Определение 3 [8, 23]. Функция социального выбора f: V ! A является «слабо монотонной» (W-MON), если для любых i, v_, 2 V_,-, и любого v i;/ € Vi выполняется следующее условие. Предположим, что /(v.-.v-i) = a, и/(v;,v_,) = b. Тогда v0i(b) - vi(b) >

Другими словами, это условие означает следующее. Предположим, что игрок i меняет свое объявление с vi на vi0, и это вызывает изменение социального выбора с a на b. Тогда должнм иметь место следующая ситуация: ценность i для b увеличивается при переходе от vi к vi0 не меньше, чем ценность i для a.

Теорема 10 [35]. Зафиксируем функцию социального выбора f: V ! A, где V – выпуклая, а A – конечная. Тогда существуют цены p такие, что M = (f; p) правдива тогда и только тогда, когда f слабо монотонна.

Более того, для слабо монотонной функции f существует явный способ определения соответствующих цен p (подробнее см. [ 18 ]).

Таким образом, разработчик должен стремиться к слабо монотонным алгоритмам, и ему не нужно беспокоиться о фактических ценах. Но насколько это сложно? Для одномерных областей оказывается, что W-MON оставляет разработчику алгоритмов достаточно гибкие возможности. Рассмотрим, например, случай, когда каждая альтернатива имеет значение либо 0 (игрок «проигрывает»), либо некоторое v i 2< (игрок «выигрывает» и получает ценность vi). В таком случае нетрудно показать, что W-MON сводится к следующему условию монотонности: если игрок выигрывает при vi и увеличивает свою ценность до v0i > vi (при этом v_, остается фиксированным), то он должен выиграть и при v0i. Более того, в этом случае цена выигрывающего игрока должна быть установлена на инфимум по всем выигрышным ценностям.

Невозможность правдивого дизайна

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

Как уже было сказано в начале, функция социального выбора, максимизирующая благосостояние, является реализуемой. Эта конкретная функция может быть слегка обобщена при помощи добавления весовых коэффициентов следующим образом: зафиксируйте некоторые неотрицательные вещественные константы fwigni=1 (не все они равны нулю) и {ya}aeA> и выберите альтернативу, которая максимизирует взвешенное социальное благосостояние, т. е. f(v) 2 argmaxa2A Pi wivi(a) + Ya-. Этот класс функций иногда называют «аффинными максимизаторами». Оказывается, что эти функции также реализуемы, с ценами, близкими по духу к алгоритму ВКГ. В контексте вышеупомянутого вопроса о характеристиках выделяется один особенный результат:

Теорема 11 [ ]. Зафиксируем функцию социального выбора f: V ! A, таких, что (i) A конечна, |A| > 3, и f отображается на A, и (ii) Vi = <A для всех i. Тогда f реализуема (в доминирующих стратегиях) тогда и только тогда, когда она является аффинным максимизатором.

Область V, которая удовлетворяет неравенству Vi = <A для всех i, называется «неограниченной областью». Теорема утверждает, что если область неограниченная, выбрано не менее трех альтернатив, а множество A альтернатив конечное, то не может быть реализовано ничего, помимо аффинных максимизаторов.

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

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

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

Альтернативные концепции решения

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

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

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

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

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

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

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

Применение

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

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

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

См. также

• Ценообразование рекламных объявлений
• Конкурентный аукцион
• Аукцион с доказанным присутствием фиктивных участников
• Обобщенный аукцион Викри
• Выбор совместимых стимулов
• Позиционный аукцион
• Правдивая многоадресная рассылка

Литература

Представленные здесь темы подробно изложены в учебнике [33]. Раздел «Постановка задачи» основан на статье [32], в которой также введен термин «алгоритмический дизайн механизмов». Книга [14] охватывает различные аспекты комбинаторных аукционов.

1. Aggarwal, G., Fiat, A., Goldberg, A., Immorlica, N., Sudan, M.: Derandomization of auctions. In: Proc. of the 37th ACM Symposium on Theory of Computing (STOC'05), 2005

2. Andelman, N., Azar, Y., Sorani, M.: Truthful approximation mechanisms for scheduling selfish related machines. In: Proc. of the 22nd International Symposium on Theoretical Aspects of Computer Science (STACS), 2005, pp. 69-82

3. Archer, A., Tardos, Ё.: Truthful mechanisms for one-parameter agents. In: Proc. 42nd Annual Symposium on Foundations of Computer Science (FOCS), 2001, pp.482-491

4. Awerbuch, B., Azar, Y., Meyerson, A.: Reducing truth-telling online mechanisms to online optimization. In: Proc. of the 35th ACM Symposium on Theory of Computing (STOC'03), 2003

5. Babaioff, M., Lavi, R., Pavlov, E.: Single-value combinatorial auctions and implementation in undominated strategies. In: Proc. of the 17th Symposium on Discrete Algorithms (SODA), 2006

6. Balcan, M., Blum, A., Hartline, J., Mansour, Y.: Mechanism design via machine learning. In: Proc. of the 46th Annual Symposium on Foundations of Computer Science (FOCS'05), 2005

7. Bartal, Y., Gonen, R., Nisan, N.: Incentive compatible multi-unit combinatorial auctions. In: Proc. of the 9th Conference on Theoretical Aspects of Rationality and Knowledge (TARK'03), 2003

8. Bikhchandani, S., Chatterjee, S., Lavi, R., Mu'alem, A., Nisan, N., Sen, A.: Weak monotonicity characterizes deterministic dominant-strategy implementation. Econometrica 74, 1109-1132 (2006)

9. Blum, A., Hartline, J.: Near-optimal online auctions. In: Proc. of the 16th Symposium on Discrete Algorithms (SODA), 2005

10. Blum, A., Sandholm, T., Zinkevich, M.: Online algorithms for market clearing. J. ACM 53(5), 845-879 (2006)

11. Blumrosen, L., Nisan, N.: On the computational power of iterative auctions. In: Proc. of the 7th ACM Conference on Electronic Commerce (EC'05), 2005

12. Borgs, C., Chayes, J., Immorlica, N., Mahdian, M., Saberi, A.: Multi-unit auctions with budget-constrained bidders. In: Proc. of the 7th ACM Conference on Electronic Commerce (EC'05), 2005

13. Christodoulou, G., Koutsoupias, E., Vidali, A.: A lower bound for scheduling mechanisms. In: Proc. 18th Symposium on Discrete Algorithms (SODA), 2007

14. Cramton, P., Shoham, Y., Steinberg, R.:Combinatorial Auctions. MIT Press (2005)

15. Dobzinski, S., Nisan, N., Schapira, M.: Truthful randomized mechanisms for combinatorial auctions. In: Proc. of the 38th ACM Symposium on Theory of Computing (STOC'06), 2006

16. Feige, U.: On maximizing welfare when utility functions are subadditive. In: Proc. of the 38th ACM Symposium on Theory of Computing (STOC'06), 2006

17. Goldberg, A., Hartline, J., Karlin, A., Saks, M., Wright, A.: Competitive auctions. Games Econ. Behav. 55(2), 242-269 (2006)

18. Gui, H., Muller, R., Vohra, R.V.: Characterizing dominant strategy mechanisms with multi-dimensional types (2004).

19. Hajiaghayi, M., Kleinberg, R., Parkes, D.: Adaptive limited-supply online auctions. In: Proc. of the 6th ACM Conference on Electronic Commerce (EC'04), 2004

20. Hartline, J., McGrew, R.: From optimal limited to unlimited supply auctions. In: Proc. of the 7th ACM Conference on Electronic Commerce (EC'05), 2005

21. Kothari, A., Parkes, D., Suri, S.: Approximately-strategyproof and tractable multi-unit auctions. Decis. Support Syst. 39,105-121 (2005)

22. Kovacs, A.: Fast monotone 3-approximation algorithm for scheduling related machines. In: Proc. 13th Annual European Symposium on Algorithms (ESA), 2005, pp. 616-627

23. Lavi, R., Mu'alem, A., Nisan, N.: Towards a characterization of truthful combinatorial auctions. In: Proc. of the 44rd Annual Symposium on Foundations of Computer Science (FOCS'03), 2003

24. Lavi, R., Nisan, N.: Competitive analysis of incentive compatible on-line auctions. Theor. Comput. Sci. 310,159-180 (2004)

25. Lavi, R., Nisan, N.: Online ascending auctions for gradually expiring items. In: Proc. of the 16th Symposium on Discrete Algorithms (SODA), 2005

26. Lavi, R., Swamy, C.: Truthful and near-optimal mechanism design via linear programming. In: Proc. 46th Annual Symposium on Foundations of Computer Science (FOCS), 2005, pp. 595-604

27. Lavi, R., Swamy, C.: Truthful mechanism design for multi-dimensional scheduling via cycle monotonicity (2007).

28. Lehmann, B., Lehmann, D., Nisan, N.: Combinatorial auctions with decreasing marginal utilities. Games Econom. Behav. 55(2), 270-296 (2006)

29. Lehmann, D., O'Callaghan, L., Shoham, Y.: Truth revelation in approximately efficient combinatorial auctions. J. ACM 49(5), 577-602 (2002)

30. Mu'alem, A., Schapira, M.: Setting lower bounds on truthful ness. In: Proc. 18th Symposium on Discrete Algorithms (SODA), 2007

31. Nisan, N., Ronen, A.: Computationally feasible vcg mechanisms. In: Proc. of the 2nd ACM Conference on Electronic Commerce (EC'00), 2000

32. Nisan, N., Ronen, A.: Algorithmic mechanism design. Games Econom. Behav. 35,166-196 (2001)

33. Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V.: Algorithmic Game Theory. Cambridge University Press (2007). (expected to appear)

34. Roberts, K.: The characterization of implementable choice rules. In: Laffont, J.J. (ed.) Aggregation and Revelation of Preferences, pp. 321-349. North-Holland (1979)

35. Saks, M., Yu, L.: Weak monotonicity suffices for truthfulness on convex domains. In: Proc. 6th ACM Conference on Electronic Commerce (ACM-EC), 2005, pp. 286-293