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

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

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

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

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