Algorithms for the shapley and myerson values in graph-restricted games
Algorithms for the shapley and myerson values in graph-restricted games
复制标题
图限制游戏中 shapley 和 myerson 值的算法
DOI：
10.5555/2615731.2615766
复制
发表时间：
2014
影响因子：
1.2
通讯作者：
M. Wooldridge
中科院分区：
文献类型：
--
作者：
Oskar Skibski;Tomasz P. Michalak;Talal Rahwan;M. Wooldridge
图限制博弈首先由 Myerson [20] 引入，它对自然发生的场景进行建模，其中联盟内的任何两个代理之间只有在它们之间存在通信通道（路径）时才可能进行协调。针对此类游戏提出的两个基本解决方案概念是沙普利值和迈尔森值。虽然已经提出了一种算法来计算任意图限制游戏中的 Shapley 值，但尚未开发出适用于 Myerson 值的通用算法。本文的目的是开发一种更有效的计算 Shapley 值的算法，并开发一种在图限制游戏中计算 Myerson 值的通用算法。由于任一值的计算都涉及访问游戏底层图的所有连接的诱导子图，因此我们首先开发一种专用于此目的的算法，并表明它比文献中最快的可用算法更快。然后将该算法用作我们构建两个算法的基石。第一个设计用于计算 Shapley 值，并且被证明比现有技术更有效。第二个是第一个计算任意图中的迈尔森值的专用算法。
Graph-restricted games, first introduced by Myerson[20], model naturally-occurring scenarios where coordination between any two agents within a coalition is only possible if there is a communication channel(a path) between them. Two fundamental solution concepts that were proposed for such a game are the Shapley value and the Myerson value. While an algorithm has been proposed to compute the Shapley value in arbitrary graph-restricted games, no such general-purpose algorithm has yet been developed for the Myerson value.Our aim in this paper is to develop a more efficient algorithm for computing the Shapley value, and to develop a general-purpose algorithm for computing the Myerson value, in graph-restricted games. Since the computation of either value involves visiting all connected induced subgraphs of the graph underlying the game, we start by developing an algorithm dedicated for this purpose, and show that it is faster that the fastest available one in the literature. This algorithm is then used as the cornerstone upon which we build two algorithms. The first is designed to compute the Shapley value, and is shown to be more efficient than the state of the art. The second is the first dedicated algorithm to compute the Myerson value in arbitrary graphs.