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

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

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

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

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

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

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