4430
правок
Алгоритмический дизайн механизмов: различия между версиями
Материал из WEGA
Алгоритмический дизайн механизмов (посмотреть исходный код)
Версия от 15:25, 9 июля 2023
, 9 июля 2023→Предметная область 3: комбинаторные аукционы
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 120: | Строка 120: | ||
Поскольку в общем случае размер оценки экспоненциален относительно n и m, необходимо учитывать проблему представления. Обычно рассматриваются две модели (более подробно см. [ ]). В модели языков торгов ставка игрока представляет его оценку в краткой форме. Для этой модели задача аппроксимации общественного благосостояния в пределах отношения | Поскольку в общем случае размер оценки экспоненциален относительно n и m, необходимо учитывать проблему представления. Обычно рассматриваются две модели (более подробно см. [11]). В модели ''языков торгов'' ставка игрока представляет его оценку в краткой форме. Для этой модели задача аппроксимации общественного благосостояния в пределах отношения <math>\Omega(m^{1/2 - \epsilon})</math> для любого <math>\epsilon > 0</math> (если разрешены «целеустремленные» ставки; точное определение дано ниже) является NP-полной. В модели ''доступа по запросу'' механизм итеративно опрашивает игроков в процессе вычислений. Для этой модели любой алгоритм с коммуникациями полиномиальной сложности не может получить коэффициент аппроксимации <math>\Omega(m^{1/2 - \epsilon})</math> для любого <math>\epsilon > 0</math>. Эти границы являются строгими, поскольку существует детерминированная pm-аппроксимация с полиномиальной сложностью вычислений и коммуникаций. Таким образом, в рамках общей структуры оценки вычислительного статуса само по себе вполне понятно. | ||
Основной вопрос стимулирования также вполне понятен: механизм ВКГ обеспечивает правдивость. Поскольку ВКГ необходим точный оптимум, вычисление которого является NP-полной задачей, эти два соображения конфликтуют друг с другом при попытке использовать классические техники. Разработка алгоритмических механизмов направлена на разработку новых техник, позволяющих объединить эти два желаемых аспекта. | Основной вопрос стимулирования также вполне понятен: механизм ВКГ обеспечивает правдивость. Поскольку ВКГ необходим точный оптимум, вычисление которого является NP-полной задачей, эти два соображения конфликтуют друг с другом при попытке использовать классические техники. Разработка алгоритмических механизмов направлена на разработку новых техник, позволяющих объединить эти два желаемых аспекта. | ||
Первый положительный результат для этой интеграционной задачи был получен в работе [29] для особого случая «целеустремленных» участников торгов: каждый участник торгов, i, заинтересован в приобретении конкретного пакета <math>S_i</math> за стоимость <math>v_i</math> (любой пакет, содержащий <math>S_i</math>, стоит <math>v_i</math>, а другие пакеты имеют нулевую стоимость). И <math>v_i</math>, и <math>S_i</math> являются частными для игрока i. | |||
Теорема 5 [29]. Существует правдивый детерминированный комбинаторный аукцион для целеустремленных участников с полиномиальным временем выполнения, позволяющий получить | |||
'''Теорема 5 [29]. Существует правдивый детерминированный комбинаторный аукцион для целеустремленных участников с полиномиальным временем выполнения, позволяющий получить <math> \sqrt{m} </math>-аппроксимацию оптимального общественного благосостояния.''' | |||
| Строка 134: | Строка 135: | ||
Теорема 6 [7]. Существует правдивый детерминированный многотоварный комбинаторный аукцион с полиномиальным временем выполнения для B > | '''Теорема 6 [7]. Существует правдивый детерминированный многотоварный комбинаторный аукцион с полиномиальным временем выполнения для <math>B \ge 3</math> экземпляров каждого товара, позволяющий получить <math>O(B \cdot m^{1 / (B - 2})</math>-аппроксимацию оптимального общественного благосостояния.''' | ||
Этот аукцион справляется с проблемой представления (поскольку предполагаются общие оценки) путем доступа к оценкам через «оракул спроса»: заданные цены за единицу товара { | Этот аукцион справляется с проблемой представления (поскольку предполагаются общие оценки) путем доступа к оценкам через «оракул спроса»: заданные цены за единицу товара <math>\{ p_x \}_{x \in \Omega}</math> определяют пакет S, который максимизирует <math>v_i(S) - \sum_{x \in S} p_x</math>. | ||
| Строка 143: | Строка 144: | ||
Теорема 7 [26]. Существует ожидаемо правдивый рандомизированный многотоварный комбинаторный аукцион с полиномиальным временем выполнения для B > 1 экземпляров каждого товара, позволяющий получить O(m1 /(B+1))-аппроксимацию | Теорема 7 [26]. Существует ожидаемо правдивый рандомизированный многотоварный комбинаторный аукцион с полиномиальным временем выполнения для B > 1 экземпляров каждого товара, позволяющий получить O(m1 /(B+1))-аппроксимацию оптимального общественного благосостояния. | ||
