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

Oskar Skibski, Tomasz P. Michalak, Talal Rahwan, Michael Wooldridge

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publication13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014
PublisherInternational Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Pages197-204
Number of pages8
ISBN (Electronic)9781634391313
StatePublished - 2014
Event13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014 - Paris, France
Duration: May 5 2014May 9 2014

Publication series

Name13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014
Volume1

Other

Other13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014
CountryFrance
CityParis
Period5/5/145/9/14

Keywords

  • Enumerating induced connected subgraphs
  • Myerson value
  • Shapley value
  • Terrorist networks

ASJC Scopus subject areas

  • Artificial Intelligence

Cite this

Skibski, O., Michalak, T. P., Rahwan, T., & Wooldridge, M. (2014). Algorithms for the shapley and myerson values in graph-restricted games. In 13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014 (pp. 197-204). (13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014; Vol. 1). International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).