1 Introduction

Shortest path games (Rosenthal 2013; Bahel and Trudeau 2014) are network games where agents must ship their demands of some homogeneous good from a source point to their respective locations. The cost on each arc of the network is linear in the total demand crossing it, which gives rise to a cooperative game (with transferable cost) where each coalition seeks to minimize the total cost of shipping the demands of its members. Applications of shortest paths include for instance public transportation networks (Rosenthal 2017), airline networks (Bryan and O’Kelly 1999), resource supply chains (Massol and Tchung-Ming 2010), and small package delivery (Sim et al. 2009).

Under our framework, an optimal network configuration is obtained when each agent i’s demand is shipped through a shortest path to agent i, that is, a path achieving minimum cost among all paths from the source to agent i. A natural way to share the cost is the demander rule, which requires each agent i to pay the cost of her shortest path for each unit she demands. It is known from Rosenthal (2013) that this cost allocation belongs to the core, i.e., no subgroup of players can ship their respective demands (using only the connections available in the subgroup) at a cost lower than their joint share under the demander rule.

The present work focuses on two consistency properties: Merge Proofness and Cost Solidarity. The axiom Merge Proofness prevents any group S of distinct agents from increasing others’ cost shares (and hence reducing their own joint share) by merging and acting as a single node whose connection to any given outsider is the cheapest among those available in the group S. Merge Proofness has been studied in many different settings, such as bilateral monopolies (Horn and Wolinsky 1988), bankruptcy problems (de Frutos 1999), cost-sharing problems (Sprumont 2005), scheduling problems (Moulin 2008), bipartite matching games (Hezarkhani 2016), or minimum cost spanning tree problems (Gómez-Rúa and Vidal-Puga 2011, 2017).

The axiom Cost Solidarity states that an agent’s cost share should be weakly increasing in the cost matrix. Note that, following an increase in the unit cost for some arcs (all else unchanged), Cost Solidarity says that no agent should have a lower cost share. If this property is not satisfied, some agents may be incentivized to sabotage the shipping operation and report higher costs to pay lower-cost shares. Cost solidarity generalizes the well-known idea of cost monotonicity, and it has also been studied in minimum cost spanning tree problems (Bergantiños and Vidal-Puga 2007; Gómez-Rúa and Vidal-Puga 2017).

We offer two characterizations of the demander rule. The first one, stated in Theorem 3.1, asserts that the demander rule is the only cost allocation scheme satisfying Core Selection and Merge Proofness. The second one, stated in Theorem 3.2, asserts that the demander rule is the only cost allocation scheme satisfying Core Selection and Cost Solidarity.

The paper is organized as follows. In Sect. 2, we set up the framework by defining shortest-path problems and cost-sharing rules. In Sect. 3, we define the demander rule and provide our characterization results.

2 The model

Our framework is close to that of Bahel and Trudeau (2014) and Bahel et al. (2024). The main differences stem from the fact that we consider here a variable set of agents—whereas the set of agents in these previous papers is fixed. Let U be the set of natural numbers (positive integers) denoting the (infinite) set of potential agents. We consider problems where a (finite) number of agents in U need to ship units of some commodity from a fixed point \({\textbf {0}}\) to their respective locations (\({\textbf {0}}\) is called the source). Let \(\mathcal {N}\) denote the set of nonempty, finite subsets of U. We use the symbol N to refer to a generic element of U, that is to say, \(N\in \mathcal {N}\).

To ease on notation, we will often write i instead of \(\{i\}\) and \(S\setminus i\) instead of \(S\setminus \{i\}\), for any \(i\in S \subseteq N\). Moreover, for any vector \(x \in \mathbb {R}^N\) and any subset \(S\subseteq N\), we write

$$\begin{aligned} x_S:= \sum _{i\in S}x_i. \end{aligned}$$

A Shortest Path Problem (SPP) is a tuple \(P=(N,c,x)\), where:

  • \(N \in \mathcal {N}\) is the set of agents who need to connect to the source \({\textbf {0}}\);

  • \(c=\left\{ c(i,j):i\in N \cup {\textbf {0}},j \in N, i\ne j\right\} \) is a collection of non-negative numbers (often referred to as a “cost matrix”) giving the unit cost of shipping demands through each arc (i, j);

  • \(x \in \mathbb {R}_+^{N}\) is the demand vector: each agent \(i\in N\) has a demand \(x_i \in \mathbb {R}_+\) (of the commodity) to ship from the source to her location.

The set of SPP with agent set \(N \in \mathcal {N}\) will be denoted by \(\mathbb {P}_N\), and \(\mathbb {P}:= \bigcup _{N\in \mathcal {N}}\mathbb {P}_N\). Note that the source \({\textbf {0}}\) is not an agent and that the unit costs c(i, j) need not be symmetric—we may well have \(c(i,j) \ne c(j, i)\) for some \(i,j \in N\). Whenever \(c(i, j)= c(j, i)\) holds for all \(i,j \in N\) s.t. \(i \ne j\), we say that the SPP has symmetric arcs.

Definition 2.1

Given \(N\in \mathcal {N}\) and \(i \in N\), we call path (of length K) to agent i any sequence \(p:= (p_k)_{k=0,....,K}\) such that:

  1. 1.

    \(p_k \in N\), for \(k=1,2,\dots ,K\);

  2. 2.

    \(p_0 = \textbf{0}\) and \(p_K=i\);

  3. 3.

    \(p_k \notin \{p_1,\ldots ,p_{k-1}\}\) whenever \(2\le k\le K\).

Note that all paths p originate from the source \({\textbf {0}}\) and cross any location \(p_k\) only once. Thus, the length of each path and the number of paths to any given \(i\in N\) are both finite. We denote by \(\mathcal {P}_N(i)\) the set containing all paths to agent i. For simplicity, and as long as the player set is clear, we write \(\mathcal {P}(i)\) instead of \(\mathcal {P}_N(i)\). For any path p of length K, let [p] refer to the set of players in the range of p, that is:

$$ [p]:= \{j\in N: p_k = j \,{\text { for some }}\, k=1,\dots ,K\}. $$

Given \(P=(N,c,x)\), one can extend the cost function c to paths as follows: for any path p (of length K) to agent \(i\in N\), c(p) represents the cost of shipping one unit from the source to agent i via the path p, i.e.,

$$ c(p):=\sum _{k=1}^K c(p_{k-1},p_k). $$

For any \(i\in N\), we call shortest path to i any path \(\bar{p}^i\in \mathcal {P}(i)\) that solves the problem \(\min _{p\in \mathcal {P}(i)} c(p)\). Note that there exists a shortest path to any \(i\in N\)—since the set \(\mathcal {P}(i)\) is nonempty and finite—but it may not be unique.

Example 2.1

Consider the SPP with symmetric arcs given by \(P=(N,c,x)\), where \(N=\{1,2,3\}\), \(x=(2,0,1)\) and the cost structure is depicted by Fig. 1. Hence, we have \(c({\textbf {0}},1)=500\), \(c(3,1)=c(1,3)=10\), \(c(2,1)=c(1,2)=70\), and so on.

Fig. 1
figure 1

SPP with three agents

Full size image

One can see that there are 5 paths to agent 1, \(({\textbf {0}},1), ({\textbf {0}},2,1)\), \(({\textbf {0}},3,1), ({\textbf {0}},2,3,1)\), \(({\textbf {0}},3,2,1)\); and the shortest path to 1 is \(({\textbf {0}},2,3,1)\), with cost \(c({\textbf {0}},2,3,1)= 60 + 20 + 10 = 90\). For agents 2 and 3, the costs of their respective shortest paths are \(c({\textbf {0}},2)=60\) and \(c({\textbf {0}},2,3) = 60 + 20 = 80\).

The cooperative game (with transferable cost) associated with P can be formulated by defining the cost of any nonempty coalition \(S\subseteq N\) as

$$\begin{aligned} C_P(S) := \min \left\{ \sum \limits _{j\in S}x_j \cdot c(p^j) : p^j\in \mathcal {P}(j) \,{ \text{ and } }\, [p^j]\subseteq S, \forall j\in S\right\} . \end{aligned}$$
(1)

That is to say, the members of S pay the lowest possible cost of shipping their respective demands when using only the connections available in S. In particular, \(C_P(S)=0\) whenever there is no demand to ship, i.e., \(x_S=0\). We also adopt the convention that \(C_P(\emptyset )=0\). For the problem P depicted in Example 2.1, \(C_P(\{1\})=2\cdot c({\textbf {0}},1) = 1000\); \(C_P(\{2\})=0\cdot c({\textbf {0}},2) = 0\); \(C_P(\{3\})=1\cdot c({\textbf {0}},3) = 120\); \(C_P(\{1,2\})=2\cdot c({\textbf {0}},2,1) + 0\cdot c({\textbf {0}},2) = 2\cdot 130=260\); \(C_P(\{1,3\})=2\cdot c({\textbf {0}},3,1) + 1\cdot c({\textbf {0}},3) = 2\cdot 130+1\cdot 120=380\); \(C_P(\{2,3\})=0\cdot c({\textbf {0}},2) + 1\cdot c({\textbf {0}},2,3) = 0\cdot 60+1\cdot 80=80\); and \(C_P(N)=2\cdot c({\textbf {0}},2,3,1)+0\cdot c({\textbf {0}},2)+1\cdot c({\textbf {0}},2,3) = 180 + 80 = 260\).

Definition 2.2

Given a shortest path problem \(P=(N,c,x)\), we have the following.

(i) An allocation is a profile of cost shares, \(y\in \mathbb {R}^N\), such that \(y_N=C_P(N)\). Let \(\mathcal {A}(P)\) be the set containing all cost allocations in P.

(ii) The core of P is the set

$$Core(P):= \left\{ y\in \mathcal {A}(P): y_S\le C_P(S), \forall S\subsetneq N\right\} .$$

An allocation y is called stable if \(y\in Core(P)\).

The above definition says that a cost allocation splits the total cost of shipping the respective demands between all agents in N. Remark that we allow for negative cost shares, which may be desirable in particular if we have agents who demand zero while providing others with cheaper access to the source. Definition 2.2-(ii) is the standard notion of stability: every coalition S should jointly pay at most its stand-alone cost \(C_P(S)\).

It is known from the works of Rosenthal (2013) and Bahel and Trudeau (2014) that the Shapley value does not always pick a stable allocation. In particular, in Example 2.1, the Shapley value assigns the shares \((480,-170,-50)\); and this allocation does not belong to the core of the game because \(y_{\{1,2\}} = 480 -170 = 310 > C_P(\{1,2\})\) and \(y_{\{1,3\}} = 480 -50 = 430 > C_P(\{1,3\}).\)

Let us now define the solution concepts studied in this work.

Definition 2.3

A Cost Sharing Rule (CSR) is a mapping \(y:\mathbb {P} \rightarrow \bigcup _{N\in \mathcal {N}}\mathbb {R}^N\) that assigns to each \(P\in \mathbb {P}_N\) a cost allocation \(y(P)\in \mathbb {R}^N\) such that \(y_N(P)=C_P(N)\).

In words, a CSR is a mapping which, for any given problem P, allows to divide between agents the total cost \(C_P(N)\) of satisfying the respective demands (we refer to this property as efficiency). In the following sections, we introduce a number of desirable properties for a CSR.

3 The demander rule

Following Bahel et al. (2024), we define the demander rule as follows:

Definition 3.1

The demander rule \(y^d\) is the CSR defined as:

$$\begin{aligned} y_i^d(N,c,x)=x_i\cdot \min _{p^i\in \mathcal {P}(i)}c(p^i) \end{aligned}$$

for all \((N,c,x)\in \mathbb {P}\) and \(i\in N\).

In other words, the demander rule requires each agent to pay the cost of her shortest path for each unit demanded. Agents who demand zero pay nothing. As an illustration, for the SPP depicted in Example 2.1, the demander rule yields the cost share \(y^d=(180, 0, 80)\).

In this section, we propose several characterization results for the demander rule. We first introduce the axioms involved in these characterizations.

3.1 Core selection

The first one of these axioms is the well-known Core Selection property. It requires the considered CSR to select a stable allocation in every problem.

Definition 3.2

A CSR y satisfies Core Selection if, for all \(P \in \mathbb {P}\), we have

$$ y(P)\in Core(P). $$

Since the core of an SPP is always nonempty, there exist many rules satisfying Core Selection. In fact, it is shown in Bahel and Trudeau (2014) (among other papers) that the demander rule meets Core Selection. To make our current analysis self-contained, we provide the formal argument here as well.

Proposition 3.1

The demander rule \(y^d\) satisfies Core Selection.

Proof

Fix a problem \(P=(N, c,x)\in \mathbb {P}\). First, note from (1) and Definition 3.1 that

$$\sum _{i\in N}y_i^d(P) = \sum _{i\in N}x_i \min _{{p}\in {\mathcal {P}}^i}c({p}) = C_P(N).$$

Second, for any coalition \(S\subsetneq N\), remark that

$$ x_S=\sum _{i\in S}y^d_i(P) = \sum _{i\in S}x_i\min _{{p}\in {\mathcal {P}}^i}c({p}) \le \sum _{i\in {S}} x_i \min _{{p} \in {\mathcal {P}}^i: [{p}]\subseteq S}c({p}) = C_P(S). $$

\(\square \)

3.2 Merge proofness

The second axiom is Merge Proofness. This property says that no group of agents should be able to increase the cost share of an outsider by merging and acting as a single node. If a group of agents S merge into the single agent \(s\in S\) (while every agent not in S remains the same) then we have a new problem \(P^{s,S}:= \left( N^{s,S},c^{s,S},x^{s,S}\right) \), which is defined as follows. First, the new set of agents and their demands are respectively:

$$\begin{aligned} N^{s,S} := \left( N\setminus S\right) \cup \{s\} \end{aligned}$$
(2)

and

$$\begin{aligned} x^{s,S}_i:= \left\{ \begin{array}{ll} x_i & \,{\text { if }}\, i \in N \setminus S\\ x(S) & \,{\text { if }}\, i = s. \end{array} \right. \end{aligned}$$
(3)

Note from (3) that agent s in the new problem inherits the aggregate demand of the coalition S, and the demand of every other agent \(i\in N\setminus S\) remains unchanged. In addition, the cost matrix \(c^{s,S}\) of the new problem is given by

$$\begin{aligned} c^{s,S}(i,j) := \left\{ \begin{array}{ll} \min _{k\in S}c(i,k) & \,{\text { if }}\, i \in (N \setminus S)\cup {\textbf {0}} \,{\text { and }}\, j = s\\ \min _{k\in S}c(k,j) & \,{\text { if }}\, i =s \,{\text { and }}\, j \in N \setminus S\\ c(i,j) & \,{\text { if }}\, i \in (N \setminus S)\cup {\textbf {0}} \,{\text { and }}\, j\in N \setminus S. \end{array} \right. \end{aligned}$$
(4)

In the reduced problem, any node outside S will always use the best link available in S to connect with s (and vice-versa). Given this notation, the formal definition of Merge Proofness can then be stated as follows.

Definition 3.3

A CSR y satisfies Merge Proofness if, for all \(P \in \mathbb {P}\), \(S\subsetneq N\), \(s\in S\) and \(i\in N{\setminus } S\),

$$ y_i(P^{s,S})\le y_i(P). $$

If a group of agents S merge in advance to be treated as a single agent s, note from (2)–(4) that \(C_P(N)\ge C_{P^{s, S}}(N^{s, S})\), that is to say, the total cost of connecting everybody (without accounting for the internal costs of linking members of S) decreases from P to \(P^{s,S}\). Merge Proofness then ensures that no outsider agent \(i\notin S\) will be worse off in the reduced problem \(P^{s, S}\). Given that \(\sum _{i\in S}y_i(P) = C_P(N) - \sum _{i\in N {\setminus } S} y_i(P)\) and \(\sum _{i\in N{\setminus } S}y_i(P^{s, S}) = C_{P^{s, S}}(N^{s, S}) - y_s(P^{s, S})\) must hold for every CSR y, it is not difficult to see that Merge Proofness implies that the joint share of agents in S should not decrease more than the total cost of connecting all agents in N.

Recalling Example 2.1, let us consider the group of agents \(S=\{1,2\}\). If the two agents of S merge into a single agent s, then the new problem \(P^{s,S}:= \left( N^{s,S},c^{s,S},x^{s,S}\right) \) is given by: \(N^{s,S}=\{s,3\}\); \(x^{s,S}_s=2\), \(x^{s,S}_3=1\); \(c^{s,S}(0,s)=\min \{c(0,1),c(0,2)\}=60\), \(c^{s,S}(0,3)=c(0,3)=120\), and \(c^{s,S}(s,3)=\min \{c(1,3),c(2,3)\}=10\). Definition 3.3 then says that we should have \(y_3(P^{s,S})\le y_3(P)\), which protects agent 3 from the merging manipulation available to the coalition formed by agents 1 and 2.

The following result states an additional additional property of the demander rule.

Proposition 3.2

The demander rule \(y^d\) satisfies Merge Proofness.

Proof

Consider an SPP denoted by \(P=(N,c,x)\); and let \(\bar{p}^i=(\bar{p}^i_0={\textbf {0}}, \bar{p}^i_1,\ldots , \bar{p}^i_{K_i}=i)\) be a shortest path (for the problem P) to each \(i\in N\), with \(K_i\) denoting the length of \(\bar{p}^i\). Suppose that the players of coalition \(S\subsetneq N\) (with \(|S|\ge 2\)) decide to merge into the node \(s\in S\); and consider the reduced problem \(P^{s,S}\) defined by (2)–(4). Fix \(j\in N\setminus S\) and, in the case where \([\bar{p}^j]\cap S\ne \emptyset \), let

$$ \underline{k}^j_S:= \min \{k\in \left\{ 1,\ldots , K_j\}: ~p^j_k\in S\right\} \,{ \text{ and } }\, \bar{k}^j_S:= \max \{k\in \left\{ 1,\ldots , K_j\}: ~p^j_k\in S\right\} . $$

Let \(\mathcal {P}^{s,S}(j)\) be the set of paths to j in the problem \(P^{s,S}\). We can define a reduced path \(\tilde{p}^j \in \mathcal {P}^{s,S}(j)\) (which is of length \(K_j-(\bar{k}^j_S-\underline{k}^j_S)\) if \([\bar{p}^j]\cap S\ne \emptyset \)) as follows.

$$\begin{aligned} \tilde{p}^j=&\bar{p}^j = \left( \bar{p}^j_0, \bar{p}^j_1,\ldots , \bar{p}^j_{K_j}\right)&\,{\text{ if } }\, [\bar{p}^j]\cap S= \emptyset ;\\ \nonumber \tilde{p}^j=&\left( \bar{p}^j_0, \bar{p}^j_{\underline{k}^j_S-1},s, \bar{p}^j_{\bar{k}^j_S+1}, \ldots , \bar{p}^j_{K_j}\right)&\,{\text{ otherwise }}. \end{aligned}$$
(5)

To conclude the proof, remark from (4) and (5) that \(c^{s,S}(\tilde{p}^j)\le c(\bar{p}^j)\); and therefore \( y^d_j(P^{s,S})=x_j \cdot \min _{p^j\in \mathcal {P}^{s,S}(j)}c^{s,S}(p^j)\le x_j \cdot c^{s,S}(\tilde{p}^j)\le x_j \cdot c(\bar{p}^j) = y^d_j(P)\).\(\square \)

We are now ready to state our first characterization result.

Theorem 3.1

The demander rule \(y^d\) is the only CSR that satisfies Merge Proofness and Core Selection.

Proof

We have already proved that \(y^d\) satisfies both properties. Conversely, letting y be a CSR satisfying Merge Proofness and Core Selection, we must show that \(y=y^d\). Let \(P=(N,c,x)\) be an SPP. Since \(y_N(P) = y^d_N(P) = C_P(N)\) (by efficiency of y and \(y^d\)), it is enough to prove that \(y \ge y^d\), i.e., \(y_i \ge y^d_i\) for all \(i\in N\). Fix \(i\in N\). Let \(i'\in U {\setminus } N\) and consider a problem \(P^{\prime }=(N^{\prime },c^{\prime },x^{\prime })\) such that \(N^{\prime } = N \cup \{i^\prime \}\), \(x^{\prime }_j= x_j\) if \(j \in N {\setminus } i\), \(x_i = x^{\prime }_{i} + x^{\prime }_{i^\prime }\) and \(c^{\prime }(j,k) = c(j,k)\) if \(j,k\in N \setminus {i}\), \(c^{\prime }(i,i^\prime )=c^{\prime }(i^\prime ,i)=0\), \(c^{\prime }(i,j)=c^{\prime }(i^\prime ,j) = c(i,j)\) for all \(j\in N{\setminus } i\). For each \(j\in N{\setminus } i\), let \(\bar{p}^j\) be a shortest path to agent j in the problem P; and denote by \(\bar{p}^{\prime {j}}\) the path obtained from \(\bar{p}^j\) by replacing agent i with agent \(i'\) (if \(i\in [\bar{p}^j]\)) and keeping all agents \(k\in [\bar{p}^j]\setminus i\). Then, \(\bar{p}^{\prime {j}}\) is a shortest path to agent j in \(P'\). Hence, by the definition of the demander rule, the minimum cost to satisfy the demands of the agents in \(N\setminus i\) (for either problem P or \(P'\)) is

$$ \Upsilon = \sum _{j\in N{\setminus } i}y^d_j(P) = \sum _{j\in N{\setminus } i}x_jc(\bar{p}^{j})= \sum _{j\in N{\setminus } i} x_j c(\bar{p}^{\prime {j}}) = \sum _{j\in N{\setminus } i}y^d_j(P^\prime ). $$

Under Core Selection,

$$ y_i(P^\prime ) + \sum _{j\in N {\setminus } i}y_j(P^\prime ) \le y^d_i(P^\prime ) + \Upsilon $$

and

$$ y_{i^\prime }(P^\prime ) + \sum _{j\in N {\setminus } i}y_j(P^\prime ) \le y^d_{i^\prime }(P^\prime ) + \Upsilon $$

so that

$$\begin{aligned} y_{i}(P^\prime ) + y_{i^\prime }(P^\prime ) + 2\sum _{j\in N \setminus i}y_j(P^\prime ) \le y^d_{i}(P^\prime ) + y^d_{i^\prime }(P^\prime )+ 2\Upsilon . \end{aligned}$$
(6)

On the other hand, by efficiency,

$$\begin{aligned} y_i(P^\prime ) + y_{i^\prime }(P^\prime ) + \sum _{j\in N \setminus i}y_j(P^\prime ) = y^d_{i}(P^\prime ) + y^d_{i^\prime }(P^\prime )+ \Upsilon . \end{aligned}$$
(7)

Combining (6) and (7),

$$\begin{aligned} \sum _{j\in N \setminus i}y_j(P^\prime ) \le \Upsilon . \end{aligned}$$
(8)

Using Merge Proofness, remark that we must have \(y_j(P)\le y_j(P')\), for all \(j\in N{\setminus } i\); and combining these inequalities with 8 thus gives

$$\begin{aligned} \sum _{j\in N \setminus i}y_j(P)\le \sum _{j\in N \setminus i}y_j(P^\prime ) \le \Upsilon . \end{aligned}$$
(9)

Since \(y_i(P)+\sum \limits _{j\in N {\setminus } i}y_j(P)=C_P(N)=y^d_i(P)+\sum \limits _{j\in N {\setminus } i}y^d_j(P)\) by efficiency of y and \(y^d\), it finally comes from (9) that \(y_i(P)\ge y_i^d(P)\). \(\square \)

The properties in Theorem 3.1 are independent.

  • The average lexicographic value defined in Tijs et al. (2011) satisfies Core Selection and fails Merge Proofness.

  • For each \(P=(N,c,x)\in \mathbb {P}\), let \(M(P) = \{i \in N: x_i = \max _{k\in N}x_k\}\). Consider the CSR \(y^m\) defined as

    $$ y^m_i(P)= \left\{ \begin{array}{cl} \frac{C_P(N)}{|M(P)|} & \,{ \text{ if } }\,i\in M(P) \\ 0 & \,{ \text{ if } }\, i\notin M(P) \end{array} \right. $$

    for each \(P \in \mathbb {P}\). Then, \(y^m\) satisfies Merge Proofness and fails Core Selection.

3.3 Cost solidarity

Our next characterization result will make use of a third axiom, which is formally defined as follows.

Definition 3.4

A CSR y satisfies Cost Solidarity if, for any \(P = (N,c,x)\), \(P^\prime = (N,c',x)\), we have

$$ [c(i,j)\le c^{\prime }(i,j), \forall i,j\in N] \Rightarrow [y_i(P)\le y_i(P^\prime ), \forall i\in N]. $$

In words, Cost Solidarity says that no agent should be better off if the shipping costs increase on some arcs of the network (all else equal).Footnote 1 For instance, recalling Example 2.1, suppose that the cost of shipping one unit from the source to agent 2 increases from \(c(\textbf{0},2)=60\) to \(c'(\textbf{0},2)=90\), with the shipping costs on all other arcs remaining the same. Then Cost solidarity says that no agent should be paying a lower share for the resulting cost matrix \(c'\) than for the initial cost matrix c. Combining Core Selection and Cost Solidarity allows to state the following result.

Theorem 3.2

The demander rule \(y^d\) is the only CSR that satisfies Core Selection and Cost Solidarity.

Proof

It is not difficult to check that \(y^d\) satisfies both Core Selection and Cost Solidarity. Fix a CSR y satisfying Core Selection and Cost Solidarity. We show below that \(y(P)=y^d(P)\) for all \(P\in \mathbb {P}\). We proceed by induction on the size of

$$ \Omega (P) = \left\{ i \in N: c({\textbf {0}},i) > \min _{p\in \mathcal {P}(i)}c(p) \right\} . $$

Assume first \(|\Omega (P)| = 0\), i.e., \(c({\textbf {0}},i) = \min _{p\in \mathcal {P}(i)}c(p)\) for all \(i\in N\). This means it is optimal for each agent i to ship her demand directly from the source. Hence, the associated cooperative game—defined in (1)—is additive. This implies that the core is a singleton. Thus, under Core Selection, we must have \(y(P) = y^d(P)\).

Fix now a problem P satisfying \(|\Omega (P)| = \omega >0\); and assume by induction that \(y(P') = y^d(P')\) whenever \(|\Omega (P')| < \omega \). Let \(i\in \Omega (P)\). This means that \(c(\textbf{0},i) > c(\bar{p}^{i}) = \min _{p\in \mathcal {P}(i)} c(p)\). Consider the problem \(P^{\prime } = (N,c^\prime ,x)\) defined by \( c^{\prime }(\textbf{0},i) = c(\bar{p}^{i}) \) and \(c^{\prime }(j,k) = c(j,k)\) otherwise. Under Cost Solidarity, we deduce \(y_j(P) \ge y_j(P^\prime )\) and \(y^d_j(P) \ge y^d_j(P^\prime )\) for all \(j\in N\). Moreover, \(C_P(N) = C_{P^{\prime }}(N)\) because \(c^\prime (\textbf{0},i) = c^\prime (\bar{p}^{i}) = c(\bar{p}^{i}) = \min _{p\in \mathcal {P}(i)} c(p) = \min _{p \in \mathcal {P}(i)} c^\prime (p)\). Hence, \(y(P) = y(P^\prime )\) and \(y^d(P) = y^d(P^\prime )\). By induction hypothesis, \(y(P^\prime ) = y^d(P^\prime )\), and hence \(y(P) = y^d(P)\). \(\square \)

Observe that the properties used in Theorem 3.2 are independent.

  • The average lexicographic value defined in Tijs et al. (2011) satisfies Core Selection and fails Cost Solidarity.

  • The equal division rule \(y^e\), defined as \(y^e_i(P) = \frac{C_P(N)}{|N|}\) for all \(P\in \mathbb {P}_N\) and all \(i\in N\), satisfies Cost Solidarity and fails Core Selection.