Keywords

1 Introduction

There is a concept of the vertex cover of an undirected graph in the graph theory [17]. A vertex cover of a graph G = 〈N, E〉, E ⊆{{a, b}|a, b ∈ N} is any subset S of the set of graph vertices N such that any edge of this graph is incident to least one vertex in the set S. We are interested in the vertex cover with a minimal number of vertices, i.e. so-called minimum vertex cover of a graph.

Let us list some of the applications for the problem of finding the minimum vertex cover.

Vertex cover in transport networks. Let the undirected graph G be a transport network. Each vertex is a crossroad, an edge is a road. If surveillance cameras are deployed at vertices of the minimum vertex cover, then every road portion will be monitored by a camera and the costs of purchasing cameras will be minimized [1, 23].

Vertex cover in a society. Let each vertex of the graph G be a person. If there is a conflict between two people, then there exists an edge between the vertices representing these people. Denote by S the minimum vertex cover. There are no conflicts between people in the set N  ∖ S, and the dimensionality of this set is maximal [7, 19].

To determine the power of vertices in the vertex cover, we use the methods of the cooperative game theory. In the terms of the game theory, each vertex can be regarded as an individual player. We consider the terms ‘vertex’ and ‘player’ to be synonyms. The vertex cover is a coalition of players. If a group of vertices contains at least one vertex cover, the payoff of this group of vertices is one; otherwise it is zero. The characteristic function of the cooperative game takes only two values: 0 and 1 [6]. Shapley suggested using the cooperative game theory for measuring the influence of parties. The application of Shapley values and cooperative games to allocate resources can be found in [4]. An application of the Shapley value to transport and computer networks is described in [14]. The Shapley-Shubik index is also used in benefit allocation in games on electricity networks [24], and for the analysis of hierarchical structures [12], and human behavior [20]. In this study, the Shapley-Shubik index is applied to estimate the power of graph vertices with regard to vertex covers. Methods of decision-making on networks can be found in [8]. The problems of resource allocation on the network are studied in [5].

2 Game Formation

Let us introduce several concepts to define the cooperative vertex cover game. A vertex cover S of an undirected graph G = 〈N, E〉 is a subset of N such that ∀(u, v) ∈ E ⇒ u ∈ S or v ∈ S [11, 16]. The minimum vertex cover of the graph G = 〈N, E〉 is the vertex cover consisting of the smallest possible number of vertices. A vertex cover S of the graph G is called least vertex cover if for ∀i ∈ S the set S ∖{i} is not a vertex cover. Denote by M(G) the set of least vertex covers of the graph G.

Definition 1

Let G = 〈N, E〉, E ≠ ∅ an undirected graph, M(G) is the set of least vertex covers of the graph G. A simple game 〈N, v〉 is a vertex cover game of G if W m(v) = M(G), that is

$$\displaystyle \begin{aligned} v(K)=\begin{cases} 1, &\mathrm{if}\;\exists A\in M(G):A\subseteq K;\\ 0,&\mathrm{otherwise}. \end{cases}\;\; \forall K\subseteq N.\end{aligned}$$

Definition 2

Let G = 〈N, E〉, E ≠ ∅ an undirected graph, M(G) is the set of least vertex covers of the graph G. A simple game 〈N, v〉 is a vertex cover game of G if W m(v) = M(G), that is

$$\displaystyle \begin{aligned} v(K)=\begin{cases} 1, &\mathrm{if}\;\exists A\in M(G):A\subseteq K;\\ 0,&\mathrm{otherwise}. \end{cases}\;\; \forall K\subseteq N. \end{aligned}$$

Proposition 1 shows how the characteristic function of the vertex cover game can be represented in the form of an intersection of simple monotone characteristic functions.

Proposition 1

Let Y = {1, 2, …, r}, G = 〈N, E〉, G j = 〈N, E j〉, j ∈ Y  be undirected graphs, where E =⋃j ∈ Y E j. Then, ∀K ⊆ N we have

$$\displaystyle \begin{aligned} v(K)= \left ( v_1\wedge v_2\wedge\ldots \wedge v_r\right ) (K),{} \end{aligned} $$
(1)

where ∀j ∈ Y  〈N, v〉, 〈N, v j〉 are vertex cover game with W m(v) = M(G), W m(v j) = M(G j).

Proposition 1 is based on the properties of vertex covers of a graph. No papers have been found that analyze simple games in which the set of minimal winning coalitions is the set of least vertex covers of a graph. Applications for the union and intersection of simple functions can be found in the papers [2].

Consider two simple games 〈N, v〉, 〈N, w〉, such that |W m(v)| = |W m(w)| = a and ∀A ∈ W m(v) ∀B ∈ W m(w) : A⊈B and B⊈A. Then,

$$\displaystyle \begin{aligned} W^m(v\vee w )=\{A|A\in W^m(v)\; \mathrm{or}\; A\in W^m(w)\}, \end{aligned}$$
$$\displaystyle \begin{aligned} W^m(v\wedge w)=\{A\cup B|A\in W^m(v) \;\mathrm{and}\; B\in W^m(w)\}. \end{aligned}$$

Hence, |W m(v ∧ w)| = a 2, and |W m(v ∨ w)| = 2a. Since the equality (v ∧ w)(K) = v(K) + w(K) − (v ∨ w)(K), holds for simple games, then instead of considering the characteristic function with a 2 minimal winning coalitions we can simultaneously consider three games, the total number of minimal winning coalitions in the three games being 4a. Knowing the representation of the characteristic function in the form of a conjunction of simple games, one can consider games with a smaller number of minimal winning coalitions.

Value ϕ has linearity property if ϕ(αv + βw) = αϕ(v) + βϕ(w), α, β ∈ R;v, w are characteristic functions. If the characteristic function of a cooperative vertex cover game can be represented in the form of a linear combination of characteristic functions, then the linearity property can be used to calculate the Shapley-Shubik index. The original graph can be decomposed into subgraphs so as to fulfill the conditions of Proposition 1. Then, using (v ∧ w)(K) = v(K) + w(K) − (v ∨ w)(K), the characteristic function of the vertex cover game can be represented in the form of a linear combination of other functions. It is convenient to use the decomposition procedure if a graph is large enough, e.g. a network- or a communication graph. With this approach, it is not necessary to know the minimal winning coalitions of the original characteristic function. The same is true for linear values in games, such as the Banzhaf value, Owen value and others.

Proposition 2

A simple game 〈N, v〉, is a vertex cover game on graph G if and only if there exist simple games 〈N, v l(K)〉, l ∈{1, 2, …, r}, W m(v l) = {{i l}, {k l}} for which the equality

$$\displaystyle \begin{aligned} v(K)=(v_1\wedge v_2\wedge \ldots \wedge v_r )(K){} \end{aligned} $$
(2)

holds, and G = 〈N, E〉, E = {{i l, k l}|1 ≤ l ≤ r}.

Decompose the characteristic function v over the basis (Möbius transformation) [22], and set \(u(x)=\sum _{S\subseteq N}\left ( \lambda _S(v)\prod _{i\in S} x_i\right ),\; \forall x\in \{0,1\}^n,\) where λ S(v) =  ∑R⊆S(−1)|S|−|R| v(R). In that case, if f : [0, 1]n → R is a multilinear extension of u : {0, 1}n → R, then \(\phi _i(N,v)=\int _{0}^{1}\frac {\partial f}{\partial x}(t,t,\ldots ,t)dt \;\)[15, 21]. If the minimal winning coalitions do not intersect, the following statement is true.

Proposition 3

Let W m(v) = {A 1, A 2, …, A m}, |A j| = a j, j = 1, 2, …, m;∀i, j, i ≠ j : A i ∩ A j = ∅. Then, in the simple game 〈N, v〉, the Shapley-Shubik index for the player k ∈ N is calculated by the formula

$$\displaystyle \begin{aligned} \phi_k(v)=\int_{0}^{1}x^{a_i-1}\prod_{j=1,j\neq i}^m(1-x^{a_j})dx, \end{aligned}$$

where k ∈ A i, a i = |A i|, i ∈{1, 2, …, m}.

Proof

Fix the player k. Since the minimal winning coalitions do not intersect, there exists only one minimal winning coalition containing the player k. Denote this coalition by A i. Let L ⊆{1, 2, …, m}, L ≠ ∅. Then

The following sequence of equations is valid:

$$\displaystyle \begin{aligned}=\sum_{L\subseteq \{1,2,\ldots ,m\}\setminus \{i\}}\frac{(-1)^{|L|}}{a_i+\sum_{j\in L}a_j}=\sum_{L\subseteq \{1,2,\ldots ,m\}\setminus \{i\}}(-1)^{|L|}\int_{0}^{1}x^{a_i-1+\sum_{j\in L}a_j}dx= \end{aligned}$$
$$\displaystyle \begin{aligned} =\int_{0}^{1}\left (\sum_{L\subseteq \{1,2,\ldots ,m\}\setminus \{i\}}(-1)^{|L|}\cdot x^{a_i-1+\sum_{j\in L}a_j} \right )dx= \end{aligned}$$
$$\displaystyle \begin{aligned} =\int_{0}^{1}x^{a_i-1}\left (\sum_{L\subseteq \{1,2,\ldots ,m\}\setminus \{i\}}(-1)^{|L|}\cdot x^{\sum_{j\in L}a_j} \right )dx=\int_{0}^{1}x^{a_i-1}\prod_{j=1,j\neq i}^m(1-x^{a_j})dx. \end{aligned}$$

The lemma is thus proven.

Example 1

Let N be the set of players, and 1  ∈ N. W m(v) = {A 1, …, A m} is the set of minimal winning coalitions, and elements of the set W m(v) fulfill the following restrictions: 1. ∀i, j, i ≠ j : A i ∩ A j = {1}; 2. |A i| = i + 1. E.g., A 1 = {1, 2}, A 2 = {1, 3, 4}, A 3 = {1, 5, 6, 7}, etc. Find the limit payoff of player 1 in the game 〈N, v〉, where the number of minimal winning coalitions tends to infinity. We get

$$\displaystyle \begin{aligned}=1-\int_{0}^{1}\prod_{k=1}^{\infty}\left ( 1-x^{k} \right )dx=1-\frac{4\pi \sqrt{3}}{\sqrt{23}}\cdot \frac{\mathrm{sinh}\frac{\pi \sqrt{23}}{3}}{\mathrm{cosh}\frac{\pi \sqrt{23}}{2}}\approx 0.6316. \end{aligned}$$

We find that as the number of minimal winning coalitions in the set W m(v) increases, the payoff of player 1 tends to a finite limit. Some limit theorems for the Penrose-Banzhaf value can be found in [18].

The Shapley-Shubik indices for the linear graph consisting of n vertices, n = 2, 3, …, 10 are given in Table 1. Numbers from 2 to 10 in the first line indicate the number of vertices in the linear graph. Numbers from 1 to 10 in the first column are the players’ numbers. The index will be the highest for the vertices connected to end vertices.

Table 1 Solution for the linear graph
Full size table

Let G  =  〈N, E〉 be a star graph, for which E  =  {{1, 2}{1, 3}, …, {1, n}}. Consider the vertex cover game 〈N, v〉 of G, where W m(v) = {{1}, {2, 3, …, n}}. Calculate Shapley-Shubik index of each player. Elements of the set of minimal winning coalitions do not intersect each other, wherefore Proposition 3 can be applied:

$$\displaystyle \begin{aligned} \phi_1\left( v\right)=\int_{0}^{1}(1-x^{n-1})dx=1-\frac{1}{n}, \end{aligned}$$
$$\displaystyle \begin{aligned}\phi_i\left( v\right)=\int_{0}^{1}x^{n-2}(1-x)dx=\frac{1}{n(n-1)},i\neq 1. \end{aligned}$$

Proposition 4

Let G = 〈N, E〉 be a complete bipartite graph, L ∪ R = N, L ∩ R = ∅, E = {{a, b}|a ∈ L, b ∈ R}. Then, the Shapley-Shubik index for the player i ∈ N in the vertex cover game 〈N, v〉 has the following form:

$$\displaystyle \begin{aligned} \phi_i( v) =\begin{cases} \frac{1}{|L|}-\frac{1}{|L|+|R|},&i\in L;\\ \frac{1}{|R|}-\frac{1}{|L|+|R|},&i\in R. \end{cases}\end{aligned}$$

Proof

For a complete bipartite graph, W m(G) = {L, R} is valid. Elements of the set of minimal winning coalitions do not intersect with one another, wherefore Proposition 3 can be applied.

$$\displaystyle \begin{aligned} \phi_i\left( v\right)=\int_{0}^{1}x^{|L|-1}(1-x^{|R|})dx=\frac{1}{|L|}-\frac{1}{|L|+|R|},i\in L \end{aligned}$$
$$\displaystyle \begin{aligned}\phi_j\left( v\right)=\int_{0}^{1}x^{|R|-1}(1-x^{|L|})dx=\frac{1}{|R|}-\frac{1}{|L|+|R|},j\in R.\end{aligned}$$

Proposition 5

Let \(G=\langle N, E\rangle , E=\{\{1,2\},\{\{1,a_p\}_{p=1}^k\},\{\{2,b_q\}\}_{q=1}^r\}, \forall p,q:a_p\neq 2, b_q \neq 1,a_p\neq b_q\) . Then, the Shapley-Shubik index for the player i ∈ N in the vertex cover game 〈N, v〉 has the following form:

$$\displaystyle \begin{aligned} \phi_i( v)=\begin{cases} \frac{1}{2}-\frac{1}{k+2}+\frac{1}{r+1}-\frac{1}{r+2},&i=1;\\ \frac{1}{2}-\frac{1}{r+2}+\frac{1}{k+1}-\frac{1}{k+2},&i=2;\\ \frac{1}{k+1}-\frac{1}{k+2},&i=a_p,p\in\{1,\ldots ,k\};\\ \frac{1}{r+1}-\frac{1}{r+2},&i=b_q,q\in \{1,\ldots ,r\}. \end{cases}\end{aligned}$$

Proof

Decompose the graph G = 〈N, E〉 into subgraph

$$\displaystyle \begin{aligned} G_1=\langle N,E_1\rangle, G_2=\langle N,E_2\rangle \end{aligned}$$
$$\displaystyle \begin{aligned}E_1=\{\{1,2\},\{1,a_p\}\},p\in \{1,\ldots ,k\}, E_2=\{\{2,b_q\} \},q\in \{1,\ldots ,r\}, \end{aligned}$$
$$\displaystyle \begin{aligned}W^m(v_1)=\{\{1\},\{2,a_1,\ldots ,a_k\}\}, W^m(v_2)=\{\{2\},\{b_1,\ldots ,b_r\}\}, \end{aligned}$$
$$\displaystyle \begin{aligned} W^m(v_1\vee v_2)=\{\{1\},\{2\},\{b_1,\ldots ,b_r\}\}.\end{aligned}$$

Apply Proposition 1, Shapley-Shubik index linearity property, and Proposition 3. We get

$$\displaystyle \begin{aligned} \phi(v)=\phi\left (v_1\wedge v_2 \right )=\phi(v_1)+\phi(v_2)-\phi\left (v_1\vee v_2\right ). \end{aligned}$$
$$\displaystyle \begin{aligned} \phi_1(v)=\int_{0}^{1}(1-x^{k+1})dx-\int_{0}^{1}(1-x)(1-x^r)dx=\frac{1}{2}-\frac{1}{k+2}+\frac{1}{r+1}-\frac{1}{r+2}; \end{aligned}$$
$$\displaystyle \begin{aligned} \phi_2(v)=\int_{0}^{1}x^k(1-x)dx+\int_{0}^{1}(1-x^r)dx-\int_{0}^{1}(1-x)(1-x^r)dx= \end{aligned}$$
$$\displaystyle \begin{aligned} =\frac{1}{2}-\frac{1}{r+2}+\frac{1}{k+1}-\frac{1}{k+2}; \end{aligned}$$
$$\displaystyle \begin{aligned} \phi_{a_p}(v)=\int_{0}^{1}x^k(1-x)dx=\frac{1}{k+1}-\frac{1}{k+2}.\end{aligned}$$

Calculate \(\phi _{b_q}(v).\) Since W m(v 1 ∨ v 2) = {{1}, {2}, {b 1, …, b r}}, |{1}| = 1, |{2}| = 1, |{b 1, …, b r}| = r, then

$$\displaystyle \begin{aligned} \phi_{b_q}(v)=\int_{0}^{1}x^{r-1}(1-x)dx-\int_{0}^{1}(1-x)^{r-1}(1-x)^1(1-x)^1dx = \end{aligned}$$
$$\displaystyle \begin{aligned} =\int_{0}^{1}x^{r-1}(1-x)dx-\int_{0}^{1}(1-x)^{r-1}(1-x)^2dx=\frac{1}{r+1}-\frac{1}{r+2}. \end{aligned}$$

An example of the graph used in Proposition 5 is shown in Fig. 1. We get \(\phi _1(v)=\frac {34}{105}\approx 0.32, \phi _2(v)=\frac {57}{140}\approx 0.41, \phi _{a_p}(v)=\frac {1}{20}=0.05, \phi _{b_q}(v)=\frac {1}{42}\approx 0.02, p\in \{1,2,3\}, q\in \{1,2,3,4,5\}.\)

Fig. 1
figure 1

Star graph with two centers, k = 3, r = 5

Full size image

3 Application of the Shapley-Shubik Index for Estimating the Efficiency of Vertices in the Vertex Cover of a Graph

Let the graph G be a transport network. A vertex in this graph is a crossroads, an edge is a road. The task is to optimally distribute surveillance cameras. Knowing the power of graph vertices, one can deploy the cameras accordingly.

Surveillance cameras are to provide for full coverage of the transport network. If the existing cameras capture the transport network entirely, no more budget allocations are needed to purchase new cameras. Let us consider all possible rearrangements of graph vertices. Let σ denote a rearrangement of vertices. In the rearrangement σ, enumerate vertices as 1, 2, …, |V |. Denote by σ(k) the set of vertices occupying in the rearrangement σ positions before and including the vertex with the number k. The coalition of vertices σ(k) in the rearrangement σ is losing if it does not cover the transport network, and winning otherwise. If σ(k − 1) is the losing coalition and σ(k) is the winning one, then the vertex numbered as k is called pivotal for the given rearrangement. Vertices occupying positions preceding the pivotal vertex in the rearrangement do not cover the network. Vertices after the pivotal vertex make no further contribution since the transport network is already covered. Hence, the essential question when arranging cameras is whether a vertex is the pivotal one. Knowing this, the efficiency of each vertex can be calculated by the formula

where n! is the number of all possible rearrangements among n vertices. The value of ϕ i is the Shapley-Shubik index for the vertex cover game. The higher is the number of the rearrangements where the vertex is pivotal, the higher is the power of this vertex.

Denote SG n the set of all simple games with n players.

Since the vertex cover game is a simple game and the efficiency axiom (for all \(v\in SG_n, \sum _{i=1}^{n}\phi _i(v)=1\) [9]) is fulfilled for the Shapley-Shubik index, the power of each vertex is not less than zero and the sum of all values is equal to unity.

Let us demonstrate what properties an array of surveillance cameras will have if the cameras are arranged proportionately to the values of the Shapley-Shubik index in a vertex cover game. The Shapley-Shubik index conforms to the null player, anonymity, symmetry, transfer axioms.

Null player axiom: for any v ∈ SG n and any i ∈ N, if i is a null player in game v, then ϕ i(v) = 0. The player i ∈ N is called the null player if v(S) = v(S ∖{i}) for all i ∈ S ⊆ N. If the vertex degree is 0, this means there are no roads running across the given crossroads. In the vertex cover game, such a vertex is the null player. Owing to the null player property, cameras will not be deployed in the vertices in which they are unnecessary.

Anonymity axiom: for all v ∈ SG n, any permutation π of N, and any i ∈ N, ϕ i(πv) = ϕ π(i)(v), where (πv)(S) := v(π(S)). The numbers assigned to vertices have no effect on the distribution of cameras. If the vertex numbering scheme is changed but the transport network topology remains the same, the distribution of cameras will not be affected. Owing to the anonymity axiom, all vertices are in an equal position.

The Shapley-Shubik index has the symmetry axiom, i.e. if i, j ∈ N, i ≠ j v(S ∪{i}) = v(S ∪{j}) ∀S ⊆ N ∖{i, j} then ϕ i(v) = ϕ j(v). If there are two vertices symmetrical with respect to the graph’s vertex cover, then these vertices will have equal Shapley-Shubik index in the vertex cover game. This axiom ensures that symmetric vertices are allocated equal numbers of surveillance cameras.

Transfer axiom: for any v, w ∈ SG n such that v ∨ w ∈ SG n, ϕ(v) + ϕ(w) = ϕ(v ∧ w) + ϕ(v ∨ w). This axiom implies that when winning coalitions are added, changes in the solution of the game depend only on the added coalitions. This interpretation of the axiom can be found in [10]. If, for instance, a new road appeared in the transport network or, vice versa, a road has been closed, changes in the distribution of cameras will depend solely on the respective changes in the graph topology, but not on any other factors.

4 Conclusions

The article is an overview of the main results from [13].

Games on graphs have become a popular field in game theory because the solution of applied problems requires the analysis of transport, communication, or computer networks. As the society and social interactions develop, this field is moving even further into the foreground. The questions of centrality and significance of objects in a network structure come up.

Relying on the graph theory and methods of the cooperative game theory, a graph decomposition technique for Shapley-Shubik index estimation was suggested. This procedure permits representing the characteristic function of the original game in the form of a linear combination of simpler characteristic functions. Using this approach, the Shapley-Shubik index was calculated in the cooperative vertex cover game for a transport network and some classes of graphs.

The cooperative game in this paper depends on vertex covers of the graph. Since there exist also other covers of a graph, such as the edge cover, it is interesting to consider the corresponding simple games, too. If the covers are interrelated, is there also a relationship between the respective simple games?

The usual procedure in mathematical models of resource allocation is that a functional is composed to be then optimized. One of the properties of the solution is that the composed functional reaches the required value. The cooperative game theory has a different approach to resource allocation. The optimal distribution fulfils several axioms, these axioms having an applied interpretation.

Where a graph has several minimum vertex covers, a measure of centrality can be composed based only on minimum vertex covers.