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

Чем вызван переход от «в основном возможного» к «в основном невозможному»? Связанные машины представляют собой одномерную область (игроки владеют только одним секретным числом), для которой правдивость характеризуется простым условием монотонности, что позволяет использовать достаточно гибкие подходы алгоритмического дизайна. В то же время несвязанные машины представляют собой многомерную область, и в алгоритмических условиях, подразумеваемых правдивостью в этом случае, работать сложнее. До сих пор неясно, подразумевают ли эти условия реальные математические невозможности или просто представляют собой более сложные препятствия, которые в принципе могут быть решены. Одной из многомерных областей планирования, возможности для которой известны, является случай <math>p_{ij} \in \{ L_j, H_j \}</math>, где «низкие» и «высокие» значения фиксированы и известны. Этот случай обобщает классическую многомерную модель ограниченных машин <math>(p_{ij} \in \{ p_j, \infty \} )</math> и допускает правдивую 3-аппроксимацию [27].

В данном построении элегантно используются принципы теории обучения. Аукционы с объявленной ценой для этого случая также возможны; в этом случае аддитивные потери возрастают до O(h log log h). В [19] рассматриваются полностью правдивые онлайн-аукционы для максимизации дохода, но авторам удается получить только очень высокие (хотя и фиксированные) коэффициенты конкурентоспособности. Построение полностью правдивых онлайн-аукционов с близким к оптимальному доходом остается открытым вопросом. Еще один интересный открытый вопрос связан с многомерными оценками. Работа [24] остается единственным источником для игроков, которым может требоваться несколько товаров. Однако их конкурентные гарантии довольно высоки, и достижение лучших приближенных гарантий (особенно в отношении дохода) является сложной задачей.