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

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

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

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

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

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

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

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

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

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