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

== '''Открытый вопрос № 3''': каков наилучший возможный коэффициент аппроксимации, который детерминированные и правдивые комбинаторные аукционы могут получить за полиномиальное время? ==

Как выглядит общий подход к разработке правдивого механизма? Самый простой способ – проверить, существуют ли для данной функции социального выбора f правдивые цены. Если нет, то следует попытаться «исправить» f. Однако оказывается, что существует более структурированный способ – алгоритмическое условие, которое будет подразумевать существование правдивых цен. Такое условие возвращает разработчика на знакомую территорию алгоритмического дизайна. К счастью, такое условие существует, и лучше всего оно излагается в абстрактной постановке задачи социального выбора, описанного в разделе «Постановка задачи».