4551
правка
Алгоритмический дизайн механизмов: различия между версиями
Перейти к навигации
Перейти к поиску
м
Алгоритмический дизайн механизмов (посмотреть исходный код)
Версия от 14:25, 11 июля 2023
, 11 июля 2023→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 154: | Строка 154: | ||
(1) Неясно, как именно следует организовать правильное и точное распределение вероятностей с помощью детерминированного компьютера. Ситуация здесь отличается от ситуации в «обычных» алгоритмических условиях, где можно использовать различные методы дерандомизации, поскольку они в общем случае не несут в себе свойства правдивости. | (1) Неясно, как именно следует организовать правильное и точное распределение вероятностей с помощью детерминированного компьютера. Ситуация здесь отличается от ситуации в «обычных» алгоритмических условиях, где можно использовать различные методы дерандомизации, поскольку они в общем случае не несут в себе свойства правдивости. | ||
(2) Даже если естественный источник случайности существует, нельзя улучшить качество фактического | (2) Даже если естественный источник случайности существует, нельзя улучшить качество фактического исхода, повторив вычисления несколько раз (используя закон больших чисел). Подобное повторение разрушит правдивость. Таким образом, именно потому, что теоретико-игровые вопросы рассматриваются параллельно с вычислительными, важность детерминизма возрастает. | ||
| Строка 160: | Строка 160: | ||
Существует множество классов оценок, которые ограничивают возможные оценки некоторым разумным форматом (подробнее см. в [28]). Например, субаддитивные оценки таковы, что для любых двух пакетов <math>S, T \subseteq \Omega, v(S \cup T) \le v(S) + v(T)</math>. Такие классы демонстрируют гораздо лучшие гарантии аппроксимации; например, для субаддитивных оценок известна 2-аппроксимация с полиномиальным временем [16]. Однако ни для одного из этих классов не известен полиномиальный по времени правдивый механизм (рандомизированный или детерминированный) с | Существует множество классов оценок, которые ограничивают возможные оценки некоторым разумным форматом (подробнее см. в [28]). Например, субаддитивные оценки таковы, что для любых двух пакетов <math>S, T \subseteq \Omega, v(S \cup T) \le v(S) + v(T)</math>. Такие классы демонстрируют гораздо лучшие гарантии аппроксимации; например, для субаддитивных оценок известна 2-аппроксимация с полиномиальным временем [16]. Однако ни для одного из этих классов не известен полиномиальный по времени правдивый механизм (рандомизированный или детерминированный) с константным коэффициентом аппроксимации. | ||
'''Открытый вопрос № 4''': существуют ли полиномиальные по времени правдивые аппроксимации с | '''Открытый вопрос № 4''': существуют ли полиномиальные по времени правдивые аппроксимации с константным коэффициентом для особых случаев комбинаторных аукционов, которые являются NP-полными? | ||
Разумеется, максимизация доходов | Разумеется, максимизация доходов также является важной целью в комбинаторных аукционах. Эта тема все еще слабо изучена, за некоторыми исключениями. Механизм [7] получает те же гарантии в отношении оптимального дохода. Улучшенные аппроксимации имеются для многотоварных аукционов (в которых все товары одинаковы) с ограниченными по бюджету игроками [12], а также для комбинаторных аукционов с неограниченным предложением и целеустремленными участниками [6]. | ||