Learning-Augmented Mechanism Design: Leveraging Predictions for Facility Location
Learning-Augmented Mechanism Design: Leveraging Predictions for Facility Location
复制标题
学习增强机制设计：利用设施位置预测
DOI：
10.1145/3490486.3538306
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Tan, Xizhi
中科院分区：
文献类型：
--
作者：
Agrawal, Priyank;Balkanski, Eric;Gkatzelis, Vasilis;Ou, Tingting;Tan, Xizhi
在这项工作中，我们介绍了一种替代模型的设计和分析的strategyproof机制，这是出于最近激增的工作在“学习增强算法”。为了补充计算机科学中基于最坏情况实例分析算法性能的传统方法，这一工作重点是设计和分析通过机器学习预测最优解而增强的算法。算法可以使用预测作为指导来告知他们的决策，目标是在这些预测准确时实现更强的性能保证（一致性），同时保持接近最佳的最坏情况保证，即使这些预测非常不准确（鲁棒性）。到目前为止，这些结果仅限于算法，但在这项工作中，我们认为，这个框架的另一个肥沃的土壤是在机制design.We发起的strategyproof机制的设计和分析，增强与参与代理的私人信息的预测。为了展示这种方法的重要好处，我们重新审视了在二维欧氏空间中与战略代理的设施选址的规范问题。我们研究了平等主义和功利主义的社会成本函数，我们提出了新的strategyproof机制，利用预测来保证一致性和鲁棒性保证之间的最佳权衡。这为设计人员提供了一个机制选项菜单，可供选择，具体取决于她对预测准确性的信心。此外，我们还证明了参数化的近似结果作为预测误差的函数，表明我们的机制即使在预测不完全准确的情况下也能很好地执行。
In this work we introduce an alternative model for the design and analysis of strategyproof mechanisms that is motivated by the recent surge of work in "learning-augmented algorithms". Aiming to complement the traditional approach in computer science, which analyzes the performance of algorithms based on worst-case instances, this line of work has focused on the design and analysis of algorithms that are enhanced with machine-learned predictions regarding the optimal solution. The algorithms can use the predictions as a guide to inform their decisions, and the goal is to achieve much stronger performance guarantees when these predictions are accurate (consistency), while also maintaining near-optimal worst-case guarantees, even if these predictions are very inaccurate (robustness). So far, these results have been limited to algorithms, but in this work we argue that another fertile ground for this framework is in mechanism design.We initiate the design and analysis of strategyproof mechanisms that are augmented with predictions regarding the private information of the participating agents. To exhibit the important benefits of this approach, we revisit the canonical problem of facility location with strategic agents in the two-dimensional Euclidean space. We study both the egalitarian and utilitarian social cost functions, and we propose new strategyproof mechanisms that leverage predictions to guarantee an optimal trade-off between consistency and robustness guarantees. This provides the designer with a menu of mechanism options to choose from, depending on her confidence regarding the prediction accuracy. Furthermore, we also prove parameterized approximation results as a function of the prediction error, showing that our mechanisms perform well even when the predictions are not fully accurate.
登录
查看更多内容
DOI：
10.1145/3465456.3467623
发表时间：
2020-11
期刊：
Proceedings of the 22nd ACM Conference on Economics and Computation
影响因子：
--
作者：
Paul Dütting;Silvio Lattanzi;R. Leme;Sergei Vassilvitskii
通讯作者：
Paul Dütting;Silvio Lattanzi;R. Leme;Sergei Vassilvitskii
DOI：
10.1137/1.9781611977073.3
发表时间：
2021-12
期刊：
ArXiv
影响因子：
--
作者：
Y. Azar;Debmalya Panigrahi;Noam Touitou
通讯作者：
Y. Azar;Debmalya Panigrahi;Noam Touitou
影响因子：
22.7
作者：
M. Mitzenmacher;Sergei Vassilvitskii
通讯作者：
M. Mitzenmacher;Sergei Vassilvitskii
带有频率预测的在线背包
DOI：
--
发表时间：
2021
期刊：
Advances in neural information processing systems
影响因子：
--
作者：
Im, Sungjin;Kumar, Ravi;Montazer Qaem, Mahshid;Purohit, Manish
通讯作者：
Purohit, Manish
DOI：
10.1016/j.disopt.2023.100778
发表时间：
2020-06
期刊：
ArXiv
影响因子：
--
作者：
A. Antoniadis;Themis Gouleakis;P. Kleer;Pavel Kolev
通讯作者：
A. Antoniadis;Themis Gouleakis;P. Kleer;Pavel Kolev