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

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

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