4430
правок
Алгоритмический дизайн механизмов: различия между версиями
Материал из WEGA
Алгоритмический дизайн механизмов (посмотреть исходный код)
Версия от 14:44, 9 июля 2023
, 9 июля 2023→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 68: | Строка 68: | ||
Более подробно этот результат описан в статье [[Механизмы для агентов с | Более подробно этот результат описан в статье [[Механизмы для Механизм для однопараметрических агентов с одним покупателем]]. Итоговый вывод состоит в том, что, хотя социальная цель отличается от максимизации благосостояния, все же существует правдивый механизм для ее достижения. Достигается нетривиальная гарантия аппроксимации, даже при дополнительном требовании вычислительной эффективности. Однако эта гарантия не соответствует наилучшей гарантии, возможной без требования правдивости, поскольку для этого случая известна схема аппроксимации с полиномиальным временем выполнения (PTAS). | ||
| Строка 89: | Строка 89: | ||
Чем вызван переход от «в основном возможного» к «в основном невозможному»? Связанные автоматы – это одномерная область (игроки владеют только одним секретным числом), для которой правдивость характеризуется простым условием монотонности, что позволяет использовать достаточно гибкие подходы алгоритмического дизайна. С другой стороны, несвязанные автоматы представляют собой многомерную область, и в алгоритмических условиях, подразумеваемых правдивостью в этом случае, работать сложнее. До сих пор неясно, подразумевают ли эти условия реальные математические невозможности или просто представляют собой более сложные препятствия, которые в принципе могут быть решены. Одной из многомерных областей планирования, возможности для которой известны, является случай | Чем вызван переход от «в основном возможного» к «в основном невозможному»? Связанные автоматы – это одномерная область (игроки владеют только одним секретным числом), для которой правдивость характеризуется простым условием монотонности, что позволяет использовать достаточно гибкие подходы алгоритмического дизайна. С другой стороны, несвязанные автоматы представляют собой многомерную область, и в алгоритмических условиях, подразумеваемых правдивостью в этом случае, работать сложнее. До сих пор неясно, подразумевают ли эти условия реальные математические невозможности или просто представляют собой более сложные препятствия, которые в принципе могут быть решены. Одной из многомерных областей планирования, возможности для которой известны, является случай <math>p_{ij} \in \{ L_j, H_j \}</math>, где «низкие» и «высокие» значения фиксированы и известны. Этот случай обобщает классическую многомерную модель ограниченных машин <math>(p_{ij} \in \{ p_j, \infty \} )</math> и допускает правдивую 3-аппроксимацию [27]. | ||
Предметная область 2: цифровые товары и максимизация доходов | '''Предметная область 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]. В доказательстве используется ситуация, когда вся прибыль поступает от участника торгов с самой высокой ставкой. Поскольку возможности конкуренции между участниками нет, правдивый аукцион не может заставить этого единственного участника раскрыть свое значение. | |||
Предположим, что аукционист обязан продавать все товары по одинаковой цене, как это бывает у многих «реальных» монополистов, и обозначим за F( | |||
