Keywords

1 Multi-objective Cooperative Games in the Literature

We start this paper with an overview on contributions to the literature that deal with multi-objective cooperative games and distinguish between concepts for transferable and non-transferable utilities for multiple objectives. However, what we can state for both is that there are only very few contributions that consider multi-objective allocations from a game-theoretical perspective and they all are strictly focused solely on a one type of the utility. For transferable utilities Fernandez et al. in [3] introduced set-valued TU games on an example of a multi-criteria minimum cost spanning tree problem. Fernandez et al. in [4] present for set-valued TU games two different core solution concepts, explore the differences among them and also consider multi-objective linear production game as another application of set-valued TU games. Nishizaki and Sakawa in [8] also study a multi-objective representation of linear production games with only common objectives, defined in terms of transferable utilities.

In terms of non-transferable utilities Christinsen et al. in [2] study a class of NTU games resulting from multi-objective linear programs with one objective per player. They consider an extension of the nucleolus as a solution concept and provide an algorithm for its computation. Andersen and Lind in [1] solve the allocation problem for this class of games with the Shapley NTU value and present a simplex-based computational algorithm for a two players case.

The bi-allocation game has been introduced by Kimms, Kozeletskyi and Meca in [6] for a general multi-objective optimization problem with one objective per player and a common objective function for all players. This game was illustrated using a multi-objective extension of linear production games and for allocation problem a new solution concept, inspired by the Shapley value for NTU games (see [9]), has been proposed. In this paper this solutions concept is described using the multi-objective cooperative TSP. Kimms and Kozeletskyi in [5] define a core-based allocation for the bi-allocation game and propose a computational algorithm for it.

2 A Multi-objective Cooperative Traveling Salesman Problem

In this section a cooperative planning situation in terms of the traveling salesman problem where players besides the traveling costs consider their individual objectives is formulated. Individual objectives are associated with utilities that players can gain from the fulfillment of available orders. Let \(u^k_i\) be a utility for player k from order i, if this order is fulfilled by k, meaning that player k visits node i. We assume that this utility can not be negative. This utility can be seen as a measure of importance of order i to player k. For instance, the higher the value of \(u_i^k\) the higher are chances that player k will get a new order from the same customer that placed order i in the future. Therefore in our perception every player k seeks to minimize his traveling costs as well as maximize the total utility from the assigned orders. In the case of a given coalition this representation leads to a multi-objective problem with one cost function and utility functions for every player. The cost function represents a common objective for all players.

For the formal definition of the problem additional notation is required. Let \(N=\{1, \ldots , n\}\) be a set of salesmen (also here referred to as players) with depots \(\{0_1, \ldots , 0_n\}\), where \(0_k\) corresponds to the depot of salesman k. For every non-empty coalition \(S \subseteq N\) we take V(S) as the set of orders, \(D(S):=\cup _{k \in S} 0_k\) as the set of depots and denote \(s:=|S|\). Orders set are taken as disjoint, i.e. \(\forall k, l \in N\), \(k \ne l:\) \(V(\{k\}) \cap V(\{l\}) = \emptyset \). And for two coalitions \(S, T \subseteq N\) we take that \(V(S \cup T) = V(S) \cup V(T)\). The problem can be represented as a directed graph \(G(S)=(V(S) \cup D(S), A(S), C(S), T(S))\) with the set of arcs A(S), representing connections between the nodes, matrix of traveling costs \(C(S)=(c_{ij})\) and matrix of traveling times \(T(S)=(t_{ij})\). Furthermore \(t_{max}\) defines the maximal length of a tour. Regarding the decision variables we use the binary variable \(x_{ijk}\), that indicates whether the arc (i, j) is used by salesman k (\(x_{ijk}=1\)), or not, and the real-valued decision variable \(\delta _i\) for the arrival time in node i.This variable is also in combination with a large number M a part of subtour elimination constraints.

Using the introduced notation the objective functions described above can be stated for a non-trivial coalition \(S \subseteq N\) as follows:

$$\begin{aligned}&f_0^S = \sum _{k \in S} \sum _{i \in V(S) \cup \{0_k\}} \sum _{j \in V(S) \cup \{0_k\}}{c_{ij} x_{ijk}}&\end{aligned}$$
(1)
$$\begin{aligned}&f_k^S = \sum _{j \in V(S)}{ u_j^k \sum _{i \in V(S) \cup \{0_k\}}{x_{ijl}}}&k \in S \; \end{aligned}$$
(2)

where \(f_0^S\) defines the cost function and \(\{f_k^S \, | \, k \in S\}\) are the utility functions. Finally the optimization problem looks as follows:

$$\begin{aligned}&\text{ optimize } \; \; \; \{f_0^S, \, f^S_{i_1}, \, f^S_{i_2}, \ldots , \, f^S_{i_{s}}\}&\end{aligned}$$
(3)
$$\begin{aligned}&\text{ s.t. } \nonumber \\&\sum _{k \in S}\sum _{j \in V(S) \cup \{0_k \}, j \ne i}{x_{ijk}}=1&i \in V(S), \end{aligned}$$
(4)
$$\begin{aligned}&\sum _{k \in S}\sum _{i \in V(S) \cup \{0_k \}, i \ne j}{x_{ijk}}=1&j \in V(S), \end{aligned}$$
(5)
$$\begin{aligned}&\sum _{j \in V(S) \cup \{0_k\}}{x_{ijk}} + \sum _{j \in V(S) \cup \{0_l\}}{x_{jil}} \le 1&i \in V(S), \; k, l \in S, k \ne l, \end{aligned}$$
(6)
$$\begin{aligned}&\delta _j^k + M \ge \delta _i^k + t_{ij} + M x_{ijk}&k \in S, \; i \in V(S), \nonumber \\&&j \in V(S) \cup \{0_k\}, \; j \ne i, \end{aligned}$$
(7)
$$\begin{aligned}&\delta _{0_k}^k \le t_{max}&k \in S, \end{aligned}$$
(8)
$$\begin{aligned}&\delta _i^k \ge d_i&i \in V(S), \; k \in S, \end{aligned}$$
(9)
$$\begin{aligned}&\sum _{j \in V(S)} x_{ijk} = 1&k \in S,\; i \in T^k, \end{aligned}$$
(10)
$$\begin{aligned}&x_{ijk} \in \{0, 1\}&\, k \in S, i, \; j \in V(S) \cup \{0_k\}, \; \end{aligned}$$
(11)
$$\begin{aligned}&\delta _i^k \ge 0&i \in V(S) \cup \{0_k\}, \; k \in S. \end{aligned}$$
(12)

For a given coalition S and \(l \in [1, \ldots , |S|]\), \(i_l\) denotes a player on the position l in the coalition S. More precisely this notation should be \(i_k(S)\), but as it is clear from the formulation which coalition S is considered, we skip S for notational brevity. The problem (3)–(12) is a multi-objective optimization problem and its solutions are considered under the notion of Pareto optimality. In the remainder of this paper for \(S \subseteq N\) we refer to the set of feasible solutions, defined through (4)–(12) as X(S) and to the set of Pareto optimal solutions as P(S). The optimization problem (3)–(12) will be referred to as the multi-objective cooperative TSP.

3 A Game-Theoretic Represantation of the Problem

The above described cooperative scenario includes, besides the cost function, additional objectives that express a metric interpretation of individual preferences of players towards customer’s orders. As these preferences vary for different players, values of individual objective functions have non-identical meaning to the players and therefore will be treated as a non-transferable utility in the allocation problem. For this reason the proposed cooperative scenario of a multi-objective cooperaive TSP represents a combination of transferable and non-transferable utilities, which cannot be treated by a common cooperative TU game. To handle allocation problems from a game-theoretical perspective in such cooperative scenarios a new class of cooperative games, called bi-allocation games, is applied. Kimms, Kozeletskyi and Meca in [6] introduced the bi-allocation game resulting from multi-objective optimization problems with all objectives to be maximized. In this section the definition of the bi-allocation game will be adapted to the case of the multi-objective cooperative TSP, with the cost function as a common objective.

For the multi-objective cooperative TSP the tuple

$$\begin{aligned} <N,\{f_0^S,(f_k^S)_{k \in S}, X(S)\}_{\begin{array}{c} S \subseteq N \\ S \ne \emptyset \end{array}}> \end{aligned}$$

denotes all feasible outcomes for all possible subcoalitions of N. Based on feasible outcomes the corresponding bi-allocation game for the multi-objective cooperative TSP can be defined as a pair \((N,\mathcal {V})\), with the characteristic set \(\mathcal {V}(S)\) for \(S \subseteq N\), \(S \ne \emptyset \):

$$\begin{aligned}&\mathcal {V}(S)=\{ \chi \in \mathbb {R}^{2s} \, | \, \exists \, x \in X(S), \, (\exists \, \pi \in \mathbb {R}^{s}: \, \sum _{k \in S}{\pi _{i(k)}}=f_0^S(x)), \, \text{ and } \, \nonumber \\&\quad (\chi _{1}, \ldots , \chi _{{s}}, \chi _{s+1}, \ldots , \chi _{2s}) \le (f_{i_1}^S(x), \ldots , f_{i_{s}}^S(x), -\pi _{1}, \ldots , -\pi _{s}) \} \end{aligned}$$
(13)

and \(\mathcal {V}(\emptyset )=\emptyset \). Every element \(\chi \in \mathcal {V}(S)\) represents a feasible payoff attainable for coalition S that consists of individual utilities \(\chi _k\) (that have a non-transferable nature) and an allocation of total traveling costs \(-\chi _{n+k}\). As it can be seen, this definition is related to the one of an non-transferable ultity (NTU) game, and the characteristic set \(\mathcal {V}(S)\) is also a set-valued mapping. However in the bi-allocation game, every characteristic set \(\mathcal {V}(S)\) is a subset of a 2s-dimensional space, as two allocations per player are considered. This formally distinguishes bi-allocation games from NTU games.

Besides the definition of the characteristic set the notion of its boundary is important for the computation of allocation and formal definitions of allocation concepts. The boundary consists of non-dominated allocations from a set \(\mathcal {V}(S)\). Using the notion of Pareto optimality and the introduced notation for P(S) we can define the boundary as:

$$\begin{aligned}&\partial \mathcal {V}(S)=\{ \chi \in \mathbb {R}^{2s} \, | \, \exists \, x \in P(S), \, (\exists \, \pi \in \mathbb {R}^{s}: \, \sum _{k \in S}{\pi _{i(k)}}=f_0^S(x)) \, \text{ and } \nonumber \\&\quad (\chi _{1}, \ldots , \chi _{s},\chi _{s+1}, \ldots , \chi _{2s}) = (f_{i_1}^S(x), \ldots , f_{i_{s}}^S(x), -\pi _{1}, \ldots , -\pi _{s})\}. \end{aligned}$$
(14)

For further discussion on bi-allocation games and especially on their properties the reader is referred to [6, 7]. In the next section an allocation concept called the Bi-allocation Shapley value we’ll be presented.

4 The Bi-allocation Shapley Value

For the definition of the Bi-allocation Shapley value a transferable correspondence to the bi-allocation game \((N, \mathcal {V})\) is required. This correspondence represents a scalar value associated with every coalition \(S \subseteq N\) and hence with every characteristic set \(\mathcal {V}(S)\) of the bi-allocation game. The transferable correspondence will be defined through weighting of allocation vectors components. We consider the set of weights

$$\begin{aligned} \varLambda =\{\lambda \in (0,1)^{2n} \, | \, \sum \limits _{i \in 2N}{\lambda _i}=1 \; \wedge \; \forall k \in N: \; \lambda _{n+i}=\lambda _0, \; \lambda _0 \in (0,1)\}. \end{aligned}$$
(15)

A weighting vector \(\lambda \in \varLambda \) defines weights associated with allocations from the characteristic set \(\mathcal {V}(N)\). In every allocation vector \(\chi \in \mathcal {V}(N)\) components \((\chi _{n+1}, \ldots , \chi _{2n})\) correspond to an allocation of the transferable utility \(f_0^N\) and are measured on the same scale. Therefore it is reasonable to consider same weights for the transferable part of the allocation and we take \(\lambda \), such that \(\lambda _{n+k}=\lambda _0\) for all \(k \in N\) and for some scalar \(\lambda _0 \in (0,1)\). Let for every weighting vector \(\lambda \in (0,1)^{2n}\) \(\lambda ^S\) be a subvector of components of \(\lambda \) corresponding to allocations associated with coalition S, i.e. \(\lambda ^S=(\lambda _{i_1}, \ldots , \lambda _{i_s}, \underbrace{\lambda _0, \ldots , \lambda _0}_{s})\).

Then for every \(S \subseteq N\) and \(\lambda \in \varLambda \) the transferable correspondence for the characteristic function \(\mathcal {V}(S)\) is

$$\begin{aligned} \nu _{\lambda }(S)= \max _{\chi \in \mathcal {V}(S)}{\lambda ^S \cdot \chi } \end{aligned}$$
(16)

with \(\nu _{\lambda }(\emptyset )=0\). From the definition of the characteristic set (13) and its boundary (14) it follows that the maximum in (16) is always reached in the boundary \(\partial \mathcal {V}(S)\) and \(\nu _{\lambda }(S)= \lambda ^S \chi \), for some \(\chi \in \partial \mathcal {V}(S)\). This means that \(\nu _{\lambda }(S)\) corresponds to a Pareto optimal solution of the underlying optimization problem, which in our case is the multi-objective cooperative TSP. Furthermore, as all elements of \(\partial \mathcal {V}(S)\) are finite-valued, we have that \(\nu _{\lambda }(S) < \infty \) for all \(S \subseteq N\) and all \(\lambda \in \varLambda \).

From (16) follows that for a given \(\lambda \in \varLambda \) \(\nu _\lambda \) is a mapping \(\nu _\lambda : 2^N \rightarrow \mathbb {R}\), with \(\nu _\lambda (\emptyset )=0\) and therefore it represents a well-defined characteristic function of a cooperative TU game. Thus we can define for every \(\lambda \in \varLambda \) a cooperative game \((N, \nu _\lambda )\), which can be interpreted as a transferable correspondence of the bi-allocation game \((N, \mathcal {V})\) for a given value \(\lambda \). For the cooperative game \((N, \nu _\lambda )\) we can compute the Shapley value and define it as \(\phi (\nu _\lambda )=(\phi _k(\nu _{\lambda }))_{k \in N}\), where for every \(k \in N\) \(\phi _k(\nu _\lambda )\) represents a payoff allocated to player k.

Then following the idea of Shapley for NTU games (see [9]), the allocation vector \(\chi \in \mathcal {V}(N)\) is called a Bi-allocation Shapley value of the game \((N,\mathcal {V})\), if there exists \(\lambda \in \varLambda \), such that

$$\begin{aligned} \lambda _k \chi _k + \lambda _{0} \chi _{n+k} = \phi _k(\nu _{\lambda }) \; \; \text{ for } \text{ all } \; k \in N. \end{aligned}$$
(17)

From the definition follows that, in contrary to the Shapley value for games with transferable utilities, the Bi-allocation Shapley value is not unique and there can be multiple \(\lambda \)’s and hence \(\chi \)’s that satisfy condition (17). We denote by \(\Phi (N,\mathcal {V})\) the set of all Bi-allocation Shapley values of the game \((N,\mathcal {V})\). As the Shapley value \(\phi \) of the game \((N, \nu _\lambda )\) is efficient we have that

$$\begin{aligned} \sum _{k \in N}{(\lambda _k \chi _k + \lambda _0 \chi _{n+k})}=\sum _{k \in N}{\phi _k(\nu _{\lambda })} = \nu _\lambda (N). \end{aligned}$$

Therefore the Bi-allocation Shapley value \(\chi \) is an allocation vector that satisfies the definition of \(\nu _\lambda (N)\) and hence belongs to the boundary \(\partial \mathcal {V}(N)\). So that, the Bi-allocation Shapley value corresponds to a Pareto optimal solution of the multi-objective cooperative TSP with an efficient allocation of the cost function \(f_0^N\). From this follows, that the set of Bi-allocation Shapley values \(\Phi (N,\mathcal {V})\) contains only Pareto optimal allocations.

For further discussion of the Bi-allocation Shapley value including its existence, we refer to [6] and regarding a computational approach with an application to the multi-objective cooperative TSP see [7].

5 Conclusions

The introduced cooperative game as well as the Bi-allocation Shapley value represent a general methodology for cooperative scenarios with a common and individual objectives of players. The described concept of weights in the definition of the Bi-allocation Shapley value is in its nature a weighting vector for the objective functions regarding the multi-objective optimization problem. Therefore this allocation concept addresses the multi-objective problem from an a priori perspective and weights can be interpreted as preferences of players towards the objective functions.