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

Facility location situations are a promising topic in the field of Operations Research (OR), which has many applications to real life. In this type of problems, there exist a given cost for constructing a facility. Further, connecting a player to this facility by minimizing the total cost is necessary.

In cooperative game theory allocating the costs in a fair way is very important, which is known as the cost allocation problem. In facility location situations, two cases can occur. One of them is the case of public facilities (such as libraries, municipal swimming pools, fire stations, etc.) and the other one is the case of private facilities (such as distribution centers, switching stations, etc.).

In a facility location situation, each facility is constructed to please the players. Here, the problem is to minimize the total cost. This cost is composed of both the player distance and the construction of each facility. A facility location game is constructed from a facility location situation [8].

In classical cooperative game theory payoffs to coalitions of players are known with certainty. On the other hand, there are many real-life situations in which people or businesses are uncertain about their coalition payoffs. Situations with uncertain payoffs in which the agents cannot await the realizations of their coalition payoffs cannot be modelled according to classical game theory. Several models that are useful to handle uncertain payoffs exist in the game theory literature [5, 14, 16].

The paper is organized as follows. In Sect. 2, we give some preliminaries about the study. We mention facility location games and PMAS in Sect. 3. Section 4 introduces facility location interval games and their Shapley value.

2 Preliminaries

In this section, some terminology on the theory of cooperative games and some useful results from the theory of cooperative interval games are given [3, 4, 8, 15].

A cooperative (cost) game in coalitional form is an ordered pair < N, c > , where \(N = \left \{1,2,\ldots,n\right \}\) is the set of players, and \(c: 2^{N} \rightarrow \mathbb{R}\) is a map, assigning to each coalition S ∈ 2N a real number \(c\left (S\right )\), such that \(c\left (\emptyset \right ) = 0.\)

We identify a cooperative cost game < N, c > with its characteristic function c. The family of all games with player set N is denoted by G N. We recall that G N is a \(\left (2^{\left \vert N\right \vert } - 1\right )\)-dimensional linear space for which unanimity games form an interesting basis. The unanimity game based on \(S,\ u_{S}: 2^{N} \rightarrow \mathbb{R}\) is defined by

$$\displaystyle{ u_{S}\left (T\right ) = \left \{\begin{array}{cc} 1& S \subset T,\\ 0 &\text{otherwise,} \end{array} \right. }$$

where \(S \in 2^{N}\setminus \left \{\emptyset \right \}.\)

Every coalitional game < N, c > can be written as a linear combination of unanimity games in a unique way such that \(c =\sum _{S\in 2^{N}\setminus \left \{\emptyset \right \}}\lambda _{S}\left (c\right )u_{S}\) [11]. The coefficients \(\lambda _{S}\left (c\right ),\ S \in 2^{N}\setminus \left \{\emptyset \right \}\) are called the unanimity coefficients of the game < N, c > , where c ∈ G N and satisfy

$$\displaystyle{ \lambda _{S}\left (c\right ) =\sum _{T\in 2^{S}\setminus \left \{\emptyset \right \}}\left (-1\right )^{\left \vert S\right \vert -\left \vert T\right \vert }c\left (T\right )\text{ for all }S \in 2^{N}\setminus \left \{\emptyset \right \}. }$$

Let c ∈ G N. The potential game \(<N,P_{\left (N,c\right )}^{HM}>\) associated with c ∈ G N is the coalitional game as follows,

$$\displaystyle{ P_{\left (N,c\right )}^{HM}\left (S\right ) = P\left (S,c_{ \vert S}\right ) }$$

\(\forall S \subseteq N.\) Hart and Mas-Colell [7] shows that the characteristic function of the potential game can be expressed in terms of the unanimity coefficients \(\lambda _{S}\left (c\right )\) of the game < N, c > which is given by,

$$\displaystyle{ P_{\left (N,c\right )}^{HM} =\sum _{ S\in 2^{N}\setminus \left \{\emptyset \right \}}\dfrac{\lambda _{S}\left (c\right )} {\left \vert S\right \vert } u_{S}. }$$

Let \(\pi \left (N\right )\) be the set of all permutations σ: N → N of N and c ∈ G N. The marginal contribution vector \(m^{\sigma }\left (c\right ) \in \mathbb{R}^{N}\) with respect to σ and c has the ith coordinate the value

$$\displaystyle{ m_{i}^{\sigma }\left (c\right ):= c\left (P^{\sigma }\left (i\right ) \cup \left \{i\right \}\right ) - c\left (P^{\sigma }\left (i\right )\right )\text{ for each }S \in 2^{N}. }$$

One of the most important solution concepts in cooperative game theory is the Shapley value [10]. The Shapley value associates to each game c ∈ G N one payoff vector in \(\mathbb{R}^{N}.\) The Shapley value \(\varPhi \left (c\right )\) of a game c ∈ G N is the average of the marginal vectors of the game, i.e.

$$\displaystyle{ \varPhi \left (c\right ):= \dfrac{1} {n!}\sum \limits _{\sigma \in \pi \left (N\right )}m^{\sigma }\left (c\right ). }$$

We call a game < N, c > as concave iff

$$\displaystyle{ c\left (S\right ) + c\left (T\right ) \geq c\left (S \cup T\right ) + c\left (S \cap T\right )\text{ }\forall S,T \in 2^{N}. }$$

We denote by CG N the class of concave games with player set N. It is well known that a concave game has a non-empty core.

In this paper, we consider a (point-valued) solution f on G N assigns that a payoff vector \(f\left (c\right ) \in \mathbb{R}^{N}\) to every TU-game c ∈ G N. Examples of such solutions are the Centre-of-gravity of the Imputation-Set value, shortly denoted by CIS-value, Egalitarian Non-Separable Contribution value, shortly denoted by ENSC-value and the equal division solution (see [6, 17]).

The CIS-value assigns to every player its individual worth, and distributes the remainder of the worth of the grand coalition N equally among all players, i.e.

$$\displaystyle{ CIS_{i}\left (c\right ) = c(\left \{i\right \}) + \dfrac{1} {\left \vert N\right \vert }(c\left (N\right ) -\sum _{j\in N}c(\left \{j\right \}))\text{ for all }i \in N. }$$

The ENSC-value assigns to every player in a game its marginal contribution to the ‘grand coalition’ and distributes the (positive or negative) remainder equally among the players, i.e.

$$\displaystyle{ ENSC_{i}\left (c\right ) = -c(N\setminus \left \{i\right \}) + \dfrac{1} {\left \vert N\right \vert }(c\left (N\right ) +\sum _{j\in N}c(N\setminus \left \{j\right \}))\text{ for all }i \in N. }$$

The equal division solution (ED-value) just distributes c(N) equally among all players, i.e.

$$\displaystyle{ ED_{i}\left (c\right ) = \dfrac{1} {\left \vert N\right \vert }c\left (N\right )\text{ for all }i \in N. }$$

A cooperative interval (cost) game is an ordered pair < N, c ′ > , where \(N = \left \{1,\ldots,n\right \}\) is the set of players, and \(c^{{\prime}}: 2^{N} \rightarrow I(\mathbb{R})\) is the characteristic function such that c ′(∅) = [0, 0]. Here, \(I(\mathbb{R})\) is the set of all nonempty, compact intervals in \(\mathbb{R}\). For each S ∈ 2N, the cost set (or: the cost interval) c ′(S) of the coalition S in the interval game < N, c ′ > is of the form \([\underline{c^{{\prime}}}(S),\overline{c^{{\prime}}}(S)]\), where c ′(S) is the minimal cost which coalition S could receive on its own and \(\overline{c^{{\prime}}}(S)\) is the maximal cost which coalition S could get. The family of all interval games with player set N is denoted by IG N.

Let \(I,J \in I(\mathbb{R})\) with \(I = \left [\underline{I},\overline{I}\right ]\), \(J = \left [\underline{J},\overline{J}\right ]\), \(\left \vert I\right \vert = \overline{I} -\underline{ I}\) and \(\alpha \in \mathbb{R}_{+}\). Then,

  1. (i)

    \(I + J = \left [\underline{I},\overline{I}\right ] + \left [\underline{J},\overline{J}\right ] = \left [\underline{I} +\underline{ J},\overline{I} + \overline{J}\right ]\);

  2. (ii)

    \(\alpha I =\alpha \left [\underline{I},\overline{I}\right ] = \left [\alpha \underline{I},\alpha \overline{I}\right ]\).

By (i) and (ii) we see that \(I(\mathbb{R})\) has a cone structure.

Here, we need a partial substraction operator. We define I − J, only if \(\left \vert I\right \vert \geq \left \vert J\right \vert\), by \(I - J:= \left [\underline{I},\overline{I}\right ] -\left [\underline{J},\overline{J}\right ] = \left [\underline{I} -\underline{ J},\overline{I} -\overline{J}\right ]\). Let us note that \(\underline{I} -\underline{ J} \leq \overline{I} -\overline{J}\). We recall that I is weakly better than J, which we denote by \(I \succcurlyeq J\), if and only if I ≥ J and \(\overline{I} \geq \overline{J}\). Furthermore, we use the reverse notation \(I \preccurlyeq J\), if and only if I ≤ J and \(\overline{I} \leq \overline{J}\). We say that I is better than J, which we denote by I ≻ J, if and only if \(I \succcurlyeq J\) and I ≠ J.

Finally, let \(I,J \in I(\mathbb{R})\) with \(I = \left [\underline{I},\overline{I}\right ]\), \(J = \left [\underline{J},\overline{J}\right ]\). We define the minimum of the two intervals, I ∧ J, by I ∧ J = I if \(I \preccurlyeq J,\) and their maximum, I ∨ J, by I ∨ J = J if \(I \preccurlyeq J.\)

In general, let \(I_{1},\ldots,I_{k} \in I\left (\mathbb{R}\right ).\) Suppose that \(I_{j} \succcurlyeq I_{r}\) for each \(r \in \left \{1,\ldots,k\right \}.\) Then, we say that \(I_{j}:=\max \left \{I_{1},\ldots,I_{k}\right \}.\) If \(I_{s} \preccurlyeq I_{r}\) for each \(r \in \left \{1,\ldots,k\right \},\) then \(I_{s}:=\min \left \{I_{1},\ldots,I_{k}\right \}.\) For example, let \(I_{1} = \left [0,1\right ],\ I_{2} = \left [-1,2\right ]\) and \(I_{3} = \left [3,5\right ].\) Then, \(I_{3} =\max \left \{I_{1},I_{2},I_{3}\right \},\) whereas max\(\left \{I_{1},I_{2}\right \}\) does not exist. Similarly, \(I_{2} =\min \left \{I_{2},I_{3}\right \},\) but \(\min \left \{I_{1},I_{2},I_{3}\right \}\) does not exist. For details see [1].

3 Facility Location Games and PMAS

In a facility location game a set \(\mathcal{A}\) of agents (also known as cities, clients, or demand points), a set \(\mathcal{F}\) of facilities, a facility opening cost f i for every facility \(i \in \mathcal{F}\), and a distance d ij between every pair (i, j) of points in \(\mathcal{A}\cup \mathcal{F}\) indicating the cost of connecting j to i are given. We assume that the distances come from a metric space; i.e., they are symmetric and obey the triangle inequality. For a set \(S \subseteq \mathcal{A}\) of agents, the cost of this set is defined as the minimum cost of opening a set of facilities and connecting every agent in S to an open facility. More precisely, the cost function c is defined by [8].

$$\displaystyle{ c\left (S\right ) =\min \limits _{\mathcal{F}^{{\ast}}\subseteq \mathcal{F}}\{\sum _{i\in \mathcal{F}^{{\ast}}}f_{i} +\sum _{j\in S}\min \limits _{i\in \mathcal{F}^{{\ast}}}d_{ij}\} }$$
(1)

Now, we give an example of facility location game.

Example 3.1.

Figure 1 shows a facility location game with three cities {Burdur (Player 1), Antalya (Player 2), Isparta (Player 3)} in Turkey and two hospitals \(\left \{1,2\right \}\). The cost function is calculated by using \(\left (1\right )\) the following:

$$\displaystyle\begin{array}{rcl} c\left (1\right )& =& 5,c\left (2\right ) = 4,c\left (3\right ) = 4, {}\\ c\left (12\right )& =& 7,c\left (23\right ) = 5,c\left (13\right ) = 9, {}\\ c\left (123\right )& =& 10. {}\\ \end{array}$$
Fig. 1
figure 1

An example of the facility location game

Full size image

Now, we recall the allocation schemes [8, 12]. An allocation scheme is a scheme which provides payoff vectors for a game and all its subgames. Formally, an allocation scheme for a game < N, c > is a vector \(\left (a_{i,S}\right )_{i\in S,S\subseteq N}\). The allocation scheme based on the Shapley value is called the Shapley allocation scheme.

Example 3.2.

We reconsider the facility location game in Example  3.1. The marginal vectors are given in Table 1.

Table 1 Marginal vectors
Full size table

Table 1 illustrates the marginal vectors of the facility location game in Example  3.2. The average of the six marginal vectors is the Shapley value of this game, which can be written as:

$$\displaystyle{ \varPhi (c) = (4\tfrac{2} {3},2\tfrac{1} {6},3\tfrac{1} {6}). }$$

The Shapley allocation scheme of < N, c > is represented in Table 2.

Table 2 The Shapley allocation scheme
Full size table

PMAS are introduced by Sprumont [13]. Sprumont [13] argues that this requires that the payoff of any player does not decrease as the coalition he belongs to grows larger. An allocation scheme that satisfies this property and that also satisfies efficiency for each subgame is called PMAS [12]. In formula, a vector \(a = (a_{i,S})_{i\in S,S\in 2^{N}\setminus \left \{\emptyset \right \}}\) is a population monotonic allocation scheme for a coalitional game < N, c > if it satisfies the following two conditions.

  1. 1.

    \(\sum \limits _{i\in S}a_{i,S} = c\left (S\right )\) for all \(S \in 2^{N}\setminus \left \{\emptyset \right \},\)

  2. 2.

    a i, S  ≥ a i, T for all \(S,T \in 2^{N}\setminus \left \{\emptyset \right \}\) with S ⊂ T and i ∈ S. 

Now, we give a relation between the Shapley allocation scheme being a PMAS and concavity of the associated potential game [8].

Remark 3.1.

The Shapley allocation scheme of coalitional game < N, c > is PMAS if and only if the associated potential game \(<N,P_{\left (N,c\right )}^{HM}>\) is concave.

An illustration of this remark can be found in the following facility location game.

Example 3.3.

We continue studying the facility location game in Example  3.1. The unanimity game of this facility location game is < N, c > with \(N = \left \{1,2,3\right \}\) and

$$\displaystyle{ c = 5u_{1} + 4u_{2} + 4u_{3} - 2u_{1,2} - 3u_{2,3} + 2u_{1,2,3}. }$$

The Shapley allocation scheme of this game is represented in Table 2. Using the payoffs in this table we find

$$\displaystyle{ a_{1,\left \{1,2,3\right \}}> a_{1,\left \{1,2\right \}} }$$

Hence, the Shapley allocation scheme is not a population monotonic allocation scheme.

The potential game associated with \(<N,P_{\left (N,c\right )}^{HM}>\) is described by

$$\displaystyle{ P_{\left (N,c\right )}^{HM} = 5u_{ 1} + 4u_{2} + 4u_{3} - 1u_{1,2} -\dfrac{3} {2}u_{2,3} + \dfrac{2} {3}u_{1,2,3} }$$

Consequently, we conclude that \(<N,P_{\left (N,c\right )}^{HM}>\) is not concave because of the following result.

$$\displaystyle{ c\left (12\right ) + c\left (23\right ) = 8 + \dfrac{13} {2} <4 + \dfrac{67} {6} = c\left (2\right ) + c\left (123\right ). }$$

Remark 3.2.

The facility location game is not concave. Then, the Shapley allocation scheme of the facility location game is not PMAS.

Now, we study the other allocation schemes on the facility location game. The allocation scheme based on CIS-value, ENSC-value and ED-value is called the CIS, ENSC and ED allocation scheme respectively.

Example 3.4.

We use the facility location game in Example  3.1 again. The CIS-value is defined by

$$\displaystyle{ CIS_{i}\left (c\right ) = c(\left \{i\right \}) + \dfrac{1} {\left \vert N\right \vert }(c\left (N\right ) -\sum _{j\in N}c(\left \{j\right \}))\text{ for all }i \in N. }$$

Then,

$$\displaystyle\begin{array}{rcl} CIS_{1}\left (c\right )& =& c\left (\left \{1\right \}\right ) + \dfrac{1} {3}\left (c\left (\left \{123\right \}\right ) - (c\left (\left \{1\right \}\right ) + c\left (\left \{2\right \}\right ) + c\left (\left \{3\right \}\right ))\right ) {}\\ & =& 4, {}\\ CIS_{2}\left (c\right )& =& c\left (\left \{2\right \}\right ) + \dfrac{1} {3}\left (c\left (\left \{123\right \}\right ) - (c\left (\left \{1\right \}\right ) + c\left (\left \{2\right \}\right ) + c\left (\left \{3\right \}\right ))\right ) {}\\ & =& 3, {}\\ CIS_{3}\left (c\right )& =& c\left (\left \{3\right \}\right ) + \dfrac{1} {3}\left (c\left (\left \{123\right \}\right ) - (c\left (\left \{1\right \}\right ) + c\left (\left \{2\right \}\right ) + c\left (\left \{3\right \}\right ))\right ) {}\\ & =& 3 {}\\ \end{array}$$

So, the CIS-value of this game is obtained by

$$\displaystyle{ CIS\left (c\right ) = \left (4,3,3\right ). }$$

The CIS-values of the subgames of < N, c > are easily computed. The CIS allocation scheme of < N, c > is represented in Table 3.

Table 3 The CIS allocation scheme
Full size table

Using the payoffs in this table we find

$$\displaystyle{ a_{2,\left \{1,2,3\right \}}> a_{2,\left \{2,3\right \}} }$$

Hence, the CIS allocation scheme is not a population monotonic allocation scheme. Let us compute the ENSC-value of this game. The ENSC-value is defined by

$$\displaystyle{ ENSC_{i}\left (c\right ) = -c(N\setminus \left \{i\right \}) + \dfrac{1} {\left \vert N\right \vert }(c\left (N\right ) +\sum _{j\in N}c(N\setminus \left \{j\right \}))\text{ for all }i \in N. }$$

Then,

$$\displaystyle\begin{array}{rcl} ENSC_{1}\left (c\right )& =& -c\left (\left \{2,3\right \}\right ) + \dfrac{1} {3}\left (c\left (\left \{123\right \}\right ) + c\left (\left \{1,2\right \}\right ) + c\left (\left \{1,3\right \}\right ) + c\left (\left \{2,3\right \}\right )\right ) {}\\ & =& \dfrac{16} {3}, {}\\ ENSC_{2}\left (c\right )& =& -c\left (\left \{1,3\right \}\right ) + \dfrac{1} {3}\left (c\left (\left \{123\right \}\right ) + c\left (\left \{1,2\right \}\right ) + c\left (\left \{1,3\right \}\right ) + c\left (\left \{2,3\right \}\right )\right ) {}\\ & =& \dfrac{4} {3}, {}\\ ENSC_{3}\left (c\right )& =& -c\left (\left \{1,2\right \}\right ) + \dfrac{1} {3}\left (c\left (\left \{123\right \}\right ) + c\left (\left \{1,2\right \}\right ) + c\left (\left \{1,3\right \}\right ) + c\left (\left \{2,3\right \}\right )\right ) {}\\ & =& \dfrac{10} {3} {}\\ \end{array}$$

So, the ENSC-value of this game is obtained by

$$\displaystyle{ ENSC\left (c\right ) = (5\tfrac{1} {3},1\tfrac{1} {3},3\tfrac{1} {3}). }$$

The ENSC-values of the subgames of < N, c > are easily computed. The ENSC allocation scheme of < N, c > is represented in Table 4.

Table 4 The ENSC allocation scheme
Full size table

Hence, the ENSC allocation scheme is not a population monotonic allocation scheme. Finally we compute the ED-value of this game. The ED-value is defined by

$$\displaystyle{ ED_{i}\left (c\right ) = \dfrac{1} {\left \vert N\right \vert }c\left (N\right )\text{ for all }i \in N. }$$

Then,

$$\displaystyle\begin{array}{rcl} ED_{1}\left (c\right )& =& \dfrac{c\left (\left \{1,2,3\right \}\right )} {3} {}\\ & =& \dfrac{10} {3} {}\\ ED_{2}\left (c\right )& =& \dfrac{c\left (\left \{1,2,3\right \}\right )} {3} {}\\ & =& \dfrac{10} {3} {}\\ ED_{3}\left (c\right )& =& \dfrac{c\left (\left \{1,2,3\right \}\right )} {3} {}\\ & =& \dfrac{10} {3} {}\\ \end{array}$$

So, the ED-value of this game is obtained by

$$\displaystyle{ ED\left (c\right ) = (3\tfrac{1} {3},3\tfrac{1} {3},3\tfrac{1} {3}). }$$

The ED-values of the subgames of < N, c > are easily computed. The ED allocation scheme of < N, c > is represented in Table 5.

Table 5 The ED allocation scheme
Full size table

Using the payoffs in this table we find

$$\displaystyle{ a_{2,\left \{1,2,3\right \}}> a_{2,\left \{2,3\right \}} }$$

Hence, the ED allocation scheme is not a population monotonic allocation scheme.

As you can see that in facility location games the CIS, ENSC and ED allocation scheme does not form population monotonic allocation scheme. Now, we give main result of this paper.

Remark 3.3.

The three allocation schemes CIS, ENSC and ED used in Example 3.4 do not generate PMAS.

Remark 3.4.

When we check the results in Table 2 (Shapley allocation scheme), only the player 2 is satisfied from cooperation. On the other hand we consider the results in Table 3 (CIS allocation scheme), the player 2 and player 3 are satisfied from cooperation. Additionally, we can see that the results in Table 4 (ENSC allocation scheme), only the player 3 is satisfied from cooperation. Finally, we take the results in Table 5 (ED allocation scheme), only the player 1 is satisfied from cooperation.

4 Facility Location Interval Games and Their Interval Shapley Value

In this section, we introduce the facility location interval games inspired by Nisan [8]. In a facility location interval game, a set \(\mathcal{A}\) of agents (also known as cities, clients, or demand points), a set \(\mathcal{F}\) of facilities, a facility opening interval cost f i ′ for every facility \(i \in \mathcal{F}\), and a distance d ij ′ between every pair (i, j) of points in \(\mathcal{A}\cup \mathcal{F}\) indicating the interval cost of connecting j to i are given. Here, \(f_{i}^{{\prime}}:= \left [\underline{f_{i}},\overline{f_{i}}\right ],d_{ij}^{{\prime}}:= \left [\underline{d_{ij}},\overline{d_{ij}}\right ] \in I\left (\mathbb{R}\right ).\) The distances are supposed to come from a metric space. So, these distances are symmetric and satisfy the triangle inequality. For a set \(S \subseteq \mathcal{A}\) of agents, the interval cost of this set is defined as the minimum interval cost of opening a set of facilities and connecting every agent in S to an open facility. More precisely, the interval cost function c ′ is defined by

$$\displaystyle{ c^{{\prime}}\left (S\right ) = \left [\min \limits _{ \mathcal{F}^{{\ast}}\subseteq \mathcal{F}}\{\sum _{i\in \mathcal{F}^{{\ast}}}\underline{f_{i}} +\sum _{j\in S}\min \limits _{i\in \mathcal{F}^{{\ast}}}\underline{d_{ij}}\},\min \limits _{\mathcal{F}^{{\ast}}\subseteq \mathcal{F}}\{\sum _{i\in \mathcal{F}^{{\ast}}}\overline{f_{i}} +\sum _{j\in S}\min \limits _{i\in \mathcal{F}^{{\ast}}}\overline{d_{ij}}\}\right ] \in I\left (\mathbb{R}\right ) }$$
(2)

Now, we give the example of facility location interval game.

Example 4.1.

Figure 2 shows a facility location interval game with three cities {Burdur (Player 1), Antalya (Player 2), Isparta (Player 3)} in Turkey and two hospitals \(\left \{1,2\right \}\). The interval cost function is calculated by using \(\left (2\right )\) the following:

$$\displaystyle\begin{array}{rcl} c^{{\prime}}\left (1\right )& =& \left [5,5.5\right ],c^{{\prime}}\left (2\right ) = \left [4,4.4\right ],c^{{\prime}}\left (3\right ) = \left [4,4.4\right ], {}\\ c^{{\prime}}\left (12\right )& =& \left [7,7.7\right ],c^{{\prime}}\left (23\right ) = \left [5,5.5\right ],c^{{\prime}}\left (13\right ) = \left [9,9.9\right ], {}\\ c^{{\prime}}\left (123\right )& =& \left [10,11\right ]. {}\\ \end{array}$$
Fig. 2
figure 2

An example of the facility location interval game

Full size image

Now, we calculate the interval Shapley value of the facility location interval game. Firstly, we recall the definition of the interval Shapley value. For this, we need to recall some notions from the theory of cooperative interval games [2].

Interval solutions are useful to solve reward/cost sharing problems with interval data using cooperative interval games as a tool. The interval payoff vectors, which are the building blocks for interval solutions, are the vectors whose components belong to \(I(\mathbb{R})\). We denote by \(I(\mathbb{R})^{N}\) the set of all such interval payoff vectors.

We call a game < N, c ′ > size monotonic if \(<N,\left \vert c^{{\prime}}\right \vert>\) is monotonic, i.e., \(\left \vert c^{{\prime}}\right \vert (S) \leq \left \vert c^{{\prime}}\right \vert (T)\) for all S, T ∈ 2N with S ⊂ T. For further use we denote by SMIG N the class of size monotonic interval games with player set N.

The following theorem shows that the facility location interval games are size monotonic.

Theorem 4.1.

The facility location interval game < N,c ′ > belongs the class of SMIG N .

Proof.

We show that the facility location interval game c ′ belongs to the class of SMIG N. For this,

$$\displaystyle{ \left \vert c^{{\prime}}\right \vert (S) \leq \left \vert c^{{\prime}}\right \vert (T)\text{ for all }S,T \in 2^{N}\text{ with }S \subset T. }$$

It can be seen that < N, c ′ > belongs to the class of SMIG N. For details see [9].

We know that if an interval game is belonging to SMIG N, then the interval Shapley value is always given [2].

Remark 4.1.

The interval Shapley value of the facility location interval games always exists.

The interval marginal operators and the interval Shapley value were defined on SMIG N in [2] as follows.

Denote by Π(N) the set of permutations σ: N → N of \(N = \left \{1,2,\ldots,n\right \}\). The interval marginal operator \(m^{\sigma }: SMIG^{N} \rightarrow I(\mathbb{R})^{N}\) corresponding to σ, associates with each c ′ ∈ SMIG N the interval marginal vector m σ(c ′) of c ′ with respect to σ, defined by \(m_{i}^{\sigma }(c^{{\prime}}) = c^{{\prime}}(P^{\sigma }(i) \cup \left \{i\right \}) - c^{{\prime}}(P^{\sigma }(i))\) for each i ∈ N, where \(P^{\sigma }(i):= \left \{r \in N\vert \sigma ^{-1}(r) <\sigma ^{-1}(i)\right \}\). Here, σ −1(i) denotes the entrance number of player i.

For size monotonic games < N, c ′ > , c ′(T) − c ′(S) is defined for all S, T ∈ 2N with S ⊂ T, since \(\left \vert c^{{\prime}}(T)\right \vert = \left \vert c^{{\prime}}\right \vert (T) \geq \left \vert c^{{\prime}}\right \vert (S) = \left \vert c^{{\prime}}(S)\right \vert\). Now, we notice that for each c ′ ∈ SMIG N the interval marginal vectors m σ(c ′) are defined for each σ ∈ Π(N), because the monotonicity of \(\left \vert c^{{\prime}}\right \vert\) implies \(\overline{c^{{\prime}}}(S \cup \left \{i\right \}) -\underline{ c^{{\prime}}}(S \cup \left \{i\right \}) \geq \overline{c^{{\prime}}}(S) -\underline{ c^{{\prime}}}(S)\), which can be rewritten as \(\overline{c^{{\prime}}}(S \cup \left \{i\right \}) -\overline{c^{{\prime}}}(S) \geq \underline{ c^{{\prime}}}(S \cup \left \{i\right \}) -\underline{ c^{{\prime}}}(S)\). So, \(c^{{\prime}}(S \cup \left \{i\right \}) - c^{{\prime}}(S)\) is defined for each S ⊂ N and i ∉ S.

The interval Shapley value assigns to each cooperative interval game a payoff vector whose components are compact intervals of real numbers. Cooperative games in the additive cone on which we use the interval Shapley value arise from several OR and economic situations with interval data.

The interval Shapley value \(\varPhi: SMIG^{N} \rightarrow I(\mathbb{R})^{N}\) is defined by

$$\displaystyle{ \varPhi (c^{{\prime}}):= \frac{1} {n!}\sum _{\sigma \in \varPi (N)}m^{\sigma }(c^{{\prime}}),\ \text{for each}\ c^{{\prime}}\in SMIG^{N}. }$$

The following example shows the calculation of the interval Shapley value in the facility location interval game.

Example 4.2.

Consider < N, c ′ > as the facility location interval game in Example  4.2. Here, \(N = \left \{1,2,3\right \}\) and the characteristic function c ′ is given as

$$\displaystyle\begin{array}{rcl} c^{{\prime}}\left (1\right )& =& \left [5,5.5\right ],c^{{\prime}}\left (2\right ) = \left [4,4.4\right ],c^{{\prime}}\left (3\right ) = \left [4,4.4\right ], {}\\ c^{{\prime}}\left (12\right )& =& \left [7,7.7\right ],c^{{\prime}}\left (23\right ) = \left [5,5.5\right ],c^{{\prime}}\left (13\right ) = \left [9,9.9\right ], {}\\ c^{{\prime}}\left (123\right )& =& \left [10,11\right ]. {}\\ \end{array}$$

Then, the interval marginal vectors are given in the Table 6. The set of permutations of N is

$$\displaystyle{ \pi \left (N\right ) = \left \{\begin{array}{c} \sigma _{1} = \left (1,2,3\right ),\sigma _{2} = \left (1,3,2\right ),\sigma _{3} = \left (2,1,3\right ), \\ \sigma _{4} = \left (2,3,1\right ),\sigma _{5} = \left (3,1,2\right ),\sigma _{6} = \left (3,2,1\right ) \end{array} \right \}. }$$

Firstly, for \(\sigma _{2} = \left (1,3,2\right ),\) we calculate the interval marginal vectors. Then,

$$\displaystyle\begin{array}{rcl} m_{1}^{\sigma _{2} }\left (c^{{\prime}}\right )& =& c^{{\prime}}\left (1\right ) = \left [5,5.5\right ], {}\\ m_{2}^{\sigma _{2} }\left (c^{{\prime}}\right )& =& c^{{\prime}}\left (123\right ) - c^{{\prime}}\left (13\right ) = \left [10,11\right ] -\left [9,9.9\right ] = \left [1,1.1\right ], {}\\ m_{3}^{\sigma _{2} }\left (c^{{\prime}}\right )& =& c^{{\prime}}\left (13\right ) - c^{{\prime}}\left (1\right ) = \left [9,9.9\right ] -\left [5,5.5\right ]. {}\\ \end{array}$$

The others can be calculated similarly, which is shown in Table 1.

Table 6 Interval marginal vectors
Full size table

Table 6 illustrates the interval marginal vectors of the facility location interval game in Example  4.2. The average of the six interval marginal vectors is the interval Shapley value of this game, which can be written as:

$$\displaystyle{ \varPhi (c^{{\prime}}) = ([4\tfrac{2} {3},5 \tfrac{2} {15}],[2\tfrac{1} {6},2\tfrac{23} {60}],[3\tfrac{1} {6},3\tfrac{29} {60}]). }$$

5 Conclusion and Outlook

The objective of cooperative game theory is to study ways to enforce and sustain cooperation among agents willing to cooperate. A central question in this field is how the benefits (or costs) of a joint effort can be divided among participants, taking into account individual and group incentives, as well as various fairness properties.

In this paper, we study some results related with facility location situations and games. After that, we introduce facility location interval games. Further, we show that some allocation schemes of facility games do not have PMAS.

For future studies, allocation schemes of other solutions can be studied and interpreted. In this study, we introduce facility location interval games. Similarly, potential interval games can be studied.