Enumerating Connected Subgraphs and Computing the Myerson and Shapley Values in Graph-Restricted Games

摘要

At the heart of multi-agent systems is the ability to cooperate to improve the performance of individual agents and/or the system as a whole. While a widespread assumption in the literature is that such cooperation is essentially unrestricted, in many realistic settings this assumption does not hold. A highly influential approach for modelling such scenarios are graph-restricted games introduced by Myerson [36]. In this approach, agents are represented by nodes in a graph, edges represent communication channels, and a group can generate an arbitrary value only if there exists a direct or indirect communication channel between every pair of agents within the group. Two fundamental solution-concepts that were proposed for such games are the Myerson value and the Shapley value. While an algorithm has been developed to compute the Shapley value in arbitrary graph-restricted games, no such general-purpose algorithm has been developed for the Myerson value to date. With this in mind, we set out to develop for such games a general-purpose algorithm to compute the Myerson value, and a more efficient algorithm to compute the Shapley value. Since the computation of either value involves enumerating all connected induced subgraphs of the game's underlying graph, we start by developing an algorithm dedicated to this enumeration, and then we show empirically that it is faster than the state of the art in the literature. Finally, we present a sample application of both algorithms, in which we test the Myerson value and the Shapley value as advanced measures of node centrality in networks.