Allocating the fixed cost: an approach based on data envelopment analysis and cooperative game

Abstract

Allocating the fixed cost among a set of users in a fair way is an important issue both in management and economic research. Recently, Du et al. (Eur J Oper Res 235(1): 206–214, 2014) proposed a novel approach for allocating the fixed cost based on the game cross-efficiency method by taking the game relations among users in efficiency evaluation. This paper proves that the novel approach of Du et al. (Eur J Oper Res 235(1): 206–214, 2014) is equivalent to the efficiency maximization approach of Li et al. (Omega 41(1): 55–60, 2013), and may exist multiple optimal cost allocation plans. Taking into account the game relations in the allocation process, this paper proposes a cooperative game approach, and uses the nucleolus as a solution to the proposed cooperative game. The proposed approach in this paper is illustrated with a dataset from the prior literature and a real dataset of a steel and iron enterprise in China.

Appendices

Appendix 1

Theorem 1

Each fixed cost allocation under a common set of weights based on system (9) can satisfy the algorithm of the game cross-efficiency method.

Proof

The cost allocation under a common set of weights is presented as

$$ \begin{array}{*{20}l} {r_{j} = \sum\nolimits_{r = 1}^{s} {u_{r} y_{rj} } - \sum\nolimits_{i = 1}^{m} {v_{i} x_{ij} } ,\quad \forall j} \hfill \\ {\sum\nolimits_{j = 1}^{n} {r_{j} } = v_{m + 1} R} \hfill \\ {r_{j} \ge 0,\quad \forall j} \hfill \\ {u_{r} ,v_{i} \ge 0,v_{m + 1} > 0,\quad \forall r,i.} \hfill \\ \end{array} $$

(A1.1)

Let $\hat{R}_{j} = {{\hat{r}_{j} } \mathord{\left/ {\vphantom {{\hat{r}_{j} } {\hat{v}_{m + 1} }}} \right. \kern-0pt} {\hat{v}_{m + 1} }}\left( {j = 1, \ldots ,n} \right)$ be an allocation associated with $\left( {\hat{u}_{r} ,\hat{v}_{i} ,\hat{v}_{m + 1} } \right)$ in (A1.1), and then $\left( {\hat{u}_{r} ,\hat{v}_{i} ,\hat{v}_{m + 1} ,\hat{R}_{j} = {{\hat{r}_{j} } \mathord{\left/ {\vphantom {{\hat{r}_{j} } {\hat{v}_{m + 1} }}} \right. \kern-0pt} {\hat{v}_{m + 1} }}} \right)$ is a feasible solution to model (4) [or linear model (5)], for it can satisfy all constraints of model (4), such that

$$ \begin{aligned} e_{j} \left( d \right) & = \frac{{\sum\nolimits_{{r = 1}}^{s} {u_{r}^{d} y_{{rj}} } }}{{\sum\nolimits_{{i = 1}}^{m} {v_{i}^{d} x_{{ij}} } + v_{{m + 1}}^{d} R_{j}^{d} }} = \frac{{\sum\nolimits_{{r = 1}}^{s} {\hat{u}_{r} y_{{rj}} } }}{{\sum\nolimits_{{i = 1}}^{m} {\hat{v}_{i} x_{{ij}} } + \left( {\sum\nolimits_{{r = 1}}^{s} {\hat{u}_{r} y_{{rj}} } - \sum\nolimits_{{i = 1}}^{m} {\hat{v}_{i} x_{{ij}} } } \right)}} \\ & = \frac{{\sum\nolimits_{{r = 1}}^{s} {\hat{u}_{r} y_{{rj}} } }}{{\sum\nolimits_{{r = 1}}^{s} {\hat{u}_{r} y_{{rj}} } }} = 1,\quad \forall j. \\ \end{aligned} $$

$$ \sum\limits_{j = 1}^{n} {R_{j} } = \sum\limits_{j = 1}^{n} {\left( {{{\hat{r}_{j} } \mathord{\left/ {\vphantom {{\hat{r}_{j} } {\hat{v}_{m + 1} }}} \right. \kern-0pt} {\hat{v}_{m + 1} }}} \right)} = \sum\limits_{j = 1}^{n} {{{\hat{r}_{j} } \mathord{\left/ {\vphantom {{\hat{r}_{j} } {\hat{v}_{m + 1} }}} \right. \kern-0pt} {\hat{v}_{m + 1} }}} = R. $$

Hence, we have also $e_{j} = \frac{1}{n}\sum\nolimits_{d = 1}^{n} {e_{j} \left( d \right)} = 1,\forall j$ and E ^* _d (d) = 1. It means that $\left( {\hat{u}_{r} ,\hat{v}_{i} ,\hat{v}_{m + 1} ,\hat{R}_{j} = {{\hat{r}_{j} } \mathord{\left/ {\vphantom {{\hat{r}_{j} } {\hat{v}_{m + 1} }}} \right. \kern-0pt} {\hat{v}_{m + 1} }}} \right)$ is an optimal solution to model (4) and we cannot further improve the efficiency for any DMU_j. Then for any smaller enough positive ɛ > 0, we have |e ^t+1 _j  − e ^t _j | = 0 < ɛ. The algorithm of cross-efficiency iterative method terminates.

Note that $\left( {\hat{u}_{r} ,\hat{v}_{i} ,\hat{v}_{m + 1} ,\hat{R}_{j} = {{\hat{r}_{j} } \mathord{\left/ {\vphantom {{\hat{r}_{j} } {\hat{v}_{m + 1} }}} \right. \kern-0pt} {\hat{v}_{m + 1} }}} \right)$ is chosen randomly based on (A1.1), so any fixed cost allocation under a common set of weights based on system (9) can satisfy the algorithm of the cross-efficiency iterative method.□

Appendix 2

Theorem 2

When the algorithm of the game cross-efficiency method terminates, the resulted fixed cost allocation can be generated based on system (9) under a common set of weights.

Proof

It is proven by Du et al. (2014) that, when the cross-efficiency iterative algorithm terminates the optimal cross-efficiency for any DMU_j equals one. Denote the optimal solution to the game cross-efficiency method as $\left( {\hat{u}_{r}^{d*} ,\hat{v}_{i}^{d*} ,\hat{v}_{m + 1}^{d*} ,\hat{r}_{j}^{d*} } \right)$. Based on formula (7) we have

$$ e_{j} = \frac{1}{n}\sum\limits_{d = 1}^{n} {\frac{{\sum\nolimits_{r = 1}^{s} {\hat{u}_{r}^{d*} y_{rj} } }}{{\sum\nolimits_{i = 1}^{m} {\hat{v}_{i}^{d*} x_{ij} } + \hat{r}_{j}^{d*} }} = 1} ,\quad \forall j. $$

(A2.1)

Since the input-oriented d-cross-efficiency is no more than one, it must be that

$$ \frac{{\sum\nolimits_{r = 1}^{s} {\hat{u}_{r}^{d*} y_{rj} } }}{{\sum\nolimits_{i = 1}^{m} {\hat{v}_{i}^{d*} x_{ij} } + \hat{r}_{j}^{d*} }} = 1,\begin{array}{*{20}c} & {\forall d} \\ \end{array} ,j. $$

(A2.2)

$$ {\text{Then}},\;\hat{r}_{j}^{d*} = \sum\limits_{r = 1}^{s} {\hat{u}_{r}^{d*} y_{rj} } - \sum\limits_{i = 1}^{m} {\hat{v}_{i}^{d*} x_{ij} } ,\quad \forall d,j. $$

(A2.3)

Further, we have

$$ \begin{aligned} r_{j} & = \frac{1}{n}\sum\nolimits_{d = 1}^{n} {r_{j}^{d*} } = \frac{1}{n}\sum\nolimits_{d = 1}^{n} {\left( {\sum\nolimits_{r = 1}^{s} {\hat{u}_{r}^{d*} y_{rj} } - \sum\nolimits_{i = 1}^{m} {\hat{v}_{i}^{d*} x_{ij} } } \right)} \\ & = \sum\nolimits_{r = 1}^{s} {\left( {\frac{1}{n}\sum\nolimits_{d = 1}^{n} {\hat{u}_{r}^{d*} } } \right)y_{rj} } - \sum\nolimits_{i = 1}^{m} {\left( {\frac{1}{n}\sum\nolimits_{d = 1}^{n} {\hat{v}_{i}^{d*} } } \right)x_{ij} } ,\quad \forall j. \\ \end{aligned} $$

(A2.4)

Let $u_{r} = \frac{1}{n}\sum\nolimits_{d = 1}^{n} {\hat{u}_{r}^{d*} }$ and $v_{i} = \frac{1}{n}\sum\nolimits_{d = 1}^{n} {\hat{v}_{i}^{d*} }$, then we have system (A2.5).

$$ \begin{array}{*{20}l} {r_{j} = \sum\nolimits_{r = 1}^{s} {u_{r} y_{rj} } - \sum\nolimits_{i = 1}^{m} {v_{i} x_{ij} } ,\forall j.} \hfill \\ {\sum\nolimits_{j = 1}^{n} {r_{j} } = \frac{1}{n}\sum\nolimits_{j = 1}^{n} {\sum\nolimits_{d = 1}^{n} {\hat{r}_{j}^{d*} } } = \frac{1}{n}\sum\nolimits_{d = 1}^{n} {\sum\nolimits_{j = 1}^{n} {\hat{r}_{j}^{d*} } } = \frac{1}{n}\sum\nolimits_{d = 1}^{n} {v_{m + 1} R} = v_{m + 1} R.} \hfill \\ \end{array} $$

(A2.5)

By combining system (A2.5) and the non-negative/positive constraints on variables, we get the same formulation as system (9). Therefore, when the cross-efficiency iterative algorithm terminates, the resulted final fixed cost allocation can be realized under a common set of weights based on system (9).□

Appendix 3

Corollary 1

The optimal cost allocation of the game cross-efficiency method is equivalent to that of the extended proportional sharing method under a common set of weights based on system (9).

Proof

It can be easily proven by combining Theorems 1 and 2.□

Appendix 4

Based on Corollary 1, all cost allocations based on Du et al. (2014) can be represented by system (9). And it can be transformed as follows:

$$ R = {{\left( {\sum\limits_{r = 1}^{s} {u_{r} } \sum\limits_{j = 1}^{n} {y_{rj} } - \sum\limits_{i = 1}^{m} {v_{i} } \sum\limits_{j = 1}^{n} {x_{ij} } } \right)} \mathord{\left/ {\vphantom {{\left( {\sum\limits_{r = 1}^{s} {u_{r} } \sum\limits_{j = 1}^{n} {y_{rj} } - \sum\limits_{i = 1}^{m} {v_{i} } \sum\limits_{j = 1}^{n} {x_{ij} } } \right)} {v_{m + 1} }}} \right. \kern-0pt} {v_{m + 1} }},v_{m + 1} > 0. $$

(A4.1)

In the one dimensional case, the allocation based on Formula (A4.1) is unique and the same as the standard proportional sharing method (Li et al. 2013; Si et al. 2013).

In the general multi-dimensional case, however, the two approaches of Du et al. (2014) and Li et al. (2013) may give multiple allocations, since there exist (m + s + n + 1) variables and (n + 1) equations in system (9). Based on Li et al. (2013) and Si et al. (2013), we present Proposition 1 here to show the non-uniqueness.

Proposition 1

According to the extended proportional sharing method based on system (9):

• (i) The unique allocation can be obtained if the cost allocation problem is a one-dimensional case in which only one output measure is considered, i.e., s = 1 and m = 0;

• (ii) Multiple allocations may be available if and only if m + s > 1.

Proposition 1 can be easily proven using basic results in linear algebra, and here we omit the proof.

Appendix 5

Proposition 2

V(∅) = 0, V(N) = ∑ _j∈SC(j) − R.

Proof

The first part is held automatically. For the second part,

$$ V\left( N \right) = \sum\nolimits_{j \in N} {C\left( j \right)} - C\left( S \right) = \sum\nolimits_{j \in N} {C\left( j \right)} - R \ge 0. $$

Appendix 6

Theorem 3

The characteristic function V(S) satisfies the super-additivity property, i.e., we have$V\left( S \right){ + }V\left( T \right) \le V\left( {S \cup T} \right)$, if S, T ⊆ N and S ∩ T = ∅.

Proof

$$ \begin{aligned} V\left( S \right) + V\left( T \right) & = \sum _{j \in S} C\left( j \right) - C\left( S \right) + \sum _{j \in T} C\left( j \right) - C\left( T \right) \\ & = \sum\nolimits_{j \in S \cup T} {C\left( j \right)} - \left( {C\left( S \right) + C\left( T \right)} \right) \\ \end{aligned} $$

Based on the egoist’s dilemma in Nakabayashi and Tone (2006), we can find that the fixed allocation problem in model (11) would be sub-additive. That is, C(S ∪ T) ≤ C(S) + C(T) for any S, T ⊂ N. As a result, we have

$$ \begin{aligned} V\left( S \right) + V\left( T \right) & = \sum\nolimits_{j \in S \cup T} {C\left( j \right)} - \left( {C\left( S \right) + C\left( T \right)} \right) \\ & \le \sum\nolimits_{j \in S \cup T} {C\left( j \right)} - C\left( {S \cup T} \right) \\ & = V\left( {S \cup T} \right)\quad \forall S,T \subset N,S \cap T = \emptyset \\ \end{aligned} $$

□

Appendix 7

Theorem 4

The cooperative game (N, V) is a balanced game.

Proof

Consider a vector ${\varvec{\uplambda}}$ with n² − 2 nonnegative components λ_S, S ⊆ N, which satisfies that ∑ _j∈S⊆Nλ_S = 1, ∀j ∈ N. Then, according to Shapley (1967) the game (N, V) is said to be balanced if it holds ∑ _S⊆Nλ_SV(S) ≤ V(N).

According to model (11) and Definition 1 on the characteristic function, we have

$$ \begin{aligned} \sum\nolimits_{{S \subseteq N}} {\lambda _{S} V(S)} & = \sum\nolimits_{{S \subseteq N}} {\lambda _{S} \left[ {\sum\nolimits_{{j \in S}} {C\left( j \right)} - C\left( S \right)} \right]} \hfill \\ & = \sum\nolimits_{{S \subseteq N}} {\lambda _{S} \left\{ {\sum\nolimits_{{j \in S}} {C\left( j \right)} - \mathop {\max }\limits_{{\mu _{r} ,w_{i} }} \left[ {\sum\nolimits_{{r = 1}}^{s} {\mu _{r} \left( {\sum\nolimits_{{j \in S}} {y_{{rj}} } } \right)} } \right.} \right.} \hfill \\ & \left. {\left. {\quad - \sum\nolimits_{{i = 1}}^{m} {w_{i} \left( {\sum\nolimits_{{j \in S}} {x_{{ij}} } } \right)} } \right]} \right\} \hfill \\ & = \sum\nolimits_{{S \subseteq N}} {\lambda _{S} \left[ {\sum\nolimits_{{j \in S}} {C\left( j \right)} } \right]} - \sum\nolimits_{{S \subseteq N}} {\lambda _{S} \left\{ {\mathop {\max }\limits_{{\mu _{r} ,w_{i} }} \left[ {\sum\nolimits_{{r = 1}}^{s} {\mu _{r} \left( {\sum\nolimits_{{j \in S}} {y_{{rj}} } } \right)} } \right.} \right.} \hfill \\ &\quad \left. {\left. { - \sum\nolimits_{{i = 1}}^{m} {w_{i} \left( {\sum\nolimits_{{j \in S}} {x_{{ij}} } } \right)} } \right]} \right\} \hfill \\ & \le \sum\nolimits_{{S \subseteq N}} {\lambda _{S} \left[ {\sum\nolimits_{{j \in S}} {C\left( j \right)} } \right]} - \mathop {\max }\limits_{{\mu _{r} ,w_{i} }} \sum\nolimits_{{S \subseteq N}} {\lambda _{S} \left[ {\sum\nolimits_{{r = 1}}^{s} {\mu _{r} \left( {\sum\nolimits_{{j \in S}} {y_{{rj}} } } \right)} } \right.} \hfill \\ &\left. {\quad - \sum\nolimits_{{i = 1}}^{m} {w_{i} \left( {\sum\nolimits_{{j \in S}} {x_{{ij}} } } \right)} } \right] \hfill \\ & = \sum\nolimits_{{S \subseteq N}} {\lambda _{S} \left[ {\sum\nolimits_{{j \in S}} {C\left( j \right)} } \right]} - \mathop {\max }\limits_{{\mu _{r} ,w_{i} }} \left[ {\sum\nolimits_{{r = 1}}^{s} {\mu _{r} \left[ {\sum\nolimits_{{S \subseteq N}} {\lambda _{S} \left( {\sum\nolimits_{{j \in S}} {y_{{rj}} } } \right)} } \right]} } \right. \hfill \\ &\left. {\quad - \sum\nolimits_{{i = 1}}^{m} {w_{i} \left[ {\sum\nolimits_{{S \subseteq N}} {\lambda _{S} \left( {\sum\nolimits_{{j \in S}} {x_{{ij}} } } \right)} } \right]} } \right\} \hfill \\ & = \sum\nolimits_{{j \in N}} {C\left( j \right)\left( {\sum\nolimits_{{j \in S \subseteq N}} {\lambda _{S} } } \right)} - \mathop {\max }\limits_{{\mu _{r} ,w_{i} }} \left\{ {\sum\nolimits_{{r = 1}}^{s} {\mu _{r} \left[ {\sum\nolimits_{{j \in N}} {y_{{rj}} \left( {\sum\nolimits_{{j \in S \subseteq N}} {\lambda _{S} } } \right)} } \right]} } \right. \hfill \\ &\left. {\quad - \sum\nolimits_{{i = 1}}^{m} {w_{i} \left[ {\sum\nolimits_{{j \in N}} {x_{{ij}} \left( {\sum\nolimits_{{j \in S \subseteq N}} {\lambda _{S} } } \right)} } \right]} } \right\} \hfill \\ & = \sum\nolimits_{{j \in N}} {C\left( j \right)} - \mathop {\max }\limits_{{\mu _{r} ,w_{i} }} \left[ {\sum\nolimits_{{r = 1}}^{s} {\mu _{r} \left( {\sum\nolimits_{{j \in N}} {y_{{rj}} } } \right)} - \sum\nolimits_{{i = 1}}^{m} {w_{i} \left( {\sum\nolimits_{{j \in N}} {x_{{ij}} } } \right)} } \right] \hfill \\ & = \sum\nolimits_{{j \in N}} {C\left( j \right)} - R = V\left( S \right). \end{aligned} $$

The above inequality is an immediate result of Nakabayashi and Tone’s (2006) egoist’s dilemma.

Hence, the cooperative game (N, V) is a balanced game.□

Appendix 8

Combine equations in system (9) and equation $\sum\nolimits_{j \in S} {C\left( j \right)} - \sum\nolimits_{j \in S} {z_{j} } - V\left( S \right) = \beta_{1}^{*}$,

$$ {\text{we}}\;{\text{have}}\;C\left( S \right) - \beta_{1}^{*} = \sum _{r} \mu_{r} \sum _{j \in S} y_{rj} - \sum _{i} w_{i} \sum _{j \in S} x_{ij} , \quad \forall S \in \varGamma_{1} . $$

(A8.1)

where μ_r = u_r/v_m+1, v_i = w_i/v_m+1, and R_j = r_j/v_m+1. Apparently, it contains m + s variables (μ_r, w_i, ∀r, i). If n₁ = m + s, we have m + s equations that are reciprocally linearly independent, then the unique solution can be obtained according to theories in Linear Algebra. Accordingly, the fixed cost allocation plan can be uniquely determined, and then the algorithm terminates. If n₁ < m + s, the rank of coefficient matrix is smaller than the number of variables. As a result, there still leaves flexibility in the variables, and we cannot terminate the algorithm but go to step 3. A similar situation occurs in step 4. If n_l = m + s, then we get uniquely determined fixed cost allocation plan and terminate the algorithm, else do until there are m + s linearly independent equations uniquely determining the variables and resulted allocation plan.