A bankruptcy approach to solve the fixed cost allocation problem in transport systems

Abstract

In this paper, we study the allocation of a fixed cost among different cities involved in a line-shape transport system like a tram line or a railway. The central characteristic of the problem is that the intended cost is not depending on the infrastructure length or the use intensity. Estañ et al. (Ann Oper Res 301(1):81–105, https://doi.org/10.1007/s10479-020-03645-1, 2021) originally introduced the problem and axiomatically studied it. Based on the well-known bankruptcy problem and game, we analyze it by applying two other approaches. First, adding a parameter, we take into account the municipalities revenues in the determination of cost shares. That enables one to transform a fixed cost allocation problem (FCAP) into a well-known bankruptcy one. We propose two bankruptcy problems for FCAP and use the proportional, adjusted proportional, constrained equal awards, constrained equal losses, and Talmud rules to solve it. Then, we define two bankruptcy games corresponding to FCAP and use the Shapley value for cost allocation. The characteristic functions have attractive interpretations; one considers the agents’ minimum desire to contribute to the cost, and the other does their minimum expectation from the overall profit. We investigate presented solutions if they meet some fairness and stability properties. Finally, we apply the suggested approaches to a practical problem.

Appendix

Remark 1

Suppose x be a cost allocation prescribed by the AP, CEA, CEL, or TAL rules or the Shapley value of the bankruptcy game. In that case, it satisfies the null municipality, symmetry, and adjacent symmetry properties. In addition, it violates the additivity, weighted additivity, bilateral ratio consistency, trip decomposition, and no advantageous merging or splitting ones.

Proof

We present proof for the positive statements and counterexample for the negative ones.

• Null municipality

  Consider the municipality i with $\gamma _{gh} =\gamma _{hg} = 0$ for all $s_g \in S_i$ and all $s_h \in S$. Then, $\Gamma _i=0$ and $r_i=0$. The AP, CEA, CEL, and TAL rules satisfy claim boundedness, i.e., $0\le x_i \le r_i$ (Thomson 2003). From the definition of the characteristic function of the bankruptcy game (3), the municipality i is a dummy player ($v(D\cup \{i\})=v(D), \ \forall D\subset N$). The Shapley value satisfies the dummy player property, i.e., $\phi _i(v)=0$. Hence, if x is a cost allocation prescribed by the AP, CEA, CEL, and TAL rules or the Shapley value of the bankruptcy game, then $x_i=0$.

• Symmetry

  The AP, CEA, CEL, and TAL rules satisfy equal treatment of equals (Thomson 2003) that is equivalent to symmetry in the FCAP context. The characteristic function of the bankruptcy game preserves the municipalities symmetry, i.e., symmetric municipalities have the same marginal contributions to the coalitions. Shapley value also satisfies symmetry (Shapley 1953). Hence, the Shapley value of the bankruptcy game satisfies symmetry.

• Adjacent symmetry

  Consider the $fc=(M,S,F,C) \in {{\mathbb {F}}}{{\mathbb {C}}}$. Suppose that there exist $\{i,j\}\subset M$ such that $\gamma _{gh}+\gamma _{hg}=\Gamma (F)$, $|g-h|=1$, $g \in S_i$, and $h \in S_j$. Therefore (a)$\gamma _{lp}=0$ for all $l, p \in S\setminus \{g,h\}$ and (b)$\Gamma _i(F)=\Gamma _j(F)$. (a) shows that each $k \in M\setminus \{i,j\}$, is a null municipality. (b) implies that municipalities i and j are symmetric. Hence, $x_i=x_j=\frac{C}{2}$.

• Additivity and weighted additivity

  Consider $fc = (M, S, F, C)$ with $M = \{ 1, 2, 3 \}$, $S = \{ S_1 = \{s_1\}, S_2 = \{s_2\}, S_3 = \{s_3\} \}$, and the following flow matrix and cost:

  $$\begin{aligned} F=\begin{pmatrix}0 &{}\quad 1&{}\quad 1 \\ 1 &{}\quad 0 &{}\quad 1 \\ 1 &{}\quad 1 &{}\quad 0 \end{pmatrix},\ C=6. \end{aligned}$$

  Then, consider $fc'=(M,S,F',C')$ and $fc''=(M,S,F'',C'')$ with

  $$\begin{aligned} F'=\begin{pmatrix}0 &{}\quad 0&{}\quad 0 \\ 0 &{}\quad 0 &{}\quad 1 \\ 0 &{}\quad 1 &{}\quad 0 \end{pmatrix},\ C'=2,\quad F''=\begin{pmatrix}0 &{}\quad 1&{}\quad 1 \\ 1 &{}\quad 0 &{}\quad 0 \\ 1 &{}\quad 0 &{}\quad 0 \end{pmatrix},\ C''=4. \end{aligned}$$

  Table 10 demonstrates the results for $B=1.5$ showing the violation of the additivity property by the AP, CEA, TAL, and Shapley value. Here and in the following tables in this section, BP stands for bankruptcy problem. Doing some calculation, one can observe that the example also shows that weighted additivity is not met.

• Bilateral ratio consistency

  Consider the $fc = (M,S,F,C)$ where

  $$\begin{aligned} M&=\{1,2,3\}, \\ S&=\{S_1=\{s_1\},S_2=\{s_2, s_3\},S_3=\{s_4\}\},\\ F&=\begin{pmatrix} 0 &{}\quad 2 &{}\quad 3 &{}\quad 1\\ 2 &{}\quad 0 &{}\quad 4 &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad 0 &{}\quad 2\\ 0 &{}\quad 2 &{}\quad 0 &{}\quad 0 \end{pmatrix},\\ C&=11. \end{aligned}$$

  Now, consider the problem $fc' = (M', S', F',C)$ where $M'=\{1,2\}$,$S'=S_1\cup S_2$, $F' = F_{\{1,2\}}$. Table 11 demonstrates the results for $B=0.5$ showing that the requirement of bilateral ratio consistency is not met.

• Trip decomposition

  Let fc be the FCAP of Example 1. Now consider $fc'=(M, S, F', C)$ with $F'$ as the following flow matrix resulted by the decomposition of the two trips from station $s_1$ to $s_3$ to the trips from $s_1$ to $s_2$ and from $s_2$ to $s_3$:

  $$\begin{aligned} F'=\begin{pmatrix} 0 &{}\quad 5 &{}\quad 0 &{}\quad 0 \\ 1 &{}\quad 0 &{}\quad 2 &{}\quad 0 \\ 5 &{}\quad 2 &{}\quad 0 &{}\quad 0\\ 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 \end{pmatrix}. \end{aligned}$$

  Table 12 shows the result for fc and $fc'$ for $B=0.5$ which demonstrate that the Shapley value, AP, CEA, CEL, and TAL do not meet the requirement of trip decomposition.

• No advantageous merging or splitting

  Again let fc be the FCAP of Example 1. Now consider $fc' = (M',S',F,C)$ that differs from fc in the splitting of municipality 2 with two stations into two municipalities with one station; i.e., $M'=\{1,2,3,4\}$ and

  $$\begin{aligned} S'=\{S'_1=\{s_1\},S'_2=\{s_2\},S'_3=\{s_3\},S'_4=\{s_4\}\}. \end{aligned}$$

  Table 13 shows the results for both problems for $B=1$. One can observe that for the AP, CEA, TAL, and the Shapley value, merging is advantageous, and for the CEL, splitting is advantageous.

$\square$

Table 10 Examples for violation of the additivity property by the Shapley value, AP, CEA, CEL, and TAL

Table 11 Examples for violation of the bilateral ratio consistency property by the Shapley value, AP, CEA, CEL, and TAL

Table 12 Examples for violation of the trip decomposition property by the Shapley value, AP, CEA, CEL, and TAL

Table 13 Examples for violation of the no advantageous merging or splitting property by the Shapley value, AP, CEA, CEL, and TAL

Remark 2

If x be a cost allocation prescribed by the PROP rule, it satisfies the null municipality, symmetry, adjacent symmetry, weighted additivity, and no advantageous merging or splitting properties. In addition, it violates the additivity, bilateral ratio consistency, and trip decomposition ones.

Proof

According to the Theorem 1, the proportional rule satisfies null municipality, symmetry, and weighted additivity. We prove that it meets the requirements of no advantageous merging or splitting and adjacent symmetry and give counterexamples for the remaining ones.

• No advantageous merging or splitting

  Consider two FCAPs, $fc=(M, S, F, C)$ and ${fc}'=(M', S', F, C)$ such that $M'\subset M$. Suppose that there is $i \in M'$ such that $S'_i=S_i\cup (\cup _{j \in M\setminus M'}S_j)$, and for each $j\in M'\setminus \{i\}, S'_j=S_j$. It implies that $\Gamma '_i=\Gamma _i + \sum _{j\in M\setminus M'}\Gamma _j$ and $\sum _{j\in M'}\Gamma '_j=\sum _{j\in M}\Gamma _j$. Therefore, we have

  $$\begin{aligned} {\text {PROP}}_i(M', S', F, C)&= \frac{\Gamma '_i}{\sum _{j\in M'}\Gamma '_j}\times C,\\ {}&=\frac{(\Gamma _i + \sum _{j\in M\setminus M'}\Gamma _j)}{\sum _{j\in M}\Gamma _j}\times C,\\ {}&={\text {PROP}}_i(M, S, F, C)+\sum _{j \in M\setminus M'}{\text {PROP}}_j(M, S, F, C). \end{aligned}$$

• Adjacent symmetry

  Consider the $fc=(M,S,F,C) \in {{\mathbb {F}}}{{\mathbb {C}}}$. Suppose that there exist $\{i,j\}\subset M$ such that $\gamma _{gh}+\gamma _{hg}=\Gamma (F)$, $|g-h|=1$, $g \in S_i$, and $h \in S_j$. Therefore (a)$\gamma _{lp}=0$ for all $l, p \in S\setminus \{g,h\}$ and (b)$\Gamma _i(F)=\Gamma _j(F)$. (a) shows that each $k \in M\setminus \{i,j\}$, is a null municipality. (b) implies that municipalities i and j are symmetric. Since the proportional rule satisfies null municipality and symmetry and x is efficient, $x_i=x_j=\frac{C}{2}$.

• Additivity

  Let (M, S, F, C) be the FCAP of Example 1 and consider $(M,S,F',C')$ and $(M,S,F'',C'')$ with

  $$\begin{aligned} F'=\begin{pmatrix}0 &{}\quad 3&{}\quad 0 &{}\quad 0\\ 1 &{}\quad 0 &{}\quad 0 &{}\quad 0 \\ 1 &{}\quad 2 &{}\quad 0 &{}\quad 0\\ 0&{}\quad 0&{}\quad 0&{}\quad 0\end{pmatrix}, C'=7,\quad F''=\begin{pmatrix}0 &{}\quad 1&{}\quad 2 &{}\quad 0\\ 0 &{}\quad 0 &{}\quad 1 &{}\quad 0 \\ 4 &{}\quad 0 &{}\quad 0 &{}\quad 0\\ 0&{}\quad 0&{}\quad 0&{}\quad 0\end{pmatrix}, C''=5. \end{aligned}$$

  Then, we have

  $$\begin{aligned}&{\text {PROP}}(M,S,F,C) = (4.8, 7.2, 0),\\&{\text {PROP}}(M,S,F',C') = (2.5, 4.5, 0),\\&{\text {PROP}}(M,S,F'',C'')= (2.1875, 2.8125, 0). \end{aligned}$$

  One can observe that while $F=F'+F''$ and $C=C'+C''$,

  $$\begin{aligned} {\text {PROP}}(M,S,F,C)\ne {\text {PROP}}(M,S,F',C')+{\text {PROP}}(M,S,F'',C''). \end{aligned}$$

  Note that the prescription of the proportional rule is independent of the value of the parameter B.

• Bilateral ratio consistency

  Consider the $fc=(M,S,F,C)$ where

  $$\begin{aligned} M&=\{1,2,3\}, \\ S&=\{S_1=\{s_1\},S_2=\{s_2\},S_3=\{s_3\}\},\\ F&=\begin{pmatrix} 0 &{}\quad 2 &{}\quad 3 \\ 1 &{}\quad 0 &{}\quad 1 \\ 0 &{}\quad 4 &{}\quad 0 \end{pmatrix},\\ C&=5. \end{aligned}$$

  Then, we have ${\text {PROP}}(fc)=(1.3636, 1.8182, 1.8182)$. Now consider the problem $(\{1,2\},S_1\cup S_2,F_{\{1,2\}}, 5)$. Here, the proportional rule prescribes (2.5, 2.5) for municipalities 1 and 2. Thus, the requirement of bilateral ratio consistency is not met.

• Trip decomposition

  Consider the problems fc and $fc'$ presented in Remark 1 for the trip decomposition item. Then, ${\text {PROP}}(fc) = (4.8, 7.2, 0)$, and ${\text {PROP}}(fc') = (4.4, 7.6, 0)$. One can observe that ${\text {PROP}}(fc)\ne {\text {PROP}}(fc')$ and the trip decomposition is not satisfied.

$\square$