Get Started

Skip the introduction and go directly to the code examples.

A Brief Introduction to Cooperative Game Theory

A solution concept in cooperative game theory is a method for how the payoff of the game can be allocated among the players. While the popular solution concept of the Shapley values assumes that all players can cooperate, the Myerson values restrict player cooperation. Here, the cooperation structure is modeled by a graph, where links between nodes indicate the ability to cooperate. A game itself is defined by a the coalition function, which is best explained by an example game.

The Gloves Game

In the gloves game, players have either a right or a left glove. A pair of gloves is worth $1$ while a single glove is worth $0$. For our example, we’ll look at three players, one with a left glove and two with a right glove (Figure 1a).

**Figure 1: a)** The gloves game with three players. In this example player $1$ has a right glove and players $2$ and $3$ have left gloves each. b) All coalitions that generate value.

So there are three coalitions with a payoff of $1$ (Figure 1b), all other coalitions are $0$. The coalition function $v$ can be defined as:

\[\begin{split}v_{L,R}\,(S) = \begin{cases} 1 & \text{if $S \in \{\{1,2\},\{1,3\},\{1,2,3\}\}$;} \\ 0 & \text{otherwise.} \end{cases}\end{split}\]

There are $2^N = 2^3 = 8$ possible coalitions $S$ for our example:

\[\begin{split}\begin{array}{ll} \{\emptyset\} & \{1,2\}\\ \{1\} & \{1,3\}\\ \{2\} & \{2,3 \}\\ \{3\} & \{1,2,3 \}\\ \end{array}\end{split}\]

The Shapley Value

The Shapley value for a single player can then be calculated using the following formula:

\[\text{Sh}_i\,({v}) = \frac{1}{|N|!}\; \sum_R \big({v}\,(P_i^R \cup \{i\}) - {v}(P_i^R)\big)\]

Here, $P_i^R \cup \{i\}$ denotes the set of players in the order $R$ including player $i$. So for every possible coalition in every possible order, we look at the contribution that the player adds. This is called the players marginal contribution. Note that the formula can be simplified to go from factorial complexity to exponetial complexity (see Documentation).

Using the formula, we can calculate the Shapley value for player $1$:

\[\begin{split}\begin{align*} \text{Sh}_1\,(v) &= \frac{1}{3!}\,\Big((v(\{1\}) - v(\emptyset)) & \overbrace{(1,2,3)}^R\\ &\quad+(v(\{1\}) - v(\emptyset)) & (1,3,2)\\ &\quad+(v(\{2,1\}) - v(\{2\})) & (2,1,3)\\ &\quad+(v(\{2,3,1\}) - v(\{2,3\})) & (2,3,1)\\ &\quad+(v(\{3,1\}) - v(\{3\})) & (3,1,2)\\ &\quad+(v(\{3,2,1\}) - v(\{3,2\}))\Big) & (3,2,1)\\ &=\frac{1}{3!}\,(0+0+1+1+1+1) \\ &=\frac{2}{3} \end{align*}\end{split}\]

In the order $(2,3,1)$ the players $2$ and $3$ have a right glove each, so they can generate a value of $v(\{2,3\}) = 0$. Together with player $1$ they can form a pair of gloves and thus generate a value of $v(\{2,3,1\} = 1$, so the marginal contribution player $1$ makes for this ordering is $1$.

The Shapley value for players $2$ and $3$ is $\text{Sh}_2\,(v) = \text{Sh}_3\,(v) = \frac{1}{6}$. This aligns with the intuitive expectation of player $1$ contributing more because they bring the only left glove. Additionally, players $2$ and $3$ bring the same glove and can otherwise not be distinguished from each other, so they contribute equally to the overall worth.

The Myerson Value

Myerson introduced the idea of regulate the players ability to cooperate by introducing a graph structure (Figure 2).

gloves game with three players and cooperation structure — **Figure 2:** A possible cooperation structure for the gloves game.

The player coalitions can only cooperate if they are linked in the graph $G$. The Myerson value is then the Shapley value of the graph restricted game:

\[\text{My}_i(v, \mathcal{G}) = \text{Sh}_i(v/\mathcal{G})\]

For our example we calculate the Myerson values as follows (differences to the Shapley values highlighted in bold):

\[\begin{split}\begin{align*} \text{My}_1\,(v, \mathcal{G}) &= \frac{1}{3!}\,\Big((v(\{1\}) - v(\emptyset)) & \overbrace{(1,2,3)}^R\\ &\quad+(v(\{1\}) - v(\emptyset)) & (1,3,2)\\ &\quad+(v(\{2,1\}) - v(\{2\})) & (2,1,3)\\ &\quad+(v(\{2,3,1\}) - v(\{2,3\})) & (2,3,1)\\ &\quad+(\boldsymbol{[v(\{3\})+v(\{1\})]} - v(\{3\})) & (3,1,2)\\ &\quad+(v(\{3,2,1\}) - v(\{3,2\}))\Big) & (3,2,1)\\ &=\frac{1}{3!}\,(0+0+1+1+\boldsymbol{0}+1) \\ &=\boldsymbol{\frac{1}{2}} \end{align*}\end{split}\]

For players $2$ and $3$ this results in $\text{My}_2\,(v) = \frac{1}{2}$ and $\text{My}_3\,(v) = 0$, respectively. With the cooperation structure enforced, player $2$ profits from his central role, linking the other two players. Now player $3$ can only contribute to the overall gain when player $2$ is present, who has the same glove, thus player $3$ does not contribute anything. In a complete graph the Myerson value is equivalent to the Shapley value.

Code Examples

Calculate the Myerson Values

Calculation of the three player example for the gloves game (vide supra).

import networkx as nx
from myerson import MyersonCalculator, MyersonSampler

# define L--R--R graph
graph = nx.Graph()
graph.add_edges_from([(1, 2), (2, 3)])
graph.add_node(1, glove="left")
graph.add_node(2, glove="right")
graph.add_node(3, glove="right")

# define coalition function
def gloves_game_coalition_function(coalition: tuple,
                                   nx_graph: nx.classes.graph.Graph) -> float:
    # the graph structure should have no influence on the coalition function
    # we only inclued it to get more information from the players
    if len(coalition) <= 1:
        return 0.
    gloves = nx.get_node_attributes(nx_graph, 'glove')
    r = sum([1 for k, v in gloves.items() if (v=="right" and k in coalition)])
    l = sum([1 for k, v in gloves.items() if (v=="left" and k in coalition)])
    return float(min(r, l))

# calculate the exact Myerson values
myerson_calculator = MyersonCalculator(graph=graph,
    coalition_function=gloves_game_coalition_function)
my_values = myerson_calculator.calculate_all_myerson_values()

# calculate the Myerson values by sampling
myerson_sampler = MyersonSampler(graph=graph,
    coalition_function=self.gloves_game_coalition_function,
    number_of_samples=1000,
    seed=42,
    disable_tqdm=True)
my_values_sampled = myerson_sampler.sample_all_myerson_values()

# print results
solution = {1: 0.5, 2: 0.5, 3: 0.}
print(f"Solution: {solution}")
print(f"Exact Myerson values: {my_values}")
print(f"Sampled Myerson values: {my_values_sampled}")

Explain a PyG GNN Prediction

import torch
import torch_geometric
from myerson.pyg_explain import MyersonExplainer, MyersonSamplingExplainer

# define or load a graph to be explained
edge_index = torch.tensor([[0, 1, 1, 2],
                            [1, 0, 2, 1]], dtype=torch.long)
x = torch.tensor([[-1], [0], [1]], dtype=torch.float)
graph = torch_geometric.data.Data(x=x, edge_index=edge_index)

# define or load a model
class DummyModel(torch.nn.Module):
    # init with PyG layers

    def forward(self, x, edge_index, batch):
        return sum(x)
model = DummyModel()

# explain prediction
explainer = MyersonExplainer(graph=graph, coalition_function=model,
                            disable_tqdm=False)
my_values = explainer.calculate_all_myerson_values()

# explain prediction using sampling
sampler = MyersonSamplingExplainer(graph=graph, coalition_function=model,
                                seed=42, number_of_samples=1000,
                                disable_tqdm=False)
sampled_my_values = sampler.sample_all_myerson_values()
print(f"{my_values=}")
print(f"{sampled_my_values=}")

Visualizing Explanations on Molecular Structures

We used modified functions from the RDKit package to map the Myerson values as a heatmap onto a molecular structure. For an implementation look here.