Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Network games is a new and important part of modern game theory. Networks illustrate the interaction of both individuals and groups. For the first time in the literature, a non-cooperative form of pairwise interaction in a network was considered in [3] meaning direct interactions between network neighbors. Finding an equilibrium in online gaming as an example of a Designer–Adversary game was described in [4]. Pairwise interaction was exposed in [1] on the example of the dissemination of information and misinformation in social networks. The efficiency and stability of networks depending on external factors such as marginal costs were examined in [6]. An approach for finding optimal behavior in multistage games was considered in [9]. Cooperation in network games and a model of interaction between coalitions were considered in [5].

When cooperative behavior is investigated, it is important that players follow a cooperative agreement during the whole game. If a solution of the cooperative game is time-consistent, players have no reason to deviate from the accepted agreement. An imputation distribution procedure (IDP) which is a payment scheme that provides the implementation of the solution was introduced in [8] to prevent players from deviating from the cooperative agreement. The conditions for the time consistency of the core for two-stage games with pairwise interactions were established in [2]. The dynamic properties of cooperative solutions in multicriteria games were considered in [7]. In this paper, we provide analytic expressions for characteristic functions in a two-stage game with pairwise interactions. Further, similar to [11], we provide conditions for the time consistency of the Shapley value in this game. Moreover we simplify the formula of the Shapley value for a network of a special type—a star.

2 Description of the Model

Let N be a finite set of players who make decisions in two stages, \(|N|=n\geqslant 2\). At the first stage z 1 each player i ∈ N chooses his behavior \(b_i^1=(b_{i1}^1,\ldots ,b_{in}^1)\)—a profile of offers to establish connections with other players:

$$\displaystyle \begin{aligned} b_{ij}^1 = \left\{ \begin{array}{lll} 1, && \mbox{if } j\in M_i, \\ {} 0, && \mbox{otherwise}, \end{array} \right. {} \end{aligned}$$

with

$$\displaystyle \begin{aligned} \sum_{j\in N} b_{ij}^1 \leqslant a_i. {} \end{aligned}$$

Here M i ⊆ N ∖{i} is a given set of players whom player i can offer connections, \(b^1_{ii}=0\) for i ∈ N; a i ∈{0, …, n − 1} represents the maximum number of connections for player i. If M i = N ∖{i}, player i can offer a connection to any player; in particular, if a i = n − 1, player i can have any number of connections. The result of the first stage is a network \(g(b_1^1 , \ldots , b_n^1)\) consisting of links (connections) ij such that \(b_{ij}^1 = b_{ji}^1 =1\). For brevity, denote \(g(b_1^1 , \ldots , b_n^1)\) by g. Define the neighbors of player i in network g as elements of the set N i(g) = {j ∈ N ∖{i} : ij ∈ g} or simply N i. After the network formation stage z 1, players proceed to the second stage z 2.

At second stage z 2(g) which depends upon a network chosen at the first stage, network neighbors play pairwise simultaneous bimatrix games {γ ij}. Namely, let i ∈ N, j ∈ N i, then at the second stage, player i plays with his neighbor j a bimatrix game γ ij with non-negative payoff matrices \(A_{ij}=[a^{ij}_{p\ell }]_{p=1,\ldots ,m;\;\ell =1,\ldots ,k}\) and \(B_{ij}=[b^{ij}_{p\ell }]_{p=1,\ldots ,m;\;\ell =1,\ldots ,k}\) for players i and j, respectively.

After receiving payoffs in these bimatrix games, the game ends. In other words, we have a two-stage game Γ which is a special case of a multistage non-zero-sum game. Adapting the definition of a strategy to this case, a strategy of player i ∈ N will be a rule which assigns a set of his neighbors at first stage \(b_i^1\), and a behavior \(b_i^2\) in each of the bimatrix games at the second stage of the game taking into account a network formed at the first stage. Denote the strategy of player i ∈ N in two-stage game Γ by \(u_i=(b_i^1, b_i^2)\). Let (z 1, z 2) be a trajectory realized under the strategy profile u = (u 1(⋅), …, u n(⋅)) in Γ. Define the payoff of player i as h i(z 2) which is the sum of player i’s payoffs in all bimatrix games with his neighbors when \(b_i^2\), \(b_j^2\), j ∈ N i are chosen. Then player i’s payoff function in Γ starting at z 1 is defined as K i(z 1;u i(⋅), …, u n(⋅)) = h i(z 2).

The rest of the paper will be devoted to a cooperative version of the two-stage game Γ.

2.1 Cooperation at the Second Stage of the Game

A game \(\varGamma _{z_2}\) denoting a subgame of game Γ which starts at the second stage z 2 can be considered in cooperative form. In this case, we define characteristic function v(z 2;S) for any subset (coalition) S ⊂ N as the maxmin value of a two-person zero-sum game between coalition S and its complement N ∖ S constructed with the use of game \(\varGamma _{z_2}\). The superadditivity of the characteristic function follows from its definition. Denote the maxmin value of player i (j) in game γ ij with his neighbor j (i) as

$$\displaystyle \begin{aligned} \begin{array}{rcl} {} w_{ij} &\displaystyle =&\displaystyle \max_{p} \min_{\ell}\; a^{ij}_{p\ell},\quad p=1,\ldots,m,\; \ell=1,\ldots,k,\\ {} {} w_{ji} &\displaystyle =&\displaystyle \max_{\ell} \min_{p}\; b^{ji}_{p\ell},\quad p=1,\ldots,m,\; \ell=1,\ldots,k. \end{array} \end{aligned} $$

Following [2], for any S ⊆ N, the characteristic function v(z 2;S) is given by:

$$\displaystyle \begin{aligned} v(z_2;S) = \left\{ \begin{array}{lll} \displaystyle\frac{1}{2}\sum_{i \in N}\sum_{j\in N_i} \max\limits_{p,\ell} (a^{ij}_{p\ell} + b^{ji}_{p\ell}),&& S=N,\\[1.2pc] \displaystyle\frac{1}{2}\sum_{i \in S}\sum_{j\in N_i\cap S} \max\limits_{p,\ell} (a^{ij}_{p\ell} + b^{ji}_{p\ell}) + \sum_{i\in S}\sum_{k\in N_i\setminus S} w_{ik},&& S\subset N,\quad |S|>2,\\[1.2pc] \displaystyle\max\limits_{p,\ell} (a^{ij}_{p\ell} + b^{ji}_{p\ell}) + \sum_{r\in N_i\setminus \{j\}} w_{ir} + \sum_{q\in N_j \setminus \{i\}} w_{jq},&& S=\{i,j\},\\[1.2pc] \displaystyle\sum_{j \in N_i} w_{ij},&& S=\{i\},\\[1.2pc] 0,&& S=\varnothing. \end{array} \right. \end{aligned} $$
(2.1)

2.2 Cooperation at Both Stages of the Game

Consider a cooperative form of two-stage game Γ. Suppose that all players choose strategies \(\bar {u}=(\bar {u}_1,\ldots , \bar {u}_n)\) which maximize their joint payoff in game Γ, i.e.,

$$\displaystyle \begin{aligned}\sum_{i\in N} K_i(z_1;\bar{u}_1,\ldots, \bar{u}_n)=\max\limits_{u} \sum_{i\in N} K_i(z_1;u_1,\ldots, u_n)\end{aligned}$$

The strategy profile \(\bar {u}=(\bar {u}_1,\ldots , \bar {u}_n)\) is called the cooperative strategy profile, and the corresponding trajectory \((\bar {z}_1, \bar {z}_2)\) is the cooperative trajectory.

As before for coalition S ⊆ N, we define characteristic function \(v(\bar {z}_1; S)\) as the maxmin value of a two-person two-stage zero-sum game between coalition S and its complement, where the payoff of S is the sum of players’ payoffs from S, and the strategy of S is an element of the Cartesian product of sets of players’ strategies belonging to S. Since players’ payoffs are non-negative, for player N ∖ S, the best behavior to follow is to have no connections with S. Hence we get

$$\displaystyle \begin{aligned} v(\bar{z}_1; S)= \left\{ \begin{array}{lll} v(\bar{z}_2; N),&& S=N,\\ {} \displaystyle\frac{1}{2} \sum_{i \in S}\sum_{j\in N_i\cap S} v(\bar{z}_1; \{i,j\}),&& S\subset N,\; |S|>2,\\ {} \max\limits_{p,\ell}(a_{p\ell}^{ij}+b_{p\ell}^{ji}),&& S= \{i,j\},\\ {} 0,&& |S|=1,\;\text{or}\; S=\varnothing. \end{array} \right. \end{aligned} $$
(2.2)

2.3 The Shapley Value and Time Consistency

Given a characteristic function \(v(\bar {z}_t;\cdot )\), t = 1, 2, we define an imputation as a vector \(\xi [v(\bar {z}_t)] = (\xi _1[v(\bar {z}_t)], \ldots , \xi _n[v(\bar {z}_t)])\) which is (i) efficient, i.e., \(\sum _{i\in N} \xi _i[v(\bar {z}_t)] = v(\bar {z}_t;N)\) and (ii) individually rational, i.e., \(\xi _i[v(\bar {z}_t)]\geqslant v(\bar {z}_t;\{i\})\) for all i ∈ N. Denote the set of all imputations (an imputation set) in game Γ by \(I(v(\bar {z}_t))\). As an imputation we consider the Shapley value [12] denoted by \(\varphi [v(\bar {z}_t)]= (\varphi _1[v(\bar {z}_t)], \ldots , \varphi _n[v(\bar {z}_t)])\) where

$$\displaystyle \begin{aligned} \varphi_i [v(\bar{z}_t)] = \sum_{S \subseteq N, i \in S} \frac{(|S| - 1)!(n-|S|)!}{n!}[v(\bar{z}_t;S) - v(\bar{z}_t;S\setminus \{i\})],\quad i\in N. {} \end{aligned} $$
(2.3)

Before the start of game Γ, players agree on choosing cooperative trajectory (\(\bar {z}_1, \bar {z}_2\)), i.e., the trajectory that yields the maximum joint payoff \(v(\bar {z}_1;N)\), and we suppose that players allocate this payoff according to the Shapley value. This means that in Γ each player i ∈ N expects his payoff to be equal to \(\varphi _i[v(\bar {z}_1)]\). If players recalculate the Shapley value after the network formation stage (at the second stage), it turns out that the recalculated Shapley value \(\varphi [v(\bar {z}_2)]\) differs from the previous one. This may lead to a violation of the cooperative agreement because some players may refuse to use their cooperative strategies. We say that the Shapley value as an allocation in the two-stage game is time consistent if \(\varphi [v(\bar {z}_1)]=\varphi [v(\bar {z}_2)]\) (as players do not receive payoffs at the network formation stage), otherwise we call the Shapley value time inconsistent. In the former case, players follow the cooperative agreement not expecting that someone violate it. In the latter case, to prevent players from violating the cooperative agreement, we use an imputation distribution procedure (IDP) \(\beta =\{\beta _i^1,\beta _i^2\}_{i \in N}\) (first introduced in [8]) for the Shapley value \(\varphi [v(\bar {z}_1)]\) which decomposes it over two stages of the game Γ: \(\varphi _i[v(\bar {z}_1)] = \beta _i^1+\beta _i^2\) for each i ∈ N. Here \(\beta _i^1\) can be interpreted as a stage payment to player i at the network formation stage, and \(\beta _i^2\) is his payment at the second stage of the game under the cooperative agreement. We say that the IDP β of the Shapley value \(\varphi [v(\bar {z}_1)]\) is a time-consistent IDP [10, 11] when it is given by:

$$\displaystyle \begin{aligned} \beta_i^1 = \varphi_i[v(\bar{z}_1)] - \varphi_i[v(\bar{z}_2)],\qquad \beta_i^2=\varphi_i[v(\bar{z}_2)], \qquad i \in N. \end{aligned} $$
(2.4)

Introducing the time-consistent IDP β (2.4) of the Shapley value \(\varphi [v(\bar {z}_1)]\), players can be sure that no one violates the cooperative agreement, hence it will be realized in the game and player i ∈ N gets \(\varphi _i[v(\bar {z}_1)]\) as his cooperative payoff.

3 The Shapley Value for a Star

Since the calculation of the Shapley value \(\varphi [v(\bar {z}_t)]\), t = 1, 2, is a difficult task for a large number of players in an arbitrary network, we simplify formula (2.3) for a network of a special type—a star. Within this section we suppose the following. Let M i = N ∖{i} for i ∈ N and a 1 = n − 1, a i = 1, i ≠ 1. Further let maxj ∈ N w ij = w i1. Then in order to maximize the joint payoff, players should choose the following behaviors at the first stage of the game: \(b^1_1=(0, 1, \ldots , 1)\) for player 1, and \(b^1_i=(1,0, \ldots , 0)\) for player i ≠ 1. These behaviors form a star-network at this stage (see Fig. 2.1). In the star-network, |N 1| = n − 1 and |N i| = 1, i ≠ 1.

Fig. 2.1
figure 1

A star with n players

Full size image

For a star-network, the characteristic function is calculated using a specific structure of the network. The network has central symmetry which suggests that formula (2.3) can be simplified. Let \(m_{ij}= \max _{p,\ell } (a^{ij}_{p\ell } + b^{ji}_{p\ell })\). Substituting the adopted notation, as well as (2.1), (2.2), into (2.3), we obtain the following expression for the components of the Shapley value:

$$\displaystyle \begin{aligned} \varphi_i[v(\bar{z}_t)]= \left\{ \begin{array}{lll} \displaystyle\frac{1}{2}\left[v(\bar{z}_t;\{1\}) + \sum_{j\neq 1}\left(m_{1j}-v(\bar{z}_t; \{j\})\right)\right],&& i=1,\\ \displaystyle\frac{1}{2}\left[m_{1i} + v(\bar{z}_t; \{i\})-w_{1i}\right],&& i \neq 1. \end{array} \right. \end{aligned} $$
(2.5)

3.1 Two Examples

Two examples below demonstrate that the Shapley value being an allocation in a cooperative two-stage game with pairwise interactions can be both time consistent and time inconsistent. The first example shows the time consistency of the Shapley value.

Example 1 (Prisoner’s Dilemma)

Consider the case, when n players play the same game γ with their neighbors, i.e., A ij = A, B ij = B for all i ∈ N, j ∈ N i where

$$\displaystyle \begin{aligned}A = B^{\mathrm{T}} = \begin{pmatrix} b &&& 0 \\ a+b &&& a \end{pmatrix}, \quad 0<a<b. \end{aligned}$$

To find the Shapley value \(\varphi [v(\bar {z}_2)]\), we first determine characteristic function \(v(\bar {z}_2;S)\) for all S ⊆ N. Following (2.1), we obtain

$$\displaystyle \begin{aligned} v(\bar{z}_2;S)=\left\{ \begin{array}{lll} 2b(n-1),&& S=N,\\ 2b(|S|-1)+(n-|S|)a,&& S \subset N,\; 1 \in S,\\ |S|a,&& S \subset N,\; 1 \notin S,\\ 0,&& S=\varnothing. \end{array} \right. \end{aligned}$$

Using the formula for the Shapley value (2.5) adapted to a star and noting that the Shapley value is an efficient allocation satisfying the property of symmetry and that m 1j = 2b for any j ∈ N 1, we obtain

$$\displaystyle \begin{aligned} \begin{array}{rcl} \varphi_1[v(\bar{z}_2)]&\displaystyle =&\displaystyle \frac{1}{2}\left[(n-1)a + (n-1)(2b-a)\right]=b(n-1),\\ \varphi_i[v(\bar{z}_2)]&\displaystyle =&\displaystyle \frac{v(\bar{z}_2;N)-\varphi_1[v(\bar{z}_2)]}{n-1}=b,\quad i\neq 1. \end{array} \end{aligned} $$

Similarly, to find the Shapley value \(\varphi [v(\bar {z}_1)]\), we determine characteristic function \(v(\bar {z}_1;S)\) for all S ⊆ N. Following (2.2), we have

$$\displaystyle \begin{aligned} v(\bar{z}_1;S)=\left\{ \begin{array}{lll} 2b(n-1),&& S=N,\\ 2b(|S|-1),&& S \subset N,\; 1 \in S,\\ 0,&& S \subset N,\; 1 \notin S\quad \text{or}\quad S=\varnothing. \end{array} \right. \end{aligned}$$

Again, using the formula for the Shapley value (2.5) adapted to a star, the Shapley value \(\varphi [v(\bar {z}_1)]\) is given by

$$\displaystyle \begin{aligned} \begin{array}{rcl} \varphi_1[v(\bar{z}_1)]&\displaystyle =&\displaystyle \frac{1}{2}\left[2b(n-1)\right]=b(n-1),\\ \varphi_i[v(\bar{z}_1)]&\displaystyle =&\displaystyle \frac{v(\bar{z}_1;N)-\varphi_1[v(\bar{z}_1)]}{n-1}=b,\quad i\neq 1. \end{array} \end{aligned} $$

Comparing \(\varphi [v(\bar {z}_1)]\) and \(\varphi [v(\bar {z}_2)]\), we note they coincide and hence the Shapley value is time consistent.

In the next example we demonstrate the time inconsistency of the Shapley value.

Example 2

Consider a numerical example with N = {1, 2, 3, 4} in which players form a star-network under a cooperative agreement (see Fig. 2.2). Let simultaneous bimatrix games γ 12, γ 13, and γ 14 be defined by means of the following payoff matrices of players:

$$\displaystyle \begin{aligned} \begin{array}{rcl} (A_{12},B_{12})&\displaystyle =&\displaystyle \begin{pmatrix} (2,2) &\displaystyle (3,0) \\ (5,1) &\displaystyle (1,2) \end{pmatrix},\qquad (A_{13},B_{13})= \begin{pmatrix} (3,1) &\displaystyle (4,2) \\ (6,2) &\displaystyle (2,3) \end{pmatrix},\\ (A_{14},B_{14})&\displaystyle =&\displaystyle \begin{pmatrix} (1,3) &\displaystyle (3,2) \\ (6,6) &\displaystyle (4,1) \end{pmatrix}. \end{array} \end{aligned} $$
Fig. 2.2
figure 2

A star with four players

Full size image

To compute the Shapley values \(\varphi [v(\bar {z}_1)]\) and \(\varphi [v(\bar {z}_2)]\), we use the corresponding formulas (2.1), (2.2) for characteristic functions \(v(\bar {z}_2;\cdot )\) and \(v(\bar {z}_1;\cdot )\), respectively, and the simplified formula (2.5). Hence we get

$$\displaystyle \begin{aligned} \begin{array}{lllll} w_{12}=2,&& w_{13}=3,&& w_{14}=4,\\ w_{21}=1,&& w_{31}=2,&& w_{41}=3,\\ m_{12}=6,&& m_{13}=8,&& m_{14}=12,\\ \end{array} \end{aligned}$$

and therefore

$$\displaystyle \begin{aligned} \begin{array}{lllllll} v(\bar{z}_2;\{1\})=9,&& v(\bar{z}_2;\{2\})=1,&& v(\bar{z}_2;\{3\})=2,&& v(\bar{z}_2;\{4\})=3,\\ v(\bar{z}_1;\{1\})=0,&& v(\bar{z}_1;\{2\})=0,&& v(\bar{z}_1;\{3\})=0,&& v(\bar{z}_1;\{4\})=0,\\ v(\bar{z}_1;N)=26,&& v(\bar{z}_2;N)=26.&&&&\\ \end{array} \end{aligned}$$

Thus the Shapley values are given by

$$\displaystyle \begin{aligned} \varphi[v(\bar{z}_1)]=(13,3,4,6),\qquad \varphi[v(\bar{z}_2)]=(29/2,5/2,7/2,11/2). \end{aligned}$$

We observe that the Shapley value \(\varphi [v(\bar {z}_1)]\) in the two-stage game differs from the Shapley value \(\varphi [v(\bar {z}_2)]\) in the one-stage game starting at the second stage. This means the time inconsistency of the Shapley value. Since \(\varphi _2[v(\bar {z}_2)] = 5/2 < \varphi _2[v(\bar {z}_1)] = 3\), player 2 can break the cooperative agreement as his payoff can get less (here we recall that players do not receive payoffs at the network formation stage). Similar holds for player 3: \(\varphi _3[v(\bar {z}_2)] = 7/2 < \varphi _3[v(\bar {z}_1)] = 4\) and player 4: \(\varphi _4[v(\bar {z}_2)] = 11/2 < \varphi _4[v(\bar {z}_1)] = 6\). However introducing the time-consistent IDP of the Shapley value \(\varphi [v(\bar {z}_1)]\) over two stages determined by formula (2.4), we obtain

$$\displaystyle \begin{aligned}\begin{array}{lllllll} \beta_1^1 = -3/2,&& \beta_2^1 = 1/2,&& \beta_3^1 = 1/2,&& \beta_4^1 = 1/2,\\ \beta_1^2 = 29/2,&& \beta_2^2 = 5/2,&& \beta_3^2 = 7/2,&& \beta_4^2 = 11/2,\\ \end{array} \end{aligned}$$

and therefore cooperation will be sustainable. Thus receiving \(\beta _i^1\) at the first stage and \(\beta _i^2\) at the second stage, player i ∈ N will get \(\varphi _i[v(\bar {z}_1)]\) in two stages which is exactly player i’s cooperative payoff prescribed by the Shapley value \(\varphi [v(\bar {z}_1)]\).

4 Conclusion

In this paper, we studied a two-stage network game for a special type of pairwise interactions between players. This gave us the possibility of getting analytic expressions for characteristic functions in this game. As a solution of the game under consideration, we took the Shapley value and found its analytic form for a star-network. The special structure of the network game gives us the possibility of the implementation of other cooperative solutions what enriches the scope of application. The time inconsistency of the Shapley value in the two-stage game with pairwise interactions was demonstrated, and time-consistent IDP-based payoffs were introduced to deal with time inconsistency.