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

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

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

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

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

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

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

''Функция социального выбора'' <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 всегда раскрыть свою истинную оценку, поскольку это максимизирует его полезность. Формально это можно изложить следующим образом:

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

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

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

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

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

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

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

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

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

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

Планирование заданий – это классическая алгоритмическая формулировка задачи: n заданий необходимо распределить между m машинами, при том что задание j требует времени обработки <math>p_{ij}</math> на машине i. В теоретико-игровой формулировке предполагается, что каждая машина i является эгоистичным субъектом, который несет затраты <math>p_{ij}</math> от обработки задания j. Заметим, что платежи в этой формулировке (и в общем случае) могут быть отрицательными, компенсируя такие затраты. Популярной алгоритмической целью является распределение заданий между машинами с целью минимизации «продолжительности работы»: <math>max_i \sum_{j \; is \; assigned \; to \; i} p_{ij}</math> (j назначено i). Это отличается от ориентации на максимизацию благосостояния, которая в данном случае сводится к минимизации <math>\sum_i \sum_{j \; is \; assigned \; to \; i} p_{ij}</math>, что еще раз иллюстрирует проблему различия алгоритмических целей. Таким образом, схема ВКГ здесь не может использоваться, и необходимо разработать новые методы.

Результаты для этой предметной области зависят от конкретных предположений о структуре векторов во время обработки. В случае ''связанных машин'', <math>p_{ij} = p_j / s_i</math> для любого ij, где значения <math>p_j</math> являются общеизвестными, а единственным секретным параметром игрока i является его ''скорость'', <math>s_i</math>.

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

Если число машин фиксировано, в работе [2] приводится такая правдивая схема PTAS.

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

'''Предметная область 2: цифровые товары и максимизация доходов'''

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

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

Предположим, что аукционист обязан продавать все товары по одинаковой цене, как это бывает у многих «реальных» монополистов, и обозначим за <math>F(\vec v)</math> максимальный доход от продажи по фиксированной цене участникам аукциона со стоимостями <math>\vec v = v_1, ..., v_n</math>, ''предполагая, что все стоимости известны''. Упорядочив индексы следующим образом: <math>v_1 \ge v_2 \ge ... \ge v_n</math>, положим <math>F(\vec v) = max_i \; i \cdot v_i</math>. Проблема, конечно, заключается в том, что на самом деле мы ''ничего'' не знаем о стоимостях. Поэтому необходим правдивый аукцион, который бы извлекал значения игроков. Может ли такой аукцион обеспечить прибыль, составляющую постоянную долю от <math>F(\vec v)</math>, при любом <math>\vec v</math> (т. е. в наихудшем случае)? К сожалению, ответ доказуемо отрицательный [17]. В доказательстве используется ситуация, когда вся прибыль поступает от участника торгов с самой высокой ставкой. Поскольку возможности конкуренции между участниками нет, правдивый аукцион не может заставить этого единственного участника раскрыть свое значение.

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

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

Поскольку в общем случае размер оценки экспоненциален относительно n и m, необходимо учитывать проблему представления. Обычно рассматриваются две модели (более подробно см. [11]). В модели ''языков торгов'' ставка игрока представляет его оценку в краткой форме. Для этой модели задача аппроксимации общественного благосостояния в пределах отношения <math>\Omega(m^{1/2 - \epsilon})</math> для любого <math>\epsilon > 0</math> (если разрешены «целеустремленные» ставки; точное определение дано ниже) является NP-полной. В модели ''доступа по запросу'' механизм итеративно опрашивает игроков в процессе вычислений. Для этой модели любой алгоритм с коммуникациями полиномиальной сложности не может получить коэффициент аппроксимации <math>\Omega(m^{1/2 - \epsilon})</math> для любого <math>\epsilon > 0</math>. Эти границы являются строгими, поскольку существует детерминированная pm-аппроксимация с полиномиальной сложностью вычислений и коммуникаций. Таким образом, в рамках общей структуры оценки вычислительного статуса само по себе вполне понятно.

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

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

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

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

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

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

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

Идеи этой конструкции были позже использованы в [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. Несколько статей по ссылкам затрагивают эту тему более подробно, включая статьи «Ценообразование рекламных объявлений» и «Позиционные аукционы».

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