论文标题
带预测的机理设计
Mechanism Design with Predictions
论文作者
论文摘要
近年来，通过预测改善算法是一个非常活跃的研究主题。本文在此模型中启动了机理设计的系统研究。在许多经过良好研究的机制设计设置中，我们利用不完美的预测来设计机制，如果预测是准确的（一致性），那能性能要比传统机制好得多，同时始终保留最差的案例保证，即使具有非常不精确的预测（鲁棒性）。此外，我们将最大的预测误差称为足以给予良好性能的机制的误差耐受性，并观察到一致性，鲁棒性和误差容忍度之间的固有权衡对于具有预测的机制设计是常见的。
Improving algorithms via predictions is a very active research topic in recent years. This paper initiates the systematic study of mechanism design in this model. In a number of well-studied mechanism design settings, we make use of imperfect predictions to design mechanisms that perform much better than traditional mechanisms if the predictions are accurate (consistency), while always retaining worst-case guarantees even with very imprecise predictions (robustness). Furthermore, we refer to the largest prediction error sufficient to give a good performance as the error tolerance of a mechanism, and observe that an intrinsic tradeoff among consistency, robustness and error tolerance is common for mechanism design with predictions.
