Computing the Shapley Value of Threshold Cardinality Matching Games

Abstract

The Shapley value is one of the most important solutions on the scheme of distributing the profits among agents in cooperative games. In this paper, we discuss the computational and complexity issues on the Shapley value in a particular multi-agent domain, a threshold cardinality matching game (TCMG). We show that the Shapley value can be calculated in polynomial time when graphs are restricted to some special graphs, such as linear graphs and the graphs having clique or coclique modules decomposition. For general graphs, we prove that calculating the Shapley value is #P-complete when the threshold is a constant.

The work is partially supported by National Natural Science Foundation of China (NSFC) (No. 11271341 and 11501316).

1 Introduction

Cooperative games provide a framework for profit or cost distribution in multi-agent systems, such as network flow game [10], weighted voting games [6]. In cooperative game, the Shapley value is an important distribution scheme aiming to capture the notion of fairness of the distribution, based on the intuition that the payment that each agent receives should be proportional to his contribution [16]. Algorithmic issues on computing the Shapley value have been the topic of detailed studies, varieties of complexity results are presented. In Deng and Papadimitriou’s work [6], it was shown that computing the Shapley value can be done in polynomial time in weighted subgraph games, while it is #P-complete in weighted majority games. Matsui and Matsui [12, 13] showed that in weighted voting games, although computing the Shapley value is NP-hard, it can be done by a pseudo-polynomial time algorithm.

Matching game is one of the most important cooperative game models established on optimal matching problems, that has attracted much attention from researchers [7]. Shapley and Shubik [17] introduced assignment games, a special case of matching games defined on bipartite graph, to formulate the interaction between buyers and sellers in exchange markets. The solutions of matching games related to stability, such as the core, least-core and the nucleolus, have been extensively discussed in [1, 4, 7, 9, 11, 17, 18]. Shapley et al. [17] and Deng et al. [7] showed that the core was characterized efficiently by the dual theorem of linear programming. In [4, 11, 18] it was shown that computing the nucleolus for both assignment games and matching games in the “unweighted case” can be done in polynomial time. Aziz et al. [1] and Fang et al. [9] introduced a natural variation of matching games, called threshold matching games, and investigated the algorithmic aspect on the solutions, the least-core and the nucleolus.

However, less attention has been paid to the Shapley value in matching games. Recently, Aziz and Keijzer [2] studied the algorithmic problems on the Shapley value in cardinality matching games. Although the Shapley value is hard to compute (#P-complete), it can be computed efficiently when restricted on two special graphs (paths and graphs with a constant number of clique or coclique modueles). Bousquet [5] extended Aziz and Keijzer’s results by showing that the Shapley value of trees can be computed in polynomial time.

We note that the computational difficulty on game solutions may be quite different in matching games and its threshold versions. In this paper, we investigate the computational complexity of computing the Shapley value for threshold cardinality matching games (TCMGs). We give positive answers on computing the Shapley value when graphs restricted to some classes of graphs: linear graphs, graph consists of clique or coclique modules and complete k-partite graphs. While in general case, computation of the Shapley value is shown to be #P-complete.

The organization of the paper is as follows. In Sect. 2, we introduce the definition of threshold cardinality matching games (TCMGs) and the Shapley value. In Sect. 3, we discuss the algorithms on the computation of the Shapley value of TCMG defined on some special graphs. Section 4 is dedicated to the intractability of the Shapley value in general case. Further discussion is given in Sect. 5.

2 Preliminary and Definition

2.1 Cooperative Game and Shapley Value

A cooperative game $\varGamma =(N,\nu )$ (transferable utility) consists of a set of players $N=\{1,2,...,n\}$ and a characteristic function $\nu : 2^N{\rightarrow R}$. For each $S\subseteq N$ (named a coalition), $\nu (S)$ is called the value of S, representing the benefits achieved by the players in S collectively; $\nu (N)$ is the total benefits that the whole group N achieves. One of the central problems in cooperative game is to seek a fair or stable distribution of the total benefits $\nu (N)$ between the players in N. A distribution of the total benefits $\nu (N)$ is given by a vector $x=(x_1,x_2,...,x_n)$ with $\sum _{i=1}^nx_i=\nu (N)$, where each component $x_i$ is the payoff for player i. For convenience, throughout the paper we denote $x(S)=\sum _{i\in S}x_i$, $\forall S\subseteq N$. Different criteria of fairness and stability on distributions give rise to different solution concepts. The Shapley value [16], which we focus on in this work, is an important solution concept.

Let $\varGamma =(N,\nu )$ ($|N|=n$) be a cooperative game. For coalition $S\subseteq N$ and player $i\not \in S$, the value $\nu (S\cup \{i\})-\nu (S)$ is referred to as the marginal contribution of i w.r.t. S. The Shapley value is intended to reflect the average marginal contribution of each player over all coalitions S the player may join. Formally, the Shapley value $\varphi (\varGamma )=(\varphi _1,\varphi _2,...,\varphi _n)$ is defined as follows:

$$ \varphi _ {i}(\varGamma )=\frac{1}{n!}\sum \limits _{S\subseteq N \setminus \{i\}} |S|!(n-|S|-1)!\left[ \nu (S\cup \{i\})-\nu (S)\right] \forall i\in N.$$

The importance of the Shapley value lies in the fact that it is the unique solution satisfying the following properties [20]:

• 1. Efficiency: $\sum _{i\in N}\varphi _i(\varGamma )=\nu (N)$;

• 2. Null player: If $\nu (S\cup \{i\})-\nu (S)=0$ for all $S\subseteq N \setminus \{i\}$ (player i is called a null player), then $\varphi _i (\varGamma )=0$;

• 3. Symmetry: If $\nu (S\cup \{i\})-\nu (S)=\nu (S\cup \{j\})-\nu (S)$ for all $S\subseteq N\setminus \{i,j\}$ (players i and j are called symmetric), then $\varphi _i (\varGamma )=\varphi _j (\varGamma )$;

• 4. Additivity: For any two games $\varGamma ^1=(N,\nu )$ and $\varGamma ^2=(N,w)$ and their combined game $\varGamma ^1+\varGamma ^2=(N, \nu +w)$, $\varphi _i(\varGamma ^1+\varGamma ^2) =\varphi _i(\varGamma ^1)+\varphi _i(\varGamma ^2)$.

2.2 Threshold Cardinality Matching Game (TCMG)

Now we introduce the definition of threshold cardinality matching games. For more detailed introduction, please refer to [1, 8, 11]. All the graphs we consider in this paper are simple undirected graphs.

Let $G=(V,E)$ be a graph, V be the vertex set, E be the edge set. A matching M of G is an edge subset in which no edges have a common endpoint, and the size (cardinality) of M is denoted by |M|. A matching is maximum if its size is maximum over all the matchings in G, and the size of a maximum matching of G is denoted by $\gamma ^*(G)$.

Given a graph $G=(V,E)$ and a threshold value $T\in Z^+$, the corresponding threshold cardinality matching game (TCMG), denoted by $\varGamma (G)=(V,\mu ;T)$, is defined as:

• The player set is the vertex set V;

• $\forall S\subseteq V$, $\mu (S)=\left\{ \begin{array}{ll} 1 &{} \ \ \text{ if } \ \gamma ^*(G[S])\ge T\\ 0 &{} \ \ \mathrm{otherwise}. \end{array}\right.$, where, G[S] is the subgraph of G induced by S.

Note that, TCMG is a threshold version of (cardinality) matching game. In a matching game on graph $G=(V,E)$, the value of each coalition $S\subseteq V$ is defined as $\gamma ^*(G[S])$. Some basic ideas in Aziz and Keijzer’s work [2] on matching games are used for reference in our work.

2.3 Observations on the Shapley Value of TCMG

In this subsection, we give some general observations about the Shapley value of TCMG.

Let $\varGamma (G)=(V,\mu ;T)$ be the TCMG defined on graph $G=(V,E)$. Given player $i\in V$ and coalition $S\subseteq N\setminus \{i\}$, if $\mu (S\cup \{i\})-\mu (S)=1$, then the player i is called pivotal for coalition S. That is, if player i is pivotal for coalition S, then $\gamma ^*(G[S])=T-1$ and $\gamma ^*(G[S\cup \{i\}])=T$, respectively.

Denote by $\mathcal{P}_i$ the set of coalitions for which player i is pivotal. Then the Shapley value $\varphi _i$ of TCMG $\varGamma (G)$ can be rewritten via the size of $\mathcal{P}_i$:

$$\varphi _i(\varGamma )=\sum _{s=1}^{n-1}\frac{s!(n-s-1)!}{n!} \big |\{S\in \mathcal{P}_i: |S|=s\} \big |.$$

Lemma 1

Let $G=(V,E)$ be a graph with $|V|=n$ and $i\in V$. In the corresponding TCMG $\varGamma (G)$, for each $s=1,2,...,n-1$, if the number of subsets in $\{S\in \mathcal{P}_i:|S|=s\}$ can be determined in time f(n), then the Shapley value of i in $\varGamma (G)$ can be computed in time nf(n).

3 Efficient Algorithms in Special Cases

Based on the properties of Efficiency and Symmetry, the Shapley value can be obtained easily for TCMGs on symmetric graphs, such as, the complete graph $K_n$, complete bipartite graph $K_{n\times n}$ and cycles. In the following, we shall discuss the algorithms on the Shapley value for TCMGs defined on two special kinds of graphs: linear graphs and graphs consisting of clique or coclique modules.

3.1 Linear Graphs

A linear graph (or a path) is a graph containing two end-vertices of degree 1 and the remaining vertices of degree 2. Throughout this subsection, a linear graph is denoted as $G_L=(V,E)$, where

• the vertex set is $V=\{1,2,...,n\}$, 1 and n are end-vertices (the degree is 1);

• the edge set is $E=\{(j,j+1): j=1,2,...,n-1\}$.

To compute the Shapley value, we first give the following result on linear graphs. For each $s=1,2,...,n-1$ and $0\le k\le \lfloor \frac{n}{2} \rfloor$, denote $\mathcal H^s[k]$ the set of subsets $S\subseteq V$ such that $|S|=s$ and $\gamma ^*(G[S])=k$.

Lemma 2

Given a linear graph $G_L=(V,E)$ with $|V|=n$, the size of the set $\mathcal H^s[k]$ can be computed in polynomial time ($\forall s=1,2,...,n-1$ and $0\le k\le \lfloor \frac{n}{2} \rfloor$).

Proof

We prove the result by induction on the parameter k.

When $k=0$. It is clear that the set $S\in {\mathcal H^s{0}}$ is an independent set of size s. Therefore, the size of $\mathcal H^s{0}$ equals the number of ways to choose s non-adjacent vertices from n vertices on the line, that is,

$$ \big | \mathcal H^s[0]\big | =C^s_{n-s+1}.$$

Where

$$ C^k_{n}=\frac{n!}{k!(n-k)!}.$$

When $k=1$. There is only one matching edge in G[S]. We distinguish two cases.

Case 1. G[S] has only a couple of connected vertices, and the other vertices are independent. See Fig. 1(a). Analogous to the analysis for $k=0$, we have

$$ \big | \mathcal H^s[1]\big | =C^1_{s-1}\cdot C^{s-1}_{n-s+1}.$$

Case 2. G[S] has three connected vertices, the other vertices are independent. See Fig. 1(b). We also have

$$ \big | \mathcal H^s[1]\big | =C^1_{s-2}\cdot C^{s-2}_{n-s+1}.$$

Hence, the result is true when $k=1$.

Fig. 1.

The sets with two connected vertices(a) and three connected vertices(b)

We assume that the result is true for $k=p\ge 1$, that is, $\big | \mathcal H^s[p]\big |$ can be computed in polynomial time.

Then we prove the result for $k=p+1$. For this purpose, we use induction for the number of vertices |V| in $G_L$.

For $|V|=2(p+1)$, $G_L$ has a unique maximum matching of size $p+1$. Hence, the size of $\mathcal H^s [p+1]$ is 1 for $s=2(p+1)$, and 0 for other values of s.

For $|V|=2(p+1)+1$, $\gamma ^*(G_L)=p+1$. It is easy to verify that the size of $\mathcal H^s [p+1]$ is $p+2$ for $s=2(p+1)+1$, 1 for $2(p+1)$, and 0 for other values of s.

Assume that size of $\mathcal H^s[p+1]$ can be determined in polynomial time for $|V|=n$. Consider a linear graph $G_L=(V,E)$ with $|V|=n+1$. Denote

$$V=\{0,1,2,...,n\} \ \text {and} \ E=\{(j,j+1): j=0,1,...,n-1\}.$$

We divide the set $\mathcal H^s[p+1]$ into two subsets:

$$\begin{array}{l} \mathcal H^s_{+0}[p+1]=\{S\in \mathcal H^s[p+1]: 0\in S\} \\ \mathcal H^s_{-0}[p+1]=\{S\in \mathcal H^s[p+1]: 0\not \in S\}. \end{array}$$

• (i) The size of $\mathcal H^s_{-0}[p+1]$ equals the size of $\mathcal H^s[p+1]$ in graph $G_L\setminus \{0\}$ (containing n vertices), which can be counted in polynomial time followed by induction assumption.

• (ii) For $\mathcal H^s_{+0}[p+1]$, $\forall t=0,1,...,n$, we denote

  $$\mathcal H^s_{+0}[p+1](t)=\{S\in \mathcal H^s_{+0}[p+1]:\{0,1,2,...,t\}\subseteq S \, \text{ and } \, t+1\not \in S\}.$$

When $t=0$, S does not contain vertex 1. Hence, we just need to count the number of the subset S in graph $G'_L=G_L\setminus \{0,1\}$, such that the $\gamma ^*(G'_L[S])=p+1$ and $|S|=s-1$. That is, the size of $\mathcal H^s_{+0}[p+1](0)$ equals the size of $\mathcal H^{s-1}[p+1]$ in graph $G'_L=G_L\setminus \{0,1\}$, where $G'_L$ has only $n-1$ vertices. By induction assumption, the size of $\mathcal H^s_{+0}[p+1](0)$ can be determined in polynomial time.

When $t=1$, S contains vertices 0,1 and does not contain vertex 2. Obviously, the size of $\mathcal H^s_{+0}[p+1](1)$ equals the size of $\mathcal H^{s-2}[p]$ in graph $G"_L=G_L\setminus \{0,1,2\}$, where $G"_L$ contains only $n-2$ vertices. Also by induction assumption, the size of $\mathcal H^s_{+0}[p+1](1)$ can also be determined in polynomial time.

With similar analysis, we claim that the size of $\mathcal H^s_{+0}[p+1](t)$ can be determined in polynomial time for $t=2,3,...,n$. Since

$$|\mathcal H^s_{+0}[p+1]|=\sum _{t=0}^{min\{s-1,2(p+1)\}}|\mathcal H^s_{+0}[p+1](t)|, $$

it is followed directly that $\big |\mathcal H^s[p+1]\big |$ can be determined in polynomial time.

The proof is done.    $\square$

Lemma 3

If graph $G=(V,E)$ has K connected components (K is a fixed number independent of |V|) and each component is a linear graph, then the size of the set $\mathcal H^s[k]$ can be determined in polynomial time.

In the TCMG defined on $G_L=(V,E)$ with $V=\{1,2,...,n\}$, for each player i and a coalition S for which i is pivotal, we give some notations for convenience of discussion. For $i\in V$ and $1\le s\le n-1$, denote:

$$\mathcal{P}_{i}^s=\{S\subseteq V\setminus \{i\}: \ i \ \text{ is } \text{ pivotal } \text{ for } \ S, \ |S|=s\}.$$

And

$$ \begin{array}{l} \mathcal{P}_{i,R}^{s}=\{S\subseteq V\setminus \{i-1, i\}: i+1\in S, S\in \mathcal{P}_{i}^s \};\\ \mathcal{P}_{i,L}^{s}=\{S\subseteq V\setminus \{i, i+1\}: i-1\in S, S\in \mathcal{P}_{i}^s \};\\ \mathcal{P}_{i,C}^{s}=\{S\subseteq V\setminus \{i\}: i+1, i-1\in S, S\in \mathcal{P}_{i}^s \}. \end{array} $$

It is easy to see that $\mathcal{P}_{i,R}^{s}$, $\mathcal{P}_{i,L}^{s}$ and $\mathcal{P}_{i,C}^{s}$ are disjoint, and

$$|\mathcal{P}_{i}^s|=|\mathcal{P}_{i,R}^s|+|\mathcal{P}_{i,L}^s|+|\mathcal{P}_{i,C}^s|.$$

Theorem 1

The Shapley value of the TCMG defined on linear graph $G_L=(V,E)$ ($|V|=n$) can be computed in polynomial time for any threshold $T\le \lfloor \frac{n}{2}\rfloor$.

Proof

Since the Shapley value $\varphi _i$ $(i=1,2,...,n)$ in TCMG $\varGamma (G_L)$ can be rewritten as

$$\varphi _i=\sum _{s=1}^{n-1}\frac{s!(n-s-1)!}{n!} \Big |\mathcal{P}_{i}^s\Big |,$$

we need only to show that the size of $\mathcal{P}_{i}^s$ (that is, the sizes of $\mathcal{P}_{i,R}^{s}$, $\mathcal{P}_{i,L}^{s}$ and $\mathcal{P}_{i,C}^{s}$) can be determined in polynomial time.

• (1) When $T=1$. It is clear that a coalition $S\in \mathcal{P}_{i,R}^{s}$ is exactly an independent set with size $s-1$ in $G_L$ not containing the vertices $i-1,i,i+1$ and $i+2$. That is, S must be the union of two independent sets: one is in $G[\{1,2,...,i-2\}]$ of size $s_1$ and the other is in $G[\{i+3,i+4,...,n\}]$ of size $s_2$, where $s_1+s_2=s-1$. Hence, following from Lemma 3, the size of $\mathcal{P}_{i,R}^{s}$ can be determined in polynomial time. Similarly, the size of $|\mathcal{P}_{i,L}^{s}|$ and $|\mathcal{P}_{i,C}^{s}|$ can also be computed efficiently.

• (2) We prove the result for $T=k\ge 2$. We first discuss the size of $\mathcal{P}_{i,R}^s$. Denote by $\mathcal{P}_{i,R}^s(t)$ the set of coalitions $S\in \mathcal{P}_{i,R}^s$, such that $i+1,i+2,...,i+t+1\in S$ and $i+t+2\not \in S$. It is easy to see that the size of $\mathcal{P}_{i,R}^s(t)$ is 0, if t is odd.

When $t=0$, the size of $\mathcal{P}_{i,R}^s(0)$ equals the size of $\mathcal{H}^{s-1}[k]$ in $G'=G[V\setminus \{i-1,i,i+1,i+2\}]$ (recall the notation $\mathcal{H}^{s-1}[k]$ in Lemma 2), yielding that the size of $\mathcal{P}_{i,R}^s(0)$ can be determined in polynomial time by Lemma 2. Similar analysis can be given for t is even. Also since

$$|\mathcal{P}_{i,R}^{s}|=\sum _{t=0}^{min\{s-1,2(k-1)\}}|\mathcal{P}_{i,R}^{s}(t)|,$$

$\mathcal{P}_{i,R}^s$ can be counted in polynomial time.

The size of $\mathcal{P}_{i,L}^s$ and $\mathcal{P}_{i,C}^s$ can be obtained in a similar way, meaning that the size of $\mathcal{P}_{i}^s$ can be determined in polynomial time.

The proof is done.    $\square$

3.2 Graphs with a Constant Number of Clique or Coclique Modules

Given a graph $G=(V,E)$, a subset $S\subseteq V$ is a module if all the vertices in S have the same neighbors in $N\setminus S$. A subset $S\subseteq V$ is a clique (resp. coclique) module means that S is a clique (resp. coclique) and a module, i.e.,  all vertices in the module S are pairwise connected (resp. disconnected). Obviously, the partition of vertex set V into singletons is a trivial modular decomposition. In [1], Aziz and Keijzer showed that for graph G, a minimum cardinality module decomposition into cocliques or cliques can be found in polynomial time.

In a cooperative game, a set of players S is said to be of the same player type if all players in S are pairwise symmetric. Ueda et al. [19] showed that for a cooperative game $\varGamma =(N,\nu )$ in which $\nu (S)$ $(S\subseteq N)$ can be computed in polynomial time, and there is a fixed size k partition of the players into the same player type, then the Shapley value can be computed in polynomial time (in n) via dynamic programming. For a TCMG defined on graph G, which can be decomposed into k coclique modules or clique modules, all the players in the same coclique module or clique module of G are of the same player type. Based on these analysis, we have the following theorem.

Theorem 2

Let $G=(V,E)$($|V|=n$) be a graph in which there exists a modular decomposition into k cocliques or k cliques, where k is independent of n. Then the Shapley value of the TCMG defined on G can be computed in polynomial time for any threshold $T\le \lfloor \frac{n}{2}\rfloor$.

Corollary 1

Let $G=(V,E)$ be a complete k-partite graph (k is independent of n). Then the Shapley value of the TCMG defined on G can be computed in polynomial time.

4 Computational Complexity in General Case

In this section, we discuss the computational complexity of the problem of computing the Shapley value for TCMGs in general case.

For this purpose, we introduce a well known #P-complete problem, the Cardinality Vertex Cover problem [14]:

• Input: A graph $G=(V,E)$, integer k.

• Output: The size (cardinality) of the set $\{S\subseteq V: S$ is a vertex cover for G and $|S|=k\}.$

Given a graph $G=(V,E)$, we know that a vertex subset $S\subseteq V$ is a vertex cover if and only if $V\setminus S$ is an independent set in G. Then, we define the problem of Cardinality Independent Set. Denote by $\alpha _k(G)$ the number of independent sets $S\subseteq V$ with $|S|=k$. For $k=0$, we define $\alpha _0(G)=0$. And for $k=1$, $\alpha _0(G)=|V|$. The Cardinality Independent Set problem will be:

• Input: A graph $G=(V,E)$, integer k.

• Output: The size (cardinality) of the set $\{S\subseteq V: S$ is an independent set of G and $|S|=k\}.$

Lemma 4

[14]. The problem of Cardinality Independent Set is #P-complete.

In the next theorem, we discuss the computational complexity of computing the Shapley value in the special case of TCMG where the threshold is $T=1$.

Theorem 3

Given a graph $G=(V,E)$ ($|V|=n$), computing the Shapley value of the TCMG defined on graph G for threshold $T=1$ is #P-complete.

Proof

We prove the intractability of computing the Shapley value by making use of a polynomial-time Turing reduction from the problem of Cardinality Independent Set.

We first construct a series of $n+1$ new graphs based on G.

For $i=1,2,...,n,n+1$, we construct graph $G_i$ as follows (In Fig. 2):

• (1) Add a star graph $T_i$ with center vertex y and the other vertices $x_1,x_2,...,x_i$;

• (2) The graph $G_i$ is composed of two components: the original graph G and the star graph $T_i$.

For $i=1,2,...,n,n+1$, we denote the TCMG defined on graph $G_i$ by $\varGamma _i$. Then we focus on the Shapley value of player y in each $\varGamma _i$:

$$\varphi _y(\varGamma _i)=\sum _{s=1}^{n+i}\frac{s!(n+i-s)!}{(n+i+1)!}(\mu (S\cup \{y\})-\mu (S)),$$

where $S\in V\cup \{x_1,x_2,...,x_i\}$ is the subset of players in $\varGamma _i$ (i.e., the subset of vertices in $G_i$ with size of $|S|=s$). To simplify the proof, we consider the “raw Shapley value":

$$\kappa _y(\varGamma _i)=\sum _{s=1}^{n+i}s!(n+i-s)!(\mu (S\cup \{y\})-\mu (S)),$$

which has the same computational complexity with the Shapley value.

Fig. 2.

$G_{i}$

Obviously, if $\mu (S\cup \{y\})-\mu (S)=1$, then there will be at least one vertex of $x_1,x_2,...,x_i$ in S. By carefully calculating, we have

$$\begin{aligned} \begin{array}{rl} \kappa _y(\varGamma _i) &{}=\, \displaystyle \sum _{s=1}^{n+i} {s!(n+i-s)!}[C_i^1 \alpha _{s-1}(G)+C_i^2 \alpha _{s-2}(G)+...+C_i^i\alpha _{s-i}(G)]\\ &{}=\, \mathop {\sum }\limits _{s=1}^{n+1}\Big [C_i^1 s!(n+i-s)!+C_i^2 (s+1)!(n+i-s-1)!\\ &{} \quad +...+C_i^i (s+i-1)!(n-s+1)!\Big ]\alpha _{s-1}(G). \end{array} \end{aligned}$$

(4.1)

Denote the coefficient of $\alpha _{s-1}(G)$ in the formula (4.1) by $b_{is}$ for $s=1,2,...,n+1$, that is,

$$\begin{array}{rl} b_{is}&{}= C_i^1 s!(n+i-s)!+C_i^2 (s+1)!(n+i-s-1)!\nonumber \\ &{} +...+C_i^i(s+i-1)!(n-s+1)!. \end{array}$$

Then $\kappa _y(\varGamma _i)$ can be written as:

$$\begin{aligned} \kappa _y(\varGamma _i)=\sum _{s=1}^{n+1} b_{is}\alpha _{s-1}(G). \end{aligned}$$

(4.2)

Denote the coefficient of $\alpha _{s-1}(G)$ in the (4.2) by $b_{is}$ for $s=1,2,...,n+1$, and denote by $\varTheta =\big (b_{is}\big )_{(n+1)\times (n+1)}$ the matrix. Putting all the formulas (4.2) for $i=1,2,...,n+1$ together, we have

$$\begin{aligned} \left( \begin{array}{c} {\kappa _y}(\varGamma _1)\\ {\kappa _y}(\varGamma _2)\\ \vdots \\ {\kappa _y}(\varGamma _{n+1}) \end{array}\right) =\varTheta \cdot \left( \begin{array}{c} {\alpha _0}(G)\\ {\alpha _1}(G)\\ \vdots \\ {\alpha _n}(G) \end{array}\right) . \end{aligned}$$

(4.3)

We then prove that $\alpha _s(G)$ can be computed by solving $k_y(\varGamma _i)$ in polynomial time.

Lemma 5

The determinant of matrix A defined by $A_{ij}=(i+j)!$ is equal to $\Pi _{i=0}^{n}i!^2\not =0$.

A is a matrix that is related to Pascal triangle [3], and we will show $\varTheta$ also is related to Pascal triangle and is nonsingular.

Note that $C_n^m=C_{n-1}^m+C_{n-1}^{m-1}$. We can rewrite the formulation of $\kappa _y(\varGamma _i)$ in (4.1), for $i\ge 2$:

$$\begin{aligned} \begin{array}{ll} \kappa _y(\varGamma _i)&{}=\,\displaystyle \sum _{s=1}^{n+1}\Big [(C_{i-1}^0+C_{i-1}^1) s!(n+i-s)!\\ &{} \qquad \,\, +(C_{i-1}^1+C_{i-1}^2) (s+1)!(n+i-s-1)! \\ &{} \qquad \,\, +...+(C_{i-1}^{i-1}+C_{i-1}^i) (s+i-1)!(n-s+1)!\Big ]\alpha _{s-1}(G)\\ &{}=\,\mathop {\sum }\limits _{s=1}^{n+1}s!(n+i-s)! \alpha _{s-1}(G)+(n+i+1)\kappa _y(\varGamma _{i-1})\\ &{}=\,\mathop {\sum }\limits _{s=1}^{n=1}\Big [s!(n+i-s)!+(n+i+1)b_{i-1 s}\Big ] \alpha _{s-1}(G). \end{array} \end{aligned}$$

(4.4)

The last “equation” in (4.4) holds based on the formulation of $\kappa _y(\varGamma _{i-1})$ (4.2).

From Eq. (4.4), the matrix $\varTheta$ in (4.3) can be transformed into

$$\begin{aligned} \varTheta '= \left( \begin{array}{ccc} 1!n!&{}\dots &{}(n+1)!0!\\ 1!(n+1)!+(n+2)b_{11}&{}\dots &{}(n+1)!1!+(n+2)b_{1n+1}\\ \vdots &{} \ddots &{}\vdots \\ 1!(2n)!+(2n+1)b_{n 1}&{}\dots &{}(n+1)!n!+(2n+1)b_{n 2n+1} \end{array}\right) \end{aligned}$$

(4.5)

Based on the relationship of the coefficient of $\alpha _{s-1}(G)$ in (4.2) and (4.4):

$$b_{is}=s!(n+i-s)!+(n+i+1)b_{i-1 s},$$

we use the matrix elementary operations on the matrix $\varTheta '$ to transform it into the following form:

$$\begin{aligned} \varTheta '' = \left( \begin{array}{cccc} 1!n!&{}2!(n-1)!&{}\dots &{}(n+1)!0!\\ 1!(n+1)!&{}2!n!&{}\dots &{}(n+1)!1!\\ \vdots &{}\vdots &{}\ddots &{}\vdots \\ 1!(2n)!&{}2!(2n-1)!&{}\dots &{}(n+1)!n! \end{array}\right) \end{aligned}$$

(4.6)

From Lemma 5, we conclude that the matrice ${\varTheta }$, ${\varTheta '}$ and $\varTheta ''$ are all nonsingular, it follows from (4.3) that we can solve $\alpha _s(G)$ by solving $k_y(\varGamma _i)$ in polynomial time, and vice versa.    $\square$

Note that, the case of threshold $T=1$ is a special case for TCMGs, so we have the general complexity result.

Theorem 4

Computing the Shapley value of a TCMG is #P-complete.

Based on Deng and Papadimitriou’s work [6], Aziz and Brandt [1] also conclude that Computing the Shapley value of threshold matching games is #P-complete. But in their proof, the threshold was set to be related to the size of the graph, rather than a fixed number. Therefore, Theorem 4 generalizes Aziz and Brandt’s result.

5 Conclusion and Further Discussion

In this paper, we focus on the computation of the Shapley value for TCMGs. We show that the Shapley value can be computed in polynomial time on special graphs: linear graphs and graphs consist of clique or coclique modules. For general graphs, we prove that computing the Shapley value is #P-complete. However, there are still quite a few problems for further discussion.

Firstly, given a graph G with k connected components $G_1,G_2,...,G_k$, how to obtain the Shapley value on G through the Shapley values of each components. The difficulty is that the TCMG defined G can not be viewed as the sum of the TCMGs defined on $G_1,G_2,...,G_k$, that is, the property of Additivity does not holds. For example, for both linear graphs and cycles, the Shapley value can be computed efficiently, but till now we have no evidence to show the same result for non-connected graphs with vertex degree at most two.

Secondly, Bousquet [5] recently proved that the Shapley value on trees can be computed in polynomial time. We conjecture that the ideas in [5] can be used to compute the Shapley value for TCMGs. Another algorithmic problem is that when the computation of the Shapley value is hard, how to design the approximation algorithms.

Thirdly, as a similar solution concept as the Shapley value, the Banzhaf index of TCMG has not been discussed. Like the Shapley value, the Banzhaf index measures agents marginal contributions over all coalitions. Given a characteristic function game $\varGamma =(N,v)$ with $|N| = n$, the Banzhaf index of a player $i\in N$ is

$$\beta _i(G)=\frac{1}{2^{n-1}}\sum _{S\subseteq N\setminus \{i\}}\big [v(S\cup \{i\}-v(S)\big ].$$

In our opinion, the efficiency on computation of the Shapley value would yield the same result on the Banzhaf index. However, the computational complexity on the computation of the Banzhaf index for TCMGs in general case is still open.