Time consistency of the interval Shapley-like value in dynamic games

Abstract

The paper focuses on the problem of time consistency of an interval Shapley-like value in cooperative interval dynamic games. This problem has not been investigated in the game theory literature for the considered class of dynamic games. It is proved that the interval Shapley-like value is time inconsistent, and to satisfy the time consistency condition for the interval value, it is necessary to introduce a new control variable, so-called imputation distribution procedure. The imputation distribution procedure is proposed in an explicit form.

Keywords

Dynamic games cooperative interval games interval Shapley-like value time consistency

1 Introduction

In recent papers on cooperative games it is usually supposed that the characteristic function, which shows the worth of any coalition, is given. But this approach is difficult to introduce in dynamic and differential games since for the understanding evolution of the characteristic function from one subgame to another it is necessary to understand the mechanism how the characteristic function can be calculated in each subgame. Because of that in our setting we suppose that the characteristic function is defined in a classical way for each coalition in the sense of von Neumann and Morgenstern [15] –as value of a zero-sum game between the coalition (player 1) and its complement (player 2), where the payoff to the coalition is the sum of players’ payoffs from it. This approach was used in many papers on cooperative differential games.

When cooperation in dynamic and differential games is considered, the important problem of time consistency of the solution concept arises. This problem was for the first time mentioned in the paper of Petrosyan [16]. In the mentioned paper and also in later research, authors proposed [8, 17] a special payment algorithm for players to sustain time consistency of the given cooperative solution. In this paper, we try to use an approach based only on ideas formulated in [17 –19] to dynamic cooperative games with interval payoffs. An interval payoff means that one cannot evaluate a precise value for the worth obtainable by each coalition, but instead knows a lower bound and an upper bound for each coalition value.

Branzei et al. [4, 5] provided the interval game-theoretic model to handle bankruptcy situations with interval claims and considered two Shapley-like values for the class of games. Alparslan Gök et al. [1] studied selections of cooperative interval games which are classical cooperative games. Alparslan Gök et al. [2] then characterized the interval Shapley value with the properties of additivity, efficiency, symmetry and dummy player, which are straightforward generalizations of the corresponding properties in the classical cooperative game theory. It is worth mentioning that the proposed interval Shapley value is defined on the strictly limited interval games, namely, size monotonic. From that, many axiomatization approach of the interval Shapley value have been developed [3 , 10]. Meng [11] extended recently the interval Shapley values to the so called type-2 interval games, where the player participation levels and the coalition values are both interval numbers. Methods of interval arithmetic and analysis (cf. Moore [14]) have played a key role for the models of games based on interval uncertainty. By using Moore’s subtraction operator and an introduced total order with respect to the set of closed intervals, Han et al. [6] studied the new notions of interval cores and Shapley-like values. We aim at investigating time consistency of one of such interval Shapley-like values in cooperative interval dynamic games. Although the considered interval value is not efficient, it is defined for all interval games. The theory of interval cooperative values, for example, the interval Shapley value and its extension to the case of games with a coalition structure (the Owen value), is developed in [12, 13], in which authors study a fuzzy case.

The paper has the following structure. In Section 2 we define an interval dynamic game and construct a cooperative game based on the given interval dynamic game. Here we define mathematical operations on closed and bounded intervals using interval calculus. In this section we also propose a way of constructing the characteristic function—the function of coalitions—in the cooperative interval dynamic game and consider the interval Shapley-like value as a cooperative solution concept. The time consistency problem of the cooperative solution concept in cooperative interval dynamic games is studied in Section 3. A numerical example, which illustrates our theoretical results, is considered in Section 4 and this section concludes the paper.

2 Cooperation in interval dynamic games

2.1 Operations on closed intervals

At first, we introduce mathematical operations on closed intervals which we will use in the paper [6]. Let $I (ℝ)$ be the set of all closed and bounded intervals on $ℝ$ . For any two intervals $I = [\underline{I}, \bar{I}], J = [\underline{J}, \bar{J}] \in I (ℝ)$ and $α \in ℝ$ define addition, subtraction and multiplication operators in the following way:

$I \oplus J = [\underline{I} + \underline{J}, \bar{I} + \bar{J}]$ ,

$I ⊖ J = [\underline{I} - \bar{J}, \bar{I} - \underline{J}]$ ,

$α I = {\begin{matrix} [α \underline{I}, α \bar{I}], & if α ⩾ 0, \\ [α \bar{I}, α \underline{I}], & if α < 0 . \end{matrix}$

For intervals $I_{1} = [{\underline{I}}_{1}, {\bar{I}}_{1}], \dots, I_{n} = [{\underline{I}}_{n}, {\bar{I}}_{n}] \in I (ℝ)$ define the addition operator in the similar way: $\sum_{j \in N} I_{j} : = I_{1} \oplus \dots \oplus I_{n} = [\sum_{j \in N} {\underline{I}}_{j}, \sum_{j \in N} {\bar{I}}_{j}] .$

Define now operators of the order. Let |I| be the length of interval I, i.e., $| I | = \bar{I} - \underline{I}$ . We say that

I is weakly better then J (I ≽ J or J ≼ I) if and only if $\underline{I} ⩾ \underline{J}$ and $\bar{I} ⩾ \bar{J}$ ,

I is better then J (I ≻ J or J ≺ I) if and only if I ≽ J and I ≠ J,

I is weakly superior to J (I ≿ J or J ≾ I) if and only if $\frac{\underline{I} + \bar{I}}{2} ⩾ \frac{\underline{J} + \bar{J}}{2}$ ,

I and J are related by an indifference relationship (I ∼ J) if and only if $\frac{\underline{I} + \bar{I}}{2} = \frac{\underline{J} + \bar{J}}{2}$ ,

I is superior to J (I ≻ J or J ≺ I) if and only if $\frac{\underline{I} + \bar{I}}{2} > \frac{\underline{J} + \bar{J}}{2}$ .

2.2 Interval dynamic game with perfect information

In this section, we consider more simple class of dynamic games, so-called finite multistage games with perfect information [9]. Let X be a finite set and F be a mapping that assigns a subset F_x ⊂ X to each element x ∈ X. The case F_x =∅ is also possible. A pair G = (X, F) is called a graph. Each element x ∈ X is a node of the graph, and a pair (x, y), where y ∈ F_x, is an arc. We suppose that the graph is a tree, and x₀ is its root.

Let N be a finite set of players with |N| = n. Define an interval multistage game with perfect information as follows.

Definition 1. We say that we have an n-person interval multistage game Γ with perfect information on graph tree G = (X, F) if:

The set of nodes X is split up into n + 1 disjoint sets (player partition) X₁, …, X_n, X_n+1, i.e., $\cup_{i = 1}^{n + 1} X_{i} = X$ , X_i∩ X_j = ∅, i ≠ j, and F_x =∅ for all x ∈ X_n+1. Here set X_i consists of nodes in which player i ∈ N makes a move, and set X_n+1 is the set of terminal nodes,

For all x ∈ X, n closed intervals $[{\underline{h}}_{1} (x), {\bar{h}}_{1} (x)]$ , $\dots, [{\underline{h}}_{n} (x), {\bar{h}}_{n} (x)]$ $\in I (ℝ)$ are given. Here interval $h_{i} (x) = [{\underline{h}}_{i} (x), {\bar{h}}_{i} (x)]$ is the interval of possible payoffs to player i ∈ N in node x ∈ X.

The game develops as follows. Suppose the root x₀ ∈ X_{i
₁}, then in x₀ player i₁ makes a move and chooses a node x₁ ∈ F_{x
₀}. If x₁ ∈ X_{i
₂}, then in x₁ player i₂ makes a move and chooses a node x₂ ∈ F_{x
₁} etc. Thus, if on k-th step a node x_k-1 ∈ X_{i
_k}, then player i_k makes a move and chooses a node from set F_{x
_k-1}. The game ends once a terminal node x_ℓ ∈ X_n+1 is reached, i.e., if F_{x
_ℓ} =∅.

Each player i, who makes a move in node x ∈ X_i, knows the node x and can reconstruct all previous nodes since graph G is a tree. Therefore, the players have perfect information.

Define a payoff to player i ∈ N in game Γ. Let (x₀, x₁, …, x_ℓ) such that x_k = F_{x
_k-1}, k = 1, … , ℓ, and x_ℓ ∈ X_n+1 be a trajectory (or a path) on graph tree G starting in the root x₀ and ending in the terminal node x_ℓ. The payoff to player i in the game is defined as $\begin{matrix} H_{i} & (x_{0}, x_{1}, \dots, x_{ℓ}) \\ = [{\underline{H}}_{i} (x_{0}, x_{1}, \dots, x_{ℓ}), {\bar{H}}_{i} (x_{0}, x_{1}, \dots, x_{ℓ})] \\ = h_{i} (x_{0}) \oplus h_{i} (x_{1}) \oplus \dots \oplus h_{i} (x_{ℓ}) . \end{matrix}$

Definition 2. A strategy u_i of player i ∈ N is a mapping that uniquely assigns a node y ∈ F_x to each nodex ∈ X_i.

The set of all possible strategies of player i we denote as U_i. An n-tuple u = (u₁, …, u_n), where u_i ∈ U_i, is a strategy profile in game Γ, and Cartesian product $U = \prod_{i = 1}^{n} U_{i}$ is a set of all strategy profiles.

Each strategy profile uniquely defines a game trajectory and, therefore, players’ payoffs. Suppose we have a strategy profile u = (u₁, …, u_n) which defines a trajectory (x₀, x₁, …, x_ℓ). One can introduce a payoff function $K_{i} = [{\underline{K}}_{i}, {\bar{K}}_{i}] \in I (ℝ)$ of player i in the following way: K_i (u₁, …, u_n) = H_i (x₀, x₁, …, x_ℓ), i ∈ N.

2.3 Cooperative interval dynamic game with perfect information

In papers on cooperative dynamic games with completely certain, non-interval payoffs it is supposed that before the game starts, players choose a strategy profile and the corresponding trajectory maximizing the sum of players’ payoffs. In cooperative dynamic games with interval payoffs, we cannot exactly find the maximal value that is why one needs to specify it. Similar to this approach, we suppose that before the game starts, players choose a strategy profile $(u_{1}^{*}, \dots, u_{n}^{*})$ and corresponding trajectory $(x_{0}^{*}, x_{1}^{*}, \dots, x_{ℓ}^{*})$ , $x_{0}^{*} = x_{0}$ , maximizing the sum

$\begin{matrix} max_{x_{0}, x_{1}, \dots, x_{ℓ}} & \sum_{i \in N} \sum_{k = 0}^{ℓ} \frac{{\underline{h}}_{i} (x_{k}) + {\bar{h}}_{i} (x_{k})}{2} \\ = & \sum_{i \in N} \sum_{k = 0}^{ℓ} \frac{{\underline{h}}_{i} (x_{k}^{*}) + {\bar{h}}_{i} (x_{k}^{*})}{2} . \end{matrix}$ (1)

The strategy profile $(u_{1}^{*}, \dots, u_{n}^{*})$ we call the optimal strategy profile, and the corresponding trajectory $(x_{0}^{*}, x_{1}^{*}, \dots, x_{ℓ}^{*})$ is the cooperative (median) trajectory. It is obvious that the cooperative trajectory may not be unique. If it is the case, we fix one optimal strategy profile $(u_{1}^{*}, \dots, u_{n}^{*})$ from the set of all optimal strategy profiles and the corresponding cooperative trajectory.

Any subset S of set of players N we call a coalition. The essential feature of any cooperative game is a characteristic function that shows the “worth” of any coalition.

Define a cooperative interval dynamic game.

Definition 3. We say that we have an n-person cooperative interval multistage game Γ_C = (N, v) with perfect information on graph tree G = (X, F) if characteristic function $v : 2^{N} \mapsto I (ℝ)$ is specified by game Γ with v (∅) = [0, 0].

Suppose that characteristic function v has already specified. There are different approaches of defining the characteristic function, and one of the most used definition of the characteristic function for cooperative interval dynamic games we propose below in Subsection 2.4.

The set of all cooperative interval multistage games Γ_C with player set N we denoted by IG^N.

A solution of the cooperative interval dynamic game is an interval value, a function $Ψ : {IG}^{N} \mapsto I (ℝ)^{n}$ , satisfying condition ∑_i∈NΨ_i (v) ∼ v (N). The i-th component of the interval value represents the interval payoff to player i ∈ N. The set of all interval values in game Γ_C we denote by C (v).

A solution concept is a rule that assign a subset M (v) ⊂ C (v) to each cooperative interval dynamic game Γ_C. Consider an interval value which is based on the Shapley value: the interval Shapley-like value Φ (v) = (Φ₁ (v) , …, Φ_n (v)), where for i ∈ N,

$\begin{matrix} Φ_{i} (v) = & \sum_{S \subseteq N, i \in S} \frac{(| N | - | S |)! (| S | - 1)!}{| N |!} \\ \times [v (S) ⊖ v (S \ {i})] . \end{matrix}$ (2)

Remark 1. The “original” interval Shapley value was introduced in Alparslan Gök et al. for a class of size monotonic interval games [2]. Under this strong restriction, another subtraction operator was used for the interval value. It was proved that the interval Shapley value is efficient. In the present paper, we use the interval value that was introduced and characterized in Han et al. for a general class of interval games (not necessarily size monotonic) [6]. This value was called the interval Shapley-like value since it is based on the same idea as the Shapley value for a classical cooperative (non-interval) theory. This value uses the Moore subtraction operator defined above in Subsection 2.1. It is worth noting that the interval value Φ (v) satisfies the indifference efficiency property, i.e., ∑_i∈NΦ_i (v) ∼ v (N), but it does not satisfy the efficiency property in general: ∑_i∈NΦ_i (v) ≠ v (N). The reason for introducing the concept of indifference efficiency for interval games is the following. For interval games, a payoff to a player is uncertain since it belongs to an interval, and only the lower and the upper bounds of the interval are specified. If we suppose that the payoff to the player is uniformly distributed in the interval, the median is its expectation. We will use median elements in Section 3 when considering time consistency of the interval value.

2.4 Characteristic function

In this section, we propose a way of construction the characteristic function $v (S) = [\underline{v} (S), \bar{v} (S)]$ for any S ⊆ N in the cooperative interval dynamic game. Let $(x_{0}^{*}, x_{1}^{*}, \dots, x_{ℓ}^{*})$ be the cooperative trajectory maximizing (1), then denote $v (N) = [\underline{v} (N), \bar{v} (N)] = \sum_{i \in N} H_{i} (x_{0}^{*}, x_{1}^{*}, \dots, x_{ℓ}^{*}) .$ (3)

It is obvious that the median of v (N) equals (1). For all non-empty coalitions S ⊂ N let $v (S) = [\underline{v} (S), \bar{v} (S)] = \sum_{i \in S} H_{i} (x_{0}^{'}, x_{1}^{'}, \dots, x_{m}^{'}),$ (4) where a trajectory $(x_{0}^{'}, x_{1}^{'}, \dots, x_{m}^{'})$ , $x_{0}^{'} = x_{0}$ corresponds to a strategy profile $u^{'} = (u_{1}^{'}, \dots, u_{n}^{'})$ which can be found from the following optimization problem: $max_{u_{i}, i \in S} min_{u_{j}, j \in N \ S} \sum_{i \in S} \frac{{\underline{K}}_{i} (u) + {\bar{K}}_{i} (u)}{2} = \sum_{i \in S} \frac{{\underline{K}}_{i} (u^{'}) + {\bar{K}}_{i} (u^{'})}{2},$ and $K_{i} (u^{'}) = [{\underline{K}}_{i} (u^{'}), {\bar{K}}_{i} (u^{'})] = H_{i} (x_{0}^{'}, \dots, x_{m}^{'})$ .

It is easy to prove that the superadditivity condition is satisfied, i.e., v (S ∪ T) ≿ v (S) + v (T) for all disjoint coalitions S and T from the set of players N.

3 Time consistency of the interval Shapley-like value

Suppose that before the game starts, players chose the interval value Ψ (v) ∈ M (v). It means that playing cooperatively and choosing strategies which maximize (), players expect each of them to get Ψ_i (v) as a payoff at the end of the game.

When the game Γ is realized along the cooperative trajectory $(x_{0}^{*}, x_{1}^{*}, \dots, x_{ℓ}^{*})$ , in each node $x_{k}^{*}$ players are involved in a new interval multistage game with perfect information $Γ^{x_{k}^{*}}$ , k = 1, … , ℓ which is a subgame of the initial game Γ starting in $x_{k}^{*}$ with player i’s payoff: $H_{i}^{x_{k}^{*}} (x_{k}^{*}, \dots, x_{ℓ}^{*}) = h_{i} (x_{k}^{*}) \oplus \dots \oplus h_{i} (x_{ℓ}^{*}),$ (5) and payoff function $K_{i}^{x_{k}^{*}} = [{\underline{K}}_{i}^{x_{k}^{*}}, {\bar{K}}_{i}^{x_{k}^{*}}]$ (restriction of a function $K_{i} = [{\underline{K}}_{i}, {\bar{K}}_{i}]$ to subgame $Γ^{x_{k}^{*}}$ ).

Note that the Bellman’s equation is fulfilled for the expression (1) and the remaining part $(x_{k}^{*}, \dots, x_{ℓ}^{*})$ of the cooperative trajectory $(x_{0}^{*}, x_{1}^{*}, \dots, x_{ℓ}^{*})$ , starting from node $x_{k}^{*}$ , maximizes the sum of players’ payoffs in subgame $Γ^{x_{k}^{*}}$ , i.e.,

$\begin{matrix} max_{x_{k}, \dots, x_{ℓ}} & \sum_{i \in N} \sum_{j = k}^{ℓ} \frac{{\underline{h}}_{i} (x_{j}) + {\bar{h}}_{i} (x_{j})}{2} \\ = & \sum_{i \in N} \sum_{j = k}^{ℓ} \frac{{\underline{h}}_{i} (x_{j}^{*}) + {\bar{h}}_{i} (x_{j}^{*})}{2} . \end{matrix}$ (6)

It means that the trajectory $(x_{k}^{*}, \dots, x_{ℓ}^{*})$ is also the cooperative trajectory in subgame $Γ^{x_{k}^{*}}$ .

Before entering the subgame $Γ^{x_{k}^{*}}$ , payoff to player i ∈ N belongs to the interval $h_{i} (x_{0}^{*}) \oplus \dots \oplus h_{i} (x_{k - 1}^{*})$ . On the other hand, in the beginning of game $Γ = Γ^{x_{0}^{*}}$ player i expects her payoff to belong to interval Ψ_i (v) according to interval value Ψ (v). Therefore, in subgame $Γ^{x_{k}^{*}}$ player i’s expected payoff $Ψ_{i} (v^{x_{k}^{*}})$ should satisfy the condition $h_{i} (x_{0}^{*}) \oplus \dots \oplus h_{i} (x_{k - 1}^{*}) \oplus Ψ_{i} (v^{x_{k}^{*}}) ~ Ψ_{i} (v),$ (7) where $v^{x_{k}^{*}}$ is the characteristic function in subgame $Γ^{x_{k}^{*}}$ , k = 1, … , ℓ defined in the same way as the characteristic function v in game $Γ = Γ^{x_{0}^{*}}$ (see formulas (3)–(4)), i.e.,

$\begin{matrix} v^{x_{k}^{*}} (N) & = & [{\underline{v}}^{x_{k}^{*}} (N), {\bar{v}}^{x_{k}^{*}} (N)] \\ = & \sum_{i \in N} H_{i}^{x_{k}^{*}} (x_{k}^{*}, \dots, x_{ℓ}^{*}), \end{matrix}$ (8) and for all S ⊂ N

$\begin{matrix} v^{x_{k}^{*}} (S) & = & [{\underline{v}}^{x_{k}^{*}} (S), {\bar{v}}^{x_{k}^{*}} (S)] \\ = & \sum_{i \in S} H_{i}^{x_{k}^{*}} (x_{k}^{″}, \dots, x_{m}^{″}), \end{matrix}$ (9) where a trajectory $(x_{k}^{″}, \dots, x_{m}^{″})$ , $x_{k}^{″} = x_{k}^{*}$ corresponds to a strategy profile $u^{″} = (u_{1}^{″},$ $\dots, u_{n}^{″})$ in subgame $Γ^{x_{k}^{*}}$ which can be found from the following optimization problem: $\begin{matrix} max_{u_{i}, i \in S} min_{u_{j}, j \in N \ S} & \sum_{i \in S} \frac{{\underline{K}}_{i}^{x_{k}^{*}} (u) + {\bar{K}}_{i}^{x_{k}^{*}} (u)}{2} \\ = & \sum_{i \in S} \frac{{\underline{K}}_{i}^{x_{k}^{*}} (u^{″}) + {\bar{K}}_{i}^{x_{k}^{*}} (u^{″})}{2}, \end{matrix}$ and $K_{i}^{x_{k}^{*}} (u^{″}) = [{\underline{K}}_{i}^{x_{k}^{*}} (u^{″}), {\bar{K}}_{i}^{x_{k}^{*}} (u^{″})] = H_{i}^{x_{k}^{*}} (x_{k}^{″}, \dots, x_{m}^{″})$ .

Here we have a question: will the interval value $Ψ (v^{x_{k}^{*}})$ in subgame $Γ^{x_{k}^{*}}$ , k = 1, … , ℓ be optimal in the same sense as the interval value Ψ (v) in game Γ, i.e., will $h_{i} (x_{0}^{*}) \oplus \dots \oplus h_{i} (x_{k - 1}^{*}) \oplus Ψ_{i} (v^{x_{k}^{*}}) \in M (v)$ if Ψ (v) ∈ M (v)? If it does not, in subgame $Γ^{x_{k}^{*}}$ players will not agree on the same solution concept as in game $Γ^{x_{0}^{*}}$ which may break cooperation at all and change the cooperative strategy profile $(u_{1}^{*}, \dots, u_{n}^{*})$ and, therefore, the cooperative trajectory $(x_{k}^{*}, \dots, x_{ℓ}^{*})$ in subgame $Γ^{x_{k}^{*}}$ .

Similar to set C (v), introduce sets $C (v^{x_{k}^{*}})$ , k = 1, … , ℓ as follows: $C (v^{x_{k}^{*}}) = {Ψ (v^{x_{k}^{*}}) \in I (ℝ)^{n} :$ $\sum_{i \in N} Ψ_{i} (v^{x_{k}^{*}}) \sim v^{x_{k}^{*}} (N)}$ , and a solution concept in subgame $Γ^{x_{k}^{*}}$ : a rule that assign a subset $M (v^{x_{k}^{*}}) \subset C (v^{x_{k}^{*}})$ to each subgame $Γ^{x_{k}^{*}}$ . If we suppose that players along the cooperative trajectory agree on the solution concept M (v), the interval value $Ψ (v^{x_{k}^{*}})$ should belong to the same solution concept as Ψ (v), i.e., $Ψ (v^{x_{k}^{*}}) \in M (v^{x_{k}^{*}})$ , k = 1, … , ℓ, and the condition (7) will be satisfied. Unfortunately, in most classes of cooperative dynamic games it is hard to find the solution concept satisfying the equality (7). To avoid this difficulty, introduce a special payment scheme at each stage of the cooperative interval game such that payments at each stage would not exceed the sum of players’ payoffs at this stage and payments at stages from k to ℓ in subgame $Γ^{x_{k}^{*}}$ , k = 1, … , ℓ would belong to the same solution concept $M (v^{x_{k}^{*}})$ as the interval value Ψ (v). Let Φ (v) = M (v), i.e., the solution concept is the interval Shapley-like value Φ (v) calculated by formula (2). For any subgame $Γ^{x_{k}^{*}}$ , k = 1, … , ℓ along the optimal trajectory $(x_{0}^{*}, x_{1}^{*}, \dots, x_{ℓ}^{*})$ calculate the interval Shapley-like value $Φ (v^{x_{k}^{*}})$ using the formula: for i ∈ N,

$\begin{matrix} Φ_{i} (v^{x_{k}^{*}}) = & \sum_{S \subseteq N, i \in S} \frac{(| N | - | S |)! (| S | - 1)!}{| N |!} \\ \times [v^{x_{k}^{*}} (S) ⊖ v^{x_{k}^{*}} (S \ {i})] . \end{matrix}$ (10)

Consider a median element φ (v) = (φ₁ (v) , …, φ_n (v)) of the interval Shapley-like value Φ (v), where $φ_{i} (v) = \frac{{\underline{Φ}}_{i} (v) + {\bar{Φ}}_{i} (v)}{2} \in Φ_{i} (v), i \in N,$ and the median element $φ (v^{x_{k}^{*}}) = (φ_{1} (v^{x_{k}^{*}}), \dots,$ $φ_{n} (v^{x_{k}^{*}}))$ , k = 1, … , ℓ of the interval Shapley-like value $Φ (v^{x_{k}^{*}})$ for each subgame $Γ^{x_{k}^{*}}$ , where $φ_{i} (v^{x_{k}^{*}}) = \frac{{\underline{Φ}}_{i} (v^{x_{k}^{*}}) + {\bar{Φ}}_{i} (v^{x_{k}^{*}})}{2} \in Φ_{i} (v^{x_{k}^{*}}), i \in N .$

Introduce an imputation distribution procedure [17].

Definition 4. A matrix β = {β_ik}, i = 1, …, n, k = 0, … , ℓ, such that $φ_{i} (v) = \sum_{k = 0}^{ℓ} β_{ik}$ (11) is called an imputation distribution procedure (IDP) of the median element φ_i (v) ∈ Φ_i (v).

IDP β has the following interpretation: β_ik is a payment to player i at stage k in game Γ (or at the first stage in subgame $Γ^{x_{k}^{*}}$ ), and $β_{i} (k) = \sum_{j = 0}^{k - 1} β_{ij}$ is a sum of player i’s payments at first k stages in game Γ.

From Equation (11) it follows that in game Γ each player i ∈ N expects her payoff to be equal to φ_i (v) ∈ Φ_i (v).

Definition 5. Imputation distribution procedure β of the median element φ_i (v) ∈ Φ_i (v) is time consistent if for all k = 1, … , ℓ and i ∈ N, $φ_{i} (v^{x_{k}^{*}}) = φ_{i} (v) - β_{i} (k) .$ (12)

Time consistency of imputation distribution procedure β means that if at each stage $x_{k}^{*}$ along the cooperative trajectory $(x_{0}^{*}, x_{1}^{*}, \dots, x_{ℓ}^{*})$ payments are chosen according to β, then in each subgame $Γ^{x_{k}^{*}}$ , k = 1, … , ℓ players will expect payments $φ (v^{x_{k}^{*}})$ which are optimal in subgame $Γ^{x_{k}^{*}}$ in the same sense as in game Γ. Therefore, for the median element φ (v) of the interval Shapley-like value Φ (v) one can define IDP β = {β_ik} as follows:

$\begin{matrix} β_{ik} & = & φ_{i} (v^{x_{k}^{*}}) - φ_{i} (v^{x_{k + 1}^{*}}), k = 0, \dots, ℓ - 1, \\ φ_{i} (v^{x_{0}^{*}}) = φ_{i} (v), \\ β_{i ℓ} & = & φ_{i} (v^{x_{ℓ}^{*}}), i = 1, \dots, n . \end{matrix}$ (13)

From Definition 1 it follows that $\begin{matrix} \sum_{k = 0}^{ℓ} β_{ik} & = & \sum_{k = 0}^{ℓ - 1} (φ_{i} (v^{x_{k}^{*}}) - φ_{i} (v^{x_{k + 1}^{*}})) + φ_{i} (v^{x_{ℓ}^{*}}) \\ = & φ_{i} (v^{x_{0}^{*}}) = φ_{i} (v) . \end{matrix}$

At the same time, $φ_{i} (v) - β_{i} (k) = φ_{i} (v^{x_{k}^{*}}) \in Φ_{i} (v^{x_{k}^{*}})$ , k = 0, … , ℓ which means time consistency of imputation distribution procedure β of the median element φ_i (v) ∈ Φ_i (v).

Remark 2. Note that the IDP, constructed by formulas (13), is time consistent in a weak sense, since we obtain the IDP only for the median element of the interval Shapley-like value. Finding an IDP for any element ξ (v) ∈ Φ (v) and fulfilling the time consistency condition for it is more difficult. We can do it only if along the cooperative trajectory $(x_{0}^{*}, x_{1}^{*}, \dots, x_{ℓ}^{*})$ there exists a sequence of elements $ξ (v^{x_{1}^{*}}), \dots, ξ (v^{x_{ℓ}^{*}})$ such that IDP β satisfies the following two conditions: $\begin{matrix} β_{i} (k) + ξ_{i} (v^{x_{k}^{*}}) = ξ_{i} (v), and \\ ξ_{i} (v^{x_{k}^{*}}) \in Φ_{i} (v^{x_{k}^{*}}) for all k = 1, \dots, ℓ and i \in N . \end{matrix}$

4 Numerical example

Consider a numerical example which illustrates theoretical results. Suppose that the set of players N = {1, 2, 3}, |N| = n = 3. The game Γ on graph tree G = (X, F) is represented in Fig. 1. Here set X = X₁ ∪ X₂ ∪ X₃ ∪ X₄ is a set of nodes {x₀, x₁, …, x₁₀}. Suppose that X₁ = {x₀}, X₂ = {x₁, x₂}, X₃ = {x₄, x₆} and X₄ = {x₃, x₅, x₇, x₈, x₉, x₁₀}. It means that player i = 1, 2, 3 makes a move in nodes from set X_i, and the game ends in nodes from set X₄. In each node n intervals are given (players’ possible payoffs). For instance, in the root x₀ payoff to player 1 belongs to the interval $h_{1} (x_{0}) = [{\underline{h}}_{1} (x_{0}), {\bar{h}}_{1} (x_{0})] = [2, 4]$ , payoff to player 2 belongs to the interval $h_{2} (x_{0}) = [{\underline{h}}_{2} (x_{0}), {\bar{h}}_{2} (x_{0})] = [0, 6]$ , payoff to player 3 belongs to the interval $h_{3} (x_{0}) = [{\underline{h}}_{3} (x_{0}), {\bar{h}}_{3} (x_{0})] = [1, 3]$ .

Using (1), one can find that the maximal value equals 46 along the trajectory (x₀, x₂, x₆, x₉). This trajectory is the cooperative trajectory. Therefore, to calculate the interval Shapley-like value along (x₀, x₂, x₆, x₉) one needs to construct the characteristic function (see (3)–(4)). In Table 1, interval values of the characteristic function $v (S) = [\underline{v} (S), \bar{v} (S)]$ are given for all coalitions S ⊆ N. Therefore, the interval Shapley-like value Φ (v) = (Φ₁ (v) , Φ₂ (v) , Φ₃ (v)), calculated by formula (2), has the form: $Φ (v) = ([- \frac{11}{3}, 33], [0, \frac{109}{3}], [- \frac{17}{3}, 32])$ .

Consider now subgame Γ^{x
₂} on the cooperative trajectory (x₀, x₂, x₆, x₉) and calculate the new interval Shapley-like value Φ (v^{x
₂}) = (Φ₁ (v^{x
₂}) , Φ₂ (v^{x
₂}) , Φ₃ (v^{x
₂})) in this subgame. Intervals of the characteristic function $v^{x_{2}} (S) = [{\underline{v}}^{x_{2}} (S), {\bar{v}}^{x_{2}} (S)]$ for all S ⊆ N are shown in Table 2, column 2 (see (8)–(9)). Therefore, we have $Φ (v^{x_{2}}) = ([- 6, 24], [4, 33], [- \frac{13}{3}, \frac{76}{3}])$ .

Now check condition (7) in node x₂. For player 1 we obtain $[2, 4] \oplus [- 6, 24] ≁ [- \frac{11}{3}, 33]$ . This fact shows that we need to use a payment scheme, IDP β, and make it time consistent. To find matrix β, we calculate the remaining interval Shapley-like values in all nodes on the cooperative trajectory (x₀, x₂, x₆, x₉): Φ (v^{x
₆}) and Φ (v^{x
₉}). In Table 2, columns 4 and 6, intervals of characteristic functions $v^{x_{6}} (S) = [{\underline{v}}^{x_{6}} (S), {\bar{v}}^{x_{6}} (S)]$ and $v^{x_{9}} (S) = [{\underline{v}}^{x_{9}} (S), {\bar{v}}^{x_{9}} (S)]$ for all S ⊆ N are represented. Using values v^{x
₆} (S) and v^{x
₉} (S), S ⊆ N, we obtain: $Φ (v^{x_{6}}) = ([- \frac{8}{3}, \frac{46}{3}], [- \frac{13}{3}, 13], [\frac{4}{3}, \frac{58}{3}])$ , Φ (v^{x
₉}) = ([3, 11] , [- 3, 5] , [1, 9]).

Now find the time-consistent imputation distribution procedure β of the median element φ_i (v) = (φ₁ (v) , φ₂ (v) , φ₃ (v)) ∈ Φ_i (v). Here we have: $φ (v) = (\frac{44}{3}, \frac{109}{6}, \frac{79}{6})$ , $φ (v^{x_{2}}) = (9, \frac{37}{2}, \frac{21}{2})$ , $φ (v^{x_{6}}) = (\frac{19}{3}, \frac{13}{3},$ $\frac{31}{3})$ , φ (v^{x
₉}) = (7, 1, 5). Therefore, according to (13), we obtain stage payments to player 1 along the cooperative trajectory: $\begin{matrix} β_{10} & = & φ_{1} (v) - φ_{1} (v^{x_{2}}) = \frac{17}{3}, \\ β_{11} & = & φ_{1} (v^{x_{2}}) - φ_{1} (v^{x_{6}}) = \frac{8}{3}, \\ β_{12} & = & φ_{1} (v^{x_{6}}) - φ_{1} (v^{x_{9}}) = - \frac{2}{3}, \\ β_{13} & = & φ_{1} (v^{x_{9}}) = 7 . \end{matrix}$

Payments to players 2 and 3 are calculated in a similar way: $β_{20} = - \frac{1}{3}$ , $β_{30} = \frac{8}{3}$ , $β_{21} = \frac{85}{6}$ , $β_{31} = \frac{1}{6}$ , $β_{22} = \frac{10}{3}$ , $β_{32} = \frac{16}{3}$ , β₂₃ = 1, β₃₃ = 5. The matrix representation of the IDP β is as follows: $β = (\begin{matrix} \frac{17}{3} & \frac{8}{3} & - \frac{2}{3} & 7 \\ - \frac{1}{3} & \frac{85}{6} & \frac{10}{3} & 1 \\ \frac{8}{3} & \frac{1}{6} & \frac{16}{3} & 5 \end{matrix}) .$

For instance, consider player 1. If we take the median element as a payoff, the IDP means that player 1 in the root x₀ should be paid $\frac{17}{3}$ , in x₂ should be paid $\frac{8}{3}$ , in x₆ should be paid (or, more specifically, should return) $- \frac{2}{3}$ , and in x₉ should be paid 7. In the whole game she gets $\frac{44}{3}$ , that is the same value that she expects to get as her entry of the median element φ (v) of the interval Shapley-like value Φ (v). Even if player 1 checks equality (12) in x₂, it will hold. In other words, what she expects to get (the median element φ₁ (v^{x
₂}) =9 of the interval Shapley-like value Φ₁ (v^{x
₂})) in subgame Γ^{x
₂} is exactly the difference $φ_{1} (v) - β_{1} (1) = φ_{1} (v) - β_{10} = \frac{44}{3} - \frac{17}{3} = 9$ . The same result is true for node x₆: what player 1 expects to get (the median element $φ_{1} (v^{x_{6}}) = \frac{19}{3}$ of the interval Shapley-like value Φ₁ (v^{x
₆})) in subgame Γ^{x
₆} is exactly the difference $φ_{1} (v) - β_{1} (2) = φ_{1} (v) - β_{10} - β_{11} = \frac{44}{3} - \frac{17}{3} - \frac{8}{3} = \frac{19}{3}$ . For node x₉: what player 1 expects to get (the median element φ₁ (v^{x
₉}) =7 of the interval Shapley-like value Φ₁ (v^{x
₉})) in subgame Γ^{x
₉} is the difference $φ_{1} (v) - β_{1} (3) = φ_{1} (v) - β_{10} - β_{11} - β_{12} = \frac{44}{3} - \frac{17}{3} - \frac{8}{3} + \frac{2}{3} = 7$ . This shows that player 1 will always agree on the median element of the interval Shapley-like value and will not break cooperation. The same result is true for player 2 and player 3. Thus, time-consistent IDP β of the median element φ_i (v) = (φ₁ (v) , φ₂ (v) , φ₃ (v)) ∈ Φ_i (v) guarantees its realization and cooperation of players in the game along the cooperative trajectory (x₀, x₂, x₆, x₉).

5 Conclusion

In the paper, we have shown that in cooperative dynamic games with uncertain payoffs, namely interval payoffs, the problem of time consistency takes place. It means that in general, the cooperative outcome will not be realized as the game develops along the prescribed cooperative agreement. As a cooperative solution of the game, we have considered the interval Shapley-like value, an interval value based on the Shapley value that satisfies the indifference efficiency property. To realize the interval value in the dynamic game, we have introduced a mechanism of stage payments that reallocates the solution over time redistributing players’ stage payoffs—an imputation distribution procedure. The mentioned procedure has been implemented not only for the median element of the interval Shapley-like value; however, for an arbitrary element belonging to the interval value, we have provided two conditions which the procedure must satisfy. Our findings also correlate with those of crisp cooperative dynamic games, i.e., when the game becomes crisp, it can be easily seen that the interval Shapley-like value coincides with the Shapley value for crisp cooperative dynamic game. In this case, the imputation distribution procedure for the median value (or any arbitrary element belonging to the interval value) also coincides with the imputation distribution procedure for the crisp Shapley value (since the median value or the mentioned arbitrary element will coincide with the crisp Shapley value). As for limitations of our study, the theory has been developed for the interval value which is not efficient, so in future one can study the time consistency problem for other cooperative interval values, for instance, for the interval Shapley value satisfying the efficiency property. In this case one needs to redetermine the characteristic function of the game (to fulfill the property of size monotonicity mentioned in Alparslan Gök et al. [2]) and then calculate the solution, which was not a goal in the present research.

Acknowledgments

Authors thank two anonymous referees for their comments, which have improved the paper. Authors also acknowledge support from the Russian Foundation for Basic Research (Grant 13-01-91160), Saint Petersburg State University (Grants 9.38.245.2014, 9.42.1456.2015), the National Natural Science Foundation of China (Grants 71171163, 71271171, and 71311120091), the Science and Technology Research and Development Program in Shaanxi Province of China (Grant 2014KW03-01), and the Fundamental Research Funds for the Central Universities of China (Grant 3102014JCQ01072).

References

Alparslan Gök

S.Z.

, Miquel

and Tijs

, Cooperation under interval uncertainty, Math Meth Oper Res69 (2009), 99–109.

Alparslan Gök

S.Z.

, Branzei

and Tijs

, The interval Shapley value: An axiomatization, Cent Eur J Oper Res18 (2010), 131–140.

Alparslan

S.Z.

, Gök, On the interval Shapley value, Optimization63(5) (2014), 747–755.

Branzei

, Dimitrov

and Tijs

, Shapley-like values for interval bankruptcy games, Economics Bulletin3 (2003), 1–8.

Branzei

, Dimitrov

, Pickl

and Tijs

, How to cope with division problems under interval uncertainty of claims, Int J Unc Fuzz Knowl Based Syst12 (2004), 191–200.

Han

, Sun

and Xu

, A new approach of cooperative interval games: The interval core and Shapley value, Operations Research Letters40 (2012), 462–468.

Hwang

Y.A.

and Chen

M.C.

, A new axiomatization of the Shapley value under uncertainty, Economics Bulletin32 (2012), 799–810.

Jørgensen

and Zaccour

, Time consistent side payments in a dynamic game of downstream pollution, J Econ Dyn Control25 (2001), 1973–1987.

Kuhn

H.W.

, Extensive games and the problem of information, In Contributions to the Theory of Games II, Kuhn

H.W.

and Tucker

A.W.

eds., Princeton, Princeton University Press, 1953, pp. 193–216.

10.

Liao

Y.H.

, Alternative axiomatizations of the Shapley value under interval uncertainty, Int J Unc Fuzz Knowl Based Syst20(4) (2012), 619–628.

11.

Meng

and Liu

, The interval Shapley value for type-2 interval games, Res J Appl Sci Eng Technol4(10) (2012), 1334–1342.

12.

Meng

, Zhang

and Wang

, Cooperative fuzzy games with a coalition structure and interval payoffs, International Journal of Computational Intelligence Systems6(3) (2013), 548–558.

13.

Meng

, Chen

and Tan

, Cooperative fuzzy games with interval characteristic functions, Oper Res Int J. DOI: 10.1007/s12351-015-0183-z

14.

Moore

, Methods and applications of interval analysis, SIAM, Philadelphia, 1979.

15.

von Neumann

and Morgenstern

Theory of games and economic behavior,Princeton, Princeton University Press, 1953.

16.

Petrosyan

L.A.

, Stability of solutions in differential games with many participants, Vestnik Leningradskogo Universiteta Ser 1, Mat Mekhanika Astron19 (1977), 46–52.

17.

Petrosyan

L.A.

and Danilov

N.N.

, Stability of solutions in non-zero sum differential games with transferable payoffs, Vestnik Leningradskogo Universiteta Ser 1, Mat Mekhanika Astron1 (1979), 52–59.

18.

Petrosyan

L.A.

and Danilov

N.N.

, Cooperative differential games and their applications, Tomsk, Izd. Tomskogo University, 1985.

19.

Petrosyan

and Zaccour

, Time-consistent Shapley value allocation of pollution cost reduction, J Econ Dyn Control27(3) (2003), 381–398.