Improved Price of Anarchy via Predictions
Improved Price of Anarchy via Predictions
复制标题
通过预测改善无政府状态的价格
DOI：
10.1145/3490486.3538296
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Tan, Xizhi
中科院分区：
文献类型：
--
作者：
Gkatzelis, Vasilis;Kollias, Kostas;Sgouritsa, Alkmini;Tan, Xizhi
算法博弈论的一个中心目标是分析分散式多智能体系统的性能，如通信和信息网络。在没有一个中央规划者来强制执行这些系统如何被利用的情况下，用户可以战略性地与系统交互，旨在最大化他们自己的效用，这可能导致非常低效的结果，从而导致无政府状态的高昂代价。为了缓解这个问题，系统设计者可以使用分散的机制来调节每个资源的使用（例如，使用本地排队协议或调度机制），但是仅具有关于系统状态的有限信息。这些信息限制对这种分散机制可以实现的目标产生了严重影响，因此本文献中的大多数成功案例都不得不做出限制性假设（例如，通过限制网络的结构或成本函数的类型）。在本文中，我们克服了文献中对分散机制施加的一些障碍，通过设计机制来增强对缺失信息的预测。具体而言，受“预测算法”文献的巨大成功的启发，我们设计了具有预测的分散机制，并评估其无政府状态的价格作为预测误差的函数，重点放在两个非常好的研究类游戏：调度游戏和多播网络形成游戏。
A central goal in algorithmic game theory is to analyze the performance of decentralized multiagent systems, like communication and information networks. In the absence of a central planner who can enforce how these systems are utilized, the users can strategically interact with the system, aiming to maximize their own utility, possibly leading to very inefficient outcomes, and thus a high price of anarchy. To alleviate this issue, the system designer can use decentralized mechanisms that regulate the use of each resource (e.g., using local queuing protocols or scheduling mechanisms), but with only limited information regarding the state of the system. These information limitations have a severe impact on what such decentralized mechanisms can achieve, so most of the success stories in this literature have had to make restrictive assumptions (e.g., by either restricting the structure of the networks or the types of cost functions).In this paper, we overcome some of the obstacles that the literature has imposed on decentralized mechanisms, by designing mechanisms that are enhanced with predictions regarding the missing information. Specifically, inspired by the big success of the literature on "algorithms with predictions", we design decentralized mechanisms with predictions and evaluate their price of anarchy as a function of the prediction error, focusing on two very well-studied classes of games: scheduling games and multicast network formation games.
登录
查看更多内容
无向 Shapley 网络设计游戏稳定性代价的 O(log(n)/log(log(n))) 上限
DOI：
10.1016/j.ipl.2009.04.015
发表时间：
2008
期刊：
ArXiv
影响因子：
--
作者：
Jian Li
通讯作者：
Jian Li
影响因子：
6.4
作者：
T. Harks;Philipp von Falkenhausen
通讯作者：
Philipp von Falkenhausen
DOI：
10.1137/1.9781611977073.3
发表时间：
2021-12
期刊：
ArXiv
影响因子：
--
作者：
Y. Azar;Debmalya Panigrahi;Noam Touitou
通讯作者：
Y. Azar;Debmalya Panigrahi;Noam Touitou
加权拥塞博弈中成本分摊的严格界限
DOI：
10.1007/978-3-662-47666-6_50
发表时间：
2015
期刊：
ACM Transactions on Economics and Computation (TEAC)
影响因子：
--
作者：
Martin Gairing;K. Kollias;Grammateia Kotsialou
通讯作者：
Grammateia Kotsialou
资源分配博弈中成本分摊方法的最坏情况效率
影响因子：
2.7
作者：
T. Harks;K. Miller
通讯作者：
K. Miller