TY - GEN

T1 - Algorithms for the shapley and myerson values in graph-restricted games

AU - Skibski, Oskar

AU - Michalak, Tomasz P.

AU - Rahwan, Talal

AU - Wooldridge, Michael

N1 - Publisher Copyright:
Copyright © 2014, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved.

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

KW - Enumerating induced connected subgraphs

KW - Myerson value

KW - Shapley value

KW - Terrorist networks

UR - http://www.scopus.com/inward/record.url?scp=84911404011&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84911404011&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84911404011

T3 - 13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014

SP - 197

EP - 204

BT - 13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014

PB - International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)

T2 - 13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014

Y2 - 5 May 2014 through 9 May 2014

ER -