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

Комбинаторные аукционы (КА) представляют собой центральную модель, имеющую теоретическое значение и практическую значимость. Она обобщает многие задачи теории алгоритмов, такие как планирование заданий и сетевая маршрутизация, и проявляется во многих реальных ситуациях. Эта новая модель имеет различные чисто вычислительные аспекты, а кроме того, демонстрирует интересные проблемы теории игр. Хотя каждый аспект важен сам по себе, очевидно, что только их объединение дает приемлемое решение.

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